PAC-Bayes Mini-tutorial: A Continuous Union Bound
This is an incremental tutorial for machine learning researchers, clarifying theoretical connections in statistical learning.
The paper explains how PAC-Bayesian concentration inequalities relate to traditional results like Hoeffding's and Bernstein's inequalities, highlighting a continuous version of the union bound as the key innovation.
When I first encountered PAC-Bayesian concentration inequalities they seemed to me to be rather disconnected from good old-fashioned results like Hoeffding's and Bernstein's inequalities. But, at least for one flavour of the PAC-Bayesian bounds, there is actually a very close relation, and the main innovation is a continuous version of the union bound, along with some ingenious applications. Here's the gist of what's going on, presented from a machine learning perspective.