{"id":"264faf85-c0d4-42c2-ac24-40a6fb7ce8e5","arxiv_id":"2607.21258","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Introduces the Goldstein second-order δ-subdifferential for C¹,¹ functions and a Gaussian-smoothing cubic-regularization zeroth-order method that provably finds (ε₁, ε₂, δ)-second-order stationary points under a coercivity growth condition.","lead":"The paper defines a new 'Goldstein second-order' relaxation of the Hessian for functions that are differentiable but not twice differentiable, and proves a derivative-free Gaussian-smoothing algorithm reaches approximate second-order stationarity with an explicit iteration bound. The result matters because many modern nonconvex problems need second-order (saddle-avoiding) guarantees, which previously required twice differentiability.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Moment bound (4.30) is the load-bearing extra assumption: it is not implied by C^{1,1} + bounded-below, and the unknown θ/fMD control the rate exponent, so the 'explicit' complexity is conditional.","rationale":"The paper is a serious theoretical contribution: the Goldstein second-order δ-subdifferential, the Gaussian-smoothing bridge, and the cubic-regularization algorithm are coherent, and the main descent machinery in Lemmas 4.4–4.5 and Theorems 4.1–4.2 checks out. I do not rely on the reader's 'false constant identity': the OCR '3dρ' is more naturally read as 3^{dρ}, under which the disputed equality holds and the T-threshold does ensure ϵ_T<min{5L,1}. The genuine load-bearing issue is the moment bound (4.30). Theorems 4.1–4.2 only give weighted bounds with 1/(1+||x||)^3 denominators; without a bound on the moments of x_{k*}, Lemma 2.2 cannot strip these weights, so the unweighted fractional-moment conclusions of Theorem 4.3 simply do not follow. The sufficient condition (4.39) is a real coercivity assumption, not a consequence of boundedness below, and the theorem gives the user no recipe for θ or fMD. Since the final guarantee is stated for a p-th moment with p=1/(6⌈1/θ⌉), an unknown small θ can make the convergence arbitrarily slow; the abstract's 'mild coercivity-type assumption' and the strongest_claim's phrasing 'merely Lipschitz-differentiable, bounded-below' both overstate what is established. This does not invalidate the paper's framework, but it means the capstone complexity result is conditional on an unquantified growth condition, exactly as the reader's weakest_assumption states. A concrete computational Lyapunov check on a canonical non-coercive smooth function would test whether (4.30) can fail in the claimed problem class; until such a test is done, the conditional verdict is appropriate.","tokens_in":27254,"tokens_out":32865,"duration_ms":325265,"concrete_test":"Analyze f(x)=1-e^{-||x||²} in d=1 (smooth, bounded-below, but failing (4.39) for all θ>0) under Algorithm 1: either obtain a rigorous Lyapunov bound on E[||x_{k*}||^θ] for θ=0.5,0.1, or run a large-scale simulation (T up to 10^6, ≥10^4 seeds) estimating these moments. If the moments grow without bound as T increases, (4.30) is genuinely extra and the 'bounded-below' version of the claim is false; if they remain bounded, then (4.39) is only sufficient and the concern reduces to a quantitative (but still serious) dependence of the rate on θ.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4.3's passage from the weighted guarantees of Theorems 4.1–4.2 to the unweighted stationarity measures is entirely mediated by Lemma 2.2 and the moment bound (4.30): sup_T E[||x_{k*}||^θ] ≤ fMD for some θ>0. This condition is not a consequence of the paper's standing assumptions (f ∈ C^{1,1}, L-Lipschitz gradient, f* > -∞). The stated sufficient condition (4.39) requires polynomial growth f(x) ≥ μ1||x||^θ - μ2; smooth bounded-below functions such as f(x) = -e^{-||x||²} violate (4.39) for every θ>0, and nothing in Lemma 4.5 or Theorems 4.1–4.2 prevents unbounded iterates for such f. Moreover, the final rate contains the exponent 1/(6⌈1/θ⌉) and the prefactor (1+√fMD); the user is not told θ, μ1, μ2, or fMD, and these are not bounded in terms of the problem data. Since smaller θ makes the exponent much smaller (e.g., θ=0.01 gives 1/(600)), the 'mild coercivity' assumption actually sets the rate, not merely the reach of the proof. Thus the strongest_claim's summary 'merely Lipschitz-differentiable, bounded-below nonconvex f' is not supported by Theorem 4.3 as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a Goldstein-type second-order δ-subdifferential ∂²_{G,δ}f for functions in C^{1,1}(R^d), together with the associated notion of (ε1,ε2,δ)-second-order stationary point. It then proposes a zeroth-order algorithm (Algorithm 1) that combines Gaussian smoothing, cubic regularization, a homotopy schedule σ_k = γk^{−ρ}, and increasing sample sizes N_k, J_k. The main results are Theorems 4.1–4.2, which give bounds on the smoothed gradient and smoothed Hessian eigenvalue, and Theorem 4.3, which converts these into guarantees on the original, unsmoothed stationarity measures under an additional moment/coercivity assumption (4.30). The paper claims to provide the first zeroth-order complexity guarantee for approximate second-order stationarity without twice differentiability.","tokens_in":27568,"tokens_out":17372,"duration_ms":132701,"significance":"If the results hold, this is a meaningful contribution: it provides a natural second-order analog of the Goldstein subdifferential and a zeroth-order method with explicit complexity rates for finding points satisfying the new stationarity criterion, under weaker smoothness than the existing Lipschitz-Hessian assumption. The proofs are largely self-contained and the constants are explicit, with no fitted parameters. The main caveats are that the headline guarantee is conditional on an extra moment bound, and that the proof of Theorem 4.3 contains a fixable but load-bearing technical error.","major_comments":[{"comment":"The proof asserts that σ_{k*} ≤ σ_{⌊T/2⌋} = γ(⌊T/2⌋)^{−ρ} ≤ γ3^ρ T^{−ρ} = (dπe)^{−1/2}δ(4L)^{−1/d}ϵ_T^{1/d}. Direct substitution of ϵ_T from (4.33) gives (dπe)^{−1/2}δ(4L)^{−1/d}ϵ_T^{1/d} = (3dρ)^{1/d}γT^{−ρ} (or 3ρ^{1/d}γT^{−ρ} if the intended factor was 3^dρ). This equals γ3^ρT^{−ρ} only for special (d,ρ); for example d=1, ρ=1/2 gives 1.5γT^{−ρ} versus 1.732γT^{−ρ}. Consequently the invocation of Remark 3.2 to obtain (4.32) is not justified as written. This is fixable by redefining ϵ_T (e.g., with factor 3^{ρd} in place of 3dρ or 3^dρ) and adjusting λ3 accordingly, but it is a genuine error in the proof of the main complexity bound.","section":"Theorem 4.3, proof after (4.33)"},{"comment":"The complexity guarantee in Theorem 4.3 is entirely mediated by the moment bound (4.30), which is not a consequence of the standing assumptions (Lipschitz-differentiable, bounded below). The sufficient condition (4.39) fails for natural bounded-below C^{1,1} functions such as f(x) = −e^{−||x||²}. Moreover, the rates in (4.31)–(4.32) contain the exponent 1/(6⌈1/θ⌉) and the prefactor (1+√fMD), and the user is not told θ or fMD in terms of problem data. The paper calls this assumption 'mild', but it controls the quality of the rate, not just the reach of the proof. This should be stated more prominently in the abstract/introduction, and the dependence on θ and fMD should be discussed, ideally with examples or a remark quantifying the degradation for small θ.","section":"§4.2, (4.30)–(4.39)"}],"minor_comments":[{"comment":"The condition on T involves min{5L,1}^{1/d} in the denominator, while the proof refers to 0<ϵ_T<min{5L,1}. Please ensure consistency between the stated T-threshold and the condition used in the proof.","section":"Theorem 4.3 statement"},{"comment":"A few displays have missing norms, e.g., the left-hand sides should involve E_k[||x_{k+1}−x_k||^3] rather than E_k[||x_{k+1}−x_k||^3] without the norm in the text. Please proofread the equations.","section":"Lemma 4.5, equations (4.25)–(4.26)"},{"comment":"The exponent ⌈1/θ⌉ is used throughout Theorem 4.3; a short remark clarifying its behavior for θ>1 (where it equals 1) would improve readability.","section":"Notation"},{"comment":"The sample sizes N_k and J_k are given as ⌈(k+1)^{4/3 β}⌉ and ⌈(k+1)^{2/3 α}⌉; stating that these are not tuned to a target tolerance (the algorithm is anytime) would help the reader.","section":"Algorithm 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is potentially acceptable after a rigorous revision. The false equality in the proof of Theorem 4.3 is a genuine technical error but is readily fixable by redefining ϵ_T and λ3. The moment-bound caveat is more of a presentation/assessment issue: the assumption is explicit, but its strength relative to the claimed 'mild' and 'explicit rate' language should be recalibrated. I recommend major_revision rather than reject, because the central framework and the main proof structure appear sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one. The Goldstein second-order δ-subdifferential and the associated (ε1, ε2, δ)-SOSP are a real framework: they extend second-order stationarity to C^{1,1} in a way that is checkable through Gaussian smoothing, and Theorem 3.2 is the core contribution. The proof machinery in Section 4 up through Theorems 4.1–4.2 is coherent; I did a line-by-line pass on Lemmas 4.4, 4.5, and the descent analysis and found no hidden fitting or circularity. The sample-growth and vanishing smoothing sequence are sensible, and the (1+‖x_k‖)^3 scaling in the subproblem is justified by Remark 4.1. Credit where due: the paper contains no fitted constants, and the imported tail bound from [31] is published and parameter-free.\n\nNow the soft spots. First, the capstone Theorem 4.3 has a real constant bug. After (4.33), the proof uses (3dρ)^{1/d} = 3^ρ to convert the definition of ε_T into the threshold T. That identity is false in general—take d=3, ρ=0.3, where the left side is 2.7 and the right side is 3^0.9 ≈ 2.687. The inequality goes the wrong way, so the stated constants and the threshold are not proven as written. This is mechanical and fixable—redefine ε_T or multiply the threshold by the missing factor—but it has to be fixed.\n\nSecond, the moment bound (4.30) is load-bearing, not just a technical reach. It does not follow from C^{1,1} plus bounded-below: f(x) = −e^{−‖x‖²} is a smooth bounded-below function with Lipschitz gradient and violates the sufficient condition (4.39) for every θ > 0. Theorems 4.1–4.2 do not need it; Theorem 4.3 does, and the unknown θ and fMD enter the rate exponent 1/(6⌈1/θ⌉) and the prefactor. If θ is small, the stated rate is essentially empty. The abstract does say a coercivity-type assumption is used, so the authors are not hiding it, but “mild” understates that this assumption sets the rate.\n\nOverall: the framework is a genuine subfield-level advance for zeroth-order non-twice-differentiable optimization, and the parts I checked support the conceptual claims. The capstone needs a corrected constant and a more honest statement of what the moment bound buys. Send it to serious peer review—a good referee will pin the authors to fix Theorem 4.3 and clarify the rate dependence on θ.","headline":"Genuinely new C^{1,1} second-order stationarity framework with a sound core analysis, but Theorem 4.3 has a false constant identity and a load-bearing moment bound that controls the rate.","tokens_in":28280,"tokens_out":4331,"would_cite":true,"duration_ms":43040,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C56","90C26","49J52","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces a Goldstein-style second-order stationarity criterion for functions that are only once differentiable with locally Lipschitz gradients, and proves that a zeroth-order algorithm using Gaussian smoothing and cubic regula","keywords":["zeroth-order optimization","Goldstein second-order δ-subdifferential","Gaussian smoothing","cubic regularization","homotopy method","Lipschitz differentiable functions","second-order stationarity","iteration complexity"],"falsifier":"Take the one-dimensional C^{1,1} function f(x)=x²/2 for x≥0 and x²/4 for x<0, which has Lipschitz gradient but no second derivative at 0, and run Algorithm 1 with fixed γ, ρ, α, β. The theorem predicts E[|∇f(x_{k*})|^{1/(6⌈1/θ⌉)}] decays like T^{−ρ} (here θ=2) and the curvature measure like T^{−dρ} + T^{−(1−2ρ)/3}; fit the empirical rates over T = 10² to 10⁵. A rate much slower than predicted, or a failure to decrease, would show the complexity claim is false or not tight. Separately, evaluate Theorem 3.2(ii) at x=0 for this f, where fσ''(0)=3/4 for every σ, to check the bridge on a non-twice-","tokens_in":26955,"feed_emoji":"🎯","tokens_out":14423,"duration_ms":142642,"temperature":0.7,"pith_summary":"The paper asks whether second-order stationarity can be meaningfully defined and algorithmically reached when the objective is not twice differentiable. It answers yes by defining the Goldstein second-order δ-subdifferential, the convex hull of all generalized Hessians on a δ-ball, and the associated notion of (ε1, ε2, δ)-second-order stationary points for C^{1,1} functions. The central bridge is a new connection between the Hessian of the Gaussian-smoothed function and this Goldstein subdifferential, which requires only Lipschitz differentiability, not Lipschitz Hessian. On that bridge, the paper builds a function-value-only algorithm with growing Monte Carlo sample sizes and a vanishing smoothing parameter, and proves iteration complexity for reaching such points under a coercivity-type moment bound. If correct, this gives the first complexity guarantee for approximate second-order stationarity in a derivative-free setting without assuming twice differentiability.","feed_headline":"Value-only method provably finds second-order critical points","feed_subtitle":"For functions with just Lipschitz gradients, it gives explicit convergence rates to a new Goldstein-style stationarity.","key_machinery":"The load-bearing object is the Goldstein second-order δ-subdifferential, a tractable surrogate for the pointwise generalized Hessian. Its algorithmic partner is the bridge theorem (Theorem 3.2), which shows that for σ at most an explicit threshold, −2ε + λ_min(∇²fσ(x)) lower-bounds inf_{||h||=1} s(h, ∂²_{G,δ} f(x) h). This transfers negative curvature from the smoothed Hessian, which can be estimated by function-value samples, to the original function's generalized Hessian. The cubic subproblem with the (1+||x_k||)³ scaling provides descent and Hessian-feasibility through its first- and second-order optimality conditions, while Lemma 2.2 converts bounds for the smoothed function into bounds","core_discovery":"For a continuously differentiable function with locally Lipschitz gradient and bounded-below values, the paper defines the Goldstein second-order δ-subdifferential ∂²_{G,δ}f(x) = conv(∪_{y∈B(x,δ)} ∂²_H f(y)) and calls x an (ε1, ε2, δ)-second-order stationary point when ||∇f(x)|| ≤ ε1 and inf_{||h||=1} s(h, ∂²_{G,δ} f(x) h) ≥ −ε2. The paper proves that the Hessian of the Gaussian smoothing fσ admits a derivative-free expectation formula and, for σ below an explicit threshold, its minimum eigenvalue lower-bounds the Goldstein second-order curvature. Algorithm 1 estimates ∇fσ and ∇²fσ from centered function-value differences, solves a cubic-regularized subproblem with a (1+||x_k||)³ scaling, le","pith_inferences":["Editorial inference: the moment bound (4.30) is doing more work than the word 'mild' suggests. Theorems 4.1 and 4.2 control only the smoothed quantities, and it is Lemma 2.2 that promotes those to guarantees for the original f; if (4.30) fails, or holds only with very small θ, the stated complexity of Theorem 4.3 either says nothing or degrades severely because the final exponents are 1/(6⌈1/θ⌉).","Editorial inference: the rates contain a built-in trade-off. Since ρ ∈ (0,1/2), choosing ρ close to 1/2 improves the T^{−ρ} gradient term but pushes the T^{−(1−2ρ)/3} curvature term toward a constant rate; no single parameter choice makes both measures converge quickly.","Editorial inference: the stationarity notion averages generalized Hessians over a δ-ball, so a point can pass the criterion while having a negative-curvature direction of width smaller than δ. A natural testable extension is to let δ shrink adaptively with T, which would make the smoothed-Hessian proxy approximate the pointwise generalized Hessian as the iteration count grows."],"forward_implications":["Any bounded-below objective with Lipschitz continuous gradient can be optimized to approximate second-order stationarity using only function evaluations; no gradients or Hessians are ever queried.","The user does not need to pre-specify a target accuracy: the smoothing parameter decreases and sample sizes increase automatically, giving an a priori iteration bound in terms of T.","The Gaussian-smoothing Hessian is a valid computational proxy for the Goldstein second-order subdifferential under Lipschitz differentiability alone, widening the class of functions for which second-order guarantees are available.","When the coercivity condition f(x) ≥ μ1||x||^θ − μ2 holds, the complexity statement applies to the original objective, not merely to the smoothed one.","The framework extends derivative-free second-order stationarity guarantees from twice-differentiable functions with Lipschitz Hessian to the larger class C^{1,1}."],"fun_headline_variants":["Value-only method nails Goldstein second-order stationarity","Zeroth-order cubic regularization reaches Goldstein SOSP","No gradients needed for second-order critical points","Gaussian smoothing unlocks derivative-free Goldstein Hessian","Explicit rates to Goldstein second-order stationarity"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof needs the iterates to have a bounded θ-th moment: sup_T E[||x_{k*}||^θ] < ∞ for some θ > 0; the paper offers f(x) ≥ μ1||x||^θ − μ2 as a sufficient condition, but θ and the constants are not specified, and if the bound fails the convergence guarantees apply only to the smoothed function, not the original.","fun_headline_variants_meta":{"raw":{"variants":["Value-only method nails Goldstein second-order stationarity","Zeroth-order cubic regularization reaches Goldstein SOSP","No gradients needed for second-order critical points","Gaussian smoothing unlocks derivative-free Goldstein Hessian","Explicit rates to Goldstein second-order stationarity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000113,"raw_usage":{"total_tokens":855,"prompt_tokens":651,"completion_tokens":204,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":395,"completion_tokens_details":{"reasoning_tokens":133}},"tokens_in":395,"tokens_out":204,"duration_ms":3202,"temperature":1.0,"reasoning_tokens":133,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T08:02:40.645914+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the one-dimensional C^{1,1} function f(x)=x²/2 for x≥0 and x²/4 for x<0, which has Lipschitz gradient but no second derivative at 0, and run Algorithm 1 with fixed γ, ρ, α, β. The theorem predicts E[|∇f(x_{k*})|^{1/(6⌈1/θ⌉)}] decays like T^{−ρ} (here θ=2) and the curvature measure like T^{−dρ} + T^{−(1−2ρ)/3}; fit the empirical rates over T = 10² to 10⁵. A rate much slower than predicted, or a failure to decrease, would show the complexity claim is false or not tight. Separately, evaluate Theorem 3.2(ii) at x=0 for this f, where fσ''(0)=3/4 for every σ, to check the bridge on a non-twice-","supporting_citations":[],"review_version":1}