  Various approaches have been developed to upper bound the generalization
error of a supervised learning algorithm. However, existing bounds are often
loose and even vacuous when evaluated in practice. As a result, they may fail
to characterize the exact generalization ability of a learning algorithm. Our
main contributions are exact characterizations of the expected generalization
error of the well-known Gibbs algorithm (a.k.a. Gibbs posterior) using
different information measures, in particular, the symmetrized KL information
between the input training samples and the output hypothesis. Our result can be
applied to tighten existing expected generalization error and PAC-Bayesian
bounds. Our information-theoretic approach is versatile, as it also
characterizes the generalization error of the Gibbs algorithm with a
data-dependent regularizer and that of the Gibbs algorithm in the asymptotic
regime, where it converges to the standard empirical risk minimization
algorithm. Of particular relevance, our results highlight the role the
symmetrized KL information plays in controlling the generalization error of the
Gibbs algorithm.
