{"id":"a5c417fc-be55-42ba-866c-e36d69e1e510","arxiv_id":"2505.04807","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"A new adaptive Newton method with negative curvature steps achieves near-optimal complexity for nonconvex optimization using only local Hessian Lipschitz smoothness.","lead":"This paper introduces a new second-order optimization algorithm, AN2CLS, and proves it finds approximate first-order stationary points in at most O(|log ε| ε^{-3/2}) iterations under only a local Lipschitz smoothness assumption on the Hessian. A variant for second-order critical points is also analyzed, and experiments on CUTEst problems show the method is competitive with existing second-order solvers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; AS.4 is global but explicitly assumed and correctly used.","rationale":"The reader's weakest-assumption identification, AS.4, is exactly the point where the proof most depends on a global quantity. I agree that without AS.4 the |log ε| term in the complexity bound is not controlled and the proof of Lemma 2.4 fails. However, this is an explicit assumption of the theorem, and the proof uses it correctly. I independently spot-checked the main algebraic steps: the derivation of Lemma 2.4's gradient-ratio bound, the role of σ_k ≤ κ_max/ε in the decrease arguments, and the verification of Assumption 0 for both the exact and Krylov step computations. No internal inconsistency emerged. The paper's presentation could more prominently emphasize that AS.4 is a separate global restriction on nonconvexity rather than part of the local smoothness condition, but this is a scope/completeness remark, not a correctness objection. Therefore the reader's ACCEPT verdict should stand unchanged.","tokens_in":627,"tokens_out":24797,"duration_ms":564854,"concrete_test":"Independently re-derive the proof of Lemma 2.3, checking every occurrence of L_0/‖g_k‖ + L_1, and verify that the bound σ_k ≤ κ_max/ε covers all of them using ‖g_k‖ ≥ ε and ε ≤ 1. If the computation reproduces (2.6)–(2.7) without a hidden missing power of ε, the complexity chain from Lemma 2.3 through Theorem 2.5 is intact.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I reviewed the main complexity proof for internal consistency. The central bound in Theorem 2.5 is obtained by combining Lemma 2.3, which gives σ_k ≤ κ_max/ε, with Lemma 2.4, which bounds the number of gradient-decreasing successful iterations. The only assumption that is both global and essential is AS.4: it is used in Lemma 2.4 to bound μ_k by κ_B/θ. This use is valid, because from (1.19) we have u_k^T H_k u_k ≤ −θ μ_k, and since λ_min(H_k) ≤ u_k^T H_k u_k, AS.4 gives θ μ_k ≤ κ_B. Without AS.4 the negative-curvature gradient-growth ratio would be uncontrolled and the |log ε| factor would fail; however, AS.4 is an explicit hypothesis of Theorem 2.5, not an unstated one. I also checked the power analysis: Lemma 2.3's bound σ_k ≤ κ_max/ε correctly absorbs the L_0/‖g_k‖ terms, and the decrease arguments in Theorem 2.5 then correctly yield ε^{-3/2} factors. The Krylov implementation Lemma 4.2 also correctly verifies Assumption 0. I did not find a load-bearing logical gap in the proof as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes AN2CLS, an adaptive second-order method for unconstrained nonconvex optimization that alternates between regularized Newton steps and negative-curvature steps. Its main contribution is a worst-case complexity bound of O(|log ε| ε^{-3/2}) iterations for finding a first-order ε-stationary point under a local Hessian Lipschitz condition (AS.3) rather than the usual global Lipschitz Hessian assumption. The step computation is abstracted through Assumption 0, and two implementations are given: one using exact linear algebra (AN2CLSE) and one based on nested Krylov subspaces (AN2CLSK). A second-order variant, SOAN2CLS, is also analyzed and claimed to have complexity O(ε1^{-3/2} + ε2^{-3}) for finding (ε1,ε2)-second-order critical points. Numerical experiments on CUTEst problems compare the proposed methods with AN2C, AR2, and TR2 variants.","tokens_in":26466,"tokens_out":31672,"duration_ms":280423,"significance":"If the main theorem stands, the paper makes a valuable contribution: it shows that the fast second-order complexity O(ε^{-3/2}) up to a logarithmic factor is achievable without global Hessian Lipschitz continuity, replacing it by a local smoothness condition that covers polynomials and exponentials. The abstract Assumption 0 formulation cleanly separates the convergence analysis from the linear-algebra implementation, and the explicit attention to inexact Krylov solves is practically relevant. The numerical study is honest in scope and shows the new method is competitive. However, the significance is tempered by two correctness gaps: the proof of the second-order variant (Theorem 3.1) appears to rely on an invalid implication, and the Krylov implementation's validity is not established for the full stated parameter range.","major_comments":[{"comment":"The bound ∥g_{p_i}∥ ≤ κ_gpi is derived from condition (3.4), but (3.4) is a conjunction: REJECT is set only if ρ_k < η1 AND ∥∇f(x_k+s_k)∥ > κ_{k,hess}. An accepted second-order step with ρ_k ≥ η1 is not subject to the gradient bound, so the proof does not establish the claimed bound on the gradient at the start of the next first-order phase. This is load-bearing for Theorem 3.1; either the acceptance condition must be changed to reject on the disjunction (ρ_k < η1 OR gradient exceeds the threshold), or a separate argument must bound ∥g_{p_i}∥ for accepted second-order steps with ρ_k ≥ η1.","section":"Appendix B, Lemma B.3"},{"comment":"The assertion that 'since θ≤1, u_p can be chosen as the negative curvature of T_p' is false. Condition (4.10) requires u_p^T T_p^2 u_p ≤ λ_min(T_p)^2/(2θ^2), and for a unit vector satisfying u_p^T T_p u_p ≤ θ λ_min(T_p) with λ_min(T_p)<0 one has u_p^T T_p^2 u_p ≥ (u_p^T T_p u_p)^2 ≥ θ^2 λ_min(T_p)^2. For θ>2^{-1/2} these two inequalities can be incompatible; for example, with T_p = diag(-1,-0.9) and θ=0.8, no unit vector satisfies both. Lemma 4.2 therefore proves Assumption 0 for StepcompK only for a restricted range of θ (the numerical choice θ=1/2 is safe), not for all θ∈(0,1] as stated. The condition in Step 4 should be revised or θ restricted.","section":"Section 4.2, StepcompK Step 4 and Lemma 4.2"},{"comment":"The displayed lower bound in (2.1) is algebraically incorrect. Solving the quadratic inequality in the proof gives ∥s_trial∥ ≥ (√(a^2+Y)-a)/(√σ Y) with Y=(L0/∥g∥+L1)/σ, not the expression in (2.1). As printed, (2.1) is false; for instance, take a=1 and Y=4, where the correct bound gives a smaller value than the printed one by a factor of 4. The subsequent sufficient condition (2.2) is nevertheless correct, so the main complexity proof can be repaired by correcting (2.1), but the lemma as stated is not a valid theorem.","section":"Lemma 2.1, Eq. (2.1)"}],"minor_comments":[{"comment":"The phrase 'optimal O(|log ε| ε^{-3/2})' is inaccurate: since the known lower bound is Ω(ε^{-3/2}), the stated bound is within a logarithmic factor of optimal, as the authors correctly note later in the paper. The abstract should be reworded to avoid claiming optimality.","section":"Abstract"},{"comment":"Equation (1.4) has a stray superscript '⊺' after 's⊺∇²f(x)s'; the intended expression is f(x+s)-f(x)-s^T∇f(x)-½s^T∇²f(x)s.","section":"Section 1, Eq. (1.4)"},{"comment":"In the negative-curvature case, the passage from terms like κ_C μ_k/√σ to (κ_C μ_k/√σ)∥g∥/ε uses both ∥g∥≥ε and ε≤1; adding an explicit sentence would improve readability.","section":"Lemma 2.2, proof"},{"comment":"Reference [29] is missing author names and formatting, and reference [39] has inconsistent punctuation in its title. These should be corrected.","section":"References"},{"comment":"The baseline 'AN2C' is described as a modified variant that suppresses conditions (1.12) and (1.8) and changes the negative-curvature formula; the comparison should state more clearly that this is not exactly the published AN2C algorithm but an adapted implementation.","section":"Section 5.1"}],"recommendation":"major_revision","confidential_remarks":"The main first-order complexity proof (Theorem 2.5) appears sound once the algebraic typo in Lemma 2.1 is corrected; I do not see a circularity or hidden assumption there. The two substantive problems are localized: the proof of Theorem 3.1 in Appendix B has a genuine logical gap, and the Krylov implementation is not valid for all θ∈(0,1] as claimed. Both are fixable within the scope of the paper, but they require changes to the text or the algorithms, not just copyediting."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hi — here’s my read on 2505.04807.\n\nThe paper is a genuine extension, not a repackaging. It gives an adaptive regularized Newton method, AN2CLS, that finds an ε-first-order point in O(|log ε| ε^{-3/2}) successful iterations under a local Hessian Lipschitz condition (AS.3) instead of the usual global one. The algorithm does not need to know L0, L1, or δ, and the inexact Krylov variant is analyzed as part of the framework rather than tuned after the fact. The second-order variant SOAN2CLS gets within a log factor of the O(ε1^{-3/2}+ε2^{-3}) benchmark. I checked the proof of Theorem 2.5; the parts that usually hide gaps — the σ_k bound, the partition of successful iterations, the gradient-growth accounting in Lemma 2.4, the role of AS.4 — are all handled explicitly. The proof holds together on a careful read.\n\nThe novelty is narrower than the title might suggest. The smoothness condition (1.2) is from [33], and the algorithmic skeleton is from the authors’ own AN2C [18]. What is new is the ∥g∥-dependent regularization, the acceptance/rejection tests that make local smoothness work, the Krylov implementations, and the second-order critical-point analysis. That is enough for a solid contribution.\n\nSoft spots, in proportion:\n- AS.4, the global bound on negative curvature over the sublevel set, is doing heavy lifting. It is needed to control the gradient-growth ratio after negative-curvature steps; without it the |log ε| factor is uncontrolled and Theorem 2.5 collapses. The assumption is explicit and used correctly, but it is a global condition, which weakens the ‘local smoothness’ story. A reader hoping the method is fully local will be disappointed.\n- Lemma 1.1 is cited from [33] rather than proved. Defensible, but makes the paper less self-contained.\n- SOAN2CLS assumes an exact eigenvector/eigenvalue at each second-order-phase step; the inexact treatment of Section 4 does not carry over to that phase. Minor, but worth noting.\n- No code is shipped. The numerical claims are modest and hedged, the performance profiles are standard, and the results are only slightly better than the baselines.\n\nAlso the abstract says “optimal O(|log ε| ε^{-3/2})”; the body correctly says “within a log factor of optimal.” Clean up the abstract.\n\nWho benefits: people doing complexity analysis of second-order methods and adaptive regularization. Not an applied paper. I would send it to review, and I would expect minor-to-moderate revision. The central claim is credible, the proofs are detailed, and the prior work is credited honestly.","headline":"Careful and honest extension of adaptive regularized Newton to local Hessian smoothness, with an explicit global negative-curvature assumption carrying the logarithmic factor.","tokens_in":27007,"tokens_out":4617,"would_cite":true,"duration_ms":46435,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C30","90C53","90C60","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A Newton-type method for nonconvex optimization finds an $\\epsilon$-stationary point in $O(|\\log\\epsilon|\\,\\epsilon^{-3/2})$ iterations under only a local Hessian Lipschitz condition, and a second-order variant reaches near-optimal rates…","keywords":["second-order optimization","Newton method","local Lipschitz smoothness","negative curvature","worst-case complexity","adaptive regularization","Krylov subspaces","nonconvex optimization"],"falsifier":"Run the exact AN2CLS variant on a family of univariate polynomials of high degree, starting near a stationary point, over a range of $\\epsilon$, and count successful iterations: if the count grows faster than $\\epsilon^{-3/2}\\log(1/\\epsilon)$, Theorem 2.5 is false. A sharper test targets Lemma 2.4 directly: track $\\|g_{k+1}\\|/\\|g_k\\|$ after each negative-curvature step and check whether it exceeds the paper's bound $\\kappa_{\\rm upncurv}/\\epsilon$; the lemma forbids such a spike under AS.4.","tokens_in":26029,"feed_emoji":"📉","tokens_out":16855,"duration_ms":153466,"temperature":0.7,"pith_summary":"This paper proposes AN2CLS, an adaptive Newton method with negative-curvature steps, and proves that it produces a point with gradient norm at most $\\epsilon$ in $O(|\\log\\epsilon|\\,\\epsilon^{-3/2})$ successful iterations. The novelty is that the proof does not assume a globally Lipschitz Hessian: a local condition, $\\|\\nabla^2 f(y)-\\nabla^2 f(x)\\|\\le(L_0+L_1\\|\\nabla f(x)\\|)\\|x-y\\|$ for $\\|x-y\\|\\le\\delta$, suffices. That matters because global Lipschitz smoothness fails for simple functions such as polynomials and exponentials, while the local condition covers them. The paper also gives an inexact Krylov-subspace implementation retaining the same bound, and an extended algorithm, SOAN2CLS, that finds approximate second-order critical points with complexity within a log factor of the optimal rate. Numerical experiments on standard test problems are reported as initial evidence that the method is competitive.","feed_headline":"Newton method hits near-optimal speed without global smoothness","feed_subtitle":"A local-smoothness condition replaces the global one, so the guarantee extends to polynomials and exponentials.","key_machinery":"The load-bearing mechanism is the doubly regularized quadratic model $m_k(s)=g_k^\\top s+\\frac12 s^\\top(H_k+(\\sqrt{\\sigma_k}\\|g_k\\|+\\mu_k)I_n)s$, where $g_k$ and $H_k$ are the gradient and Hessian at the current iterate, $\\sigma_k$ is adaptively updated, and $\\mu_k$ carries eigenvalue information. Step computation is regulated by Assumption 0: for moderate $\\mu_k$ the step approximately minimizes this model with residual bounds and orthogonality (1.15)–(1.16); for large $\\mu_k$ the algorithm takes a negative-curvature step. The two acceptance tests (1.8) and (1.12) are what make the local smoothness condition sufficient, because they prevent acceptance of small steps that cause the gradient to jump and they control the gradient ratio after each step. Lemma 1.2 provides Taylor bounds with coefficients $L_0+L_1\\|\\nabla f(x)\\|$, and Lemma 2.4 uses the negative-curvature bound AS.4 to keep $\\|g_{k+1}\\|/\\|g_k\\|$ under control; together they yield the $|\\log\\epsilon|$ factor in the final complexity.","core_discovery":"On the paper's own terms, the central discovery is that near-optimal second-order complexity for nonconvex optimization does not require global Hessian Lipschitz continuity. Theorem 2.5 states that, under Assumptions AS.1–AS.4, AN2CLS terminates with $\\|\\nabla f(x)\\|\\le\\epsilon$ after at most $O(|\\log\\epsilon|\\,\\epsilon^{-3/2})$ successful iterations, and the same order of total iterations, using only the local smoothness condition and a bound on negative curvature. The algorithm alternates between a Newton step computed from a doubly regularized quadratic model and a negative-curvature step, with adaptive regularization governed by the current gradient norm; no prior knowledge of the Lipschitz constants is required. The inexact variant based on nested Krylov subspaces satisfies the same step-quality conditions, and the second-order variant SOAN2CLS terminates at a point with $\\|\\nabla f(x)\\|\\le\\epsilon_1$ and $\\lambda_{\\min}(\\nabla^2 f(x))\\ge-\\epsilon_2$ in $O(\\epsilon_1^{-3/2}+\\epsilon_2^{-3})$ iterations up to log factors. The rate matches the complexity of methods that assume a globally Lipschitz Hessian, up to the $|\\log\\epsilon|$ factor, while applying to a strictly broader class of functions.","pith_inferences":["Beyond the paper: because the step-computation conditions in Assumption 0 are already inexact, the same $O(|\\log\\epsilon|\\epsilon^{-3/2})$ bound should transfer to stochastic or matrix-free settings where gradients and Hessians are approximated, provided the approximation errors respect the residual tolerances.","Beyond the paper: the proof isolates the ratio $\\|g_{k+1}\\|/\\|g_k\\|$ after a negative-curvature step as the quantity that produces the $|\\log\\epsilon|$ factor, so a sharper potential-function argument might reduce that factor to $|\\log\\log(1/\\epsilon)|$, as in the globally smooth case; the paper does not attempt this.","Beyond the paper: the reported experiments use negative-curvature steps in less than one percent of iterations, which raises the testable question of whether a simplified regularized-Newton variant with only the two acceptance tests would achieve the same practical rate without explicit negative-curvature steps."],"forward_implications":["The same near-optimal rate previously known for globally Lipschitz Hessians now holds for functions whose Hessians satisfy only the local condition, including univariate polynomials and exponentials.","The inexact Krylov variant keeps the $O(|\\log\\epsilon|\\epsilon^{-3/2})$ guarantee while computing steps with matrix-vector products, so the bound is realistic for large-scale problems where exact solves are unavailable.","Without prior knowledge of $L_0$, $L_1$, $\\delta$, or the criticality threshold, the algorithm adapts its regularization internally and still terminates with the stated complexity.","The SOAN2CLS extension achieves approximate second-order criticality in $O(\\epsilon_1^{-3/2}+\\epsilon_2^{-3})$ iterations (up to log factors) under the same local smoothness assumption, matching the order of optimal global-smoothness methods.","On the standard test problems used in the paper, the new method's efficiency and reliability profiles are at least as competitive as those of trust-region, cubic-regularization, and earlier Newton variants in the reported experiments."],"supporting_citations":[{"why":"Supplies the AN2C algorithm whose alternating Newton and negative-curvature structure and gradient regularization AN2CLS adapts, and the baseline for numerical comparison.","marker":"[18]"},{"why":"Introduces the local Hessian Lipschitz condition (1.2) and supplies Lemma 1.1's proof that bounded cubic growth implies it.","marker":"[33]"},{"why":"Establishes the $\\Omega(\\epsilon^{-3/2})$ lower bound for first-order stationarity under Lipschitz Hessians, the benchmark the new rate matches up to a log factor.","marker":"[3]"},{"why":"Supplies the standard global-smoothness complexity framework and the iteration-counting lemma used to convert successful-step bounds into total-iteration bounds.","marker":"[6]"},{"why":"Provides the adaptive regularization update and the bound connecting total iterations to successful iterations used in Lemma 1.3.","marker":"[2]"}],"fun_headline_variants":["Newton speeds up without global smooth assumptions","Local smoothness gets Newton near-optimal rate","Newton method: near-optimal without global Lipschitz","Fast Newton under only local smoothness","Near-optimal Newton with local Lipschitz only"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the Hessian's negative curvature never becomes unboundedly large on the set of points the algorithm can visit: a finite $\\kappa_B$ caps how negative the smallest eigenvalue can get, and this cap is what prevents the gradient from exploding after a negative-curvature step.","fun_headline_variants_meta":{"raw":{"variants":["Newton speeds up without global smooth assumptions","Local smoothness gets Newton near-optimal rate","Newton method: near-optimal without global Lipschitz","Fast Newton under only local smoothness","Near-optimal Newton with local Lipschitz only"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000516,"raw_usage":{"total_tokens":2522,"prompt_tokens":985,"completion_tokens":1537,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":601,"completion_tokens_details":{"reasoning_tokens":1467}},"tokens_in":601,"tokens_out":1537,"duration_ms":12112,"temperature":1.0,"reasoning_tokens":1467,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:21:44.164793+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the exact AN2CLS variant on a family of univariate polynomials of high degree, starting near a stationary point, over a range of $\\epsilon$, and count successful iterations: if the count grows faster than $\\epsilon^{-3/2}\\log(1/\\epsilon)$, Theorem 2.5 is false. A sharper test targets Lemma 2.4 directly: track $\\|g_{k+1}\\|/\\|g_k\\|$ after each negative-curvature step and check whether it exceeds the paper's bound $\\kappa_{\\rm upncurv}/\\epsilon$; the lemma forbids such a spike under AS.4.","supporting_citations":[{"cited_title":"Yet another fast variant of newton’s method for nonconvex optimization.IMA Journal of Numerical Analysis, 45(2):971–1008, 2025","cited_arxiv_id":null,"evidence_quote":"Supplies the AN2C algorithm whose alternating Newton and negative-curvature structure and gradient regularization AN2CLS adapts, and the baseline for numerical comparison."},{"cited_title":"Trust region methods for nonconvex stochastic optimization beyond Lipschitz smoothness.Proceedings of the AAAI Conference on Artificial Intelligence, 38(14):16049–16057, Mar","cited_arxiv_id":null,"evidence_quote":"Introduces the local Hessian Lipschitz condition (1.2) and supplies Lemma 1.1's proof that bounded cubic growth implies it."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the adaptive regularization update and the bound connecting total iterations to successful iterations used in Lemma 1.3."}],"review_version":1}