PAC-Bayes under potentially heavy tails

Subsequent work developed finite-sample risk bounds for "Bayesian" learning algorithms which specify a distribution over the model [14]. These bounds are controlled using the empirical risk and the relative entropy between "prior" and "posterior" distributions, and hold uniformly over the choice of the latter, meaning that the guarantees hold for data-dependent posteriors, hence the naming. Furthermore, choosing the posterior to minimize PAC-Bayesian risk bounds leads to practical learning algorithms which have seen numerous successful applications [3]. Following this framework, a tremendous amount of work has been done to refine, extend, and apply the PAC-Bayesian framework to new learning problems. Tight risk bounds for bounded losses are due to Seeger [16] and Maurer [12], with the former work applying them to Gaussian processes.