2020

The role of regularization in classification of high-dimensional noisy Gaussian mixture

Mignacco, Francesca, Krzakala, Florent, Lu, Yue M. et al.

Understand

We consider a high-dimensional mixture of two Gaussians in the noisy regime where even an oracle knowing the centers of the clusters misclassifies a small but finite fraction of the points.

We provide a rigorous analysis of the generalization error of regularized convex classifiers, including ridge, hinge and logistic regression, in the high-dimensional limit where the number $n$ of samples and their dimension $d$ go to infinity while their ratio is fixed to $\alpha= n/d$.
We discuss surprising effects of the regularization that in some cases allows to reach the Bayes-optimal performances.
We also illustrate the interpolation peak at low regularization, and analyze the role of the respective sizes of the two clusters.

Built on

T. M. Cover, Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition, IEEE transactions on electronic computers , 326 (1965)
1965
Earlier work this paper cites.
Y. Gordon, Some inequalities for Gaussian processes and applications, Israel Journal of Mathematics 50
1985
Earlier work this paper cites.
M. Mézard, G. Parisi, and M. Virasoro, Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications , Vol. 9 (World Scientific Publishing Company, 1987)
1987
Earlier work this paper cites.
Y. Gordon, On milman’s inequality and random subspaces which escape through a mesh in rn, in Geometric Aspects of Functional Analysis , Lecture Notes in Mathematics No. 1317, edited by J. Lindenstrauss and V. D. Milman (Springer Berlin Heidelberg, 1988) pp. 84–106
1988
Earlier work this paper cites.
E. Gardner, The space of interactions in neural network models, Journal of physics A: Mathematical and general 21
1988
Earlier work this paper cites.
E. Gardner and B. Derrida, Three unfinished works on the optimal storage capacity of networks, Journal of Physics A: Mathematical and General 22
1989
Earlier work this paper cites.
W. Krauth and M. Mézard, Storage capacity of memory networks with binary couplings, Journal de Physique 50
1989
Earlier work this paper cites.
P. Del Giudice, S. Franz, and M. Virasoro, Perceptron beyond the limit of capacity, Journal de Physique 50
1989
Earlier work this paper cites.
S. Franz, D. J. Amit, and M. A. Virasoro, Prosopagnosia in high capacity neural networks storing uncorrelated classes, Journal de Physique 51
1990
Earlier work this paper cites.
M. Opper and W. Kinzel, Statistical mechanics of generalization, in Models of neural networks III (Springer, 1996) pp. 151–209
1996
Earlier work this paper cites.
J. Friedman, T. Hastie, and R. Tibshirani, The elements of statistical learning , Vol. 1 (Springer series in statistics New York, 2001)
2001
Earlier work this paper cites.

Similar

S. Rosset, J. Zhu, and T. J. Hastie, Margin maximizing loss functions, in Advances in neural information processing systems (2004) pp. 1237–1244
2004
Cited alongside, same era.
D. O. Hebb, The organization of behavior: A neuropsychological theory (Psychology Press, 2005)
2005
Cited alongside, same era.
D. L. Donoho, A. Maleki, and A. Montanari, Message-passing algorithms for compressed sensing, Proceedings of the National Academy of Sciences 106
2009
Cited alongside, same era.
M. Mézard and A. Montanari, Information, physics, and computation (Oxford University Press, 2009)
2009
Cited alongside, same era.
M. Bayati and A. Montanari, The dynamics of message passing on dense graphs, with applications to compressed sensing, IEEE Transactions on Information Theory 57
2011
Cited alongside, same era.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al. , Scikit-learn: Machine learning in python, Journal of machine learning research 12
2011
Cited alongside, same era.
C. Thrampoulidis, S. Oymak, and B. Hassibi, Regularized linear regression: A precise analysis of the estimation error, in Proceedings of The 28th Conference on Learning Theory , Vol. 40 (PMLR, Paris, France, 2015) pp. 1683–1709
2015
Cited alongside, same era.
T. Lesieur, C. De Bacco, J. Banks, F. Krzakala, C. Moore, and L. Zdeborová, Phase transitions and optimal algorithms in high-dimensional gaussian mixture clustering, in 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (IEEE, 2016) pp. 601–608
2016
Cited alongside, same era.
D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro, The implicit bias of gradient descent on separable data, The Journal of Machine Learning Research 19
2018
Cited alongside, same era.
E. J. Candès and P. Sur, The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression, arXiv preprint arXiv:1804.09753 (2018)
Original
2018
Cited alongside, same era.
E. Dobriban, S. Wager, et al. , High-dimensional asymptotics of prediction: Ridge regression and classification, The Annals of Statistics 46
2018
Cited alongside, same era.

Then

T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani, Surprises in high-dimensional ridgeless least squares interpolation, arXiv preprint arXiv:1903.08560 (2019)
Original
2019
Later among the works it cites.
P. Sur and E. J. Candès, A modern maximum-likelihood theory for high-dimensional logistic regression, Proceedings of the National Academy of Sciences 116
2019
Later among the works it cites.
M. Lelarge and L. Miolane, Asymptotic Bayes risk for Gaussian mixture in a semi-supervised setting, arXiv preprint arXiv:1907.03792 (2019)
Original
2019
Later among the works it cites.
X. Mai and Z. Liao, High dimensional classification via empirical risk minimization: Improvements and optimality, arXiv preprint arXiv:1905.13742 (2019)
Original
2019
Later among the works it cites.
Z. Deng, A. Kammoun, and C. Thrampoulidis, A model of double descent for high-dimensional binary linear classification, arXiv preprint arXiv:1911.05822 (2019)
Original
2019
Later among the works it cites.
M. Geiger, S. Spigler, S. d’Ascoli, L. Sagun, M. Baity-Jesi, G. Biroli, and M. Wyart, Jamming transition as a paradigm to understand the loss landscape of deep neural networks, Physical Review E 100
2019
Later among the works it cites.
M. Belkin, D. Hsu, S. Ma, and S. Mandal, Reconciling modern machine-learning practice and the classical bias–variance trade-off, Proceedings of the National Academy of Sciences 116
2019
Later among the works it cites.
P. P. Mitra, Understanding overfitting peaks in generalization error: Analytical risk curves for l _ 2 l\_2 and l _ 1 l\_1 penalized interpolation, arXiv preprint arXiv:1906.03667 (2019)
Original
2019
Later among the works it cites.
S. Mei and A. Montanari, The generalization error of random features regression: Precise asymptotics and double descent curve, arXiv preprint arXiv:1908.05355 (2019)
Original
2019
Later among the works it cites.
P. Nakkiran, G. Kaplun, Y. Bansal, T. Yang, B. Barak, and I. Sutskever, Deep double descent: Where bigger models and more data hurt, arXiv preprint arXiv:1912.02292 (2019)
Original
2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…