Newton Method Revisited: Global Convergence Rates up to \mathcal O(k^-3 ) for Stepsize Schedules and Linesearch Procedures

2024/05/29 by Slavomír Hanzely, Hanzely, Slavomír, Farshed Abdukhakimov +3
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Iterative Methods for Nonlinear Equations #Numerical Methods and Algorithms #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2405.18926

openalex publication_date 2024/05/29 · openalex created_date 2024/05/31 · openalex updated_date 2026/07/28

Abstract

This paper investigates the global convergence of stepsized Newton methods for convex functions with Hölder continuous Hessians or third derivatives. We propose several simple stepsize schedules with fast global convergence guarantees, up to \mathcal O(k^-3 ). For cases with multiple plausible smoothness parameterizations or an unknown smoothness constant, we introduce a stepsize linesearch and a backtracking procedure with provable convergence as if the optimal smoothness parameters were known in advance. Additionally, we present strong convergence guarantees for the practically popular Newton method with exact linesearch.

Related

• Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees
• Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
• A Damped Newton Method Achieves Global O((1)/(k²)) and Local Quadratic Convergence Rate
• Regularized Newton Method with Global O(1/k²) Convergence
• Multilevel Regularized Newton Methods with Fast Convergence Rates