Roughly speaking, most PAC-Bayes proofs follow four key steps. [1]} presents a comprehensive tutorial
about PAC-Bayes bounds. Here, we review the key steps of
finding PAC-Bayes bounds.
Let \(\mathrm {F} \left(a,b\right)\)  be a convex function in both \(a\)  and \(b\) .
Firstly, a suitable convex function such as \(\mathrm {F} \left(\cdot ,\cdot \right)\)  links the expected loss averaged over the posterior distribution with the empirical loss
averaged over the posterior distribution. Then, by applying Jensen’s inequality, the function over the expectation (posterior distribution) is bounded by the expectation of the function.
By using a change of measure inequality [2]}, we find a bound in terms of a divergence (usually KL-divergence between posterior and prior distributions),
and the expectation of the function over prior distribution. Then, by applying Markov's inequality, we usually bound the expectation of the function with the logarithm
of the confidence parameter.
Thus, the convex function linking the expected and empirical losses is bounded by a complexity term, like \(\mathrm {F} \left(a,b\right)\le c\) .
Usually, a further bounding technique, which we refer to as the ‘affine transformation’, is used to bound the expected loss as an affine transformation of the complexity term. It means that from \(\mathrm {F} \left(a,b\right)\le c\) , one can conclude that \(a\le k\cdot b+\mathrm {G} \left(c\right)\) , where \(k\in \mathbb {R}\)  is a coefficient, and \(\mathrm {G}:\mathbb {R}^+\rightarrow \mathbb {R}\) .
