Understanding Generalization via Leave-One-Out Conditional Mutual Information
We study the mutual information between (certain summaries of) the output of
a learning algorithm and its $n$ training data, conditional on a supersample of
$n+1$ i.i.d. data from which the training data is chosen at random without
replacement. These leave-one-out variants of the conditional mutual information
(CMI) of an algorithm (Steinke and Zakynthinou, 2020) are also seen to control
the mean generalization error of learning algorithms with bounded loss
functions. For learning algorithms achieving zero empirical risk under 0-1 loss
(i.e., interpolating algorithms), we provide an explicit connection between
leave-one-out CMI and the classical leave-one-out error estimate of the risk.
Using this connection, we obtain upper and lower bounds on risk in terms of the
(evaluated) leave-one-out CMI. When the limiting risk is constant or decays
polynomially, the bounds converge to within a constant factor of two. As an
application, we analyze the population risk of the one-inclusion graph
algorithm, a general-purpose transductive learning algorithm for VC classes in
the realizable setting. Using leave-one-out CMI, we match the optimal bound for
learning VC classes in the realizable setting, answering an open challenge
raised by Steinke and Zakynthinou (2020). Finally, in order to understand the
role of leave-one-out CMI in studying generalization, we place leave-one-out
CMI in a hierarchy of measures, with a novel unconditional mutual information
at the root. For 0-1 loss and interpolating learning algorithms, this mutual
information is observed to be precisely the risk.