# Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime

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

## Key facts

- Cited by 81 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2020.

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

- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning](https://mlsanity.com/paper/2109.02355/) (2021)
- [Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions](https://mlsanity.com/paper/2106.03791/) (2021)
- [Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures](https://mlsanity.com/paper/2104.13628/) (2021)
- [Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data](https://mlsanity.com/paper/2210.07082/) (2022)
- [Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation](https://mlsanity.com/paper/2106.10865/) (2021)
- [Towards A Proactive ML Approach for Detecting Backdoor Poison Samples](https://mlsanity.com/paper/2205.13616/) (2022)
- [The Implicit Bias of Benign Overfitting](https://mlsanity.com/paper/2201.11489/) (2022)
- [Characterizing Datapoints via Second-Split Forgetting](https://mlsanity.com/paper/2210.15031/) (2022)
- [Benign Overfitting for Two-layer ReLU Convolutional Neural Networks](https://mlsanity.com/paper/2303.04145/) (2023)
- [Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Data](https://mlsanity.com/paper/2310.02541/) (2023)
- [Implicit Bias and Fast Convergence Rates for Self-attention](https://mlsanity.com/paper/2402.05738/) (2024)
- [Towards an Understanding of Benign Overfitting in Neural Networks](https://mlsanity.com/paper/2106.03212/) (2021)
- [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023)
- [Why Does Sharpness-Aware Minimization Generalize Better Than SGD?](https://mlsanity.com/paper/2310.07269/) (2023)
- [Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension](https://mlsanity.com/paper/2305.14077/) (2023)
- [The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspective](https://mlsanity.com/paper/2210.05021/) (2022)
- [The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks](https://mlsanity.com/paper/2303.01456/) (2023)
- [Interpolating Classifiers Make Few Mistakes](https://mlsanity.com/paper/2101.11815/) (2021)
- [Is Importance Weighting Incompatible with Interpolating Classifiers?](https://mlsanity.com/paper/2112.12986/) (2021)
- [The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks](https://mlsanity.com/paper/2108.11489/) (2021)
- [From Tempered to Benign Overfitting in ReLU Neural Networks](https://mlsanity.com/paper/2305.15141/) (2023)
- [Provable Weak-to-Strong Generalization via Benign Overfitting](https://mlsanity.com/paper/2410.04638/) (2024)
- [Trained Transformer Classifiers Generalize and Exhibit Benign Overfitting In-Context](https://mlsanity.com/paper/2410.01774/) (2024)
- [Harmless interpolation in regression and classification with structured features](https://mlsanity.com/paper/2111.05198/) (2021)
- [On the interplay between data structure and loss function in classification problems](https://mlsanity.com/paper/2103.05524/) (2021)
- [On Feature Learning in Neural Networks with Global Convergence Guarantees](https://mlsanity.com/paper/2204.10782/) (2022)
- [Benign Overfitting in Adversarially Robust Linear Classification](https://mlsanity.com/paper/2112.15250/) (2021)

## Abstract (arXiv)

We prove bounds on the population risk of the maximum margin algorithm for two-class linear classification. For linearly separable training data, the maximum margin algorithm has been shown in previous work to be equivalent to a limit of training with logistic loss using gradient descent, as the training error is driven to zero. We analyze this algorithm applied to random data including misclassification noise. Our assumptions on the clean data include the case in which the class-conditional distributions are standard normal distributions. The misclassification noise may be chosen by an adversary, subject to a limit on the fraction of corrupted labels. Our bounds show that, with sufficient over-parameterization, the maximum margin algorithm trained on noisy data can achieve nearly optimal population risk.