# Barzilai-Borwein Step Size for Stochastic Gradient Descent

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2016.

## Built on by (most cited first, 30 of 33)

- [Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient](https://mlsanity.com/paper/2301.04431/) (2023)
- [AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods](https://mlsanity.com/paper/2102.09700/) (2021)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models](https://mlsanity.com/paper/2306.12747/) (2023)
- [SVRG Meets AdaGrad: Painless Variance Reduction](https://mlsanity.com/paper/2102.09645/) (2021)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [Rethinking and Reweighting the Univariate Losses for Multi-Label Ranking: Consistency and Generalization](https://mlsanity.com/paper/2105.05026/) (2021)
- [Adaptive Learning Rates for Faster Stochastic Gradient Methods](https://mlsanity.com/paper/2208.05287/) (2022)
- [AdaLoss: A computationally-efficient and provably convergent adaptive gradient method](https://mlsanity.com/paper/2109.08282/) (2021)
- [Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction](https://mlsanity.com/paper/2201.12302/) (2022)
- [Towards Understanding Generalization of Macro-AUC in Multi-label Learning](https://mlsanity.com/paper/2305.05248/) (2023)
- [Second-order step-size tuning of SGD for non-convex optimization](https://mlsanity.com/paper/2103.03570/) (2021)
- [A Stochastic Bundle Method for Interpolating Networks](https://mlsanity.com/paper/2201.12678/) (2022)
- [On a Faster R-Linear Convergence Rate of the Barzilai-Borwein Method](https://mlsanity.com/paper/2101.00205/) (2021)
- [Stochastic Steffensen method](https://mlsanity.com/paper/2211.15310/) (2022)
- [Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients](https://mlsanity.com/paper/2512.02342/) (2025)
- [On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization](https://mlsanity.com/paper/2101.00236/) (2021)
- [Optimizer Dynamics at the Edge of Stability with Differential Privacy](https://mlsanity.com/paper/2512.19019/) (2025)
- [Adaptivity via a Parallel Architecture for Stochastic Gradient Methods](https://mlsanity.com/paper/2607.28902/) (2026)
- [Meta-Regularization: An Approach to Adaptive Choice of the Learning Rate in Gradient Descent](https://mlsanity.com/paper/2104.05447/) (2021)
- [Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization](https://mlsanity.com/paper/2109.15292/) (2021)
- [An Adaptive Incremental Gradient Method With Support for Non-Euclidean Norms](https://mlsanity.com/paper/2205.02273/) (2022)
- [A Stochastic Variance Reduced Gradient using Barzilai-Borwein Techniques as Second Order Information](https://mlsanity.com/paper/2208.11075/) (2022)
- [Layer-wise Adaptive Step-Sizes for Stochastic First-Order Methods for Deep Learning](https://mlsanity.com/paper/2305.13664/) (2023)
- [A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques](https://mlsanity.com/paper/2403.11163/) (2024)
- [Fisher Information based Stochastic Gradient Ascent for Online Learning of Dirichlet Process Mixture and Theory](https://mlsanity.com/paper/2412.08951/) (2024)
- [Normalized Iterative Hard Thresholding for Tensor Recovery](https://mlsanity.com/paper/2507.04228/) (2025)
- [Stochastic Adaptive Gradient Descent Without Descent](https://mlsanity.com/paper/2509.14969/) (2025)
- [Using Multi-modal Large Language Model to Boost Fireworks Algorithm's Ability in Settling Challenging Optimization Tasks](https://mlsanity.com/paper/2511.03137/) (2025)
- [Parameter Estimation in Stochastic Differential Equations via Wiener Chaos Expansion and Stochastic Gradient Descent](https://mlsanity.com/paper/2603.27019/) (2026)

## Abstract (arXiv)

One of the major issues in stochastic gradient descent (SGD) methods is how to choose an appropriate step size while running the algorithm. Since the traditional line search technique does not apply for stochastic optimization algorithms, the common practice in SGD is either to use a diminishing step size, or to tune a fixed step size by hand, which can be time consuming in practice. In this paper, we propose to use the Barzilai-Borwein (BB) method to automatically compute step sizes for SGD and its variant: stochastic variance reduced gradient (SVRG) method, which leads to two algorithms: SGD-BB and SVRG-BB. We prove that SVRG-BB converges linearly for strongly convex objective functions. As a by-product, we prove the linear convergence result of SVRG with Option I proposed in [10], whose convergence result is missing in the literature. Numerical experiments on standard data sets show that the performance of SGD-BB and SVRG-BB is comparable to and sometimes even better than SGD and SVRG with best-tuned step sizes, and is superior to some advanced SGD variants.