mlsanityData to 14 Oct 2026

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

arXiv 2112.02089 ↗First posted 3 Dec 2021math.OC cs.LGcited by 22

Not on the map. Why?

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.

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

28 of 74 references.

References · 28

  1. 2021Convex optimizationcited by 2,515
  2. 2018OpenPose: Realtime Multi-Person 2D Pose Estimation using Part Affinity Fieldscited by 1,162
  3. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  4. 2015Optimizing Neural Networks with Kronecker-factored Approximate Curvaturecited by 796
  5. 2019SGD: General Analysis and Improved Ratescited by 207
  6. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
  7. 2019Adaptive Gradient Descent without Descentcited by 79
  8. 2020Practical Quasi-Newton Methods for Training Deep Neural Networkscited by 68
  9. 2019Wireless Networks Design in the Era of Deep Learning: Model-Based, AI-Based, or Both?cited by 38
  10. 2019RSN: Randomized Subspace Newtoncited by 34
  11. 2019Efficient Subsampled Gauss-Newton and Natural Gradient Methods for Training Neural Networkscited by 33
  12. 2017Oracle Complexity of Second-Order Methods for Smooth Convex Optimizationcited by 24
16 more
  1. 2019Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Ratescited by 24
  2. 2020Greedy Quasi-Newton Methods with Explicit Superlinear Convergencecited by 21
  3. 2020Stochastic Subspace Cubic Newton Methodcited by 21
  4. 2019Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Lossescited by 17
  5. 2020Practical Reinforcement Learning For MPC: Learning from sparse objectives in under an hour on a real robotcited by 17
  6. 2018Randomized Block Cubic Newton Methodcited by 14
  7. 2019Curious iLQR: Resolving Uncertainty in Model-based RLcited by 11
  8. 2020Curiosities and counterexamples in smooth convex optimizationcited by 7
  9. 2016Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracycited by 5
  10. 2018A Distributed Second-Order Algorithm You Can Trustcited by 5
  11. 2019DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Ratecited by 5
  12. 2020Convergence and Complexity Analysis of a Levenberg-Marquardt Algorithm for Inverse Problemscited by 4
  13. 2020Inexact Tensor Methods with Dynamic Accuraciescited by 3
  14. 2015A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity O(1/n^2)cited by 2
  15. 2020DINO: Distributed Newton-Type Optimization Methodcited by 2
  16. 2021Optimization Methods for Fully Composite Problemscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 5; 2023: 6; 2024: 3; 2025: 2; 2026: 5.

22 papers.

Sort:

By area:

  1. 2022FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learningcited by 23
  2. 2022The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimizationcited by 20
  3. 2022Super-Universal Regularized Newton Methodcited by 20
  4. 2022Second-order optimization with lazy Hessianscited by 15
  5. 2023Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methodscited by 12
  6. 2022Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methodscited by 8
  7. 2024The Iterative Optimal Brain Surgeon: Faster Sparse Recovery by Leveraging Second-Order Informationcited by 8
  8. 2023Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Methodcited by 7
  9. 2023Rethinking Gauss-Newton for learning over-parameterized modelscited by 6
  10. 2023SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithmscited by 5
  11. 2024CoVO-MPC: Theoretical Analysis of Sampling-based MPC and Optimal Covariance Designcited by 4
  12. 2021SCORE: Approximating Curvature Information under Self-Concordant Regularizationcited by 3
10 more
  1. 2023Sketch-and-Project Meets Newton Method: Global mathcal O(k-2) Convergence with Low-Rank Updatescited by 3
  2. 2025Gradient-Normalized Smoothness for Optimization with Approximate Hessianscited by 3
  3. 2023Self-concordant smoothing in proximal quasi-Newton algorithms for large-scale convex composite optimizationcited by 1
  4. 2026Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrencecited by 1
  5. 2024Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problemscited by 0
  6. 2025Second-Order Optimization with Asynchronous Curvaturecited by 0
  7. 2026Beyond SGD, Without SVD: Proximal Subspace Iteration LoRA with Diagonal Fractional K-FACcited by 0
  8. 2026Gradient Regularized Newton Boosting Trees with Global Convergencecited by 0
  9. 2026Convergence Analysis of Newton's Method for Neural Networks in the Overparameterized Limitcited by 0
  10. 2026Primal Acceleration of Newton's Methodcited by 0