# Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 17 references that are in the map.
- First posted on arXiv 27 Feb 2022.

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

- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [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)
- [Stability and Convergence Trade-off of Iterative Optimization Algorithms](https://mlsanity.com/paper/1804.01619/) (2018)
- [Gradient Methods Never Overfit On Separable Data](https://mlsanity.com/paper/2007.00028/) (2020)
- [Algorithmic Instabilities of Accelerated Gradient Descent](https://mlsanity.com/paper/2102.02167/) (2021)
- [Characterizing the implicit bias via a primal-dual analysis](https://mlsanity.com/paper/1906.04540/) (2019)

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

- [On the Optimization and Generalization of Multi-head Attention](https://mlsanity.com/paper/2310.12680/) (2023)
- [Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks](https://mlsanity.com/paper/2209.09298/) (2022)
- [Generalization and Stability of Interpolating Neural Networks with Minimal Width](https://mlsanity.com/paper/2302.09235/) (2023)
- [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)
- [On Generalization of Decentralized Learning with Separable Data](https://mlsanity.com/paper/2209.07116/) (2022)
- [Tight Risk Bounds for Gradient Descent on Separable Data](https://mlsanity.com/paper/2303.01135/) (2023)
- [Resource Allocation for Stable LLM Training in Mobile Edge Computing](https://mlsanity.com/paper/2409.20247/) (2024)
- [Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/2303.10758/) (2023)
- [Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally](https://mlsanity.com/paper/2305.02247/) (2023)
- [Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalization](https://mlsanity.com/paper/2310.01139/) (2023)
- [Flat Minima and Generalization: Insights from Stochastic Convex Optimization](https://mlsanity.com/paper/2511.03548/) (2025)
- [Fast Convergence in Learning Two-Layer Neural Networks with Separable Data](https://mlsanity.com/paper/2305.13471/) (2023)
- [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)
- [Differentially Private Stochastic Gradient Descent with Low-Noise](https://mlsanity.com/paper/2209.04188/) (2022)
- [A Stability Analysis of Fine-Tuning a Pre-Trained Model](https://mlsanity.com/paper/2301.09820/) (2023)
- [Convex SGD: Generalization Without Early Stopping](https://mlsanity.com/paper/2401.04067/) (2024)
- [Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2601.22409/) (2026)
- [Sufficient Conditions for Stability of Minimum-Norm Interpolating Deep ReLU Networks](https://mlsanity.com/paper/2602.13910/) (2026)
- [Stochastic Gradient Descent with Momentum is Algorithmically Stable](https://mlsanity.com/paper/2605.28517/) (2026)
- [Bootstrap SGD: Algorithmic Stability and Robustness](https://mlsanity.com/paper/2409.01074/) (2024)
- [Generalization and Optimization of SGD with Lookahead](https://mlsanity.com/paper/2509.15776/) (2025)
- [Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationarity](https://mlsanity.com/paper/2601.19730/) (2026)
- [Learning Theory of the SVRG: Generalization and Convergence Analysis](https://mlsanity.com/paper/2605.28513/) (2026)
- [Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity](https://mlsanity.com/paper/2606.11431/) (2026)
- [Dangerous Liaisons of Convex Learning and Non-Affine Aggregation](https://mlsanity.com/paper/2606.28123/) (2026)
- [Non-asymptotic implicit bias of logistic regression at early-stage gradient descent dynamics](https://mlsanity.com/paper/2608.04382/) (2026)

## Abstract (arXiv)

An influential line of recent work has focused on the generalization properties of unregularized gradient-based learning procedures applied to separable linear classification with exponentially-tailed loss functions. The ability of such methods to generalize well has been attributed to the their implicit bias towards large margin predictors, both asymptotically as well as in finite time. We give an additional unified explanation for this generalization and relate it to two simple properties of the optimization objective, that we refer to as realizability and self-boundedness. We introduce a general setting of unconstrained stochastic convex optimization with these properties, and analyze generalization of gradient methods through the lens of algorithmic stability. In this broader setting, we obtain sharp stability bounds for gradient descent and stochastic gradient descent which apply even for a very large number of gradient steps, and use them to derive general generalization bounds for these algorithms. Finally, as direct applications of the general bounds, we return to the setting of linear classification with separable data and establish several novel test loss and test accuracy bounds for gradient descent and stochastic gradient descent for a variety of loss functions with different tail decay rates. In some of these cases, our bounds significantly improve upon the existing generalization error bounds in the literature.