Generalization Bounds via Information Density and Conditional Information Density

Understand

We present a general approach, based on exponential inequalities, to derive bounds on the generalization error of randomized learning algorithms.

• Using this approach, we provide bounds on the average generalization error as well as bounds on its tail probability, for both the PAC-Bayesian and single-draw scenarios.
• Specifically, for the case of sub-Gaussian loss functions, we obtain novel bounds that depend on the information density between the training data and the output hypothesis.
• When suitably weakened, these bounds recover many of the information-theoretic bounds available in the literature.