# Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate

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

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2018.

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

- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [Robust Training under Label Noise by Over-parameterization](https://mlsanity.com/paper/2202.14026/) (2022)
- [On the Implicit Bias in Deep-Learning Algorithms](https://mlsanity.com/paper/2208.12591/) (2022)
- [Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias](https://mlsanity.com/paper/2110.13905/) (2021)
- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures](https://mlsanity.com/paper/2104.13628/) (2021)
- [Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability](https://mlsanity.com/paper/2305.11788/) (2023)
- [The Implicit Bias of Adam on Separable Data](https://mlsanity.com/paper/2406.10650/) (2024)
- [On Implicit Bias in Overparameterized Bilevel Optimization](https://mlsanity.com/paper/2212.14032/) (2022)
- [Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond](https://mlsanity.com/paper/2202.13441/) (2022)
- [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023)
- [On the Power of Differentiable Learning versus PAC and SQ Learning](https://mlsanity.com/paper/2108.04190/) (2021)
- [On the Implicit Bias of Adam](https://mlsanity.com/paper/2309.00079/) (2023)
- [The Asymmetric Maximum Margin Bias of Quasi-Homogeneous Neural Networks](https://mlsanity.com/paper/2210.03820/) (2022)
- [Does Momentum Change the Implicit Regularization on Separable Data?](https://mlsanity.com/paper/2110.03891/) (2021)
- [The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks](https://mlsanity.com/paper/2108.11489/) (2021)
- [Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization](https://mlsanity.com/paper/2406.08654/) (2024)
- [The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks](https://mlsanity.com/paper/2306.17499/) (2023)
- [Why adversarial training can hurt robust accuracy](https://mlsanity.com/paper/2203.02006/) (2022)
- [Implicit Optimization Bias of Next-Token Prediction in Linear Models](https://mlsanity.com/paper/2402.18551/) (2024)
- [Improving Generalization and Convergence by Enhancing Implicit Regularization](https://mlsanity.com/paper/2405.20763/) (2024)
- [Benign Overfitting in Adversarially Robust Linear Classification](https://mlsanity.com/paper/2112.15250/) (2021)
- [The Implicit Bias of Gradient Descent on Separable Multiclass Data](https://mlsanity.com/paper/2411.01350/) (2024)
- [Implicit Bias of Mirror Flow on Separable Data](https://mlsanity.com/paper/2406.12763/) (2024)
- [Deep Linear Networks can Benignly Overfit when Shallow Ones Do](https://mlsanity.com/paper/2209.09315/) (2022)
- [The Implicit Bias of Batch Normalization in Linear Models and Two-layer Linear Convolutional Neural Networks](https://mlsanity.com/paper/2306.11680/) (2023)
- [Tight Risk Bounds for Gradient Descent on Separable Data](https://mlsanity.com/paper/2303.01135/) (2023)
- [On the Implicit Bias of Linear Equivariant Steerable Networks](https://mlsanity.com/paper/2303.04198/) (2023)
- [Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergence](https://mlsanity.com/paper/2206.07892/) (2022)
- [How Memory in Optimization Algorithms Implicitly Modifies the Loss](https://mlsanity.com/paper/2502.02132/) (2025)

## Abstract (arXiv)

Stochastic Gradient Descent (SGD) is a central tool in machine learning. We prove that SGD converges to zero loss, even with a fixed (non-vanishing) learning rate - in the special case of homogeneous linear classifiers with smooth monotone loss functions, optimized on linearly separable data. Previous works assumed either a vanishing learning rate, iterate averaging, or loss assumptions that do not hold for monotone loss functions used for classification, such as the logistic loss. We prove our result on a fixed dataset, both for sampling with or without replacement. Furthermore, for logistic loss (and similar exponentially-tailed losses), we prove that with SGD the weight vector converges in direction to the L2 max margin vector as O(1/log(t)) for almost all separable datasets, and the loss converges as O(1/t) - similarly to gradient descent. Lastly, we examine the case of a fixed learning rate proportional to the minibatch size. We prove that in this case, the asymptotic convergence rate of SGD (with replacement) does not depend on the minibatch size in terms of epochs, if the support vectors span the data. These results may suggest an explanation to similar behaviors observed in deep networks, when trained with SGD.