SURPRISES IN HIGH-DIMENSIONAL RIDGELESS LEAST SQUARES INTERPOLATION

Abstract

Interpolators-estimators that achieve zero training error-have attracted growing attention in machine learning, mainly because state-of-the art neural networks appear to be models of this type. In this paper, we study minimum ℓ ₂ norm ("ridgeless") interpolation least squares regression, focusing on the high-dimensional regime in which the number of unknown parameters p is of the same order as the number of samples n. We consider two different models for the feature distribution: a linear model, where the feature vectors $x_i\in {ℝ}^p$ are obtained by applying a linear transform to a vector of i.i.d. entries, x _i = Σ^1/2 z _i (with $z_i\in {ℝ}^p$ ); and a nonlinear model, where the feature vectors are obtained by passing the input through a random one-layer neural network, x_i = φ(Wz _i ) (with $z_i\in {ℝ}^d$ , $W\in {ℝ}^{p\times d}$ a matrix of i.i.d. entries, and φ an activation function acting componentwise on Wz _i ). We recover-in a precise quantitative way-several phenomena that have been observed in large-scale neural networks and kernel machines, including the "double descent" behavior of the prediction risk, and the potential benefits of overparametrization.

Keywords: Primary 62J05, 62J07; Regression; interpolation; overparametrization; random matrix theory; ridge regression; secondary 62J02, 62F12.