Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension $n\geq 4$
2026-07-23 • Artificial Intelligence
Artificial IntelligenceMachine Learning
AI summaryⓘ
The authors study the Barzilai–Borwein (BB) method, a technique used to solve optimization problems, and focus on how fast it converges when applied to certain smooth problems. They show that for dimensions four and higher, there are many strictly convex quadratic problems and starting points where the BB method always converges but never very quickly (not superlinearly). Using a detailed and computer-assisted argument, they prove that the error decreases at a steady geometric rate instead of getting rapidly smaller. This means that in these cases, the BB method's convergence speed is fundamentally limited.
Barzilai-Borwein methodconvergence ratesuperlinear convergencestrictly convex quadraticgradient methodoptimizationspectral componentsgeometric convergenceprojectivized dynamicscomputer-assisted proof
Authors
Dawei Li, Xiaotian Jiang, Mingyi Hong
Abstract
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. We provide a negative answer to this question. Specifically, for every finite dimension $n\geq4$, we 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 $ρ_{\min}=10^{-6},ρ_{\max}=0.61$, every spectral component of the gradient is bounded above and below by the corresponding geometric sequence. Consequently, the gradient norm and the energy norm of the error satisfy two-sided geometric estimates with the same rates, while the objective gap satisfies the corresponding estimates with squared rates. In particular, all three quantities are bounded below by geometric sequences, ruling out superlinear convergence. The construction is highly nontrivial, based on a computer-assisted proof of a nonresonant, attracting seven-cycle of the projectivized BB dynamics in dimension four.