# Rates of superlinear convergence for classical quasi-Newton methods

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Mar 2020.

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

- [Provably Convergent Plug-and-Play Quasi-Newton Methods](https://mlsanity.com/paper/2303.07271/) (2023)
- [Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence](https://mlsanity.com/paper/2204.09266/) (2022)
- [Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence](https://mlsanity.com/paper/2302.08580/) (2023)
- [Quasi-Newton Methods for Saddle Point Problems and Beyond](https://mlsanity.com/paper/2111.02708/) (2021)
- [Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization](https://mlsanity.com/paper/2306.02212/) (2023)
- [Approximate Newton policy gradient algorithms](https://mlsanity.com/paper/2110.02398/) (2021)
- [Multiple Greedy Quasi-Newton Methods for Saddle Point Problems](https://mlsanity.com/paper/2408.00241/) (2024)
- [Gradient Methods with Online Scaling Part I. Theoretical Foundations](https://mlsanity.com/paper/2505.23081/) (2025)
- [Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach](https://mlsanity.com/paper/2106.05445/) (2021)
- [qNBO: quasi-Newton Meets Bilevel Optimization](https://mlsanity.com/paper/2502.01076/) (2025)
- [Sharpened Lazy Incremental Quasi-Newton Method](https://mlsanity.com/paper/2305.17283/) (2023)
- [NumS: Scalable Array Programming for the Cloud](https://mlsanity.com/paper/2206.14276/) (2022)
- [Limited-Memory Greedy Quasi-Newton Method with Non-asymptotic Superlinear Convergence Rate](https://mlsanity.com/paper/2306.15444/) (2023)

## Abstract (arXiv)

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 (fracn L2μ2 k)k/2 and (fracn Lμ k)k/2 respectively, where k is the iteration counter, n is the dimension of the problem, μ is the strong convexity parameter, and L is the Lipschitz constant of the gradient.