  Conformal Prediction (CP) is a distribution-free uncertainty estimation
framework that constructs prediction sets guaranteed to contain the true answer
with a user-specified probability. Intuitively, the size of the prediction set
encodes a general notion of uncertainty, with larger sets associated with
higher degrees of uncertainty. In this work, we leverage information theory to
connect conformal prediction to other notions of uncertainty. More precisely,
we prove three different ways to upper bound the intrinsic uncertainty, as
described by the conditional entropy of the target variable given the inputs,
by combining CP with information theoretical inequalities. Moreover, we
demonstrate two direct and useful applications of such connection between
conformal prediction and information theory: (i) more principled and effective
conformal training objectives that generalize previous approaches and enable
end-to-end training of machine learning models from scratch, and (ii) a natural
mechanism to incorporate side information into conformal prediction. We
empirically validate both applications in centralized and federated learning
settings, showing our theoretical results translate to lower inefficiency
(average prediction set size) for popular CP methods.
