Optimal Convex Optimization with Inexact Second-Order Oracles

Chengchang Liu; Jingzhao Zhang; John C.S. Lui; Lesi Chen; Luo Luo

REVIEW 2 major objections 4 minor 123 references

Optimal Convex Optimization with Inexact Second-Order Oracles

T0 review · 2 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read AINE achieves optimal convergence rates for convex optimization with approximate Hessians, matching proven lower bounds.

desk verdict The p=2 result is a real step forward and likely correct; the p=3 claim rests on a false relative-smoothness lemma and is not supported as written. read the letter →

arxiv 2607.24520 v3 pith:EWS3ZDWA submitted 2026-07-27 math.OC

Lesi Chen , Chengchang Liu , Luo Luo , John C.S. Lui , Jingzhao Zhang This is my paper · ORCID

classification math.OC MSC 90C2590C6065K05

keywords inexactHessianconvexoptimizationsecond-orderoraclecomplexityacceleratedNewtonmethodsMonteiro-Svaiteraccelerationtensorlowerboundscubicregularization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Accelerated Inexact Newton Extragradient (AINE) brings the optimal convergence rates of second-order methods into the setting where Hessians are only known approximately. The paper establishes that, with δ-inexact Hessians, AINE finds an ε-solution in O((δ/ε)^{1/2} + (L2/ε)^{2/7}) inexact-Hessian queries when the true Hessian is L2-Lipschitz, and in O((δ/ε)^{1/2} + (L3/ε)^{1/5}) when the third derivative is L3-Lipschitz. The same rates are proven to be the best possible, so the method is optimal in both settings. Each iteration costs about the same as a matrix multiplication, up to logarithmic factors, making the theoretical optimum potentially practical.

What carries the argument

AINE extends the accelerated Newton proximal extragradient (A-NPE) framework, which solves a proximal subproblem with a regularization parameter λ_t balancing Hessian inexactness and high-order smoothness. The key machinery is an epoch-wise guessing strategy for λ′_t: iterations are partitioned into epochs where the guess is fixed, and the guess is updated only when the cumulative progress A_t doubles. For inexactness, the analysis separates iterations where δ dominates (λ_t ≈ δ) from those where p-th order terms dominate; the new 'separation trick' bounds the number of each type of iteration separately. For p=3, the third-order MS oracle is implemented by a BDGM subroutine whose convergence

What would settle it

Take a simple convex function with L3-Lipschitz third derivative, fix a query point z_t, numerically compute the smallest and largest eigenvalues of ∇²f_t(y) and ∇²ρ_t(y) over y within radius R_t, and check whether (1−1/ξ)∇²ρ_t ⪯ ∇²f_t ⪯ (1+1/ξ)∇²ρ_t holds for the paper's ξ. If it fails for any such function satisfying Assumptions 2.1–2.3, then Lemma 4.2 is false and the BDGM termination bound, and hence the claimed p=3 complexity, collapses.

Watch

Extended reading notes

Core claim

For convex functions whose Hessian is L2-Lipschitz, the paper proves AINE achieves an inexact second-order oracle complexity of O((δ/ε)^{1/2} + (L2/ε)^{2/7}), and under L3-smoothness it achieves O((δ/ε)^{1/2} + (L3/ε)^{1/5}); it then proves matching lower bounds, demonstrating these rates cannot be improved. The second rate is obtained without ever querying a third-order derivative: the required third-order tensor step is implemented by a Bregman-distance gradient subroutine that only calls the inexact Hessian oracle, and terminates in polylogarithmically many iterations.

Load-bearing premise

For the third-order rate to hold, the proximal function f_t must be non-degenerate with respect to the chosen scaling function ρ_t with constants (1±1/ξ); the paper's proof of this inequality in Appendix E contains algebraic equalities that are not equalities as written, and if the constants fail, the inner BDGM subroutine may not terminate in polylogarithmically many iterations, leaving the O((δ/ε)^{1/2} + (L3/ε)^{1/5}) guarantee unsupported.

Editorial extensions

If this is right

Practical solvers can use approximate Hessians (e.g., mini-batch estimates) and still achieve the optimal iteration count without exact curvature.
The p=3 rate improves the previously best inexact method's dependence on the third-order term from (L3/ε)^{1/4} to (L3/ε)^{1/5}, matching exact-tensor lower bounds while needing only Hessian queries.
The lower bounds certify that no deterministic algorithm using δ-inexact Hessians can do better, so the two-term complexity is tight for both Lipschitz classes.
Each iteration's near matrix-multiplication cost means the optimal oracle complexity translates into comparable runtime, making the method a candidate for large-scale problems.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the p=3 relative-smoothness constants in Lemma 4.2 fail, the BDGM subroutine could require more than polylog iterations; the O((L3/ε)^{1/5}) claim would then need an additional logarithmic factor or a modified scaling function, so verifying Lemma 4.2 is the first check before building on the p=3 result.
The separation trick (dividing damped iterations by whether δ or p-th order progress dominates) may transfer to other inexact higher-order or nonconvex settings where the regularization coefficient is ambiguous.
The formal lower bound matching for all p suggests a general principle: any method with δ-inexact Hessians must pay an unavoidable (δ/ε)^{1/2} term, independent of smoothness order.
Because each iteration is nearly as cheap as a Newton step, AINE narrows the gap between optimal theoretical oracle counts and what is implementable in large-scale machine learning, where exact Hessians are rarely available.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Rough take: the p=2 half of this paper is a genuine contribution and probably right; the p=3 half rests on a lemma that is false as stated, so that half is not currently supported.

What's actually new: the epoch separation trick that splits the 'large λ' iterations by whether δ or L_p r^{p-1} dominates, and the idea of implementing a third-order MS oracle with only inexact second-order queries via BDGM. The p=2 result, O((δ/ε)^{1/2}+(L2/ε)^{2/7}), closes the gap left by AINCR and matches lower bounds. The lower-bound generalization to all deterministic algorithms and all p is also useful.

I checked the p=2 proof. There are typos in the appendix—e.g., Eq. (21) has λ^{2p/(p-1)} where the algebra gives λ^{(p+1)/(p-1)}, and the displayed inequality for |S↓| has the λ' on the wrong side. But the proof sketch in the main text has the right form, and once the arithmetic is corrected the final rate works. Nothing fitted here; the constants come from prior work.

The soft spot is real. Lemma 4.2, the relative-smoothness claim that makes BDGM terminate in polylog iterations, is false for ξ>2. Take f≡0, H(z_t)=0, δ=1, L3=0, and y=z_t: the lemma reduces to ((ξ²−1)/ξ)I ≤ (1+1/ξ)I, which forces ξ≤2. The appendix proof also writes an equality between a multiple of (H+δI+... ) and ∇²ρ_t that omits the 1/3 and the h h^T cross term. Since the condition number in Lemma 4.1 and the termination argument in Theorem 4.1 both rely on Lemma 4.2, the O((δ/ε)^{1/2}+(L3/ε)^{1/5}) claim is unsupported as written. Maybe the lemma holds for a carefully chosen ξ≤2 and a corrected proof, but that needs to be shown. The lower-bound section likewise says two lower bounds imply a sum, but doesn't construct the single hard instance; that's a gap, probably fixable.

Bottom line: the p=2 contribution deserves publication if the typos get cleaned up. The p=3 section needs real work—rewrite the proof of Lemma 4.2 or restrict the constant, and detail the lower-bound combination. This is not a desk reject; an editor should send it to referees who know the A-NPE and relative-smoothness literature. I'd tell the authors to submit a revision with the p=3 claim deferred if they can't repair Lemma 4.2.

Referee Report

2 major / 4 minor

Summary. The paper introduces an accelerated inexact Newton extragradient (AINE) method for convex optimization with δ-inexact Hessian oracles. The main claims are: (i) for convex functions with L₂-Lipschitz Hessians, AINE achieves an inexact second-order oracle (ISO) complexity of O((δ/ε)^{1/2} + (L₂/ε)^{2/7}); (ii) when the third derivative is L₃-Lipschitz, it achieves O((δ/ε)^{1/2} + (L₃/ε)^{1/5}) by implementing a third-order MS oracle with a Bregman-distance gradient method using only inexact Hessians; (iii) matching oracle lower bounds are provided for both regimes; and (iv) each iteration is claimed to run in nearly matrix-multiplication time. The proof of the general convergence rate is given in Theorem 3.1, the p=2 oracle implementation in Lemma 3.1/Corollary 3.1, the p=3 implementation in Lemma 4.2/Theorem 4.1/Corollary 4.1, and the lower bounds in Proposition 5.1.

Significance. The p=2 result, if correct, would match the exact-setting optimal rate while retaining the (δ/ε)^{1/2} noise dependence, improving on prior inexact second-order methods. The per-iteration near-matrix-multiplication cost and the extension of lower bounds to all deterministic algorithms are also valuable. However, the p=3 branch rests on Lemma 4.2, which is false as stated; this currently invalidates the O((δ/ε)^{1/2}+(L₃/ε)^{1/5}) claim. The Eq. (21) exponent error in the proof of Theorem 3.1 is repairable and the final rate appears salvageable, but both issues must be addressed before the claims are established.

major comments (2)

[Appendix C, Eq. (21)-(22)] The displayed derivation before Eq. (21) gives ∥y_t−z_t∥ ≥ const·(λ'_t)^{1/(p−1)}, so λ'_t∥y_t−z_t∥² ≥ const·(λ'_t)^{1+2/(p−1)} = (λ'_t)^{(p+1)/(p−1)}. Eq. (21) instead writes (λ'_t)^{2p/(p−1)}, which is not implied. Consequently, the epoch-length bound in Eq. (22) has the wrong power in the third term. Note that choosing λ' by Eq. (6) is actually the minimizer for the correct exponent (p+1)/(p−1), not for the exponent 2p/(p−1) displayed in Eq. (21); with the displayed exponent the algebra in Eq. (22) and the claimed final rate do not follow. This is a load-bearing step for Theorem 3.1 and Corollary 3.1, although the exponent appears fixable.
[Lemma 4.2 / Appendix E / Eq. (10)-(11)] Lemma 4.2 is false as stated. Take f≡0, H(z_t)=0, δ=1, L₃=0, and y=z_t. Then ∇²f_t(y) = ((ξ²−1)/ξ) I from Eq. (10), while ∇²ρ_t(y) = I from Eq. (11). The claimed upper bound (1+1/ξ)∇²ρ_t(y) is equivalent to ξ≤2; for ξ=3 it already fails. The proof in Appendix E confirms this: it replaces ∇²ρ_t by (H+ξδI+(ξ+ξ²)L₃∥h∥²I), but the actual Hessian of ρ_t in Eq. (11) has coefficients (ξ+ξ²)L₃/3 on ∥h∥²I and an additional (2/3)(ξ+ξ²)L₃ hh^T. Thus the displayed equalities are not equalities. Moreover, Assumption 2.3 does not prevent H(z_t)+δI from being singular or indefinite, in which case ρ_t is not non-degenerate and no constants (1±1/ξ) can hold. Since this lemma is the basis for the BDGM subroutine's linear-rate termination used in Theorem 4.1, the p=3 claim is currently unsupported.

minor comments (4)

[General] There are several small typos: 'generaliza ons' in Section 3.1, the caption of Table 2 refers to 'Figure 2' but the experiment is in Figure 2 (the tabular figure itself is unnumbered), and Eq. (24) uses z0 in βρ(z0,y*_t) where z_t is meant.
[Section 4.2 / Eq. (9)] The parameter ξ is described only as 'a numerical constant' and no value is ever chosen. Since Lemma 4.2 is false for ξ>2, the statement should either fix ξ explicitly (and prove the lemma for that value) or impose the necessary restrictions.
[Assumption 2.3 / Lemma 4.2] The definition of a δ-Hessian estimator does not require H(x)+δI to be positive definite. The p=3 BDGM analysis seems to need a stronger assumption (or a different scaling/proximal function); this should be stated explicitly.
[Appendix D] In the proof of Lemma 3.1, the term '2L₃∥y−x∥(y−x)' should be 'L₂∥y−x∥(y−x)' since λ=2δ+L₂∥y−x∥. The typo is cosmetic but should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the derivation chain relies on external prior results and verified oracle constructions, not on fitted parameters or self-citations.

full rationale

Walking the derivation chain: Algorithm 2's convergence (Theorem 3.1) depends on Lemma 3.2, quoted from Carmon et al. (2022, Proposition 1), an external MS-acceleration guarantee. The inexact CRN oracle (Lemma 3.1) is verified directly from Assumptions 2.2 and 2.3, and no parameter is fitted to the target complexity. The p=3 branch uses Nesterov's BDGM linear-rate lemma (Lemma 4.1) and the paper's own Lemma 4.2 as a relative-smoothness certification; even if the appendix algebra of Lemma 4.2 is questionable, that is an unsupported correctness step, not a reduction of the complexity claim to its own inputs by construction. The lower bounds (Proposition 5.1) are imported from Arjevani et al. (2019), an external oracle lower bound, with the delta-term obtained by applying the p=1 instance with L1=delta; this is not a self-citation and does not presuppose the paper's rates. No fitted constants, no self-referential uniqueness argument, and no renaming of a known result as a new prediction were found. The complexity claims therefore do not reduce to their assumptions by construction; remaining concerns are correctness risks, not circularity.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The central complexity theorem relies on convexity, Lp-smoothness, the δ-Hessian error model, and the MS-oracle abstraction. The p=3 implementation additionally depends on a relative-smoothness inequality whose proof in Appendix E is not cleanly stated; this is the main unverified premise. No data-fitted constants are used.

assumptions (8)

domain assumption f is convex and attains its minimum (Assumption 2.1).
Standard for convex optimization; not proven in the paper.
domain assumption f has Lp-Lipschitz pth-order derivatives for p ∈ {1,2,3} (Assumption 2.2).
Needed for the Taylor bounds and the oracle implementations.
domain assumption Access to a symmetric δ-Hessian estimator H with ∥H−∇²f∥ ≤ δ (Assumption 2.3).
Formalizes the inexact oracle model.
standard math Carmon et al. (2022, Proposition 1) potential inequality (Lemma 3.2).
Independent prior result used as a black box for the MS acceleration analysis.
standard math Nesterov (2021c) BDGM linear convergence (Lemma 4.1).
Provides the convergence rate of the inner subroutine.
standard math Nesterov (2021c) norm bounds and norm-dominance inequalities (Lemma 4.4 and Theorem 4.1).
Used to bound the compact sets and termination time of the BDGM subroutine.
standard math Arjevani et al. (2019, Theorem 3) oracle lower bounds.
External result used for the matching lower bounds.
domain assumption Relative smoothness of f_t with respect to ρ_t (Lemma 4.2).
The proof in Appendix E contains apparent algebraic errors; without a corrected proof, the p=3 result is unsupported.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimal Convex Optimization with Inexact Second-Order Oracles." pith.science (2026). https://pith.science/paper/EWS3ZDWA

@misc{pith2026260724520,
  author       = {Pith},
  title        = {Pith review of: Optimal Convex Optimization with Inexact Second-Order Oracles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EWS3ZDWA}},
  note         = {Machine review of arXiv:2607.24520}
}

abstract

In this paper, we present a novel second-order method called Accelerated Inexact Newton Extragradient (AINE) for convex optimization using $\delta$-inexact Hessians. We show that AINE can find an $\epsilon$-solution in the inexact second-order oracle (ISO) complexity of $\mathcal{O}( (\delta/\epsilon)^{1/2} + (L_2/\epsilon)^{2/7} )$ when the Hessian is $L_2$-Lipschitz continuous, and a better complexity of $\mathcal{O}( (\delta/\epsilon)^{1/2} + (L_3/\epsilon)^{1/5} )$ when the third-order derivative is $L_3$-Lipschitz continuous. Notably, each iteration of our method can be conducted in the same running time as matrix multiplication up to logarithmic factors. In addition, we also establish matching oracle complexity lower bounds for both setups, demonstrating the optimality of our methods.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

123 extracted references · 3 linked inside Pith

[1]

Matecon , volume=

The extragradient method for finding saddle points and other problems , author=. Matecon , volume=
[2]

Langley , title =

P. Langley , title =. Proceedings of the 17th International Conference on Machine Learning (ICML 2000) , address =. 2000 , pages =

2000
[3]

T. M. Mitchell. The Need for Biases in Learning Generalizations. 1980

1980
[4]

M. J. Kearns , title =
[5]

Machine Learning: An Artificial Intelligence Approach, Vol. I. 1983

1983
[6]

R. O. Duda and P. E. Hart and D. G. Stork. Pattern Classification. 2000

2000
[7]

Suppressed for Anonymity , author=
[8]

Newell and P

A. Newell and P. S. Rosenbloom. Mechanisms of Skill Acquisition and the Law of Practice. Cognitive Skills and Their Acquisition. 1981

1981

Show all 123 references

[9]

A. L. Samuel. Some Studies in Machine Learning Using the Game of Checkers. IBM Journal of Research and Development. 1959

1959
[10]

Mathematical programming , volume=

Cubic regularization of Newton method and its global performance , author=. Mathematical programming , volume=. 2006 , publisher=

2006
[11]

STOC , year=

Finding approximate local minima faster than gradient descent , author=. STOC , year=
[12]

SIAM Journal on Optimization , volume=

Accelerated methods for nonconvex optimization , author=. SIAM Journal on Optimization , volume=
[13]

NeurIPS , year=

Balancing Gradient and Hessian Queries in Non-Convex Optimization , author=. NeurIPS , year=
[14]

ICML , year=

``Convex until proven guilty''': Dimension-free acceleration of gradient descent on non-convex functions , author=. ICML , year=
[15]

COLT , year=

Accelerated gradient descent escapes saddle points faster than gradient descent , author=. COLT , year=
[16]

Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the in the

Li, Huan and Lin, Zhouchen , journal=. Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the in the
[17]

NeurIPS , year=

Stochastic cubic regularization for fast nonconvex optimization , author=. NeurIPS , year=
[18]

Sharp analysis for nonconvex

Fang, Cong and Lin, Zhouchen and Zhang, Tong , booktitle=. Sharp analysis for nonconvex
[19]

NeurIPS , year=

How to make the gradients small stochastically: Even faster convex and nonconvex sgd , author=. NeurIPS , year=
[20]

Momentum improves normalized

Cutkosky, Ashok and Mehta, Harsh , booktitle=. Momentum improves normalized
[21]

ICLR , year=

Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism , author=. ICLR , year=
[22]

Universal heavy-ball method for nonconvex optimization under H

Marumo, Naoki and Takeda, Akiko , journal=. Universal heavy-ball method for nonconvex optimization under H. 2025 , publisher=

2025
[23]

SIAM Journal on Optimization , volume=

Parameter-free accelerated gradient descent for nonconvex minimization , author=. SIAM Journal on Optimization , volume=. 2024 , publisher=

2024
[24]

Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the

Li, Huan and Lin, Zhouchen , booktitle=. Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the. 2022 , organization=

2022
[25]

and Hinder, Oliver and Sidford, Aaron , journal=

Carmon, Yair and Duchi, John C. and Hinder, Oliver and Sidford, Aaron , journal=. Lower bounds for finding stationary points. 2020 , publisher=

2020
[26]

and Hinder, Oliver and Sidford, Aaron , journal=

Carmon, Yair and Duchi, John C. and Hinder, Oliver and Sidford, Aaron , journal=. Lower bounds for finding stationary points. 2021 , publisher=

2021
[27]

ALT , year=

On the complexity of finding stationary points of smooth functions in one dimension , author=. ALT , year=
[28]

Mathematical Programming , volume=

Lower bounds for non-convex stochastic optimization , author=. Mathematical Programming , volume=. 2023 , publisher=

2023
[29]

NeurIPS , year=

Reducing the variance in online optimization by transporting past gradients , author=. NeurIPS , year=
[30]

AISTATS , year =

Improving Stochastic Cubic Newton with Momentum , author =. AISTATS , year =
[31]

TMLR , year=

Unified convergence theory of stochastic and variance-reduced cubic Newton methods , author=. TMLR , year=
[32]

arXiv preprint arXiv:1710.05782 , year=

Second-order methods with cubic regularization under inexact information , author=. arXiv preprint arXiv:1710.05782 , year=

arXiv
[33]

Optimization Methods and Software , volume=

Inexact tensor methods and their application to stochastic convex optimization , author=. Optimization Methods and Software , volume=. 2024 , publisher=

2024
[34]

Antonakopoulos, Kimon and Kavis, Ali and Cevher, Volkan , booktitle=. Extra-
[35]

ICLR , year=

Advancing the Lower Bounds: an Accelerated, Stochastic, Second-order Method with Optimal Adaptation to Inexactness , author=. ICLR , year=
[36]

NeurIPS , year=

Exploring jacobian inexactness in second-order methods for variational inequalities: lower bounds, optimal algorithms and quasi-newton approximations , author=. NeurIPS , year=
[37]

ICML , year=

Optimal stochastic non-smooth non-convex optimization through online-to-non-convex conversion , author=. ICML , year=
[38]

COLT , year=

Second-order information in non-convex stochastic optimization: Power and limitations , author=. COLT , year=
[39]

SIAM journal on optimization , volume=

Stochastic first-and zeroth-order methods for nonconvex stochastic programming , author=. SIAM journal on optimization , volume=. 2013 , publisher=

2013
[40]

Fang, Cong and Li, Chris Junchi and Lin, Zhouchen and Zhang, Tong , booktitle=
[41]

NeurIPS , year=

Non-convex finite-sum optimization via scsg methods , author=. NeurIPS , year=
[42]

JMLR , volume=

Stochastic nested variance reduction for nonconvex optimization , author=. JMLR , volume=
[43]

JMLR , volume=

Stochastic variance-reduced cubic regularization methods , author=. JMLR , volume=
[44]

ICML , year=

Stochastic subspace cubic Newton method , author=. ICML , year=
[45]

AISTATS , year=

Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate , author=. AISTATS , year=
[46]

ICML , year=

Shampoo: Preconditioned stochastic tensor optimization , author=. ICML , year=
[47]

Vyas, Nikhil and Morwani, Depen and Zhao, Rosie and Shapira, Itai and Brandfonbrener, David and Janson, Lucas and Kakade, Sham M , booktitle=
[48]

ICML , year=

A kronecker-factored approximate fisher matrix for convolution layers , author=. ICML , year=
[49]

The Potential of Second-Order Optimization for

Abreu, Natalie and Vyas, Nikhil and Kakade, Sham and Morwani, Depen , booktitle=. The Potential of Second-Order Optimization for
[50]

Annals of the Institute of Statistical Mathematics , volume=

Penalized likelihood regression for generalized linear models with non-quadratic penalties , author=. Annals of the Institute of Statistical Mathematics , volume=. 2011 , publisher=

2011
[51]

ICML , year=

PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization , author=. ICML , year=
[52]

ICML , year=

Stochastic variance reduction for nonconvex optimization , author=. ICML , year=
[53]

ICML , year=

Variance reduction for faster non-convex optimization , author=. ICML , year=
[54]

NeurIPS , year=

Spiderboost and momentum: Faster variance reduction algorithms , author=. NeurIPS , year=
[55]

ICML , year=

Complexity of finding stationary points of nonconvex nonsmooth functions , author=. ICML , year=
[56]

NeurIPS , volume=

Accelerating stochastic gradient descent using predictive variance reduction , author=. NeurIPS , volume=
[57]

SIAM Journal on Optimization , volume=

A proximal stochastic gradient method with progressive variance reduction , author=. SIAM Journal on Optimization , volume=. 2014 , publisher=

2014
[58]

A method for solving the convex programming problem with convergence rate

Nesterov, Yurii , booktitle=. A method for solving the convex programming problem with convergence rate
[59]

STOC , year=

Improved complexity for smooth nonconvex optimization: a two-level online learning approach with quasi-Newton methods , author=. STOC , year=
[60]

COLT , year=

Online learning with predictable sequences , author=. COLT , year=
[61]

How to make the gradients small , author=. Optima. Mathematical Optimization Society Newsletter , number=
[62]

Mathematical Programming , volume=

Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models , author=. Mathematical Programming , volume=. 2017 , publisher=

2017
[63]

Machine learning , volume=

Extracting certainty from uncertainty: Regret bounded by variation in costs , author=. Machine learning , volume=. 2010 , publisher=

2010
[64]

COLT , year=

Impossible tuning made possible: A new expert algorithm and its applications , author=. COLT , year=
[65]

2000 , publisher=

Trust region methods , author=. 2000 , publisher=

2000
[66]

ICML , year=

A second look at exponential and cosine step sizes: Simplicity, adaptivity, and performance , author=. ICML , year=
[67]

arXiv preprint arXiv:2312.03218 , year=

Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization , author=. arXiv preprint arXiv:2312.03218 , year=

arXiv
[68]

ICML , year=

Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions , author=. ICML , year=
[69]

ICML , year=

Anytime online-to-batch, optimism and acceleration , author=. ICML , year=
[70]

NeurIPS , year=

Online adaptive methods, universality and acceleration , author=. NeurIPS , year=
[71]

NeurIPS , year=

Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization , author=. NeurIPS , year=
[72]

ICML , year=

A simpler approach to accelerated optimization: iterative averaging meets optimism , author=. ICML , year=
[73]

ICML , year=

How to escape saddle points efficiently , author=. ICML , year=
[74]

COLT , year=

Escaping from saddle points—online stochastic gradient for tensor decomposition , author=. COLT , year=
[75]

NeurIPS , year=

Acceleration with a ball optimization oracle , author=. NeurIPS , year=
[76]

Journal of the ACM , volume=

On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points , author=. Journal of the ACM , volume=. 2021 , publisher=

2021
[77]

SIAM Journal on Optimization , volume=

Iteration-complexity of a Newton proximal extragradient method for monotone variational inequalities and inclusion problems , author=. SIAM Journal on Optimization , volume=. 2012 , publisher=

2012
[78]

Symposium on Foundations of Computer Science , pages=

Understanding alternating minimization for matrix completion , author=. Symposium on Foundations of Computer Science , pages=. 2014 , organization=

2014
[79]

IEEE Trans

Phase retrieval via Wirtinger flow: Theory and algorithms , author=. IEEE Trans. Inform. Theory , volume=. 2015 , publisher=

2015
[80]

nature , volume=

Deep learning , author=. nature , volume=. 2015 , publisher=

2015
[81]

Journal of Optimization Theory and Applications , volume=

Accelerated adaptive cubic regularized Quasi-Newton methods , author=. Journal of Optimization Theory and Applications , volume=. 2026 , publisher=

2026
[82]

ICML , year=

Second-order optimization with lazy Hessians , author=. ICML , year=
[83]

arXiv preprint arXiv:2309.02412 , year=

First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians , author=. arXiv preprint arXiv:2309.02412 , year=

arXiv
[84]

FOCS , year=

Faster matrix multiplication via asymmetric hashing , author=. FOCS , year=
[85]

SODA , year=

More asymmetry yields faster matrix multiplication , author=. SODA , year=
[86]

, author=

Adaptive subgradient methods for online learning and stochastic optimization. , author=. JMLR , year=
[87]

ICLR , year=

Adam: A method for stochastic optimization , author=. ICLR , year=
[88]

ICLR , year=

Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-training , author=. ICLR , year=
[89]

SIAM Journal on Optimization , volume=

An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods , author=. SIAM Journal on Optimization , volume=. 2013 , publisher=

2013
[90]

SIAM Journal on Optimization , volume=

Inexact high-order proximal-point methods with auxiliary search procedure , author=. SIAM Journal on Optimization , volume=. 2021 , publisher=

2021
[91]

International Conference on Mathematical Optimization Theory and Operations Research , pages=

Near-optimal hyperfast second-order method for convex optimization , author=. International Conference on Mathematical Optimization Theory and Operations Research , pages=. 2020 , organization=

2020
[92]

SIAM Journal on Optimization , volume=

Unified acceleration of high-order algorithms under general holder continuity , author=. SIAM Journal on Optimization , volume=. 2021 , publisher=

2021
[93]

COLT , year=

Near-optimal method for highly smooth convex optimization , author=. COLT , year=
[94]

COLT , year=

Near optimal methods for minimizing convex functions with lipschitz p -th derivatives , author=. COLT , year=
[95]

COLT , year=

Optimal tensor methods in smooth convex and uniformly convexoptimization , author=. COLT , year=
[96]

Mathematical Programming , volume=

Implementable tensor methods in unconstrained convex optimization , author=. Mathematical Programming , volume=. 2021 , publisher=

2021
[97]

Mathematics of Operations Research , volume=

An optimal high-order tensor method for convex optimization , author=. Mathematics of Operations Research , volume=. 2021 , publisher=

2021
[98]

NeurIPS , year=

The first optimal acceleration of high-order methods in smooth convex optimization , author=. NeurIPS , year=
[99]

Optimal and adaptive

Carmon, Yair and Hausler, Danielle and Jambulapati, Arun and Jin, Yujia and Sidford, Aaron , booktitle=. Optimal and adaptive
[100]

ALT , year=

Convex optimization with p -norm oracles , author=. ALT , year=
[101]

1983 , publisher=

Problem complexity and method efficiency in optimization , author=. 1983 , publisher=

1983
[102]

2018 , publisher=

Lectures on convex optimization , author=. 2018 , publisher=

2018
[103]

Mathematical Programming , volume=

Accelerating the cubic regularization of Newton’s method on convex problems , author=. Mathematical Programming , volume=. 2008 , publisher=

2008
[104]

COLT , year=

Lower bounds for higher-order convex optimization , author=. COLT , year=
[105]

Mathematical Programming , volume=

Oracle complexity of second-order methods for smooth convex optimization , author=. Mathematical Programming , volume=. 2019 , publisher=

2019
[106]

and Gould, Nicholas I.M

Conn, Andrew R. and Gould, Nicholas I.M. and Toint, Ph. L. , journal=. Convergence of quasi-. 1991 , publisher=

1991
[107]

general considerations , author=

The convergence of a class of double-rank minimization algorithms 1. general considerations , author=. IMA Journal of Applied Mathematics , volume=. 1970 , publisher=

1970
[108]

Mathematical Programming , volume=

Non-asymptotic superlinear convergence of standard quasi-Newton methods , author=. Mathematical Programming , volume=. 2023 , publisher=

2023
[109]

Rates of superlinear convergence for classical quasi-

Rodomanov, Anton and Nesterov, Yurii , journal=. Rates of superlinear convergence for classical quasi-. 2022 , publisher=

2022
[110]

COLT , year=

Online learning guided curvature approximation: A quasi-Newton method with global non-asymptotic superlinear convergence , author=. COLT , year=
[111]

arXiv preprint arXiv:2512.09439 , year=

Parameter-Free Accelerated Quasi-Newton Method for Nonconvex Optimization , author=. arXiv preprint arXiv:2512.09439 , year=
[112]

2011 , publisher=

Chang, Chih-Chung and Lin, Chih-Jen , journal=. 2011 , publisher=

2011
[113]

arXiv preprint arXiv:2508.07473 , year=

Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications , author=. arXiv preprint arXiv:2508.07473 , year=
[114]

ICML , year=

General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization , author=. ICML , year=
[115]

JMLR , volume=

An algorithm with optimal dimension-dependence for zero-order nonsmooth nonconvex stochastic optimization , author=. JMLR , volume=
[116]

Journal of Optimization Theory and Applications , volume=

Superfast second-order methods for unconstrained convex optimization , author=. Journal of Optimization Theory and Applications , volume=. 2021 , publisher=

2021
[117]

SIAM Journal on Optimization , volume=

Relatively smooth convex optimization by first-order methods, and applications , author=. SIAM Journal on Optimization , volume=. 2018 , publisher=

2018
[118]

NeurIPS , year=

Accelerated quasi-newton proximal extragradient: Faster rate for smooth convex optimization , author=. NeurIPS , year=
[119]

Mathematics of Operations Research , volume=

A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications , author=. Mathematics of Operations Research , volume=
[120]

AISTATS , year=

Stochastic variance-reduced cubic regularization for nonconvex optimization , author=. AISTATS , year=
[121]

AISTATS , year=

Stochastic recursive variance-reduced cubic regularization methods , author=. AISTATS , year=
[122]

ICML , year=

Dimension-free Complexity Bounds for High-order Nonconvex Finite-sum Optimization , author=. ICML , year=
[123]

AISTATS , year=

On the oracle complexity of higher-order smooth non-convex finite-sum optimization , author=. AISTATS , year=

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [1]

Matecon , volume=

The extragradient method for finding saddle points and other problems , author=. Matecon , volume=

[2] [2]

Langley , title =

P. Langley , title =. Proceedings of the 17th International Conference on Machine Learning (ICML 2000) , address =. 2000 , pages =

2000

[3] [3]

T. M. Mitchell. The Need for Biases in Learning Generalizations. 1980

1980

[4] [4]

M. J. Kearns , title =

[5] [5]

Machine Learning: An Artificial Intelligence Approach, Vol. I. 1983

1983

[6] [6]

R. O. Duda and P. E. Hart and D. G. Stork. Pattern Classification. 2000

2000

[7] [7]

Suppressed for Anonymity , author=

[8] [8]

Newell and P

A. Newell and P. S. Rosenbloom. Mechanisms of Skill Acquisition and the Law of Practice. Cognitive Skills and Their Acquisition. 1981

1981