Data to 7 Oct 2026

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

arXiv 2004.12019 ↗First posted 25 Apr 2020stat.ML cs.LG math.STcited by 81

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 19; 2022: 17; 2023: 21; 2024: 16; 2025: 6; 2026: 2.

81 papers.

Sort:

By area:

2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 90
2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
2021A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learningcited by 54
2021Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensionscited by 52
2021Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixturescited by 48
2022Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Datacited by 46
2021Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolationcited by 41
2022Towards A Proactive ML Approach for Detecting Backdoor Poison Samplescited by 40
2022The Implicit Bias of Benign Overfittingcited by 38
2022Characterizing Datapoints via Second-Split Forgettingcited by 37
2023Benign Overfitting for Two-layer ReLU Convolutional Neural Networkscited by 34

38 more

2023Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Datacited by 32
2024Implicit Bias and Fast Convergence Rates for Self-attentioncited by 31
2021Towards an Understanding of Benign Overfitting in Neural Networkscited by 29
2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
2023Why Does Sharpness-Aware Minimization Generalize Better Than SGD?cited by 27
2023Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimensioncited by 26
2022The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspectivecited by 24
2023The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networkscited by 23
2021Interpolating Classifiers Make Few Mistakescited by 22
2021Is Importance Weighting Incompatible with Interpolating Classifiers?cited by 19
2021The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networkscited by 18
2023From Tempered to Benign Overfitting in ReLU Neural Networkscited by 16
2024Provable Weak-to-Strong Generalization via Benign Overfittingcited by 16
2021Harmless interpolation in regression and classification with structured featurescited by 14
2024Trained Transformer Classifiers Generalize and Exhibit Benign Overfitting In-Contextcited by 14
2021On the interplay between data structure and loss function in classification problemscited by 12
2022On Feature Learning in Neural Networks with Global Convergence Guaranteescited by 12
2021Benign Overfitting in Adversarially Robust Linear Classificationcited by 11
2023Noisy Interpolation Learning with Shallow Univariate ReLU Networkscited by 11
2022Multiple Descent in the Multiple Random Feature Modelcited by 10
2023Benign Overfitting in Deep Neural Networks under Lazy Trainingcited by 10
2023Benign Overfitting in Two-Layer ReLU Convolutional Neural Networks for XOR Datacited by 10
2024Deep Learning Through A Telescoping Lens: A Simple Model Provides Empirical Insights On Grokking, Gradient Boosting & Beyondcited by 9
2025Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regressioncited by 9
2021Support vector machines and linear regression coincide with very high-dimensional featurescited by 8
2022Generalization for multiclass classification with overparameterized linear modelscited by 8
2022Deep Linear Networks can Benignly Overfit when Shallow Ones Docited by 8
2023Sketched Ridgeless Linear Regression: The Role of Downsamplingcited by 7
2023Per-Example Gradient Regularization Improves Learning Signals from Noisy Datacited by 7
2023Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign?cited by 7
2023Regularized Linear Regression for Binary Classificationcited by 7
2024The Surprising Harmfulness of Benign Overfitting for Adversarial Robustnesscited by 7
2024On the Benefits of Over-parameterization for Out-of-Distribution Generalizationcited by 7
2024Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionalitycited by 7
2022Benign Overfitting in Classification: Provably Counter Label Noise with Larger Modelscited by 5
2023Interpolation Learning With Minimum Description Lengthcited by 5
2024Benign overfitting in leaky ReLU networks with moderate input dimensioncited by 5
2025When and How Unlabeled Data Provably Improve In-Context Learningcited by 5

50 most cited of 81 All 81 (JSON)