# Super-Universal Regularized Newton Method

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 46 references that are in the map.
- First posted on arXiv 11 Aug 2022.

## Builds on (most cited first, 17 of 17)

- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Oracle Complexity of Second-Order Methods for Smooth Convex Optimization](https://mlsanity.com/paper/1705.07260/) (2017)
- [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)
- [Regularized Newton Method with Global O(1/k2) Convergence](https://mlsanity.com/paper/2112.02089/) (2021)
- [Stochastic Subspace Cubic Newton Method](https://mlsanity.com/paper/2002.09526/) (2020)
- [The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization](https://mlsanity.com/paper/2205.09647/) (2022)
- [Gradient Regularization of Newton Method with Bregman Distances](https://mlsanity.com/paper/2112.02952/) (2021)
- [Randomized Block Cubic Newton Method](https://mlsanity.com/paper/1802.04084/) (2018)
- [Minimizing Uniformly Convex Functions by Cubic Regularization of Newton Method](https://mlsanity.com/paper/1905.02671/) (2019)
- [Local convergence of tensor methods](https://mlsanity.com/paper/1912.02516/) (2019)
- [Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints](https://mlsanity.com/paper/1811.01220/) (2018)
- [Tensor Methods for Minimizing Convex Functions with H"older Continuous Higher-Order Derivatives](https://mlsanity.com/paper/1904.12559/) (2019)
- [Contracting Proximal Methods for Smooth Convex Optimization](https://mlsanity.com/paper/1912.07972/) (2019)
- [On Inexact Solution of Auxiliary Problems in Tensor Methods for Convex Optimization](https://mlsanity.com/paper/1907.13023/) (2019)
- [Near-Optimal Hyperfast Second-Order Method for convex optimization and its Sliding](https://mlsanity.com/paper/2002.09050/) (2020)
- [Affine-invariant contracting-point methods for Convex Optimization](https://mlsanity.com/paper/2009.08894/) (2020)

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

- [Second-order optimization with lazy Hessians](https://mlsanity.com/paper/2212.00781/) (2022)
- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method](https://mlsanity.com/paper/2308.14742/) (2023)
- [First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians](https://mlsanity.com/paper/2309.02412/) (2023)
- [SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithms](https://mlsanity.com/paper/2312.17369/) (2023)
- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [Adaptive proximal gradient methods are universal without approximation](https://mlsanity.com/paper/2402.06271/) (2024)
- [DADA: Dual Averaging with Distance Adaptation](https://mlsanity.com/paper/2501.10258/) (2025)
- [Policy Newton Algorithm in Reproducing Kernel Hilbert Space](https://mlsanity.com/paper/2506.01597/) (2025)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)
- [Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits](https://mlsanity.com/paper/2510.10690/) (2025)
- [Newton Losses: Using Curvature Information for Learning with Differentiable Algorithms](https://mlsanity.com/paper/2410.19055/) (2024)
- [Stochastic Newton Proximal Extragradient Method](https://mlsanity.com/paper/2406.01478/) (2024)
- [Distance-Aware Muon: Adaptive Step Scaling for Normalized Optimization](https://mlsanity.com/paper/2605.18999/) (2026)
- [Incremental Gauss--Newton Methods with Superlinear Convergence Rates](https://mlsanity.com/paper/2407.03195/) (2024)
- [Inertial Quadratic Majorization Minimization with Application to Kernel Regularized Learning](https://mlsanity.com/paper/2507.04247/) (2025)
- [Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees](https://mlsanity.com/paper/2508.19712/) (2025)
- [Gradient Regularized Newton Boosting Trees with Global Convergence](https://mlsanity.com/paper/2605.00581/) (2026)
- [On Optimization Complexity of Second-Order Certified Unlearning](https://mlsanity.com/paper/2607.20192/) (2026)
- [Primal Acceleration of Newton's Method](https://mlsanity.com/paper/2608.21359/) (2026)

## Abstract (arXiv)

We analyze the performance of a variant of Newton method with quadratic regularization for solving composite convex minimization problems. At each step of our method, we choose regularization parameter proportional to a certain power of the gradient norm at the current point. We introduce a family of problem classes characterized by H"older continuity of either the second or third derivative. Then we present the method with a simple adaptive search procedure allowing an automatic adjustment to the problem class with the best global complexity bounds, without knowing specific parameters of the problem. In particular, for the class of functions with Lipschitz continuous third derivative, we get the global O(1/k3) rate, which was previously attributed to third-order tensor methods. When the objective function is uniformly convex, we justify an automatic acceleration of our scheme, resulting in a faster global rate and local superlinear convergence. The switching between the different rates (sublinear, linear, and superlinear) is automatic. Again, for that, no a priori knowledge of parameters is needed.