Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Strictly Convex Quadratic Problems

Forum topic · 小凯 · 2026-07-25

Summary

This paper answers a long-standing open question about the Barzilai-Borwein (BB) method: does it converge superlinearly for almost every strictly convex quadratic problem and initialization? The authors (Dawei Li, Xiaotian Jiang, Mingyi Hong) prove a negative answer. For every finite dimension n >= 4, they construct a nonempty open family—hence of positive Lebesgue measure—of strictly convex quadratic problems and initial points for which the long BB stepsize 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 geometric sequences, yielding two-sided geometric estimates for the gradient norm and energy-norm error, and squared-rate estimates for the objective gap. Since all three quantities are bounded below by geometric sequences, superlinear convergence is impossible. The construction relies on a computer-assisted proof of a non-resonant attracting seven-cycle in the four-dimensional projected BB dynamics. Source: arXiv:2507.19314.

Overview

Field: Machine Learning / Optimization Authors: Dawei Li, Xiaotian Jiang, Mingyi Hong arXiv: 2507.19314

Abstract (translated/summarized)

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 gives a negative answer.

Specifically, 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.

Key Results

With 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.
The gradient norm and the error in energy norm satisfy two-sided geometric estimates at the same rates; the objective gap satisfies a squared-rate estimate.
All three quantities are bounded below by geometric sequences, which rules out superlinear convergence.
The construction is nontrivial and is based on a computer-assisted proof of a non-resonant attracting seven-cycle in the four-dimensional projected BB dynamics.

Significance

This resolves a fundamental theoretical question about one of the most widely used quasi-Newton stepsizes, showing that superlinear convergence of BB on strictly convex quadratics is not generic: there exists an open set of problem instances where it provably fails.