Paper Overview
Field: Machine Learning / Optimization Authors: Dawei Li, Xiaotian Jiang, Mingyi Hong arXiv: 2507.20474
Summary
The Barzilai-Borwein (BB) method has shown strong practical performance in continuous optimization, yet its convergence dynamics remains poorly understood. In particular, a central unresolved question is whether BB converges superlinearly for almost every strictly convex quadratic problem and initialization. This paper provides a negative answer to this question.
Specifically, for every finite dimension n >= 4, the authors construct a nonempty open—hence positive-Lebesgue-measure—family of strictly convex quadratic problems and initial points for which the long Barzilai-Borwein method (BB1) converges but cannot converge root-superlinearly.
More precisely, with the explicit constants rho_min = 10^{-6} and rho_max = 0.61, every spectral component of the gradient is bounded above and below by the corresponding geometric sequences. As a result:
- The gradient norm and the energy norm of the error satisfy two-sided geometric estimates with the same rate.
- The objective gap satisfies a corresponding estimate with a squared rate.
- All three quantities are bounded below by geometric sequences, excluding superlinear convergence.
- Negative resolution of the open question on almost-everywhere superlinear convergence of BB for strictly convex quadratics.
- An explicit open set of problem/initialization pairs (positive Lebesgue measure) where BB1 fails to converge root-superlinearly.
- Quantitative two-sided geometric convergence bounds with explicit constants.
- A computer-assisted analysis of a seven-period attracting cycle in projected BB dynamics.
The construction is highly nontrivial and is based on a computer-assisted proof of a non-resonant, attracting seven-cycle of the four-dimensional projected BB dynamics.