Rates of superlinear convergence for classical quasi-Newton methods

Abstract

We study the local convergence of classical quasi-Newton methods for nonlinear optimization. Although it was well established a long time ago that asymptotically these methods converge superlinearly, the corresponding rates of convergence still remain unknown. In this paper, we address this problem. We obtain first explicit non-asymptotic rates of superlinear convergence for the standard quasi-Newton methods, which are based on the updating formulas from the convex Broyden class. In particular, for the well-known DFP and BFGS methods, we obtain the rates of the form $(\frac{n{L}^2}{{\mu }^{2}k}{)}^{k/2}$ and $(\frac{nL}{\mu k}{)}^{k/2}$ respectively, where $k$ is the iteration counter, $n$ is the dimension of the problem, $\mu$ is the strong convexity parameter, and $L$ is the Lipschitz constant of the gradient.

References in corpus (1)

• Fast Linear Convergence of Randomized BFGS

Cited by in corpus (8)

• New Results on Superlinear Convergence of Classical Quasi-Newton Methods
• Explicit Superlinear Convergence Rates of The SR1 Algorithm
• Approximate Newton policy gradient algorithms
• Explicit Superlinear Convergence Rates of Broyden's Methods in Nonlinear Equations
• Hybrid Acceleration Scheme for Variance Reduced Stochastic Optimization Algorithms
• A trust region-type normal map-based semismooth Newton method for nonsmooth nonconvex composite optimization
• Quasi-Newton Methods for Saddle Point Problems and Beyond
• Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach