Vidya Muthukumar - Surprises in overparameterized linear classification

Seemingly counter-intuitive phenomena in deep neural networks and kernel methods have prompted a recent re-investigation of classical machine learning methods, like linear models. Of particular focus is sufficiently high-dimensional setups in which interpolation of training data is possible. In this talk, we will first briefly review recent works showing that zero regularization, or fitting of noise, need not be harmful in regression tasks. Then, we will use this insight to uncover two new surprises for high-dimensional linear classification:

• least-2-norm interpolation can classify consistently even when the corresponding regression task fails, and
• the support-vector-machine and least-2-norm interpolation solutions exactly coincide in sufficiently high-dimensional linear model.

These findings taken together imply that the linear SVM can generalize well in settings beyond those predicted by training-data-dependent complexity measures.

This is joint work with Misha Belkin, Daniel Hsu, Adhyyan Narang, Anant Sahai, Vignesh Subramanian, Christos Thrampoulidis, Ke Wang and Ji Xu.