# Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2018.

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

- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Differentially private inference via noisy optimization](https://mlsanity.com/paper/2103.11003/) (2021)
- [FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learning](https://mlsanity.com/paper/2206.08829/) (2022)
- [Second-order optimization with lazy Hessians](https://mlsanity.com/paper/2212.00781/) (2022)
- [Faster Differentially Private Convex Optimization via Second-Order Methods](https://mlsanity.com/paper/2305.13209/) (2023)
- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimates](https://mlsanity.com/paper/2309.02014/) (2023)
- [Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods](https://mlsanity.com/paper/2211.01832/) (2022)
- [Curvature-Aware Derivative-Free Optimization](https://mlsanity.com/paper/2109.13391/) (2021)
- [Gradient Descent Converges Linearly for Logistic Regression on Separable Data](https://mlsanity.com/paper/2306.14381/) (2023)
- [Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method](https://mlsanity.com/paper/2308.14742/) (2023)
- [A Stochastic Newton Algorithm for Distributed Convex Optimization](https://mlsanity.com/paper/2110.02954/) (2021)
- [NeST-BO: Fast Local Bayesian Optimization via Newton-Step Targeting of Gradient and Hessian Information](https://mlsanity.com/paper/2510.05516/) (2025)
- [Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy](https://mlsanity.com/paper/2310.14661/) (2023)
- [SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning](https://mlsanity.com/paper/2501.15941/) (2025)
- [Sketch-and-Project Meets Newton Method: Global mathcal O(k-2) Convergence with Low-Rank Updates](https://mlsanity.com/paper/2305.13082/) (2023)
- [Regularized Gauss-Newton for Optimizing Overparameterized Neural Networks](https://mlsanity.com/paper/2404.14875/) (2024)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)
- [Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretation](https://mlsanity.com/paper/2205.11033/) (2022)
- [Level Set Teleportation: An Optimization Perspective](https://mlsanity.com/paper/2403.03362/) (2024)
- [Unnatural Algorithms in Machine Learning](https://mlsanity.com/paper/2312.04739/) (2023)
- [Second-Order Optimization with Asynchronous Curvature](https://mlsanity.com/paper/2510.15714/) (2025)
- [Fast, Parallel, Query-Efficient Binary Classification](https://mlsanity.com/paper/2607.04062/) (2026)
- [On Optimization Complexity of Second-Order Certified Unlearning](https://mlsanity.com/paper/2607.20192/) (2026)

## Abstract (arXiv)

We show that Newton's method converges globally at a linear rate for objective functions whose Hessians are stable. This class of problems includes many functions which are not strongly convex, such as logistic regression. Our linear convergence result is (i) affine-invariant, and holds even if an (ii) approximate Hessian is used, and if the subproblems are (iii) only solved approximately. Thus we theoretically demonstrate the superiority of Newton's method over first-order methods, which would only achieve a sublinear O(1/t2) rate under similar conditions.