{"id":"17831656-94be-48d5-882f-1530cdf93626","arxiv_id":"2607.24122","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A randomized first-order algorithm computes Goldstein approximate second-order stationary points of L-smooth nonconvex functions with oracle complexity Õ(ΔL⁸n²/ε⁹ + ΔL⁶n³/ε⁷).","lead":"The paper gives a randomized algorithm that, using only gradient evaluations of a smooth nonconvex function, provably reaches an approximate second-order stationary point in the Goldstein sense. The result matters because it turns a deterministic-hard problem into a tractable randomized one, and it extends to weakly convex and bilevel optimization.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Prop 4.7 silently assumes ξr⋆² ≤ ε_g, i.e. r⋆≤1, but Algorithm 2 defines r⋆ without that cap; for r⋆>1 the claimed stationarity guarantee can fail.","rationale":"The reader identified the r⋆ scaling issue as a mechanical inconsistency in Prop 4.7, and that is the most load-bearing concern I find: it directly invalidates the proof of the full theorem as stated. However, the headline equal-tolerance complexity is claimed for ε small and L≫1, a regime where r⋆ is automatically below 1, so the main contribution likely survives with a small repair (cap r⋆ at 1 or add the small-ε hypothesis). The exact-global-minimizer concern is real but standard for cubic-regularization analyses; the lack of an output/selection rule is also addressable by stopping at the first r_k≤r⋆ once the r⋆ issue is fixed. These are conditional-acceptance issues rather than reasons to reject the approach. Hence the reader's CONDITIONAL verdict stands unchanged.","tokens_in":32670,"tokens_out":33757,"duration_ms":294486,"concrete_test":"Analytical/1D simulation: set n=1, ε1=ε2=δ=1, and choose L so small that σ=1 and ξ=cL < 16εg/17 ≈ 0.314, hence r⋆>1. Take f(x)=μx²/2 with 0<μ≤L, and choose x0 satisfying μ|x0| = r(μ+ξr/2) at r=r⋆. The cubic subproblem minimizer is p=−sign(x0)r, so ∥p∥=r≤r⋆ but |∇fσ(x0+p)|=ξr²/2. For instance with L=10^{-3}/c, ξ≈10^{-3}, r⋆≈313, giving |∇fσ(x0+p)|≈49 > ε_g=1/3. Recompute the same example with r⋆ capped at 1 (or with ε small and L≫1) and verify the stationarity bound is restored.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 2 sets r⋆ := min{16εg/(17ξ), 24εH/(37ξ)}. In the proof of Prop 4.7, after finding k⋆ with r_{k⋆} ≤ r⋆, Lemma 4.6 gives ∥∇fσ(x_{k⋆+1})∥ ≤ α + δr + ξr² ≤ 17ξr⋆²/16. The proof then asserts this is ≤ ε_g. But ξr⋆² ≤ 16εg r⋆/17, so ξr⋆² ≤ ε_g requires r⋆ ≤ 17/16; the second term in the definition of r⋆ does not enforce this. When r⋆>1, the conclusion can fail badly. For example, for a quadratic fσ(x)=μx²/2, the cubic subproblem minimizer satisfies ∇fσ(x+p)=−ξrp/2 (with r=∥p∥), so a point with r=r⋆ has gradient norm ξr⋆²/2. If ε_g is comparable to ξr⋆, this is of order ε_g r⋆, which can exceed ε_g by an arbitrary factor. Thus the iterate identified by the proof's r≤r⋆ stopping criterion need not be an ε_g-stationary point, so Theorem 4.2 and Theorem 4.1 are not proven as stated. This is an internal proof gap, not merely a modeling assumption: the descent argument only guarantees the existence of some r≤r⋆, and Lemma 4.6 cannot convert that into the claimed stationarity without the missing cap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a randomized first-order method for computing Goldstein approximate second-order stationary points of L-smooth (not necessarily twice differentiable) functions. The method applies uniform randomized smoothing to obtain a function f_σ with Lipschitz Hessian, estimates the gradient and Hessian of f_σ via first-order sampling, and then runs a cubic-Newton-type method with high-probability concentration bounds. The main result is an oracle complexity Õ(ΔL⁸n²/ε⁹ + ΔL⁶n³/ε⁷) in the regime ε₁,ε₂,δ ≍ ε. The paper also defines a Moreau-envelope notion of Goldstein SOSPs for weakly convex functions, proves a second-order stationarity correspondence, and sketches applications to nonconvex-strongly-convex and nonconvex-(Polyak–Łojasiewicz) bilevel programs.","tokens_in":33067,"tokens_out":19748,"duration_ms":173414,"significance":"If the central theorem can be made fully correct, the paper would provide the first randomized upper bound for computing Goldstein second-order stationary points of L-smooth functions, complementing a deterministic lower bound and extending second-order smoothing ideas from [71]. The smoothing calculus in Theorem 3.1, the gradient/Hessian concentration estimates, and the Moreau-envelope second-order correspondence are potentially useful tools. The paper is careful with measure-theoretic details and gives self-contained proofs of the main smoothing identities. Its main limitations are the dependence on exact global solutions of the cubic subproblem, the existential nature of the iterate guarantee, and a missing condition in the proof of Proposition 4.7 that currently leaves the main theorem unproven as stated.","major_comments":[{"comment":"The definition r⋆ := min{16εg/(17ξ), 24εH/(37ξ)} is inconsistent with the proof of Proposition 4.7. The proof asserts 17ξr⋆²/16 ≤ εg, but the first component only gives ξr⋆² ≤ (16εg/17)r⋆, which implies the desired inequality only when r⋆ ≤ 17/16. The second component does not enforce this. Thus the unconditional gradient bound in Prop 4.7 is not established, and Theorem 4.1 is not proven as stated. The general K⋆ display in Theorem 4.1 (first term ∆L^{1/2}n^{1/4}/(σ^{1/2}εg^{3/2})) appears to assume r⋆ ≈ (εg/ξ)^{1/2}, further confirming the inconsistency. Please fix the definition, e.g., r⋆ := min{√(16εg/(17ξ)), 24εH/(37ξ)}, or add an explicit r⋆≤1 hypothesis and update the batch sizes, complexity display, and proof accordingly.","section":"Algorithm 2, Step 1; Proposition 4.7; Theorem 4.1"},{"comment":"The claimed application to NC–P/Łojasiewicz bilevel programs is left incomplete. Algorithm 5 requires Prox_{hp/(2ρ)}, but the paper says the evaluation 'allows us to apply the zeroth-order algorithm in [93]' and then 'leave[s] the details to interested readers.' No oracle complexity or accuracy analysis is given for this proximal computation, so Corollary 5.13 is conditional on an unspecified subroutine. Since this is presented as one of the paper's applications, the missing analysis should either be supplied or the claim should be explicitly marked as a heuristic extension.","section":"Section 5.2.2 and Algorithm 5"}],"minor_comments":[{"comment":"The guarantee is existential: the proof shows that some k⋆ satisfies the stationarity conditions, but no stopping criterion or certificate is provided. A short discussion of how the user is supposed to identify such an iterate would strengthen the 'computing' language.","section":"Theorem 4.1 and Algorithm 2"},{"comment":"The algorithm requires an exact global minimizer of the cubic subproblem (4). Lemma 4.4 relies on global optimality. The paper cites polynomial-time solvability, but a brief discussion of inexact subproblem solves and their effect on Lemma 4.4/Prop 4.7 would be useful, especially since the algorithm is otherwise first-order.","section":"Algorithm 2, Step 5"},{"comment":"K⋆ is defined using Δ = fσ(x0) − min fσ, which may not be known a priori. The paper should state how Δ is obtained or how the analysis extends to an unknown Δ (e.g., doubling).","section":"Theorem 4.1 and Algorithm 2"},{"comment":"The claim ∂²_C f(0)=∅ follows because f''(y)→+∞ rather than having finite cluster points; a parenthetical explanation would avoid confusion.","section":"Example 5.2"},{"comment":"The proposed definition of Goldstein SOSPs for weakly convex functions depends on the Moreau parameter 1/(2ρ). It would help to state explicitly that this is a new definition and to discuss its sensitivity to the choice of λ.","section":"Section 5.1, Definition 5.7"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is plausible and the missing-sqrt issue is local, but it is load-bearing and should be fixed before publication. The deterministic lower bound motivating the paper is cited to an unpublished manuscript [48]; the editors may wish to verify that this reference is available and peer-reviewed. The bilevel application in Section 5.2.2 is advertised but relies on an undeveloped subroutine; this should be addressed in revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this is a genuine new technique, second-order randomized smoothing, and the first randomized polynomial-complexity algorithm for Goldstein SOSPs of L-smooth functions. The transfer property (Prop 3.8), the divergence-theorem Hessian estimator (Prop 3.3), and the Moreau-envelope second-subderivative equality (Prop 5.4) are real contributions, and the proofs are careful. The bilevel extensions are broad but mostly definitional; the weakly convex notion is new and justified by the exact-stationarity coincidence in Cor 5.3.\n\nThe soft spot the stress-test note identifies is real. In Prop 4.7, the bound ∥∇fσ(x_{k⋆+1})∥ ≤ (17/16)ξ r⋆² ≤ ε_g is asserted, but with r⋆ = min{16ε_g/(17ξ), 24ε_H/(37ξ)}, you only get ξr⋆² ≤ (16/17)ε_g r⋆. To close the inequality you need r⋆ ≤ 1, or a sqrt in the definition. The quadratic example checks out: for r⋆ > 1 the gradient at the exit point can be ~ξ r⋆²/2, which can exceed ε_g arbitrarily if ε_g is large relative to ξ. This is a mechanical fix — replace the first term with sqrt(16ε_g/(17ξ)) — and it does not perturb the headline equal-tolerance complexity, since there r⋆ is already O(ε²/(L²√n)) ≪ 1. But Theorem 4.1/4.2 as currently stated is not proven.\n\nThe reader's 'no verification mechanism' complaint is less serious than made out: r_k = ∥p_k∥ is computed, so stopping at the first index with r_k ≤ r⋆ identifies the good iterate. The paper should say that. The exact-solution requirement for the cubic subproblem is a standard oracle assumption; an inexact-solve analysis would be welcome but is not a flaw in the complexity model. The NC–P/Lojasiewicz section leans heavily on [18], partly a self-citation, but that's a legitimate dependence, not circularity.\n\nThe central architecture is sound. This deserves a serious referee. I'd engage — ask for a revision fixing r⋆ and stating the stopping rule.","headline":"Real new technique with one mechanical proof gap in the main theorem; fix the r⋆ scaling and this is a strong paper.","tokens_in":33519,"tokens_out":12009,"would_cite":true,"duration_ms":93154,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30","49J52"],"pacs":[],"model":"deepseek-v4-flash","headline":"A randomized first-order algorithm computes Goldstein approximate second-order stationary points of L-smooth functions, with oracle complexity Õ(n²/ε⁹ + n³/ε⁷), by smoothing the function and applying cubic Newton.","keywords":["randomized smoothing","Goldstein subdifferential","second-order stationary points","nonsmooth nonconvex optimization","cubic Newton method","weakly convex functions","bilevel optimization","oracle complexity"],"falsifier":"Check whether the stated r⋆ in Algorithm 2 satisfies r⋆ ≤ 1; if not, the inequality 17ξr⋆²/16 ≤ ε_g used in Proposition 4.7 is not guaranteed, and a function attaining these parameters would invalidate the proof.","tokens_in":32567,"feed_emoji":"🎯","tokens_out":7958,"duration_ms":62867,"temperature":0.7,"pith_summary":"Second-order stationarity—vanishing gradient plus a curvature nonnegativity condition—is the standard way to escape saddle points in nonconvex optimization, but for nonsmooth functions even defining a second-order critical point is delicate, and deterministic algorithms hit a fundamental barrier. This paper shows the barrier is not fatal: randomizing the smoothing radius turns any function with Lipschitz gradient into a twice-differentiable function with Lipschitz Hessian, and stationarity of the smoothed function transfers to a Goldstein-style second-order stationarity of the original. Then a cubic regularization method applied to the smoothed function finds such a point in Õ(n²/ε⁹ + n³/ε⁷) first-order oracle calls, with high probability. The same smoothing machinery extends to weakly convex functions via their Moreau envelopes and to bilevel programs, where it removes a third-differentiability assumption.","feed_headline":"Smoothing makes nonsmooth second-order stationary points computable","feed_subtitle":"A first-order randomized method finds Goldstein-approximate second-order critical points in Õ(n²/ε⁹ + n³/ε⁷) gradient calls.","key_machinery":"The workhorse is the Goldstein generalized Hessian ∂²_δ f(x) = conv(∪_{y∈x+δBⁿ} ∂²_C f(y)) — the convex hull of Clarke Hessians in a δ-ball — together with the second-order randomized smoothing identity ∇²f_σ(x) = (n/σ) E_{s∼Unif(Sⁿ)}[∇f(x+σs)sᵀ], which lets the Hessian of the smoothed function be estimated from gradient values alone. The cubic subproblem min_p pᵀg + ½pᵀHp + (ξ/6)‖p‖³, whose global minimizers satisfy H + λI ⪰ 0 with λ = ξ‖p‖/2, provides the descent mechanism.","core_discovery":"The central discovery is a second-order transfer theorem: for an L-smooth f and its uniformly smoothed version f_σ(x)=E_{u∼Unif(Bⁿ)}[f(x+σu)], ∇²f_σ is Lipschitz with constant O(L√n/σ), and moreover ∇f_σ(x)∈∂_σ f(x) and ∇²f_σ(x)∈∂²_σ f(x), the Goldstein subdifferential and generalized Hessian. Consequently, any (ε_g,ε_H)-second-order stationary point of f_σ with ε_g=ε₁/3, ε_H=ε₂ and σ≤min{δ,ε₁/(3L)} is an (ε₁,ε₂,δ)-Goldstein approximate SOSP of f. Algorithm 1 runs cubic Newton on f_σ, estimating its gradient and Hessian by finite differences of ∇f along random directions, and returns the desired point with probability 1−η.","pith_inferences":["If the exact-cubic-solver assumption can be relaxed to an inexact solve with controlled error, the algorithm would become directly usable with standard trust-region or Lanczos-based cubic solvers; the paper does not provide such an analysis.","The Moreau-envelope stationarity coincidence (Corollary 5.3) suggests a general recipe: define second-order stationarity for nonsmooth functions through an L-smooth surrogate, which could reshape landscape analyses for nonsmooth deep learning objectives.","The Hessian estimator built only from gradient differences might be adapted to zeroth-order (function-value-only) settings, where similar concentration bounds would yield practical derivative-free second-order methods — an extension the paper does not explore.","The dimension dependence n³/ε⁷ in the Hessian-estimation term suggests that the true bottleneck is the variance of Hessian estimates; sharp variance reduction, e.g., via control variates or importance sampling, could materially improve the complexity."],"forward_implications":["With probability at least 1−η, Algorithm 1 returns an (ε₁,ε₂,δ)-Goldstein approximate SOSP of any L-smooth function using only first-order oracle calls; complexity is Õ(ΔL⁸n²/ε⁹ + ΔL⁶n³/ε⁷) when ε₁,ε₂,δ ≍ ε.","The same algorithm computes Goldstein approximate SOSPs of ρ-weakly convex functions once the Moreau envelope and its proximal map are available (Corollary 5.8).","For nonconvex–strongly-convex bilevel programs it yields second-order guarantees without third-order differentiability of the lower-level problem (Corollary 5.11).","For nonconvex–PŁ bilevel programs it applies through the weak-convexity route (Corollary 5.13).","The paper conjectures that no dimension-free randomized algorithm exists for this task, and its framework may be extended to trilevel optimization."],"fun_headline_variants":["Randomized smoothing computes Goldstein second-order stationary points","First-order randomized method for second-order stationary points","Smoothing enables second-order stationarity for nonsmooth problems","Compute approximate SOSPs with smoothing and cubic Newton","Randomized smoothing yields Goldstein SOSPs efficiently"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The algorithm requires an exact global minimizer of the cubic subproblem at every iteration; with only an approximate subproblem solution the model-decrease lemma fails and the proof gives no guarantee.","fun_headline_variants_meta":{"raw":{"variants":["Randomized smoothing computes Goldstein second-order stationary points","First-order randomized method for second-order stationary points","Smoothing enables second-order stationarity for nonsmooth problems","Compute approximate SOSPs with smoothing and cubic Newton","Randomized smoothing yields Goldstein SOSPs efficiently"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000669,"raw_usage":{"total_tokens":2854,"prompt_tokens":681,"completion_tokens":2173,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":425,"completion_tokens_details":{"reasoning_tokens":2100}},"tokens_in":425,"tokens_out":2173,"duration_ms":13176,"temperature":1.0,"reasoning_tokens":2100,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T22:58:07.417754+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check whether the stated r⋆ in Algorithm 2 satisfies r⋆ ≤ 1; if not, the inequality 17ξr⋆²/16 ≤ ε_g used in Proposition 4.7 is not guaranteed, and a function attaining these parameters would invalidate the proof.","supporting_citations":[],"review_version":1}