Double descent

The risk is $\sigma^2$ plus the parameter error, and omitted features act as extra label noise. Isotropy gives risk $\sigma^2+\|\beta-\hat\beta\|^2=\sigma^2+\|\beta_{T^c}\|^2+\|\beta_T-\hat\beta_T\|^2$ in expectation, so only the last term needs analysis. Write $y=X_T\beta_T+\eta$ with $\eta=X_{T^c}\beta_{T^c}+\sigma\epsilon$. Independent Gaussian coordinates make $X_{T^c}$ and $\epsilon$ independent of $X_T$, so $$\eta\mid X_T\sim N\big(0,(\|\beta_{T^c}\|^2+\sigma^2)I_n\big).$$ Misspecification is label noise of variance $\|\beta_{T^c}\|^2$, and this independence (Gaussian, identity covariance) lets every later expectation factor.

Below the threshold the variance is an inverse Wishart trace (Breiman and Freedman). For $p\le n$, conditioning on $X_T$ gives $\mathbb E\|\hat\beta_T-\beta_T\|^2=(\|\beta_{T^c}\|^2+\sigma^2)\,\mathbb E\operatorname{tr}(X_T^*X_T)^{-1}$. By the Schur complement, $1/[(X_T^*X_T)^{-1}]_{jj}$ is the squared distance from column $j$ to the span of the others, a $\chi^2_{n-p+1}$, and $\mathbb E[1/\chi^2_k]=1/(k-2)$ for $k\ge3$ and $\infty$ for $k\le2$. So the trace has mean $p/(n-p-1)$ for $p\le n-2$ and is infinite at $p\in\{n-1,n\}$.

Above the threshold the error splits into a component in $\ker X_T$ and fitted noise. For $p\ge n$, with $K=X_TX_T^*$ and $\Pi_T$ the projection onto the row space, $$\beta_T-\hat\beta_T=(I-\Pi_T)\beta_T-X_T^*K^{-1}\eta,$$ a vector in $\ker X_T$ plus one in the row space, and Pythagoras separates bias and variance. The row space is uniformly random, so $\mathbb E\Pi_T=(n/p)I$ and the bias is $\|\beta_T\|^2(1-n/p)$, which grows with $p$ for fixed $\beta_T$. Under random selection its mean $\|\beta\|^2(p-n)/D$ grows exactly as fast as $\|\beta_{T^c}\|^2$ falls, keeping their sum at $\|\beta\|^2(1-n/D)$. So the second descent comes from the variance alone and levels off at a positive value.

The variance is $\operatorname{tr}K^{-1}$, finite only from $p=n+2$. The fitted noise has squared norm $\eta^*K^{-1}\eta$, with mean $(\|\beta_{T^c}\|^2+\sigma^2)\,\mathbb E\operatorname{tr}K^{-1}$. The Schur complement argument of Step 2, now on rows, makes $1/(K^{-1})_{ii}$ a $\chi^2_{p-n+1}$, so $\mathbb E\operatorname{tr}K^{-1}=n/(p-n-1)$ for $p\ge n+2$ and is infinite at $p\in\{n,n+1\}$. Since $\sigma\gt0$, the risk is infinite at $p\in\{n-1,n,n+1\}$, where the smallest singular value of $X_T$ (about $|\sqrt p-\sqrt n|$) is near zero.

Averaging over a random $T$ gives Corollary 1 and the shape of the curve. Theorem 1 is affine in $(\|\beta_T\|^2,\|\beta_{T^c}\|^2)$ given $|T|$, and exchangeability gives $\mathbb E\|\beta_T\|^2=\frac pD\|\beta\|^2$, so averaging amounts to substituting this mean. For $p\le n-2$ the risk is $(a-bp)\frac{n-1}{n-1-p}$ with $a=\|\beta\|^2+\sigma^2$, $b=\|\beta\|^2/D$; its derivative has the sign of $a-b(n-1)\gt0$, so the minimum over $p\le n$ is at $p=0$, and comparing with $p=D$ gives the threshold $D/(D-n-1)$. For $p\ge n+2$ both coefficients in Corollary 1 decrease in $p$ when $D\gt n+1$.

Theorem 2 follows by concentrating the bias and the variance separately. By the invariance of Step 3 the bias is $\|\beta_T\|^2(1-L)$ with $L\sim\mathrm{Beta}(n/2,(p-n)/2)$, concentrated by the Johnson-Lindenstrauss Chernoff bound. The variance $\eta^*K^{-1}\eta$ given $K$ is a weighted sum of $\chi^2_1$ variables, which concentrates around its conditional mean at the rate $$\Pr\big[\eta^*K^{-1}\eta\notin(1\pm\epsilon)(\|\beta_{T^c}\|^2+\sigma^2)\operatorname{tr}K^{-1}\mid K\big]\le2\exp\!\Big(-\frac{n\epsilon^2}{24\,\kappa(X_T)^2}\Big),$$ with the condition number $\kappa$ controlled by Gordon/Davidson-Szarek singular-value bounds. A union bound over the $\chi^2_{p-n+1}$ diagonals centers $\operatorname{tr}K^{-1}$ at the typical value $n/(p-n+1)$ rather than the mean $n/(p-n-1)$. For $\alpha\lt1$ there is no bias, and the same argument runs on $\eta^*K^\dagger\eta$ with $(n,p,\alpha)\to(p,n,\alpha^{-1})$.

Proposition 1 is Bernstein for sampling without replacement. $\|\beta_T\|^2$ sums $p$ draws without replacement from $(\beta_1^2,\dots,\beta_D^2)$, and Hoeffding's convex-order comparison transfers Bernstein's inequality from sampling with replacement. The population range $\mu^2\|\beta\|^2$ and variance at most $\frac{\|\beta\|^4}{D}(\mu^2-\frac1D)$ give its two terms.

In the Fourier model, unitarity reduces the risk to one inverse moment. With $P=F_{S,T}^\dagger F_{S,T}$, Pythagoras splits the error into $\|\beta\|^2-\|P\beta_T\|^2+\|F_{S,T}^\dagger F_{S,T^c}\beta_{T^c}\|^2$, and $\mathbb E\beta\beta^*=I/D$ turns each norm into a trace. For full-rank $F_{S,T}$, $\operatorname{tr}P=\min\{|S|,|T|\}$, and for $|T|\ge|S|$ orthonormal rows give $F_{S,T}F_{S,T}^*=I-F_{S,T^c}F_{S,T^c}^*$, and $$\mathbb E\|\beta-\hat\beta\|^2=1-2\,\mathbb E\min\Big\{\frac{|S|}D,\frac{|T|}D\Big\}+\frac nD\,(*),\qquad(*)=\mathbb E\Big[\frac1n\operatorname{tr}(F_{S,T}F_{S,T}^*)^{-1}\Big].$$

The limit of $(*)$, computed from a Haar block. By Farrell (2011) the squared singular values of a random DFT restriction have the same Wachter (MANOVA) limit as an $n\times p$ block of a Haar unitary, with support bounded away from $0$ when $\rho_p\gt\rho_n$. For the Haar block the inverse moment is exact: writing $U_{S,\cdot}\overset d=(ZZ^*)^{-1/2}Z$ with $Z$ complex Gaussian, $A=Z_TZ_T^*$ and $B=Z_{T^c}Z_{T^c}^*$ independent complex Wisharts, $$\operatorname{tr}(U_{S,T}U_{S,T}^*)^{-1}=n+\operatorname{tr}(A^{-1}B),\qquad\mathbb E=\frac{n(D-n)}{p-n},$$ so $(*)\to(1-\rho_n)/(\rho_p-\rho_n)$. A simulation ($D=1031$, $n=258$, $p=400$: 1.89 against 1.86) agrees.

The PNAS noiseless bound, which favors the minimum-norm interpolant. A Gaussian-RKHS function that vanishes on a dense set is uniformly small relative to its norm, and $f=h-h^*$ vanishes at every $x_i$ with $\|f\|\le\|h\|+\|h^*\|$. The sample has fill distance $\kappa_n=\max_{x\in\Omega}\min_j\|x-x_j\|=O((n/\log n)^{-1/d})$ with high probability, and Wendland's sampling inequality for Gaussian native spaces gives $$\|f\|_\infty\le e^{-c|\log\kappa|/\kappa}\|f\|_{\mathcal H_\infty}\le e^{-c/\kappa}\|f\|_{\mathcal H_\infty}$$ for small $\kappa$. Substituting $\kappa_n$ gives the theorem.