# Bias-Optimal Bounds for SGD: A Computer-Aided Lyapunov Analysis

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 50 references that are in the map.
- First posted on arXiv 23 May 2025.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation](https://mlsanity.com/paper/2006.10311/) (2020)
- [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018)
- [Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition](https://mlsanity.com/paper/1308.6370/) (2013)
- [Clarabel: An interior-point solver for conic programs with quadratic objectives](https://mlsanity.com/paper/2405.12762/) (2024)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2312.08531/) (2023)
- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketching](https://mlsanity.com/paper/1805.02632/) (2018)
- [Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize](https://mlsanity.com/paper/2110.15412/) (2021)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions](https://mlsanity.com/paper/1902.00947/) (2019)
- [On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions](https://mlsanity.com/paper/1606.09365/) (2016)
- [Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry](https://mlsanity.com/paper/1703.09477/) (2017)
- [Automated tight Lyapunov analysis for first-order methods](https://mlsanity.com/paper/2302.06713/) (2023)
- [Revisiting Stochastic Proximal Point Methods: Generalized Smoothness and Similarity](https://mlsanity.com/paper/2502.03401/) (2025)
- [Exact worst-case convergence rates of the proximal gradient method for composite convex minimization](https://mlsanity.com/paper/1705.04398/) (2017)
- [A Unified Theory of Stochastic Proximal Point Methods without Smoothness](https://mlsanity.com/paper/2405.15941/) (2024)
- [Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functions](https://mlsanity.com/paper/2406.17506/) (2024)
- [Variance reduction techniques for stochastic proximal point algorithms](https://mlsanity.com/paper/2308.09310/) (2023)
- [Defining Lyapunov functions as the solution of a performance estimation saddle point problem](https://mlsanity.com/paper/2411.12317/) (2024)

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

- [Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime](https://mlsanity.com/paper/2507.11274/) (2025)
- [Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption](https://mlsanity.com/paper/2609.06580/) (2026)

## Abstract (arXiv)

The non-asymptotic analysis of Stochastic Gradient Descent (SGD) typically yields bounds that decompose into a bias term and a variance term. In this work, we focus on the bias component and study the extent to which SGD can match the optimal convergence behavior of deterministic gradient descent. Assuming only (strong) convexity and smoothness of the objective, we derive new bounds that are bias-optimal, in the sense that the bias term coincides with the worst-case rate of gradient descent. Our results hold for the full range of constant step-sizes γ L ∈ (0,2), including critical and large step-size regimes that were previously unexplored without additional variance assumptions. The bounds are obtained through the construction of a simple Lyapunov energy whose monotonicity yields sharp convergence guarantees. To design the parameters of this energy, we employ the Performance Estimation Problem framework, which we also use to provide numerical evidence for the optimality of the associated variance terms.