Limits of uniform convergence

Other results. (1) An infinite-width network with frozen $N(0,I)$ hidden weights, exponential activations and one trained output layer gives the same conclusion, with a proof, when $D$ grows only like $\ln m$. (2) A wide two-layer ReLU network trained by SGD on two concentric spheres in $\mathbb R^{1000}$ (radii 1 and 1.1) misclassifies, at every $m$ tested, the whole sample obtained by projecting each training point onto the other sphere and flipping its label, while its test error falls like $m^{-0.5}$; this part is empirical. (3) Two standard derandomized PAC-Bayes bounds are lower bounded through $\epsilon_{\mathrm{unif\text{-}alg}}$, in the linear example by $e^{-3/2}(1-\epsilon)-(1-e^{-3/2})\epsilon\approx0.22$ and $1-e^{3/2}\epsilon$.

On MNIST the norms in the bounds, and so the bounds, grow with the sample size. A depth-5, width-1024 ReLU network is trained by SGD until 99% of the training points have margin at least 10, which fixes the margin term. From $m=128$ to 32,768 the test error falls like $m^{-0.43}$, while the distance from initialization grows at least like $m^{0.4}$, the product of spectral norms grows polynomially, and so does the distance between the weights learned from two independent samples with the same initialization. That last distance lower bounds the diameter of the region SGD explores, so recentering the bounds at a better point than the initialization would not help. The spectrally normalized bounds of Neyshabur et al. and Bartlett et al. grow like $m^{0.68}$ and are far above 1 throughout, and still like $m^{0.48}$ with $\gamma$ the median margin. With squared loss, which stops at a finite distance, the norms still grow, so cross-entropy pushing the weights to infinity is not the cause; other widths and larger batches help only partly, and pseudo-overfitting (bumps at the training points that inflate margins) is not the main cause, since mean train and test margins converge. The paper blames the uniform convergence step itself.

If each learned hypothesis has a typical mirror sample on which it always errs, no uniform bound can be small. Uniform convergence may discard a set of samples of mass $\delta$, but it must be the same set for every hypothesis. Suppose the algorithm generalizes, yet each $h_S$ errs everywhere on a bad sample $S'=\phi(S)$, where $\phi$ maps $\mathcal D^m$ to itself. Since $\phi(S)$ has the law of $S$, $\Pr[\phi(S)\notin\mathcal S_\delta]\le\delta$, and a union bound shows that for any $\mathcal S_\delta$ the four good events occur together with positive probability: $$\Pr_S\big[S\in\mathcal S_\delta,\ \phi(S)\in\mathcal S_\delta,\ L_{\mathcal D}(h_S)\le\epsilon,\ \hat L_{\phi(S)}(h_S)=1\big]\ge1-3\delta-\Pr\big[\hat L_{\phi(S)}(h_S)\ne1\big]\gt0.$$ Any $S_\star$ in this event puts $h_{S_\star}\in\mathcal H_\delta$ and $\phi(S_\star)\in\mathcal S_\delta$, so the supremum in the definition is at least $1-\epsilon$. The rest of the paper realizes $\phi$ with gradient descent.

The linear classifier generalizes because its memorizing part has almost no effect on fresh points. On a training point the output is $$y_ih(x_i)=4+\|x_{2,i}\|^2+y_i\,x_{2,i}^\top\sum_{j\ne i}y_jx_{2,j}\approx4+32\pm O\big(32\sqrt{m/D}\big),$$ by a chi-square tail bound and Hoeffding, so training margins are large and almost all of each comes from $w_2$ memorizing the sample. On a fresh $x$, $x_2$ is independent of $w_2$, so $yh(x)=4+x_2^\top w_2$ with $x_2^\top w_2\sim N(0,1024\,m/D)$ given the sample, and the error is about $\Pr[N(0,1)\gt\sqrt{D/m}/8]$, at most $\epsilon$ once $D\gtrsim m\ln(1/\epsilon)$. So $D\gg m$ is what keeps the memorization from affecting test points: the $m$ noise vectors are nearly orthogonal (Gram matrix close to $32I_m$), and $w_2$ fits each label through its own direction without pointing where a test point is likely to be. It also makes $w$ essentially the minimum-norm interpolant, $X^\top(XX^\top)^{-1}y\approx X^\top y/36$; in my simulation ($K=5$, $m=100$, $D=20{,}000$) the cosine between the two is 0.997, both have about 4% test error, and both misclassify all of the bad sample of Step 4.

Negating the noise gives a typical sample on which $h_S$ is always wrong. Let $S'=\{((x_1,-x_2),y):((x_1,x_2),y)\in S\}$. The same expansion with the sign of $x_2$ flipped gives $$y_ih(x_1,-x_{2,i})=4-\|x_{2,i}\|^2-y_i\,x_{2,i}^\top\sum_{j\ne i}y_jx_{2,j}\approx4-32\lt0,$$ so with high probability $h_S$ misclassifies every point of $S'$ and $\hat L_{S'}(h_S)=1$ for every $\gamma\ge0$. Since $x_2$ is a centered Gaussian independent of $(x_1,y)$, negation preserves $\mathcal D$, and $S'\sim\mathcal D^m$. Step 2 then gives $\epsilon_{\mathrm{unif\text{-}alg}}\ge1-\epsilon$ whenever $\delta\le1/4$, and no better-chosen class avoids this, even one that fixes $w_1$ at its learned value and truncates $w_2$ to any set of mass $1-\delta$.

The argument uses two-sidedness, and the extensions follow from it. At the pair $(h_{S_\star},S_\star')$ the empirical error exceeds the test error, which a hypothetical one-sided bound on $L_{\mathcal D}-\hat L_S$ allows; existing techniques bound the absolute deviation, and the paper notes it is not known how to make them one-sided. A hypothesis-dependent bound fails too, since the bound for $h_{\tilde S}$ must hold on every $S\in\mathcal S_\delta$, including $\tilde S'$. The PAC-Bayes KL form $\mathrm{kl}(\hat L_S(Q)\,\|\,L_{\mathcal D}(Q))\le(\mathrm{KL}(Q\|P)+\ln\frac{2m}\delta)/(m-1)$ is itself two-sided, so derandomizing it, by adding perturbation terms or by sandwiching the margin loss of a perturbed $Q_h$ between losses of $h$, gives a deterministic bound lower bounded through $\epsilon_{\mathrm{unif\text{-}alg}}$, with the constants of item (3). Bounds on a stochastic network concern a different classifier and are not covered.

The same failure appears in networks. For the exponential network, one gradient step on the output layer gives a kernel machine in which each training point adds a term $y_i\exp(\|(z+x_i)/2\|^2)$, playing the role of $w_2$; the bad sample negates every coordinate except the noise, $((-x_1,x_2),-y)$, and Steps 3 and 4 go through with $D$ only of order $\ln m$. For the ReLU network on spheres there is no formula: the bad sample has law $\mathcal D^m$ by rotation invariance and is measured to be misclassified entirely, so Step 2 applies. Two-dimensional slices show the boundary bent around each training point so that its projection falls on the wrong side. The claim depends on the setup: it needs enough width or input dimension relative to $m$, and with outer radius 2 SGD separates the spheres cleanly and $S'$ is classified correctly.