CMSA Probability Seminar: Universality of max-margin classifiers

Many modern learning methods, such as deep neural networks, are so complex that they perfectly fit the training data. Despite this, they generalize well to the unseen data. Motivated by this phenomenon, we consider high-dimensional binary classification with linearly separable data. First, we consider Gaussian covariates and characterize linear classification problems for which the minimum norm interpolating prediction rule, namely the max-margin classification, has near-optimal prediction accuracy. Then, we discuss universality of max-margin classification. In particular, we characterize the prediction accuracy of the non-linear random features model, a two-layer neural network with random first layer weights. The spectrum of the kernel random matrices plays a crucial role in the analysis. Finally, we consider the wide-network limit, where the number of neurons tends to infinity, and show how non-linear max-margin classification with random features collapse to a linear classifier with a soft-margin objective.

Joint work with Andrea Montanari, Feng Ruan, Jun Yan, and Basil Saeed.