PAC-Bayes Un-Expected Bernstein Inequality

Understand

We present a new PAC-Bayesian generalization bound.

• Standard bounds contain a $\sqrt{L_n \cdot \KL/n}$ complexity term which dominates unless $L_n$, the empirical error of the learning algorithm's randomized predictions, vanishes.
• We manage to replace $L_n$ by a term which vanishes in many more situations, essentially whenever the employed learning algorithm is sufficiently stable on the dataset at hand.
• Our new bound consistently beats state-of-the-art bounds both on a toy example and on UCI datasets (with large enough $n$).