Uniform convergence of interpolators

The worst predictor's risk is a Gaussian max problem. Whiten and center at $w^*$: with $X=Z\Sigma^{1/2}$ and $v=\Sigma^{1/2}(w-w^*)$, the residual is $\xi-Zv$ and $L=\sigma^2+\|v\|^2$. For interpolators, KZSS split $Zv=Z_1w_1+Z_2w_2$ along the covariance split and get $\sup L-\sigma^2\overset{d}{=}\Phi=\max\{\|w_1\|^2+\|w_2\|^2:\ Z_1w_1+Z_2w_2=\xi\}$. ZKSS write the failure of the optimistic rate as positivity of $$\Phi=\sup_v\ \inf_{\|\lambda\|_2=1}\ \langle Zv,\lambda\rangle+\sqrt{\frac{n\sigma^2+n\|v\|_2^2}{1+\beta}}-\langle\xi,\lambda\rangle-\tilde F(v),$$ using $-\|a\|_2=\inf_{\|\lambda\|=1}\langle\lambda,-a\rangle$. Either way the random matrix enters through one bilinear term, and the rest is deterministic given $\xi$ (and, in KZSS, $Z_1$).

Gordon's theorem replaces the matrix by two vectors, in the direction that needs no convexity. Gordon's theorem bounds the lower tail of a min-max of $\langle u,Zw\rangle+\psi$ by that of the auxiliary problem with $\|w\|\langle G,u\rangle+\|u\|\langle H,w\rangle$ in its place, for any continuous $\psi$ on compact sets; only the upper tail needs convexity (the CGMT). The bad event is the upper tail of a sup-inf, which after negation is exactly the convexity-free half, so $K$ and $F$ can be arbitrary. Optimizing the multiplier's direction (after truncation), $\Pr(\Phi\gt t)\le2\Pr(\phi\ge t)$ with $$\phi=\sup_v\ \sqrt{\frac{n(\sigma^2+\|v\|_2^2)}{1+\beta}}-\big\|\,\|v\|_2G-\xi\big\|_2+\langle H,v\rangle-\tilde F(v),$$ and for KZSS the constraint $\|\xi-Z_1w_1-\|w_2\|G\|_2\le\langle w_2,H\rangle$. One technical point there is that $w_1$ appears only in the deterministic term, so the theorem does not apply verbatim; embedding such variables as extra coordinates scaled by $\epsilon$ and letting $\epsilon\to0$ recovers it, since Gordon's theorem uses no quantitative smoothness of $\psi$.

The auxiliary problem is controlled by a few scalar events, which is why the constant is one. On the events that $\|G\|$ and $\|\xi\|$ concentrate and $\xi$ is nearly orthogonal to $G$, $$\big\|\|v\|G-\xi\big\|_2^2\ge(1-\rho)(1-\alpha)^2n(\|v\|^2+\sigma^2),$$ so $1+\beta=[(1-\rho)(1-\alpha)^2]^{-1}$ makes the loss part of $\phi$ nonpositive for every $v$ at once, and the hypothesis $\langle H,v\rangle\le\tilde F(v)$, at $x=\Sigma^{1/2}H$, makes the rest nonpositive. In KZSS the same expansion of the squared constraint gives $\langle w_2,H\rangle^2\gtrsim n(\sigma^2+\|w_1\|^2+\|w_2\|^2)$, with the $Z_1$ block handled as in Step 4: the projection onto $H$ must account for both the noise and the norm. The proof never applies symmetrization or chaining to the class; in ZKSS's Theorem 1 the only slack is the concentration of two norms and one inner product.

The covariance split puts the width on the tail, at a relative error $\sqrt{\mathrm{rank}\,\Sigma_1/n}$. Bound $\langle w-w^*,x\rangle$ by a head term $\|w-w^*\|_{\Sigma_1}\|H_1\|_2\le\sqrt{L(w)}\,(\sqrt{\mathrm{rank}\Sigma_1}+O(\sqrt{\log}))$ plus a Gaussian term in $w^*$ plus $\sup_{u\in\Sigma_2^{1/2}K}|\langle u,H\rangle|\le W_{\Sigma_2}(K)+\mathrm{rad}\sqrt{2\log(32/\delta)}$ by Gaussian concentration, and use the sum ($+\infty$ off $K$) as $F$ in Theorem 1. Moving the head term to the left side multiplies $\sqrt L$ by $1-O(\sqrt{\mathrm{rank}\Sigma_1/n})$, negligible only when $\mathrm{rank}\Sigma_1=o(n)$; in KZSS the head cannot absorb noise because the $o(n)$-dimensional range of $Z_1$ is nearly orthogonal to $\xi$ and $G$, and the near isometry of $Z_1/\sqrt n$ on $\mathrm{span}\,\Sigma_1$ turns what it does contribute into the term $\|w_1\|^2$. As a result, the relative error rad/width is computed on $\Sigma_2$, where it is small even if spiked eigenvalues make it large on $\Sigma$. Dilations need no extra work, since the supremum over $\alpha K$ is $\alpha$ times that over $K$.

At $\hat L=0$ the noise term cancels exactly. The auxiliary constraint gives $\phi\le\frac{1+\beta}{n}\big(\sup_{u\in\Sigma_2^{1/2}K}|\langle u,H\rangle|+|\langle\Sigma_2^{1/2}w^*,H\rangle|\big)^2-\sigma^2$, and that $-\sigma^2$ cancels the Bayes risk in $L=\sigma^2+\Phi$. This cancellation is essential, since $\sigma^2+(\text{width})^2/n$ would be about $2\sigma^2$ at the min-norm radius. For a norm ball, duality gives width $B\,\mathbb E\|\Sigma_2^{1/2}H\|_*$ and radius $B\sup_{\|w\|\le1}\|w\|_{\Sigma_2}$, a relative $r_{\|\cdot\|}(\Sigma_2)^{-1/2}$ correction. With no spectral assumption, take $\Sigma_1$ to be the top $k$ directions: $k\|\Sigma_2\|_{op}\le\mathrm{Tr}\Sigma$, so the radius adds a relative error $\sqrt{\log(1/\delta)/k}$ and the split $\sqrt{k/n}$, and $k\asymp\sqrt{n\log(1/\delta)}$ balances them at $(\log(1/\delta)/n)^{1/4}$.

The minimal norm is at most $\|w^*\|$ plus the minimal norm needed to interpolate pure noise, and that problem is convex. By the triangle inequality, $\min_{Xw=Y}\|w\|\le\|w^*\|+\min_{Zw=\xi}\|\Sigma^{-1/2}w\|$; the crude additive $\|w^*\|$ later becomes the aliasing term. Now the target is an upper bound on a minimum, the direction that needs convexity, and here it holds: a norm under a linear constraint. The CGMT bounds it by the auxiliary problem $\min\{\|\Sigma^{-1/2}w\|:\ \|\xi-\|w\|_2G\|_2\le\langle H,w\rangle\}$.

One feasible point, built from a dual-norm subgradient, gives the norm bound (Lemma 8). An upper bound on a minimum needs one feasible point: the direction that fits the low-variance Gaussian best per unit norm, scaled to fit the noise. Up to $1+o(1)$, the constraint is $n(\sigma^2+\|\Sigma^{1/2}w\|_2^2)\le\langle H,\Sigma^{1/2}w\rangle^2$. Try $w=s\,Pv^*$: since $\Sigma^{1/2}P=\Sigma_2^{1/2}$ (orthogonal spans), the fit is $s\|\Sigma_2^{1/2}H\|_*$, the risk term $s\|v^*\|_{\Sigma_2}$, and the point is feasible for $$s^2\approx\sigma^2\Big(\frac{\|\Sigma_2^{1/2}H\|_*^2}{n}-\|v^*\|_{\Sigma_2}^2\Big)^{-1}.$$ Gaussian concentration puts $\|\Sigma_2^{1/2}H\|_*$ within a relative $r_{\|\cdot\|}(\Sigma_2)^{-1/2}$ of its mean, and the subtracted term is a relative $(1+\epsilon_1)^2n/R_{\|\cdot\|}(\Sigma_2)$, so $R$ compares the fit of the noise-fitting direction with the risk it adds, and $\mathrm{rank}\,\Sigma_1$ never enters because the construction avoids the large-variance directions. In $\ell_2$ everything reduces to traces: Bernstein turns the $R_{\|\cdot\|}$ term into $n\log(1/\delta)/R(\Sigma_2)$, and Gaussian Poincaré replaces $\mathbb E\|\Sigma_2^{1/2}H\|_2$ by $\sqrt{\mathrm{Tr}\Sigma_2}$.

Setting the ball radius to the norm bound gives benign overfitting. Take $B=\|w^*\|+(1+\epsilon)^{1/2}\sigma\sqrt n/\mathbb E\|\Sigma_2^{1/2}H\|_*$. The norm bound puts $\hat w$ in the ball (for consistency, its hypothesis on $\|v^*\|_{\Sigma_2}$ follows from Markov's inequality), the ball bound applies, and the width cancels, leaving $\sigma$ plus an aliasing term. In $\ell_2$, $R\le r^2$, so $n/R(\Sigma_2)\to0$ also forces the radius correction to vanish. Moving the eigenvalues within a factor $\tau$ of the top into $\Sigma_1$ moves only $o(n)$ directions and makes $r(\Sigma_2)=\omega(n)$, so Bartlett et al.'s split loses nothing for consistency.

For $\ell_1$ a single effective rank suffices, and folding the signal into the noise handles isotropic data. Every subgradient of $\|\cdot\|_\infty$ lies in the convex hull of signed basis vectors, so $\|v^*\|_{\Sigma_2}\le\max_i\sqrt{(\Sigma_2)_{ii}}$ deterministically and one rank suffices. For $\Sigma=I$ the aliasing term $\|w^*\|_1\sqrt{2\log d/n}$ diverges in the needed regime $\log d\gg n$, so rewrite $Y=X_{S^c}0+\xi'$ with $\xi'=X_Sw_S^*+\xi$, Gaussian and independent of $X_{S^c}$; the bound then has no $\|w^*\|_1$, but the target risk becomes $\sigma^2+\|w^*\|_2^2$.

The risk is flat along the path, by convex interpolation between $w^*$ and the interpolator, and tuning needs no norm bound. The optimistic bound is affine along the segment from $w^*$ to an interpolator $w_0$ and about $\sigma$ at both ends. Since $Xw_0=Y$, the point $w_a=(1-a)w^*+aw_0$ has residual $(1-a)\xi$, so $\sqrt{\hat L(w_a)}=(1-a)\sqrt{\hat L(w^*)}$, and a convex $F$ (here affine in $\|w\|$) satisfies $F(w_a)\le(1-a)F(w^*)+aF(w_0)$; the constrained ERM at the matching norm does at least as well on both terms. For the tuned estimator, KKT gives some $\lambda^*$ with $\hat w_{\lambda^*}=\arg\min\{\|w\|:\hat L(w)\le\|\xi\|_2^2/n\}$, and $w^*$ is feasible, so $\|\hat w_{\lambda^*}\|\le\|w^*\|$ with training error about $\sigma^2$, and the dilated width bound applies without any interpolator norm bound.

Sharp constants come from solving the quadratic that Theorem 1 produces. When $F$ depends on $w$ through $\|w-w^*\|_\Sigma$, the bound is a quadratic inequality in the excess risk, and its roots give two-sided bounds. For OLS, Cauchy-Schwarz gives $F\approx\sqrt d\,e$, $e=\sqrt{L-\sigma^2}$, so Theorem 1 reads $\sigma^2+e^2\le(\sqrt{\hat L}+\sqrt\gamma\,e)^2$ up to a factor $1+\epsilon$, $\epsilon\lesssim\sqrt{\log(36/\delta)/n}$, and completing the square, $$\Big(e-\frac{\sqrt{\gamma\hat L}}{1-\gamma}\Big)^2\le\frac1{1-\gamma}\Big(\frac{\hat L}{1-\gamma}-\sigma^2\Big);$$ at $\hat w_{OLS}$, $n\hat L/\sigma^2\sim\chi^2_{n-d}$ makes the right side $O(\epsilon)$, so $e^2\to\sigma^2\gamma/(1-\gamma)$, and the square root of that $O(\epsilon)$ slack gives the $n^{-1/4}$. For isotropic interpolation, split $w-w^*$ along $\mathrm{span}(w^*)$ and its complement, where only the complement sees the full $\|x\|\approx\sqrt d$; Pythagoras makes the bound at $\hat L=0$ a quadratic in $\|w\|$, and the CGMT with a feasible point in $\mathrm{span}(w^*,H)$ bounds the minimal norm.

With the local width as complexity, the bound and the ERM meet at the minimizer of one convex function. On $K_r$, Gaussian concentration makes $F\equiv W_\Sigma(K_r)+Cr\sqrt{\log(2/\delta)}$ valid, so Theorem 1 bounds $\sqrt{\hat L}$ below on each sphere $\|w-w^*\|_\Sigma=r$, while the convex half of the minimax theorem bounds $\min_K\sqrt{\hat L}$ above. They meet because $\psi(r)\approx\sqrt{\sigma^2+r^2}-W_\Sigma(K_r)/\sqrt n$ is convex: convex combinations of $K_s$ and $K_t$ lie in the localized set at the averaged radius, so the local width is concave. Convexity of $\sqrt{\hat L}$ in $w$ then keeps the ERM inside the interval of radii, with a union bound over a grid for the lower end.

The $n^{-1/4}$ slack is unavoidable for bounds that see only $\hat L$, and the first-order condition avoids it. Along $w_a=w^*+a(\hat w_{OLS}-w^*)$, Pythagoras gives $$\hat L(w_a)=\hat L(\hat w_{OLS})+(1-a)^2\|\hat w_{OLS}-w^*\|_{\hat\Sigma}^2,\qquad L(w_a)-\sigma^2=a^2\big(L(\hat w_{OLS})-\sigma^2\big),$$ so training error moves to second order and risk to first order, and $a-1\asymp n^{-1/4}$ keeps the training gap at $n^{-1/2}$, the size of $\hat L(\hat w_{OLS})$'s own fluctuation, while the risk moves by $(a^2-1)(L(\hat w_{OLS})-\sigma^2)\asymp n^{-1/4}$, since $L(\hat w_{OLS})-\sigma^2\to\sigma^2\gamma/(1-\gamma)\gt0$. The ERM's fast rate also uses the first-order condition. KKT gives $\|\hat w-w^*\|_{\hat\Sigma}^2\le\frac1n\langle\xi,X(\hat w-w^*)\rangle\le\frac{\|\xi\|}{n}F(\hat w)$, since $Z^\top\xi$ is Gaussian given $\xi$; the noiseless Theorem 1 lifts the empirical norm to the population one, and with $F=\sqrt p\,\|w-w^*\|_\Sigma$ this solves to $e^2\lesssim\sigma^2p/n$. This fails in the proportional regime, where the two norms differ by more than $1+o(1)$.

Consequences and limits. Uniform convergence explains interpolation once it is localized (to interpolators, or by training error) with leading constant one; arguments that lose a constant cannot show consistency. Benign overfitting is then a statement about norms: under the $\ell_2$ conditions every interpolator within $(1+o(1))$ of the norm bound is consistent, and the spectrum acts only through the split, with a low-rank head learned as in classical regression, no aliasing ($\|w^*\|^2\mathrm{Tr}\Sigma_2=o(n)$), and $R(\Sigma_2)=\omega(n)$ so that fitting the noise adds negligible risk (at $R(\Sigma_2)\asymp n$ the bound is $c\sigma^2$ with $c\gt1$). For basis pursuit KZSS give the first consistency results with Gaussian covariates and $\sigma\gt0$, at slow rates. Limits: Gaussian, well-specified data are essential to Gordon's theorem; rates are somewhat worse than Bartlett et al.'s ($\sqrt{\mathrm{rank}\Sigma_1/n}$ for $\mathrm{rank}\Sigma_1/n$, plus an $r(\Sigma_2)^{-1/2}$ term); the interpolator's norm is a separate input; no lower bound beyond $L\ge\sigma^2$ is proved for interpolators; the local-width results need convex $K$.