mlsanityData to 14 Oct 2026

Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures

arXiv 2104.13628 ↗First posted 28 Apr 2021cs.LG math.ST stat.MLcited by 49

Not on the map. Why?

Abstract (arXiv)

Modern machine learning systems such as deep neural networks are often highly over-parameterized so that they can fit the noisy training data exactly, yet they can still achieve small test errors in practice. In this paper, we study this "benign overfitting" phenomenon of the maximum margin classifier for linear classification problems. Specifically, we consider data generated from sub-Gaussian mixtures, and provide a tight risk bound for the maximum margin linear classifier in the over-parameterized setting. Our results precisely characterize the condition under which benign overfitting can occur in linear classification problems, and improve on previous work. They also have direct implications for over-parameterized logistic regression.

Key facts. Cited by 49 papers in the map (data through 14 Oct 2026). Builds on 20 of its 38 references that are in the map. First posted on arXiv 28 Apr 2021.

Builds on

20 of 38 references.

References · 20

  1. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  2. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  3. 2019Benign Overfitting in Linear Regressioncited by 549
  4. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 513
  5. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 413
  6. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
  7. 2017Implicit Regularization in Matrix Factorizationcited by 322
  8. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 320
  9. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  10. 2019Two models of double descent for weak featurescited by 195
  11. 2018To understand deep learning we need to understand kernel learningcited by 187
  12. 2020Benign overfitting in ridge regressioncited by 153
8 more
  1. 2019Harmless interpolation of noisy data in regressioncited by 121
  2. 2020On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regressioncited by 98
  3. 2020Classification vs regression in overparameterized regimes: Does the loss function matter?cited by 97
  4. 2020The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Trainingcited by 84
  5. 2020Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regimecited by 81
  6. 2020A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descentcited by 70
  7. 2018Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Ratecited by 64
  8. 2020On the proliferation of support vectors in high dimensionscited by 32

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 12; 2022: 13; 2023: 11; 2024: 7; 2025: 4; 2026: 2.

49 papers.

Sort:

  1. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 91
  2. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  3. 2021A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learningcited by 57
  4. 2021Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensionscited by 54
  5. 2021Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolationcited by 42
  6. 2022The Implicit Bias of Benign Overfittingcited by 38
  7. 2023Benign Overfitting for Two-layer ReLU Convolutional Neural Networkscited by 34
  8. 2021Towards an Understanding of Benign Overfitting in Neural Networkscited by 30
  9. 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
  10. 2022The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspectivecited by 24
  11. 2021Is Importance Weighting Incompatible with Interpolating Classifiers?cited by 19
  12. 2023From Tempered to Benign Overfitting in ReLU Neural Networkscited by 16
37 more
  1. 2021Harmless interpolation in regression and classification with structured featurescited by 14
  2. 2024Implicit Optimization Bias of Next-Token Prediction in Linear Modelscited by 14
  3. 2021Benign Overfitting in Adversarially Robust Linear Classificationcited by 11
  4. 2023Noisy Interpolation Learning with Shallow Univariate ReLU Networkscited by 11
  5. 2022Multiple Descent in the Multiple Random Feature Modelcited by 10
  6. 2023Benign Overfitting in Two-Layer ReLU Convolutional Neural Networks for XOR Datacited by 10
  7. 2025Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regressioncited by 9
  8. 2021Support vector machines and linear regression coincide with very high-dimensional featurescited by 8
  9. 2022Deep Linear Networks can Benignly Overfit when Shallow Ones Docited by 8
  10. 2023Per-Example Gradient Regularization Improves Learning Signals from Noisy Datacited by 7
  11. 2023Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign?cited by 7
  12. 2024Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionalitycited by 7
  13. 2021Minimax Supervised Clustering in the Anisotropic Gaussian Mixture Model: A new take on Robust Interpolationcited by 6
  14. 2022Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergencecited by 6
  15. 2022Malign Overfitting: Interpolation Can Provably Preclude Invariancecited by 6
  16. 2024Benign overfitting in leaky ReLU networks with moderate input dimensioncited by 6
  17. 2025When and How Unlabeled Data Provably Improve In-Context Learningcited by 6
  18. 2022Benign Overfitting in Classification: Provably Counter Label Noise with Larger Modelscited by 5
  19. 2023On the Clean Generalization and Robust Overfitting in Adversarial Training from Two Theoretical Views: Representation Complexity and Training Dynamicscited by 5
  20. 2022On how to avoid exacerbating spurious correlations when models are overparameterizedcited by 4
  21. 2023General Loss Functions Lead to (Approximate) Interpolation in High Dimensionscited by 4
  22. 2023New Equivalences Between Interpolation and SVMs: Kernels and Structured Featurescited by 3
  23. 2024Sharp analysis of out-of-distribution error for "importance-weighted" estimators in the overparameterized regimecited by 3
  24. 2024Balanced Data, Imbalanced Spectra: Unveiling Class Disparities with Spectral Imbalancecited by 2
  25. 2021Learning Curves for SGD on Structured Featurescited by 1
  26. 2021Classification and Adversarial examples in an Overparameterized Linear Model: A Signal Processing Perspectivecited by 1
  27. 2022Benign-Overfitting in Conditional Average Treatment Effect Prediction with Linear Regressioncited by 1
  28. 2022Benefit of Interpolation in Nearest Neighbor Algorithmscited by 1
  29. 2023PASS: Peer-Agreement based Sample Selection for training with Noisy Labelscited by 1
  30. 2024Can overfitted deep neural networks in adversarial training generalize? -- An approximation viewpointcited by 1
  31. 2026Hard labels sampled from sparse targets mislead rotation invariant algorithmscited by 1
  32. 2026Benign Overfitting in Adversarial Training for Vision Transformerscited by 1
  33. 2021Explaining generalization in deep learning: progress and fundamental limitscited by 0
  34. 2022Interpolating Discriminant Functions in High-Dimensional Gaussian Latent Mixturescited by 0
  35. 2024Benign Overfitting under Learning Rate Conditions for α Sub-exponential Inputcited by 0
  36. 2025Directional Convergence, Benign Overfitting of Gradient Descent in leaky ReLU two-layer Neural Networkscited by 0
  37. 2025Benign Overfitting in Linear Classifiers with a Bias Termcited by 0