A Counterexample To Benign Overfitting

Why Interpolation Need Not Be Benign

An interpolating predictor has zero training error, but that fact alone says little about its predictions on new observations. Whether interpolation is benign depends on how the design distributes information across feature directions, how many effective directions remain relative to the sample size, and how the signal and noise interact with those directions. A useful counterexample makes the failure visible without relying on anisotropy or a badly aligned signal.

We use a particularly simple model: the features are isotropic Gaussian, the regression signal is zero, and the responses are pure noise. Even here, when the number of features is only slightly larger than the sample size, the minimum-norm interpolator can have large expected prediction risk. Thus, “more features than observations” is not, by itself, a guarantee of benign overfitting.

Model and Minimum-Norm Interpolation

Let $X$ be an $n \times p$ design matrix whose rows $x_i^T$ are independent $N(0,I_p)$ vectors, with $p>n$. The responses follow the linear model

y=X\beta^*+\varepsilon,\qquad \varepsilon\sim N(0,\sigma^2 I_n),

where the noise is independent of $X$. For a fresh feature vector $x_{\mathrm{new}}\sim N(0,I_p)$, independent of the training data, the regression function is $x_{\mathrm{new}}^T\beta^*$. We measure excess prediction risk by the expected squared difference between the fitted prediction and this regression function. This excludes the irreducible noise in a future response.

Definition: When $X$ has full row rank and $p>n$, the minimum-Euclidean-norm interpolator is the vector of smallest squared Euclidean norm among all $\beta$ satisfying $X\beta=y$. It is $$ \hat{\beta}=X^T(XX^T)^{-1}y. $$ The Gaussian design has full row rank with probability one.

The formula does interpolate because $X\hat{\beta}=XX^T(XX^T)^{-1}y=y$. It is the minimum-norm solution because it lies in the row space of $X$, which is orthogonal to the null space of $X$. Every other solution differs from it by a vector in that null space, so its squared norm is the squared norm of $\hat{\beta}$ plus the squared norm of that difference.

Worked Example: A Finite but Large Risk

Take $n=100$, $p=102$, $\beta^*=0$, and $\sigma^2=1$. There are two more features than observations, so the minimum-norm interpolator can fit all 100 noisy responses exactly. We will calculate its expected excess prediction risk below; it is 100.

The population feature covariance is $I_{102}$, so prediction risk for a fixed fitted vector is its squared Euclidean norm: $E[(x_{\mathrm{new}}^T\hat{\beta})^2\mid\hat{\beta}]=\|\hat{\beta}\|^2$. The interpolator is fitting pure noise, so a large value of this norm represents noise that has been fitted in directions that also affect new predictions. The calculation does not depend on a hidden signal or on a covariance direction with a specially small eigenvalue.

An Exact Risk Calculation

Theorem: Under the Gaussian model above, if $p>n+1$, the expected excess prediction risk of the minimum-norm interpolator is $$ E\!\left[(x_{\mathrm{new}}^T\hat{\beta}-x_{\mathrm{new}}^T\beta^*)^2\right] = \left(1-\frac{n}{p}\right)\|\beta^*\|^2 +\sigma^2\frac{n}{p-n-1}. $$

The first term is the contribution from the part of the signal that the training row space does not capture. The second is the contribution from fitting the noise. We prove the formula, including the inverse-matrix expectation on which the noise term depends.

Lemma: If $Z\sim\chi^2_\nu$ and $\nu>2$, then $E[1/Z]=1/(\nu-2)$.

The density of $Z$ is $z^{\nu/2-1}e^{-z/2}/(2^{\nu/2}\Gamma(\nu/2))$ for $z>0$. Therefore

E[1/Z] =\frac{1}{2^{\nu/2}\Gamma(\nu/2)} \int_0^\infty z^{\nu/2-2}e^{-z/2}\,dz =\frac{\Gamma(\nu/2-1)}{2\Gamma(\nu/2)} =\frac{1}{\nu-2}.

The integral is finite precisely when $\nu/2-1>0$. In the second equality, the substitution $u=z/2$ gives the gamma integral; the last equality uses $\Gamma(a)=(a-1)\Gamma(a-1)$. This proves the lemma.

To use it, write the rows of $X$ as $x_1^T,\ldots,x_n^T$, and let $A=XX^T$. For each $i$, condition on all rows except $x_i^T$. Those other rows span a space of dimension $n-1$ with probability one. The Schur-complement formula for the inverse of a block matrix gives

(A^{-1})_{ii} = \frac{1}{x_i^T(I-P_{-i})x_i},

where $P_{-i}$ is the orthogonal projection onto the span of the other rows. The projection $I-P_{-i}$ has rank $p-n+1$. Conditional on those rows, $x_i$ is an independent standard Gaussian vector, so the denominator has a $\chi^2_{p-n+1}$ distribution. Since $p>n+1$, the lemma applies and gives $E[(A^{-1})_{ii}]=1/(p-n-1)$. Summing the diagonal entries yields

E[\operatorname{tr}(XX^T)^{-1}]=\frac{n}{p-n-1}.

Now let $P=X^T(XX^T)^{-1}X$, the orthogonal projection onto the row space of $X$. Substituting $y=X\beta^*+\varepsilon$ into the estimator gives $\hat{\beta}=P\beta^*+X^T(XX^T)^{-1}\varepsilon$. The row space has dimension $n$ and, under an isotropic Gaussian design, its distribution is unchanged by rotations. Consequently $E[P]$ is a scalar multiple of $I_p$; taking traces, $E[\operatorname{tr}(P)]=n$, so $E[P]=(n/p)I_p$. Thus the expected squared signal error is

E[\|(I_p-P)\beta^*\|^2] =\beta^{*T}(I_p-E[P])\beta^* =\left(1-\frac{n}{p}\right)\|\beta^*\|^2.

Conditional on $X$, the noise contribution has mean zero and expected squared norm $\sigma^2\operatorname{tr}((XX^T)^{-1})$. Its cross-product with the signal error has conditional expectation zero because the noise is mean zero and independent of $X$. The test-feature covariance is $I_p$, so conditional test prediction error equals squared coefficient error. Combining these facts with the trace calculation proves the theorem. $\square$

Worked Example: Two Extra Features

Return to $n=100$, $p=102$, $\beta^*=0$, and $\sigma^2=1$. The signal term in the theorem is zero. The noise term is

\sigma^2\frac{n}{p-n-1} =1\cdot\frac{100}{102-100-1} =100.

So the expected excess prediction risk is 100, despite exact training interpolation and an isotropic covariance matrix. In this particular model, a predictor that always returns zero has zero excess risk because the true regression function is zero. Interpolation has therefore made prediction worse, not better.

What Fails: A Large Enough Tail Relative to the Sample

This example is not a counterexample to conditions for benign overfitting. It shows why those conditions matter. Benign-overfitting results require suitable relationships between the sample size, the covariance spectrum, and the signal; having $p>n$ is not a substitute for those relationships. Here the covariance is $I_p$, with all eigenvalues equal, but $p$ is barely larger than $n$. There are only $p-n$ dimensions beyond the sample size, and the effective rank $\operatorname{tr}(I_p)/\|I_p\|_{\mathrm{op}}=p$ is only slightly larger than $n$. The covariance has no sufficiently large feature tail relative to the number of observations to make fitting the noise harmless.

There is no signal-alignment failure in this construction: $\beta^*=0$, so there is no signal direction to be poorly aligned with the covariance spectrum. The failure is in the quantitative dimension or covariance-tail requirement. This distinction matters. A counterexample need not violate every benign-overfitting condition; it can isolate one missing ingredient while keeping the signal as simple as possible.

The denominator $p-n-1$ also explains the sharp sensitivity near the interpolation threshold. When $p$ is just above $n+1$, the expected inverse Gram matrix is large. A design matrix can be nearly singular, and then the interpolator requires large coefficients to fit the observed noise. Those coefficients may produce substantial predictions on fresh inputs.

Worked Example: The Boundary Case Has Infinite Expected Risk

Set $p=n+1$, keep $\beta^*=0$, and suppose $\sigma^2>0$. In the diagonal-inverse calculation, the relevant chi-square degrees of freedom are $p-n+1=2$. For $Z\sim\chi^2_2$, its density is $\tfrac12 e^{-z/2}$, and

E[1/Z] =\frac12\int_0^\infty \frac{e^{-z/2}}{z}\,dz =\infty,

because the integral diverges at zero. Hence each diagonal entry of $(XX^T)^{-1}$ has infinite expectation, and the expected noise contribution to prediction risk is infinite. For almost every realized design the interpolator is still well-defined and its risk is finite; the infinite expectation reflects the contribution of designs arbitrarily close to singularity. It is not a claim that every training sample produces infinite risk.

Worked Example: More Separation Changes the Risk Scale

Compare two isotropic, zero-signal models with $n=50$ and $\sigma^2=1$. If $p=52=n+2$, the expected excess risk is

\frac{50}{52-50-1}=50.

If instead $p=100=2n$, it is

\frac{50}{100-50-1}=\frac{50}{49}\approx 1.02.

Both models interpolate, and both have isotropic features. But in the second model the feature dimension is substantially larger than the sample size, whereas in the first only two feature directions remain beyond it. The exact risk calculation makes that difference consequential rather than merely descriptive.

Common Pitfall

Wrong reasoning: “Since $p>n$, there are enough extra directions to absorb the noise, so the minimum-norm interpolator must generalize well.” The existence of null directions makes interpolation possible, but does not imply that the solution has small prediction risk.
Correction: The minimum-norm solution fits the data using directions in the row space of $X$; its coefficients depend on $(XX^T)^{-1}$. When this Gram matrix is poorly conditioned, fitting noise can require large coefficients. The prediction cost depends on the covariance and the dimension of its relevant tail relative to $n$, not just on the inequality $p>n$.
Another wrong inference: “The signal must be misaligned with a low-variance direction.” In the counterexample the signal is exactly zero. The large risk comes from noise fitting and insufficient dimension separation, not signal alignment.

Key takeaway: Minimum-norm interpolation can have large prediction risk even with isotropic features and no signal. In the Gaussian example the expected noise risk is $\sigma^2 n/(p-n-1)$, so a feature dimension barely above the sample size is not enough to guarantee benign overfitting.

Check Your Understanding

Use the model and risk calculation developed above to answer these questions.

For $\beta^*=0$, $n=20$, $p=24$, and $\sigma^2=2$, calculate the expected excess prediction risk.
Why does isotropy not prevent the risk from being large when $p$ is only slightly larger than $n$?
In the counterexample, which part of the benign-overfitting conditions is inadequate: signal alignment, covariance-tail dimension, or both? Explain.
Why does infinite expected risk at $p=n+1$ not mean the estimator is undefined for almost every realized design?
What changes in the formula when $p=2n$ and $n$ grows, with $\sigma^2$ fixed?