A data-dependent prior can invalidate the PAC-Bayes bound

Let $\mathcal{X}=\{1,\dots ,20\}$ with its full sigma-algebra, let $D$ be uniform on $\mathcal{X}$, let $c(x)=0$, and let $\mathcal{H}=\{h_A:A\subseteq \mathcal{X},\mathrm{\mid }A\mathrm{\mid }=10\}$ with its full sigma-algebra, where $h_A(x)={\mathbf{1}}_A(x)$. Use the zero-one loss $\mathrm{\ell }(h,x)=\mathbf{1}\{h(x)\mathrm{\ne }c(x)\}$, the sample size $m=10$, confidence $\delta =1\mathrm{/}4$, and tuning parameter $\lambda =20$. Draw independent observations $X_1,\dots ,X_{10}$ with common law $D$. For each sample $S=(X_1,\dots ,X_{10})$, let $A(S)$ be the lexicographically first ten-element subset disjoint from $\{X_1,\dots ,X_{10}\}$ and put ${\pi }_S={\rho }_S={\delta }_{h_{A(S)}}$. Even if one drops the requirement that the prior be fixed independently of the sample, the same PAC-Bayes formula holds with probability at least $3\mathrm{/}4$ over this sample: ${\mathbb{E}}_{h\sim {\rho }_S}{R}_D(h)\le {\mathbb{E}}_{h\sim {\rho }_S}{\widehat{R}}_S(h)+\frac{\lambda }{8m}+\frac{\mathrm{K}\mathrm{L}({\rho }_S\mathrm{\parallel }{\pi }_S)+\log (1\mathrm{/}\delta )}{\lambda },$ where $R_D(h)=D\{x:h(x)\mathrm{\ne }c(x)\}$, ${\widehat{R}}_S(h)=m^{-1}{\sum }_{i=1}^m\mathrm{\ell }(h,X_i)$, and $\mathrm{K}\mathrm{L}$ is the supremum of the finite-partition divergences with zero-numerator terms equal to $0$ and positive-numerator/zero-denominator terms equal to $+\mathrm{\infty }$.

The PAC-Bayes KL generalization bound: gives this form of bound when the prior is fixed independently of the sample.

PAC-Bayes priors, posteriors, and relative entropy: defines the prior's sample-independence requirement and the finite-partition relative entropy.

The natural logarithm as the inverse of the exponential function: $\log$ is the inverse of the real exponential on positive reals.

Alquier, User-friendly Introduction to PAC-Bayes Bounds, Chapter 2, §2.1.1: states the PAC-Bayes result with a prior fixed before observing the sample.