{"id":"0dff4e3e-8701-49db-95c8-2b4807198fd7","arxiv_id":"2411.10378","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A two-step negative curvature method is extended to deterministic and stochastic noisy settings with second-order convergence guarantees, plus a practical adaptive-sampling Newton-CG variant.","lead":"This paper designs optimization algorithms that use both descent directions and negative curvature directions to find good solutions in noisy nonconvex problems, and proves they converge to second-order stationary points. It also presents a practical large-scale variant with adaptive sampling and tests it on machine learning problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Hessian accuracy conditions (2.5)/(3.4) collapse to exact information at degenerate second-order points, so the stochastic convergence theorem does not cover finite-sample subsampled Hessians.","rationale":"The reader's verdict is CONDITIONAL, and the weakest assumption is indeed the Hessian accuracy condition. My stress-test sharpens it: it is not only that the allowable error shrinks near a positive semidefinite Hessian; at λ_min=0 the condition forces the approximate Hessian to be positive semidefinite almost surely, which finite-sample random Hessians violate with positive probability. This makes the stochastic second-order convergence theorem inapplicable to the motivating subsampled-Hessian setting at exactly the points of interest. The proof of Lemma 3.8 and Theorem 3.12 is internally coherent under these conditions, so this is a scope limitation rather than a proof error; the deterministic theorem has the analogous issue via (2.5). The practical algorithm is also not covered by the theory, as it uses a different search-direction mechanism and does not verify conditions (3.3)–(3.4). These considerations support the reader's CONDITIONAL verdict rather than suggesting rejection. I agree with the reader's identification of the load-bearing assumption, and the concrete test above would settle whether the stochastic theorem can ever apply to genuinely finite-sample Hessian approximations.","tokens_in":29232,"tokens_out":23300,"duration_ms":201532,"concrete_test":"Take f(x)=½x_2² on R², so ∇²f has eigenvalues {0,1}. Let H_b be the average of b i.i.d. per-sample Hessians of the form ∇²f + diag(η_i,0), where η_i has zero mean and variance σ²>0. Compute or bound P(λ_min(H_b)<0) for finite b; for Gaussian η_i, P(Ση_i<0)=1/2 for every b. Since λ^-_min=0 at x=0, Condition 3.4 demands λ^-_k=0 almost surely, which fails with probability 1/2 for every finite b. This shows Theorem 3.12 cannot apply to finite-sample stochastic Hessian approximations at degenerate second-order stationary points; the same test applies to Condition 2.5 in the deterministic setting with a fixed perturbation δ>0.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The second-order convergence theorems (Theorem 2.10 and Theorem 3.12) rest on Conditions 2.5 and 3.3. In particular, Condition 3.4 requires E[|λ^-_k − λ^-_min,k|] ≤ γ_λ |λ^-_min,k|. When the true Hessian is positive semidefinite, λ^-_min,k = 0, so this forces λ^-_k = 0 almost surely: the subsampled Hessian H_k must have no negative eigenvalues. For any finite sample size, a random subsampled Hessian at a point with a zero curvature direction has positive probability of having a negative smallest eigenvalue (unless the per-sample Hessian has zero variance along that direction). Consequently, Condition 3.4 is incompatible with finite-sample Hessian approximations at exactly the points the theorem aims to characterize, and near such points the condition forces the sample size to grow without bound as |λ^-_min,k|→0. The practical algorithm's adaptive sampling (Section 4.1) uses a fixed θ and a capped growth rate ζ, and it does not enforce (3.3)–(3.4), so the theoretical guarantee does not transfer to Algorithm 4.2. Thus the central stochastic claim is conditional on a Hessian oracle whose accuracy becomes exact in the limit, which undermines the 'inexact Hessian' framing of the paper.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies unconstrained nonconvex optimization with inexact gradient and Hessian information. It proposes a two-step algorithmic framework: a negative curvature step followed by a descent step, analyzed first with deterministic bounded errors and then with stochastic approximations. In the deterministic setting, Theorem 2.10 proves convergence to a second-order stationary point under Conditions 2.3, 2.5, and 2.7 with constant step sizes satisfying (2.8), and Corollary 2.11 gives an O(epsilon_g^{-2} + epsilon_H^{-3}) iteration complexity. In the stochastic setting, Lemma 3.8 provides an expected descent inequality, Theorem 3.10 gives a first-order convergence result under diminishing step sizes and constant variance, and Theorem 3.12 gives an expected second-order convergence result under constant step sizes and diminishing variance. Section 4 develops a practical algorithm, NCAS, combining adaptive sampling, CG with negative curvature detection, and a backtracking line search; Section 5 reports numerical comparisons on two nonconvex machine learning problems.","tokens_in":1476,"tokens_out":3982,"duration_ms":137431,"significance":"The deterministic part of the paper is a solid, clean extension of the two-step negative curvature framework to explicit inexact oracle conditions; the proofs are not circular and the complexity claims match known rates. The practical algorithm is sensible and the numerical study is reasonably thorough. However, the stochastic second-order guarantee rests on a Hessian accuracy condition that finite-sample subsampled Hessians cannot satisfy at exactly the degenerate points the theorem is meant to describe, and the practical algorithm is not shown to enforce the theoretical conditions. Thus Theorem 3.12 is best read as a conditional result for an oracle that is effectively exact near second-order stationary points, and the gap between theory and Algorithm 4.2 is substantial.","major_comments":[{"comment":"At any iterate with lambda^-_min,k = 0, Condition 3.4 reduces to E_k[|lambda^-_k|] <= 0, so lambda^-_k = 0 almost surely. For a finite-sample subsampled Hessian H_k = (1/b_H) sum_i nabla^2 F(x_k, xi_i), this requires the random matrix to have no negative eigenvalue almost surely whenever the true Hessian is positive semidefinite. If the per-sample Hessians have negative curvature along any null-space direction of nabla^2 f(x_k), a finite subsample has positive probability of producing a negative smallest eigenvalue. Therefore Condition 3.4 is not satisfiable by finite-sample Hessians at exactly the second-order stationary points that Theorem 3.12 is intended to characterize. Moreover, near such points, with per-sample curvature variance sigma^2, the condition forces the Hessian sample size to grow at least on the order of sigma^2/(gamma_lambda^2 |lambda^-_min,k|^2), which diverges as lambda^-_min,k tends to zero. The deterministic analogue, Condition 2.5, has the same collapse at lambda^-_min,k = 0. This is load-bearing because the central stochastic second-order convergence claim depends on a Hessian oracle that becomes exact in the degenerate regime.","section":"Section 3.1, Condition 3.4; Theorem 3.12"},{"comment":"The practical algorithm is not connected to the theoretical Conditions 3.3 and 3.4. The adaptive sampling rules (4.5)-(4.9) are designed to enforce (4.3)-(4.4), which control the gradient variance and the Hessian error only along the computed CG step d_k. They do not control the leftmost-eigenvalue gap E[|lambda^-_k - lambda^-_min,k|] appearing in (3.4) nor the Hessian error along the negative curvature direction q_k appearing in (3.3). Algorithm 4.2 never computes lambda_k or checks either condition, and the capped growth rate zeta described in Remark 4.1 explicitly forbids the unbounded sample-size growth that (3.4) demands near degenerate points. Consequently Theorem 3.12 does not apply to Algorithm 4.2, and the numerical results in Section 5, while informative, do not validate the stochastic convergence theorem.","section":"Section 4.1, Eqs. (4.3)-(4.4); Algorithm 4.2"}],"minor_comments":[{"comment":"The hypotheses set hat_theta_k = hat_theta as a constant, but the proof writes hat_theta_k in the line involving (1 + L_g alpha (1 + hat_theta_k)); the notation should be unified. The summability hypotheses are imposed on sigma_k^2 and hat_sigma_k^2, not on hat_theta_k^2.","section":"Theorem 3.12"},{"comment":"In the proof of Corollary 3.14, the implications following the definitions of G(epsilon_g) and H(epsilon_H) mix indices k and k-1 for sigma_k, and the expression '1/4 C beta^2 epsilon_H^3' uses an undefined constant C; the argument is recoverable but should be rewritten for precision.","section":"Corollary 3.14"},{"comment":"The theoretical conditions (4.3)-(4.4) are stated with a sequence theta_k, while Algorithm 4.2 uses a single fixed theta; please clarify whether the analysis of the practical sampling tests is intended for a fixed or a varying accuracy parameter.","section":"Section 4.1"},{"comment":"The numerical experiments appear to report single runs; since SGAS, TRAS, and NCAS are stochastic methods, averaging over several random seeds would strengthen the claims of robustness and efficiency.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the deterministic theory is sound and could stand on its own, but the stochastic second-order theorem as stated is not a theorem about finite-sample subsampled Hessians near degenerate second-order stationary points. I would ask the authors to either relax the target to (epsilon_g, epsilon_H)-second-order stationarity with epsilon_H > 0, or replace Conditions 3.3-3.4 with conditions involving a tolerance or a probability tail that finite-sample Hessians can actually satisfy. The absence of any theoretical link between Algorithm 4.2 and the convergence results is also a serious concern; the numerical section cannot compensate for that gap. This is a fit issue for math.OC because the paper's practical claims are more prominent than the theory currently supports."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Jorge — quick take on 2411.10378. The deterministic half is a clean, honest extension of Curtis-Robinson's two-step framework to inexact oracles. The stochastic theorem is new — expected second-order convergence with O(max{eps_g^{-2}, eps_H^{-3}}) complexity in the diminishing-variance/constant-step regime — but it leans on a Hessian accuracy condition that becomes vacuous exactly at the interesting points.\n\nWhat I liked: the conditions are explicit and the proofs are checkable. Theorem 2.10's descent argument and Lemma 3.8's expectation bound are coherent; I spot-checked the algebra and it holds. The complexity corollaries match exact-information rates up to constants. The practical algorithm is sensible: adaptive sampling, CG with negative curvature detection, and a cautious line search. The experiments, though limited, show NCAS beats first-order adaptive sampling and is competitive with trust-region Newton-CG.\n\nThe soft spots, in order. First, and this is the one to push on: Condition 2.5 and its stochastic version 3.3–3.4 require that when the true Hessian is positive semidefinite (λ^-_min,k = 0), the approximate Hessian H_k have no negative eigenvalues, almost surely in the stochastic case. A finite-sample subsampled Hessian at a degenerate point has positive probability of a negative eigenvalue unless the per-sample Hessian has zero variance along that direction. So the stochastic convergence theorem is really about an oracle whose accuracy becomes exact as λ_min^- → 0, which is not the 'inexact Hessian' story the abstract sells. This is repairable — either weaken the conclusion or modify the condition — but it should be stated plainly. It doesn't sink the deterministic part, where bounded deterministic noise can in principle satisfy the condition if one knows λ_min^-.\n\nSecond, Theorem 3.12's statement is sloppy: θ̂_k is defined as a constant and then the proof uses θ̂_k as a sequence; the limit arguments mix constant and sequence notation. That's easily fixed, but right now it's confusing. Third, Algorithm 4.2 is not covered by the theory — the sampling rules don't enforce (3.3)–(3.4) — so the practical claims are heuristic. No code or seeds either.\n\nBottom line: this paper makes a real, incremental contribution. The deterministic analysis is a solid reference, and the stochastic result is genuinely new. The main theorem is conditional on a strong oracle, and the paper should be pushed to be upfront about that. Send it to a good referee; with the statement cleaned up and the degenerate-case limitation acknowledged, it's worth publishing. I'd probably cite the deterministic framework and use it as a reference for the stochastic conditions.","headline":"Solid extension of Curtis-Robinson to inexact oracles, with a genuinely new stochastic theorem that rests on a Hessian condition so strong it becomes exact at degenerate points.","tokens_in":30071,"tokens_out":3795,"would_cite":true,"duration_ms":35876,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30","90C15","90C53"],"pacs":[],"model":"deepseek-v4-flash","headline":"A two-step method using negative curvature directions reaches second-order stationary points even when gradients and Hessians are only noisy estimates.","keywords":["nonconvex optimization","negative curvature","second-order stationary points","adaptive sampling","stochastic optimization","Newton-CG","inexact Hessian","line search"],"falsifier":"On a function with a known saddle whose Hessian has smallest eigenvalue $-\\delta$ for a tunable small $\\delta$, run the stochastic algorithm from a start near the saddle and record whether the iterates reach a point with $E\\|\\nabla f(x_k)\\|$ small and $E\\lambda_{\\min}(\\nabla^2 f(x_k)) \\ge -\\epsilon_H$; the central claim fails if a non-vanishing fraction of runs stalls with $\\lambda_{\\min}$ below $-\\epsilon_H$, or if the sample size needed to satisfy the Hessian accuracy condition grows without bound as $\\delta \\to 0$. One can also compute the left-hand side and right-hand side of Condition 3.3 on the actual computed directions to check the assumption directly.","tokens_in":29023,"feed_emoji":"🎯","tokens_out":9610,"duration_ms":85524,"temperature":0.7,"pith_summary":"Unconstrained nonconvex optimization problems whose gradients and Hessians are only available as noisy or sampled estimates are common in machine learning, yet most stochastic methods can only promise first-order stationarity. This paper claims that a two-step update, one step along a direction of negative curvature and one descent step, restores second-order guarantees in both a deterministic-inexact and a stochastic setting. Under accuracy conditions that tie the approximate-Hessian error to the true smallest eigenvalue, the iterates converge to points where the gradient vanishes and the Hessian is positive semidefinite, with iteration complexity $O(\\epsilon_g^{-2}+\\epsilon_H^{-3})$. The paper also designs a practical matrix-free Newton-CG variant with adaptive sample sizes, negative-curvature detection inside CG iterations, and a backtracking line search, and reports experiments on two nonconvex regression problems.","feed_headline":"Two-step method hits second-order points with only noisy estimates","feed_subtitle":"Proven iteration counts match exact-information methods; practical Newton-CG runs matrix-free with adaptive sample sizes.","key_machinery":"The load-bearing object is the negative-curvature direction $q_k$, computed from the approximate Hessian $H_k$; it must satisfy $q_k^T H_k q_k \\le \\gamma \\lambda_k \\|q_k\\|_2^2$ with $\\lambda_k$ the leftmost eigenvalue of $H_k$ and $\\|q_k\\|_2=\\delta|\\lambda_k|$, and its sign is chosen so that the final direction $p_k$ is also a descent direction for the approximate gradient. The analysis needs the Hessian approximation to be accurate only along this direction, not in full norm, so the negative-curvature step guarantees a model decrease proportional to $|\\lambda_{\\min,k}^-|^3$ while the descent step contributes decrease proportional to $\\|\\nabla f(\\hat{x}_k)\\|_2^2$. Summing these two decrease mechanisms yields the convergence and complexity theorems; in the stochastic setting the same mechanism is packaged into the expectation inequality of Lemma 3.8, whose two extra error terms determine whether second-order convergence survives.","core_discovery":"The central claim is that the two-step descent-plus-negative-curvature framework extends to inexact deterministic and stochastic settings without losing its second-order convergence order. In the deterministic setting (Theorem 2.10), if the approximate Hessian $H_k$ satisfies the directional error bound $\\|(H_k-\\nabla^2 f(x_k))p_k\\|_2 \\le \\gamma_H |\\lambda_k^-| \\|p_k\\|_2$ and the eigenvalue-gap bound $|\\lambda_k^- - \\lambda_{\\min,k}^-| \\le \\gamma_\\lambda |\\lambda_k^-|$, then choosing constant step sizes $\\alpha \\le (1-\\hat\\theta)^2/(L_g(1+\\hat\\theta))$ and $\\beta \\le (\\gamma-\\gamma_H)/(\\delta L_H)$ makes the iterates either stop at a second-order stationary point or satisfy $\\lim_k \\|\\nabla f(x_k)\\|_2=0$ and $\\liminf_k \\lambda_{\\min}(\\nabla^2 f(x_k)) \\ge 0$. In the stochastic setting with vanishing variance and constant step size, Theorem 3.12 gives the same conclusion in expectation, while with constant variance and diminishing step size Theorem 3.10 only gives $\\liminf_k E[\\|\\nabla f(x_k)\\|_2]=0$. The accompanying corollaries bound the number of iterations needed to reach gradient test $\\epsilon_g$ and curvature test $\\epsilon_H$ by $O(\\epsilon_g^{-2})$ and $O(\\epsilon_H^{-3})$, respectively.","pith_inferences":["Because the analysis controls Hessian error only along the negative-curvature direction rather than in full norm, a natural extension is a Hessian sample-size rule that estimates accuracy along the current most-negative eigen-direction instead of the full matrix; the paper does not test this cheaper rule.","The theory's right-hand sides use the exact eigenvalue magnitude $|\\lambda_{\\min}^-|$, which the algorithm cannot observe; a practical certification would need a confidence interval for the smallest eigenvalue of the true Hessian, a gap the paper leaves open.","As $\\lambda_{\\min}^- \\to 0$ the guaranteed decrease from a negative-curvature step is cubic in this small number, so near a nearly flat saddle the descent step carries the convergence burden; this suggests the adaptive-precision policy could stop growing the Hessian sample size once the negative-curvature contribution is negligible.","The $O(\\epsilon_H^{-3})$ negative-curvature rate is the same order as in exact-information analysis, but faster subspace or accelerated methods might reduce it; testing that would require a different proof and is not addressed here."],"forward_implications":["In the deterministic inexact setting, second-order convergence holds under constant step sizes, with the same $O(\\epsilon_g^{-2}+\\epsilon_H^{-3})$ iteration complexity as exact-information two-step methods.","In the stochastic setting with diminishing variance and constant step size, the expected gradient norm converges to zero and the expected minimum eigenvalue is asymptotically nonnegative, matching the deterministic complexity order in expectation.","With constant variance and diminishing step sizes, only first-order convergence is claimed; the paper does not assert second-order convergence in this regime.","The practical algorithm computes steps with conjugate-gradient iterations that detect negative curvature for free, uses adaptive sample sizes for gradient and Hessian, and sets step sizes by a backtracking line search, so no explicit Hessian or eigendecomposition is required.","Numerical comparisons against a stochastic-gradient adaptive-sampling method, a full-batch Newton-CG method, and a trust-region variant indicate that negative curvature and adaptive sampling reduce total function, gradient, and Hessian evaluations on the tested regression problems."],"supporting_citations":[{"why":"Defines the two-step descent and negative-curvature update that the paper extends to inexact deterministic and stochastic settings; its convergence result is the template for Theorems 2.10 and 3.12.","marker":"[21]"},{"why":"Supplies the Newton-CG method with negative curvature detection and early stopping used as the step-computation subroutine in the practical algorithm.","marker":"[50]"},{"why":"Introduces the norm-based adaptive sampling tests that the paper adapts to choose gradient and Hessian sample sizes.","marker":"[14]"},{"why":"Provides the adaptive step-size and sampling-test framework behind the practical line search and sample-size update rules.","marker":"[9]"},{"why":"Gives the second-order line-search complexity framework and the $(\\epsilon_g,\\epsilon_H)$ stationarity criteria that Corollaries 2.11 and 3.14 match.","marker":"[51]"},{"why":"Proposes a randomized negative-curvature algorithm for inexact evaluations; the paper contrasts its deterministic sign choice with this coin-flipping alternative.","marker":"[38]"},{"why":"States the standard stochastic gradient convergence conditions that Condition 3.5 mirrors, providing the expected-convergence framework for the stochastic analysis.","marker":"[12]"}],"fun_headline_variants":["Inexact two-step method reaches second-order stationarity with noisy gradients","Adaptive sampling plus negative curvature: rigorous second-order guarantees","Noisy nonconvex optimization: second-order convergence proven","Stochastic and deterministic inexact algorithms hit second-order points","Matrix-free Newton-CG with adaptive sampling for second-order convergence"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the approximate Hessian is accurate along the negative-curvature direction and in its leftmost eigenvalue, with both errors bounded by a fixed multiple of the true most-negative eigenvalue magnitude, which vanishes near second-order stationary points and therefore demands near-exact Hessian information exactly where the stopping decision is hardest.","fun_headline_variants_meta":{"raw":{"variants":["Inexact two-step method reaches second-order stationarity with noisy gradients","Adaptive sampling plus negative curvature: rigorous second-order guarantees","Noisy nonconvex optimization: second-order convergence proven","Stochastic and deterministic inexact algorithms hit second-order points","Matrix-free Newton-CG with adaptive sampling for second-order convergence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001624,"raw_usage":{"total_tokens":6481,"prompt_tokens":985,"completion_tokens":5496,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":601,"completion_tokens_details":{"reasoning_tokens":5411}},"tokens_in":601,"tokens_out":5496,"duration_ms":35423,"temperature":1.0,"reasoning_tokens":5411,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T19:42:27.909022+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a function with a known saddle whose Hessian has smallest eigenvalue $-\\delta$ for a tunable small $\\delta$, run the stochastic algorithm from a start near the saddle and record whether the iterates reach a point with $E\\|\\nabla f(x_k)\\|$ small and $E\\lambda_{\\min}(\\nabla^2 f(x_k)) \\ge -\\epsilon_H$; the central claim fails if a non-vanishing fraction of runs stalls with $\\lambda_{\\min}$ below $-\\epsilon_H$, or if the sample size needed to satisfy the Hessian accuracy condition grows without bound as $\\delta \\to 0$. One can also compute the left-hand side and right-hand side of Condition 3.3 on the actual computed directions to check the assumption directly.","supporting_citations":[{"cited_title":"Exploiting negative curvature in deterministic and stochastic optimization","cited_arxiv_id":null,"evidence_quote":"Defines the two-step descent and negative-curvature update that the paper extends to inexact deterministic and stochastic settings; its convergence result is the template for Theorems 2.10 and 3.12."},{"cited_title":"Sample size se- lection in optimization methods for machine learning","cited_arxiv_id":null,"evidence_quote":"Introduces the norm-based adaptive sampling tests that the paper adapts to choose gradient and Hessian sample sizes."},{"cited_title":"Complexity analysis of second-order line- search algorithms for smooth nonconvex optimization.SIAM Journal on Optimization, 28(2):1448–1477, 2018","cited_arxiv_id":null,"evidence_quote":"Gives the second-order line-search complexity framework and the $(\\epsilon_g,\\epsilon_H)$ stationarity criteria that Corollaries 2.11 and 3.14 match."},{"cited_title":"A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees","cited_arxiv_id":"2310.18841","evidence_quote":"Proposes a randomized negative-curvature algorithm for inexact evaluations; the paper contrasts its deterministic sign choice with this coin-flipping alternative."},{"cited_title":"Optimization methods for large- scale machine learning","cited_arxiv_id":null,"evidence_quote":"States the standard stochastic gradient convergence conditions that Condition 3.5 mirrors, providing the expected-convergence framework for the stochastic analysis."}],"review_version":1}