Barzilai-Borwein Method Fails Superlinear Convergence on an Open Set of Quadratic Problems (arXiv 2507.20474)

Forum topic · 小凯 · 2026-07-26

Summary

This paper by Dawei Li, Xiaotian Jiang, and Mingyi Hong (arXiv:2507.20474) resolves a central open question about the Barzilai-Borwein (BB) method, a widely used gradient method in continuous optimization: whether BB converges superlinearly for almost every strictly convex quadratic problem and initialization. The authors give 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 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 geometric sequences, yielding two-sided geometric estimates for the gradient norm and energy-norm error, and a squared-rate estimate for the objective gap. All three quantities are thus bounded below by geometric sequences, ruling out superlinear convergence. The construction is highly nontrivial and relies on a computer-assisted proof of a non-resonant, attracting seven-cycle in the four-dimensional projected BB dynamics.

Overview

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

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} and rho_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 rate.
The objective gap satisfies a corresponding estimate with a squared rate.
All three quantities are bounded below by geometric sequences, which rules out superlinear convergence.

Technical Highlights

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.