# Convergence of Gradient Descent on Separable Data

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

## Key facts

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

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

- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [The Low-Rank Simplicity Bias in Deep Networks](https://mlsanity.com/paper/2103.10427/) (2021)
- [Noise Is Not the Main Factor Behind the Gap Between SGD and Adam on Transformers, but Sign Descent Might Be](https://mlsanity.com/paper/2304.13960/) (2023)
- [An Unconstrained Layer-Peeled Perspective on Neural Collapse](https://mlsanity.com/paper/2110.02796/) (2021)
- [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)
- [Imbalance Trouble: Revisiting Neural-Collapse Geometry](https://mlsanity.com/paper/2208.05512/) (2022)
- [Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokking](https://mlsanity.com/paper/2311.18817/) (2023)
- [Heavy-Tailed Class Imbalance and Why Adam Outperforms Gradient Descent on Language Models](https://mlsanity.com/paper/2402.19449/) (2024)
- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [On Large-Cohort Training for Federated Learning](https://mlsanity.com/paper/2106.07820/) (2021)
- [Transformers as Support Vector Machines](https://mlsanity.com/paper/2308.16898/) (2023)
- [Dissecting Supervised Contrastive Learning](https://mlsanity.com/paper/2102.08817/) (2021)
- [Max-Margin Token Selection in Attention Mechanism](https://mlsanity.com/paper/2306.13596/) (2023)
- [Implicit Bias of AdamW: ℓ_∞ Norm Constrained Optimization](https://mlsanity.com/paper/2404.04454/) (2024)
- [Implicit Regularization Towards Rank Minimization in ReLU Networks](https://mlsanity.com/paper/2201.12760/) (2022)
- [Mechanistic Mode Connectivity](https://mlsanity.com/paper/2211.08422/) (2022)
- [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021)
- [Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability](https://mlsanity.com/paper/2305.11788/) (2023)
- [Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping](https://mlsanity.com/paper/2412.19529/) (2024)
- [Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data](https://mlsanity.com/paper/2502.04664/) (2025)
- [Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descent](https://mlsanity.com/paper/2207.04036/) (2022)
- [On Margin Maximization in Linear and ReLU Networks](https://mlsanity.com/paper/2110.02732/) (2021)
- [Fast Margin Maximization via Dual Acceleration](https://mlsanity.com/paper/2107.00595/) (2021)
- [Implicit Bias and Fast Convergence Rates for Self-attention](https://mlsanity.com/paper/2402.05738/) (2024)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [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)
- [Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networks](https://mlsanity.com/paper/2201.11729/) (2022)
- [On the Implicit Bias of Adam](https://mlsanity.com/paper/2309.00079/) (2023)

## Abstract (arXiv)

We provide a detailed study on the implicit bias of gradient descent when optimizing loss functions with strictly monotone tails, such as the logistic loss, over separable datasets. We look at two basic questions: (a) what are the conditions on the tail of the loss function under which gradient descent converges in the direction of the L2 maximum-margin separator? (b) how does the rate of margin convergence depend on the tail of the loss function and the choice of the step size? We show that for a large family of super-polynomial tailed losses, gradient descent iterates on linear networks of any depth converge in the direction of L2 maximum-margin solution, while this does not hold for losses with heavier tails. Within this family, for simple linear models we show that the optimal rates with fixed step size is indeed obtained for the commonly used exponentially tailed losses such as logistic loss. However, with a fixed step size the optimal convergence rate is extremely slow as 1/log(t), as also proved in Soudry et al. (2018). For linear models with exponential loss, we further prove that the convergence rate could be improved to log (t) /√t by using aggressive step sizes that compensates for the rapidly vanishing gradients. Numerical results suggest this method might be useful for deep networks.