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

arXiv: https://arxiv.org/abs/2211.01832 · HTML: https://mlsanity.com/paper/2211.01832/

## 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 (most cited first, 30 of 31)

- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019)
- [Online Adaptive Methods, Universality and Acceleration](https://mlsanity.com/paper/1809.02864/) (2018)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize](https://mlsanity.com/paper/2204.02833/) (2022)
- [Adaptive extra-gradient methods for min-max optimization and games](https://mlsanity.com/paper/2010.12100/) (2020)
- [A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise](https://mlsanity.com/paper/1902.01637/) (2019)
- [Oracle Complexity of Second-Order Methods for Smooth Convex Optimization](https://mlsanity.com/paper/1705.07260/) (2017)
- [Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients](https://mlsanity.com/paper/1806.00413/) (2018)
- [Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates](https://mlsanity.com/paper/1912.01597/) (2019)
- [Optimal and Adaptive Monteiro-Svaiter Acceleration](https://mlsanity.com/paper/2205.15371/) (2022)
- [Acceleration through Optimistic No-Regret Dynamics](https://mlsanity.com/paper/1807.10455/) (2018)
- [Regularized Newton Method with Global O(1/k2) Convergence](https://mlsanity.com/paper/2112.02089/) (2021)
- [Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities](https://mlsanity.com/paper/2007.08840/) (2020)
- [Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses](https://mlsanity.com/paper/1907.01771/) (2019)
- [No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation](https://mlsanity.com/paper/2206.06015/) (2022)
- [Higher-order methods for convex-concave min-max optimization and monotone variational inequalities](https://mlsanity.com/paper/2007.04528/) (2020)
- [Generalized Optimistic Methods for Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2202.09674/) (2022)
- [Lower Bounds for Higher-Order Convex Optimization](https://mlsanity.com/paper/1710.10329/) (2017)
- [The global rate of convergence for optimal tensor methods in smooth convex optimization](https://mlsanity.com/paper/1809.00382/) (2018)
- [Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method](https://mlsanity.com/paper/1706.04680/) (2017)
- [META-STORM: Generalized Fully-Adaptive Variance Reduced SGD for Unbounded Functions](https://mlsanity.com/paper/2209.14853/) (2022)
- [Accelerating Adaptive Cubic Regularization of Newton's Method via Random Sampling](https://mlsanity.com/paper/1802.05426/) (2018)
- [A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization](https://mlsanity.com/paper/1811.02427/) (2018)
- [Anytime Online-to-Batch Conversions, Optimism, and Acceleration](https://mlsanity.com/paper/1903.00974/) (2019)
- [A universal black-box optimization method with almost dimension-free convergence rate guarantees](https://mlsanity.com/paper/2206.09352/) (2022)
- [A Unified Scheme to Accelerate Adaptive Cubic Regularization and Gradient Methods for Convex Optimization](https://mlsanity.com/paper/1710.04788/) (2017)
- [Adaptive Cubic Regularization Methods with Dynamic Inexact Hessian Information and Applications to Finite-Sum Minimization](https://mlsanity.com/paper/1808.06239/) (2018)

## Built on by (most cited first, 8 of 8)

- [Improving Stochastic Cubic Newton with Momentum](https://mlsanity.com/paper/2410.19644/) (2024)
- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [Fault Tolerant ML: Efficient Meta-Aggregation and Synchronous Training](https://mlsanity.com/paper/2405.14759/) (2024)
- [Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism](https://mlsanity.com/paper/2510.03167/) (2025)
- [Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits](https://mlsanity.com/paper/2510.10690/) (2025)
- [Diffusion Stochastic Optimization for Min-Max Problems](https://mlsanity.com/paper/2401.14585/) (2024)
- [Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees](https://mlsanity.com/paper/2508.19712/) (2025)
- [Primal Acceleration of Newton's Method](https://mlsanity.com/paper/2608.21359/) (2026)

## 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.