# Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting and Regularization

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2020.

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

- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [Transformers as Support Vector Machines](https://mlsanity.com/paper/2308.16898/) (2023)
- [Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions](https://mlsanity.com/paper/2106.03791/) (2021)
- [Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation](https://mlsanity.com/paper/2106.10865/) (2021)
- [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)
- [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023)
- [Toward Understanding Generative Data Augmentation](https://mlsanity.com/paper/2305.17476/) (2023)
- [The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspective](https://mlsanity.com/paper/2210.05021/) (2022)
- [Information-Theoretic Characterization of the Generalization Error for Iterative Semi-Supervised Learning](https://mlsanity.com/paper/2110.00926/) (2021)
- [Noisy Interpolation Learning with Shallow Univariate ReLU Networks](https://mlsanity.com/paper/2307.15396/) (2023)
- [Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression](https://mlsanity.com/paper/2502.13283/) (2025)
- [Support vector machines and linear regression coincide with very high-dimensional features](https://mlsanity.com/paper/2105.14084/) (2021)
- [On the Benefits of Over-parameterization for Out-of-Distribution Generalization](https://mlsanity.com/paper/2403.17592/) (2024)
- [Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality](https://mlsanity.com/paper/2409.03891/) (2024)
- [Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergence](https://mlsanity.com/paper/2206.07892/) (2022)
- [When and How Unlabeled Data Provably Improve In-Context Learning](https://mlsanity.com/paper/2506.15329/) (2025)
- [On how to avoid exacerbating spurious correlations when models are overparameterized](https://mlsanity.com/paper/2206.12739/) (2022)
- [General Loss Functions Lead to (Approximate) Interpolation in High Dimensions](https://mlsanity.com/paper/2303.07475/) (2023)
- [Sharp analysis of out-of-distribution error for "importance-weighted" estimators in the overparameterized regime](https://mlsanity.com/paper/2405.06546/) (2024)
- [Balanced Data, Imbalanced Spectra: Unveiling Class Disparities with Spectral Imbalance](https://mlsanity.com/paper/2402.11742/) (2024)
- [A Theory for Conditional Generative Modeling on Multiple Data Sources](https://mlsanity.com/paper/2502.14583/) (2025)
- [Harmful Overfitting in Sobolev Spaces](https://mlsanity.com/paper/2602.00825/) (2026)
- [Hard labels sampled from sparse targets mislead rotation invariant algorithms](https://mlsanity.com/paper/2603.20967/) (2026)
- [Benign Overfitting under Learning Rate Conditions for α Sub-exponential Input](https://mlsanity.com/paper/2409.00733/) (2024)
- [Directional Convergence, Benign Overfitting of Gradient Descent in leaky ReLU two-layer Neural Networks](https://mlsanity.com/paper/2505.16204/) (2025)
- [Benign Overfitting in Linear Classifiers with a Bias Term](https://mlsanity.com/paper/2511.12840/) (2025)

## Abstract (arXiv)

Deep neural networks generalize well despite being exceedingly overparameterized and being trained without explicit regularization. This curious phenomenon has inspired extensive research activity in establishing its statistical principles: Under what conditions is it observed? How do these depend on the data and on the training algorithm? When does regularization benefit generalization? While such questions remain wide open for deep neural nets, recent works have attempted gaining insights by studying simpler, often linear, models. Our paper contributes to this growing line of work by examining binary linear classification under a generative Gaussian mixture model. Motivated by recent results on the implicit bias of gradient descent, we study both max-margin SVM classifiers (corresponding to logistic loss) and min-norm interpolating classifiers (corresponding to least-squares loss). First, we leverage an idea introduced in [V. Muthukumar et al., arXiv:2005.08054, (2020)] to relate the SVM solution to the min-norm interpolating solution. Second, we derive novel non-asymptotic bounds on the classification error of the latter. Combining the two, we present novel sufficient conditions on the covariance spectrum and on the signal-to-noise ratio (SNR) under which interpolating estimators achieve asymptotically optimal performance as overparameterization increases. Interestingly, our results extend to a noisy model with constant probability noise flips. Contrary to previously studied discriminative data models, our results emphasize the crucial role of the SNR and its interplay with the data covariance. Finally, via a combination of analytical arguments and numerical demonstrations we identify conditions under which the interpolating estimator performs better than corresponding regularized estimates.