Research map / Optimization / Nonconvex and smooth optimization
Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first explicit non-asymptotic global linear and superlinear convergence rates for BFGS with an Armijo-Wolfe line search on strongly convex functions, plus a log-bisection line search and complexity bounds.
Problem
Global non-asymptotic convergence rates of BFGS with inexact (Armijo-Wolfe) line search on strongly convex smooth functions, where prior results were asymptotic or only local, or gave weaker rates than gradient descent.
Approach
Combines a Broyden-class potential function Psi(A)=Tr(A)-d-log Det(A) with weighted-norm analysis (weight P=LI or the Hessian at optimum) and Armijo-Wolfe bounds on the step-size ratios, yielding a linear rate (1-1/kappa)^t matching gradient descent, a condition-number-free linear rate under Hessian Lipschitzness, and a global superlinear rate.
Key results
- BFGS with Armijo-Wolfe line search and B0=LI attains global linear rate (1-1/kappa)^t from the first iteration, matching gradient descent's rate.
- With Lipschitz Hessian, BFGS reaches a condition-number-free linear rate (1-alpha(1-beta)*2/3)^t after roughly d*kappa (B0=LI) or (1+3C0)d log kappa (B0=mu I) iterations.
- Global superlinear rate of O((C'/t)^t) is established, with line-search evaluations per iteration bounded on average and constant in the superlinear phase.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Armijo-Wolfe line search with BFGS instead of exact line search | BFGS · Strongly convex, L-smooth functions | global linear convergence rate: (1 - e^{-\frac{\Psi(\bar{B}_0)}{t}}\frac{1}{\kappa(1+\sqrt{\kappa})})^{t} -> (1 - e^{-\frac{\Psi(\bar{B}_0)}{t}}\frac{2\ | Helped |
| Initialize B_0 = LI rather than B_0 = μI (ablation) | BFGS with Armijo-Wolfe · Strongly convex, L-smooth functions | iterations to reach the stated linear phase: 1 -> d\log\kappa | Helped |
| Initialize B_0 = μI rather than B_0 = LI (ablation) | BFGS with Armijo-Wolfe · Hessian-Lipschitz strongly convex functions | iterations to reach condition number-independent linear convergence: d\kappa + \frac{9}{\alpha(1 - \beta)}C_0 \kappa -> (1 + 3C_0)d\log{\kappa} + \frac{9}{\alpha(1 - \beta)}C_0 \kappa | Mixed |
| Assume the objective Hessian is Lipschitz continuous | BFGS with Armijo-Wolfe · Strongly convex functions | linear convergence rate: (1 - \frac{1}{\kappa})^t -> (1 - \frac{2\alpha(1 - \beta)}{3} )^{t} | Helped |
| Initialize B_0 = μI rather than B_0 = LI (ablation) | BFGS with Armijo-Wolfe · Hessian-Lipschitz strongly convex functions | iterations to reach the superlinear phase: d\kappa -> d\log{\kappa} | Helped |
| Initialize B_0 = μI rather than B_0 = LI (ablation) | BFGS with Armijo-Wolfe · Hessian-Lipschitz strongly convex functions | global superlinear convergence rate: \mathcal{O}((\frac{d\kappa + C_0 \kappa}{t})^{t}) -> \mathcal{O}((\frac{C_0 d\log{\kappa} + C_0 \kappa}{t})^{t}) | Mixed |
| Initialize B_0 = I or B_0 = cI instead of B_0 = μI (ablation) | BFGS with Armijo-Wolfe · Cubic objective numerical experiments | function suboptimality ratio | No clear effect |
| Initialize B_0 = LI rather than B_0 = μI (ablation) | BFGS with Armijo-Wolfe · Cubic objective numerical experiments | early convergence | Helped |
Surprising findings
- Initializing with B0=mu I can require fewer iterations than B0=LI to reach the condition-number-free linear rate when C0 is small relative to kappa.
- In experiments, BFGS with B0=LI starts faster but transitions to superlinear convergence later than with B0=mu I, and this delay grows with kappa.
Limitations
- Analysis applies only to strongly convex functions; general convex case is open.
- Only covers BFGS, not the full convex Broyden class including DFP.
- Rates for condition-number-free linear and superlinear phases require an additional Lipschitz-Hessian assumption.
Experimental setup
Benchmarks: synthetic cubic objective (Nesterov-style lower bound function)
Metrics: function suboptimality ratio (f(x_t)-f*)/(f(x_0)-f*) vs iter
Baselines: BFGS with exact line search (Rodomanov & Nesterov) gradient descent with backtracking line search BFGS with B0 = I BFGS with B0 = cI
Builds on: BFGS Armijo-Wolfe line search Broyden-class potential function analysis (Rodomanov & Nesterov) Dennis-Moré superlinear analysis
Closest papers by meaning
- Affine-Invariant Global Non-Asymptotic Convergence Analysis of BFGS under Self-Concordance (NeurIPS 2025 · similarity 0.94)
- Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster (ICML 2025 · similarity 0.88)
- A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees (NeurIPS 2025 · similarity 0.87)
- Skip the Hessian, Keep the Rates: Globalized Semismooth Newton with Lazy Hessian Updates (NeurIPS 2026 · similarity 0.87)
- Balancing Gradient and Hessian Queries in Non-Convex Optimization (NeurIPS 2025 · similarity 0.86)
- Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximations (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.