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

Forum topic · 小凯 · 2026-07-27

Summary

This paper investigates the convergence dynamics of the Barzilai-Borwein (BB) method, a widely used algorithm in continuous optimization whose theoretical behavior remains poorly understood. A central open question is whether BB converges superlinearly for almost every strictly convex quadratic problem and initialization. The authors answer this question negatively: for every finite dimension n>=4, they construct a nonempty, open, positive-Lebesgue-measure family of strictly convex quadratic problems and initial points for which the long BB method (BB1) converges but cannot converge root-superlinearly. Using explicit constants rho_min=10^-6 and rho_max=0.61, they show that every spectral component of the gradient is bounded above and below by geometric sequences. Consequently, the gradient norm and the energy-norm error satisfy two-sided geometric estimates with identical rates, while the objective gap follows a squared rate. All three quantities are lower-bounded by geometric sequences, ruling out superlinear convergence. The construction relies on a nontrivial computer-assisted proof of a non-resonant, attracting 7-cycle in the projected 4D BB dynamics. (arXiv:2507.21740)

Paper Overview

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

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.

The authors provide a negative answer to this question. Specifically, for every finite dimension n>=4, they 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.

Key Findings

Explicit constants: With 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.
Two-sided geometric estimates: The gradient norm and the energy-norm error satisfy bilateral geometric estimates at the same rate.
Objective gap: Satisfies a corresponding estimate at the squared rate.
Lower bounds exclude superlinear convergence: All three quantities (gradient norm, energy-norm error, objective gap) are lower-bounded by geometric sequences, ruling out superlinear convergence.
Constructive method: The construction is highly nontrivial and rests on a computer-assisted proof of a non-resonant, attracting 7-cycle in the projected 4D BB dynamics.

Source 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>=4, 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.

--- *Auto-collected 2026-07-27*

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

Summary

Paper Overview

Summary

Key Findings

Source Abstract

Tags