# On a Faster R-Linear Convergence Rate of the Barzilai-Borwein Method

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 20 references that are in the map.
- First posted on arXiv 1 Jan 2021.

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

- [Barzilai-Borwein Step Size for Stochastic Gradient Descent](https://mlsanity.com/paper/1605.04131/) (2016)
- [Worst-case Complexity of Cyclic Coordinate Descent: O(n2) Gap with Randomized Version](https://mlsanity.com/paper/1604.07130/) (2016)
- [A family of spectral gradient methods for optimization](https://mlsanity.com/paper/1812.02974/) (2018)

## Built on by (most cited first, 2 of 2)

- [Safeguarding adaptive methods: global convergence of Barzilai-Borwein and other stepsize choices](https://mlsanity.com/paper/2404.09617/) (2024)
- [Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension n≥ 4](https://mlsanity.com/paper/2607.21579/) (2026)

## Abstract (arXiv)

The Barzilai-Borwein (BB) method has demonstrated great empirical success in nonlinear optimization. However, the convergence speed of BB method is not well understood, as the known convergence rate of BB method for quadratic problems is much worse than the steepest descent (SD) method. Therefore, there is a large discrepancy between theory and practice. To shrink this gap, we prove that the BB method converges R-linearly at a rate of 1-1/kappa, where kappa is the condition number, for strongly convex quadratic problems. In addition, an example with the theoretical rate of convergence is constructed, indicating the tightness of our bound.