  This paper presents a general methodology for deriving information-theoretic
generalization bounds for learning algorithms. The main technical tool is a
probabilistic decorrelation lemma based on a change of measure and a relaxation
of Young's inequality in $L_{\psi_p}$ Orlicz spaces. Using the decorrelation
lemma in combination with other techniques, such as symmetrization, couplings,
and chaining in the space of probability measures, we obtain new upper bounds
on the generalization error, both in expectation and in high probability, and
recover as special cases many of the existing generalization bounds, including
the ones based on mutual information, conditional mutual information,
stochastic chaining, and PAC-Bayes inequalities. In addition, the
Fernique-Talagrand upper bound on the expected supremum of a subgaussian
process emerges as a special case.
