MDL1 — How Deep Learning Changed Statistical Learning Theory

1. For a fixed h, \Pr[|\hat R_n(h)-R(h)|>t]\le2e^{-2nt^2}. The event that some h\in\mathcal H has a gap larger than t is the union over h of these events, so its probability is at most 2|\mathcal H|e^{-2nt^2}. Setting this equal to \delta and solving for t gives t=\sqrt{\ln(2|\mathcal H|/\delta)/(2n)}.

2. \ln|\mathcal H|\le32W\ln2\approx2.22\times10^7, so the bound is \sqrt{(2.22\times10^7+\ln 40)/10^5}\approx\sqrt{222}\approx14.9. The gap cannot exceed 1, so a bound of 14.9 says nothing. The VC scale W\ln W\approx1.4\times10^7 is far larger than n=5\times10^4, so a VC bound is vacuous too. (This scale is a generic upper bound; it does not prove that this architecture has so large a VC dimension. But if the true VC dimension is at least n, then the class can label some set of n inputs in every possible way, and the no-free-lunch argument of 3.1.1 applies: for inputs drawn uniformly from that set, a training sample of size n misses an expected fraction (1-1/n)^n\approx e^{-1} of them, and some labelling of the missed inputs makes any learner wrong on half of them, so the expected error is at least \tfrac12(1-1/n)^n\approx0.18.)

3. Take P' to be CIFAR-10 images with labels drawn uniformly from the 10 classes, independently of the image. By assumption SGD then reaches an h\in\mathcal H with \hat R_n(h)=0. The label of a fresh example is independent of its image, so any classifier is right with probability 1/10: R(h)=0.9, and \mathrm{gap}(h)=0.9 with high probability. A bound that depends only on \mathcal H, n and \delta must hold for P' in particular, so \epsilon(n,\delta)\ge0.9-o(1). The same bound then applies, and is vacuous, on the real labels as well. (Zhang et al.’s experiment is on one fixed image collection; it motivates the assumption that fitting succeeds on random draws, but does not prove it.) A vacuous bound is not wrong, but it cannot be the explanation. 1.2.1 asks which explanations survive.

1. Ruled out:

• any explanation in which the class of reachable functions is small enough for a bound that holds for every distribution to be tight. This covers the VC dimension, and also the Rademacher complexity, which measures how well functions in the class can fit random \pm1 labels on the training inputs: fitting random labels pushes it to its maximum, as the paper notes in §2.2;
• explicit regularization as the main cause, since the networks generalize nearly as well without it;
• “SGD cannot find memorizing solutions”, since it finds them, only a constant factor more slowly.

Not ruled out:

• data-dependent accounts, in which what is learned depends on structure in the true labels: a preference of the training procedure for low-norm, flat or simple solutions when such solutions exist, an implicit bias of training;
• bounds evaluated on the particular function found rather than on the whole class, in terms of its weight norms, its classification margin, how compressible it is, or its probability under a prior (PAC-Bayes, §6);
• a prior over functions whose support is everything but whose mass is on structured functions.

This is what the random-labels experiment alone leaves standing; §6 and §8 constrain the second item further.

The slower fit on random labels is a hint that some simplicity ordering is at work. Such a “soft” bias (the class can fit anything, but training prefers some fits) predicts things a hard restriction on the class does not:

• the same model at the same n generalizes differently depending on the labels;
• random labels take longer to fit and end at larger norm or complexity;
• adding parameters need not hurt, and can help (double descent, 1.3–1.6), whereas a bound based on the size of the class only gets worse as the class grows;
• a bound in terms of the prior mass or description length of the found function can be non-vacuous where class-size bounds are not.

2. It counts against the constraint reading used as an explanation: the networks generalize without the constraint, and with it they still fit random labels, so the constrained class is still far too large for a class-size bound. The prior reading survives if the prior is soft and implemented implicitly, by architecture, initialization and SGD. The spectral-filter reading also survives as implicit regularization: gradient descent fits the directions the data determine strongly first, stopping early leaves the others unfit, and from zero initialization gradient descent converges to the smallest-norm fit (4.3).

1. \sigma^2\frac{p}{n-p-1}=\sigma^2\frac{p/n}{1-p/n-1/n}\to\sigma^2\frac{\gamma}{1-\gamma}. For the trace formula, \hat\beta-\beta=(X^\top X)^{-1}X^\top\varepsilon, so at fixed X, \mathbb E[\|\hat\beta-\beta\|^2\mid X]=\sigma^2\mathrm{Tr}\big[(X^\top X)^{-1}X^\top X(X^\top X)^{-1}\big]=\sigma^2\mathrm{Tr}(X^\top X)^{-1}, and \mathrm{Tr}(X^\top X)^{-1}=\frac1n\sum_i1/\lambda_i. By the Marchenko–Pastur law the eigenvalues fill [(1-\sqrt\gamma)^2,(1+\sqrt\gamma)^2], and as \gamma\to1 the lower edge tends to 0, so the smallest eigenvalues, the directions in which the data barely determine \beta, blow up the sum. Consistently, \frac1p\mathrm{Tr}(X^\top X/n)^{-1}\to\frac1{1-\gamma}.

2. Zero: \mathbb E[\hat\beta\mid X]=(X^\top X)^{-1}X^\top X\beta=\beta whenever X^\top X is invertible (2.2). Below the threshold the whole risk is variance, the fluctuation of \hat\beta around \beta caused by the noise.

1. X\hat\beta=XX^\top(XX^\top)^{-1}y=y, so \hat\beta interpolates. Any other interpolant is \hat\beta+w with Xw=0. Now \hat\beta=X^\top(XX^\top)^{-1}y is a linear combination of the rows of X, while Xw=0 says w is orthogonal to every row, so \hat\beta\perp w and \|\hat\beta+w\|^2=\|\hat\beta\|^2+\|w\|^2\ge\|\hat\beta\|^2.

2. P=X^\top(XX^\top)^{-1}X is symmetric and satisfies P^2=P, so it is an orthogonal projection; its range lies in the row space (it is X^\top times something) and PX^\top=X^\top, so it fixes the row space and is the projection onto it. Then \hat\beta=X^+(X\beta+\varepsilon)=P\beta+X^+\varepsilon, so \hat\beta-\beta=-(I-P)\beta+X^+\varepsilon. The first term is orthogonal to the row space and the second lies in it, so the cross term vanishes. Here “bias squared” means the squared bias at fixed X, then averaged over X, rather than the bias after averaging over X. Finally \mathbb E[\|X^+\varepsilon\|^2]=\sigma^2\mathrm{Tr}(X^{+\top}X^+) and X^{+\top}X^+=(XX^\top)^{-1}XX^\top(XX^\top)^{-1}=(XX^\top)^{-1}.

3. For orthogonal O, XO has the same distribution as X (each row is a rotated standard Gaussian vector, which is again standard Gaussian), and its row-space projection is O^\top PO. So \mathbb E[P]=O^\top(\mathbb E[P])O for all O, which forces \mathbb E[P]=cI. Taking traces, \mathrm{Tr}\,P=n (a projection onto an n-dimensional space) gives c=n/p. For any fixed \beta, \mathbb E[\|(I-P)\beta\|^2]=\beta^\top(I-\mathbb E[P])\beta=r^2(1-n/p). The interpolant only sees the component of \beta along the training inputs, a random n-dimensional subspace, and misses the rest.

4. For p>n+1, the quoted fact with (n,p)\to(p,n) gives \mathbb E[(XX^\top)^{-1}]=I_n/(p-n-1), so the variance is \sigma^2n/(p-n-1)\to\sigma^2/(\gamma-1). (Hastie et al. state this branch as part of their Theorem 1. For independent Gaussian inputs it is a two-line consequence of the same fact.)

5.

\mathcal R(\gamma)=\begin{cases}\sigma^2\dfrac{\gamma}{1-\gamma},&\gamma<1,\\[2mm] r^2\Big(1-\dfrac1\gamma\Big)+\dfrac{\sigma^2}{\gamma-1},&\gamma>1.\end{cases}

The risk starts at 0, rises, and diverges at \gamma=1 from both sides; the divergence is entirely variance. Past the threshold, the bias grows from 0 toward r^2 while the variance falls from \infty toward 0. As \gamma\to\infty the risk tends to r^2, the risk of predicting zero: the training inputs span a vanishing fraction of the directions of \beta, and the noise is spread over so many directions that it does no harm. The “second descent” is the variance falling faster than the bias rises.

1. \frac{d}{d\gamma}\big[r^2(1-1/\gamma)+\sigma^2/(\gamma-1)\big]=\frac{r^2}{\gamma^2}-\frac{\sigma^2}{(\gamma-1)^2}. This vanishes when \frac{\gamma-1}{\gamma}=\frac\sigma r, i.e. \gamma^\star=\frac{1}{1-\sigma/r}=\frac{r}{r-\sigma}, which requires r>\sigma. There 1-1/\gamma^\star=\sigma/r and \gamma^\star-1=\sigma/(r-\sigma), so

\mathcal R(\gamma^\star)=r\sigma+\sigma(r-\sigma)=2r\sigma-\sigma^2=r^2-(r-\sigma)^2<r^2 .

The derivative is negative before \gamma^\star and positive after, and \mathcal R\to r^2 from below as \gamma\to\infty. So for signal-to-noise ratio above one, the interpolant beats predicting zero over a whole range of \gamma. If r\le\sigma, then \frac{\gamma-1}{\gamma}<1\le\frac\sigma r, the derivative is negative everywhere on (1,\infty), and the risk falls toward r^2 without crossing it: the interpolant never beats predicting zero.

In this model the global minimum over all \gamma is still at \gamma\to0, because r^2 is held fixed as p grows, so each added feature carries less signal. Whether adding features can win globally depends on whether they carry new signal. Hastie et al. (§5) study a variant in which the true function depends on features the model leaves out, so that adding features brings in signal the model was missing; there, for signal-to-noise ratio above one, the global minimum can lie at \gamma>1.

2. With \tau^2=r^2/p: \lambda=\frac{\sigma^2}{n\tau^2}=\frac{\sigma^2p}{nr^2}=\frac{\sigma^2\gamma}{r^2}=\lambda^*. By 4.1.1, \hat\beta_{\lambda^*} is the posterior mean, which minimizes \mathbb E[\|b-\beta\|^2] over all estimators b when \beta is drawn from that prior. (This is also 2.5.3’s best common penalty n\lambda=\sigma^2/\tau^2.)

3. (a) Both estimators are unchanged by rotating inputs and coefficients together, and the distribution of X is rotation-invariant, so each one’s risk at fixed \beta depends only on \|\beta\|. More precisely, for either estimator the risk at fixed \beta has the form A\|\beta\|^2+B: by the same symmetry the squared-bias matrix is a multiple of I, and the noise term does not involve \beta. So the risk averaged over any prior with \mathbb E[\|\beta\|^2]=r^2 equals the risk at any single vector of norm r, already at finite p (whenever the risks are finite). \hat\beta_{\lambda^*} has the smallest prior-averaged risk of any estimator, so it is at least as good as the minimum-norm interpolant at every fixed \beta of norm r. (This compares the two estimators at fixed norm; it does not make \hat\beta_{\lambda^*} the best of all estimators for a \beta drawn uniformly from the sphere.)

(b) An estimator given n+1 samples can ignore the last one, so the best estimator with n+1 samples has prior-averaged risk at most that of the best estimator with n samples. More data never hurts the posterior mean. The limiting curve depends on \gamma alone, and at fixed p increasing n decreases \gamma, so the risk of \hat\beta_{\lambda^*} is non-decreasing in \gamma. There is no peak.

The double-descent peak is therefore a property of the minimum-norm estimator, a variance divergence at p\approx n that properly tuned regularization removes, and not a property of the problem.

What a correct sketch shows. For both signal-to-noise ratios, the curve starts at 0, rises as \sigma^2\gamma/(1-\gamma), and has a vertical asymptote at \gamma=1, entirely from variance; the bias is zero for \gamma<1.

• For r^2/\sigma^2=5 (r\approx2.24\sigma): past the peak the curve falls through r^2, has its minimum at \gamma=r/(r-\sigma)\approx1.81 with value 2r\sigma-\sigma^2\approx3.47\sigma^2<r^2=5\sigma^2, and then climbs back to r^2 from below.
• For r^2/\sigma^2=0.5: past the peak the curve falls toward r^2 from above and never crosses it.

The risk of \hat\beta_{\lambda^*} is a smooth, non-decreasing curve that lies below that of the minimum-norm interpolant everywhere and tends to r^2 as \gamma\to\infty.

Train several networks of the same size on independent draws of the training data (or with different seeds and different label noise) near the apparent peak. Split the test loss into the loss of the averaged prediction (bias plus noise) and the spread of the individual predictions around it (variance), as in 2.4. If the peak is a variance divergence, the spread peaks there while the loss of the averaged prediction does not. Weight decay tuned separately at each size should then flatten the peak. A second check is the eigenvalues of whatever matrix plays the role of X^\top X/n for the network, its feature covariance: a variance divergence of the kind in 1.3 requires eigenvalues near zero.

1. Take x\sim\mathrm{Unif}[0,1] and y=f^*(x)+\varepsilon with \varepsilon\sim\mathcal N(0,\sigma^2), under squared loss. Let the class be f^* together with every “patched” function f_T, where T is a finite set of labelled points with distinct inputs: f_T(x)=y if (x,y)\in T and f_T(x)=f^*(x) otherwise. Each f_T differs from f^* on a set of measure zero, so R(f_T)=R(f^*)=\sigma^2 and every member of the class is a population minimizer. ERM returns f_S, which has zero training loss because the x_i are almost surely distinct. Hence

\mathcal E_n=0,\qquad \mathrm{gap}_n=\sigma^2 .

Memorizing costs nothing here because the memorized inputs never recur. This is a caricature of benign overfitting; 5.2–5.3 have a real version.

2. Take the rule that ignores the data and outputs a fixed \theta_0 with R(\theta_0)>R(\theta^*). Since \theta_0 does not depend on S, \mathbb E\hat R_n(\theta_0)=R(\theta_0), so \mathbb E\,\mathrm{gap}_n=0. Meanwhile \mathcal E_n=R(\theta_0)-R(\theta^*)>0 for every S. A small gap means the training loss is an honest estimate of the test loss, not that the model is good.

3. Write

\mathcal E_n=\underbrace{R(\hat\theta_n)-\hat R_n(\hat\theta_n)}_{\mathrm{gap}_n} +\underbrace{\hat R_n(\hat\theta_n)-\hat R_n(\theta^*)}_{\le 0\ \text{(ERM)}} +\underbrace{\hat R_n(\theta^*)-R(\theta^*)}_{\text{mean }0}.

The middle term is non-positive because \hat\theta_n minimizes \hat R_n. The last has mean zero because \theta^* does not depend on S. Taking expectations gives \mathbb E\,\mathcal E_n\le\mathbb E\,\mathrm{gap}_n. Bounding the first and third terms by \sup_\theta|R-\hat R_n| and dropping the middle one gives \mathcal E_n\le2\sup_\theta|R(\theta)-\hat R_n(\theta)|. This is the route every capacity bound takes (§3, 1.1): control the worst gap over the whole class, and the excess risk follows.

4. Because \hat\theta_n is independent of the held-out data, the held-out mean loss is unbiased for R(\hat\theta_n), with standard error \mathrm{sd}(\ell)/\sqrt m. Subtracting the training loss estimates the gap. The excess risk also needs R(\theta^*), the best achievable loss in the class, which a held-out loss alone does not identify without further assumptions or knowledge. You can measure differences of excess risk between two fitted predictors in the same model class, since R(\theta^*) cancels. Different classes can have different optimum risks. More generally, a held-out set estimates the population loss of whatever predictor you evaluate on it, whether one network or an ensemble.

A sanity example with both quantities nonzero: for constant predictors on y\sim\mathcal N(\mu,\sigma^2), \hat\theta_n=\bar y, \mathbb E\,\mathcal E_n=\sigma^2/n and \mathbb E\,\mathrm{gap}_n=2\sigma^2/n.

1. \nabla_b\hat R_n=-\frac2nX^\top(y-Xb)=0 gives the normal equations X^\top Xb=X^\top y. Since X^\top X is invertible, \hat\beta=(X^\top X)^{-1}X^\top y. Substituting y=X\beta+\varepsilon,

\hat\beta=\beta+(X^\top X)^{-1}X^\top\varepsilon,

so \mathbb E\hat\beta=\beta, and

\mathrm{Cov}\,\hat\beta=(X^\top X)^{-1}X^\top(\sigma^2I)X(X^\top X)^{-1}=\sigma^2(X^\top X)^{-1}.

2. R(b)=\mathbb E(x^\top\beta+\varepsilon-x^\top b)^2=\sigma^2+(\beta-b)^\top\mathbb E[xx^\top]\,(\beta-b)=\sigma^2+\|b-\beta\|^2, since \varepsilon is independent of x and \mathbb E xx^\top=I. So \theta^*=\beta, R(\theta^*)=\sigma^2 and \mathcal E_n=\|\hat\beta-\beta\|^2. Then

\mathbb E\|\hat\beta-\beta\|^2=\mathrm{Tr}\,\mathrm{Cov}\,\hat\beta=\sigma^2\,\mathrm{Tr}\,(X^\top X)^{-1}.

3. The residual is y-X\hat\beta=(I-P_X)y=(I-P_X)\varepsilon, because (I-P_X)X=0. So \mathbb E\|y-X\hat\beta\|^2=\sigma^2\,\mathrm{Tr}(I-P_X)=\sigma^2(n-p), and dividing by n gives \sigma^2(n-p)/n. The fit absorbs the noise along p directions, so the training loss underestimates \sigma^2.

1. Proportional to I. For any orthogonal O\in\mathbb R^{p\times p}, XO has the same law as X, and ((XO)^\top XO)^{-1}=O^\top(X^\top X)^{-1}O. So M=\mathbb E(X^\top X)^{-1} satisfies M=O^\top MO for all O, which forces M=cI.

The constant. By the Schur complement, [(X^\top X)^{-1}]_{11}=1/\big(x_{\cdot1}^\top(I-P_{-1})x_{\cdot1}\big). Conditional on the other columns, I-P_{-1} is an orthogonal projection of rank n-p+1, and it is independent of x_{\cdot1}\sim\mathcal N(0,I_n). So the denominator is \chi^2_{n-p+1}. Next, \mathbb E[1/\chi^2_k]=\frac{\Gamma(k/2-1)}{2\Gamma(k/2)}=\frac1{k-2} for k>2, which gives c=1/(n-p-1). Combining with 2.2.2,

\mathbb E\,\mathcal E_n=\sigma^2\,\mathrm{Tr}\,\mathbb E(X^\top X)^{-1}=\frac{\sigma^2p}{n-p-1}.

2. \mathbb E R(\hat\beta)=\sigma^2+\sigma^2p/(n-p-1)=\sigma^2\frac{n-1}{n-p-1}, and by 2.2.3, \mathbb E\hat R_n(\hat\beta)=\sigma^2\frac{n-p}{n}. So

\mathbb E\,\mathrm{gap}_n=\sigma^2\Big[\frac{n-1}{n-p-1}-\frac{n-p}{n}\Big] \approx\sigma^2\Big[\Big(1+\frac pn\Big)-\Big(1-\frac pn\Big)\Big]=\frac{2\sigma^2p}{n}.

The test loss overestimates \sigma^2 by about \sigma^2p/n (the excess risk), and the training loss underestimates it by the same amount, because the fit has absorbed the noise along p directions. The gap counts both. This is the factor of two between “optimism” and “excess risk” that 7.2 derives in general (TIC vs \tfrac1{2n}\mathrm{Tr}(H^{-1}C)).

3. Each of the p coefficients is estimated with variance \approx\sigma^2/n, which is “parameter counting”. The exact correction n/(n-p-1) diverges as p\to n-1. The cause is the smallest eigenvalues of X^\top X/n. When p/n\to\gamma<1, its spectrum fills [(1-\sqrt\gamma)^2,(1+\sqrt\gamma)^2] (Marchenko–Pastur, quoted), and \mathrm{Tr}(X^\top X)^{-1}=\frac1n\sum_i 1/\lambda_i(X^\top X/n) is dominated by the eigenvalues near the lower edge, which tends to 0 as \gamma\to1. Noise along nearly degenerate directions of the design is amplified without limit. The keystone exercises (1.3) pick this up.

(All of these formulas are checked by Monte Carlo in checks/wb2a_check.py.)

1. Write \hat f_S(x)-y=(\hat f_S-\mathbb E\hat f_S)+(\mathbb E\hat f_S-f)+(f-y) and square. The cross terms vanish in expectation. (\hat f_S-\mathbb E\hat f_S) has mean zero over S. (f-y)=-\varepsilon has mean zero and is independent of S. (\mathbb E\hat f_S-f) is a constant. What remains is variance, plus squared bias, plus \sigma^2(x).

2. The average of K independent copies has the same mean, hence the same bias, and variance \mathrm{Var}_S\hat f_S(x)/K. The noise term is untouched. (Real bagging resamples a single dataset, so the copies are correlated and the reduction is smaller.)

3. Expand f_\theta-y=(f_\theta-\bar f)+(\bar f-y) and take \mathbb E_{\theta\sim q} with x,y fixed. The cross term is 2(\bar f-y)\,\mathbb E_q[f_\theta-\bar f]=0. With q a posterior, the left side is the Gibbs loss at (x,y) and (\bar f-y)^2 is the Bayes-ensemble loss. Averaging over (x,y):

\text{Gibbs error}=\text{Bayes-ensemble error}+\mathbb E_x\,\mathrm{Var}_{\text{post}}f_\theta(x)\ \ge\ \text{Bayes-ensemble error},

with equality iff the posterior predictors agree for almost every input under the test distribution. For squared loss, ensembling never hurts a posterior draw. 7.6 finds that in the regular case the excess parts differ by a factor of two (p/n vs p/2n).

4. No: the 0–1 loss does not decompose additively. Take y=1 deterministically and predict \mathbf 1[\hat g_S(x)>0], where \hat g_S(x)\sim\mathcal N(\mu,v) with \mu<0, so the average prediction is on the wrong side. The error is \Pr[\hat g_S\le0]=\Phi(-\mu/\sqrt v), which decreases toward \tfrac12 as v grows. When the bias has the wrong sign, variance helps. “Variance always hurts” is a fact about squared loss.

1. \mathbb E\hat\beta_\lambda=(X^\top X+aI)^{-1}X^\top X\beta, so in the V basis coordinate k is \frac{s_k^2}{s_k^2+a}\beta_k and the bias is \big(\frac{s_k^2}{s_k^2+a}-1\big)\beta_k=-\frac{a}{s_k^2+a}\beta_k. The covariance is \sigma^2(X^\top X+aI)^{-1}X^\top X(X^\top X+aI)^{-1}=V\,\mathrm{diag}\!\big(\sigma^2s_k^2/(s_k^2+a)^2\big)V^\top, which is diagonal in V, so the coordinates are uncorrelated. Summing squared bias and variance over k gives the total.

2. At a=0, \mathrm{var}_k=\sigma^2/s_k^2, so the weakest directions (small s_k) dominate. That is the same \mathrm{Tr}(X^\top X)^{-1} as in 2.2.2. Write f_k(a)=\frac{a^2\beta_k^2+\sigma^2s_k^2}{(s_k^2+a)^2}. Then

f_k'(a)=\frac{2a\beta_k^2(s_k^2+a)-2(a^2\beta_k^2+\sigma^2s_k^2)}{(s_k^2+a)^3}=\frac{2s_k^2(a\beta_k^2-\sigma^2)}{(s_k^2+a)^3}.

At a=0 this is -2\sigma^2/s_k^4<0 for every k, so a small amount of ridge lowers the total error, for every \beta. This is the observation of Hoerl and Kennard (1970).

3. By the factored derivative, f_k decreases for a<\sigma^2/\beta_k^2 and increases after, so a_k^*=\sigma^2/\beta_k^2, which does not involve s_k. Substituting,

f_k(a_k^*)=\frac{\sigma^2(\sigma^2+s_k^2\beta_k^2)/\beta_k^2}{(s_k^2\beta_k^2+\sigma^2)^2/\beta_k^4}=\frac{\sigma^2\beta_k^2}{s_k^2\beta_k^2+\sigma^2}=\Big(\frac{s_k^2}{\sigma^2}+\frac1{\beta_k^2}\Big)^{-1}.

If \beta_k=0, the optimum is the limit a_k\to\infty, with zero error. This has the form of a posterior variance: data precision plus prior precision. If \beta\sim\mathcal N(0,\tau^2I), then \mathbb E\beta_k^2=\tau^2, and \mathbb E_\beta f_k(a)=\frac{a^2\tau^2+\sigma^2s_k^2}{(s_k^2+a)^2} is minimized at a=\sigma^2/\tau^2 for every k at once. So the best common penalty is n\lambda=\sigma^2/\tau^2. 4.1 gets the same value as the MAP prior, and 1.5.2 as the optimal \lambda^*=\sigma^2\gamma/r^2 for random designs, where \gamma=p/n, r^2=\|\beta\|^2 and \tau^2=r^2/p.

4. With the thin SVD X=U\,\mathrm{diag}(s_k)V^\top, S_\lambda=U\,\mathrm{diag}\big(s_k^2/(s_k^2+a)\big)U^\top, so \mathrm{Tr}\,S_\lambda=\sum_k s_k^2/(s_k^2+a)\in[0,p]. Let \mu=X\beta. Then

\|y'-\hat y\|^2=\|\varepsilon'\|^2+\|\mu-\hat y\|^2+2\langle\varepsilon',\mu-\hat y\rangle,\qquad \|y-\hat y\|^2=\|\varepsilon\|^2+\|\mu-\hat y\|^2+2\langle\varepsilon,\mu-\hat y\rangle .

The first cross term has mean 0 because \varepsilon' is independent of \hat y. In the second, \mu-\hat y=(I-S_\lambda)\mu-S_\lambda\varepsilon, so \mathbb E\langle\varepsilon,\mu-\hat y\rangle=-\sigma^2\,\mathrm{Tr}\,S_\lambda. The difference is 2\sigma^2\,\mathrm{Tr}\,S_\lambda, and dividing by n gives 2\sigma^2\mathrm{df}(\lambda)/n. At \lambda=0, \mathrm{df}=p, which has the same leading 2\sigma^2p/n value as 2.3. Here it is exact for new labels at the training inputs; 2.3 evaluates fresh random inputs, so its finite-sample gap differs. Ridge replaces “count the parameters” with “count the directions the data can resolve against the penalty.”

1. Under the uniform prior, the values \{f(x)\}_{x\in\mathcal X} are i.i.d. fair coins. Condition on the training inputs and their labels. The values \{f(x)\}_{x\in U} are still i.i.d. fair coins, independent of everything the learner sees. The hypothesis h is a function of the training labels and of independent internal randomness, so h is independent of f|_U. Hence \Pr[h(x)\ne f(x)]=\tfrac12 for each x\in U, and the average over U has expectation \tfrac12.

2. By 1, \sum_f\mathrm{err}_{\mathrm{OTS}}(A,f)=2^N\cdot\tfrac12=\sum_f\mathrm{err}_{\mathrm{OTS}}(B,f), so the difference sums to zero. Whatever advantage A has over B on one set of targets, it gives back exactly on the complement. No learner is better than another “in general”, even the learner that predicts the opposite of the majority label.

3. Fix h with \mathrm{err}_D(h)>\epsilon. Each i.i.d. sample is consistent with it with probability below 1-\epsilon, so \Pr[h\text{ consistent with all }n]\le(1-\epsilon)^n\le e^{-n\epsilon}. There are at most M such h, so by the union bound \Pr[\exists\text{ consistent }h\text{ with }\mathrm{err}_D(h)>\epsilon]\le Me^{-n\epsilon}. Equivalently, with probability at least 1-\delta, every consistent h has \mathrm{err}_D(h)\le(\ln M+\ln(1/\delta))/n. For programs of at most b bits, M<2^{b+1}, so n\approx(b\ln2+\ln(1/\delta))/\epsilon samples suffice. The cost of learning scales with the description length of the target (Occam). For the class of all functions, M=2^N, and the bound needs n\gtrsim N\ln2/\epsilon: you must see a constant fraction of the domain, which is NFL again.

4. It entered at “f|_U is independent of the labels on the training set”. Any prior under which seen labels are informative about unseen ones escapes NFL. Examples:

• a simplicity (Solomonoff) prior, which favours the shortest consistent program (MDL3);
• a smoothness prior, which favours kernel or nearest-neighbour methods;
• a symmetry prior, which favours equivariant architectures such as CNNs (MDL2).

The question “why does deep learning generalize?” becomes: which prior over targets do the architecture and the optimizer implement, and why does it match the world?

1. Let the breakpoints be 0=t_0<t_1<\dots<t_{K-1}<1, with slopes a_0,\dots,a_{K-1} on the pieces. Then on [0,1]

g(x)=g(0)+a_0\,\mathrm{ReLU}(x-t_0)+\sum_{k=1}^{K-1}(a_k-a_{k-1})\,\mathrm{ReLU}(x-t_k),

since each ReLU switches on the slope change at its breakpoint. That is K units plus a bias.

2. On a knot interval of length h=1/K, the interpolation error is e(x)=\tfrac12f''(\xi)(x-a)(x-b), and |(x-a)(x-b)|\le h^2/4. With |f''|\le\omega^2 this gives |e|\le\omega^2h^2/8=\omega^2/(8K^2). Setting \omega^2/(8K^2)\le\epsilon gives K\ge\omega/\sqrt{8\epsilon}, so m=\lceil\omega/\sqrt{8\epsilon}\rceil units suffice. The count is linear in the frequency.

3. Each unit \mathrm{ReLU}(wx+b) has at most one breakpoint, so the sum has at most m breakpoints and at most m+1 affine pieces. The extrema of \sin\omega x in [0,1] are at x_j=(\pi/2+j\pi)/\omega, with values (-1)^j, and there are J=\lfloor\omega/\pi-\tfrac12\rfloor+1 of them. If \sup|g-\sin\omega x|<1, then g(x_j) has sign (-1)^j. An affine function that is positive at x_j and x_{j+2} is positive at x_{j+1}, which lies between them. So a single piece contains at most two consecutive extrema, and J\le2(m+1), i.e. m\ge J/2-1\approx\omega/(2\pi). Together with 2, the number of units needed is \Theta(\omega) at fixed accuracy.

4. On [0,\tfrac12], t(x)=2x is an increasing bijection onto [0,1]; on [\tfrac12,1], t(x)=2-2x is a decreasing bijection onto [0,1]. So t^{\circ k}=t^{\circ(k-1)}\circ t consists of two reparametrized copies of t^{\circ(k-1)}, one of them reversed, and by induction it has 2\cdot2^{k-1}=2^k pieces. Each layer uses 2 units, so the depth-k network has 2k units. By 3, one hidden layer needs m+1\ge2^k units. Depth buys pieces exponentially.

5. UAT does not tell you:

• how many units are needed. For generic Lipschitz targets in d dimensions the count grows like \epsilon^{-d}.
• whether gradient descent finds the approximant.
• how many samples identify it, or which of the many interpolants of the data training selects.

Polynomials (Weierstrass) and lookup tables are universal approximators too. Expressivity is cheap, so it cannot be what distinguishes networks. UAT rules out “the net cannot represent the target” and nothing else.

1. One point x is shattered: t\le x labels it 1 and t>x labels it 0. For two points x_1<x_2, the labelling (1,0) needs t\le x_1 and t>x_2, which is impossible. So d_{\mathrm{VC}}=1. On m distinct sorted points the achievable labellings are 0\cdots01\cdots1, fixed by the number k\in\{0,\dots,m\} of zeros. So \Pi(m)=m+1=\binom m0+\binom m1, and Sauer–Shelah holds with equality.

2. Two points x_1<x_2: a long interval gives (1,1), a short interval around one point gives (1,0) or (0,1), and an interval away from both gives (0,0). Three points x_1<x_2<x_3: an interval containing x_1 and x_3 contains x_2, so (1,0,1) is impossible, and d_{\mathrm{VC}}=2. On m sorted points the 1s must form one contiguous block. There is the empty block, plus one block for each choice of first and last point i\le j, which gives

\Pi(m)=1+\frac{m(m+1)}2=\binom m0+\binom m1+\binom m2 ,

again equal to the Sauer–Shelah bound.

3. Lower bound. Write the labels of 0,e_1,\dots,e_d as y_0,\dots,y_d and let s_i=2y_i-1\in\{\pm1\}. Take b=s_0/2 and w_i=s_i-s_0/2. Then w^\top0+b=s_0/2 and w^\top e_i+b=s_i. Each has the sign s_i and none is zero, so every labelling is produced and d_{\mathrm{VC}}\ge d+1.

Upper bound. Take any d+2 points x_1,\dots,x_{d+2}. The system \sum_i\alpha_ix_i=0, \sum_i\alpha_i=0 has d+1 equations and d+2 unknowns, so it has a solution \alpha\ne0. Because the \alpha_i sum to zero, some are positive and some negative. Let I=\{i:\alpha_i>0\}, let J be the rest, and let s=\sum_{i\in I}\alpha_i>0. Then

p=\sum_{i\in I}\frac{\lambda_i}{s}x_i=\sum_{i\in J}\frac{-\lambda_i}{s}x_i

is a convex combination of the I-points and also of the J-points (Radon’s theorem). Label I by 1 and J by 0. A halfspace producing this labelling would have the convex set \{w^\top x+b\ge0\} contain all I-points, hence p. The convex set \{w^\top x+b<0\} would contain all J-points, hence p too. That is a contradiction. So d_{\mathrm{VC}}=d+1, which for this class equals the number of parameters.

4. Write c_j=1-y_j\in\{0,1\}. Then

\frac{\omega x_i}{\pi}=2^{-i}\Big(1+\sum_{j=1}^mc_j2^j\Big)=\underbrace{\sum_{j>i}c_j2^{j-i}}_{\text{even integer}}+c_i+\theta_i,\qquad \theta_i=\sum_{j<i}c_j2^{j-i}+2^{-i}.

The even integer shifts \omega x_i by a multiple of 2\pi and does not change the sine. Also 0<\theta_i\le\sum_{k=1}^{i-1}2^{-k}+2^{-i}=1-2^{-i}<1. So \omega x_i\equiv\pi(c_i+\theta_i)\pmod{2\pi} with \theta_i\in(0,1), and \sin(\omega x_i)>0 iff c_i=0 iff y_i=1. Every labelling of every finite set \{2^{-1},\dots,2^{-m}\} is produced, so d_{\mathrm{VC}}=\infty. No distribution-free VC bound applies to this one-parameter class.

The number of parameters is neither an upper bound on the VC dimension (this example; ReLU networks with W weights in L layers, whose VC dimension can be of order WL\log(W/L)) nor a lower bound (redundant parameters, as in \mathbf 1[(w_1+w_2)x\ge0], add nothing).

If \omega is a 32-bit float, the class has at most 2^{32} members. Shattering m points needs 2^m distinct functions, so d_{\mathrm{VC}}\le32, and the finite-class bound applies with \ln|\mathcal H|\le32\ln2. The construction above needs \omega/\pi to about m+1 significant bits. The infinite VC dimension comes from the infinite precision of one real number, which can hide arbitrarily many bits. This is the difference between counting parameters and counting bits that the float-encoding bound in 1.1 relies on.

1. The negative log posterior is \frac1{2\sigma^2}\|y-X\beta\|^2+\frac1{2\tau^2}\|\beta\|^2+\text{const}. Multiplying by 2\sigma^2/n gives \frac1n\|y-X\beta\|^2+\frac{\sigma^2}{n\tau^2}\|\beta\|^2, the ridge objective with \lambda=\sigma^2/(n\tau^2). The log posterior is quadratic in \beta, so the posterior is Gaussian. Its precision is X^\top X/\sigma^2+I/\tau^2=(X^\top X+n\lambda I)/\sigma^2, and its mean (which is also the mode) is \hat\beta_\lambda.

2. Write G=X^\top X and a=n\lambda. The posterior covariance is \sigma^2(G+aI)^{-1} and the sampling covariance is \sigma^2G(G+aI)^{-2}. Their difference is \sigma^2a(G+aI)^{-2}\succeq0, so the posterior is wider. The sampling covariance ignores the bias. The posterior covariance is the bias–variance mean squared error averaged over the prior: along a singular direction v_k of X with singular value s (and \mathbb E\beta_k^2=\tau^2 under the prior), using 2.5.1 at a=\sigma^2/\tau^2,

\frac{a^2\tau^2+\sigma^2s^2}{(s^2+a)^2}=\frac{\sigma^2(a+s^2)}{(s^2+a)^2}=\frac{\sigma^2}{s^2+a}.

3. \frac{d}{d\beta}\log(\beta e^{-\beta})=1/\beta-1=0, so the mode is \beta=1. The density of u=\log\beta is \pi(e^u)e^u\propto e^{2u-e^u}, and \frac{d}{du}(2u-e^u)=0 gives e^u=2, i.e. \beta=2. Same posterior, different “MAP”. The mean is not invariant under nonlinear maps either. The median is invariant under monotone maps.

So the identification “penalty = negative log prior” holds in a chosen parametrization. Weight decay is a Gaussian prior on the weights, which in a network induces some prior on functions that depends on the architecture. The MAP estimate under it is not an invariant summary of the posterior.

1. The problem is convex, and Slater’s condition holds for \rho>0. The Lagrangian is \hat R_n(b)+\lambda(\|b\|^2-\rho) with \lambda\ge0. Stationarity gives -\frac2nX^\top(y-Xb)+2\lambda b=0, i.e. b=(X^\top X+n\lambda I)^{-1}X^\top y=\hat\beta_\lambda for \lambda>0. For \lambda=0, use the minimum-norm least-squares solution X^+y; other feasible least-squares solutions may also minimize when X is rank deficient. Complementary slackness says either \lambda=0 (the constraint need not be strictly slack) or \|\hat\beta_\lambda\|^2=\rho.

2. In the SVD, \|\hat\beta_\lambda\|^2=\sum_k\frac{s_k^2(u_k^\top y)^2}{(s_k^2+n\lambda)^2}. Each term is non-increasing in \lambda, and at least one is strictly decreasing when X^\top y\ne0. As \lambda\downarrow0 the norm rises to \|X^+y\|^2, the minimum-norm least-squares solution, and as \lambda\to\infty it falls to 0. So the map from \rho to \lambda is a decreasing bijection on (0,\|X^+y\|^2). Tighter constraints need bigger multipliers.

3. The explanation is capacity. The norm ball \{x\mapsto x^\top b:\|b\|\le B\} has Rademacher complexity of order B\sqrt{\mathbb E\|x\|^2/n} (quoted), which controls prediction complexity. To turn this into a squared-loss gap bound, additionally control the input norms and labels (or suitable tails), so the loss is Lipschitz on the allowed prediction range. Small enough complexity then gives an excess-risk bound via 2.1.3. This inherits two problems. The norm depends on the parametrization (4.1.3, 4.5), and Zhang et al.’s objection applies: nets with weight decay still fit random labels, so the constraint that is actually active is not small.

1. X^\top y=\sum_k s_k(u_k^\top y)v_k and (X^\top X+n\lambda I)^{-1}v_k=v_k/(s_k^2+n\lambda), so \hat\beta_\lambda=\sum_k\frac{s_k(u_k^\top y)}{s_k^2+n\lambda}v_k=\sum_k\frac{s_k^2}{s_k^2+n\lambda}\cdot\frac{u_k^\top y}{s_k}v_k.

2. \nabla L=\frac1n(X^\top X\beta-X^\top y). In coordinates b_k=v_k^\top\beta,

\dot b_k=-\frac{s_k^2}{n}b_k+\frac{s_k}{n}u_k^\top y,

with fixed point (u_k^\top y)/s_k. From b_k(0)=0 the solution is b_k(t)=(1-e^{-s_k^2t/n})(u_k^\top y)/s_k. For gradient descent, b_k^{(T)}-b_k^\infty=(1-\eta s_k^2/n)^T(b_k^{(0)}-b_k^\infty), which gives the stated filter. Directions with s_k=0 never move. Discrete gradient descent converges on the positive eigendirections when 0<\eta<2n/s_{\max}^2; the filter is non-oscillatory for \eta\le n/s_{\max}^2.

3. Ridge equals \tfrac12 at s^2=n\lambda, and flow equals \tfrac12 at s^2t/n=\ln2, i.e. at s^2=n\ln2/t. These coincide iff t=\ln2/\lambda. With this matching, ridge is x/(1+x) and flow is 1-e^{-x\ln2}=1-2^{-x}.

• Weak directions, x\ll1: ridge \approx x and flow \approx x\ln2, so ridge passes about 1/\ln2\approx1.44 times more of each weak direction.
• Strong directions, x\gg1: ridge leaves a shrinkage of 1-\phi\approx1/x, only polynomially small, while flow leaves 2^{-x}, exponentially small. So ridge shrinks the strong directions more.

Gradient flow is the sharper, more step-like filter. The largest disagreements are flow above ridge by about 0.138 (near x\approx4.3) and ridge above flow by about 0.044 (near x\approx0.36). With the naive matching t=1/\lambda, flow becomes 1-e^{-x} and its half-point moves to x=\ln2. “Early stopping is ridge” is right in outline (keep the strong directions, drop the weak ones) and wrong in detail. MDL4 (learning curves) derives how the polynomial tail of the ridge filter affects learning-curve exponents.

4. \dot\beta\in\mathrm{row}(X), so \beta(t)\in\mathrm{row}(X) for all t. For p>n with X of full row rank, all s_k>0 for k\le n, so by 2 the flow converges to \sum_{k\le n}\frac{u_k^\top y}{s_k}v_k=X^+y. That is the unique interpolant in the row space, and so the minimum-norm interpolant. From \beta_0, the row-space component converges to the same place and the null-space component never moves: the limit is X^+y+(I-X^+X)\beta_0. The implicit bias is “minimum distance from the initialization”.

1. Let \eta_i=x_i^\top\beta and \delta_i=\tilde x_i^\top\beta-\eta_i=\sum_jx_{ij}\beta_j(\xi_{ij}/q-1). Then \mathbb E\delta_i=0 and, by independence, \mathrm{Var}\,\delta_i=\frac{1-q}{q}\sum_jx_{ij}^2\beta_j^2. So \mathbb E(y_i-\eta_i-\delta_i)^2=(y_i-\eta_i)^2+\mathrm{Var}\,\delta_i. Averaging over i gives the penalty \frac{1-q}{q}\sum_j\beta_j^2\|x_{\cdot j}\|^2/n.

2. \Gamma=\frac{1-q}{q}\,\mathrm{diag}(X^\top X/n). Under x_{\cdot j}\to \alpha x_{\cdot j}, \beta_j\to\beta_j/\alpha, the product \beta_j^2\|x_{\cdot j}\|^2 is unchanged, while ridge’s \beta_j^2 changes by 1/\alpha^2. Dropout on inputs is ridge after standardizing each feature by its root mean square: ridge in the metric \mathrm{diag}(\hat\Sigma).

3. \mathbb E\tilde x_i^\top\beta=\eta_i, so the linear term -y\,\tilde x_i^\top\beta is unchanged in expectation. A second-order expansion gives \mathbb E A(\eta_i+\delta_i)\approx A(\eta_i)+\tfrac12A''(\eta_i)\mathrm{Var}\,\delta_i, so the penalty is \frac1n\sum_i\tfrac12A''(\eta_i)\frac{1-q}{q}\sum_jx_{ij}^2\beta_j^2. For logistic regression A''(\eta)=\hat p(1-\hat p), the Fisher information of the example. The penalty is ridge in the metric of the diagonal Fisher information. Confidently classified examples contribute little, and features that matter on uncertain examples are penalized most. “Adaptive” because the metric depends on the current \beta. For squared loss written as \tfrac12(y-\eta)^2, A''=1, which recovers 1 up to the factor \tfrac12 of that convention.

The general lesson: many “hacky” regularizers are quadratic penalties in disguise, in some metric. The question to ask is “which metric?”

1. R(\theta^*+\delta)=R(\theta^*)+\nabla R(\theta^*)^\top\delta+\tfrac12\delta^\top H\delta+O(\|\delta\|^3). The gradient term vanishes, and \mathbb E\,\delta^\top H\delta=\mathrm{Tr}(H\Sigma). Here \Sigma is the second moment about \theta^*, so it includes any bias. For OLS, R(b)=\sigma^2+\|b-\beta\|^2 is exactly quadratic with H=2I, and \Sigma=\sigma^2(X^\top X)^{-1}, so \tfrac12\mathrm{Tr}(H\Sigma)=\sigma^2\mathrm{Tr}(X^\top X)^{-1} exactly, as in 2.2.2.

2. \tfrac12\mathrm{Tr}\big(H\cdot\tfrac1nH^{-1}CH^{-1}\big)=\tfrac1{2n}\mathrm{Tr}(CH^{-1}). If C=cH, this is cp/(2n). The curvature cancels: a sharp direction is pinned down more tightly by the data (\Sigma\propto H^{-1}), and this exactly offsets the larger cost of a given error there. “Flatter is better” needs \Sigma that does not shrink in proportion as H grows. One case is a perturbation scale set by something other than the data’s curvature, such as SGD noise at a fixed learning rate: if the gradient noise scales as C\propto H^{g}, 8.2 finds \Sigma\propto H^{g-1} (it writes the exponent as \gamma). So “flat minima generalize” is a claim about H and \Sigma jointly.

3. Write u=w_1w_2, so R=a(u-c^*)^2+\text{const}. Then \partial_{w_1}R=2a(u-c^*)w_2, and at a minimum (u=c^*),

H=2a\begin{pmatrix}w_2^2&w_1w_2\\ w_1w_2&w_1^2\end{pmatrix}=2a\,vv^\top,\qquad v=(w_2,w_1)^\top .

The terms proportional to u-c^* vanish there. So H has rank one, with eigenvalue 2a(w_1^2+w_2^2)=\mathrm{Tr}\,H along v and eigenvalue 0 along (w_1,-w_2), the direction tangent to the hyperbola. Under the rescaling, \mathrm{Tr}\,H=2a(\alpha^2w_1^2+w_2^2/\alpha^2)\ge4a|w_1w_2|=4a|c^*| by AM–GM, with equality at \alpha^2=|w_2/w_1|, and it is unbounded as \alpha\to0 or \infty. Every value in [4a|c^*|,\infty) is attained by the same function. Weight decay would pick the balanced representative. For ReLU networks, \mathrm{ReLU}(\alpha z)=\alpha\,\mathrm{ReLU}(z) for \alpha>0, so multiplying one layer by \alpha and the next by 1/\alpha leaves the network function unchanged. Dinh et al. use this to make any minimum arbitrarily sharp.

4. At a critical point, H_\varphi=J^\top HJ. To first order \delta_\theta=J\delta_\varphi, so \Sigma_\varphi=J^{-1}\Sigma J^{-\top}. Then \mathrm{Tr}(H_\varphi\Sigma_\varphi)=\mathrm{Tr}(J^\top HJJ^{-1}\Sigma J^{-\top})=\mathrm{Tr}(H\Sigma), which is invariant, whereas \mathrm{Tr}\,H_\varphi=\mathrm{Tr}(J^\top HJ) depends on J. A meaningful flatness claim has to say in what metric the perturbations are measured: either the distribution \Sigma of perturbations that actually occurs, or an invariant geometry such as the Fisher (output-space) metric. Raw \mathrm{Tr}\,H in weight space is a property of the parametrization, not of the function.

The paper shows that weight-space sharpness measures (\mathrm{Tr}\,H, the top eigenvalue, \epsilon-sharpness in a Euclidean ball, flat volume) are not functions of the network function, because a symmetry of the parametrization changes them arbitrarily. So none of them can be a sufficient statistic for generalization, and an empirical correlation between them and test error depends on how parametrizations happen to be distributed in practice. It leaves open quantities that are invariant under the symmetry or carry their own metric:

• \mathrm{Tr}(H\Sigma) with the \Sigma that training actually produces;
• sharpness measured in the Fisher or output-space metric;
• normalized or scale-invariant sharpness;
• the volume of a function-space neighbourhood (the posterior mass of a function), which is what PAC-Bayes and Bayesian accounts use.

It also leaves open whether SGD, from standard initializations, tends to land in parametrizations where raw sharpness happens to track one of these. That is an empirical question about the training procedure, not about the geometry.

1. Both sides of \Phi^\top(\Phi\Phi^\top+aI_n)=\Phi^\top\Phi\Phi^\top+a\Phi^\top=(\Phi^\top\Phi+aI_D)\Phi^\top agree. For a>0 both bracketed matrices are positive definite, hence invertible. Multiplying on the left by (\Phi^\top\Phi+aI_D)^{-1} and on the right by (\Phi\Phi^\top+aI_n)^{-1} gives the identity. With a=n\lambda, \hat w_\lambda=\Phi^\top(K+n\lambda I)^{-1}y=\Phi^\top\hat\alpha, and \hat f_\lambda(x)=\phi(x)^\top\Phi^\top\hat\alpha=k_x^\top\hat\alpha.

Costs, counting arithmetic operations:

The dual form wins when D\gg n, and it is the only option when D=\infty; the primal form wins when n\gg D. For large n the O(n^3) solve and the O(n^2) memory for K are the bottleneck of kernel methods, which is what random features (Rahimi and Recht, in the readings above) address.

2. Split w=w_\parallel+w_\perp, where w_\parallel=\Phi^\top\alpha lies in the span of \phi(x_1),\dots,\phi(x_n) and w_\perp is orthogonal to it. Each entry of \Phi w_\perp is \phi(x_i)^\top w_\perp=0, so \mathcal L(\Phi w)=\mathcal L(\Phi w_\parallel), while \|w\|^2=\|w_\parallel\|^2+\|w_\perp\|^2. Hence J(w)=J(w_\parallel)+\lambda\|w_\perp\|^2, and any w with w_\perp\neq0 is strictly beaten by w_\parallel. Substituting \Phi w=\Phi\Phi^\top\alpha=K\alpha and \|w\|^2=\alpha^\top K\alpha,

J=\mathcal L(K\alpha)+\lambda\,\alpha^\top K\alpha .

The infinite-dimensional problem has become an n-dimensional one that needs only kernel values. The same proof works for any regularizer that is a nondecreasing function of \|w\| (with “a minimizer” in place of “every minimizer” when it is not strictly increasing).

For the squared loss, the gradient in \alpha is -\frac2nK(y-K\alpha)+2\lambda K\alpha=\frac2nK\big[(K+n\lambda I)\alpha-y\big], which vanishes at \hat\alpha. The objective is a convex quadratic in \alpha, so a stationary point is a minimizer. (If K is singular, other minimizers \hat\alpha+v with Kv=0 exist, but \|\Phi^\top v\|^2=v^\top Kv=0, so they all give the same w.)

3. If K is invertible, (K+n\lambda I)^{-1}\to K^{-1}, so \hat f_\lambda(x)\to k_x^\top K^{-1}y. At the training inputs, \Phi\hat w_0=\Phi\Phi^\top K^{-1}y=y, so the limit interpolates. Any other interpolant is \hat w_0+w' with \Phi w'=0, and \hat w_0^\top w'=y^\top K^{-1}\Phi w'=0, so \|\hat w_0+w'\|^2=\|\hat w_0\|^2+\|w'\|^2\ge\|\hat w_0\|^2. Finally \|\hat w_0\|^2=y^\top K^{-1}\Phi\Phi^\top K^{-1}y=y^\top K^{-1}y. In RKHS language: among all functions in \mathcal H_k that fit the data exactly, k_x^\top K^{-1}y has the smallest RKHS norm. Here \hat w_0=\Phi^+y (Moore–Penrose pseudoinverse): the same minimum-norm interpolant that gradient descent from zero finds in linear regression with more parameters than data (4.3.4, 1.4).

4. On the span of the u_k, K(K+aI)^{-1} acts as s_k^2/(s_k^2+a), and it is zero on the orthogonal complement. So \hat y=K\hat\alpha=K(K+n\lambda I)^{-1}y is as stated, and \|\hat w_\lambda\|^2=\hat\alpha^\top K\hat\alpha=\sum_ks_k^2(u_k^\top y)^2/(s_k^2+n\lambda)^2. This is the primal ridge filter of 4.3, as it must be: it is the same estimator.

At \lambda=0, \|\hat w_0\|^2=\sum_k(u_k^\top y)^2/s_k^2. Write y=\Phi w^*+\varepsilon. Since u_k^\top\Phi w^*=s_kv_k^\top w^*, and \mathbb E(u_k^\top\varepsilon)^2=\sigma^2 in every direction,

\mathbb E\|\hat w_0\|^2=\sum_k(v_k^\top w^*)^2+\sigma^2\sum_k\frac1{s_k^2}=\|P_{\rm row}w^*\|^2+\sigma^2\,\mathrm{Tr}\,K^{-1},

where P_{\rm row} projects onto the span of the \phi(x_i). The signal contributes at most \|w^*\|^2, however small the eigenvalues. The noise contributes \sigma^2/s_k^2 per direction, which explodes along the smallest eigenvalues of K: the interpolant fits the noise using exactly the directions the kernel considers least plausible (largest RKHS cost), and pays for it in norm. Ridge suppresses those directions instead. Whether the interpolant’s noise fit actually hurts test error depends on how many small eigenvalues there are and how they spread; that is benign overfitting, 5.2–5.3.

1. \hat\beta=X^\top(XX^\top)^{-1}y with X^\top=\begin{pmatrix}X_s^\top\\ X_t^\top\end{pmatrix}, so the two blocks are X_s^\top(XX^\top)^{-1}y and X_t^\top(XX^\top)^{-1}y, and XX^\top=X_sX_s^\top+X_tX_t^\top. For the identity, both sides of (X_s^\top X_s+cI_k)X_s^\top=X_s^\top X_sX_s^\top+cX_s^\top=X_s^\top(X_sX_s^\top+cI_n) are equal. Multiply on the left by (X_s^\top X_s+cI_k)^{-1} and on the right by (X_sX_s^\top+cI_n)^{-1}; both inverses exist because c>0. If X_tX_t^\top=cI_n, then \hat\beta_s=X_s^\top(X_sX_s^\top+cI_n)^{-1}y=(X_s^\top X_s+cI_k)^{-1}X_s^\top y=\hat\beta^{\rm R}_{\lambda},\qquad n\lambda=c . The interpolant never sees a penalty. The tail’s Gram matrix plays the role of n\lambda I_n inside the “kernel” form of ridge.

2. \mathbb E\,z_jz_j^\top=I_n, so \mathbb E W/m=I_n. A diagonal entry \frac1m\sum_jz_{ij}^2 has variance \frac1m\mathrm{Var}(z^2)=\frac1m(3-1)=\frac2m. An off-diagonal entry \frac1m\sum_jz_{ij}z_{lj} (i\ne l) has mean 0 and variance \frac1m\mathbb E z_{ij}^2z_{lj}^2=\frac1m. Each entry is an average of m i.i.d. terms, so it converges to the corresponding entry of I_n, and X_tX_t^\top=\nu W=c\,W/m\to cI_n.

3. With v=e_1, (W/m)v=\frac1m\sum_jz_jz_{1j}, and \mathbb E\|(W/m)v\|^2=\frac1{m^2}\sum_{j,l}\mathbb E\big[z_{1j}z_{1l}\,z_j^\top z_l\big]. For j\ne l the factors are independent and \mathbb E[z_{1j}z_j]=e_1, so each of the m(m-1) terms is e_1^\top e_1=1. For j=l, \mathbb E\big[z_{1j}^2\|z_j\|^2\big]=\mathbb Ez_1^4+(n-1)=n+2, for m terms. So \mathbb E\|(W/m)v\|^2=1+(n+1)/m. Since \mathbb E\,v^\top(W/m)v=1, \mathbb E\|(W/m-I)v\|^2=\mathbb E\|(W/m)v\|^2-2\,\mathbb E\,v^\top(W/m)v+1=\frac{n+1}{m}. Summing over v=e_1,\dots,e_n gives \mathbb E\|W/m-I\|_F^2=n(n+1)/m, which matches 2: n\cdot\frac2m+n(n-1)\cdot\frac1m. The individual entries are O(1/\sqrt m), but their effect on a vector adds up over n coordinates. The operator norm \|W/m-I\| is about 2\sqrt{n/m} (part 4), so the approximation X_tX_t^\top\approx cI_n is controlled by n/m.

4. The eigenvalues of W are the squared singular values, so on the stated event they lie in [(\sqrt m-\sqrt n-t)^2,(\sqrt m+\sqrt n+t)^2]=m[(1-d)^2,(1+d)^2]. Multiplying by \nu and using m\nu=c puts the eigenvalues of X_tX_t^\top in [c(1-d)^2,c(1+d)^2]. Since X_sX_s^\top\succeq0, XX^\top\succeq X_tX_t^\top, and so \lambda_{\min}(XX^\top)\ge c(1-d)^2, equivalently \|(XX^\top)^{-1}\|\le1/\big(c(1-d)^2\big). (With n=100, m=20000 the edges are near (1\pm0.07)^2\approx0.86,\,1.15, and a simulation agrees.)

The noise enters the interpolant as X^\top(XX^\top)^{-1}\varepsilon, so its size is governed by the small eigenvalues of XX^\top. In the isotropic model with p\approx n, XX^\top has eigenvalues near zero, and that is where the divergence of the risk at p=n comes from. A high-dimensional tail puts a floor of about c under every eigenvalue of XX^\top, which is exactly what an explicit ridge penalty n\lambda=c does.

1. u solves (X_sX_s^\top+cI_n)u=y, i.e. cu=y-X_s(X_s^\top u)=y-X_s\hat\beta_s. By 5.2.1, \hat\beta_s=\hat\beta^{\rm R}_\lambda with n\lambda=c. On the training inputs the tail predicts X_t\hat\beta_t=X_tX_t^\top u=cu=y-X_s\hat\beta^{\rm R}_\lambda: the signal block makes the ridge fit, and the tail adds exactly the ridge residual, so the total fit interpolates. The tail’s test cost is \nu\|\hat\beta_t\|^2=\nu\,u^\top X_tX_t^\top u=\nu c\|u\|^2=\frac{\nu}{c}\|y-X_s\hat\beta^{\rm R}_\lambda\|^2=\frac{\|y-X_s\hat\beta^{\rm R}_\lambda\|^2}{m}. For n\gg k, the expected squared ridge residual is about \sigma^2(n-k)+c^2r^2/n (noise the signal block cannot fit, plus the shrinkage bias), so for c\ll n the tail costs about \sigma^2(n-k)/m.

Why it is cheap: \hat\beta_t=\sum_iu_i\,x_{t,i} is a combination of the n training tail vectors. These are nearly orthogonal in \mathbb R^m (here exactly orthogonal, each of squared norm c), so x_{t,i}^\top\hat\beta_t=cu_i reproduces residual i at training point i. A fresh x_t is nearly orthogonal to all of them, and x_t^\top\hat\beta_t has variance \nu\|\hat\beta_t\|^2. The fitted function is the ridge fit plus a narrow spike at each training point, and the spikes occupy a vanishing fraction of the m-dimensional tail.

2. \nu\|\hat\beta_t\|^2=\nu\,u^\top X_tX_t^\top u\le\nu\mu_{\max}\|u\|^2. Because XX^\top\succeq X_tX_t^\top, \mu_{\min}(XX^\top)\ge\mu_{\min}, so \|u\|=\|(XX^\top)^{-1}y\|\le\|y\|/\mu_{\min}. On the event of 5.2.4, \mu_{\min}\ge c(1-d)^2 and \mu_{\max}\le c(1+d)^2, so \nu\|\hat\beta_t\|^2\le\frac{\nu c(1+d)^2}{c^2(1-d)^4}\|y\|^2=\frac{\|y\|^2}{m}\cdot\frac{(1+d)^2}{(1-d)^4}. With \|y\|^2\approx n(r^2+\sigma^2) this is O\big((r^2+\sigma^2)n/m\big). The bound uses \|y\|^2 where 1 had the smaller ridge residual. In simulation (k=5, n=100, m=20000, \sigma=1, r^2=5) the tail cost matches \|y-X_s\hat\beta^{\rm R}_\lambda\|^2/m\approx0.005 to within 1%, against a bound of about 0.05.

3. With k=0, \nu\|\hat\beta_t\|^2=\nu\,\varepsilon^\top(X_tX_t^\top)^{-1}X_tX_t^\top(X_tX_t^\top)^{-1}\varepsilon=\nu\,\varepsilon^\top(\nu W)^{-1}\varepsilon=\varepsilon^\top W^{-1}\varepsilon. Averaging over \varepsilon and then over W, \mathbb E\,\nu\|\hat\beta_t\|^2=\sigma^2\,\mathbb E\,\mathrm{Tr}\,W^{-1}=\frac{\sigma^2n}{m-n-1}. The \nu cancels: rescaling the tail rescales \hat\beta_t inversely, and the test cost is scale-free. As m\downarrow n+1 the cost diverges; this is the double-descent peak again, now inside the tail. For m\gg n it is about \sigma^2n/m. So what makes memorization cheap is the dimension of the tail relative to n. A small \nu is needed for a different reason (part 4): to keep the total c=m\nu, and hence the implicit penalty, small.

4. Write X_tX_t^\top=c(I+\Delta), where \|\Delta\|\le(1+d)^2-1\approx2\sqrt{n/m}\to0, and A=X_sX_s^\top+cI_n\succeq cI_n. Then \hat\beta_s-\hat\beta^{\rm R}_\lambda=X_s^\top\big[(A+c\Delta)^{-1}-A^{-1}\big]y, and \|(A+c\Delta)^{-1}-A^{-1}\|\le\frac1c\cdot c\|\Delta\|\cdot\frac1{c(1-\|\Delta\|)}\to0. So \hat\beta_s\to\hat\beta^{\rm R}_\lambda. With 2, \mathcal R(\hat\beta)=\|\hat\beta_s-\beta_s\|^2+\nu\|\hat\beta_t\|^2\to\|\hat\beta^{\rm R}_\lambda-\beta_s\|^2. The training error is 0 for every m, since \hat\beta interpolates.

Ridge risk: if X_s^\top X_s=nI_k, then \hat\beta^{\rm R}_\lambda=\frac{1}{n+c}X_s^\top y=\frac{n}{n+c}\beta_s+\frac1{n+c}X_s^\top\varepsilon. The bias is -\frac{c}{n+c}\beta_s, and the noise term has covariance \frac{\sigma^2n}{(n+c)^2}I_k. Adding squared bias and variance, \mathbb E_\varepsilon\|\hat\beta^{\rm R}_\lambda-\beta_s\|^2=\frac{c^2r^2+\sigma^2nk}{(n+c)^2}. For c\ll n this is \approx\sigma^2k/n+c^2r^2/n^2. (The fluctuations of X_s^\top X_s around nI_k are of relative size \sqrt{k/n} and change this by a factor 1+O(k/n) on the variance term.) In total, \mathcal R(\hat\beta)\approx\underbrace{\frac{\sigma^2k}{n}}_{\text{signal variance}}+\underbrace{\frac{c^2r^2}{n^2}}_{\text{tail-as-ridge bias}}+\underbrace{\frac{\sigma^2(n-k)}{m}}_{\text{memorized noise}} . In simulation with k=5, n=100, m=20000: for c=10, 0.086 against ridge’s 0.082 (and \sigma^2k/n=0.05); for c=50, both \approx0.62, dominated by the bias. At m=200 (still c=10) the risk is about 1.0, of which 0.92 is the tail term: a tail only twice as wide as n is not benign.

Interpolation is benign (\mathcal R\to0 as n\to\infty) when, besides k\ll n:

• The tail is high-dimensional: m\gg n. The tail then absorbs the noise in nearly orthogonal directions at a cost \approx\sigma^2n/m, and its Gram matrix is close to a multiple of the identity, so it acts as an isotropic ridge.
• The tail is small in total: c=m\nu\ll n, i.e. the implicit penalty \lambda=c/n is small compared with the signal eigenvalue 1. Otherwise the tail-as-ridge over-shrinks the signal.

Both together require \nu\ll n/m\ll1: very many, very weak directions.

5. In the isotropic model every direction has variance 1, so a tail of m\approx p features has c\approx p>n. Near p\approx n the tail is not high-dimensional: \sigma^2n/(p-n-1) is part 3’s formula, and it diverges. For p\gg n the tail is high-dimensional, but its total variance c\approx p\gg n makes the implicit ridge so strong that the fit captures only the fraction n/p of \beta; the risk tends to \|\beta\|^2(1-n/p)\to\|\beta\|^2, the risk of predicting zero. Because \nu=1 is fixed, m\gg n forces c=m\gg n, so the two conditions cannot hold together. (In the isotropic model the signal is also spread over all directions, so this “tail” is not junk; the analogy is about the variance and shrinkage mechanisms, not an exact match.)

6. The eigenvalues are 1 (k times) then \nu (m times). r_0=(k+m\nu)/1=k+c. For j<k, r_j=k-j+c<bn, and r_k=m\nu/\nu=m\ge bn, so k^*=k. Then R_k=(m\nu)^2/(m\nu^2)=m. The benign conditions become (k+c)/n\to0, k/n\to0 and n/m\to0: small tail total (c\ll n), few signal directions, and a high-dimensional tail (m\gg n). Their variance bound \sigma^2(k^*/n+n/R_{k^*})=\sigma^2(k/n+n/m) matches the first and third terms in 4. For a non-isotropic tail, r_k and R_k are the right notions of “how many dimensions the tail effectively has”.

1. If \mathrm{KL}(Q\|P)=\infty there is nothing to prove. Otherwise write Z=\mathbb E_Pe^f, so \frac{dQ}{dP_f}=\frac{dQ}{dP}\,Ze^{-f} and

0\le\mathrm{KL}(Q\|P_f)=\mathbb E_Q\Big[\ln\frac{dQ}{dP}-f+\ln Z\Big]=\mathrm{KL}(Q\|P)-\mathbb E_Qf+\ln\mathbb E_Pe^f .

Rearranging gives the inequality, and \mathrm{KL}(Q\|P_f)=0 iff Q=P_f, so the maximum is attained exactly at the Gibbs measure. With P uniform on N states, \mathrm{KL}(Q\|P)=\ln N-\mathrm{Ent}(Q), where \mathrm{Ent}(Q)=-\sum Q\ln Q is the entropy. Taking f=-\beta E gives \mathbb E_Pe^f=Z_\beta/N, with Z_\beta=\sum e^{-\beta E} the partition function. The inequality becomes \langle E\rangle_Q-T\,\mathrm{Ent}(Q)\ge-T\ln Z_\beta=F, with equality for the Boltzmann distribution: the Gibbs variational principle for the free energy.

2. The X_i=R(h)-\ell(h;z_i) are i.i.d., have mean zero, and lie in [R(h)-1,R(h)], an interval of length 1. By independence and Hoeffding’s lemma with s=\lambda/n,

\mathbb E_S\,e^{\lambda(R(h)-\hat R_n(h))}=\prod_{i=1}^n\mathbb E\,e^{(\lambda/n)X_i}\le\big(e^{\lambda^2/(8n^2)}\big)^n=e^{\lambda^2/(8n)} .

3. Average part 2 over h\sim P. Since P is fixed and the integrand is nonnegative, Tonelli’s theorem lets you swap the order: \mathbb E_S\big[\mathbb E_{h\sim P}e^{\lambda(R-\hat R_n)}\big]\le e^{\lambda^2/(8n)}. This is where P must not depend on S. If it did, the inner average would be over a different distribution for each sample, and the swap would no longer reduce to part 2. Markov’s inequality applied to Y=\mathbb E_Pe^{\lambda(R-\hat R_n)}\ge0 gives \Pr_S\big[Y>e^{\lambda^2/(8n)}/\delta\big]\le\delta. On the complementary event, part 1 with f=\lambda(R-\hat R_n) (bounded, since the loss is) gives, for every Q,

\lambda\,\mathbb E_Q(R-\hat R_n)\le\mathrm{KL}(Q\|P)+\ln Y\le\mathrm{KL}(Q\|P)+\frac{\lambda^2}{8n}+\ln\frac1\delta .

Dividing by \lambda gives (\star). The event was defined without reference to Q, which is why the bound holds for all Q at once, including Q chosen using S.

4. Let a=\mathrm{KL}(Q\|P)+\ln(1/\delta). Then a/\lambda+\lambda/(8n) is minimized at \lambda^*=\sqrt{8na}, with value \sqrt{a/(2n)}. This would give \mathbb E_QR\le\mathbb E_Q\hat R_n+\sqrt{(\mathrm{KL}+\ln(1/\delta))/(2n)}, the theorem’s form with \ln(1/\delta) in place of \ln(2\sqrt n/\delta). But \lambda^* depends on \mathrm{KL}(Q\|P), and Q depends on S. The event in part 3 was built for a single \lambda chosen in advance, and nothing covers a \lambda chosen after seeing the data.

Repair. Before seeing the data, fix the grid \lambda_k=2^k, k=0,\dots,K-1, with 2^{K-1}\ge4n, so K\approx\log_2(4n)+1. Apply part 3 to each \lambda_k at confidence \delta/K. By the union bound, with probability at least 1-\delta all K bounds hold at once, for all Q, with \ln(K/\delta) in place of \ln(1/\delta), so you may pick the best k after seeing the data. With a=\mathrm{KL}(Q\|P)+\ln(K/\delta) and whenever the optimized bound is below 1, the optimal \lambda^*=\sqrt{8na} lies in [1,4n], hence within a factor \sqrt2 of a grid point; at \lambda=c\lambda^* the value is \frac12(c+1/c)\sqrt{a/(2n)}, at most 1.061\sqrt{a/(2n)} for c\in[1/\sqrt2,\sqrt2]. The cost is that factor and \ln K\sim\ln\ln n extra nats; the theorem pays \ln(2\sqrt n) instead.

Best Q. Only \mathbb E_Q\hat R_n+\mathrm{KL}(Q\|P)/\lambda depends on Q, and by part 1 with f=-\lambda\hat R_n,

\min_Q\Big[\mathbb E_Q\hat R_n+\frac{\mathrm{KL}(Q\|P)}\lambda\Big]=-\frac1\lambda\ln\mathbb E_Pe^{-\lambda\hat R_n},

attained at Q_\lambda\propto e^{-\lambda\hat R_n}P. If the loss were the negative log-likelihood -\ln p(y\mid x,h) and \lambda=n, then e^{-n\hat R_n}=\prod_ip(y_i\mid x_i,h), and Q_\lambda would be exactly the Bayesian posterior. Other values of \lambda give “tempered” posteriors. The log loss is unbounded, so the [0,1] theorem does not cover that case as stated. The Bayesian posterior is one possible Q among many, and the bound certifies whichever Q you choose.

5. \mathrm{KL}(\delta_h\|P)=1\cdot\ln\frac1{P(h)}, since \delta_h puts all its mass on h. With probability at least 1-\delta, for all h simultaneously,

R(h)\le\hat R_n(h)+\sqrt{\frac{\ln(1/P(h))+\ln(2\sqrt n/\delta)}{2n}} .

• Uniform P on M hypotheses: \ln(1/P(h))=\ln M. This is the finite-class bound, except for \ln(2\sqrt n/\delta) in place of \ln(1/\delta); a direct union bound avoids that extra \ln(2\sqrt n).
• Prefix code: Kraft’s inequality \sum_h2^{-L(h)}\le1 makes P(h)=2^{-L(h)}/Z a distribution with Z\le1, so \ln(1/P(h))\le L(h)\ln2. The complexity is the description length of the particular h you output, L(h)\ln2 nats, regardless of how large the class is. This is the Occam bound: hypotheses with short descriptions need few samples.
• Continuous weights: if P has a density, then P(\{w\})=0 and \mathrm{KL}(\delta_w\|P)=\infty, so the bound is vacuous. To pay a finite price for a real-valued w, either store it to finite precision (a code, as above) or spread Q over a neighbourhood of w whose prior mass is not too small. 6.2 does the second.

1. With \Delta=\mu_Q-\mu_P,

\ln\frac{q(x)}{p(x)}=\frac12\ln\frac{\det\Sigma_P}{\det\Sigma_Q}-\frac12(x-\mu_Q)^\top\Sigma_Q^{-1}(x-\mu_Q)+\frac12(x-\mu_P)^\top\Sigma_P^{-1}(x-\mu_P).

Under Q, the first quadratic form has mean \mathrm{tr}(\Sigma_Q^{-1}\Sigma_Q)=p, and the second has mean \mathrm{tr}(\Sigma_P^{-1}\Sigma_Q)+\Delta^\top\Sigma_P^{-1}\Delta, which gives the formula. With \Sigma_P=\sigma_P^2I, \mathrm{tr}(\Sigma_P^{-1}\Sigma_Q)=\sum_ks_k/\sigma_P^2 and \ln\det\Sigma_P/\det\Sigma_Q=\sum_k\ln(\sigma_P^2/s_k).

• Norm term. \|w-w_0\|^2/(2\sigma_P^2) is an L_2 penalty on the distance travelled from w_0 (see part 3).
• Width term. Each eigendirection costs \frac12\phi(s_k/\sigma_P^2), with \phi(t)=t-1-\ln t\ge0, which is zero iff t=1. Narrowing Q below the prior width costs complexity. For \Sigma_Q=\sigma_Q^2I with \sigma_Q\ll\sigma_P, the cost is about p\ln(\sigma_P/\sigma_Q): roughly the nats needed to specify each of p coordinates to precision \sigma_Q within a range \sigma_P. For p=10^6 and \sigma_P/\sigma_Q=10^3, it is \frac p2(10^{-6}-1+\ln10^6)\approx6.4\times10^6 nats, hopeless for n=5\times10^4.

So a nonvacuous bound needs Q to be about as wide as the prior in almost every direction. In Dziugaite and Roy’s runs, \mathrm{KL}\approx5\times10^3 nats for about 5\times10^5 parameters, roughly 0.01 nats per parameter.

2. Write \varepsilon=w'-w\sim\mathcal N(0,\Sigma_Q). Then \hat R_n(w+\varepsilon)=\hat R_n(w)+\nabla\hat R_n(w)^\top\varepsilon+\frac12\varepsilon^\top\hat H\varepsilon+O(\|\varepsilon\|^3). The linear term has mean zero, whether or not the gradient vanishes, and \mathbb E\,\varepsilon^\top\hat H\varepsilon=\mathrm{tr}(\hat H\Sigma_Q). The cubic term also has mean zero (odd Gaussian moments), so the error is fourth order, and the formula is exact for a quadratic \hat R_n. The randomized predictor pays for curvature in proportion to how widely it spreads. This is where flatness enters.

3. The \Sigma-dependent part of the bound is

J(\Sigma)=\frac12\mathrm{tr}(\hat H\Sigma)+\frac1{2\lambda}\Big[\frac{\mathrm{tr}\,\Sigma}{\sigma_P^2}-p-\ln\det\Sigma+p\ln\sigma_P^2\Big].

It is convex, since -\ln\det is convex. Setting the gradient to zero gives \frac12\hat H+\frac1{2\lambda}(\sigma_P^{-2}I-\Sigma^{-1})=0, so \Sigma_Q^{-1}=\sigma_P^{-2}I+\lambda\hat H. At the optimum, \mathrm{tr}(\hat H\Sigma_Q)+\mathrm{tr}(\Sigma_Q)/(\lambda\sigma_P^2)=\frac1\lambda\mathrm{tr}\big(\Sigma_Q(\lambda\hat H+\sigma_P^{-2}I)\big)=p/\lambda, so

J=\frac p{2\lambda}-\frac p{2\lambda}+\frac1{2\lambda}\ln\det\big(\sigma_P^2\Sigma_Q^{-1}\big)=\frac1{2\lambda}\ln\det\big(I+\lambda\sigma_P^2\hat H\big).

Adding the norm term, \ln(1/\delta)/\lambda and \lambda/(8n) gives the stated bound.

In the eigenbasis of \hat H, with eigenvalues h_k\ge0, the posterior variance is s_k=\sigma_P^2/(1+\lambda\sigma_P^2h_k), and the direction contributes \frac1{2\lambda}\ln(1+\lambda\sigma_P^2h_k) to the bound (its share of the KL plus its curvature penalty, times 1/\lambda).

• Flat directions, h_k\ll1/(\lambda\sigma_P^2): the posterior is as wide as the prior and the contribution is about zero, however many such directions there are.
• Sharp directions: the posterior width is about 1/\sqrt{\lambda h_k} and the contribution about \frac1{2\lambda}\ln(\lambda\sigma_P^2h_k), only logarithmic in the sharpness.

The bound counts the curved directions, not the parameters. This is the PAC-Bayes form of the old minimum-description-length argument that flat minima need fewer bits. Weight decay is the norm term, with w held fixed here. Optimizing w as well trades \hat R_n(w) against \|w-w_0\|^2/(2\lambda\sigma_P^2), which is weight decay towards w_0. Neither \sigma_P nor \lambda may be tuned on the data for free; both need a grid and a union bound, as in 6.1.4. (The Laplace approximation to the Bayesian evidence has the same log-determinant, with n in place of \lambda.)

4. Write \rho(\alpha)=\alpha^2w_1^2+w_2^2/\alpha^2. The norm term is \|w\|^2/(2\sigma_P^2)=\rho(\alpha)/(2\sigma_P^2). At the rescaled point \hat H=2a\,v_\alpha v_\alpha^\top with v_\alpha=(w_2/\alpha,\alpha w_1)^\top. This has rank one with nonzero eigenvalue 2a\|v_\alpha\|^2=2a\rho(\alpha), so \ln\det(I+\lambda\sigma_P^2\hat H)=\ln\big(1+2a\lambda\sigma_P^2\rho(\alpha)\big). Both terms increase with \rho. By AM–GM, \rho\ge2|w_1w_2|=2|c^*|, with equality iff \alpha^2=|w_2/w_1|, the balanced point, and \rho\to\infty as \alpha\to0 or \infty.

Wrong or loose? Every one of these bounds is true, because the theorem holds for all Q at once. They are different numbers for the same function. Since Q may be chosen after seeing the data, you are free to centre it at the balanced representative, so the rescaling cannot make the best available bound worse. Dinh et al.’s construction (sharp minima, same function) shows only that the representative SGD lands on need not be the one that gives the best bound.

Invariance. If \varphi is a smooth bijection and P'=\varphi_\#P, Q'=\varphi_\#Q, both densities pick up the same Jacobian factor, which cancels in q'/p', so \mathrm{KL}(Q'\|P')=\mathrm{KL}(Q\|P). The dependence on the representative came from choosing isotropic Gaussians in the w coordinates: an isotropic Gaussian in rescaled coordinates is a different prior, which favours different representatives. Choosing P is choosing a metric, and so a notion of “flat”, which is the requirement 4.5.4 found for any meaningful flatness claim. Because the loss depends on w only through the function f_w, the theorem applies equally to distributions over functions, and by the data-processing inequality their KL is no larger than the weight-space KL. Weight-space KL overcharges by paying to specify which of many equivalent w you hold (Dziugaite and Roy, Appendix B).

5. For any fixed h, \Pr[h(x)\ne y]=0.9, because y is uniform on 10 classes and independent of x, hence of h(x). So \mathbb E_QR=0.9 for every Q. On the theorem’s event, 0.9\le\mathbb E_Q\hat R_n+\sqrt{(\mathrm{KL}+\ln(2\sqrt n/\delta))/(2n)}. If \mathbb E_Q\hat R_n\le0.1, then \mathrm{KL}(Q\|P)\ge2n(0.8)^2-\ln(2\sqrt n/\delta). For n=5\times10^4 and \delta=0.05, \ln(2\sqrt n/\delta)\approx9.1, so \mathrm{KL}\ge6.4\times10^4 nats, about 1.3 nats per training example.

This is consistent with fitting random labels. SGD finds w with \hat R_n(w)=0, but every Q that keeps the Gibbs training error below 0.1 must be far from P: narrow around a sharp memorizing solution, or far from w_0, or both. The theorem predicts its own vacuity on such data. On real labels nothing forbids a small KL. Dziugaite and Roy found Q with \mathrm{KL}\approx5\text{–}9\times10^3 nats at n=55{,}000, and nonvacuous bounds. Their random-label run (two classes) ended at \mathrm{KL}\approx2\times10^5, with a bound of 1.35.

The argument of 1.1.3 applies to bounds of the form \epsilon(n,\delta) that depend only on the class, n and \delta. Such a bound must also hold on the random-label distribution, so it is at least 0.9. The PAC-Bayes right-hand side also depends on S through Q and \mathbb E_Q\hat R_n. It can be large on random labels and small on real ones, with the same prior, architecture and n. What the bound does not explain is why SGD on real data lands near wide, low-KL regions. It certifies that when it happens; it does not predict it.

Expanding, 0=\nabla\hat R_n(\hat\theta_n)=\nabla\hat R_n(\theta^*)+\nabla^2\hat R_n(\tilde\theta)\,(\hat\theta_n-\theta^*) for some \tilde\theta between \hat\theta_n and \theta^* (row by row). So \sqrt n(\hat\theta_n-\theta^*)=-\big[\nabla^2\hat R_n(\tilde\theta)\big]^{-1}\sqrt n\,\nabla\hat R_n(\theta^*). \nabla\hat R_n(\theta^*)=\frac1n\sum_i\nabla\ell(\theta^*;z_i) is an average of i.i.d. vectors with mean 0 and covariance C, so by the CLT \sqrt n\,\nabla\hat R_n(\theta^*)\Rightarrow\mathcal N(0,C). By the LLN and consistency, \nabla^2\hat R_n(\tilde\theta)\to H in probability. By Slutsky, the limit is -H^{-1}\mathcal N(0,C)=\mathcal N(0,H^{-1}CH^{-1}). This is the sandwich, with H^{-1} as the bread and C as the filling (Huber; White 1982 for misspecified likelihoods).

The “inverse Fisher information” formula is H^{-1} (or C^{-1}; for the log loss, C is the score form of I and H the Hessian form), which equals the sandwich only when C=H (7.4). Misspecification can break this equality, although it need not do so in every model. Example: heteroscedastic noise fitted with a homoscedastic model, as in 7.3.

7.2.1. By 7.1, \delta=\hat\theta_n-\theta^* has \mathbb E\,\delta\delta^\top\approx\Sigma_n:=H^{-1}CH^{-1}/n. By the 4.5 formula, the expected excess risk is \tfrac12\mathrm{Tr}(H\Sigma_n)=\frac1{2n}\mathrm{Tr}(HH^{-1}CH^{-1})=\frac1{2n}\mathrm{Tr}(H^{-1}C).

7.2.2. Expand \hat R_n around its minimizer, where its gradient vanishes: \hat R_n(\theta^*)\approx\hat R_n(\hat\theta_n)+\tfrac12\delta^\top\hat H\delta, with \hat H=\nabla^2\hat R_n\approx H. Take expectations, using \mathbb E\hat R_n(\theta^*)=R(\theta^*) because \theta^* does not depend on the sample: \mathbb E\hat R_n(\hat\theta_n)\approx R(\theta^*)-\tfrac1{2n}\mathrm{Tr}(H^{-1}C). Subtracting this from 1 gives \mathbb E[R(\hat\theta_n)-\hat R_n(\hat\theta_n)]\approx\big(\tfrac1{2n}+\tfrac1{2n}\big)\mathrm{Tr}(H^{-1}C)=\frac1n\mathrm{Tr}(H^{-1}C).

7.2.3. The test loss of \hat\theta_n is above R(\theta^*) by \mathrm{Tr}(H^{-1}C)/2n, and its training loss is below R(\theta^*) by the same amount, because \hat\theta_n was fitted to that sample’s noise. The optimism spans both. A held-out set estimates R(\hat\theta_n), so held-out minus training loss estimates the optimism. Held-out loss cannot give the excess risk without the unknown R(\theta^*), although differences of excess risk between two models are measurable.

7.3.1. \nabla\ell=-(y-\theta x)x, so H=\mathbb E x^2=1. At \theta^*=\beta, \nabla\ell=-\varepsilon x, so C=\mathbb E[\varepsilon^2x^2]=\mathbb E[\sigma^2x^2\cdot x^2]=3\sigma^2, using \mathbb E x^4=3. Hence:

• \mathrm{Var}\,\hat\theta_n\approx H^{-1}CH^{-1}/n=3\sigma^2/n;
• excess risk \approx\mathrm{Tr}(H^{-1}C)/2n=3\sigma^2/2n;
• optimism \approx3\sigma^2/n.

7.3.2. The homoscedastic formulas use C=\sigma^2H, i.e. \mathrm{Tr}(H^{-1}C)=\sigma^2p with p=1. They give variance \sigma^2/n, excess risk \sigma^2/2n and optimism \sigma^2/n: all too small by a factor of 3. The noise is largest exactly where x is large, which is where the data have the most leverage on \hat\theta.

Numerical check (checks/wb2b_check.py): for a model misspecified in both mean and noise (y=\sin2x+(0.3+0.5|x|)\xi fitted linearly with an intercept), \mathrm{Tr}(H^{-1}C)=3.19 while the naive \sigma^2p=2.01. At n=200, over 2\times10^4 replications, the excess risk is 0.00812 against the formula’s 0.00799, and the optimism 0.01608 against 0.01597, a ratio of 1.98. The same check for a misspecified logistic regression (a non-quadratic loss, n=400) gives a ratio of 1.98.

1. Write s=\nabla_\theta\log p_\theta (the score). Differentiating \int p_\theta\,dy=1 once gives 0=\int\nabla p_\theta=\int p_\theta\,s, so \mathbb E_{p_\theta}s=0. Differentiating again gives 0=\int\nabla^2p_\theta=\int p_\theta\big(\nabla^2\log p_\theta+ss^\top\big), using \nabla^2p/p=\nabla^2\log p+ss^\top. So \mathbb E_{p_\theta}[ss^\top]=-\mathbb E_{p_\theta}[\nabla^2\log p_\theta]. At \theta=\theta^* the data come from p_{\theta^*}, so averaging also over x gives C=\mathbb E[ss^\top]=\mathbb E[\nabla^2\ell]=H.

2. \mathrm{Tr}(H^{-1}C)=\mathrm{Tr}(I_p)=p. So the optimism is p/n and the excess risk, which here is the KL to the truth, is p/2n nats per sample. Estimating the expected test log loss by \hat R_n(\hat\theta_n)+p/n and multiplying by 2n gives -2\log L(\hat\theta)+2p: AIC is TIC with C=H assumed. This is “parameter counting”, and it is exact only for well-specified regular models.

3. \nabla\ell=-r\nabla f with r=y-f_\theta(x), and \nabla^2\ell=\nabla f\nabla f^\top-r\nabla^2f. At \theta^*, r=\varepsilon. So C=\mathbb E[\varepsilon^2\nabla f\nabla f^\top]=\sigma^2\mathbb E[\nabla f\nabla f^\top] by independence, and H=\mathbb E[\nabla f\nabla f^\top]-\mathbb E[\varepsilon\nabla^2f]=\mathbb E[\nabla f\nabla f^\top] since \mathbb E[\varepsilon\mid x]=0. Hence C=\sigma^2H.

For OLS with x\sim\mathcal N(0,I), this predicts excess risk \sigma^2p/2n in the \tfrac12 convention, i.e. \sigma^2p/n in 2.3’s (y-f)^2 convention. That matches the large-n limit of 2.3’s exact \sigma^2p/(n-p-1).

1. Near \hat\theta_n, n\hat R_n(\theta)\approx n\hat R_n(\hat\theta_n)+\frac n2(\theta-\hat\theta_n)^\top\hat H(\theta-\hat\theta_n), and \pi(\theta)\approx\pi(\hat\theta_n) over the region of width O(n^{-1/2}) that dominates the integral. The Gaussian integral gives Z_n\approx\pi(\hat\theta_n)\,e^{-n\hat R_n(\hat\theta_n)}\,(2\pi)^{p/2}\det(n\hat H)^{-1/2}, and \det(n\hat H)=n^p\det\hat H. Taking -\log gives the stated expansion. Every term except the first two is O(1), so -2\log Z_n=-2\log L(\hat\theta_n)+p\log n+O(1).

2. AIC (and TIC) estimate the expected test loss of the plug-in predictor p_{\hat\theta_n}: a prediction question. BIC approximates -2\log of the evidence, so differences of BIC approximate log posterior odds between models: a model-identification question. The evidence penalizes each parameter by \tfrac12\log n because the posterior volume shrinks like n^{-p/2} relative to the prior (the Occam factor; MDL3, Occam and prior volume). In singular models this volume scaling changes: \frac p2\log n becomes \lambda\log n with \lambda the real log canonical threshold (RLCT), the central quantity of singular learning theory (SLT). (This \lambda is not a ridge penalty.) In one sentence: with K(\theta)=R(\theta)-R(\theta^*), the prior mass of near-optimal parameters scales as \int_{K(\theta)<\epsilon}\pi(\theta)\,d\theta\propto\epsilon^{\lambda} as \epsilon\to0 (up to a power of \log(1/\epsilon)). In a regular model that set is an ellipsoid \tfrac12\delta^\top H\delta<\epsilon in p dimensions, with mass \propto\epsilon^{p/2}, so \lambda=p/2. Degenerate (flat) directions make the set fatter, which makes \lambda smaller than p/2.

1. \bar p_n=\mathbb E_{\theta\sim\pi_n}p_\theta, and \mathrm{KL}(q\|\cdot) is convex, so by Jensen \mathrm{KL}(q\|\bar p_n)\le\mathbb E_{\theta\sim\pi_n}\mathrm{KL}(q\|p_\theta). Average over x and D.

2. For a draw \theta=\theta^*+\delta+u, the excess risk is \approx\tfrac12(\delta+u)^\top H(\delta+u). Given the data, u has mean zero, so the cross term vanishes in expectation, and G_g\approx\tfrac12\mathrm{Tr}\Big(H\big(\mathbb E\delta\delta^\top+\mathbb Euu^\top\big)\Big) =\tfrac12\mathrm{Tr}\big(H(H^{-1}/n+H^{-1}/n)\big)=\frac pn, using \mathbb E\delta\delta^\top=H^{-1}CH^{-1}/n=H^{-1}/n (since C=H). The draw pays the ERM’s error once and the posterior’s own spread once more.

3. Write \ell=-\log p_\theta, g=\nabla\ell(\hat\theta_n) and h=\nabla^2\ell(\hat\theta_n) at a given (x,y). Then \log\bar p_n=\log\mathbb E_u\,e^{-\ell(\hat\theta_n+u)} \approx-\ell(\hat\theta_n)+\log\mathbb E_u\,e^{-u^\top g-\frac12u^\top hu} \approx-\ell(\hat\theta_n)+\tfrac12\mathbb E_u\big[u^\top(gg^\top-h)u\big], to order 1/n, since \mathbb E u=0. With \mathbb Euu^\top=(nH)^{-1}, the correction is \frac1{2n}\mathrm{Tr}\big(H^{-1}(gg^\top-h)\big). Averaging over (x,y)\sim q near \theta^*, \mathbb E[gg^\top-h]=C-H=0 by the Fisher identity. So -\mathbb E\log\bar p_n=R(\hat\theta_n)+o(1/n), and B_g\approx\mathcal E\approx p/2n.

In the regular case the ensemble buys nothing at leading order. The three estimands differ by constant factors (\tfrac12,\tfrac12,1 times p/n). In singular models they come apart: B_g\approx\lambda/n, while these regular-case arguments do not determine the MLE’s leading error.

Numerical check (checks/wb2b_check.py), with linear-Gaussian regression, p=5, n=100, known noise and a flat prior, so that the posterior is exactly Gaussian: \mathcal E=0.0268 (exact finite-n value p/2(n-p-1)=0.0266), B_g=0.0258, G_g=0.0526, against p/2n=0.025 and p/n=0.05.

4. Now \mathbb E\delta\delta^\top=H^{-1}CH^{-1}/n while the posterior still has covariance H^{-1}/n, so G_g-K^*\approx\frac1{2n}\big(\mathrm{Tr}(H^{-1}C)+p\big). The approximation error K^* need not vanish under misspecification. The posterior’s width is set by H alone, but the actual sampling spread of \hat\theta_n is set by the sandwich. A misspecified posterior is overconfident when C\succ H and underconfident when C\prec H. This is one honest motivation for tempering.

1. g_i=\nabla\ell_i=r_iv_i and \nabla^2\ell_i=v_iv_i^\top+r_i\nabla^2f, so h_i=v_iv_i^\top, which has rank at most one (rank one when v_i\ne0). Averaging gives H_{GN}. The empirical gradient covariance is \frac1n\sum_ig_ig_i^\top-\bar g\bar g^\top=\frac1n\sum_ir_i^2v_iv_i^\top-\bar g\bar g^\top.

2. At interpolation every r_i=0, so every g_i=0 and C=0. But H_{GN}=\frac1n\sum v_iv_i^\top\neq0. So C\propto H fails completely: gradient noise vanishes in every direction while curvature does not. Away from interpolation, at the population optimum with r=-\varepsilon independent of x (hence of v) and \mathbb E\varepsilon=0: \bar g=0 and C=\mathbb E[\varepsilon^2]\,\mathbb E[vv^\top]=\sigma^2H_{GN}. The cancellation needs noise that is independent of where you are in input space, i.e. a well-specified model with homoscedastic noise.

3. \partial\ell_i/\partial f=s_i-y_i, so g_i=(s_i-y_i)v_i, and \partial^2\ell_i/\partial f^2=s_i(1-s_i), giving h_i=a_iv_iv_i^\top. For y_i=1 with margin f\to\infty: g_ig_i^\top has weight (1-s_i)^2\approx e^{-2f}, and h_i has weight a_i\approx e^{-f}. So g_ig_i^\top\approx a_i^2v_iv_i^\top: the noise weight is the square of the curvature weight. Both vanish as the network separates the data, but the noise vanishes faster, so C/H\to0 again. (If y were resampled from the model, \mathbb E_y(s-y)^2=s(1-s)=a and C=H: the Fisher identity. The mismatch comes from using the observed labels, which the model fits.)

1. \theta_k is independent of \xi_k, so \mathrm{Cov}\,\theta_{k+1}=(I-\eta H)\,\mathrm{Cov}\,\theta_k\,(I-\eta H)+\eta^2C/B. At stationarity, expanding gives \Sigma_\eta=\Sigma_\eta-\eta(H\Sigma_\eta+\Sigma_\eta H)+\eta^2H\Sigma_\eta H+\eta^2C/B, i.e. H\Sigma_\eta+\Sigma_\eta H=\frac\eta BC+\eta H\Sigma_\eta H. Since \Sigma_\eta=O(\eta), the last term is O(\eta^2); dropping it gives the Lyapunov equation. (Along an eigendirection of curvature h, the discrete law is wider by a relative O(\eta h), and diverges at \eta h\ge2.)

2. In the eigenbasis of H (eigenvalues h_j>0), the equation reads (h_j+h_k)\Sigma_{jk}=\frac\eta BC_{jk}, which has the unique solution \Sigma_{jk}=\frac\eta B\,C_{jk}/(h_j+h_k). If C commutes with H, C is diagonal in the same basis, so \Sigma_{jj}=\frac\eta{2B}C_{jj}/h_j, i.e. \Sigma=\frac\eta{2B}CH^{-1}. With C=cH^\gamma, \Sigma=\frac{\eta c}{2B}H^{\gamma-1}.

3. If \Sigma=\kappa H^{-1}, then H\Sigma+\Sigma H=2\kappa I, so \frac\eta BC=2\kappa I and C\propto I. Conversely, if C=cI then \Sigma=\frac{\eta c}{2B}H^{-1} solves the equation, and by uniqueness it is the solution. No commutation was assumed. Matching \frac{\eta c}{2B}=\frac Tn gives T=\frac{n\eta c}{2B}.

4. Take the trace of the Lyapunov equation: \mathrm{Tr}(H\Sigma)+\mathrm{Tr}(\Sigma H)=2\,\mathrm{Tr}(H\Sigma)=\frac\eta B\mathrm{Tr}\,C. So \tfrac12\mathrm{Tr}(H\Sigma)=\frac{\eta\,\mathrm{Tr}\,C}{4B}, for any C, commuting or not.

5. With C=cH^\gamma:

At \gamma=1 (the Fisher case), ERM gives \frac{cp}{2n}, parameter counting, while SGD gives \frac{\eta c}{4B}\mathrm{Tr}H, which grows with sharpness. For this \gamma=1 comparison at fixed c, the SGD excess-risk value increases with curvature. This local calculation does not by itself determine how SGD selects between basins. Its noise scale is \eta/B, not 1/n.

6. The update is \theta\leftarrow(I-\eta PH)\theta-\eta P\xi. The same calculation gives PH\Sigma+\Sigma HP=\frac\eta BPCP. With P=C^{-1}, try \Sigma=\kappa H^{-1}: the left side is 2\kappa C^{-1} and the right side is \frac\eta BC^{-1}, so \kappa=\frac\eta{2B}. Preconditioning by the inverse noise covariance makes the continuous-time stationary covariance posterior-shaped when C\succ0. With Gaussian diffusion this also matches the Gaussian stationary law; covariance matching alone does not establish a Gaussian law for arbitrary discrete update noise. This is the idea behind using preconditioned SGD as an approximate posterior sampler.

7. With \gamma\in[1,2], \Sigma\propto H^{\gamma-1} ranges from isotropic (\gamma=1) to \propto H (\gamma=2). The posterior \propto H^{-1} is long in flat directions and narrow in sharp ones. SGD’s cloud is at least as wide in sharp directions as in flat ones: the opposite ordering. “SGD samples a (tempered) posterior” is the claim that \gamma\approx0, i.e. isotropic gradient noise, or that one has preconditioned by C^{-1}. Neither holds for plain SGD in the measured regime.

• \gamma=0: \Sigma\propto H^{-1}, elongated along the flat \theta_1 with aspect ratio \sqrt{10} in standard deviations. Same shape as the posterior.
• \gamma=1: \Sigma=\frac{\eta c}{2B}I, a circle.
• \gamma=2: \Sigma\propto H, elongated along the sharp \theta_2: rotated 90° from the posterior.
• Rotating C’s eigenbasis tilts \Sigma off the axes. Since \Sigma\propto H^{-1} requires C\propto I (8.2.3), no temperature fixes the shape, and \mathrm{KL}^*>0 for every T.
• The discrete-time ellipse is slightly wider than the continuous one along \theta_2, by a relative O(\eta h_2)=O(10\eta), where h_2=10 is the sharp curvature.

This is as far as MDL1 goes. The Training Dynamics materials take up state-dependent noise, edge-of-stability effects and what happens away from a quadratic basin.

1. Under a reparametrization \theta=A\phi with A invertible (or its linearization, for a smooth one) that leaves the function fixed, gradients transform as \nabla_\phi=A^\top\nabla_\theta, so H\to A^\top HA and C\to A^\top CA at the minimum. Then \mathrm{Tr}(H^{-1}C)\to\mathrm{Tr}(A^{-1}H^{-1}A^{-\top}A^\top CA)=\mathrm{Tr}(H^{-1}C): TIC is invariant. (More generally, the eigenvalues of H^{-1}C are.)

• Not invariant: the parameter \ell_2 norm, the raw gradient variance \mathrm{Tr}\,C, and plain sharpness (\mathrm{Tr}\,H or a worst-case perturbation of fixed size).
• Invariant to the layer rescaling of 4.5.3 but not to general reparametrizations: the product of layer spectral norms, since \|\alpha W_1\|\,\|W_2/\alpha\|=\|W_1\|\,\|W_2\| in a ReLU network.
• Functions of the function: the margin, and the gap itself.

2. Fixing the training loss removes a trivial predictor: models with higher training loss have a different gap for uninteresting reasons. The price is that every model is near interpolation, where per-sample gradients are small (8.1). \hat C is then small and dominated by the hardest examples, and the regular-case theory behind \mathrm{Tr}(H^{-1}C) is furthest from applying. The assumptions that fail:

• Interpolation (8.1): at exact squared-loss interpolation, the empirical \hat C is zero even though population gradient variability and test loss can remain positive. Plug-in TIC then loses its regular-regime justification. Jiang et al. stop at a small positive cross-entropy, not exact interpolation; for cross-entropy both curvature and gradient covariance can shrink, at different rates.
• Singular H: overparametrized networks have flat directions, so H^{-1} is undefined and damped versions depend on \epsilon. The regular-case p/2 becomes the RLCT (7.5–7.6), which TIC does not see.
• SGD is not ERM: the trained parameter’s spread is the stationary law of 8.2, set by \eta/B and \mathrm{Tr}\,C, not the sandwich. Learning-rate and batch-size axes move the gap through a channel TIC does not model. (\mathrm{Tr}\,C itself does model it, which is one reading of Jiang et al.’s gradient-variance result.)
• Wrong loss: TIC is about the training loss. The 0–1 gap can move while the cross-entropy optimism does not, and conversely.
• Ensembles: TIC is about a single fitted network. If what you report is an ensemble’s error, the leading constant can change (7.6).

Where the assumptions do roughly hold (p small compared with n, a nondegenerate minimum, training loss bounded away from zero, a trained parameter close to the ERM), comparisons within one architecture across data size or regularization strength are the natural use of TIC.

3. If one hyperparameter (say, width) moves both the measure and the gap strongly, the pooled \tau is high even if the measure tracks nothing within any fixed setting of the others. \Psi only counts comparisons where one hyperparameter changes, so a measure that just tracks one axis scores well on that axis and near zero on the others. A measure that predicts along one axis and not another is tracking the axis, not the gap.

1. I(X;T)=H(T)-H(T\mid X), and H(T\mid X)=0 because T is determined by X. So I(X;T)=H(T)=H(f(X)). If f is injective on the support, f(X) is a relabelling of X, so H(f(X))=H(X).

2. H(X)=\log4096=12 bits \approx8.32 nats, for every such layer, at every step of training, as long as the layer stays injective on the 4096 inputs. Exact collisions are possible but need a mechanism: units that are exactly zero on whole regions of input (dead ReLUs), or saturated \tanh units that round to exactly \pm1 in floating point, can map distinct inputs to the same vector. Without such collisions, nothing in I(X;T) changes, whatever a binned estimate does.

3. Let q_\Delta map T to the cube of side \Delta that contains it. q_\Delta(T) is a deterministic function of X, so by 1, I(X;q_\Delta(T))=H(q_\Delta(T)). Since X\to T\to q_\Delta(T), data processing gives I(X;T)\ge H(q_\Delta(T))\ge-\log\max_k\Pr[q_\Delta(T)=k].

It remains to show that m(\Delta):=\sup_{\text{cubes }Q\text{ of side }\Delta}\Pr[T\in Q]\to0. Suppose not: then there are \epsilon>0 and cubes Q_j with sides \Delta_j\to0 and \Pr[T\in Q_j]\ge\epsilon. By tightness, the Q_j eventually lie in a compact set, so a subsequence of their centres converges to some t_0. Every ball around t_0 then has probability at least \epsilon, so \Pr[T=t_0]\ge\epsilon, contradicting atomlessness. Hence H(q_\Delta(T))\to\infty and I(X;T)=\infty.

(Equivalently, when T has a density, h(T\mid X)=-\infty because T given X is a point mass.)

4. In case 3, none: I(X;T)=\infty for every weight setting that keeps T atomless. In case 1, only exact collisions, where two distinct inputs are mapped to exactly the same activation vector, can lower H(f(X)). Such collisions are possible, for example with dead ReLUs. The constancy conclusion requires injectivity on the discrete input support; the infinite-information conclusion requires atomlessness. Under those conditions, movement in a finite plotted estimate does not describe a change in the exact mutual information.

1. The top bin is [1-2/K,1], and \Pr[T\ge1-2/K]=\Pr\big[Z\ge\operatorname{artanh}(1-2/K)/a\big]\to\Pr[Z>0]=\tfrac12 as a\to\infty. The bottom bin likewise tends to \tfrac12, so every other bin tends to 0. Entropy is continuous on the finite simplex, so H\to\log2: the unit has become a sign function, and the estimate counts two cells.

As a\to0, T\approx aZ concentrates at 0. With K even, 0 is a bin edge, so the two bins adjacent to 0 each get mass \to\tfrac12 and H\to\log2 again. With K odd, the middle bin straddles 0, takes all the mass, and H\to0.

2. For K=30, exact bin probabilities give (from checks/wb2b_check.py):

At small a the activations occupy a few central bins. As a grows they spread over more bins, so the estimate rises (“fitting”). Past a\approx1 they pile up in the two saturated end bins, so it falls toward \log2 (“compression”). Monotone weight growth produces the two-phase curve with no change in what the network distinguishes: T stays an injective function of Z throughout.

3. Let S=\mathbf 1[Z>0]. All mass with Z\le0 sits at T=0, in bin 0, together with \Pr[0<Z<\Delta/a]\to0. Up to that vanishing overlap, S is a function of the bin, so H(\mathrm{bin}\,T)=H(S)+\Pr[S=1]\,H(\mathrm{bin}\,T\mid S=1)+o(1) =\log2+\tfrac12H\big(\mathrm{bin}_{\Delta/a}(|Z|)\big)+o(1). Given Z>0, Z has the density of |Z|, and binning aZ at width \Delta is binning Z at width \delta=\Delta/a\to0. So H(\mathrm{bin}_\delta|Z|)=h(|Z|)-\log\delta+o(1). The half-normal has h(|Z|)=\tfrac12\log(2\pi e)-\log2=\tfrac12\log(\pi e/2), which gives the formula. Check: with \Delta=1/15 and a=100 the formula gives 4.713 nats and the exact value is 4.710; at a=1000, 5.864 against 5.864. The ReLU estimate keeps growing, with no compression phase. This is the pattern Saxe et al. report.

4. \max(0,aZ)/\max_i(0,aZ_i) does not depend on a, so the binned estimate is exactly constant in a. The answer to 3 versus 4 is decided by a choice of bins, not by the network.

5. It measures how many cells of size \Delta the data occupy, i.e. the spread of the representation measured at a resolution fixed by the analyst. That is a geometric quantity. For a fixed binning rule it is a property of the distribution of T, but it is not generally equal to the unquantized I(X;T). The distribution and geometry of T can change even while the latter stays constant.