# Global Complexity Analysis of BFGS

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2024.

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

- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)

## Abstract (arXiv)

In this paper, we present a global complexity analysis of the classical BFGS method with inexact line search, as applied to minimizing a strongly convex function with Lipschitz continuous gradient and Hessian. We consider a variety of standard line search strategies including the backtracking line search based on the Armijo condition, Armijo-Goldstein and Wolfe-Powell line searches. Our analysis suggests that the convergence of the algorithm proceeds in several different stages before the fast superlinear convergence actually begins. Furthermore, once the initial point is far away from the minimizer, the starting moment of superlinear convergence may be quite large. We show, however, that this drawback can be easily rectified by using a simple restarting procedure.