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 2 norm ("ridgeless") interpolation in high-dimensional least squares regression. We consider two different models for the feature distribution: a linear model, where the feature vectors xi ∈ R p are obtained by applying a linear transform to a vector of i.i.d. entries, xi = Σ 1/2 zi (with zi ∈ R p ); and a nonlinear model, where the feature vectors are obtained by passing the input through a random one-layer neural network, xi = ϕ(W zi) (with zi ∈ R d , W ∈ R p×d a matrix of i.i.d. entries, and ϕ an activation function acting componentwise on W zi). 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. arXiv:1903.08560v2 [math.ST] 2 Apr 2019 • Linear model. Here each x i = Σ 1/2 z i , where z i ∈ R p has i.i.d. entries with zero mean and unit variance and Σ ∈ R p×p deterministic and positive definite. This is a standard model in random matrix theory and we leverage known results from that literature to obtain a fairly complete asymptotic characterization of the out-of-sample prediction risk. In particular, we recover a number of phenomena that have been observed in kernel regression and neural networks (summary in the next subsection). • Nonlinear model. Here each entries from N (0, 1/d), and ϕ is an activation function acting componentwise. This corresponds to a two-layer neural network with random weights at the first layer, and weights at the second layer given by the regression coefficients β. This model was introduced by Rahimi and Recht (2008) as a randomized approach for scaling kernel methods to large datasets. But (relative to the linear model described above) it is far less studied in the random matrix theory literature. We prove a new asymptotic result that allows us to characterize the prediction variance. The result is remarkably close to the result for the linear model (and in some cases, identical to it), despite the fact that d can be much smaller than p. Because of its simplicity, the linear model abstracts away some interesting properties of the model (1), specifically, the distinction between the input dimension d and the number of parameters p. But, also due to its simplicity, we are able to develop a fairly complete picture of the asymptotic risk (which shows the effect of correlations between the features, signal-to-noise ratio, strength of model misspecification, etc.). The fact that the two models give closely related results (for the variance component of the risk) supports the hope that the linear model can still provide useful insights into the model (1). In what follows, we study the out-of-sample prediction risk of the minimum 2 norm (or min-norm, for short) least squares estimator, in an asymptotic setting where both the number of samples and features diverge, n, p → ∞, and their ratio converges to a nonzero constant, p/n → γ ∈ (0, ∞). When γ < 1, we call the problem underparametrized, and when γ > 1, we call it overparametrized. Below we summarize our main results on the asymptotic risk. Denote by β, Σ the underlying signal and feature covariance matrix, respectively, and by SNR the signal-to-noise ratio (defined precisely in Section 3.3). Note that all but the last point below pertain to the linear model; also, see Figure 1 for a supporting plots, of the asymptotic risk curves for different cases of interest. 0. In the underparametrized regime (γ < 1), the risk is purely variance (there is no bias), and does not depend on β, Σ (see Theorem 1). Moreover, the risk diverges as we approach the interpolation boundary (as γ → 1). 1. In the overparametrized regime (γ > 1), the risk is composed of both bias and variance, and generally depends on β, Σ (see Theorem 4, Corollary 1, Appendix A.5). 2. When SNR ≤ 1, the risk is monotonically decreasing over γ ∈ (1, ∞), and approaches the null risk (from above) as γ → ∞ (see Section 3.3). 3. When SNR > 1, the risk has a local minimum on γ ∈ (1, ∞), is better than the null risk for large enough γ, and approaches the null risk (from below) as γ → ∞ (see Section 3.3). 4. For a misspecified model, when SNR > 1, the risk can attain its global minimum on γ ∈ (1, ∞) (when there is strong enough approximation bias, see Section 5.3). Optimally-tuned ridge regression dominates the min-norm least squares estimator in risk, across all values of γ and SNR, in both the well-specified and misspecified settings. For a misspecified model, optimally-tuned ridge regression attains its global minimum around γ = 1 (see Section 6). 6. For the nonlinear model, the asymptotics we obtain are still (surprisingly) exact (meaning, no hidden constants) (see Theorem 7). For the case of a "purely nonlinear" activation function, our theory reveals that the asymptotic risk, somewhat remarkably, matches that the linear model with isotropic features (see Corollary 2). A few remarks are in order. We number the first point above (which provides important context for the points that follow) as 0, because it is a known result that has appeared in various places in the random matrix theory literature.
REF use random matrix theory tools to compute the asymptotic risk when both P, N → ∞ with P N → γ > 0.
Surprises in High-Dimensional Ridgeless Least Squares Interpolation
ArXiv
ArXiv
Computer Science Mathematics