Proof Strategy For Benign-Overfitting Bounds

Why Separate Bias From Variance?

Minimum-norm least squares can interpolate the training data when the number of features is at least the number of observations. Exact fit alone does not determine prediction quality: the fitted coefficient vector may still have error in directions that matter under the test distribution. A useful risk analysis therefore separates two questions. How much signal is missed because the estimator projects onto the training row space? How much prediction error is added by fitting noise?

The derivation below keeps these terms distinct. The bias term depends on the realized design and the signal. The variance term depends on the noise covariance and on how well-conditioned the design is. Covariance eigenvalues connect the geometry of the observed design to prediction under the population feature distribution.

Definition: Let $X$ be an $n\times p$ design matrix with rows $x_i^\top$, and suppose a fresh feature vector $x_0$, independent of the training data, has mean zero and covariance $\Sigma=E[x_0x_0^\top]$. For an estimator $\hat\beta$, its conditional excess prediction risk is $E[(x_0^\top\hat\beta-x_0^\top\beta)^2\mid X]$, where the expectation averages over the training noise and the fresh feature vector, conditional on $X$. This risk concerns prediction of the conditional mean $x_0^\top\beta$, not an additional noisy test outcome.

Model and Exact Risk Decomposition

Assume the linear model $y=X\beta+\boldsymbol\varepsilon$, where $\beta\in\mathbb R^p$ is fixed. For the finite-sample bound below, the design rows are independent $N(0,\Sigma)$, with $\Sigma$ positive definite and $p\ge n$. In particular, $X$ has full row rank with probability one. Assume also that the noise satisfies

E[\boldsymbol\varepsilon\mid X]=0, \qquad \operatorname{Cov}(\boldsymbol\varepsilon\mid X)=\sigma^2 I_n.

The second condition is conditional homoskedasticity and absence of conditional cross-observation covariance. An unconditional statement that each noise coordinate has variance $\sigma^2$ is not a substitute for it.

When $X$ has full row rank, the minimum-Euclidean-norm solution that interpolates $y$ is

\hat\beta=X^\top(XX^\top)^{-1}y.

Write $P=X^\top(XX^\top)^{-1}X$. This matrix is the orthogonal projection onto the row space of $X$: it is symmetric, and $P^2=P$. Substituting the model into the estimator gives

\hat\beta-\beta=-(I-P)\beta+X^\top(XX^\top)^{-1}\boldsymbol\varepsilon.

The first term is the part of the signal lying outside the row space; the second is the contribution of training noise.

Theorem: Under the stated full-row-rank design and conditional noise assumptions, the conditional excess prediction risk is $$ R(X)=B(X)+V(X), $$ where $$ B(X)=\beta^\top(I-P)\Sigma(I-P)\beta $$ and $$ V(X)=\sigma^2\operatorname{tr}\!\left\{\Sigma X^\top(XX^\top)^{-2}X\right\}. $$

Proof. Put $A=X^\top(XX^\top)^{-1}$. For any fixed coefficient error $u$, the fresh-feature prediction error has conditional second moment $E[(x_0^\top u)^2]=u^\top\Sigma u$. Thus $R(X)=E[(\hat\beta-\beta)^\top\Sigma(\hat\beta-\beta)\mid X]$. Insert $\hat\beta-\beta=-(I-P)\beta+A\boldsymbol\varepsilon$ and expand the quadratic form. The cross term has conditional expectation zero because $E[\boldsymbol\varepsilon\mid X]=0$. The deterministic term is $B(X)$. For the remaining term, use $E[\boldsymbol\varepsilon\boldsymbol\varepsilon^\top\mid X]=\sigma^2I_n$:

E[\boldsymbol\varepsilon^\top A^\top\Sigma A\boldsymbol\varepsilon\mid X] =\operatorname{tr}\!\left(A^\top\Sigma A\,E[\boldsymbol\varepsilon\boldsymbol\varepsilon^\top\mid X]\right) =\sigma^2\operatorname{tr}(A^\top\Sigma A).

Substituting $A$ gives the displayed expression for $V(X)$. $\square$

Worked Examples: What the Decomposition Measures

Worked Example: Bias and Variance for a Two-Feature Design

Take one observed row $X=(1,1)$, $\Sigma=\operatorname{diag}(1,4)$, $\beta=(1,0)^\top$, and $\sigma^2=1/4$. This fixed design illustrates the exact algebra; it is not being treated as a draw from the Gaussian model used for the probability bound.

First, $XX^\top=2$, so

P=X^\top(XX^\top)^{-1}X =\frac12\begin{pmatrix}1&1\\1&1\end{pmatrix}, \qquad (I-P)\beta=\begin{pmatrix}1/2\\-1/2\end{pmatrix}.

Therefore the bias is

B(X) =\begin{pmatrix}1/2&-1/2\end{pmatrix} \begin{pmatrix}1&0\\0&4\end{pmatrix} \begin{pmatrix}1/2\\-1/2\end{pmatrix} =\frac14+\frac44=\frac54.

For the variance, $A=X^\top/2=(1/2,1/2)^\top$, so $A^\top\Sigma A=1/4+4/4=5/4$. Multiplying by $\sigma^2=1/4$ gives $V(X)=5/16$. The total conditional excess risk is $5/4+5/16=25/16$.

Worked Example: Covariance Weights the Missed Signal

Let $X=(1,0)$, $\Sigma=\operatorname{diag}(1,9)$, and $\beta=(0,1)^\top$. The row space is the first coordinate direction, so $P=\operatorname{diag}(1,0)$ and $(I-P)\beta=(0,1)^\top$. Hence

B(X)=(0,1) \begin{pmatrix}1&0\\0&9\end{pmatrix} \begin{pmatrix}0\\1\end{pmatrix}=9.

The signal is entirely in an unobserved direction, and that direction has population variance $9$, so the missed signal contributes $9$ to prediction risk. If instead $\beta=(1,0)^\top$, then $(I-P)\beta=0$ and $B(X)=0$. The amount of coefficient error alone is not enough to determine prediction bias; the covariance of future features matters.

Controlling the Variance With Spectral Bounds

For a symmetric positive-definite matrix $\Sigma$, let $\lambda_{\min}(\Sigma)$ and $\lambda_{\max}(\Sigma)$ denote its smallest and largest eigenvalues. Since $\Sigma\preceq\lambda_{\max}(\Sigma)I_p$, the variance term obeys

V(X) \le \sigma^2\lambda_{\max}(\Sigma) \operatorname{tr}\!\left\{X^\top(XX^\top)^{-2}X\right\} =\sigma^2\lambda_{\max}(\Sigma)\operatorname{tr}\!\left\{(XX^\top)^{-1}\right\}.

The trace identity follows by cycling the trace: $\operatorname{tr}\{X^\top(XX^\top)^{-2}X\} =\operatorname{tr}\{(XX^\top)^{-2}XX^\top\} =\operatorname{tr}\{(XX^\top)^{-1}\}$. If $s_{\min}(X)$ denotes the smallest of the $n$ singular values of the full-row-rank matrix $X$, then every eigenvalue of $(XX^\top)^{-1}$ is at most $1/s_{\min}(X)^2$. Consequently,

V(X)\le \sigma^2\lambda_{\max}(\Sigma)\frac{n}{s_{\min}(X)^2}.

To relate this to a standard random matrix, write $X=Z\Sigma^{1/2}$, where $Z$ is $n\times p$ with independent $N(0,1)$ entries. For every $u\in\mathbb R^n$,

\|X^\top u\|_2 =\|\Sigma^{1/2}Z^\top u\|_2 \ge\sqrt{\lambda_{\min}(\Sigma)}\,\|Z^\top u\|_2.

Taking the infimum over unit vectors $u$ gives $s_{\min}(X)\ge\sqrt{\lambda_{\min}(\Sigma)}s_{\min}(Z)$. Combining these inequalities yields the deterministic comparison

V(X)\le \sigma^2\frac{\lambda_{\max}(\Sigma)}{\lambda_{\min}(\Sigma)} \frac{n}{s_{\min}(Z)^2}.

Gaussian singular-value bound: If $Z$ is an $n\times p$ matrix of independent $N(0,1)$ entries with $p\ge n$, then for every $t\ge0$, $$ P\!\left(s_{\min}(Z)\ge\sqrt p-\sqrt n-t\right)\ge 1-\exp(-t^2/2). $$ This is the standard Gaussian smallest-singular-value inequality. When the threshold on the right is positive, combining it with the deterministic comparison gives a finite-sample upper bound on $V(X)$.

Theorem: Under the Gaussian design and conditional noise assumptions above, for $t\ge0$ such that $\sqrt p-\sqrt n-t>0$, with probability at least $1-\exp(-t^2/2)$ over the design, $$ R(X)\le B(X)+ \frac{\sigma^2\lambda_{\max}(\Sigma)}{\lambda_{\min}(\Sigma)} \frac{n}{(\sqrt p-\sqrt n-t)^2}. $$

Derivation. On the event in the Gaussian singular-value bound, $s_{\min}(Z)\ge\sqrt p-\sqrt n-t>0$. The deterministic variance comparison then gives

V(X)\le \frac{\sigma^2\lambda_{\max}(\Sigma)}{\lambda_{\min}(\Sigma)} \frac{n}{(\sqrt p-\sqrt n-t)^2}.

The exact decomposition gives $R(X)=B(X)+V(X)$, so adding $B(X)$ proves the claim on that same event. Its probability is at least $1-\exp(-t^2/2)$. $\square$

Worked Example: Evaluating the Finite-Sample Variance Bound

Suppose $n=2$, $p=10$, $\lambda_{\min}(\Sigma)=1$, $\lambda_{\max}(\Sigma)=4$, $\sigma^2=1/2$, and choose $t=1$. The required positive-threshold condition holds because \[ \sqrt{10}-\sqrt{2}-1\approx3.1623-1.4142-1=0.7481>0. \] The bound on the variance contribution is

\frac{(1/2)\cdot4}{1} \frac{2}{(0.7481)^2} \approx 2\frac{2}{0.5597} \approx 7.15.

The stated probability guarantee is $1-\exp(-1/2)\approx0.3935$. Thus the result says that, with probability at least about $0.3935$, the risk is at most $B(X)+7.15$. The bound is valid but may be loose; a finite-sample guarantee is not automatically a sharp estimate.

Reading the Bias Spectrally

The same covariance matrix also clarifies what the bias term measures. Let $\Sigma=U\operatorname{diag}(\lambda_1,\ldots,\lambda_p)U^\top$, with orthonormal eigenvectors $u_j$, and put $v=(I-P)\beta$. Then

B(X)=v^\top\Sigma v =\sum_{j=1}^p\lambda_j(u_j^\top v)^2.

This equality is an immediate consequence of substituting the eigendecomposition and using $U^\top U=I_p$. It shows why a small Euclidean norm of the missed signal does not by itself guarantee a small prediction bias: components aligned with large-eigenvalue directions receive larger weights. Conversely, a nonzero missed component in a low-variance direction can have a modest prediction-risk contribution. This identity is a way to inspect the bias; it does not, by itself, guarantee that a random design will leave only low-variance signal components unobserved.

Common Pitfall: Unconditional Noise Variance Is Not Enough

A tempting but invalid argument is: “The noise has variance $\sigma^2$, so the conditional variance term must be $\sigma^2\operatorname{tr}\{\Sigma X^\top(XX^\top)^{-2}X\}$.” That formula uses $\operatorname{Cov}(\boldsymbol\varepsilon\mid X)=\sigma^2I_n$, not merely an unconditional variance statement. If the conditional noise variance depends on the design, the correct variance term is instead

\operatorname{tr}\!\left[ \Sigma X^\top(XX^\top)^{-1} \operatorname{Cov}(\boldsymbol\varepsilon\mid X) (XX^\top)^{-1}X \right].

This follows from the same quadratic-form calculation as before, using the actual conditional covariance matrix. It need not be bounded by the homoskedastic expression. A separate upper bound on $\operatorname{Cov}(\boldsymbol\varepsilon\mid X)$ would be needed to obtain a corresponding variance guarantee. Also, the finite-sample theorem bounds the variance term while leaving $B(X)$ explicit; it does not assert that the bias is small for every signal and covariance.

Key takeaway: For minimum-norm least squares, derive risk as an exact design-dependent bias plus a conditional noise-variance term. Spectral comparison and Gaussian singular-value concentration control the latter; the signal’s alignment with the unobserved directions determines the former.

Check Your Understanding

Check that you can identify which part of the argument each assumption or matrix controls.

Why does the cross term in the risk expansion vanish, and what conditional assumption is used?
For $B(X)=\beta^\top(I-P)\Sigma(I-P)\beta$, explain why the Euclidean norm of $(I-P)\beta$ alone does not determine the prediction bias.
Where does the factor $\lambda_{\max}(\Sigma)/\lambda_{\min}(\Sigma)$ enter the finite-sample variance bound?
What does the Gaussian singular-value inequality say about the probability of a lower bound for $s_{\min}(Z)$?
If the noise is conditionally mean zero but has a design-dependent conditional covariance, which part of the risk decomposition remains unchanged, and what must replace the homoskedastic variance term?