Paper: Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension n>=4
- Authors: Dawei Li, Xiaotian Jiang, Mingyi Hong
- arXiv: 2507.21740
- Posted: 2025-07-27
- Field: Machine Learning / Optimization
- For every finite dimension n>=4, the authors construct a nonempty open set (hence of positive Lebesgue measure) of strictly convex quadratic problems and initial points for which the long Barzilai-Borwein method (BB1) converges but cannot converge root-superlinearly.
- With explicit constants rho_min = 10^-6 and rho_max = 0.61, every spectral component of the gradient is bounded above and below by corresponding geometric sequences.
- Consequently:
- The gradient norm and the error in energy norm satisfy two-sided geometric estimates with the same rate.
- The objective gap satisfies a corresponding squared-rate estimate.
- In particular, all three quantities are bounded below by geometric sequences, which rules out superlinear convergence.
- The construction is highly nontrivial and is based on a computer-assisted proof of a non-resonant, attracting seven-cycle in the four-dimensional projected BB dynamics.
Summary
The Barzilai-Borwein (BB) method has shown strong practical performance in continuous optimization, yet its convergence dynamics remains poorly understood. A central unresolved question is whether BB converges superlinearly for almost every strictly convex quadratic problem and initialization. This paper provides a negative answer.
Key Points
Significance
This result resolves a long-standing open question in optimization theory by showing that superlinear convergence of BB methods is not a generic property even on strictly convex quadratics—its failure occurs on an open, positive-measure set in every dimension n>=4.