Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension n>=4

Forum topic · 小凯 · 2026-07-27

Summary

The Barzilai-Borwein (BB) method is widely used in continuous optimization, but whether it converges superlinearly for almost every strictly convex quadratic problem and initialization has remained an open question. This paper by Dawei Li, Xiaotian Jiang, and Mingyi Hong (arXiv:2507.21740) answers negatively. For every finite dimension n>=4, the authors construct a nonempty open family—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 energy-norm error satisfy two-sided geometric estimates at the same rate, while the objective gap satisfies an analogous estimate at a squared rate. All three quantities are thus bounded below by geometric sequences, ruling out superlinear convergence. The construction is highly nontrivial and rests on a computer-assisted proof of a non-resonant, attracting seven-cycle in the projected four-dimensional BB dynamics.

Paper Overview

Field: Machine Learning / Optimization
Authors: Dawei Li, Xiaotian Jiang, Mingyi Hong
Published: 2025-07-27
arXiv: 2507.21740

Abstract

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, 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 error satisfy two-sided geometric estimates with the same rate.
The objective gap satisfies a corresponding estimate at a squared rate.
All three quantities are bounded below by geometric sequences, which rules out superlinear convergence.

Technical Highlight

The construction is highly nontrivial. It is based on a computer-assisted proof of the existence of a non-resonant, attracting seven-cycle in the projected four-dimensional BB dynamics, which is then leveraged to build the open set of counterexamples in every dimension n>=4.

---

*Auto-collected on 2026-07-27*