Epistemological Status: Correct, probably too technical for Less Wrong, but these results are interesting and relevant.

There's been a flurry of posts on generalization recently. Some talk about simplicity priors and other about the bias of SGD. However, I think it's worth bringing up the fact that there is already an alternative that already works well enough to provides non-vacuous bounds for neural networks. Namely, I'm talking about the PAC-Bayes approach.

The twist I'll give in this brief note is a motivation of the bound from a biological perspective and then derive the full PAC-Bayes bound. The first part relies on the error threshold for replication and the patching interpretation of the KL-divergence. The second part relies on the Donsker-Varadhan variational characterization of KL-divergence.

Error Threshold

A replication $\hat{R}$ of an object $R$ is an approximate copy (up to mutation). The environment determines whether or not an object gets to replicate via a fitness $S\left(R\right)$. Suppose $I$ is an instruction set or parameterization of $R$. When $R$ replicates $I$ is copied.

We begin with a prior distribution of instructions ${\pi }_0$ and then the distribution changes as the population replicates to $\pi$. The amount of information needed to achieve the modification is the patching cost and is equal to $D_{KL}(\pi \parallel {\pi }_0)$.

Only information from the fitness landscape $L\left(\pi \right)$ is useful for converging to the fittest individual(s). On the other hand, the amount of information available from the environment is equal to $D_{KL}\left(L\right(\pi )\parallel L({\pi }_0\left)\right)$. Thus, transitions are favorable only when we have, $$D_{KL}(\pi \parallel {\pi }_0)<D_{KL}\left(L\right(\pi )\parallel L({\pi }_0\left)\right)$$ As an example, suppose that the space of instructions is the set of boolean strings of length $|I|$​ and that mutation flips a bit in the string with uniform independent probability $ϵ$. Suppose that $I$ always survives and our fitness is simply whether or not the replicate survives. This means $L\left(I\right)=1$ and $L\left(\hat{I}\right)$ is a Bernoulli random variable with parameter $S$. Then we have, $$D_{\text{KL}}(I\parallel \hat{I})=\sum _{i=1}^n{p}_I\left(i\right)\log \left(p_I\right(i\left)/p_{\hat{I}}\right(i\left)\right)=\sum _{i=1}^n\log \left(1/\right(1-ϵ\left)\right)\simeq ϵ\cdot |I|D_{\text{KL}}\left(L\right(\hat{I})\parallel L(I\left)\right)=\log \left(1/S\right)\Rightarrow ϵ\cdot |I|+\log \left(S\right)<0$$

PAC-Bayes Bound

Now suppose that the instructions are parameterizations for some sort of learning model and that the fitness is the training metric. In particular, the survival rate could be a classification error metric. If we are given $n$ examples that induce an error rate of $ϵ$ we have the requirement, $$D_{KL}(\pi \parallel {\pi }_0)<n\cdot \log \left(1/\right(1-ϵ\left)\right)\Rightarrow 1-e^{-\frac{1}{n}{D}_{KL}(\pi \parallel {\pi }_0)}<ϵ$$ This implies that using a lot of information to update our estimate for the optimal model paramters will require high error rates.

Specifically, a sublinear relationship between the information used and the data obtained is necessary for a low error rate if we are to avoid an error catastrophe. This would be a situation where the model continues to update despite being at the optimum.

At this point it's natural to wonder if a sublinear relationship is sufficient. This is precisely the content of the PAC-Bayes theorem. To show this first note that for any $f\in L^{\infty }$, $$⟨f,\pi ⟩=⟨\log \left(e^f\right),\pi ⟩=⟨\log \left(\frac{\pi }{{\pi }_0}\frac{{\pi }_0}{\pi }{e}^f\right),\pi ⟩=⟨\log \left(\frac{\pi }{{\pi }_0}\right),\pi ⟩+⟨\log \left(\frac{{\pi }_0}{\pi }{e}^f\right),\pi ⟩=D_{KL}(\pi \parallel {\pi }_0)+⟨\log \left(\frac{{\pi }_0}{\pi }{e}^f\right),\pi ⟩\text{(Definition)}\le D_{KL}(\pi \parallel {\pi }_0)+\log (⟨\frac{{\pi }_0}{\pi }{e}^f,\pi ⟩)\text{(Jensen)}=D_{KL}(\pi \parallel {\pi }_0)+\log (⟨e^f,{\pi }_0⟩)\Rightarrow ⟨f,\pi ⟩\le D_{KL}(\pi \parallel {\pi }_0)+\log (⟨e^f,{\pi }_0⟩)$$ As an aside, the astute reader might notice this as a Young-Inequality between dual functions in which case we have the famous relation, $$\Rightarrow D_{KL}(\pi \parallel {\pi }_0)=\underset{f\in L^{\infty }}{sup}⟨f,\pi ⟩-\log (⟨e^f,{\pi }_0⟩)\text{(Donsker-Varadhan)}$$ Either way, it's clearer now that if we take $f$ to be a generalization error such as, $$f=\lambda \left(\frac{1}{n}\sum _{i=1}^{n}l\right(h\left(x_i\right),y_i)-E[l\left(h\right(x_i),y_i)\left]\right)=\lambda \left(\hat{L}\right(h)-L(h\left)\right)$$ then the left-hand side of our Young-inequality yeilds an empirical loss which is similar to what we had before. The major difference is that we have a contribution from a cumulant function which we can bound using the Markov and Hoeffding inequalities, $$⟨e^f,{\pi }_0⟩{\le }_{1-\delta }\frac{1}{\delta }E[⟨e^f,\pi ⟩]\text{(Markov)}=\frac{1}{\delta }⟨E\left[e^f\right],\pi ⟩\le \frac{1}{\delta }⟨e^{{\lambda }^2/2n},\pi ⟩=\frac{1}{\delta }{e}^{{\lambda }^2/2n}$$ Now we put everything together and then optimize over $\lambda$. $$\hat{L}\left(\pi \right)-L\left(\pi \right)=\frac{1}{\lambda }⟨f,\pi ⟩\le \frac{1}{\lambda }\left[D_{KL}\right(\pi \parallel {\pi }_0)+\log (⟨e^f,{\pi }_0⟩)]{\le }_{1-\delta }\frac{D_{KL}(\pi \parallel {\pi }_0)+\log \left(\frac{1}{\delta }\right)}{\lambda }+\frac{\lambda }{2n}$$ Optimizing we obtain, $$L\left(\pi \right)\le \hat{L}\left(\pi \right)+\sqrt{\frac{D_{KL}(\pi \parallel {\pi }_0)+\log \left(\frac{1}{\delta }\right)}{2n}}\text{(PAC-Bayes)}$$