Benign Overfitting in Linear Regression

The risk is a bias form plus a noise form. With $A=\lambda I_n+XX^\top$, substituting $y=X\theta^*+\varepsilon$ gives $\hat\theta-\theta^*=(X^\top A^{-1}X-I)\theta^*+X^\top A^{-1}\varepsilon$, so the risk is at most $2B+2\varepsilon^\top C\varepsilon$ with bias $B=\|(X^\top A^{-1}X-I)\theta^*\|_\Sigma^2$ (at $\lambda=0$, $B=\theta^{*\top}P\Sigma P\theta^*$ with $P$ the projection onto $\ker X$) and $C=A^{-1}X\Sigma X^\top A^{-1}$. In expectation over $\varepsilon$ the cross term vanishes and the noise part averages to $\sigma^2V$ with $V=\mathrm{tr}(C)$ (at least $\sigma^2V$ under BLLT's $\mathbb E[\varepsilon^2\mid x]\ge\sigma^2$, which gives the lower bounds), and a Hanson-Wright bound for sub-Gaussian noise keeps the realized value within a constant times $\log(1/\delta)\,\sigma_y^2V$.

The variance is a sum of one term per eigendirection, and Sherman-Morrison makes each term explicit. Whiten each eigendirection, $z_i=Xv_i/\sqrt{\lambda_i}$, and write $V=\sum_i\lambda_i^2z_i^\top A^{-2}z_i$ with $A=\lambda I_n+\sum_i\lambda_iz_iz_i^\top$. Pull direction $i$ out of $A$ with Sherman-Morrison: $$\lambda_i^2z_i^\top A^{-2}z_i=\frac{\lambda_i^2\,z_i^\top A_{-i}^{-2}z_i}{\left(1+\lambda_i\,z_i^\top A_{-i}^{-1}z_i\right)^2}.$$ Under BLLT's independent coordinates the $z_i$ are independent, so $z_i$ is independent of $A_{-i}$ and both pieces are quadratic forms of a fresh subgaussian vector against a fixed matrix, and they concentrate. For a strong direction the denominator is large and the term matches the least-squares variance; for a weak one it is near 1, and that direction is shrunk as in ridge. The rest of the proof controls $A_{-i}$.

The tail Gram matrix is a nearly isotropic ridge exactly when $r_k\ge bn$. For a fixed unit $v$, $v^\top X_{k:\infty}X_{k:\infty}^\top v=\sum_{i>k}\lambda_i(v^\top z_i)^2$ is a weighted sum of subexponential variables, so Bernstein and a net over the sphere put every eigenvalue of the tail Gram matrix in $$\frac1c\sum_{i>k}\lambda_i-c\lambda_{k+1}n\ \le\ \mu_n\ \le\ \mu_1\ \le\ c\Big(\sum_{i>k}\lambda_i+\lambda_{k+1}n\Big).$$ Since $\sum_{i>k}\lambda_i=\lambda_{k+1}r_k$ at $\lambda=0$, the additive $\lambda_{k+1}n$ is negligible exactly when $r_k\ge bn$. Interlacing past the rank-$k$ head gives $\mu_{k+1}(A_{-i})\le\mu_1(A_k)$ for all $i$ and $\mu_n(A_{-i})\ge\mu_n(A_k)$ for $i\le k$. The top $k$ directions are rank-one spikes added to a near multiple of the identity of size $\sum_{i>k}\lambda_i$.

Upper bound; head directions contribute $1/n$ each and tail directions are ridge-shrunk. Fix $k\le n/c$ with $r_k\ge bn$. For a head term, drop the 1 in the denominator and bound the numerator by $\|z_i\|^2/\mu_n(A_{-i})^2$; the denominator cannot use $\mu_1(A_{-i})$, which contains the other head spikes, so restrict $z_i$ to the bottom $n-k$ eigenvectors of $A_{-i}$, a subspace independent of $z_i$ that keeps all but $k\le n/c$ of its dimensions; each head term is $O(1/n)$, the least-squares rate. For tail terms use only $\mu_n(A)\gtrsim\sum_{j>k}\lambda_j$ and Bernstein for $\sum_{i>l}\lambda_i^2\|z_i\|^2\le cn\sum_{i>l}\lambda_i^2$. Together, for every cutoff $l\le k$, $$V\le c\left(\frac ln+n\,\frac{\sum_{i>l}\lambda_i^2}{\left(\sum_{i>k}\lambda_i\right)^2}\right),$$ so each tail direction is shrunk by the factor $\lambda_i/\sum_{j>k}\lambda_j$, and its share of the noise is weighted by $\lambda_i$ at prediction time.

The lower bound holds term by term and is summed without a union bound. Reverse Step 4 using only the upper eigenvalue bound, which holds for any $\Sigma$: the bottom $n-k$ eigenvalues of $A_{-i}$ are at most of order $n\lambda_{k+1}(1+\rho_k)$, so restricting $z_i$ to their eigenvectors as in Step 4 gives $z_i^\top A_{-i}^{-1}z_i\gtrsim1/(\lambda_{k+1}(1+\rho_k))$. Cauchy-Schwarz, $(z_i^\top A_{-i}^{-1}z_i)^2\le\|z_i\|^2\,z_i^\top A_{-i}^{-2}z_i$, bounds the Sherman-Morrison ratio below by $1/(\|z_i\|^2(1+(\lambda_iz_i^\top A_{-i}^{-1}z_i)^{-1})^2)$, so with probability $1-ce^{-n/c}$ $$\lambda_i^2z_i^\top A^{-2}z_i\ \ge\ \frac1{cn}\min\Big\{1,\ \frac{\lambda_i^2}{\lambda_{k+1}^2(1+\rho_k)^2}\Big\}.$$ There may be infinitely many directions, so a union bound is useless; a first-moment argument (BLLT's Lemma 15, TB's Lemma 26) shows that if each $\eta_i\ge0$ exceeds $t_i$ with probability $1-\delta$, then $\sum_i\eta_i\ge\frac12\sum_it_i$ with probability $1-2\delta$, with no independence needed, which matters because all the terms share $A$. If $r_k<bn$ for every $k\le n/c$, the first $n/c$ terms contribute order $1/n$ each and $\mathbb ER\ge\sigma^2/c$. TB run the same argument for any $\lambda$, with $|A_{-i}|$ in place of $A_{-i}$ when $\lambda<0$.

The optimal cutoff is $l=k^*$, which gives $k^*/n+n/R_{k^*}$. When $r_k\ge bn$, since $\lambda_i$ is nonincreasing and the second entry of the minimum is at most 1 for $i>k$, the summed lower bound is, up to constants, a minimum over cutoffs $l\le k$ of the Step 4 upper bound. Any qualifying $k$ gives $\sum_{i>k}\lambda_i$ within constants of $\mu_n(A)$, so take $k=k^*$. The objective puts index $i$ in the head iff $\lambda_i\ge\bar\lambda/b$, and minimality of $k^*$ with the recursion $r_k=\frac{\lambda_k}{\lambda_{k+1}}(r_{k-1}-1)$ places that threshold exactly between $\lambda_{k^*}$ and $\lambda_{k^*+1}$, so $l=k^*$ and the value is $k^*/n+n/R_{k^*}$. Going past $k^*$ cannot help, because an identity for $1/R_{k+1}$ shows that $k/(b^2n)+n/R_k$ increases once $r_k>bn$; with Step 1 this proves the variance parts of Theorem 4.

The bias is bounded by a covariance-estimation error, and its lower bound puts $\theta^*$ on the top eigenvector. The projection $P$ onto $\ker X$ annihilates the empirical covariance, so $$\theta^{*\top}P\Sigma P\theta^*\le\Big\|\Sigma-\tfrac1nX^\top X\Big\|\,\|\theta^*\|^2,$$ which the Koltchinskii-Lounici bound controls through $r_0$, whatever the alignment of $\theta^*$. For the lower bound take $\theta^*=t\,v_1$: when $r_0\ge Cn$, Step 3 with $k=1$ shows the interpolant keeps only a fraction of order $n/r_0$ of $\theta^*$, so the bias is at least $t^2\|\Sigma\|/4$, and since $\varepsilon$ is symmetric, $R(\hat\theta)$ is at least the bias with conditional probability $1/2$. The paper argues instead by reduction to learning from labels rounded to a fine grid (a dither undoes the rounding up to total variation $n\alpha$ over the sample) and counting: grouping coordinates into $d=\Omega(n\log n)$ blocks of eigenvalue mass in $[1,2)$ gives a packing, at scale $3\sqrt\tau$ in the $\Sigma$-norm, of size $(1/\tau)^{\Omega(d)}$, and for packing points $g$ in the unit ball $|x_t^\top g|\le\|x_t\|$ allows only $\exp(O(n\log(nd)))$ distinct quantized label vectors, too few to recover them all.

Which spectra are benign, by parametrizing spectra through their effective ranks. The sequence $r_k$ determines $\lambda$ up to scale through $\lambda_{k+1}r_k=\lambda_kr_{k-1}(1-r_{k-1}^{-1})$, so the conditions can be checked in $r$: for increasing $r_k$, $k^*/n\to0$ iff $r_n/n\to\infty$, and Stolz-Cesaro gives $n/R_{k^*}\to0$ whenever $r_k^{-2}=o(r_k^{-1}-r_{k+1}^{-1})$. For fixed $\Sigma$ with $\lambda_k=k^{-\alpha}\ln^{-\beta}(k+1)$, overfitting is benign iff $\alpha=1,\beta>1$: there $r_0$ is finite, $r_n=\Theta(n\log n)$ and $r_{k+1}-r_k\to\infty$, so all three conditions hold; for $\alpha>1$, $r_n=O(n)$ and $k^*/n\not\to0$; for $\alpha<1$ or $\beta\le1$ the spectrum is not summable. In finite dimension $p_n$, $R_k\le p_n-k$ forces $p_n=\omega(n)$, and even an exponentially decaying $\gamma_k=\Theta(e^{-k/\tau})$ is benign once an isotropic floor $\epsilon_n$ is added, iff $p_n=\omega(n)$ and $ne^{-o(n)}=\epsilon_np_n=o(n)$; the floor must not be exponentially small because $k^*=\tau\ln(n/(\epsilon_np_n))+O(1)$, and then $R_{k^*}=\Theta(\min\{n^2,p_n\})$.

The head solves a $k$-dimensional ridge problem, and every upper bound follows from it. Write $A=A_k+X_{0:k}X_{0:k}^\top$ in $\hat\theta_{0:k}=X_{0:k}^\top A^{-1}y$ and multiply out: $$\hat\theta_{0:k}+X_{0:k}^\top A_k^{-1}X_{0:k}\hat\theta_{0:k}=X_{0:k}^\top A_k^{-1}y,$$ the normal equation of generalized least squares on the head with weight $A_k^{-1}$ and unit ridge; if $A_k\approx(\lambda+\sum_{i>k}\lambda_i)I_n$, it is ordinary ridge at penalty $\lambda+\sum_{i>k}\lambda_i$. Testing the identity against $\hat\theta_{0:k}$ and dropping $\|\hat\theta_{0:k}\|^2\ge0$ bounds the head variance by the OLS rate $k/n$ times the squared condition number of $A_k$; the same move on the error bounds the head bias by ridge shrinkage $\|\theta^*_{0:k}\|^2_{\Sigma^{-1}}\bar\lambda^2$ plus the tail signal acting as noise. The tail needs no structure: $A\succeq A_k$ bounds its variance by $n\sum_{i>k}\lambda_i^2/\mu_n(A_k)^2$, and its bias is the unlearned signal $\|\theta^*_{k:\infty}\|^2_\Sigma$ plus two leakage terms carrying $\lambda_{k+1}$ and a factor $1+\lambda_-/\mu_n(A_k)$, $\lambda_-=\max(0,-\lambda)$, the only place where a negative ridge enlarges the bound. All of these bounds are deterministic on $\{A_k\succ0\}$, in terms of $\mu_1(A_k)$, $\mu_n(A_k)$ and the head sample covariance, which Step 10 pins down.

Concentration pins the eigenvalues of $A_k$, and CondNum reduces to a small-ball condition. The only uniform convergence used is in the $k$-dimensional head (its sample covariance is close to $nI_k$). The trace of $A_k$ concentrates at $n(\lambda+\sum_{i>k}\lambda_i)$ (Lemma 25), fixing the average eigenvalue; NoncritReg, $\sum_{i>k}\lambda_i\le(\lambda+\sum_{i>k}\lambda_i)/(1-\gamma)$, keeps the trace's fluctuation, of order $\sqrt{nt}\sum_{i>k}\lambda_i$ at deviation level $t$, a fraction $\sqrt{t/n}/(1-\gamma)$ of the mean even for $\lambda<0$, and the condition number fixes the rest, so every factor of the general bound becomes a constant (Corollary 6, valid at any such $k$); a well-conditioned tail in turn forces $\rho_k\ge1/c$, since $\mu_1(A_k)\ge\lambda+n\lambda_{k+1}/2$. Decoupling over random splits of the rows makes the off-diagonal part of $A_k$ small once $\rho_k$ is large, so the diagonal determines the conditioning (Lemma 3): if $\rho_k\ge L^2$ and $\min_j(\lambda+\|x_{j,k:\infty}\|^2)$ stays a constant fraction of its mean, CondNum holds; conversely CondNum forces $\rho_k\ge1/(cL)$ and, if it holds with probability $1-ce^{-n/c}$, the same small-ball bound, since $\mu_n(A_k)\le\min_jA_k[j,j]$. Sub-Gaussianity alone does not give it: $x$ replaced by $\sqrt2x$ or $0$ with probability $1/2$ each keeps the covariance and $\psi_2$ norm but makes the Gram matrix singular.

CondNum at an oracle $k\ge k^*$ implies CondNum at $k^*$, which gives Theorem 1. Lowering $k$ only adds PSD terms to $A_k$, so its smallest eigenvalue can only grow, while sub-Gaussianity caps the largest at $\lambda+c(n\lambda_{k^*+1}+\sum_{i>k^*}\lambda_i)$. The two scales match because the removed mass is small: $n\lambda_{k^*+1}=(\lambda+\sum_{i>k^*}\lambda_i)/\rho_{k^*}<(\lambda+\sum_{i>k^*}\lambda_i)/b$, and in Theorem 1 $k<n/c$, so $\sum_{k^*<i\le k}\lambda_i\le(n/c)\lambda_{k^*+1}<(\lambda+\sum_{i>k^*}\lambda_i)/(bc)$, and $c>2/b$ suffices. So CondNum holds at $k^*$ (Lemma 11), and Corollary 6 there is Theorem 1.

The bias lower bound, and why the two forms agree. Averaging over random signs of $\theta^*$ removes the cross terms of $B=\theta^{*\top}M\theta^*$, $M=(X^\top A^{-1}X-I)\Sigma(X^\top A^{-1}X-I)$, and Sherman-Morrison makes each diagonal entry explicit, $M_{ii}\ge\lambda_i/(1+\lambda_iz_i^\top A_{-i}^{-1}z_i)^2$. This needs $\mu_n(A_{-i})$ bounded below for every $i$, which follows from CondNum and exchangeable coordinates ($A_{-i}\succeq A_k$ for $i\le k$, and for $i>k$ swapping $z_1$ in for $z_i$ makes $A_{-i}$ dominate a copy of $A_k$); with $\|z_i\|^2\le2n$ each term is at least $\lambda_i\bar\theta_i^2/(1+2L\lambda_i/\bar\lambda)^2$, and Lemma 15 sums the terms. Coordinate by coordinate, upper and lower bounds agree iff $\lambda_i\gtrsim\bar\lambda$ in the head and $\lambda_i\lesssim\bar\lambda$ in the tail, that is, when $k$ sits where the spectrum crosses $\bar\lambda$ (Theorem 10). The tail condition is $\rho_k>a$; at $k=k^*$ the head condition follows from $\rho_{k-1}\le b$, which gives $\lambda_k\ge\bar\lambda/b$. This is also why the bounds are loose for $k\gg k^*$: coordinates in $(k^*,k]$ have $\lambda_i\ll\bar\lambda$ and are barely learned, yet a split at $k$ counts $1/n$ of variance for each of them.

A negative ridge can go below a bias lower bound that holds for every $\lambda\ge0$. For $\lambda\ge0$ the bias lower bound is monotone in $\lambda$, and at $\lambda=0$ under independent coordinates the sharper tail eigenvalue bound from BLLT's proof (TB's Lemma 16), $\sum_{i>k}\lambda_i\pm c(n\lambda_{k+1}+\sqrt{n\sum_{i>k}\lambda_i^2})$, applied for $i>k$ to the tail matrix with $\sqrt{\lambda_i}z_1$ swapped into slot $i$ (same assumptions, though not in general the same law), gives $\mu_n(A_{-i})\ge\frac12\sum_{i>k}\lambda_i$ once $\rho_k(0)>b$, so the head shrinkage is at least of order $\sum_{i>k}\lambda_i/n$ (Lemma 17). Negative ridge cancels most of it while keeping $A_k$ well conditioned: set $\lambda=-\sum_{i>k}\lambda_i+\diamond$, where $\diamond$ can go down to the fluctuation $n\lambda_{k+1}+\sqrt{n\sum_{i>k}\lambda_i^2}$ of the tail Gram eigenvalues. With small noise, $\diamond\approx\sqrt{n\lambda_{k+1}\sum_{i>k}\lambda_i}$ balances head shrinkage against leakage, and the head bias drops from $(\sum_{i>k}\lambda_i)^2/n^2$ to $\lambda_{k+1}\sum_{i>k}\lambda_i/n$, a factor of $\rho_k(0)$; with larger noise $\diamond$ instead balances head bias against tail variance, and it stays below $\sum_{i>k}\lambda_i$ when $v_\varepsilon^2\lesssim\|\bar\theta_{0:k}\|^2_{\Sigma^{-1}}(\sum_{i>k}\lambda_i)^4/(n^3\sum_{i>k}\lambda_i^2)$. The theorem: under random signs and independent coordinates, with $k=\min\{\kappa:\rho_\kappa(0)>b\}<n/c$, the minimizer over $\lambda$ of $\mathbb E_{\theta^*}B+v_\varepsilon^2V$ is negative with probability $1-ce^{-n/c}$ provided $$v_\varepsilon^2\le\frac{\|\bar\theta_{0:k}\|^2_{\Sigma^{-1}_{0:k}}}{c}\min\Big(\frac{(\sum_{i>k}\lambda_i)^2}{nk},\frac{(\sum_{i>k}\lambda_i)^4}{n^3\sum_{i>k}\lambda_i^2}\Big),\quad \rho_k(0)>c,\quad \|\bar\theta_{k:\infty}\|^2_{\Sigma_{k:\infty}}\le\frac1c\|\bar\theta_{0:k}\|^2_{\Sigma^{-1}_{0:k}}\frac{(\sum_{i>k}\lambda_i)^2}{n^2}.$$ In words, the best $\lambda$ is negative with high probability given small noise, a jump in effective rank ($\rho_{k-1}(0)\le b$ but $\rho_k(0)>c$, forcing $\lambda_k/\lambda_{k+1}>c/b$) and little tail signal, and the gain is at least of order $\rho_k(0)$; no matching lower bound is proved in this regime.

Consequences and limits. Benign overfitting needs small total scale ($r_0=o(n)$, up to a log, for the bias), few strong directions ($k^*=o(n)$), a tail that is both heavy and flat ($R_{k^*}\gg n$), so that the unimportant directions greatly outnumber $n$, and, by TB's bias bounds (under the assumptions of both their theorems, with $k^*<n/c$), signal that sits in the head: $\|\theta^*_{k^*:\infty}\|_\Sigma\to0$ and $\|\theta^*_{0:k^*}\|_{\Sigma^{-1}}\bar\lambda\to0$. The risk depends on $\lambda$ only through $\lambda+\sum_{i>k}\lambda_i$, so every $\lambda\in(-\gamma\sum_{i>k}\lambda_i,\,O(\sum_{i>k}\lambda_i))$ is within a constant of the min-norm interpolant: positive $\lambda$ helps when the implicit regularization is too small (tail variance dominates), negative $\lambda$ when it is too large. Limits: constants are unspecified; BLLT's covariates must be a linear image of independent coordinates (which excludes RKHS features of low-dimensional inputs and the NTK); TB's upper bound assumes CondNum as an oracle, their lower bounds need independent or exchangeable coordinates and random signs, and the noise must be independent of $X$ (Shamir 2022 has a misspecified counterexample).