{"id":"3234a6a8-85aa-4fec-aaeb-53fb4cfaee3b","arxiv_id":"2505.07143","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Subgradient regularization builds stable descent directions for nonsmooth marginal functions, provably converges to stationary points, and recovers the prox-linear method as a special case.","lead":"This paper introduces a unified framework of descent-oriented subdifferentials for nonsmooth optimization and a new technique, subgradient regularization, to construct descent directions from a single point. For composite convex-smooth objectives the method reduces to the prox-linear update and inherits local linear convergence under standard regularity conditions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 8's contradiction proof contains a false '→0' limit, and Corollary 1 overstates the descent constant; both are repairable, so the conditional accept stands.","rationale":"I read the paper in good faith. The central architecture is coherent: descent-oriented subdifferentials provide a clean abstract framework, subgradient regularization is a genuine construction, Proposition 7 correctly links the method to prox-linear updates, and Theorem 2 gives subsequential convergence under mild assumptions. The numerical experiments support the practical value. The weakest point is the local-linear-convergence chain, specifically Proposition 8 and its dependence on Corollary 1. The proof as written contains a false limit assertion and an overstated descent constant; both are localized and easily corrected, so they do not overturn the paper's contribution. The reader's weakest_assumption focused on the convexity of S(x) and the strength of metric subregularity; I agree those limit the scope, but they are stated assumptions rather than hidden gaps. My concern is a different, more technical soft spot in the linear-rate proof, hence partial agreement. Since the flaws are repairable and the empirical regime uses a small Armijo parameter, the conditional-accept verdict remains appropriate.","tokens_in":38193,"tokens_out":39506,"duration_ms":351733,"concrete_test":"Re-derive the passage in Appendix B.2 with the exact bound: show LHS of (47) ≤ D·sqrt((3Lβε_{k,i_k}+2)κ̄_x + 2ε_{k,i_k}) + o(1), which is bounded for fixed κ̄_x, and verify that the RHS of (47) diverges because ε_{k,i_k}≥min{ε_{k,0},1/(4Lβ)}. Separately, derive the sharp descent coefficient from Lemma 6 for η=ε, obtaining f(x−εg)≤f(x)−ε(1/2−Lβε/2)||g||²; then test whether Proposition 8 still holds for α=0.5 or other α∈(0,1), and identify the exact admissible range of α for the uniform lower bound on ε_{k,i_k}.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The local-linear-convergence claim (Corollary 2) rests on Proposition 8 (eventual constant stepsize). In the proof of Proposition 8 (Appendix B.2), after bounding the left-hand side of (47), the text asserts that the bound tends to 0 along N'. This is incorrect: combining the metric-subregularity error bound (48) with Lemma 8 gives an upper bound of the form D·sqrt((3Lβ ε_{k,i_k}+2)κ̄_x + 2ε_{k,i_k}), whose limit is D·sqrt(2κ̄_x), generally a nonzero constant. The contradiction with (47) still works, because the right-hand side of (47) diverges to +∞ while the left-hand side remains bounded; thus the flaw is a gap in the written argument rather than a fatal logical break. A second issue in the same chain: Corollary 1 asserts f(x−εg)≤f(x)−ε||g||² for all ε≤1/(2Lβ), but Lemma 6 supports only f(x−εg)≤f(x)−ε(1/2−Lβε/2)||g||². Consequently, line search acceptance with η=ε requires α≤1/2−Lβε/2 (at ε=1/(2Lβ), this is α≤1/4), so the statement 'given α∈(0,1)' in Proposition 8 is too permissive. Since the experiments use α=10⁻⁴ and the subsequential convergence (Theorem 2) is independent of these constants, the central numerical and structural claims are unaffected.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a unified framework for nonsmooth descent methods based on \"descent-oriented subdifferentials,\" set-valued maps G(x,ε) satisfying the two conditions (G1) and (G2) in Definition 1. It shows that Goldstein-type and bundle-type constructions fit this framework, and it proves a general subsequential convergence result (Algorithm 1, Theorem 1). The main algorithmic contribution is subgradient regularization for marginal functions, defined through the regularized inner problem (P_ε), and the resulting direction is shown to be a descent-oriented subdifferential in several structured cases (Lemmas 2-4). For composite problems f(x)=h(c(x)), Proposition 7 proves that the regularized direction coincides with the prox-linear step, giving a new dual interpretation. An adaptive variant (Algorithm 2) is shown to be subsequentially convergent (Theorem 2) and, under metric subregularity and Assumption 1, locally linearly convergent (Corollary 2). Numerical experiments on finite max/min of quadratics, Nesterov's nonsmooth Chebyshev-Rosenbrock function, and a parametric marginal problem illustrate the practical behavior of the methods against gradient sampling, bundle, BFGS, and LiPsMin baselines.","tokens_in":38514,"tokens_out":24598,"duration_ms":242488,"significance":"If the technical gaps identified below are repaired, this is a solid and useful contribution. The abstract framework (G1)-(G2) cleanly captures the common mechanism behind Goldstein and bundle methods and is likely to be reused by other authors. The subgradient-regularization construction is simple, depends on no fitted parameters, and its reduction to the prox-linear update is an exact mathematical equivalence rather than a heuristic analogy. The paper also provides a public code repository and reproducible pseudocode for both algorithms. The subsequential convergence arguments are largely self-contained, and the empirical comparison on challenging nonsmooth problems is informative. The main reservations concern the local-linear-convergence proof, where two local but load-bearing slips in Corollary 1 and Proposition 8 need correction before the rate result can be accepted as stated.","major_comments":[{"comment":"The proof asserts that, after combining the metric-subregularity error bound (48) with Lemma 8 and dividing by ||g_{k,i_k}||^{1/2}, the resulting upper bound on tilde-epsilon_k ||tilde-g_k|| / ||g_{k,i_k}||^{1/2} tends to 0 along N'. This is not what the estimates give. Lemma 8 together with (48) only yields an upper bound of the form D * sqrt((3L*beta*epsilon_{k,i_k}+2)*kappa_{bar x} + 2*epsilon_{k,i_k}), whose limit is D*sqrt(2*kappa_{bar x}), which is generally nonzero. The contradiction with the divergence of the right-hand side of (47) still works, because the left-hand side remains bounded while the right-hand side diverges, so the claim of Proposition 8 is salvageable; however, the written proof contains an incorrect limit and must be corrected.","section":"Appendix B.2, proof of Proposition 8, equations (47)-(48)"},{"comment":"Corollary 1 states that f(bar-x - epsilon*g) <= f(bar-x) - epsilon*||g||^2 for every epsilon in (0, 1/(2L*beta)]. This is stronger than Lemma 6 supports: setting y=bar-x in (27) gives f(bar-x - epsilon*g) <= f(bar-x) - epsilon*(1 - L*beta*epsilon/2)*||g||^2. Consequently, the statement in the proof of Proposition 8 that \"given alpha in (0,1), any epsilon in (0, 1/(2L*beta)] with stepsize eta=epsilon ensures the descent condition\" is not justified. For eta=epsilon to be accepted one needs alpha <= 1 - L*beta*epsilon/2; at epsilon=1/(2L*beta) this restricts alpha to at most 3/4. The proof can be repaired by replacing the lower bound 1/(4L*beta) with (1-alpha)/(L*beta), so the local linear convergence result can survive, but the theorem as stated is too permissive.","section":"Section 5.1, Corollary 1, and Section 5.2.2, Proposition 8"}],"minor_comments":[{"comment":"In the definition of Y_epsilon(x), the term \"h^*(x)\" should presumably be \"h^*(y)\"; as written it is a typo that makes the objective dimensionally inconsistent.","section":"Section 4.1, Example 4"},{"comment":"The singleton property of G(x,epsilon) is stated without proof and only attributed to [45, 34]. Since this property is used in the analysis of the composite case, the paper should either include a short self-contained argument or state explicitly which result in those references is being invoked.","section":"Section 4.1, Lemma 3(a)"},{"comment":"The proof of Lemma 4 is only a sketch. In particular, estimates (35)-(36) are asserted without derivation, and the verification that G(.,epsilon) is closed-valued and locally bounded in the two cases is not spelled out. A fuller proof, or at least a precise pointer to the parallel argument in Lemma 2, would help the reader verify the extension to varying feasible sets.","section":"Appendix A.2, proof of Lemma 4"},{"comment":"The letter epsilon is used both for the regularization parameter and for the radius of the neighborhood around bar-x, which is confusing. Renaming one of the two quantities would improve readability.","section":"Appendix B.1, proof of Lemma 5"}],"recommendation":"major_revision","confidential_remarks":"The two major comments are localized and fixable: the incorrect limit in Appendix B.2 can be replaced by a boundedness argument, and the descent coefficient in Corollary 1 can be corrected at the cost of a slightly smaller uniform stepsize lower bound in Proposition 8. The numerical experiments use alpha=1e-4, which is compatible with the corrected inequality, so the empirical claims are not affected. The central framework and the prox-linear equivalence appear sound. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper is legitimate and worth sending out. The descent-oriented subdifferential abstraction is genuinely useful as a unifying lens for Goldstein and bundle methods, and the subgradient-regularization construction is a clean, new way to build stable descent directions from a single point. The equivalence with the prox-linear method for composite problems is a nice byproduct, and it is derived, not assumed. The convergence theorems are backed by detailed proofs, the code is available, and the numerical comparison is honest.\n\nThe soft spots are real but repairable. In the proof of Proposition 8, the asserted ‘→0’ limit after combining the metric-subregularity error bound with Lemma 8 is wrong: the bound tends to a generally nonzero constant. The contradiction still works because the right side of (47) diverges, so the argument can be fixed. Also, Corollary 1 claims f(x−εg) ≤ f(x)−ε||g||² for all ε ≤ 1/(2Lβ), but Lemma 6 only gives coefficient (1/2 − Lβε/2), so the line-search acceptance with a general α∈(0,1) is too permissive. Since the experiments use α=1e−4 and the subsequential convergence results do not depend on these constants, neither gap breaks the central claims. A smaller issue: Lemma 3(a) is outsourced to [45,34]; that is fine as a citation but should be a full proof in a self-contained paper.\n\nThe main structural limitation is that the subgradient-regularized G satisfies (G2) only when the active gradient set S(x) is convex, which holds for affine-in-y cases like finite max/min and composites, but not for general marginal functions. This is stated plainly rather than hidden. The metric subregularity and Assumption 1 are strong, but they are standard for linear-rate results of this type.\n\nWho gets value: anyone working on first-order methods for nonsmooth optimization, especially composite problems. It is a serious contribution and I would send it to referees. Conditional accept with a requirement to fix the two proof issues and tighten Corollary 1.","headline":"Solid framework paper with repairable gaps in the linear-rate proof; deserves refereeing.","tokens_in":38986,"tokens_out":1944,"would_cite":true,"duration_ms":19962,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["49J52","90C30","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Subgradient regularization adds a squared-norm penalty to the inner maximization of a nonsmooth marginal function, producing stable descent directions that provably reach stationary points; for composite problems it recovers the…","keywords":["nonsmooth optimization","subgradient regularization","descent-oriented subdifferential","prox-linear method","marginal functions","linear convergence","Clarke subdifferential","bundle methods"],"falsifier":"Compute G from (15) for the marginal function f(x)=max_{θ∈[0,2π]}(x₁ cos θ+x₂ sin θ), whose active-gradient set at x=0 is the unit circle and therefore nonconvex, and check whether lim sup_{x→0, ε↓0} G(x,ε) equals the minimal-norm subgradient at each point. Lemma 2(d) only guarantees property (G2) when the active-gradient set is convex; if any non-minimal vector survives in that outer limit, the claim that subgradient regularization defines a descent-oriented subdifferential for a broad class of marginal functions would be false for this class, while if none appears, the convexity hypothesis is sufficient but not necessary.","tokens_in":37993,"feed_emoji":"📉","tokens_out":17995,"duration_ms":184459,"temperature":0.7,"pith_summary":"This paper sets out a unifying principle for nonsmooth descent: a set-valued map G(x,ε) is a usable oracle if, as the smoothing scale ε shrinks, it sees only Clarke subgradients at the limit (G1) and collapses to the minimal-norm subgradient at each point (G2). On top of that principle, the paper introduces subgradient regularization, which perturbs the inner maximization of a marginal function by subtracting (ε/2) times the squared norm of the candidate gradient, and shows this produces such a map for finite maxima and minima of smooth functions and for composites h(c(x)). The resulting SRDescent algorithm makes a monotone descent step using only objective values and gradients at the current point, provably converges subsequentially to stationary points, and, in the composite case, is exactly the prox-linear update. A sympathetic reader would care because the framework also reveals gradient-sampling and bundle-type methods as two instances of the same abstract recipe, and the composite specialization inherits local linear convergence under standard regularity conditions.","feed_headline":"Regularized subgradients give nonsmooth optimization provable descent","feed_subtitle":"A squared-norm penalty stabilizes minimal subgradients, unifies bundle and gradient-sampling methods, and reduces to the prox-linear update.","key_machinery":"The central object is the descent-oriented subdifferential G: R^n×(0,∞)⇒R^n, a closed-valued, locally bounded set-valued map whose joint limit as (ε,x) shrinks toward a point stays inside the Clarke subdifferential (G1) and whose limiting directions equal the minimal-norm subgradient as ε↓0 (G2). The engine that builds such a map for marginal functions is the subgradient-regularized problem Y_ε(x)=argmax_{y∈Y}[φ(x,y)−(ε/2)‖∇_x φ(x,y)‖²], with G(x,ε) collecting ∇_x φ(x,y) for y∈Y_ε(x). Lemma 2 shows this G verifies (G1) and the outer-semicontinuity part of (G2) generally, and verifies the full (G2) when the active-gradient set S(x) is convex, which Lemma 3 obtains when ∇_x φ is affine in the inner variable y, covering finite max/min functions and, via Fenchel duality, composites h(c(x)). Proposition 7 then identifies x−εG(x,ε) with the prox-linear update, giving Algorithm 2 a dual interpretation as a regularized dual selection.","core_discovery":"On its own terms, the paper claims that the failure of steepest descent in nonsmooth optimization, where an arbitrary negative subgradient can point uphill, is cured by a small regularization of the subgradient selection. For a marginal function f(x)=max_{y∈Y} φ(x,y), the paper replaces the inner maximization with the regularized problem max_{y∈Y}[φ(x,y)−(ε/2)‖∇_x φ(x,y)‖²] and uses the gradients of φ at the regularized maximizers as search directions. The set G(x,ε) of such directions satisfies the two defining properties of a descent-oriented subdifferential: its outer limit as (x,ε) approaches a point stays inside the Clarke subdifferential, and its limit as ε↓0 is the minimal-norm subgradient. This yields a deterministic descent method with a backtracking line search and subsequential convergence to stationary points for locally Lipschitz functions bounded below. For the composite f(x)=h(c(x)), the construction is shown to coincide with the prox-linear step, and an adaptive version that keeps the effective stepsize bounded away from zero converges locally linearly whenever ∂f is metrically subregular at the stationary points in the level set and Assumption 1 holds.","pith_inferences":["Inference: the convexity of the active-gradient set required by Lemma 2(d) may be sufficient rather than necessary; testing G in (15) on a marginal function whose active-gradient set is a nonconvex arc, such as f(x)=max_θ(x₁ cos θ+x₂ sin θ), would show whether the technique extends beyond the paper's proof.","Inference: reading the prox-linear update as a squared-norm-penalized subgradient selection suggests a general tuning rule in which ε balances the dual penalty against model error, potentially giving adaptive rates beyond the paper's ratio test.","Inference: the same construction should extend to the strongly concave inner-problem case of Section 4.2 when a multiplier oracle is unavailable; a variant based on strong second-order sufficient conditions may be practical.","Inference: the experiments on the finite-min-of-quadratics, which is not subdifferentially regular at cusps, hint that the framework may tolerate some nonregularity; studying convergence under relaxed regularity is a natural next step."],"forward_implications":["Every algorithm built on any descent-oriented subdifferential inherits Theorem 1: subsequential convergence to stationary points for any locally Lipschitz function bounded below.","Subgradient regularization yields an implementable oracle: for finite maxima and minima of smooth functions, eigenvalue functions, distributionally robust objectives, and composites h(c(x)), the needed inner problem is a convex, often quadratic, program solvable using data at the current point.","For h(c(x)), the regularized direction equals the prox-linear step, so the method inherits the existing error-bound analysis of prox-linear methods; under metric subregularity of ∂f and Assumption 1, Algorithm 2 converges locally linearly in both function values and iterates.","Because the direction avoids neighborhood sampling and bundled history, the method needs only one-point first-order information, which in experiments lets it keep descending where gradient sampling stalls on failed line searches."],"supporting_citations":[{"why":"introduces the neighborhood-union enlarged subdifferential and its minimal-norm direction, the prototype instance of the new framework.","marker":"[22]"},{"why":"supplies the descent-inequality lemma (Lemma 1) that converts bounded descent into subsequential stationarity in Theorems 1 and 2.","marker":"[27]"},{"why":"provides the two-sided model and error-bound machinery for prox-linear methods that Lemma 6 and Corollary 2 adapt.","marker":"[17]"},{"why":"supplies the variational-analysis toolkit (outer semicontinuity, projection continuity, marginal-function Lipschitzness) used throughout the proofs.","marker":"[43]"},{"why":"establishes joint continuity and local boundedness of the convex ε-subdifferential needed for the bundle-type descent-oriented subdifferential in Proposition 4.","marker":"[1]"},{"why":"gives Danskin's theorem identifying the Clarke subdifferential of the marginal function, which underlies the form of G in (15).","marker":"[10]"},{"why":"supplies the marginal-function calculus under constraint qualifications for the varying-feasible-set constructions in Lemma 4.","marker":"[21]"},{"why":"the gradient-sampling algorithm that the paper interprets as a randomized instance of the neighborhood-union construction and compares against numerically.","marker":"[8]"}],"fun_headline_variants":["No more uphill subgradients: a simple regularization fix","Regularized subgradients: a guaranteed descent direction","A tiny penalty makes subgradients descend in nonsmooth problems","Subgradient regularization: descent guaranteed for nonsmooth optimization","Unifying bundle and sampling methods with one subgradient trick"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the regularization to be a full descent-oriented subdifferential the proof needs the set of active gradients S(x) to be convex, and the paper obtains this only when the inner function's x-gradient is affine in the auxiliary variable, which covers finite maxima, finite minima, and composites h(c(x)) but excludes general marginal functions; for the linear-rate corollary it additionally assumes metric subregularity of ∂f at every stationary point in the level set and a positive separation between stationary points with different values.","fun_headline_variants_meta":{"raw":{"variants":["No more uphill subgradients: a simple regularization fix","Regularized subgradients: a guaranteed descent direction","A tiny penalty makes subgradients descend in nonsmooth problems","Subgradient regularization: descent guaranteed for nonsmooth optimization","Unifying bundle and sampling methods with one subgradient trick"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000766,"raw_usage":{"total_tokens":3431,"prompt_tokens":1015,"completion_tokens":2416,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":631,"completion_tokens_details":{"reasoning_tokens":2334}},"tokens_in":631,"tokens_out":2416,"duration_ms":18137,"temperature":1.0,"reasoning_tokens":2334,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:24:02.049788+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute G from (15) for the marginal function f(x)=max_{θ∈[0,2π]}(x₁ cos θ+x₂ sin θ), whose active-gradient set at x=0 is the unit circle and therefore nonconvex, and check whether lim sup_{x→0, ε↓0} G(x,ε) equals the minimal-norm subgradient at each point. Lemma 2(d) only guarantees property (G2) when the active-gradient set is convex; if any non-minimal vector survives in that outer limit, the claim that subgradient regularization defines a descent-oriented subdifferential for a broad class of marginal functions would be false for this class, while if none appears, the convexity hypothesis is sufficient but not necessary.","supporting_citations":[{"cited_title":"Optimization of Lipschitz continuous functions","cited_arxiv_id":null,"evidence_quote":"introduces the neighborhood-union enlarged subdifferential and its minimal-norm direction, the prototype instance of the new framework."},{"cited_title":"Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization","cited_arxiv_id":null,"evidence_quote":"supplies the descent-inequality lemma (Lemma 1) that converts bounded descent into subsequential stationarity in Theorems 1 and 2."},{"cited_title":"Error bounds, quadratic growth, and linear con- vergence of proximal methods","cited_arxiv_id":null,"evidence_quote":"provides the two-sided model and error-bound machinery for prox-linear methods that Lemma 6 and Corollary 2 adapt."},{"cited_title":"Variational Analysis, volume 317","cited_arxiv_id":null,"evidence_quote":"supplies the variational-analysis toolkit (outer semicontinuity, projection continuity, marginal-function Lipschitzness) used throughout the proofs."},{"cited_title":"Gradients of convex functions","cited_arxiv_id":null,"evidence_quote":"establishes joint continuity and local boundedness of the convex ε-subdifferential needed for the bundle-type descent-oriented subdifferential in Proposition 4."},{"cited_title":"Generalized gradients and applications","cited_arxiv_id":null,"evidence_quote":"gives Danskin's theorem identifying the Clarke subdifferential of the marginal function, which underlies the form of G in (15)."},{"cited_title":"Differential properties of the marginal function in mathematical programming","cited_arxiv_id":null,"evidence_quote":"supplies the marginal-function calculus under constraint qualifications for the varying-feasible-set constructions in Lemma 4."},{"cited_title":"A robust gradient sampling algorithm for nonsmooth, nonconvex optimization","cited_arxiv_id":null,"evidence_quote":"the gradient-sampling algorithm that the paper interprets as a randomized instance of the neighborhood-union construction and compares against numerically."}],"review_version":1}