Research map / Optimization / Nonconvex and smooth optimization
Affine-Invariant Global Non-Asymptotic Convergence Analysis of BFGS under Self-Concordance
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.
Proves global non-asymptotic linear and superlinear convergence of BFGS with weak Wolfe line search for strictly convex, strongly self-concordant functions, with affine-invariant rates depending only on the self-concordance constant and initial error.
Problem
Global non-asymptotic convergence guarantees for BFGS without strong convexity or Lipschitz gradient/Hessian assumptions, with rates that are affine invariant.
Approach
Replaces strong convexity and Lipschitz assumptions with strong self-concordance and uses weighted analysis (reweighting matrix P chosen as the Hessian at the optimum) to obtain affine-invariant global linear and superlinear rates for BFGS under Armijo-Wolfe line search.
Key results
- Global linear rate (f(x_t)-f*)/(f(x_0)-f*) <= (1 - alpha(1-beta)/(3(1+D_0)^2))^t for t >= Psi(bar B_0), with D_0 depending on initial suboptimality and strong self-concordance constant M.
- After a burn-in of t >= Psi(tilde B_0)+3D_0(...), the linear rate becomes independent of D_0: (1 - 2alpha(1-beta)/3)^t.
- Global superlinear rate of the form (C/t)^t, with explicit constant depending on t_0, Psi, and D_0; the step size eventually stabilizes at 1 after about d iterations in experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BFGS with Armijo-Wolfe line search on strictly convex, strongly self-concordant functions | BFGS · Strictly convex, strongly self-concordant functions | function-value gap ratio: \left(1 - \frac{\alpha(1 - \beta)e^{-\frac{\Psi(\bar{B}_0)}{t}}}{(1 + D_0)^2}\right)^{t} | Helped |
| After the stated iteration threshold, use the global linear-rate guarantee independent of D_0 and B_0 | BFGS · Strictly convex, strongly self-concordant functions | function-value gap ratio: \left(1 - \frac{2\alpha(1 - \beta)}{3} \right)^{t} | Helped |
| Use BFGS with Armijo-Wolfe line search to obtain the global superlinear guarantee | BFGS · Strictly convex, strongly self-concordant functions | function-value gap ratio: \left(\frac{\delta_6 t_0 + \delta_7 \Psi(\tilde{B}_0) + \delta_8 D_0 (\Psi(\bar{B}_{0}) + \frac{3(1 + D_0)^2}{\alpha(1 - | Helped |
| Use BFGS instead of gradient descent or accelerated gradient descent | BFGS · Hard cubic function | convergence | Helped |
| Initialize BFGS with cI instead of I (ablation) | BFGS · Hard cubic function | convergence | No clear effect |
| Initialize BFGS with cI instead of I (ablation) | BFGS · Logistic regression | convergence | Helped |
| Apply a non-singular ill-conditioned coordinate transformation | BFGS · Hard cubic function | convergence trajectory | No clear effect |
| Apply a non-singular ill-conditioned coordinate transformation | gradient descent and accelerated gradient descent · Hard cubic function | convergence | Hurt |
| Use BFGS instead of gradient descent or accelerated gradient descent | BFGS · Logistic regression | convergence | Helped |
Surprising findings
- Experiments show BFGS with B_0=cI and B_0=I perform nearly identically on the hard cubic function.
Limitations
- Relies on strong self-concordance, which is stronger than standard self-concordance (authors note extension is future work).
- Rates depend on initial suboptimality D_0 and the initial Hessian approximation through Psi terms, so the transition to the fast rate can require many iterations.
- Experiments are limited to two functions in small-scale settings.
Experimental setup
Benchmarks: hard cubic function logistic regression
Metrics: function value suboptimality versus iterations step sizes gradient evaluations running time
Baselines: gradient descent accelerated gradient descent
Builds on: BFGS Wolfe line search self-concordant function theory
Closest papers by meaning
- Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Search (NeurIPS 2024 · similarity 0.94)
- Sharpened Quasi-Newton Methods: Faster Superlinear Rate and Larger Local Convergence Neighborhood (ICML 2022 · similarity 0.91)
- Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates (AAAI 2024 · similarity 0.87)
- Skip the Hessian, Keep the Rates: Globalized Semismooth Newton with Lazy Hessian Updates (NeurIPS 2026 · similarity 0.87)
- A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees (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.86)
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.