mlsanityData to 14 Oct 2026

Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods

arXiv 2211.01832 ↗First posted 3 Nov 2022math.OC cs.LG stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

This work proposes a universal and adaptive second-order method for minimizing second-order smooth, convex functions. Our algorithm achieves O(σ / √T) convergence when the oracle feedback is stochastic with variance σ2, and improves its convergence to O( 1 / T3) with deterministic oracles, where T is the number of iterations. Our method also interpolates these rates without knowing the nature of the oracle apriori, which is enabled by a parameter-free adaptive step-size that is oblivious to the knowledge of smoothness modulus, variance bounds and the diameter of the constrained set. To our knowledge, this is the first universal algorithm with such global guarantees within the second-order optimization literature.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 31 of its 74 references that are in the map. First posted on arXiv 3 Nov 2022.

Builds on

31 of 74 references.

References · 31

  1. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  2. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  3. 2014Linear Coupling: An Ultimate Unification of Gradient and Mirror Descentcited by 58
  4. 2019UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimizationcited by 56
  5. 2018Online Adaptive Methods, Universality and Accelerationcited by 51
  6. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  7. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  8. 2020Adaptive extra-gradient methods for min-max optimization and gamescited by 30
  9. 2019A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noisecited by 26
  10. 2017Oracle Complexity of Second-Order Methods for Smooth Convex Optimizationcited by 24
  11. 2018Global linear convergence of Newton's method without strong-convexity or Lipschitz gradientscited by 24
  12. 2019Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Ratescited by 24
19 more
  1. 2022Optimal and Adaptive Monteiro-Svaiter Accelerationcited by 24
  2. 2018Acceleration through Optimistic No-Regret Dynamicscited by 22
  3. 2021Regularized Newton Method with Global O(1/k2) Convergencecited by 22
  4. 2020Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalitiescited by 18
  5. 2019Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Lossescited by 17
  6. 2022No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separationcited by 17
  7. 2020Higher-order methods for convex-concave min-max optimization and monotone variational inequalitiescited by 16
  8. 2022Generalized Optimistic Methods for Convex-Concave Saddle Point Problemscited by 16
  9. 2017Lower Bounds for Higher-Order Convex Optimizationcited by 12
  10. 2018The global rate of convergence for optimal tensor methods in smooth convex optimizationcited by 10
  11. 2017Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Methodcited by 8
  12. 2022META-STORM: Generalized Fully-Adaptive Variance Reduced SGD for Unbounded Functionscited by 5
  13. 2018Accelerating Adaptive Cubic Regularization of Newton's Method via Random Samplingcited by 3
  14. 2018A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimizationcited by 3
  15. 2019Anytime Online-to-Batch Conversions, Optimism, and Accelerationcited by 3
  16. 2022A universal black-box optimization method with almost dimension-free convergence rate guaranteescited by 3
  17. 2017A Unified Scheme to Accelerate Adaptive Cubic Regularization and Gradient Methods for Convex Optimizationcited by 2
  18. 2018Adaptive Cubic Regularization Methods with Dynamic Inexact Hessian Information and Applications to Finite-Sum Minimizationcited by 2
  19. 2021Scalable adaptive cubic regularization methodscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 4; 2025: 3; 2026: 1.

8 papers.

  1. 2024Improving Stochastic Cubic Newton with Momentumcited by 6
  2. 2024Second-Order Min-Max Optimization with Lazy Hessianscited by 5
  3. 2024Fault Tolerant ML: Efficient Meta-Aggregation and Synchronous Trainingcited by 3
  4. 2025Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimismcited by 3
  5. 2025Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limitscited by 3
  6. 2024Diffusion Stochastic Optimization for Min-Max Problemscited by 2
  7. 2025Simple Stepsize for Quasi-Newton Methods with Global Convergence Guaranteescited by 0
  8. 2026Primal Acceleration of Newton's Methodcited by 0