mlsanityData to 7 Oct 2026

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

arXiv 1806.00413 ↗First posted 1 Jun 2018cs.LG math.OC stat.MLcited by 24

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 4; 2023: 8; 2024: 2; 2025: 4; 2026: 2.

24 papers.

Sort:

By area:

  1. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
  2. 2021Differentially private inference via noisy optimizationcited by 27
  3. 2022FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learningcited by 23
  4. 2022Second-order optimization with lazy Hessianscited by 13
  5. 2023Faster Differentially Private Convex Optimization via Second-Order Methodscited by 13
  6. 2023Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methodscited by 10
  7. 2023PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimatescited by 10
  8. 2022Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methodscited by 8
  9. 2021Curvature-Aware Derivative-Free Optimizationcited by 7
  10. 2023Gradient Descent Converges Linearly for Logistic Regression on Separable Datacited by 7
  11. 2023Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Methodcited by 7
  12. 2021A Stochastic Newton Algorithm for Distributed Convex Optimizationcited by 6
12 more
  1. 2025NeST-BO: Fast Local Bayesian Optimization via Newton-Step Targeting of Gradient and Hessian Informationcited by 6
  2. 2023Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacycited by 4
  3. 2025SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learningcited by 4
  4. 2023Sketch-and-Project Meets Newton Method: Global mathcal O(k-2) Convergence with Low-Rank Updatescited by 3
  5. 2024Regularized Gauss-Newton for Optimizing Overparameterized Neural Networkscited by 3
  6. 2025Gradient-Normalized Smoothness for Optimization with Approximate Hessianscited by 3
  7. 2022Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretationcited by 1
  8. 2024Level Set Teleportation: An Optimization Perspectivecited by 1
  9. 2023Unnatural Algorithms in Machine Learningcited by 0
  10. 2025A Split-Client Approach to Second-Order Optimizationcited by 0
  11. 2026Fast, Parallel, Query-Efficient Binary Classificationcited by 0
  12. 2026On Optimization Complexity of Second-Order Certified Unlearningcited by 0