Nonvacuous PAC-Bayes bounds

A Gaussian prior centered at the random initialization turns the KL into a penalty on precision and on distance traveled. Take $Q=\mathcal N(w,\mathrm{diag}(s))$ and $P=\mathcal N(w_0,\lambda I)$, where the initialization $w_0$ is drawn before the data and so is a legal prior mean. The Gaussian KL $$\mathrm{KL}(Q\|P)=\frac12\Big(\frac{\|s\|_1}{\lambda}-d+\frac{\|w-w_0\|_2^2}{\lambda}+d\log\lambda-\sum_i\log s_i\Big)$$ penalizes every weight that must be stated precisely ($-\sum_i\log s_i$), for spread wider than the prior and for how far training moved. Centering at $w_0$ matters: initialization breaks the permutation symmetry of hidden units, the authors expect SGD not to undo it, and the bounds are much better than with a zero mean. No single $\lambda$ suits every architecture and $P$ may not depend on $S$, so the prior variance is picked from a grid $\lambda=c\,e^{-j/b}$ by a union bound: the $j$-th prior gets confidence $6\delta/(\pi^2j^2)$, these sum to $\delta$, and the cost, about $2\log j\approx12$ nats added to the KL, is negligible next to 5,000.

Minimizing the bound maps out a large axis-aligned ellipsoid of low loss around the SGD solution. The objective, a logistic surrogate plus Pinsker's square root of the complexity term, has the flat-minimum trade-off built in: raising $s_i$ lowers the KL through the $-\tfrac12\log s_i$ term until the injected noise starts to raise the training loss, so the optimizer learns, weight by weight, how imprecisely each can be stated. The mean is free to move, but the SGD solution stays deep inside the posterior: in the $\mathrm{diag}(s)^{-1}$ norm it is closer to the posterior mean than every one of 10,000 draws from $Q$. The reported number chains a Monte Carlo bound into the exact inverse: $\hat e(Q,S)$ cannot be computed, so the mean training error $\hat e_n$ of $n=150{,}000$ draws from $Q$ is turned into an upper bound by a kl-form Chernoff bound, and since $\mathrm{kl}^{-1}$ is increasing it can be fed in, $$e(Q)\le\mathrm{kl}^{-1}\Big(\mathrm{kl}^{-1}\big(\hat e_n\,\big|\,\tfrac1n\log\tfrac2{\delta'}\big)\,\Big|\,B\Big),$$ with $B$ the complexity term including the cost of the prior grid, valid with probability $1-\delta-\delta'=0.965$. My recomputation from the table (whose training error is already the Monte Carlo upper bound, so only the outer inverse is applied) matches all six bounds within 0.005, and Pinsker's form would have given 0.245 for the 600-unit network, so the exact inversion is worth about eight percentage points.

With a point mass and a universal prior, the KL is the code length of the model. Lotfi et al. put a point mass on one compressed model $h$ and use the prior $P(h)=2^{-K(h)}/Z$, with $K$ the prefix Kolmogorov complexity given the architecture and the random seed and $Z\le1$ by Kraft's inequality. Then $$\mathrm{KL}(\delta_h\|P)=\log\frac1{P(h)}\le K(h)\log2\le l(h)\log2+2\log l(h),$$ where $l(h)$ is the length in bits of any program that reproduces $h$. Against a continuous prior a point mass has infinite KL, which is why Dziugaite and Roy needed a Gaussian; against this discrete prior PAC-Bayes is the Occam bound, a union bound over codes at confidence $\delta\,2^{-l}$ each.

Training in a random subspace and quantizing makes the code scale with the task instead of the network. Write $\theta=\theta_0+Pw$ with a fixed random $P\in\mathbb R^{D\times d}$ and train only $w\in\mathbb R^d$; given the seed, $\theta_0$ and $P$ cost nothing, so the code carries only $w$: the selected $d$ is 1,000 for MNIST, 3,500 for CIFAR-10 and 10,000 for CIFAR-100, and it grows with the difficulty of the task, which lets the bound adapt. Each $w_i$ is rounded to one of $L$ learned levels, trained jointly with straight-through gradients so the network adapts to its own rounding, and arithmetic coding with the empirical level frequencies $p$ gives $$l(w)\le\lceil d\,H(p)\rceil+L\,(16+\lceil\log_2d\rceil)+2\ \text{bits}$$ for the symbols, a half-precision codebook and the frequencies. For MNIST with $d=1000$ and $L=7$ this is at most 2,992 bits (about 0.37 KB at the paper's 8,192 bits per KB), about 0.04 nats per training example. Standard pruning with the same quantization and coding gives 47.9% on MNIST at 6.5 KB. Every choice made after seeing the data adds to the code length, $\log_2H$ bits for a grid of $H$ values fixed in advance, so the whole hyperparameter search costs under 10 bits.

A prior trained on part of the sample turns the bound into a validation estimate, while a prior pretrained on independent data keeps it explanatory. If the prior is a checkpoint trained on part of the sample and the bound is evaluated on the rest, the optimal subspace dimension is 0 in every dataset: the posterior is the checkpoint itself, and the bound is a validation estimate. All the learning sits in the prior, which the bound does not constrain, so only data-independent bounds speak to why a network generalized. A checkpoint pretrained on an independent dataset avoids the objection: the bound constrains everything learned downstream and nothing learned upstream. CIFAR-10 goes from 58.2% to 35.1% even though the fine-tuned EfficientNet-B0 is much larger than the from-scratch ConvNet, since its difference from the checkpoint compresses to about 1 KB.

Breaking structure in the data or the model lengthens the code. At matched size a CNN gets lower bounds than an MLP on CIFAR-10 and loses that advantage when the pixels are shuffled. With shuffled labels every bound is 100%, and this is forced: at most a $2^{-c+1}$ fraction of random label strings compress by $c$ bits, and a fitted model is itself a compressor of the labels, so with probability $1-\delta$ $$K(h\mid P)\ge|D|-\mathrm{NLL}(D\mid h)-\log_2\tfrac1\delta-2:$$ a model that fits random labels well must be about as long as the labels. Full-batch training gives about the same bounds as SGD, so SGD's implicit bias is not needed for the certificate.

What the certified numbers mean. Neither certificate is for the network one would deploy. Dziugaite and Roy's is for the stochastic network $Q$, about twice as bad as the SGD network it came from, and Nagarajan and Kolter argue that the standard ways of derandomizing it reduce to two-sided uniform convergence. Lotfi et al.'s is for the compressed, quantized subspace model: by my kl-form back-of-envelope (an estimate, not a number the paper reports), a 58.2% bound at about 1.2 KB on 50,000 examples requires that model's training error to be near 32%, or somewhat less under Catoni's form (31% at $\alpha=1.1$, 22% at $\alpha=2$), much worse than the full network, and relating the two is open. Dziugaite and Roy show that SGD's solutions have this structure but not why SGD finds them, and the compression bounds do not explain why bigger networks generalize better, since the compressed size still increases with width. Compressibility implies generalization here, with no claim of the converse, and ImageNet stays essentially vacuous.