  We present a new family of information-theoretic generalization bounds, in
which the training loss and the population loss are compared through a jointly
convex function. This function is upper-bounded in terms of the disintegrated,
samplewise, evaluated conditional mutual information (CMI), an information
measure that depends on the losses incurred by the selected hypothesis, rather
than on the hypothesis itself, as is common in probably approximately correct
(PAC)-Bayesian results. We demonstrate the generality of this framework by
recovering and extending previously known information-theoretic bounds.
Furthermore, using the evaluated CMI, we derive a samplewise, average version
of Seeger's PAC-Bayesian bound, where the convex function is the binary KL
divergence. In some scenarios, this novel bound results in a tighter
characterization of the population loss of deep neural networks than previous
bounds. Finally, we derive high-probability versions of some of these average
bounds. We demonstrate the unifying nature of the evaluated CMI bounds by using
them to recover average and high-probability generalization bounds for
multiclass classification with finite Natarajan dimension.
