On Leave-One-Out Conditional Mutual Information For Generalization
We derive information theoretic generalization bounds for supervised learning
algorithms based on a new measure of leave-one-out conditional mutual
information (loo-CMI). Contrary to other CMI bounds, which are black-box bounds
that do not exploit the structure of the problem and may be hard to evaluate in
practice, our loo-CMI bounds can be computed easily and can be interpreted in
connection to other notions such as classical leave-one-out cross-validation,
stability of the optimization algorithm, and the geometry of the
loss-landscape. It applies both to the output of training algorithms as well as
their predictions. We empirically validate the quality of the bound by
evaluating its predicted generalization gap in scenarios for deep learning. In
particular, our bounds are non-vacuous on large-scale image-classification
tasks.