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

arXiv: https://arxiv.org/abs/2607.21579 · HTML: https://mlsanity.com/paper/2607.21579/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 48 references that are in the map.
- First posted on arXiv 23 Jul 2026.

## Builds on (most cited first, 7 of 7)

- [Barzilai-Borwein Step Size for Stochastic Gradient Descent](https://mlsanity.com/paper/1605.04131/) (2016)
- [Stabilized Barzilai-Borwein method](https://mlsanity.com/paper/1907.06409/) (2019)
- [AdaBB: Adaptive Barzilai-Borwein Method for Convex Optimization](https://mlsanity.com/paper/2401.08024/) (2024)
- [New Results on the Polyak Stepsize: Tight Convergence Analysis and Universal Function Classes](https://mlsanity.com/paper/2512.06231/) (2025)
- [A family of spectral gradient methods for optimization](https://mlsanity.com/paper/1812.02974/) (2018)
- [On a Faster R-Linear Convergence Rate of the Barzilai-Borwein Method](https://mlsanity.com/paper/2101.00205/) (2021)
- [On the asymptotic convergence and acceleration of gradient methods](https://mlsanity.com/paper/1908.07111/) (2019)

## Abstract (arXiv)

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