# Gradient Methods Never Overfit On Separable Data

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2020.

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

- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training](https://mlsanity.com/paper/2101.12699/) (2021)
- [On the Implicit Bias in Deep-Learning Algorithms](https://mlsanity.com/paper/2208.12591/) (2022)
- [Implicit Regularization Towards Rank Minimization in ReLU Networks](https://mlsanity.com/paper/2201.12760/) (2022)
- [On the Optimization and Generalization of Multi-head Attention](https://mlsanity.com/paper/2310.12680/) (2023)
- [Early-stopped neural networks are consistent](https://mlsanity.com/paper/2106.05932/) (2021)
- [On Margin Maximization in Linear and ReLU Networks](https://mlsanity.com/paper/2110.02732/) (2021)
- [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)
- [Generalization and Stability of Interpolating Neural Networks with Minimal Width](https://mlsanity.com/paper/2302.09235/) (2023)
- [Stochastic linear optimization never overfits with quadratically-bounded losses on general data](https://mlsanity.com/paper/2202.06915/) (2022)
- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (2021)
- [Guiding Neural Collapse: Optimising Towards the Nearest Simplex Equiangular Tight Frame](https://mlsanity.com/paper/2411.01248/) (2024)
- [Actor-critic is implicitly biased towards high entropy optimal policies](https://mlsanity.com/paper/2110.11280/) (2021)
- [The Implicit Bias of Gradient Descent on Separable Multiclass Data](https://mlsanity.com/paper/2411.01350/) (2024)
- [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)
- [On Generalization of Decentralized Learning with Separable Data](https://mlsanity.com/paper/2209.07116/) (2022)
- [Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization](https://mlsanity.com/paper/2202.13328/) (2022)
- [Tight Risk Bounds for Gradient Descent on Separable Data](https://mlsanity.com/paper/2303.01135/) (2023)
- [Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets](https://mlsanity.com/paper/2111.14039/) (2021)
- [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)
- [Post-Training with Policy Gradients: Optimality and the Base Model Barrier](https://mlsanity.com/paper/2603.06957/) (2026)
- [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)
- [Directional Convergence Analysis under Spherically Symmetric Distribution](https://mlsanity.com/paper/2105.03879/) (2021)
- [Accelerated Neural Network Training with Rooted Logistic Objectives](https://mlsanity.com/paper/2310.03890/) (2023)
- [Non-asymptotic implicit bias of logistic regression at early-stage gradient descent dynamics](https://mlsanity.com/paper/2608.04382/) (2026)

## Abstract (arXiv)

A line of recent works established that when training linear predictors over separable data, using gradient methods and exponentially-tailed losses, the predictors asymptotically converge in direction to the max-margin predictor. As a consequence, the predictors asymptotically do not overfit. However, this does not address the question of whether overfitting might occur non-asymptotically, after some bounded number of iterations. In this paper, we formally show that standard gradient methods (in particular, gradient flow, gradient descent and stochastic gradient descent) never overfit on separable data: If we run these methods for T iterations on a dataset of size m, both the empirical risk and the generalization error decrease at an essentially optimal rate of tildeO(1/γ2 T) up till T≈ m, at which point the generalization error remains fixed at an essentially optimal level of tildeO(1/γ2 m) regardless of how large T is. Along the way, we present non-asymptotic bounds on the number of margin violations over the dataset, and prove their tightness.