# Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods

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

## Key facts

- Cited by 16 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 30 Mar 2020.

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

- [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)
- [Faster Differentially Private Convex Optimization via Second-Order Methods](https://mlsanity.com/paper/2305.13209/) (2023)
- [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)
- [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)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (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)
- [Limited-Memory Greedy Quasi-Newton Method with Non-asymptotic Superlinear Convergence Rate](https://mlsanity.com/paper/2306.15444/) (2023)
- [Incremental Gauss--Newton Methods with Superlinear Convergence Rates](https://mlsanity.com/paper/2407.03195/) (2024)
- [Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees](https://mlsanity.com/paper/2508.19712/) (2025)
- [Primal Acceleration of Newton's Method](https://mlsanity.com/paper/2608.21359/) (2026)

## Abstract (arXiv)

In this paper, we study and prove the non-asymptotic superlinear convergence rate of the Broyden class of quasi-Newton algorithms which includes the Davidon--Fletcher--Powell (DFP) method and the Broyden--Fletcher--Goldfarb--Shanno (BFGS) method. The asymptotic superlinear convergence rate of these quasi-Newton methods has been extensively studied in the literature, but their explicit finite-time local convergence rate is not fully investigated. In this paper, we provide a finite-time (non-asymptotic) convergence analysis for Broyden quasi-Newton algorithms under the assumptions that the objective function is strongly convex, its gradient is Lipschitz continuous, and its Hessian is Lipschitz continuous at the optimal solution. We show that in a local neighborhood of the optimal solution, the iterates generated by both DFP and BFGS converge to the optimal solution at a superlinear rate of (1/k)k/2, where k is the number of iterations. We also prove a similar local superlinear convergence result holds for the case that the objective function is self-concordant. Numerical experiments on several datasets confirm our explicit convergence rate bounds. Our theoretical guarantee is one of the first results that provide a non-asymptotic superlinear convergence rate for quasi-Newton methods.