# Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 47 references that are in the map.
- First posted on arXiv 23 May 2022.

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

- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information](https://mlsanity.com/paper/1708.07164/) (2017)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [Convergence rates of sub-sampled Newton methods](https://mlsanity.com/paper/1508.02810/) (2015)
- [Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression](https://mlsanity.com/paper/1303.6149/) (2013)
- [Global convergence rate analysis of unconstrained optimization methods based on probabilistic models](https://mlsanity.com/paper/1505.06070/) (2015)
- [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)
- [Sub-sampled Newton Methods with Non-uniform Sampling](https://mlsanity.com/paper/1607.00559/) (2016)
- [Stochastic Subspace Cubic Newton Method](https://mlsanity.com/paper/2002.09526/) (2020)
- [SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization](https://mlsanity.com/paper/1502.02268/) (2015)
- [Randomized Block Cubic Newton Method](https://mlsanity.com/paper/1802.04084/) (2018)
- [Sketched Newton-Raphson](https://mlsanity.com/paper/2006.12120/) (2020)
- [Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization](https://mlsanity.com/paper/1802.07372/) (2018)
- [Minimizing Uniformly Convex Functions by Cubic Regularization of Newton Method](https://mlsanity.com/paper/1905.02671/) (2019)
- [A globally convergent incremental Newton method](https://mlsanity.com/paper/1410.5284/) (2014)
- [Practical Inexact Proximal Quasi-Newton Method with Global Complexity Analysis](https://mlsanity.com/paper/1311.6547/) (2013)
- [Inexact Successive Quadratic Approximation for Regularized Optimization](https://mlsanity.com/paper/1803.01298/) (2018)
- [Penalty & Augmented Kaczmarz Methods For Linear Systems & Linear Feasibility Problems](https://mlsanity.com/paper/2205.08085/) (2022)

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

- [ALS: Augmented Lagrangian Sketching Methods for Linear Systems](https://mlsanity.com/paper/2208.06152/) (2022)

## Abstract (arXiv)

We propose two variants of Newton method for solving unconstrained minimization problem. Our method leverages optimization techniques such as penalty and augmented Lagrangian method to generate novel variants of the Newton method namely the Penalty Newton method and the Augmented Newton method. In doing so, we recover several well-known existing Newton method variants such as Damped Newton, Levenberg, and Levenberg-Marquardt methods as special cases. Moreover, the proposed Augmented Newton method can be interpreted as Newton method with adaptive heavy ball momentum. We provide global convergence results for the proposed methods under mild assumptions that hold for a wide variety of problems. The proposed methods can be sought as the penalty and augmented extensions of the results obtained by Karimireddy et. al [24].