Surprises in High-Dimensional Ridgeless Least Squares Interpolation

Context. Deep networks fit noisy data exactly, still predict well, and show "double descent" in model size (Belkin et al. 2018). The authors compute the exact risk of the minimum-$\ell_2$-norm interpolator and of ridge with $p/n\to\gamma$, for general $\Sigma$ and $\beta$, misspecified models, and random nonlinear features. The analysis shows that, as $p/n\to\gamma$, the min-norm interpolator acts like ridge regression on the population covariance with an implicit penalty $\tau$ fixed by $\operatorname{Tr}\Sigma(\Sigma+\tau)^{-1}=n$ (this effective-ridge form is a rewriting of the paper's $c_0$ formulas, with $\tau=1/(\gamma c_0)$). Directions with eigenvalue well above $\tau$ are learned and weaker ones are lost to bias, and a factor $1/(1-\nu)$, $\nu=\tfrac1n\operatorname{Tr}\Sigma^2(\Sigma+\tau)^{-2}$, inflates both bias and variance; it diverges at $p=n$ and shrinks as $p$ grows. Overparametrization can lower the risk when $\beta$ sits in a few strong directions and many weak directions supply the implicit penalty.

Setting. $y_i=x_i^T\beta+\varepsilon_i$ with $\operatorname{Var}\varepsilon_i=\sigma^2$ and $x_i=\Sigma^{1/2}z_i$, $z_i$ with independent coordinates of mean 0 and variance 1. The estimators are the min-norm interpolator $\hat\beta=(X^TX)^+X^Ty=\lim_{\lambda\to0^+}\hat\beta_\lambda$ (also the limit of gradient descent from 0) and ridge $\hat\beta_\lambda=(X^TX+n\lambda I)^{-1}X^Ty$. With $S_X=X^TX/n$ and $\Pi$ the projection onto the null space of $X$, the conditional risk $\mathbb E[\|\hat\beta-\beta\|_\Sigma^2\mid X]$ splits as $$B_X(\hat\beta)=\beta^T\Pi\Sigma\Pi\beta,\quad V_X(\hat\beta)=\tfrac{\sigma^2}{n}\operatorname{Tr}(S_X^+\Sigma),\quad B_X(\hat\beta_\lambda)=\lambda^2\beta^T(S_X+\lambda)^{-1}\Sigma(S_X+\lambda)^{-1}\beta,\quad V_X(\hat\beta_\lambda)=\tfrac{\sigma^2}{n}\operatorname{Tr}\Sigma S_X(S_X+\lambda)^{-2}.$$ The geometry enters through the eigenvalue distribution $\hat H_n$ of $\Sigma$ and its $\beta$-weighted version $\hat G_n$. Assumption 1: all moments of $z_{ij}$ bounded, $\|\Sigma\|\le M$ and $\int s^{-1}d\hat H_n<M$, and $p/n$ in $[1/M,M]$ with $|1-p/n|\ge1/M$.

Proposition 2 and Theorem 1 (isotropic). If $\gamma<1$, $\lambda_{\min}(\Sigma)\ge c>0$ and $z$ has four moments, $R_X\to\sigma^2\gamma/(1-\gamma)$ almost surely for every $\Sigma$ and $\beta$, so the risk is all variance. If $\Sigma=I$, $4+\eta$ moments and $\|\beta\|^2=r^2$, then for $\gamma>1$ $$B_X\to r^2\Big(1-\frac1\gamma\Big),\qquad V_X\to\frac{\sigma^2}{\gamma-1}.$$ With $\mathrm{SNR}=r^2/\sigma^2\gt1$, on $\gamma>1$ the risk is below the null risk $r^2$ exactly when $\gamma>\mathrm{SNR}/(\mathrm{SNR}-1)$, with a local minimum at $\gamma=\sqrt{\mathrm{SNR}}/(\sqrt{\mathrm{SNR}}-1)$, but the global minimum is always at $\gamma\to0$.

Theorem 2 (general $\Sigma$, min-norm). Let $\tau$ solve $\frac1n\operatorname{Tr}\Sigma(\Sigma+\tau)^{-1}=1$, $\nu=\frac1n\operatorname{Tr}\Sigma^2(\Sigma+\tau)^{-2}$, and $$\mathcal B=\frac{\tau^2\,\beta^T\Sigma(\Sigma+\tau)^{-2}\beta}{1-\nu},\qquad \mathcal V=\sigma^2\frac{\nu}{1-\nu}.$$ This rewrites the paper's (11) and (12) via $\tau=1/(\gamma c_0)$, with $c_0$ the paper's fixed point (checked algebraically and numerically). Under Assumption 1 and $\lambda_{\min}(\Sigma)>1/M$, with probability at least $1-Cn^{-D}$, $|B_X(\hat\beta)-\mathcal B|\le C\|\beta\|^2n^{-1/7}$ and $|V_X(\hat\beta)-\mathcal V|\le Cn^{-1/7}$. Theorem 3 gives almost-sure limits under $4+\delta$ moments. If $G=H$ (e.g. $\beta$ uniform on a sphere), $\mathcal B=r^2\tau/\gamma$; for $\Sigma=I$, $\tau=\gamma-1$.

Theorem 5 (general $\Sigma$, ridge). Let $\tau(\lambda)>0$ solve $\tau=\lambda+\frac{\tau}{n}\operatorname{Tr}\Sigma(\Sigma+\tau)^{-1}$, so $\tau(0^+)$ is the $\tau$ of Theorem 2, with $\nu(\lambda)$, $\mathcal B(\lambda)$, $\mathcal V(\lambda)$ as before at $\tau(\lambda)$ (a rewriting of the paper's (38) and (39) via $\tau(\lambda)=1/r_n(-\lambda)$). If Assumption 1 holds, $\lambda\vee\lambda_{\min}(\Sigma)>1/M$ and $n^{-2/3+1/M}<\lambda<M$, then with probability $1-Cn^{-D}$ $$|B_X(\hat\beta_\lambda)-\mathcal B(\lambda)|\le\frac{C\|\beta\|^2}{\lambda n^{(1-\varepsilon)/2}},\qquad |V_X(\hat\beta_\lambda)-\mathcal V(\lambda)|\le\frac{C}{\lambda^2n^{(1-\varepsilon)/2}}.$$ For $\Sigma=I$ the optimal penalty is $\lambda^*=\sigma^2\gamma/r^2$, tuned ridge beats min-norm at every $\gamma$, and leave-one-out CV and GCV find it.

Theorem 4 (misspecified, isotropic). If $y=x^T\beta+w^T\theta+\varepsilon$ but only $x$ is observed, with i.i.d. entries of $(x,w)$ ($8+\eta$ moments), $r^2=\|\beta\|^2+\|\theta\|^2$ and $\kappa=\|\beta\|^2/r^2$, then for $\gamma>1$ $$R_X\to r^2(1-\kappa)+r^2\kappa\Big(1-\frac1\gamma\Big)+\big(r^2(1-\kappa)+\sigma^2\big)\frac{1}{\gamma-1},$$ and for $\gamma<1$ the first and last terms with $\frac{\gamma}{1-\gamma}$: irreducible bias, null-space bias, and variance in which the omitted signal acts as extra noise. If $1-\kappa(\gamma)=(1+\gamma)^{-a}$ with $\mathrm{SNR}>1$ and $a\le1+1/\mathrm{SNR}$, the global minimum is at some $\gamma>1$.

Corollary 4 (latent space model). $y_i=\theta^Tz_i+\xi_i$ and $x_{ij}=w_j^Tz_i+u_{ij}$, with $z_i\sim N(0,I_d)$, noise $u$, and $W^TW=(p/d)I_d$. Matching second moments gives a linear model with $$\Sigma=I_p+WW^T,\quad\beta=W(I+W^TW)^{-1}\theta,\quad\sigma^2=\sigma_\xi^2+\theta^T(I+W^TW)^{-1}\theta,$$ so $\beta$ lies in the top eigenspace $1+1/\psi$, $\psi=d/p\in(0,1)$, and Theorem 2 gives the risk in closed form. At fixed $n/d$ the paper's plots show the risk smallest as $\gamma\to\infty$ and the optimal ridge $\lambda$ tending to 0 even with $\sigma_\xi>0$ (observed, not proved).

Theorem 8 (nonlinear random features). Let $x_i=\varphi(Wz_i)$, $z_i\sim N(0,I_d)$, $W_{ij}\sim N(0,1/d)$, with $\mathbb E\varphi(G)=0$, $\mathbb E\varphi(G)^2=1$ and $\mathbb E[G\varphi(G)]=0$ (a "purely nonlinear" activation), $p/n\to\gamma$, $d/p\to\psi\in(0,1)$. Then $$\lim_{\lambda\to0^+}\lim_{n,p,d}V_X(\hat\beta_\lambda)=\frac{\sigma^2}{\gamma-1}\ (\gamma>1),\qquad \lim_{\lambda\to0^+}\lim_{n,p,d}\mathbb E_\beta B_X(\hat\beta_\lambda)=r^2\Big(1-\frac1\gamma\Big)_+,$$ with the bias averaged over an isotropic prior. These are exactly the isotropic linear answers, although each $x_i$ is a function of only $d\ll p$ Gaussians.

Consequences and limits. The limits are exact and two-sided, so the risk curves are determined exactly: the peak at $\gamma=1$ is the divergence of $1/(1-\nu)$, and the second descent is the variance falling as $\tau$ grows with $p$. With isotropic or equidistributed $\beta$ in a well-specified model, overparametrization never beats $\gamma\to0$, and tuned ridge dominates min-norm. Interpolation is near-optimal when the spectrum is spiked plus bulk with $\beta$ in the spikes: the weak directions add roughly $\gamma I_n$ to $XX^T/n$, an implicit ridge, while the spike $1+p/d$ grows as fast as $\tau$, so in the paper's plots the risk keeps falling in $\gamma$ and the best $\lambda$ tends to 0 (compare the effective ranks of Bartlett et al.). Misspecification is a second route past $\gamma=1$. Limits: $p/n$ stays bounded away from 0, 1 and $\infty$, so nothing here is about consistency; the min-norm bounds need $\lambda_{\min}(\Sigma)>1/M$, ruling out the decaying spectra of benign overfitting; the nonlinear result covers only $c_1=0$, takes $n\to\infty$ before $\lambda\to0$, and averages the bias over a prior; and fixed features link to neural networks only in the lazy regime.