Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting, and Regularization
SIAM Journal on Mathematics of Data Science · 2022-03 · 4 (1) · 260-284
DOI: 10.1137/21m1415121 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Mathematics of Data Science, online erschienen am 03.03.2022. Verfasst von Ke Wang und 1 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 50 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
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 in which the feature vectors take the form ${{\it x}}=\pm{{\eta}}+{{\it q}}$, where for a mean vector $\eta$ and feature noise ${{\it q}} \sim \mathcal{N}(0,{{\Sigma}})$. Motivated by recent results on the implicit bias of gradient descent, we study both max-margin support vector machine (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, 2020a] to relate the SVM solution to the min-norm interpolating solution. Second, we derive novel nonasymptotic 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) $SNR={||{{\eta}}||_2^4}/{{\eta}}^T{{\Sigma\eta}}$ 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.
Förderung
- National Science Foundation
Zitieren
APA
Wang, K., & Thrampoulidis, C. (2022). Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting, and Regularization. SIAM Journal on Mathematics of Data Science, 4(1), 260-284. https://doi.org/10.1137/21m1415121
Vancouver
Wang K, Thrampoulidis C. Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting, and Regularization. SIAM Journal on Mathematics of Data Science. 2022;4(1):260-284. doi:10.1137/21m1415121
BibTeX
@article{Wang2022,
author = {Wang, Ke and Thrampoulidis, Christos},
title = {Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting, and Regularization},
journal = {SIAM Journal on Mathematics of Data Science},
year = {2022},
volume = {4},
number = {1},
pages = {260--284},
doi = {10.1137/21m1415121}
}
EUVIMED