# Regularized Newton Method with Global O(1/k2) Convergence

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 74 references that are in the map.
- First posted on arXiv 3 Dec 2021.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [OpenPose: Realtime Multi-Person 2D Pose Estimation using Part Affinity Fields](https://mlsanity.com/paper/1812.08008/) (2018)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [Practical Quasi-Newton Methods for Training Deep Neural Networks](https://mlsanity.com/paper/2006.08877/) (2020)
- [Wireless Networks Design in the Era of Deep Learning: Model-Based, AI-Based, or Both?](https://mlsanity.com/paper/1902.02647/) (2019)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [Efficient Subsampled Gauss-Newton and Natural Gradient Methods for Training Neural Networks](https://mlsanity.com/paper/1906.02353/) (2019)
- [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)
- [Greedy Quasi-Newton Methods with Explicit Superlinear Convergence](https://mlsanity.com/paper/2002.00657/) (2020)
- [Stochastic Subspace Cubic Newton Method](https://mlsanity.com/paper/2002.09526/) (2020)
- [Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses](https://mlsanity.com/paper/1907.01771/) (2019)
- [Practical Reinforcement Learning For MPC: Learning from sparse objectives in under an hour on a real robot](https://mlsanity.com/paper/2003.03200/) (2020)
- [Randomized Block Cubic Newton Method](https://mlsanity.com/paper/1802.04084/) (2018)
- [Curious iLQR: Resolving Uncertainty in Model-based RL](https://mlsanity.com/paper/1904.06786/) (2019)
- [Curiosities and counterexamples in smooth convex optimization](https://mlsanity.com/paper/2001.07999/) (2020)
- [Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy](https://mlsanity.com/paper/1605.07659/) (2016)
- [A Distributed Second-Order Algorithm You Can Trust](https://mlsanity.com/paper/1806.07569/) (2018)
- [DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate](https://mlsanity.com/paper/1906.00506/) (2019)
- [Convergence and Complexity Analysis of a Levenberg-Marquardt Algorithm for Inverse Problems](https://mlsanity.com/paper/2004.03005/) (2020)
- [Inexact Tensor Methods with Dynamic Accuracies](https://mlsanity.com/paper/2002.09403/) (2020)
- [A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity O(1/n^2)](https://mlsanity.com/paper/1502.04286/) (2015)
- [DINO: Distributed Newton-Type Optimization Method](https://mlsanity.com/paper/2006.03694/) (2020)
- [Optimization Methods for Fully Composite Problems](https://mlsanity.com/paper/2103.12632/) (2021)

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

- [FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learning](https://mlsanity.com/paper/2206.08829/) (2022)
- [The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization](https://mlsanity.com/paper/2205.09647/) (2022)
- [Super-Universal Regularized Newton Method](https://mlsanity.com/paper/2208.05888/) (2022)
- [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)
- [Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods](https://mlsanity.com/paper/2211.01832/) (2022)
- [The Iterative Optimal Brain Surgeon: Faster Sparse Recovery by Leveraging Second-Order Information](https://mlsanity.com/paper/2408.17163/) (2024)
- [Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method](https://mlsanity.com/paper/2308.14742/) (2023)
- [Rethinking Gauss-Newton for learning over-parameterized models](https://mlsanity.com/paper/2302.02904/) (2023)
- [SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithms](https://mlsanity.com/paper/2312.17369/) (2023)
- [CoVO-MPC: Theoretical Analysis of Sampling-based MPC and Optimal Covariance Design](https://mlsanity.com/paper/2401.07369/) (2024)
- [SCORE: Approximating Curvature Information under Self-Concordant Regularization](https://mlsanity.com/paper/2112.07344/) (2021)
- [Sketch-and-Project Meets Newton Method: Global mathcal O(k-2) Convergence with Low-Rank Updates](https://mlsanity.com/paper/2305.13082/) (2023)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)
- [Self-concordant smoothing in proximal quasi-Newton algorithms for large-scale convex composite optimization](https://mlsanity.com/paper/2309.01781/) (2023)
- [Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence](https://mlsanity.com/paper/2608.22129/) (2026)
- [Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems](https://mlsanity.com/paper/2411.15769/) (2024)
- [Second-Order Optimization with Asynchronous Curvature](https://mlsanity.com/paper/2510.15714/) (2025)
- [Beyond SGD, Without SVD: Proximal Subspace Iteration LoRA with Diagonal Fractional K-FAC](https://mlsanity.com/paper/2602.16456/) (2026)
- [Gradient Regularized Newton Boosting Trees with Global Convergence](https://mlsanity.com/paper/2605.00581/) (2026)
- [Convergence Analysis of Newton's Method for Neural Networks in the Overparameterized Limit](https://mlsanity.com/paper/2605.08352/) (2026)
- [Primal Acceleration of Newton's Method](https://mlsanity.com/paper/2608.21359/) (2026)

## Abstract (arXiv)

We present a Newton-type method that converges fast from any initialization and for arbitrary convex objectives with Lipschitz Hessians. We achieve this by merging the ideas of cubic regularization with a certain adaptive Levenberg--Marquardt penalty. In particular, we show that the iterates given by xk+1=xk - bigl(nabla2 f(xk) + √H|nabla f(xk)| Ibigr)-1nabla f(xk), where H>0 is a constant, converge globally with a O(frac1k2) rate. Our method is the first variant of Newton's method that has both cheap iterations and provably fast global convergence. Moreover, we prove that locally our method converges superlinearly when the objective is strongly convex. To boost the method's performance, we present a line search procedure that does not need prior knowledge of H and is provably efficient.