# Tight Risk Bounds for Gradient Descent on Separable Data

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 17 references that are in the map.
- First posted on arXiv 2 Mar 2023.

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

- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Convergence of Gradient Descent on Separable Data](https://mlsanity.com/paper/1803.01905/) (2018)
- [Risk and parameter convergence of logistic regression](https://mlsanity.com/paper/1803.07300/) (2018)
- [Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate](https://mlsanity.com/paper/1806.01796/) (2018)
- [Gradient descent follows the regularization path for general losses](https://mlsanity.com/paper/2006.11226/) (2020)
- [Gradient Methods Never Overfit On Separable Data](https://mlsanity.com/paper/2007.00028/) (2020)
- [Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond](https://mlsanity.com/paper/2202.13441/) (2022)
- [Stochastic linear optimization never overfits with quadratically-bounded losses on general data](https://mlsanity.com/paper/2202.06915/) (2022)
- [Characterizing the implicit bias via a primal-dual analysis](https://mlsanity.com/paper/1906.04540/) (2019)

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

- [The Implicit Bias of Gradient Descent on Separable Multiclass Data](https://mlsanity.com/paper/2411.01350/) (2024)
- [Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm](https://mlsanity.com/paper/2306.02939/) (2023)
- [Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression](https://mlsanity.com/paper/2502.13283/) (2025)
- [Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression](https://mlsanity.com/paper/2506.02336/) (2025)
- [Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification](https://mlsanity.com/paper/2510.02779/) (2025)
- [Minimax Excess Risk of First-Order Methods for Statistical Learning with Data-Dependent Oracles](https://mlsanity.com/paper/2307.04679/) (2023)
- [Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification](https://mlsanity.com/paper/2505.22359/) (2025)

## Abstract (arXiv)

We study the generalization properties of unregularized gradient methods applied to separable linear classification -- a setting that has received considerable attention since the pioneering work of Soudry et al. (2018). We establish tight upper and lower (population) risk bounds for gradient descent in this setting, for any smooth loss function, expressed in terms of its tail decay rate. Our bounds take the form Theta(rℓ,T2 / γ2 T + rℓ,T2 / γ2 n), where T is the number of gradient steps, n is size of the training set, γ is the data margin, and rℓ,T is a complexity term that depends on the (tail decay rate) of the loss function (and on T). Our upper bound matches the best known upper bounds due to Shamir (2021); Schliserman and Koren (2022), while extending their applicability to virtually any smooth loss function and relaxing technical assumptions they impose. Our risk lower bounds are the first in this context and establish the tightness of our upper bounds for any given tail decay rate and in all parameter regimes. The proof technique used to show these results is also markedly simpler compared to previous work, and is straightforward to extend to other gradient methods; we illustrate this by providing analogous results for Stochastic Gradient Descent.