An Information Theoretic Perspective on Conformal Prediction
Authors: Alvaro Correia
Fabio Valerio Massoli
Christos Louizos
Arash Behboodi
Venue: NeurIPS 2024 poster (2024)
Keywords: conformal prediction
information theory
uncertainty quantification
Primary area: probabilistic_methods
TL;DR: We link conformal prediction to information theory, and thus derive a principled way to use side information in conformal prediction, and new upper bounds on the intrinsic uncertainty of the data-generating process, which improve conformal training.

Abstract: 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.

An Information Theoretic Perspective on Conformal Prediction
Alvaro H.C. Correia
Fabio Valerio Massoli Christos Louizos Qualcomm AI Research" Amsterdam, The Netherlands
Arash Behboodi
facorreia, fmassoli, clouizos, behboodi] catbboddd@ttt..quaccc....oommo com
Abstract
Conformal Prediction (CP) is a distribution- 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 general notion of uncertainty, with larger sets associated with higher degrees of uncertainty. In this work, we leverage information theory connect conformal prediction 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 (ūi) 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.
Introduction
Machine learning (ML) models have rapidly grown in popularity and reach, having now found use in many safety-critical domains like healthcare [1] and autonomous driving [28]. In these areas, predictions must be accompanied by reliable measures of uncertainty to ensure safe decision-making However, most ML models are designed and trained to produce only point estimates, which capture only crude notions of uncertainty with statistical guarantees. Conformal prediction (CP) [64], in particular its split variant (SCP) [47], has recently gained in popularity as a principled and scalable solution equip any, potentially black-box, model with proper uncertainty estimates in the form of prediction sets; in loose terms, larger sets are associated with higher degrees of uncertainty.
In this work, we take a closer look at conformal prediction through the lens of information theory (TT). establishing connection between conformal prediction and the underlying intrinsic uncertainty of the data-generating process, as captured by the conditional entropy H (X -Exx [log Pyix] of the target variable Y given the inputs X. We prove conformal prediction can used to bound H (Y)) from above in three different ways: one derived from the data processing inequality, which we dub DPI bound, and two coming from a variation Fano's 's inequality [19], a model agnostic one, which we call (simple) Fano bound, and another informed by the predictive model itself, to which we refer as model-based Fano bound. To the best of our knowledge, these bounds represent the first bridge connecting information theory and conformal prediction, which hope will bring new tools to both fields. We already present two such tools in this paper: (i) we show our upper bounds serve as
Qualcomm Research, Qualcomm Technologies Netherlands B.V (Qualcomm Al Rescarch initiative Qualcomm Technologies, Inc.). 'Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

principled training objectives to learn classifiers that are more amenable to SCP, and (ii) we advance a systematic way to incorporate side information into the construction of prediction sets. In number of classification tasks, we empirically validate that both these applications of our theoretical results lead to better predictive efficiency, i.e., narrower and, consequently, more informative prediction sets.
The rest of the paper is organized as follows. In Section 2, we first introduce the necessary background guide the reader through our main theoretical results. We introduce our three new upper bounds to the intrinsic uncertainty in Section 3, and their applications to conformal training and side information in Sections and respectively. Thereafter, we explore the related work in CP and IT in Section 6, present and analyze our experimental results in Section 7, and finally conclude in Section 8.
2 Background
In this section, we present the needed background on conformal prediction and list decoding [18, 22, 68], an area of information theory that, as we show, is closely related to CP and especially useful in deriving our main results. We start with the necessary notation. As usual, we denote random variables in uppercase letters and their realization in lowercase, e.g., X = x. We reserve calligraphic letters, e.g. X' for sets and use Px. .x....... to denote probability measures on the space X. To simplify the notation, we use P. Q.... when the underlying space is clear. For example, given a probability measure Qxy, the probability of the event {(X, Y): YY C(X)) is denoted as Q(Y C(X)).
2.1 Conformal Prediction
Conformal prediction (CP) is theoretically grounded framework that provides prediction sets with finite-sample guarantees under minimal distribution-free assumptions. Concretely, given a set of n data points (X,, Y,) E X Vi i = ,....,, n drawn from some (unknown) joint distribution PxY. CP allows us to construct sets C(X) E V/ such that for a new data point from the same distribution (Xrest, Ycest) we have the following guarantee for target error rate E (0.
PP E C(Xtest)) 2 1-
where the probability is over the randomness in the sample {(X,, , (( Ytest)) ). To make this more tangible, the reader can picture C(X) as a subset of the possible labels in a classification problem, or confidence interval around the point estimate of a regressor in a regression setting.
In this work, we focus on a variant called split conformal prediction (SCP) [47] that gained popularity in the ML community, since it can leverage any pre-trained model f X + y in the construction of prediction sets. In this setting, the aforesaid n data points constitute a calibration data set Deal which must be disjoint from the training data set used to fit the predictive model f. This separation between training and calibration data is what gives the name split to the method.
The first step in SCP is to define nonconformity score function s X' x y - R, which is itself a function of model f and captures the magnitude of the prediction error at given data point; the higher the score 8 sx, y). the higher the disagreement between input x and prediction y. At calibration time, we evaluate the score function every YY) E Deal to get a collection of scores {S; = sX( Yi) and at test time, we construct prediction set C(Xtest) as
test)
(2) where Quantile(1 - a; {5. is the level 1 - quantile of the empirical distribution defined by {S The central result in conformal prediction, which we restate below for completeness, proves that prediction sets thus constructed achieve marginal valid coverage, i.c., satisfy (1).
C(Xtest) = {y E y s(Xtest> 9) S Quantile(1 - a {S. (co))),
Theorem 2.1 ([31, 64J). If (X,, Y.);, are i.i.d. (or only exchangeable). then for new i.i.d. draw (Xrest, Yrest), and for any a E (0, 1) and for any score function s such that { are almost surely distinct, then C(Xtest) as defined above satisfies
1 1 < IPYeest E C(Xtest)) < 11 Onn
where On a - 1/n41.
See Appendix B for the proof and a more thorough introduction to CP. It is worth noting that valid coverage is not sufficient; the uninformative set predictor that always outputs C(Xtest) = y' trivially satisfies (1). We would also like our prediction sets to be as narrow as possible, and that is why CP methods are often compared in terms of their (empirical) inefficiency, i.e., the average prediction set size D/arl ExPP,.. [(x)] for some test data set Drest- This is, in fact, not the only type of inefficiency criterion, but we use our main performance metric since it the most common [65].

---

We depict the split conformal prediction proce- dure Figure I, where we include two extra variables that will be useful later in the text: the model prediction Y f(X), and the event of valid coverage F = (Y e C())), i.e., the event of the prediction set containing the correct class.
Dcal
C(X)
X
2.2 Conformal Prediction as List Decoding
Figure I: Graphical model of SCP. Deat is cali- bration set, C(X) the prediction set, y f(X) the model prediction, and E the event {Y E C(X). Square and round nodes are, respectively, deter- ministic and stochastic functions of their parents.
In a nutshell, we can see conformal prediction as defining a map from an input to a set of candidates in the target set V. It turns out that the conformal prediction framework is equivalent to (variable-size) list decoding, an error-recovery model going back the works of Elias [18] and Wozencraft [68] in communication theory- we review some of these results in Appendix C.2. In particular, consider the mapping from the true label y to the input x as a noisy communication channel p(xly). The goal of an error-correcting code is then to decode the input v and recover the one true label y. List decoding generalizes this idea, allowing the decoder to return a set of outcomes (a list) instead of a pointwise prediction. the correct solution is not part of the set output by the decoder, an error is declared. Although conformal prediction and list decoding were developed for different purposes, namely uncertainty quantification and error correction, it is easy to see that, if we allow for variable-size lists, the list decoding problem for the channel p(xly) (y) as described above is equivalent to the conformal prediction problem.
To our knowledge, this link between conformal prediction and information theory (and list decoding in particular) has gone unnoticed in the literature, and in this paper we leverage First, we apply information- theorettic inequalities for list decoding to upper bound the conditional entropy (Y|X) of the data-generating process. This leads to new objectives for conformal training (see Section 4) and new bounds on the inefficiency of given model (see Appendices E and G.3). Second, the information-theorete interpretation CP gives us an effective and theoretically grounded way of incorporating side-information into CP to improve predictive efficiency (see Section 5).
two directions.
3 Information Theory Applied to Conformal Prediction
In this section, we develop our main results, which link information theory and conformal prediction. Concretely, we provide three novel upper bounds on the conditional entropy H(YIX): one coming from the data processing inequality and two derived in similar way to Fano's inequality. We defer the proof's to Appendix D for the sake of conciseness, but in broad strokes, results come from relating the bounds on the error probability provided by these coormation-theoreee inequalities (typically in the context of error-correcting codes) to the guarantees provided by CP in Theorem 2.1.
3.1 Data Processing Inequality for Conformal Prediction
We start by using the classical data processing inequality (DPI) in the context of conformal prediction. Specifically, we focus on the DPI for f-divergences, which we discuss thoroughly in Appendix C.I. In brief, for convex function with (1) = 0, the f-divergence between two probability measures P and Q is defined as (see [58))
dP dQ
(y(l)) Eo
In particular, with f(x) = x log x we recover the familiar notion of KL-divergence [27]. The DPI for f-divergences states that for any two probability measures Px and Qx defined space X, and any map Wylx, which maps (Px, Qx) to (Py,Qv), Qy), we have
(x(xx|1Qx) 2 Dy (Prl(Qv).
We can apply the DPI for /-divergence above in the context conformal prediction by considering the probability of the event of valid coverage (Y E C(X)) under two different probability measures P and Q. Taking P as the data-generating distribution P Px PYlx and constructing Q == Px Qyix for arbitrary Qyix (c.g., machine learning model), get the following proposition.
3

---

Proposition 3.1 (DPI Bound), Consider any conformal prediction method satisfying the upper and lower bounds of Theorem 2.1 for a E (0, 0.5). For any arbitrary conditional distribution Qyxx , the true conditional distribution Pyix and the input measure Px, define the following two measures Q = X and P == PxPyjx Then, we have
x - (a) + (1 - aa) log Q(Y E C(X)) + on log Q(Y & C(X)) - Ep [log Qyix] (3) with On a 1/++1 and (-) the binary entropy function ha(a) = -a log(() (a) - - aa--allog log(1 a)-
Note that the entropy term (X)) computed using the measure P. We relegate the proof to Appendix D.I. In the bound in (3), the term Q(Y E C())) appears inside log, so an empirical estimate Q(Y E C(X)) would result in lower bound and would be biased. We can provide an upper confidence bound on this estimate using the empirical Bernstein inequality [41] and use that instead. Based on the empirical Bernstein inequality, with probability 1 - ō, we have
As(Z,n) 2V. (Z) log(2/8)
7 (2/(2
+
n
3(n - 1)
Q(Y E C(()) & Q(V E(()) + As = -Q(Y& E C(()),
Q(Y & C(X)) s Q(Y & ((X)))As((2 (Z. = =Q( C(X)), with (Z) the empirical variance of Z = (7,,..., 7,), 7:= Q(u E c(())). Using these bounds,
we get the following inequality with probability 1
x( & (a) + (1 (1-a) log Q(Y E CC(X) + on log Q(Y & (C(X)) - Ep [lg Qyix]- (4) This upper bound is one of our main results, which we dub the DPI bound. Note that for the last expectation, we can use the empirical estimate, as it is an unbiased approximation.
3.2 Model-Based Fano's Inequality and Variations
Next, we present an inequality which is a variation of Fano's inequality [19], a classical result that, among other things, used to prove Shannon's 's classical theorem on channel capacity. See Appendix C.4 for more details. In our context, we can use Fano's 's inequality to relate the conditional entropy (Y the probability of error, i.c., IYY & C(X)). From that insight, we obtain Proposition 3.2 by modifying the classical proof of Fano's 's inequality, which can be found in [14], and applying the conformal guarantees from Theorem 2.1 to bound the probability of error.
Proposition 3.2 (Model-Be Model-Based Fano Bound), Consider any conformal prediction method satisfying the upper and lower bounds of Theorem 2.1 for a E (0, 0.5). Then, for the true distribution P, and for any probability distribution Q, we have
H(YIX) < hs(a) + alE Py, P
[- lol Xxxxx0(x)xxxex0))
+ (1 - 0t,) Epy. VEC(x) [- log QYIx.C(x) (5)
Note that we have one term conditioned on the event of valid coverage, (Y C(X)). and another conditioned on {Y & C(X)}. We provide the proof in Appendix D.2. A good choice for Q is the predictive model itself, and that why we refer the bound above as Model-Based (MB) Fano bound. Another natural choice for Q is the uniform distribution, which gives us the following result. Corollary 3.1 (Simple Fano Bound). Consider any conformal prediction method satisfying the upper and lower bounds of Theorem 2.1 for a E (0, 0.5). Then, for the true distribution P we have
H(IIx) < ha(a)) + P.B.y, ec(o) [log( [1 (C(X))
(1 a..) Ery.x. [log [C(X)]] (6)
The proof follows directly from Proposition 3.2 by replacing Q with the uniform distribution. We refer the bound in (6) as (simple) Fano bound, since is model agnostic and can be approximated directly with only empirical estimates of the prediction set size. This last bound explicitly relates the central notion of uncertainty in conformal prediction, the prediction set size, an information- theoretic concept of uncertainty in (X)).. This reinterpretation of conformal prediction as a form of list decoding introduces various informmaiion-heoretiie tools, potentially useful for various applications. In Appendix E we derive some new inequalities for conformal prediction, in particular offering new lower bounds on the inefficiency of the conformal prediction. In the next section, we discuss how these inequalities can be used as conformal training schemes.

---

4 Conformal Training
Although split conformal prediction is applicable to any pretrained ML model post-processine step, the overall performance of any CP method (commonly measured by its inefficiency) is highly dependent on the underlying model itself. Therefore, previous works have proposed take CP into account already during model training and directly optimize for low predictive inefficiency [8, 13, 61]. We use the term conformal training to refer to such approaches in general (see Appendix F for an overview of the topic). In particular, we focus on ConfTr [61] since generalizes and outperforms [8]. In ConfTr [61] each training batch B is split into calibration Beat and test Btest halves to simulate the SCP process (see Section 2) for each gradient update of model f and minimize the following size loss
log [x]]] ~ log 3/11roacl
Σ [cy(x)] Bre
where (ar) is constructed using the statistics of the nonconformity scores computed on Beat- We use the notation Cy (x)) to emphasize the dependence of the prediction set on model f. Still, SCP involves step functions and Stutz et al. [61] introduce two relaxations to recover a differentiable objective: (i) the computation of quantiles is relaxed via differentiable sorting operators [9, 17, 50]; (ii) the thresholding operation in the construction of prediction sets in (2) is replaced by smooth assignments via the logistic sigmoid. The latter relaxation gives "soft" prediction sets C (zr). which contain each of the labels E y with a certain probability. See Algorithm for a depiction of conformal training.
Our upper bounds on (Y)))), namely DPI, MB Fano and simple Fano, presented in the previous section can be made differentiable the same way, and thus can also serve as proper loss functions for conformal training. The motivation for doing so is twofold. First, the conditional entropy (Y) captures the underlying uncertainty of the task, or equivalently, the uncertainty under the true labelling distribution Pyix. Thus, by minimizing these upper bounds, we can hope to push the model f closer to the true distribution, which is known to achieve minimal inefficiency [65]. Interestingly, the cross-entropy loss also bounds HY| X) from above and thus be motivated as conformal training objective from the same angle. In that regard, the DPI bound from Proposition 3.1
is particularly advantageous it is provably tighter than the cross-entropy (sce Appendix D.1).
Second, we can connect the simple Fano bound from Corollary 3.1 the size loss (7) from [61]. In Appendix F.1, we show that via Jensen's 's inequality and log( |Y (Y|-IC(X))) I log [Y] the bound in (6) can be further upper bounded as
X, == ha(aa + a log \ - (1 - a. -1),
E Since da and (1 a.))) are constants, they do not affect optimization, and minimizing the right hand side in (8) is equivalent to minimizing the size loss in (7). Therefore, we ground ConfTr as minimizing an upper bound to the true conditional entropy that looser than the simple Fano bound and likely also looser than the model- Fano bound for an appropriate choice for Q.
H(| Aa (1 a..) I [[C()]]]],
(8)
Algorithm 1: Conformal training algorithm.
input : batch of labeled samples B, model f. a loss function C that can be any of our upper bounds (4), (5) or (6) or a version of (7)-sce variants (25) and (26) in Appendix F. for each training batch B do
split B into Beal and Brest for each (Ix, V/)) Beal do
compute score = (y vi)
sort scores (in a differentiable manner) obtaining $(1) < 8(2) <... < ((Baa)))
set [0( (1]]
// get 1 quantile estimate using Bant
for each (z), E Blest do
for each y E y do
// Construct soft prediction set // Bounds (4) and (5) also require class probabilities under Q, which in this case are given by the model f(x,)
(C((,,, + o (z(;
compute loss according to L on Blest using yy Cx,,,) and if needed f(x,))
update of via gradient descent to minimize loss
5

---

5 Side Information
With the information theoretical interpretation of conformal prediction, we can translate various intu- itions from information theory, for example, about different types of channels or network information theory, to conformal prediction. In this section, we consider the notion of side information.
Let X be the input covariates, Y be the target variable, Z be some side information about the task, and let Qyxx be the model which we use to perform conformal prediction. As we can relate CP with Qrix an upper bound on the conditional entropy HY|)X), we would like do the same for the case of the conditional entropy when side information is available, i.e., H XY) Z). Since we know that the conditional entropy directly affects the expected set size, i.e. the inefficiency of CP, and given that H (Y 2 HY||X, Z) can expect that with the additional side information the inefficiency of CP will decrease. We can take side information into account by defining conformity scores as a function of Qy|x,z instead of Qyxx- A simple way do that would be via the Bayes rule
Q2IXQRIXY QrIx,z = Er QYIXQIIXY
(9)
where Q is an auxiliary model that predicts the side information given the input and target variables. Such a model could be learned separately from the main model Qyix given access to a dataset Daide- = {( Mis 2:)]. Therefore, we can now calibrate with CP by taking into account the side information and then, at test time, given access to the input and side information, we can use the appropriate probabilities Qy x.z to construct the prediction sets. Intuitively, the prediction sets from such a procedure should be smaller than the prediction sets obtained from using Qy x directly. It should be noted that, in the case of side information not being available, we can marginalize Qy. x over Z, which, by construction, falls back to the original model Qrix- If the availability pattern of Z consistent between the calibration and test sets, the conformal prediction guarantees still hold by defining the model as
Qrixx 1 1rxx
if Z is observed otherwise.
(10)
With this addition to the split conformal prediction tool set, if new (side) information is made available at test time, we can properly incorporate it into the CP pipeline without having to retrain the main classifier. One needs only train an auxiliary classifier Qz which might be much simpler than Qyix (in our experiments, Q2ix,y is given by single linear layer) and require much less data. One notable example of side information arises naturally the distributed setting, which we discuss next.
5.1 The Distributed Learning Setting
Consider the case where we have a dataset that is distributed among set of m devices and want to run conformal training to get a global model Qy trained on all the data. Further, assume it is hard to gather the data at central location (e.g., due to privacy reasons), and thus have to work with the data staying locally on each device. An example of this would be federated learning (or FL) [42]. In this case, if Z (1...., m) identifies the device, the entropy (Y can be expressed
X ( Z)
= Ep [H( Z = =)] + I(Y; Z(X),
which decomposes into weighted average of local entropy functions H(Y|X, 7 = =). We can now
use any of our proposed bounds for each of the conditional entropies H [, 7 = 2) by calibrating with CP independently each device, ending up with
X(YIX) < Ep [H (Y X, 2 = =)] + 2|X),
where Hab [Y| 2 = 2) corresponds to an upper bound of the conditional entropy H HY = 2). Furthermore, for the mutual information term we have that
pzix, Pzix
T(;; Z(x) E.Z.x
log
< Erzx
[- log P2Ix] < Er [- log Qzix]
where the first inequality is due to Z being discrete and having non-negative entropp and the second is due to Gibbs inequality with Qz x being an auxiliary model trained to predict the user id Z

---

given input X = A similar upper bound has been considered before in federated setting [36]. With this upper bound we get
H(Y S Bry [V|X, 2 - 1x [log =Z=e|x]]
(11)
This gives us an upper bound on the entropy of the entire population that decomposes into sum of local functions, one for each client, only requiring local information. Thus, we can easily carry out conformal training for Qylx by minimizing this upper bound in the federated setting with, e.g., federated averaging [42]. At test time, we can take the device ID as side information. To this end, we can either train a model Q in parallel and use (9) with the global model Qy test time to get Q or we can obtain Q/1x, z by fine-tuning the global model Qrjx x with local data.
6 Related Work
Conformal prediction, a powerful framework for uncertainty quantification developed by Vovk and collaborators [60, 64], has recently witnessed a wide adoption in many fields, e.g., healtheare [3, 38,3,,35 39, 48] and finance [6, 67]. The marriage of conformal prediction and machine learning has been especially fruitful. Since the seminal work by Vovk al. [64], many extensions and applications have been proposed, covering topics such as survival analysis [10], treatment effect evaluation [32],
classification [4, 21] and regression [54] settings, risk control [5, 7], and covariate shift [62].
To our knowledge, our work represents the first attempt to bridge conformal prediction and information theory. Among other things, this allows to build on the conformal training ideas of Bellotti [8] and Stutz et al. [,]], deriving principled learning objectives that generalize their approaches, dispense with some of their hyperparameters and result in more efficient prediction sets. Further, we empirically show that our conformal training objectives provide a strong enough learning signal to train complex architectures from scratch, with strong results ResNet-34 and ResNet-50 [23] fitted CIFARIO and 100, respectively. In contrast, the previous tfte-of-theear approach, ConfTr, struggles in those settings (see experiments in Section 7) and required pretrained models for consistent results [61]. Further, our iioommation-hhooeetii interpretation of CP provides a new simple and effective mechanism to leverage side information in split conformal prediction. We unaware of any other approaches to treat side information within the conformal prediction framework in the literature.
On the information theory side, the notion of f-divergence and related inequalities have appeared in many different works. The use of f-divergence goes back to works Ali and Silvey, Csiszár, and Morimoto in the 60s, as in, for instance, [2, 15, 44]. A key f-divergence inequality is the data processing inequality- see [57, 58] for an extensive survey. It provides a unified way of obtaining many classical and new results, including Fano's 's inequality [19]. The tightness of the data processing inequalities is discussed in terms of Bregman's 's divergence in [12, 34] and in terms of x 2-divergencce in [57]. List decoding, which is closely connected CP, was introduced in the context of communication design by Elias [18] and Wozencraft [68]. A generalization of Fano's 's inequality to list decoding was given in [16] in the context of multi-user information theory, also the general Fano inequality for list decoding presented in [53]. Variable-size list decoding was discussed in [57] using ideas first introduced in [52] and [35]. A selection of relevant inequalities for list decoding can be found in [57].
7 Experiments
In this section, we empirically study two applications of our theoretical results, namely conformal prediction with side information and conformal training with our upper bounds on the conditional entropy as optimization objectives. We focus our experiments on classification tasks since this is the most common setting in previous works in conformal training [8, 13, 61].
7.1 Conformal Training
We test the effectiveness of our upper bounds as objectives for conformal training in five data sets:
MNIST [29], FaSHion-MNIST [69], EMNIST [11], CIFARIO and CIFAR [25]. In addition to
our three upper bounds, we also evaluate the cross-entropy loss (CE, also another upper bound to
the entropy), and the two main variants proposed in [6]], namely ConfTr, which minimizes (7) and
ConfTretas that optimizes an additional classification loss term (see Appendix F). We follow similar
7

---

Table I: Inefficiency results for conformal training in the centralized setting. We report the mean prediction set size (# standard deviation) across 10 different calib./test splits for a = 0.01, showing in bold all values within one std. of the best result. Results for THR and APS correspond to different models trained with different hyperparameters (see Appendix G). Lower is better.
Method
MNIST
F-MNIST
EMNIST
CIFAR 10
CIFAR 100
THR
APS
THR
APS
THR
APS
THR
APS
THR
APS
CE
2 2.20
2.50go.0s
2.39
24
2.06 3.402a.8
1.69
2.34g0.22
19.70=2.05
26 26.02.1.a1
ConfTr
6.28
2.10
1. 1.73.0.00
1.8 1.00
1.99-0.10
2.36-0.11
9.90=a.02
9.98+0.00
32.80+2.75
40.58+122
ConfTreus
2.09
2.13
5.11
1.79
2.01
2.38
2.16.0.09
2.15
60.48ga.07
32.91
Funo
2.09 2.12.0.08
o. 0.87
2.10_o.11 2.75
2.0520.05
2.
40.30g1:10
33.8040.5
MB Fano
2.24:0.12
2.4920.15
1.80=0.08
2.25 14
2.01
3.6749.8
1.66:0.00
1.8920.00 00
=0.61
21.08+1.44
DPI
2.24.017 2.6420.07
1.73300.7
2.08g0000
1.98_000 4.07ga.3
1.64.0.7
1.97
17.55
17.41
optimization procedure and experimental setup to that of [61], but with the key differences that we learn the classifiers from scratch in all cases (without the need of pretrained CIFAR models), and that we use the larger "by class" split of EMNIST. For each data set, we use the default train and test splits but transfer 10% of the training data to the test data set. We train the classifiers only on the remaining 90% of the training data and, at test time, run SCP with 10 different calibration/test splits by randomly splitting the enlarged test data set. See Appendix G for a complete description of the experimental setup, with extra results and details on model architectures and hyperparameter search.
In Table 1, we report the empirical inefficiency on test data considering two SCP methods, threshold CP with probabilities (or THR) [56] and APS [55]-see Appendix G.1.1 for results with RAPS [4]. In all cases, our upper bounds proved effective loss functions to train efficient classifiers end-to-end and from seratch. For the simpler data sets (MNIST, FasHion-MNIST and EMNIST), all conformal training methods achieved similar results. but both ConfTr methods proved less consistent. This is noticeable in the oftentimes sharp difference in performance between THR and APS, since even after fine-tuning the hyperparameters (see Appendix G) some of the models failed to converge properly. For the remaining and more challenging data sets, both ConfTr variants lagged behind, probably because they do not provide strong enough signal train ResNets from scratch (on CIFAR data sets, Stutz et al. [61] only used ConfTr to fine tune pretrained models). A similar observation applies to the simple Fano bound (6), where the relaxed prediction set size is the only learning signal.
In all experiments, we run conformal training with a target coverage rate of 99%, i.e., a = 0.01. It is then important to assess whether the performance of the resulting models deteriorates at different coverage rates, "overfitting" to the value of a used for training. In Table 2. we see how inefficiency varies with at test time for models trained via conformal training with can contrast their performance against that of models trained via the CE loss, which is agnostic to the desired coverage rate. In all cases, our model- Fano and DPI bound performs best with the THR and APS methods, respectively, proving conformal training is worthwhile even if the desired coverage rate might vary at test time. Still, as noticed in [61], there is a drop in performance in comparison to the CE loss for higher values of a at test time. This could be due to some degree of overfitting, but could also be attributed to the conformal prediction problem becoming easier for lower coverage rates, thus reducing the gap between our bounds and the CE loss.
0.01. In particular,
Table 2: Inefficiency results with varying a at test time. Average prediction set size on CIFARI 100 for different a targets at test time, averaged across 10 random calib./test splits. All methods were only optimized for 0=0.11 The models used for THR and APS might not be the same according to the best hyperparameters found in Table 11. Lower is better.
Method
0.01
0.05
0.1
THR
APS
THR
APS
THR
APS
CE
19.70+2.0n
26.02-1.a1
6. 6.
9.19+0.34
3,02+0.10
4.52+0.12
ConfTr
32.8012.7
40.58_1.23
12.2510.47 21.60
7.1310.23
14.58 10.47
ConfTraue
66. 66.4843.77
32.9121.53
14.18
16.8020.00
8.90
11.29.0.42
Fano
40.30+1.10
33.80_0.93
19. 19.433+0.a so
11. 11.46+n.58 16.17
9.72+0.25
MB Fano
14.61
21. 21.68_1.44
5.24
9.25
2.88
0.05
5..1
DPI
17.55
17.41:0.a2
6. 6.26
6. 6.98
3.33
4.08#a.14
8

---

7.2 Side Information
As a first experiment, we consider datasets for which a natural grouping of the labels exists and use the group assignment as side information Z. In CIFARI00, there is disjoint partition of the 100 classes into 20 superclasses, so we define as the superclass to which example (æ, y) belongs. In EMNIST, indicates whether the example is digit, uppercase or lowercase letter. We train an auxiliary model R and, at test time, assume access to side information 2 to recompute class probabilities Qy|x.z= from the original classifier Qyix as in equation (9).
We report results for two different scenarios in Table 3. The first is the standard SCP setting, where we assess the inefficiency of THR and APS methods, with side information Z observed for 10, 30 and 100% of the instances. We redefine the classifier / as in (10) to account for when Z is missing, but otherwise, the SCP process remains unchanged. The second scenario is Mondrian or group-balanced CP [64], where one splits Peat into groups and rums CP for each of them individually. In this setting, we group the calibration data points according to 2 and base the score function on Qyix,z 12 In all cases, taking the side information into account reduced the inefficiency considerably.
Table 3: Inefficiency results with side information. We report the mean prediction set size (+ std.) across 10 different calib./test splits for a = 0.01. The side information is the superclass assignment for CIFAR and whether the class is a digit uppercase letter lowercase letter for EMNIST.
Method
CIFAR 100
EMNIST
THR
APS
Acc.(%)
THR
APS
Acc.(%)
CP
19.70=2.05
26.0221.31
72.22
2.06
3.37
85.74
CP w/ 10% SI
18. 18.13
23.5942.us
72.84
1.91-u.u7
2.18+0.09
86.93
CP w/ 30% SI
15.74
21.63
74.83
1.69_0.05
1.88
89.43
CP 100%
10.28
15. 15.65
78.72
1.06_0.02
1.07
97.65
Group CP
1..59
21. 21.92+1.80
72.22
2.32_o.14
2.6840.11
85.74
Group CP w/ 100% SI
9.07
13. 13.1640.08
78.72
1.14_0.03
1.1640.04
97.65
7.3 Federated Learning (FL)
A practically relevant application of side information arises in FL,, where we can take the device ID side information Z. In the federated setting, train two extra heads on top of the main classifier, one computing Q2ix so that we can optimize the proper upper bound in (11), and another computing Q2IX.Y (while detaching gradients to the main classifier so as not affect the upper bound optimization) that we use to integrate side information into CP using (9). Besides being a practically relevant application of side information to CP, FL also serves as a more challenging test bed for our conformal training methods, which has not been explored in previous work. We ran federated averaging [42] with CE, ConfTr, ConfTrelas- and our upper bounds as local loss functions. In this setting, we consider CIFARIO, CIFAR100, and EMNIST with 100, 500, and IK devices, resp. We assign data points to devices imposing a distribution- based label imbalance [33], i.e., we sample a marginal label distribution for each device from Dirichlet distribution Dir(1.0). See Appendix G for results with (0.(0.5) and (0.(.. As hyperparameter search in FL is notably challenging and costly [66], we keep the same hyperparameters found for the centralized case in Section 7.1.
After convergence, we ran SCP with the final global model assuming calibration and test data sets at the server, or equivalently that the clients share their scores with the server. This reflects the best inefficiency results we can hope for with the global model, as in practice we might need to resort to privacy-preserne
methods that are likely to hurt performance. See Appendix G for a discussion and extra results on other possible settings. We report inefficiency results for the global model with THR in Table 4 (see Table 5 in the appendix for APS results), where we observe similar trends to the centralized experiments in Table ConfTr methods still perform well on EMNIST but struggle on CIFAR data (with the notable exception on CIFAR100 where ConfTr excelled) while our methods delivered consistent results across all data sets This probably reflects the sensitivity of both ConfTr objectives to hyperparameters, which makes them hard to use in practice, especially in FL where hyperparameter optimization is difficult. Conversely, our bounds seem more robust to such variations, as the hyperparameters found in the centralized setting seem to translate well to the federated case.

---

Table 4: Inefficiency results for conformal training in the federated setting with THR. We report the mean prediction set size (= standard deviation) of the global federated model across 10 different /alib./test splits for a 0.01 and using THR. We +si indicate the inclusion of side information. We show in bold all values within one standard deviation of the best result. Lower is better.
Method
EMNIST
CIFAR 10
CIFAR 100
THR
THR 1st
THR
THR
THR
THR
CE
2.46+0.02 2000
2.73+0.04
2.30
55.41=1.09
52.31
ConfTr
4.60
3.30
10.00+0.00
10.00
45.60=1.30
41.18
ConfTrates
2.88
1.98
3.5310.00
3.39
58.53=1.40
56.03 1.29
Fano
2.63:..02
2.37110.0
2.39 00.07
2.07=0.07
47.91
41.1 1..02
MB Fano
2.84
2.25+20.03
2.52
2. 2.04=0.07
52.94=1.40 1.40
46.97 +97771133
DPI
2.60
2.23
2.76+0.07
+..03
62.36
00.74
Table 5: Inefficiency results for conformal training in the federated setting with APS. We report the mean prediction set size (= standard deviation) of the global federated model across 10 different calib//test splits for a = 0.01 and using APS, We use +SI to indicate the inclusion of side information. We show in bold all values within one standard deviation of the best result. Lower is better.
Method
EMNIST
CIFAR 10
CIFAR 100
APS
APS
APS
APS
APS
APS
CE
3.6940.03
3.1440.04
2.83
2.43
64.73
62.67
ConfTr
6.14
5.25.10.01
10.00 0.000
10.00
18.18
47.58 1.48
ConfTralss
2.65
2.42:0.02
10.00
10.00
99.92:1000
99.91
Fano
3.12:2004
2.7240.03
2.73=0.07
2.39=o.oo
26.95
=2.75=0.91
MB Fano
4.75+0.03
2. 2..3
2.79
2.33
50.72=1.77
45.72++1.8
DPI
2.98 03
2.5810.02
2.68 10
2.22:0.09
51.29=1.07
17.18
One marked difference between Tables I and 4 is that the simple Fano bound (6), which lagged behind the DPI bound and its model-based counterpart in the centralized setting, achieved the best results on the federated setting. We hypothesize this could be due to overfitting of the local optimization procedures to the individual data distribution of each device, which hurts the convergence of the global model. This effect exacerbated on CIFAR100, where we have 500 devices, each of which with very few data points. The simple Fano bound is less vulnerable to such overfitting since it relies on the main classifier to a much lesser degree. Finally, in almost all cases, our bounds outperformed the CE loss, reassuring the potential of conformal training. Moreover, the inclusion of side information reduced inefficiency in all settings, and markedly so few instances. This confirms the effectiveness of our side information approach in a complex and practically relevant scenario, like federated learning.
8 Conclusion
In this work, we established a link between notions of uncertainty coming from conformal prediction and information theory (or more precisely variable-size list decoding). We proved that one can use split conformal prediction methods to upper bound the conditional entropy of the target variable given the inputs, and that these upper bounds form principled objectives for conformal training. We empirically validated our approach to conformal training, with strong results in both centralized and federated settings. Furthermore, the ieformation-thooreee rigorous approach to incorporate side information into conformal prediction, which we experimentally show leads to better predictive efficiency. To the best of our knowledge, this the first attempt at connecting information theory and conformal prediction. Given the limited communication between these two research communities thus far, we expect our work to incite a fruitful exchange of not only ideas but also theory and algorithms between these two research domains. In this paper, we concentrated our exposition and experiments in classification tasks, but we see an extension of our methods to the regression setting, particularly promising avenue for future work.
perspective also offers simple yet
10

---

References
[1] Ahsan, M. M., Luna, S. A., and Siddique, Z. Machine-learning-aasee based disease diagnosis: com- prehensive review, Healthcare, 10(3), 2022. ISSN 2227-9032. doi: 00.339/heealhccarr100.000 URL https::t/.. : /www. m
com 9032/10/3/541.
[2] Ali, S. M. and Silvey, S. D. A General Class of Coefficients of Divergence of One Distribution from Another. Journal of the Royal Statistical Society. Series (Methodological), 28(1):
131-142, 1966. Publisher: [Royal Statistical Society, Wiley]. 7,21
[3] Alnemer, L.. M., Rajab, I.., and Aljarah, I. Conformal prediction technique predict breast. cancer survivability. Ins Ady Sci Technol, 96:1-10, 2016.
[4] Angelopoulos, A., Bates, S., Malik, J., and Jordan, M. I. Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv:2009. /4 14/93, 2020. 7, 32
[5] Angelopoulos, A. N., Bates, S., Candès, E. J., Jordan, M. I,, and Lei, L. Learn then test: Calibrating predictive algorithms achieve risk control. arXiv preprint lr.iv:21
2021.
[6] Bastos, J. A. Conformal prediction of option prices. Expert Systems with Applications, 245: 123087, 2024.7
[7] Bates, S., Angelopoulos, A., Lei, L., Malik, J., and Jordan, M. Distribution-free, risk-controlling prediction sets. Journal of the ACM (JACM), 68(6):1-34, 2021. Publisher: ACM New York, NY.
[8] Bellotti, A. Optimized conformal classification using gradient descent approximation. arXiv preprint arXiv:2105. 2021. 5, 7, 15, 28
[9] Blondel, M., Teboul, O., Berthet, Q., and Djolonga, J. Fast differentiable sorting and ranking.
In International Conference on Machine Learning, pp. 950-959 PMLR, 2020. 5, 28, 29
[10] Candès, E. J., Lei, L., and Ren, Z. Conformalized survival analysis. arXiv:2103.09763 2021. 7
arXiv preprint
[11] Cohen, G., Afshar, S., Tapson, J., and Van Schaik, A. Emnist: Extending mnist to handwritten letters. In 2017 international joint conference on neural networks (IJCNN) pp. 2921-2926. IEEE, 2017. 7,30
[12] Collet, J.-F. An Exact Expression for the Gap in the Data Processing Incquality for f Divergences. IEEE Transactions Information Theory, 65(7):4387-4311, July 2019. ISSN 1557-9654. 7,
[13] Colombo, N. and Vovk, V. Training conformal predictors. In Conformal and Probabilistic Prediction and Applications, pp. 55-64. PMIR, 2020. 7, 15, 28
[14] Cover, T. M. and Thomas, J. A. Elements of information theory. Wiley-Interscience, Hoboken, N.J, 2nd ed edition, 2006. 4, 18
[15] Csiszár, On topological properties of f-divergence. Studia Sci. Math. Hungar., 2:330-339, 1967. 21
[16] Csiszár, I. and Körner, J. Information theory: coding theorems for discrete memoryless systems. Cambridge University Press, Cambridge: New York, 2nd ed edition, 2011. 7, 21
[17] Cuturi, M., Teboul, O., and Vert, J.-P. Differentiable ranking and sorting using optimal transport.
Advances neural information processing systems, 32, 2019. 5, 28
[18] Elias, P. List Decoding for Noisy Channels. In IRE WESCON Convention Record, 1957,
volume 2, pp. 94-104, 1957. 3, 7, 19,21 21
[19] Fano, M. The transmission of information, volume 65. Massachusetts Institute Technology, 1949. 1, 4, 7, 21, 24

---

[20] Gallager. R. G. Information theory and reliable communication. Wiley, New York, NY, 1986. ISBN 978-0-471-29048-3, 21
[21] Gupta, C., Podkopaev, A., and Ramdas, A. Distribution-fres binary classification: prediction sets, confidence intervals and calibration. Advances in Neural Information Processing Systems, 53:3711-3777 2020. 7
[22] Guruswami, V. List decoding of ertor-correcting codes: winning thesis of the 2002 ACM doctoral dissertation competition, volume 3282. Springer Science & Business Media, 2004.
21
[23] He, K., Zhang, X., Ren, S., and Sun, Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778,
2016.7 7
[24] Humbert, P., Le Bars, B., Bellet, A., and Arlot, S. One-shot federated conformal prediction. In International Conference on Machine Learning, pp. 14153-14177. PMLR, 2023. 33
[25] Krizhevsky, A. et al. Learning multiple layers of features from tiny images, 2009. 3,
[26] Kuchibhotla, A. K. Exchangeability, conformal prediction, and rank tests. arXiv preprint arXiv:200..06095 2020. 15, 16
[27] Kullback, S. and Leibler, R. A. On information and sufficiency. The annals of mathematical statistics, 22(1):79-86, 1951. 3
[28] Kuutti, S., Bowden, R., Jin, Y., Barber, P., and Fallah, S. A survey of deep learning applications to autonomous vehicle control. IEEE Transactions on Intelligent Transportation Systems, 22(2):
712-733, 2020.
[29] LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1))6(1))))))) 86(11):2278-2324 1998. 30
[30] Lei, J. and Wasserman, L. Distribution-fies prediction bands for non por-marreettrcc regression. Journal of the Royal Statistical Society Series B: Statistical Methodology, 76(1): 2014. 17
[31] Lei, J., G'Sell, M., Rinaldo, A., Tibshirani. J., and Wasserman, L. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 113(523):1094 1111, 2018. 2, 17
[32] Lei, L. and Candès, E. J. Conformal inference of counterfactuals and individual treatment effects. Journal the Royal Statistical Society: Series B (Statistical Methodology). 2021. Publisher:
Wiley Online Library. 7
[33] Li, Q., Diao, Y., Chen, and He, B. Federated learning on non-iid data silos: An experimental study. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pp. 965-978. IEEE, 2022. 33
and
[34] Liese, F. and Vajda, I. On Divergences and Informations in Statistics and Information Theory. IEEE Transactions on Information Theory, 52(10):4394-4412, October 2006. 7, 21
[35] Liu, J.. Cuff, P., and Verdú, S. ey--Resovvaiility IEEE Transactions on Information Theory, 63
(5):2629-2658 May 2017. Conference Name: IEBE Transactions on Information Theory. 7, 21
[36] Louizos, C., Reisser, M., and Korzhenkov, D. A mutual information perspective on federated contrastive learning. In The Twelfih International Conference Learning Representations, 2024. URL htttpas//openrvviiee
aet//forummidddJJmPOOOuKKK 7
[37] Lu, C. and Kalpathy- J. Distribution-free federated learning with conformal predictions. arXiv preprint 2rX1::211000766,,0000 2021, 33
12

---

[38] Lu, C., Angelopoulos, A. N., and Pomerantz, S. Improving trustworthiness of ai disease severity rating in medical imaging with ordinal conformal prediction sets. In International Conference on Medical Image Computing and Compuler-Assisted Intervention, pp. 545-55455 445-554. Springer, 2022.
[39] Lu, C., Lemay, A., Chang, K., Höbel, K., and Kalpathy-Cramer J. Fair conformal predictors for applications in medical imaging. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 2208-11216, 2022. 7
[40] maintainers, T. and contributors. Torchvision: Pytorch's computer vision library. https:
//github. httn/pyyoorc/viisionn 2016. 30, 40
[41] Maurer, A. and Pontil, M. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:09077.37400 2009. 4, 22
[42] McMahan, B., Moore, E.,, Ramage, D., Hampson, S., and y Arcas, B. A. Communication efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273-1282. PMLR, 2017. 6, 7, 3,
[43] Merhav, N. List Recoding-Random Coding Exponents and Expurgated Exponents. IEEE Transactions on Information Theory, 60(1 1):6749-6759, November 2014. ISSN 1557-9654. Conference Name: IEEE Transactions on Information Theory. 20
[44] Morimoto, T. Markov Processes and the H-Theorem. Journal of the Physical Society of Japan, 18(3):328-4 331, March 1963. Publisher: The Physical Society of Japan. 7,21
[45] Moritz, P., Nishihara, R., Wang, S., Tumanov, A., Liaw, R., Liang, E., Elibol, M. Yang. Z., Paul, W., Jordan, M. et al. Ray: A distributed framework for emerging (AI} applications. In 13th USENIX symposium operaling systems design and implementation (OSDI 18), pp. 561-577, 2018. 30
[46] Paninski, L. Estimation of entropy and mutual information. Neural computation, 15(6):
1191-1253, 2003. 35
[47] Papadopoulos, H., Proedrou, K., Vovk, V., and Gammerman, A. Inductive confidence machines for regression. In Machine Learning: ECML 2002: 13th European Conference on Machine Learning Helsinki, Finland, August 19-23, 2002 Proceedings 13, pp. 345-356 Springer, 2002.
1, 17, 28
[48]
Papadopoulos, H., Gammerman, A., and Vovk, V. Reliable diagnosis of acute abdominal pain with conformal prediction. Engineering Intelligent Systems, 17(2):127, 2009. 7
[49] Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L.,, and Lerer, A. Automatic differentiation in pytorch. In NIPS W, 2017. 30
[50] Petersen, F., Borgelt, C., Kuehne, H., and Deussen, O. Monotonic differentiable sorting networks. In International Conference on Learning Representations (ICLR), 2022. 5, 15, 28, 29,30 30
[51] Polyanskiy, Y. and Wu, Y. Lecture notes on information theory. Lecture Notes for ECE563 (UIUC) and, 6(2012-2016) 6):7, 2014. 18, 19
[52] Polyanskiy, Y., Poor, H. V., and Verdu, S. Channel Coding Rate in the Finite Blocklength Regime. IEEE Transactions on Information Theory, 56(5):2307-235)) May 2010. 7,21
[53] Raginsky, M. and Sason, I. Concentration of measure inequalities in information theory, commut- nications, and coding. Number vol. 10, 1-2 in Foundations and Trends in Communications and Information Theory. Now Publ, Boston, Mass., 2013. ISBN 978-1-60198-722-22 7, 20, 21
[54] Romano, Y., Patterson, E., and Candes, E. Conformalized quantile regression. Advances in neural information processing systems, 32, 2019.
[55] Romano, Y., Sesia, M., and Candes, F. Classification with valid and adaptive coverage, Advances in Neural Information Processing Systems, 33:3581-3591, 2020. 8, 20, 30
13

---

[56] Sadinle, M., Lei. J., and Wasserman, L. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):233-2344 2019. 8, 30
[57] Sason, On data-procsssing and majorization inequalities for f-divergences with applications. Entropy, 21(10): 1022, 2019. Publisher: MDPI. 7, 19, 21
[58] Sason, I. and Verdú, S. f-Divergence Inequalities. IEEE Transactions on Information Theory,
62(11):5933-6006 November 2016. 3, 7, 18, 21
[59] Sason, I. and Verdú, S. Rényo conditional entropy and Bayesian M -ary hypothesis testing. IEEE Transactions on Information theory, 64(1):4-25, 2017. Publisher: IEEE. 21
[60] Shafer, G. and Vovk, V. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008. 7
[61] Stutz, D., Dvijotham, K. D., Cemgil, A. T., and Doucet, A. Learning optimal conformal classifiers. International Conference on Learning Representations, 2022. 5, 7, 8, 15, 28, 29, 30, 32
[62] Tibshirani, R. J., Foygel Barber, R., Candes, E.,, and Ramdas, A. Conformal prediction under covariate shift. Advances in neural information processing systems, 32, 2019.
[63] Vovk, V. Conditional validity of inductive conformal predictors. In Asian conference on machine learning, pp. 475-490. PMLR, 2012. 17
[64] Vovk. V., Gammerman, A., and Shafer, G. Algorithmic learning in random world, volume 29. Springer, 2005. 1, 2, 7, 17
[65] Vovk, V., Fedorova, V., Nouretdinov, I., and Gammerman, A. Criteria of efficiency for conformal prediction. Conformal and Probabilistic Prediction with Applications: 5th International Symposium, COPA 2016, Madrid, Spain, April 20-22, 2016, Proceedings 5, pp. 23- 23-39. Springer, 2016. 2, 5, 20
[66] Wang, J., Charles, Z., Xu, Z., Joshi, G., McMahan, H. B., Al-Shedivat, M., Andrew, G., Avestimehr, S., Daly, K., Data, D., et al. A field guide to federated optimization. arXiv preprint arXiv:2107.06917, 2021. 9
[67] Wisniewski, W., Lindsay, D., and Lindsay, S. Application of conformal prediction interval estimations market makers' net positions. In Conformal and Probabilistic Prediction and Applications, pp. 285-301 301. PMLR, 2020. 7
[68] Wozencraft, J. M. List decoding. Quarterly Progress Report, 48:90-95, 1958, 2, 3, 7, 19, 21
[69] Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint (xXiv:770.00744 2017. This work is licensed under the MIT License. To view a copy of this license, visit https: httpp:s////tttt.tooooo// thub. zal wwwcccchhaaahiiiiii
7, 30
14

---

A Broader Impact, Limitations and Other Remarks
Broader Impact. This work explores the connection between conformal prediction and information theory, with the end goal of advancing the state of the art of uncertainty quantification in machine learning. With that mind, we believe its potential societal consequences are chiefly positive, since our work might contribute to larger adoption of uncertainty estimates, in number of safety-critical applications. Notwithstandingg conformal prediction, like any other uncertainty estimation method, should be applied with care and proper understanding of the provided guarantees an illusion of safety when there is none. That is why our work aims to develop new methods and study and
not to create
algorithms from first principles, with the hope of providing new techniques that understand at a deeper level so as to mitigate, or at least foresee, some of their failure modes.
Limitations. Our work is not without limitations. In practice, estimating the conditional entropy (Y]]X) is difficult problem. That is part of the reason upper bounds might be useful, but that also means it is hard evaluate how tight our upper bounds are. This also limits potential applications of our upper bounds like, for instance. estimating the expected prediction set size. Our experiments in Appendix G.3 rely on quantization to get a reasonable lower bound on the conditional entropy, and thus lower bound the expected prediction set size. Finally, in terms of our experimental results, we unfortunately have not been able single out which of our new upper bounds performs best. The general trend we observe is that the DPI and model-based Fano bounds perform better on complex classification tasks, while simple Fano seems to excel relatively simple tasks or where there is a high risk of overfitting, like in the federated setting.
Regression Setting. In this paper, we focus our experiments on the classification setting, similarly to previous works conformal training [8, 13, 61]. However, in principle, bounds pose assumptions on the underlying prediction problem and we see the application of our results to the regression setting as a promising avenue for future work. In practice, only the simple Fano bound in (6) would not be directly applicable to the regression setting, but that is mainly because it assumes a uniform distribution over the output space and we get the, potentially infinite, | term. The other two bounds we propose, DPI in (4) and model- based Fano in (5), do not include the | and [C'(X) terms and can be applied regression problems as is.
Computational Cost. The computational cost of using our bounds for conformal training is the same as that of previously proposed conformal training [61]. comparison to regular training, i.e. minimizing the cross-entropy loss, the additional cost is given by the (differentiable) sorting operation of the scores, which in our case was performed with diffsort [50] with bitonic networks, which has complexity (6b log 6²) for b the batch size. Since the batch size is typically small, the additional computation cost is only marginal in practice.
B Background on Conformal Prediction
In this section, we outline a brief introduction to conformal prediction, providing the reader with the necessary background to follow main results. Readers already familiar with conformal prediction can safely skip this section. We start by reviewing the definitions of quantiles and exchangeability. which are central to the main results in conformal prediction.
B.1 Exchangeability, Ranks and Quantiles
The main assumption in conformal prediction is that the data points used for calibration and testing exchangeable. Next, we define the concept of exchangeability and discuss how it leads to the main results in conformal prediction via properties of ranks of exchangeable random variables. Our exposition is markedly brief, and we refer the reader [26] for a more thorough discussion on exchangeability and its importance in conformal prediction.
Formally, the concept of exchangeability can be defined follows.
Definition B.1 (Exchangeable Random Variables). Random variables XI,..., ......,,, X, are said to be exchangeable for any permutation æ (1.....n) n.) - (1...., m). the sequences (X1....; X,) and (Xx())..... Xa(n)) have the same joint probability distribution.
15

---

Note that exchangeability is a weaker assumption than the i..d. (independent and identically dis- tributed) assumption commonly relied upon in machine learning. More precisely, exchangeable random variables must be identically distributed but not necessarily independent [26]. Naturally, i..dd random variables are also exchangeable.
One relevant consequence of exchangeability that is central to conformal prediction is that the ranks of exchangeable random variables are uniformly distributed. We define ranks and this property more formally in Definition B.2 and Lemma B.4, respectively.
Definition B.2 (Rank). For a set of n elements X (II,...,, .n.. the rank of any one element z; in X' is defined as
rank( X = Hí E (I....,,m] 2y + EU, S x; + EUHH.
for Ş 2 0 and U IU U, set of i.i.d. random variables uniformly distributed in [-1, -1]. Remark B.3, The addition of i.id. uniform noise serves as tic- dic-breaking mechanism. Since {UI..... Un are almost surely distinct, {-; {U;)_1 also distinct with probability one. This is necessary to render the rank independent of the distribution X;, which key to ensure the distribution-free quality of conformal prediction.
Lemma B.4. (X Xn) are exchangeable random variables, then
(rank(X) (X;; .......,,,,))).. ( {I..... + nl)).....))..
In words, Lemma B.4 tell us that the ranking of exchangeable random variables is uniformly distributed among all possible permutations क fl....,, n + (1....,n.) That means the probability of observing any one ranking is equal to 1/ml and, importantly, independent of the distribution of X. The corollary below follows directly from Lemma B.4.
Corollary B.1. If (X1...., Xn) are exchangeable random variables, then
4
IP (rank(X;;; (X1, x,,) S
for t E [0, n] and [t] the smallest integer smaller or equal to t. Moreover, we can define a valid p-value as := rank(X;; .x,)...,,)))////// since
P( Sa Sa for all a E [0,1].
Proof.
P(rank(Xx;; (X1; (X1,..., xx)) S1) P(rank(X (X1,..., Xn.) S (1])
Wc]
P Prank (X;; [X1, Xx3) = =))
(n 1)! n!
[t]
where the first equality follows because rank(.) returns integer, and the third equality follows di- rectly from Lemma B.4: each permutation of (X,; [XI,,... Xx ))) _ has the same probability
3/ml, and there are (n - 1)! configurations where rank(X, (X;; ; (XI,... Xn)) i since X; is fixed at rank i, and we can permute the other (n - 1) variables.
As we shall see, Corollary B. is central the main result in conformal prediction, but before proving that result, we should first define the concept of quantiles.
Definition B.5 (Quantile). For Z a random variable with probability distribution F, the level quantile of distribution F is defined as
Quantile(B;1F) F) inf(= IP < 8}.
Similarly, for a sample {= and 8s, a point mass concentrated at 2;, the quantile the empirical distribution is given by
Quantile (3: (zi)iem)) Quantile
3: 7
8
16

---

B.2 Conformal Prediction
Armed with the definitions of quantiles and exchangeability, we are prepared to study conformal prediction, a distribution- free uncertainty quantification framework with the following goal: given a set of data points {(,,, Y=)) sampled from some distribution P on X x y, to construct a set predictor C' X - 2d such that for a new data point (Xtest, (eet) and target error rate a E (0, 1), we have the guarantee
P(ets E C(Xtest)) 21-a,
where the probability over the randomness of {(X,, Y:) U ((Xtest: Yeest). Since the prob- ability is taken over both Xtest and Ytest, this means that on average across all possible values in X. the correct label Yest included the constructed set ((Xtest) with probability at least a. This property is known as marginal coverage. This is in contrast to the stronger conditional coverage, which requires
P(Yrest t(xtst)) (Xtess)
That is, the guarantee holds for each Xeest individually, with Xtest fixed and the probability taken over the randomness of Yeest only. However, distribution- conditional coverage is known to admit non-trivial solution (i.e., besides C(X test) = }) [30, 63]. Therefore, in this paper, whenever refer to the lower and upper bounds provided by conformal prediction, we mean those provided by Theorem 2.1, which guarantees only marginal coverage.
There are different ways to achieve marginal coverage, but for simplicity we will focus on split conformal prediction or SCP [47]. since it is easier grasp than other variants of conformal prediction and is also the main object of study in this paper. We start by assuming a calibration dataset Deat which consists of i.idd samples (X,, Yj) drawn from unknown distribution over X V. We also assume access model f X' + Vr where the output space V can be different from y. Prediction sets satisfying the guarantee above can be constructed via the following three steps.
1. Define a non-conformity score function 8 x - R, which assigns high scores to unusual pairs (2r, v). The score function is typically a function of the model ʃ itself.
2. Compute S, = x(,, Yi) for all (X;, Y;) E Deat and compute Quantile(1 a; {S U {oo}), the empirical 1 a quantile of the scores in Deat-
3. Construct prediction sets C( ((tenst)) = {y ((xtest, v) & Quantile(1-at -o; (S:) ((oo))
Theorem 2.1. (same result as the main text (Lei et al. [31], Vovk et al. [64])
Let {(X,, Y be i.i.d. (or only exchangeable) random variables, and {S, be the corresponding set of scores S, = s(X,, Y:) given to each pair (X4, Y.) by some score function s s: X x x + R. Then for new i.i.d. draw (Xtest: Ylest) and any target error rate E (0,1), the prediction set constructed as
C(Xtest) = {y: (y::s(((eeee s(Xtest, u) S Quantile( - (S (ooo)))
satisfies the marginal coverage property
IP(Yesst c((test)) 2 21-c0 Oz,
Moreover, if (S:) are almost surely distinct, this probability is upper bounded by 1 - a + 1/1t1.
Proof. For simplicity, we assume that the set of scores [S:) are distinct (or have been made distinct by a suitable random tie-breaking rule). Denote Stest = s (Xteat Yiest) and observe that since s(-) is applicd element-wing wise to each pair (X,, Y,) it preserves exchangeability. and thus random variables {S, J U (Stest) } are also exchangeable. Next, we show that the following events are all equivalent
Yrest E C(Xrest)
Steat I Quantile - a: {S U (oo})
Stest < Quantile(1 o; (5:) U (Stest))
rank {S.) (Stest) )) S [(n+ + 1) - a)]
ii follows from the construction of the prediction set itself C(Xrest) itself.
17

---

iii can be easily verified as follows. If Stest & Quantile(1 -
[S Ufoo)), then shifting all values S; 2 Stest to arbitrary values larger than Stest will not change the validity of the inequality, since the 1 quantile remains unchanged. In particular, the inequality holds when replacing {Stest) with }oo} and vice-versa.
(iii) follows from the fact that Stest I Quantile(1 - as [S U (Sinst) }), then Stest among the [n + 1)(1 a)] smallest values of the set (S (Stet)
Finally, this is where the crucial exchangeability assumption comes into play, allowing us to apply Corollary B.1 to get
P(Ytest ((Xtest)) P(rank(Stest: (S:)==1 U Stest) $ [(n 1)(1 - a:]] [(n + 1) - -a]
n+1
From there, it is easy to verify that the right hand side at least - and at most 1 - a: 1/-11
C Background on List Decoding and Basic Information Theoretic Results
In this section, we enunciate some classical results from information theory that are instrumental in deriving main theoretical results, as show in the detailed proofs in Appendix D. We also provide a brief introduction to list decoding and demonstrate conformal prediction can be framed as a list decoding problem.
C.1 Data processing inequalities for f-divergence
We start by presenting the data processing inequality (DPI) for f-divergence, which we define below. Definition C.1 (f-Divergence). Consider two probability measures P and Q and assume that the measure P is absolutely continuous with respect to Q, i.e., P < Q. For convex function f: (0, 0c) - TR with f(1) = 0, the t f-divergence is defined as:
(y())) = Eo
dQ
where aq a Radon-Nikodym derivative. In partieular, using (xx log x we recover the familiar notion of KL-divergence
dPP
DeL(PI1Q) Er log
dQ
We can similarly define conditional f-divergence.
Definition C.2 (Conditional f-Divergence). Consider two probability measures P and Q such that P = Px Prjx and Q == Px and that the measure P is absolutely continuous with respect to
Q. For a convex function f (0, + R with f(1) = 0, the conditional f-divergence is defined as:
Dy(Pyxx11yxxIPP5
Epx [D((Py)===lQyxx==)))
Theorem C.3 is the classical data processing inequality (DPI), which we restate below for the sake of completeness. The classical versions of DPI, stated in terms of mutual information, can be found in classical information theoretic text books like [14], while the generalization of DPI to f-divergences can be found in other works with comprehensive survey in [51,
Theorem C.3 (Data Processing Inequality for f-divergence). Consider conditional distribution Wyix. Suppose that Py and Qy are two distributions obtained by marginalization of PxW V and Qx over X. For any f-divergence, we have
Dx(Px11Qx) ()(P)))
The proof can be found in standard textbooks in information theory see, for example, Chapter 7, Section 7.2 [51] for a derivation the DPI enunciated in the same form as above. Next, we consider the application of the DPI conformal prediction.
18

---

Theorem C.4 (Data Processing Inequality for Conformal Prediction). For any set function C: X - 2", any f f-divergence, and all distribution pairs P. Q on (X,Y), we have:
Dy(P11Q) 2 dy (P(Y E c()))IIQ EC(x)))
where y (pllq) is the binary f-divergence, namely dp(pll)) qf(p//) + (1- 10ff(11p11 q).
Proof. Consider the random variable E' = 1(Y E C(+)) denoting the event of valid coverage, and the
conditional distribution PEIX.Y ED. [1 C(+)) YJ. Note that PEIX,Y y maps distributions
Px,y and Qx to PF and QF. resp. From here, the result follows directly from Theorem C.3. O
The construction in Theorem C.4 can be further improved as follows.
Theorem C.5 (Conditional Data Processing Inequality for Conformal Prediction). For any set
function C : X + 2", any f-divergence, and all conditional distribution pairs Py|x, Qrix, and Px, we have:
Epx (y x=allQy x=a) 2.22pp Epxd, (Prix(Y C(x) = =) ((x))X
where y (pllq) the binary f-divergence, namely dy(pllg) = (p/9) + (1-q).(1 p/1 4).
Proof. Consider the conditional distribution PEIX=E,Y = ED.. [1 E C(x)){X x, YJ. We have that
and from the monotonicity property of f-divergences [51] we have that
Dj (p
= 1
2 X=all (EII==)) = Prixx E
C(x) =)).
By taking the expectation with respect to Px, we conclude the proof.
C.2
List Decoding
List decoding [18, 68] is notion coming from coding theory, large branch of engineering and mathematics that arises from the application of information theory to the design of reliable com- munication systems and robust information processing and storage. In particular, we are interested in channel coding, a field concentrated on the design of so-called error-correcting codes to enable reliable communication over inaccurate noisy communication channels.
The general setup studied in channel coding, including list decoding, can be summarized follows. A message y E ) is encoded and transmitted over a noisy channel, and a message x E X is received. The noisy channel governed by probability density p(xly) that describes the probability of observing output z E X' given input y E y. The receiver attempts to decode x, that is, to guess the originally transmitted message y from the received one, x. At this point, parallels machine learning should already have become clear. If the receiver provides single guess of the transmitted message y, we are in a unique-decoding scenario, which akin to a point prediction in machine learning. Conversely, if the receiver is allowed to guess a set (or a list in the list decoding formalism) of the most likely messages, we have list decoding, which closely resembles conformal prediction. Note that in many settings, list decoding algorithm is constrained to output list of fixed size. While simple conformal prediction methods for regression settings show the same limitation, the parallel between the two domains is more pertinent when we consider variable-size list decoding [57].
More formally, list-decoding algorithm can be defined by a set predictor L X + 2 with maximum output set size [LXX] < M. Naturally, the goal is to design the function L so as to maximize the probability of E L(X). Similarly, for given input-label pair (X, Y) the goal of conformal prediction is to provide a set that contains Y with certain pre-determined probability. this connection that motivates our bounds on the conditional entropy (Y)))). However, the nonconformity score in conformal prediction is typically function of the output of given model
19

---

f:X² +. For instance, Y= f(X) could be the logits output by the model, i.e., vector with the dimension equal to number of classes. If we consider Y the noisy observation of the ground-truth Y, then the problem of determining a set containing Y is again the list decoding problem. Therefore, we can also consider the communication channel p(oly; x) directly, which justifies applying the same upper bounds to HY])). Note that in this last case, the input data X can also be taken as side information, although it is rarely used directly in building the conformal prediction set.
This reinterpretation of conformal prediction as list decoding allows us to apply some of the standard results from the list decoding literature to conformal prediction, as we show in the next section.
C.3 List decoding:
Information Theoretic Inequalities
Fano's inequality for variable size list decoding. The following generalization of Fano's inequality is given in [[53], Appendix 3.E].
Theorem C.6. Consider a scenario where decoder upon observing Y provides a nonempty list L(Y) that contains another random variable Y E y with Y M. Define P. == TP(Y L()).. We have:
H(XI)) S (Pe))) + Pe log(M) + B(log (\{))))
Optimal list decoding and conformal prediction. can be shown that the optimal list decoder consists of selecting LÚū) elements of y with highest conditional probability p(y 0). That is, consider the sorted posteriors under the true distribution p(y (o) 2 p(yalů) 2 2 p(yar (5) and choose the first .yi..... } for some list size L]. However, this rule is for fixed-size list decoding and does not determine how select the coverage set size to guarantee a given coverage. We can modify this rule to obtain variable-sizz list decoding with the required coverage. Assuming again the sorted
posteriors plyn (0) 2 p l0) 2 ... 2 p(yM ()),
we can select the set as follows:
L(0) (v . Wey
where by =- inf { j > p(ul)) 2 21-a
It is easy to see that the above set is the smallest set given each and the confidence level 1 - a (see, for example, [43]). The same result holds in conformal prediction [55, 65].
C.4 Fano and Data Processing Inequalities for Conformal Prediction
First, from Fano's inequality for list decoding, Theorem C.6, get the next result bout-of--the-bo Proposition C.7. Suppose that | = M. Any conformal prediction method with the prediction set C(z) and confidence level a. & E (0, 0.5), satisfies the following inequality:
H( < (a) + a log(M) + E(loo [C())[]*,,
where (-)-) is the binary entropy function, [x]+ == max(æ, 0} and (Y| is computed using the true distribution Pxy. When the conformal prediction merely based on the model output Y f(X), the inequality can be modified to:
H(YIr) < ho(a) + a logg(()) + B(log [C(x)]]T).
The proposition follows easily from Theorem C.6 by using the condition IP(Y E C(x)) 2 1- a. Note that in Theorem C.6, we assume non-empty lists, whereas in Proposition C.7 we allow empty prediction sets but apply the maximum operator [x]+ == max(2, 0). This is justified because the last term of Fano's innos inequality relates to the probability of correct assignments Y C(X), which never happens for empty sets. See Proposition E. for the proof, where the same result appears.
The bounds that we present in the main paper, model-based and simple Fano bounds, are actually derived through a slightly different root by leveraging the lower and upper bounds in the finite-sample guarantee of conformal prediction (Theorem 1). We derive these other two bounds in Appendix D.2.
20

---

C.5 Related Work on Information Theoretic Inequalities
The use of f-divergences goes back to works of Ali and Silvey, Csiszár, and Morimoto in the 60s see for instance [2, 15, 44]. A key f f-divergence inequality is the data processing inequality, which was used in information theory establish various upper bounds on the achievability of coding schemes for different tasks-see see [57,58] for an extensive survey. Moreover, the data processing inequality for f-divergences provides unified way of obtaining many classical and new results, for example Fano's inequality [19]. The tightness of data processing inequalities is discussed in terms of Bregman's s divergence [12, 34] and in terms of diiiieegee in [57].
When it comes to list decoding, there are a number of relevant inequalities in the literature. List decoding was introduced in the context of communication design by Blias [18] and Wozencraft [68]. See also [22] for a more recent overview of list decoding. For fixed list size, the information theoretic bounds on list decoding were obtained in [20] using error exponent analysis. A generalization of
Fano's 's inequality to list decoding was given in [16] in the context of multi-user information theory,
see also the general Fano inequality for list decoding presented [53]. For fixed list size, stronger inequalities, some based on Rémooo-Rényí conditional entropy. were presented in [59]. Variable size list decoding was discussed in [57] using the notion of F.y resolvability first introduced in [52] related to the dependence testing bound. It was used again in the context of channel resolvability in
[35], where some relevant inequalities have been obtained and discussed. A selection of the most relevant inequalities for list decoding can be found in [57].
D Proofs of Main Theoretical Results
In this section, we provide the proof' our main results, namely the DPI bound in Proposition 3.1, the model-basee Fano bound in Proposition 3.2, and the simple Fano bound in Corollary 3.1. For notational convenience, we use the shorthand On 1/n+1 in most of the steps of the derivations.
D.1 DPI Bound
We start with the DPI bound which we restate and proof below using the data processing inequalities discussed in Appendix C. Note that, when clear from the context, we remove explicit dependence on the calibration set Deat from the derivations. It is implicitly assumed that the probability of the event Y E C(x) is computed by marginalizing over Deat-
Proposition 3.1. Consider any conformal prediction method with the prediction set C(x) with the following finite sample guarantee:
1
1 - a C(z)) n n+1
for any a E (0,0.5). For any arbitrary conditional distribution Qy x, the true conditional distri- bution Prix and the input measure Px, define the following two measures Q := PxQrxx and P : PxPvix We have for any a E (0,0.5)
H(YIX) ho(a)) (1- (1-a+
1 (++11
log Q(Y E C(())
n n+1
+ log Q(Y & C(x)) EPxy [log Qrix]
Proof. Consider an arbitrary distribution Qrix. Then we can use Pxy, and Px x Qrix in the data processing inequality for KL-divergence (Theorem C.4) get:
DK Prix Pxxx 2 dx (P(Y E c(=)))IQ(( C(x)))
(12)
Now note that we can decompose D (Px Prix|1 PxQrix) in terms of the conditional entropy H (X) and the cross-entropy EEpxy [log Qyix]:
Px Px Exxy
Prix
Dxx(PPPy1xIIIxx11 = Erxy
log Px Px
log
Qrix
EPPY [log Py x] Epxy (log Qrix]
--H(YIX) - Esxy flog Qrix).
21

---

With the decomposition above, we can rearrange the terms in (12) to get the following upper bound on (X
H(II)) ExSY [log Qr x] 2 dRL(P(Y c( e c(()))
H(Y & E C(=))IQ( e C(x))) Brxy [log Qyix] (13)
We can then apply the upper and lower bounds from conformal prediction, i.e. P(Y e C(x)) 2
and P(Y & C(x)) 2 on, to upper bound dx (P(Y e C(x)))IQ(( E C(x))) follows.
dKLL(P(Y E ((x)))IQ(Y C(x)))
ho (P E((x)) + P(Y E EC(x)) log Q(Y E EC(x)) + P(Y & C(x)) Q(Y & C(r)) - a) log Q(Y C(()) on log Q(Y & C(x)),
S hb
where h-)-) the binary entropy function, that is. h₂(a) aa lo -1 a) a). The equality in the second line follows from the definition of the binary KL divergence. and we get the inequality simply by upper bounding each of the terms individually. In particular, note that log Q(Y E C(r)) and log Q(Y & C(x)) are both negative, and ha(-) is decreasing in [0.5, 1.0) and symmetric about 0.5, such that for typical values < 0.5
P(Y E C(X)) 2 1- - = h8 (P(Y E C(x))) & h1 - a) = hs(aa)
(14)
Finally, we can replace the upper bound above into (13) to conclude the proof.
X(YIX) & (an) + (1 a) log Q(Y E C(x)) + an log Q(Y & C(x)) - Epxy [log Qrix]
Remark D.I. The DPI bound always provides a tighter upper bound on the conditional entropy H than the cross-entropy, which is easily verified (13) since the KL term is always non- negative. This serves as important motivation to optimize the DPI bound instead of the cross- entropy in conformal training.
Remark D.2. The derivation of the DPI bound places no assumptions on the conditional distribution Qyjx. However, in practice, the underlying model often already provides such a distribution, and since it is typically trained to approximate Prix well, it makes sense to take Qy x as the distribution defined by the model itself. That is how we evaluate the DPI in all of our experiments. Finally, we can again use H (Y (Y) instead of HY (X) if the conformal method uses merely Y.
Remark D.3. Typically, we have
(0.0, 0.5). and we use this fact in the proof to bound the binary entropy he (P(Y' E C(x))) The same could have been done for a E (0.5, 1.0), but since a lands in the increasing part of the binary entropy function between and 0.5, we have to resort to the lower bound from conformal prediction get
P(Y E C(X)) < 1 - an = hy (P(Y e C(x))) S ho - a.) = h)((a))
Remark D.4. One of the appeals of the DPI bound is that the terms can be computed in data-driven way using samples. While the cross-entropy can be estimated in an unbiased way with samples from the true distribution Pxy, we must be careful when estimating Q(Y E C(x)). The main challenge is that Q(Y C(x)) appears inside log, and thus an empirical estimate Q(Y C(x)) would yield lower bound of the negative KL divergence and would be biased. We can get an upper confidence bound on this estimate via the empirical Bernstein inequality [41], which we restate below.
Theorem D.5 (Empirical Bernstein Inequality [41]). Let Z, Zi...., Zn be i..dd. random variables with values in 10, 1] and let > 0. Then with probability at least 1 - ö in the i.i.d. vector Z 12 Zn) we have that
2V, (Z) log(2/0)
7 (2/8)
E Z
2
n
3(n - 1)
where Vn (Z) is the empirical variance over the (Zi, ...... Zn) samples.
22

---

By using this bound, we have with probability -
Q(Y E c(x)) Q( EC(x)) 2V, log(2/6)
7log(2/6) Q(Y E C(x)),
n
3(m 1]
2V, (Z) log(2/6)
7log(2/0) Q(Y & C(x)),
Q(Y $ (())) Q(Y & C(x))
n
3(n
where Z; = Q E C(a.)) for xi sampled from Px and prediction set (zx;) obtained with a calibration dataset sampled from Poi This yields the following inequality with probability 6:
X( ha(a)
a:) log Q(Y E C(x)) on log Q( & C(+)) Exx [log Qrix]
We can use this inequality to evaluate the bounds.
D.2 Model-Based Fano Bound
In this section, prove the model-bbasd Fano bound, which restate in Proposition 3.2 below. Proposition 3.2. Consider any conformal prediction method with the prediction set C(x), and any distribution Q, with the following finite sample guarantee:
a E C(z)) 51-))+1+++
n+1
for a E (0, 0.5). Then, for the true distribution P, and for any probability distribution Q, we have X(Y ha(a) + P.B
[- x
+ (1 (1-a+ a n n+1 n
Ery EPy.x.Dadlleeco) [- log QYIxxc(e))
Proof. For notational convenience, define conformal prediction method means that < PPFE = 1) < On- The starting point is similar the well-known proof of Fano's inequality:
1(Y E C(x)), which by our assumption on the
HEE, Y Deal) = H(||X, + HEEY
= H(Y
where the last step follows because knowing X,Y Y and Deat. know if Y E C(x), and therefore HE)YY X, Deat) = 0. Furthermore, given the structure of the graphical model of the conformal prediction process (c.f. Figure 1), we have that XY H(Y |X, Deat). We now find an upper bound on H (E,, Y X Deal):
HE D (E)X, Dowt) + H(Y E, Deat)
= (E,,,X, Deat) + PPEE = (Y E 0, D,ul + P(E = E) Deat)
0.n)) P(E (|00=11XXXXXXX1171/ = < (EE)+ + P(E (() = 0,a)) +P(E'= E)'
< (a) + P(E = (Y Ex=
=
(15)
where the first inequality follows from the fact that HE|X, Doal) (E), and the last one comes from the same argument for a < 0.5 in (14), We can continue as follows
H(Y|)) - ha(a) + P(E HY 0, Deat)
P(E (Y 1,a
ha(a) + P(E Py, R=o
[- log PYIX,De.I.BE))
+ P(E = 1) 18
log PyIx.PeaIEE=1
(a( + P(E O)EE,, D. REo
log Qy(x,C(=),E=0))
- (
B=ol
Qy (,(x))())
+ P(E 1)EPY, 18-1
log Qr QVlx.C(=),
- E[DKL (Py N.D.D.D.... D....
Qy x,C(,)
< hh(a) + P(E 0)E RED
log Qy(x.C(s)EE
+ P(E
log Qy Qy
(16)
23

---

The first equality comes from the definition of the conditional entropy, whereas in the second equality we replace the true distribution Pyxx with an arbitrary conditional distribution Qrxx plus the KL divergence between the two distributions. The last inequality then follows simply from the fact that the KI. divergence is non-negative. Finally, we can leverage the fanite-sample guarantees from conformal prediction, namely P(E 0) S and P(E 1) S Ob to upper bound each term, which yields the proof.
H(Y ha(a) + P(E = 0)E Pv,x, D.
[ log (((x))
+ ((E==))BP Pedt R=1 log Qx(x.C(=),B=))
[- log (1Ix)
< ha(a) + C.E.,, Poud R=o
+ (1 an) Epy.x.P [- [olog Qy B()
(17)
Remark D.6. When the conformal prediction is merely based on the model output y f(X), the model-based Fano bound can be modified to
H(YI)) & ha(a)) + aBBYy.x,De (XEC())
- log QYIx.C())VEC(x))
(1 1 a
1 n 1
+
BPy.x.De
[ -og -oxg
D.3
Simple Fano
In the derivation of the model-based Fano bound above, we placed no assumptions on the distribution
Qyjx- One simple choice that we consider in this section the uniform distribution Qy = 1/12/. akin to the classical Fano's 's inequality [19] and the list decoding result in Proposition C.7.
Corollary 3.1. Consider any conformal prediction method with the prediction set C(x). and any distribution Q, with the following finite sample guarantee:
1 S IPY E C(x)) 11-11110 n+1
For a E (0,0.5) we have the following inequality:
HY & ha(a) + aE PeullveerE -
+ (1-a,,) Mea Vecck) [log [C(X]]
Proof. Note that if we make an error (E -0=00 0) the correct class will not be inside C(X) and since Qrix is uniform the probability will be spread equally among the remaining 1 labels, and we have Qy]x,C(2) = [)-())())- Through the same logic, we get that Qy|x.C()).E=1 (C(X)) and plugging both into (17) we get the simple Fano bound
n
Remark D.7. Once again, when the conformal prediction prediction is merely based on the model output y f(X), the inequality can be modified to
H(YI)) < (a) + +a Peaa [log ( - (C(X))I
+ (1 ax)) BPy. [log [C(X)]]
E Further Theoretical Results and Proofs the Prediction Set Size
E.1 Fano's inequality for maximal prediction set size
we leverage the upper bound on the prediction set size, we can find a lower bound on the maximum coverage set size.
24

---

Proposition E.1. Suppose that | = M. Consider any conformal prediction method that constructs the prediction set C(X) with the following finite-sample guarantee:
1 - a P(Y E C(X)) 1
m+1
for a E (0, 0.5). Then, have the following inequality:
X( S hy (a) + a log M + (1- -1--0 a +
sup sup
log ((())
Deat zEsupp(Px)
We similarly replace [Y with H(
Proof. We use the conditional data processing inequality with f(x) x log 2, XY,, and Q = Pe X x UM where UM is the uniform distribution over V. We fix the input to X = 2, and the calibration set Deat. The conditional f-divergence, conditioned on Dent and X, given by:
Dy(Orix a P
=log M - - =
where the last step follows from the independence of the calibration set Deat and (X,Y). This means that
Ep x (D(PP)X==,DD.. 1y log M H(YIX).
(18)
On the other hand, we have
dy (Q(Y E
D(z))
dKL (P(Y E C(z) =x)]IQ( C(z)
X =r))
C(xx]
=x:) -hh (P(Y C((x)) x= =x)) P(Y E C(x) Deat: X = =x:) log
M
M C(x)
P(Y & ((z))Peat, X 2) log
(19)
M
Now, can plug both (18) and (19) into the data processing inequality of Theorem C.5. Rearranging the terms and getting the expectation from both sides w.r.t. Dent and X would yield:
H(Y(X)= - Eih (P(Y C(x)|Deat, X))
+ E[P(Y & C(r)[Deat, X) log (M - [C(=) e C(x)) X) log [C(x)]
E[P(Y & C(x))Deat, X) logoMM E[P(Y E C(z) X) X)log log M] + log M
< he (P(Y E C(x))) + P(Y & C(z)) M + E[P(Y E C((z) cat X) log C(x)
< ho (a) a log M + EE[((Y C(x))Doai, X) log [C(x)]].
Note that the log M terms in the third line cancel each other out, and that the second inequality comes from resolving the expectations and log(M - (C())) S log M. Further, in the last inequality, we used the concavity of binary entropy in (14). Finally, using respectively the inequalities P(Y E C(x) cat X) S and log [C(x)] supp... supzex log [C(x)), we get two inequalities:
XX) < h2 (a) + a log M + E (log (C(x)]++)
sup sup X < ho (a) + a log M + a + n n Deat xEsupp(Px)
log [C(x)).
The first one is the Fano's inequality for list decoding from Proposition C.7 while the second one yields the theorem. Note that C(x)) is an empty set, the probability P(Y E C(xr) X) is zero, and the term P(Y E C(r) X) log [C(z)] disappears. Therefore, if we use the inequality P(Y E C(x) supp X) & 1, we need introduce the term [log [C(x)]]+ to keep the expectation well defined.
25

---

E.2 Fano's inequality for lower bound on prediction set size
In similar manner, we can also obtain lower bounds for the set size. More specifically, we have that
- = (3122 Hay E C(=)]
[011=) (ol=)) E c(x))
Evec(a) ((Væ))
(((z) B (
(20)
QYIx,CO),E=0 (()12)) Mlly & C(x)]
[ulyl= (o0l))ly & C(x)]
yyec(x) (y)a))
(M [C(x))] ((le)))Buuees))lllllll)
(M - ([(())))))el [q(vla)) 0
(21)
where (())())) and ((V((e)) denote uniform distributions over the labels in the confidence set. By considering the standard conformal prediction bounds on the error probabilities, we have that
HY S ha( + aBBP,. Pr.x. [-log Q + llogMM C(x)) + log Bu(ver [
1 + 1 a ++1
BPrxx.
log 1 + log [C(x)] + log E (o -log log Q8 + log (idte
< hs((a) + log M + &EEPyxPeel
1 n+1
1
Bpyx
[-
log Q + log [C(x)) + log Euteew))
which leads to
EE (log [C(x)]] 2
X) hss(a) - log M- - a.Eyy.x Dent
log Q4 + log (adooapa((slaa)
+ n+1
EPy,x.Pe.11-11 [- log 1/ix x + log E. Butverrs)
Note that when E = 1, we know that Y E C(x), and therefore [C(x)] > 0 and [log [C(x)]]+
log [c()). Using this, we can find an upper bound on Eg= ([=(((o((((rr))) as follows:
E-=1 (log((((((()) = EE= ((og((((())))
Te(log (xx)]++)
P(E 0)
Eg Eg=u((log [(xx)]++))
P(E 1)
P(E = 1)
E(log ((x)]l+))
E (log ((+))++)
<
<
P(E =1
This leads to:
B[lo [c(x)]]+)= 2
H(YIX) - ha(a)) a aog M aTE a.I.PyP... py....y.x........... I.. log Q9 + log E. Buiver (a(x)=))))))
(1 a)
(1 - a -Py log @ + log E, Eu(re (a
All the above terms can be approximated from samples. We summarize this in the following proposition.
26

---

Proposition E.2. For any conformal prediction scheme with the coverage guarantee of 1 - and any distribution q(-), we have:
B(log [c(x)[)²² z X (a) alog M alE vy,x x. Peal 8=0
log Qp + log (atves))lla
(1 a)
n+1
(1 - -11-a)BPrx.paale 1811 [- log Qbix + log Bu(sece)) [d(vl2)]]
(22)
where Q [الا>\/ا C(x)] and Q (الl=)lay E (x))). When the conformal prediction
merely based on the model output y f(X), the inequality can be modified to
E(log c(x)]I+) z
H(Y - ho(a) a alo M- a.
log Q/ + log Eu(nern) (((
[4(v)=)]
PoaliB= 18-0
(1 a)
n+1
- -(I | log 0/x + log 1E (etvew))l((ll)))
(23)
Remark E.3. If use the uniform distribution in the above bound, get bound similar to what is obtained from Fano's 's inequality given in Proposition C.7, but with an additional factor of T-a+ .
1-o
Since the factor smaller than one, the current bound with the choice of uniform distribution looser than Fano's 's bound, although the gap vanishes for large
27

---

F
Conformal Training
Split conformal prediction (SCP) [47] has quickly become popular framework for uncertainty quantification, largely thanks to its computational efficiency. One only needs access to a separate calibration data set derive prediction sets with valid marginal coverage from any pretrained model. Given that training new machine learning models is becoming ever more time-consuming and expensive with new, larger architectures, this ability to apply conformal prediction to existing models is invaluable in number of applications. Yet, it is reasonable to expect that the performance of the final set predictor could be improved if the conformal prediction process were to be accounted for during training of the model well, steering the model towards better predictive efficiency, it were. That is the motivation behind the line of work that we broadly refer to as conformal training [8, 13, 61J. In a nutshell, conformal training introduces a differentiable, and hence approximate, conformal prediction step during training so that one can directly optimize for desired properties of the set predictor, most notably its predictive efficiency. In what follows we give overview of conformal training, focusing on classification tasks.
The idea of conformal training has been proposed concomitantly in [8, 13]. Here we follow the approach [8], where the key idea is to relax the prediction set defined by the model f and define "soft" prediction sets (z), which contain each of the labels y E 3 with a certain probability. That is, if (r, y) E {0,1) is the hard assignment of label y to (z)), corresponding soft version of this assignment can be defined as
(x,,)) = q (5 y)
(24)
T
where sy y) is the non-conformity score function defined by model f evaluated at (z, y). i is a thresholding value, is the logistic sigmoid function, and T is temperature parameter controlling the smoothness of the soft assignment. Then we can define (xr) the vector collection of all the soft assignments C2 (x. y) for all labels y E V. Similarly the size of (x) can be naturally defined as
|c,( : Ec((a.y)
NEY
Bellotti [8] then proposes the following loss functions which are computed for each training batch B
(1 111 Σ C,(2, v) - (1 (1-aa) [6] (2,8)EB
2
1 B
Eg (1C)(=))) Leoverage (f) ZEB
(f)
where is the desired coverage rate and g is user-defined function of the prediction set size, e.g. the log function. Intuitively, Lsize encourages small (efficient) prediction sets, whereas Leoverage penalizes deviations from the target coverage of 1 a. Naturally, there is a trade-off between these two objectives, inefficiency and coverage, so both loss terms are optimized together with a hyperparameter governing the influence of each term:
L(f) (fize(f) + XCcoverage({)
(25)
Importantly, Bellotti [8] argues the choice of the threshold in (24) is immaterial since the model can learn to shift its outputs (in logit space) accordingly to match the constraints in Looverage (f). We can then directly optimize (25) via stochastic gradient descent methods during training since it is fully differentiable with respect to the model parameters.
Stutz et al. [61] build on the work of Bellotti [8] by noticing that the calibration step is an important component in conformal prediction that should also be accounted for during training. To that end, they propose to split each training batch B in two: the Beal half used for calibration, and the Brest used for testing. Now, instead of using an arbitrary threshold q. we compute it using the quantile of Bont, or concretely
i = Quantile( - a; (2, y) (x. y) E Beat))
With this modification, we no longer need to enforce valid coverage via Cromerage(]) and can optimize for low inefficiency directly by minimizing (fi on Brest- In that case, however, we only get a learning signal from Blest, since the quantile operation applied to Bosl is non-differentiable. Stutz et al. [61] bypass that limitation via differentiable sorting operators [9, 17, 50], in particular via
28

---

version of differentiable sorting networks. In our experiments, we considered both fast sort [9] and the monotonic differentiable sorting networks of [50] but finally chose the latter since they proved more stable and provided richer gradient signals.
This version of their approach, which we refer as ConfTr, only optimizes the size loss, but Stutz et al. [61] also proposed another variant which includes a classification loss term as follows
Lelass (
1 B
Lyg (s.u)EB JE)
Σ
Σ
1 Cx 8 vl C,(,,, W0, + w|] (26)
where 5 is the indicator function, and is a user-defined square matrix of size 2 with L. capturing some similarity notion between y and ÿ. In our experiments, well as most experiments in the original paper [6]], no prior information about the classification problem is assumed, which case I. is taken to be the identity matrix of size ()). Therefore, we have two variants of conformal training as proposed in [61]] ConfTr that optimizes only Liizzs and ConfTr that jointly optimizes fai and Celasa. both of which are included in our experiments.
Our own approach conformal training follows the same recipe from [61], i.e., also simulate split conformal prediction step during training by splitting each training batch into two and using differentiable sorting operators (see Algorithm 1). The key difference is in how we define the training objectives, which we derive from first principles and standard information theory inequalities, Not only do our upper bounds. DPI (4), MB Fano (5) and Fano (6), outperform the ConfTr objectives in many cases, but they also do away with a few hyperparameters. Namely, the function in Lzizes and hyperparameters controlling the relative importance of Lixize and Lalass-
F.1 Deriving Conformal Training from Fano's bound
Through Proposition 3.2, we can connect Fano's 's bound for list decoding to the size loss from [61], proposed for conformal training. Assuming a uniform distribution for Q we can show that
X( z ho(a) + == [log(|Y| [c(x) + (1 a. Ex=1 [log [C(x)]]
< ha(a) + a log Y + (1 - a..) Ex log [C(x)]]
< hy(a) + a log Y| + (1 - ox,) log Eg=1 [[((x)]
3 hn(a) + a log Y|| - (1- (1-aa,) a.. log a) + + - log
Note that in the first line we have the simple Fano bound, whereas in the last one we have the ConfTr objective, namely log E [[C())]], multiplied by 1 - an plus constant that depends only on a. Therefore, we ground ConfTr as minimizing looser upper bound to the true conditional entropy of the data than the simple Fano bound we provide in Corollary 3.1. Moreover, the simple Fano bound can be further improved with an appropriate choice of Q, for instance as given by the model f. in the model-based Fano bound of Proposition 3.2.
29

---

G Experiments
In this section, we present further experimental results for conformal training in the centralized and federated setting. We start by defining the splits and architectures used for each data set, which are listed in Table 6. In most aspects, we follow the experimental design of [61]. All experiments were conducted on commercially available NVIDIA GPUs using our own implementation in Python 3 and Pytorch [49], which can be found at github. com (Qualcomm AI wwweeseerrciinnoooooooo All data sets were retrieved directly from torchvision [40].
Table 6: Experimental settings for each data set, with Dirainl Deat and [Pres]] the sizes of train, calibration and test splits, respectively.
Data set
Derainl
iDeal
Dieat
Epochs
Architecture
MNIST [29]
55K
5K
10K
50
1-layer MLP
Fashion-MNIST [69]
55K
5K
10K
150
2-layer MLP
EMNIST [11]
628K
70K
116K
75
2-layer MLP
CIFARIO [25]
45K
5K
10K
150
ResNet-34
CIFARIO0 [25]
45K
5K
10K
150
ResNet-50
Regarding the architectures, we also closely follow the experimental setup in [61]. For MNIST we have a simple linear model, whereas for Fashion-MNIST and EMNIST we use 2-layer MLPs with 64 and 128 hidden units for first and second layers, respectively. For the CIFAR data sets, we use the default ResNet implementations from torchvision [40], but changing the first convolution to have a kernel size of 3 and unitary stride and padding. We use Pytorch's ' default weight initialization strategy for all architectures. For all datasets, and Nesterov gradients, accompanied by a step scheduler multiplying the initial learning rate by 0.1 after 2/5, 3/5 and 4/5 of the total number of epochs. We only use data augmentations on the CIFAR datasets, and differently from [61], we only apply random flipping and cropping for both CIFARIO and CIFARIO0.
regular SGD optimizer with momentum 0.9
G.1 Centralized Setting
We followed the experimental procedure of [61], and for each dataset and each method, we ran a grid search over the following hyperparameters using ray tune [45]:
Batch size with possible values in {100, 500, 1000}.
Learning rate with possible values in {0.05, 0.01, 0.0053.
Temperature used in relaxing the construction of prediction sets at training time. We considered temperature values in (0.01, 0.5, 1.0).
Steepness of the differentiable sorting algorithm (monotonic sorting networks with Cauchy distribution [50]), which regulates the smoothness of the sorting operator; the higher the steepness value. the closer the differentiable sorting operator is to standard sorting, We considered steepness values in {1, 10, 100).
In Tables 7, 8, 9, 10 and 11, we report the best hyperparameters found for each dataset and method as well as the average prediction set size for threshold CP [56] computed in the probability domain (THR) and APS [55], as well as the test accuracy. Importantly, similarly to [61], in all cases we only train the models to optimize threshold CP with probbbbbbil...... We confirm the observation in [61] that other methods, and notably APS, are unstable during training, probably because it forces us to operate in the probability domain, as opposed to the more optimization frrenndlfrrdyyy logits or log- probabilities. Nevertheless, we still select hyperparameters according to the best performance with respect to each CP method, and that is why we have different optimal hyperparameters for THR and APS for each data set and each conformal training objective. We note ConfTr and ConfTrelas require extra hyperparameters like the target size and weights attributed to each loss term (see Appendix F). For those hyperparameters, we use the best values for each data set as reported in [61].
As described the main paper, we use the default train and test splits of each data set but transfer 10% of the training data to the test data set. We train the classifiers only on the remaining 90% of the
30

---

training data and, at test time, run SCP with 10 different calibration/test splits by randomly splitting the enlarged test data All results reported in the paper are given by the average (# one standard deviation) computed across these 10 random splits. Crucially, to avoid overfitting to the test data, the grid search was done solely on the 90% of the training data used for testing.
Table Hyperparameter Search for MNIST.
Bound
Optimized for
batch size
Ir
temperature
steepness
THR
APS
Test Acc.
THR
100
0.01
2.29 10.18
2.50
0.93
CB
APS
500
0.05
2.28
2.50
0.93
THR
500
0.05
6.28
9.81=
0.90
ConfTr
APS
500
0.01
1.0
100
2.0810.10
2.107
0.90
THR
500
0.005
1.0
2.09
2.15
0.91
ConfTr-class
APS
500
0.01
2.12
2.13
THR
100
0.005
0.1
100
2.0940.12
2.12-2009
0.91
Fano
APS
100
0.01
0.5
100
2.11
2.12
0.91
THR
1000
0.005
0.1
100
2 2.24
2.96
0.91
MB Fano
APS
100
0.005
0.1
10
2.4310.22
2049
0.92
THR
1000
0.005
0.01
100
2.24
2.87
0.92
DPI
APS
500
0.05
0.1
100
2.2910.17
2.64
0,92
Table 8: Hyperparameter Search for Fashion-MNIST.
Bound
Optimized for
batch size
Ir
temperature
steepness
THR
APS
Test Acc.
THR
1000
0.005
2.39
2.74
0.87
CB
APS
100
0.05
2. 2.18+0.17
2..1
0.89
ConfTr
THR
100
0.01
1.0
1.0
1. 20.32
1.89
0.89
APS
100
0.01
1.0
1.0
1. 1.73
1.80
0.89
THR
100
0.01
1.0
10.0
5. +0.49
8.28
0.88
ConfTrclass
APS
500
0.005
1.0
100.0
1.7910.00
1.79
0.88
THR
100
0.05
0.5
100.0
1.7010.05
2.06
0.88
APS
100
0.01
1.0
100.0
1. 1.7000004
1.87
0.87
THR
100
0.05
0.5
10.0
1.8020.08
2.7120.14
0.89
MB Fano
APS
100
0.05
1.0
100.0
1.8440.10
2.25
0.89
THR
100
0.05
0.01
10.0
1.7340.07
12.20..
0.89
DPT
APS
100
0.05
0.01
100.0
1. 1.75
2.08 2..8
0.89
Table 9: Hyperparameter Search for EMNIST.
Bound
Optimized for
batch size
temperature
steepness
THR
APS
Test Acc.
THR
100
0.01
2.06
3.37
0.86
CE
APS
100
0.005
2.0610.10
3.40
0.86
THR
100
0,01
0.1
100
1.99
4.94
0.85
ConfTr
APS
100
0.005
1.0
100
1.99+0.us
2.36
0.83
THR
100
0.005
100
2.01
5.07
0.85
ConfTr-llass
APS
100
0.05
1.0
100
1.9940.10
2..8
0.84
THR
100
0.01
100
2.10
8.27
0.84
Fano
APS
100
0.01
1.0
100
2.05
2.75
0.82
THR
100
0.01
1.0
2.01
5.21
0.86
MB Fano
APS
100
0.01
2.94+0.17
3.67
0.86
THR
100
0.05
0.5
100
1. 1.9840.08
3.86
0.86
DPI
APS
100
0.05
0.1
100
2.0440.12
4.07
0.86
31

---

Table 10: Hyperparameter Search for CIFARIO.
Bound
Optimized
batch
temperature
steepness
THR
APS
Test Acc.
THR
100
0.05
1.910.11
2. 2.1210.21
0.93
CE
APS
100
0.05
1.7440.07
2.3440.22
0.93
THR
100
0.05
0.5
10
9.90
10.00=0.00
0.10
ConfTr
APS
1000
0.005
0.1
9.9010.01
1.9810..0
0,10
THR
100
0.01
0.5
10
2.1620
2.1910.10
0,86
ConfTr-class
APS
100
0.01
0.5
10
2. 2.13+0.08
2.18 2.1800.06
0.86
THR
100
0.01
1.0
2.05
2.34
0.89
Fano
APS
100
0.01
1.0
2. 2.0620.10
2.3520.10
0.89
THR
100
0.05
0.5
100
1.66+0.00
2. 2.40+0.0s
0,92
MB Fano
APS
100
0.01
1.0
10
1. 1.69
1.89
0.91
THR
100
0.05
0.01
100
1.64
1.88 10.05
0.92
DPI
APS
100
0.005
0.01
10
1.79
1.97
0.91
Table 11: Hyperparameter Search for CIFAR100.
Bound
Optimized for
batch
temperature
steepness
THR
APS
Test Acc.
THR
100
0.05
19.70
26.0211.31
0.72
CE
APS
100
0.05
19.70
26.0211.31
0.72
THR
100
0.005
1.0
32 22270
34.09
0.52
ConfTr
APS
100
0.01
0.5
30.0411.e 1.30
40.58
0.53
THR
100
0.01
1.0
I
66.48+33.07
54.30
0.43
ConfTr-class
APS
100
0.01
10
33.32 1.89
32.91
0.37
THR
100
0.05
0.5
40.30
48.21
0.42
Fano
APS
500
0.05
30.43 1.61
33.80
0.57
THR
100
0.05
0.5
100
14.61 +0.84
21 21.69+0.71
0.70
MB Fano
APS
100
0.05
10
16.3620.90
21.68.1.44
0.68
THR
100
0.05
1.0
17.55
20.13
0.69
DPI
APS
100
0.05
1
10
14.90.0..0
17.41
0.70
G.1.1 Results with Regularized Adaptive Prediction Sets (RAPS)
We report additional results with conformal method known as RAPS (regularized adaptive prediction sets) [4]. In nutshell, RAPS works exactly like APS but adds penalization term Areg to the score of each label that would make the prediction set larger than Kigg Table 12, we have results with RAPS hyperparameters set as =1 and A =0.01, where we can see a pattern of performance across conformal training objectives that is similar to what we previously observed for THR and APS. As expected, the regularization introduced by RAPS results in prediction sets that are smaller than those obtained via APS in almost all cases. Again, similarly to [61], in all of our experiments we perform conformal training by thresholding on log-probale log-probabilities, which we observed to work best. The results we report for thresholding on probabilities (THR), APS and now RAPS show that this translates well to other score functions well. Nonetheless, the improvement the gains from conformal training. In most cases, RAPS applied to a model trained via CE produces less efficient prediction sets than APS applied to model trained optimize one of our bounds.
get via RAPS still does not offset
We also study the impact the two hyperparameter in RAPS, namely Areg and kreg in the inefficiency of each of the conformal training methods. We concentrate our analysis on CIFARI00 and report results with varying kreg in Table 13 and varying Are in Table 14. Interestingly, RAPS was much more sensitive to variations in kreg than in Areg Still, we observe models trained via our model-based Fano and DPI bounds produce more efficient prediction sets than the baselines in all cases.
G.2 Federated Setting
In the federated setting, we run conformal training exactly in the same fashion, but including the additional Q2ix term in (11) to get the proper distributed bound that can be optimized locally and independently in each device. We optimize the conformal training objective with SGD for one epoch in each device, and then communicate the resulting "personalized" model to the server, which aggregates the model parameters of each device via federated averaging [42]. After aggregation, the
32

---

Table 12: Inefficiency restuls with RAPS. Average prediction set size with both APS and RAPS (hregg and A = 0.01) methods for each conformal training objective and data set for a target 0.01. We report mean and standard deviation across 10 different calib//test splits and show in bold all values within one standard deviation of the best result. Both APS and RAPS results were computed with the same classifier. Lower is better.
Method
MNIST
MNIST
EMNIST
CIFAR 10
CIFAR
APS
RAPS
APS
RAPS
APS
RAPS
APS
RAPS
APS
RAPS
CE
2.50
2.3520.16
2.4
2.40
3.40
3.07
2.34
2.31
26.02a1a1
26.02+1.11
ConfTr
2.10
2.10
1.89=0.00
1.8420.00
2.36-0.11
2.1920.00
9.90=a.00
2.00
40.59
30.87
ConfTre
2.13:013
2.13:013
1.79.0.0v
1.79
0.38
2.21
2.18:0.0
2.18
32.91
32.94
Fano
2.12:0.05 2.12:0.05
1.87:0.05
1.80
2.75=0014
2.50
2.35-0.19
2.20
33.80
33. 83.76+100
MR Fano
2.49
2.48
2.25ga
14
2.07
3.6720.38
3.67+0.a
1.89.0.00
1.78
21 31.68_1.4 44
20.97=1.00
DPI
2.64:0.07 2.44g0.12
2.08
1.95.0.05
4.07 3.7449.7
1.97:0.us
1.87
17 17.41=0.22
17 17.26g0.58
Table 13: Inefficiency results for RAPS with varying kireg- Average prediction set size for Xveg 0.01 and varying Kieg CIFAR 100 for target a 0.01. We report mean and standard deviation across 10 different calib./test splits and show in bold all values within one standard deviation of the best result. Both APS and RAPS results were computed with the same classifier. Lower is better.
Method
kreg 0 (APS)
Kiee 1
lieg 3
Krog 5
Kiog 10
krug 15
CE
26.02_1.31
26.02
22. 22.43
20.43+1.70
18.9541.18
20.63
ConfTr
40.59 1.229
39.87=1.02
38.7320084
38.31
38.06440.48
38.06-2.59
ConfTretas
32.91=1.53
32.94
32.94
32.95
33.16+1.47
33. 149
Fano
33.80 20,93
33. 33.7521.02
32.83 1.60
31.71+1.55
30.82+1.72
30.71
MB Fano
21.68
20.97 #1.30
19.32
19.04+1..6
17.35
17.68 0
DPI
17.41
17. 17.25
17.02
16.40.0.93
17.68
19.49 :2.049
Table 14: Inefficiency results for RAPS with varying Areg- Average prediction set size for lieg = 1 and varying Are on CIFARI00 for a target a = 0.01. We report mean and standard deviation across 10 different calib./test splits and show in bold all values within one standard deviation of the best result. Both APS and RAPS results were computed with the same classifier. Lower is better.
Method
Aug = (APS)
Are = 0.01
Arge = 0.08
Arge = 0.1
Aue = 0.3
Areg = 1.0
CE
26.02_1.31
26.02
26.0221.31
26.02
26.02
1..02
ConfTr
10.59_1.23
39.87
39.17
39.09
39.09+..12
39.09
ConfTralass
32.91 1.53
32.94 1..4
32.94
32.93
32.94
92.94411.00
Fano
33.80
33. 33.75411.02
33.75.+1.02
33.75++1.02
33.75++.02
33. 33.75.1..02
MB Fano
21.68 1.44
20.97 1.330
20.96
20.96+1..29
20.96+1.29
20.96+1.28
DPI
17.41 0..2
17.25 17.25
17.25
10.58
17.25
global model thus computed is communicated to the client and the process restarts. We do 5K such communication rounds for EMNIST, and 10K for CIFARIO and CIFARIO0 100. As described in the main text, we divide the data among 100, 500, and IK clients for CIFARIO. CIFAR100 and EMNIST. respectively. We assign data points to devices imposing distribution- label imbalance [33], where we sample a marginal label distribution for each device from Dirichlet distribution. We use Dir(1.0) for all experiments, but also study the effect of Dir(0.5) and Dir(0.1) on CIFAR10, as shown in Tables 15 and 16. The remainder of the experimental setup is similar to that used for the centralized setting, with the same architectures, data augmentation strategies, and optimal hyperparameters reported in Tables 7, 8, 9, 10. In Tables 15 and 16, as well 17 and 18, we report inefficiency results for two different settings. global (GLOO) and personalized (PER).
We run SCP with the final global model assuming calibration and test data sets at the server, or equivalently that the clients share their scores with the server. This reflects the best inefficiency results we can hope for with the global model, as in practice we might need to resort to privacy- preserving methods that are likely to hurt performance. Notably, we considered the quantile of quantiles approach of Humbert et al. [24] as well as the simpler alternative proposed in [37], but in
GLO
33

---

both cases we got varying degrees of coverage due to the data heterogeneity among devices introduced in the Eistribution-basee label imbalance setup. Addressing these shortcomings is a promising avenue for future research for conformal prediction in the federated setting.
PER After learning the global model, we fine-tune it on the local training data of each device to obtain a personalized model. We then run SCP individually for each device with local calibration and test data sets and report the average prediction sets across all clients. Importantly, since each client has access to only a small number of data points, we do not always achieve valid coverage in the personalized setting. More precisely, all personalized models on CIFARTO and EMNIST achieved marginal coverage of around 97%, while for CIFAR 100 that value dropped to 90%. Nonetheless, all methods get similar coverages so the results remain comparable. Interestingly, even with personalized models, which implicitly already estimate Qrix, 2, updating the personalized model in (9) with the global head Q still results in non-negligible improvements in performance, as shown in Tables 15 and 16, as well as 17 and 18.
Table 15: Inefficiency results for different degrees of data heterogeneity in FL with THR. Average prediction set size with THR for CIFARIO with different levels of data heterogeneity among clients for both global (GLO) and personalized (PER) models in the federated setting for target a 0.01. We use +ST to indicate the inclusion of side information. Lower is better.
Method
Dirichlett 1.0)
Dirichlet(O.S)
(irichlet(O.1)
GLO
GLOO,
PER
PER,
GLO
GL.O,st
PER
PER
GLO
GLO,,)
PER
PER,
2.73
2.30
2.07 188
2.81,ua
2.4l.uos 2.08gn.s 1.79
2.73g011
2.32 2.05 182
Coaftr
10.00:amo
10.00 9. 9.8420.0
9.84
10.00.0.00
10.00
9.81gums
9.84a..0
10.00.am
10.000aa0
9.8 2.87 9.87-m0s
ConfTrow
3.39
2.86,0.3
2.79_aa5
3.54
3.38
2.
2.84,0.0
a.
2.84.0.1 o.
Fano
2.39 2.07
1.8420.7
1.632030
2.47a0.8
2.10a0.00
1.942043
1.7
2.46.0.s
2.1
1.91 1.68-0as
MB Fano
2.52.aus
2.04
1.56
1.40_022
2.66
2.09
1037
1.401am0
2.55.e1:
2.061s.00
1.98
166__032
DPI
2.76gom
2.2830
1.64g0.50 1449202 2.503007
2:1130.0 1991g0 1.6430.11
2.
2.0736.0
2.04go.1 1.70.000
Table 16: Inefficiency results for different degrees of data heterogeneity in FL with APS. Average prediction set size with APS for CIFAR10 10 with different levels of data heterogeneity among clients for both global (GLO) and personalized (PER) models in the federated setting for a target & = 0.01. We use +st indicate the inclusion of side information. Lower is better.
Method
Dinichlet 1.0)
Dirichlen(O.5)
Dirichlen(..)
GLO
GL.O.s
PER
PER,.
GLO
GL.O,su
PER
PER
GLO
GL.O.s:
PER
PER
CE
28
2:
2022 1.9
2.70
2. 2.13 187
2.81,014
2.77 2.15
CoafTr
10.00gam0
10.00
9.87
9.87
10.00
10:00.0000
2,88
1.88
10.00.m00
2000
9 9.87 9.87 2014 9.92 o.
ConfTr
10.00.a00
10
9.92g0.00
9.92_aos
10.00
10.00.ooco
9.94go
9.95
10.00ga00
10.00
Fano
2.T3-a0r 2.39 00
2.17.0.40
1.94-03s
2.61
2.302005
2.10en04
1.9220.54
267=000
2.30ga.07
2.1340.42 1.92-004
MB Fano
2.79
1c33
2:28
1.97_ was
2.71
2.31
2.27 in:4s
1.9610.5
2.87.012
2.10
2.32 2o32 1.99 o,30
DPI
2:22
2.11g 184_003 2.54go.10
2.182004 2.10g0 1.840.53
2.65
2.25
2.13....4 189_0o
Table 17: Inefficiency results for global (GLO) and personalized (PER) models with THR.
Average prediction set size with THR for federated conformal training with target a = 0.01. We use +sI to indicate the inclusion of side information. We show in bold all values within one standard deviation of the best result. Lower is better.
Mathod
FMNIST
CIFAR 1O
CIFAR 100
GLO
GI GL.Oas
PER
PER
GLO
Gl GL.O.s
PER
PFR
GLO
GL.O...
PER
PER
2.
a. 20
2.73gn0
2.30gam 2.07
n
55.41g)
52.31gi na 20.84
18.85_
ConfTr
4.80g
3.95 os 3.00ggam 1o
10.00gamm
10:00.00
9.84
984.aa
45.00 an 41.18 in 16:23.n ar 14.01:5.0
ConfTran
2.88
1.98 1.69 aaa 1.55
3.53
3,39
2.86
2.79,0a:
58.53g1.4
36.05g1 as 25.22 7. 23.87 7.00
Fano
2.63:0022
2.37 2. 2.14::0.4 1.98
2.39
2.07:0.07
1.845037
1.63:0m0
47.91:1.0
41.19:1..2 02 18. 18.42
14.55::..5
MB Fano
2.8420044 2,25amm
2. 2007 1.96
2.52.o.e
2 oz
1.56
1.40=o2z
52 52.9
46.9 46.97aum0
20.36
16.41.070
DPI
2.60gnoa
2.23 2.
2.70gmo
2:28
1.64,00s
1.49_a3s
52 22.36
48.6440.0
20.13_7 17.70
34

---

Table 18: Inefficiency results for global (GLO) and personalized (PER) models with APS. Average prediction set size with APS for federated conformal training with a target a = 0.01. We use +si to indicate the inclusion of side information. We show in bold all values within one standard deviation of the best result. Lower is better.
Method
EMNIST
CIFAR 10
CIFAR 100
GLO
GL.Oas
PER
PER,s
GLD
PER
PER..
GLO
GL.O.st
PER
PER
CR
3.14
1.42
1.40ga
2.83,am
2.43n0o
2.23
64 64.73g
62.07g304
22.39
20,2 20.22...10
CoufT:
6.14g044
5.26200r
10.00.000
10.00amm
9.87
9.87.011
15
47,58g
23.43.
ConfTraw
2.05 2.42
g.
151gaa
10.00gmm
10.00g000
9.92
9,92,a
90.92,aus
99.91gom
99.9740.0
99.68
Fano
3.12 2.72:nus
1.17:010
1.1520.11
2.73:0.07
2.39:0.05 2.17,0.45
1.94-oas
46.9520.77
42.75.0.01
19.10-1.24
16.9
MB Funo
4.75aaus
2.4349..
204ana:
2.70
2. 2.33:o
2.28 es
1.97
50.72aur7
45.72etus
21.12:7.4
18. 18.12:
DPI
2,98
2.5820m
2.73g0as
1.29
2.68.00 2:22: 2:11gaa1 1.84000
51.29g107
47.18g1
20.76.7.11
18.15.0.9
G.3 Evaluating the lower bounds on the set size
In this section, we evaluate our two lower bounds on the expected [log [C(X)]]+ The first one can be obtained by rearranging the simple Fano bound (c.f. Proposition C.7) whereas the second one can be obtained from the model- based Fano entropy upper bounds (c.f. Theorem E.2). The main challenge in evaluating these bounds is in that we require the ground truth entropy (Y or (Y)) which in general are not available. To proceed, we adopt the versions of the bounds that depend on HY))). When Ý is discrete, we can get a tractable lower bound to H (( via maximum likelihood estimate of the entropy [46]. More specifically, we have that
H(Y H(Y - HỘ) 2 HMLLE(Y 8) - log |
where |}| is the cardinality of Y
tame tower bound Medeilbssed Fano lower bound
Tame lower bound Model badel fanno lover bound
4.2
Emoirical estimate
Emoirical estimate
35-
30-
60
2.5
03
2.2
15.
031
13-
-0.5
5000
no2s
amoo
8100
6121 5150 n175
5250
3000 n825 amoo
0.77
01m
0155 ni3s 5250
(a) CIFAR 10
(b) CIFAR 100
Figure 2: Expected [log [C(X)]I+ as a function of a.
Based on this, we evaluate our set size bounds on ResNet models trained with CE on CIFAR 10 and CIFAR 100. As the logits Y used for CP are not discrete, we perform K-means clustering on them and construct a vector quantized Y,,. by assigning to each logit vector its closest cluster centroid. We then use YeD, to perform CP with thresholding and also use Yo,, to obtain a lower bound on H HY|) via a maximum likelihood estimate for HY, Yng). For this maximum likelihood estimate we also perform the Miller Madlow bias correction [46].
For CIFAR 10 we cluster the logits into 32 clusters whereas for CIFAR 100 we use 256 clusters. The centroids are learned on a calibration set of 5k logits. For the model-based Fano bound, as it needs to compute terms that depend on the model probabilities and on whether the label was correctly covered by CP or not, we further split the calibration set into two equal-sized chunks; the first used to find the quantile for thresholding and the second one is used to evaluate the terms of the bound. The obtained lower bounds on [log [C(X)]] for various or's can be seen at Figure 2. We also include an "empirical estimate" which is obtained by computing the quantile with the quantized calibration logits
and then measuring the average [log [CX)]] on the test set via thresholding on the quantized test logits. We see that model-basee Fano provides relatively tight estimates for small values of alpha.
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All of our claims supported by experimental results, and we provide detailed proofs for all theoretical results the supplemental material.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We comment on the limitations of our work in Appendix A.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
36

---

Justification: We include detailed proofs for all theoretical results, clearly stating the assumptions (mainly exchangeable data and valid conformal prediction method). We also provide the necessary background on information theory and conformal prediction in Appendix help the reader to follow our derivations.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We did our best to provide as many experimental details as possible, which can be found in the main text as well in Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
37

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: The source code will be hosted at github. info_cp.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
wwt.:euwwwssssooosssooooooooo asionnyiccy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //iiss... wwwpcc/ppcc//aeeeec.ceccce.cetle caublic/guides...e/ htteg/gguudeeeoeeuuubbiiiiiiiiii SCodeSuumissionn ssionooccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
We give detailed description of all of our experiments in Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report one standard deviation confidence intervals, computed across 10 random calibration/test splits, for all of our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
38

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Our experiments are not particularly demanding in the terms of compute and can be reproduced any modern hardware. We do state in Appendix G that ran our experiments in commercially available NVIDIA GPUs.
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https https://nnnt //tpe///nne...eeeeeeee oc
Answer: [Yes]
Justification: Our work is in accordance with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We have a discussion about the broader impact of our work in Appendix A.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
39

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cited the appropriate references for each dataset and, when license is available, we added that information to the citation. We also made it clear that we downloaded all datasets through the torchvision [40] python package.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
40

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
41

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
42


Reviews:
[{"review_id": "p3YUGDt2au", "reviewer": "Reviewer_aseq", "summary": "This work develops the upper bound of conditional entropy H(Y|X) of data generation process by information theoretic inequality. New objective for conformal training and upper bound for the inefficiency (size of prediction set) for a trained model. Including side information to improve the efficiency of CP is also introduced by the proposed upper bound.", "questions": "The reason of limiting alpha in (0,0.5) is not explained in Proposition 3.1, as Theorem 2.1 works for any alpha belongs to (0,1).\n\nSetting alpha=0.01, as stated in the caption of Table.1, is a very limited experiment setup.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "(1) Detailed background information about conformal prediction helps readers build basic understanding easily.\n(2) Extensive theoretical works are presented, demonstrating the soundness of proposed upper bound of the inefficiency of CP for a given model.\n(3) Five datasets and three baselines are included in the experiments. Standard deviation of experimental results are presented as well.", "weaknesses": "(1) Lack of clear notation clarification. For example, the subscripts of Q in Eq. (5) is not explained, making it hard to understand. Also, even if line 136 explains the meaning of H(Y|X), I suggest to write it explicitly for more clearness.\n(2) Lack of full algorithm representation. The work only states that including the upper bound as an additional loss term in line 186, but there is no enough explanation on how the proposed algorithm really works.\n(3) Proof is not self-contained. For instance, the paper leads readers to Appendix D.1 for the proof of DPI bound. And in Appendix D.1, line 806 further lead readers to Theorem C.4, which is not proved in detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and useful feedback. We address the main concerns below.\n\n## Weaknesses\n> Lack of clear notation clarification. For example, the subscripts of Q in Eq. (5) is not explained, making it hard to understand\n\nThe subscripts of $Q$ (and $P$) indicate the random variable described by the distribution, as explained in the first paragraph of Section 2. Following the same logic, we also include conditioning in the notation. For example, $Q_{Y | X, C(X), Y \\in C(X)}$ is a conditional distribution of $Y$ given input variable $X$, prediction set $C(X)$ and the event of coverage $Y \\in C(X).$ We will clarify that in the text.\n\n> I suggest to write it [$H(Y|X)$] explicitly for more clearness.\n\nWe will explicitly define $H(Y|X) = -E_{P_{XY}} [\\log P_{Y |X}]$ in the text.\n\n> Lack of full algorithm representation. The work only states that including the upper bound as an additional loss term in line 186, but there is no enough explanation on how the proposed algorithm really works.\n\nThere is a detailed discussion of conformal training and our experimental setup in appendix F and G, resp. Although we have tried to include enough details on the working of our algorithms, we also agree that a full algorithmic description of the conformal training and federated learning procedures could be helpful and will add those to the appendix. At the end of this answer, we provide a sketch of how conformal training works for each batch, which is similar to [2]. We must highlight, however, that the main contribution of the paper is the new connection between notions of uncertainty given by conformal prediction and information theory. Conformal training is simply a notable application where we demonstrate this connection to be quite useful in practice.\n\n> Proof is not self-contained. For instance, the paper leads readers to Appendix D.1 for the proof of DPI bound. And in Appendix D.1, line 806 further lead readers to Theorem C.4, which is not proved in detail.\n\nWe separated the theoretical results into different sections, concentrating the most important and new results in appendix D. The remaining results in appendices B and C are well-known in the information theory or machine learning communities, and we state them mostly for the sake of completion. We appreciate the feedback though and are happy to state Theorem C.4 just before Proposition 3.1 if that improves readability. \n\nRegarding Theorem C.4. itself, it is a direct application of the classical data processing inequality for $f$-divergences (Theorem C.3) to the conformal prediction procedure, and that is why the proof there is succinct. However, we are happy to expand the proof for clarity, as we show at the end of this answer.\n\n## Questions\n> The reason of limiting alpha in (0,0.5) is not explained in Proposition 3.1, as Theorem 2.1 works for any alpha belongs to (0,1).\n\nThis is explained in equation (19) in the appendix and lines 813 to 817, and is due to the concavity of the binary entropy function. Note that this is not restrictive, since $\\alpha$ values are typically small, and even on the off chance of the user picking $\\alpha > 0.5$, we can also get an upper bound by replacing $h_b(\\alpha)$ with $h_b(\\alpha_n)$. To be precise for $\\alpha > 0.5$, the binary entropy is non-decreasing and preserves the inequality, so we can apply the same argument in (19) to the upper bound of conformal prediction $P(Y_{test} \\in C(X_{test})) \\leq 1-\\alpha_n \\Rightarrow h_b(Y_{test} \\in C(X_{test})) \\leq h_b(1-\\alpha_n) = h_b(\\alpha_n)$.\n\n> Setting alpha=0.01, as stated in the caption of Table.1, is a very limited experiment setup.\n\nWe follow the same setup of the main reference in conformal training [2], where the models were also trained only with $\\alpha=0.01$. Note that we also evaluate our models under different $\\alpha$ values at test time in Table 10 in the appendix, where we also see improved results for other common $\\alpha$ values $\\alpha=0.05$ and $\\alpha=0.1$.\n\n## Sketch of Conformal Training Algorithm\n```\nfor each batch B \n    1. Randomly split B into B_cal and B_test\n    2. Use B_cal to compute the empirical 1-alpha quantile using differentiable sorting\n    3. Construct a prediction set C(x) for each x in B_test using a smooth assignment (see eq. 29)\n    4. At this point we have all we need to compute any of the upper bounds to H(Y|X) in a differentiable manner\n    5. Update model parameters to minimize the upper bound to H(Y|X) via gradient descent\n```\n\n## Detailed proof of Theorem C.4 \nConsider the conditional distribution $P_{E|X,Y}$ mapping distributions $P_{X,Y}$ and $Q_{X,Y}$ to $P_E$ and $Q_E$, respectively. From here, it suffices to apply Theorem C.3, but we can break it down further as follows. Consider the joints induced by this mapping $P_{E,X,Y} = P_{E|X,Y}P_{XY}$ and $Q_{E,X,Y} = P_{E|X,Y}Q_{XY}$, and the following two basic properties of $f$-divergences as applied to this specific case (see e.g. [1]):\n    $$D_f(P_{E,X,Y} || Q_{E,X,Y}) = D_f(P_{X,Y} || Q_{X,Y})$$ and  $$D_f(P_{E,X,Y} || Q_{E,X,Y}) \\geq D_f(P_{E}||Q_{E}).$$\n    The proof then follows directly from these two results with $D_f(P_{X,Y} || Q_{X,Y}) \\geq D_f(P_{E}||Q_{E}).$\n\n## References\n\n[1] Polyanskiy, Y. and Wu, Y. \"Lecture notes on information theory\". Lecture Notes for ECE563 (UIUC) and, 6(2012-2016):7, 2014. 17, 18\n\n[2] Stutz, David, et al. \"Learning Optimal Conformal Classifiers.\" ICLR 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nMEvRQ7msf", "reviewer": "Reviewer_T2Vh", "summary": "The paper aims to relate the uncertainty measured by conformal prediction by the uncertainty measured by the conditional entropy $H(Y|X)$. Towards this end, they make the following contributions:\n1. They observe that the miscoverage quantity from conformal prediction is the same as the decoding-error quantity from list decoding in information theory.\n2. They exploit this observation to upper bound the conditional entropy $H(Y|X)$ in terms of quantities from conformal prediction.\n3. They use these bounds as objectives for conformal training in order to maximize efficiency i.e keep the prediction sets as small as possible. \n4. They empirically verify that their modifications to conformal training using their upper bounds improve efficiency.", "questions": "1. Could you answer W1 above, and in general connect the theoretical results to epistemic/aleatoric uncertainty?\n\nI am happy to change my assessment/confidence if the authors are able to alleviate my concerns through discussion.", "limitations": "Yes\n\n\n---------\n\nEDIT POST REBUTTAL:\n\nAfter discussing with the authors, I have increased my score to 6. The authors have done a great job in the discussion of contextualizing the results in terms of epistemic&aleatoric uncertainty. My hope is that the authors in the final version will:\n1. Modify the exposition of the paper to discuss the role of these categories of uncertainty.\n2. In the discussion section, be upfront about the looseness of the bounds when epistemic uncertainty is high.\n3. In the discussion, mention the challenges to quantifying the epistemic uncertainty theoretically.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "**Originality** The problem of relating the uncertainty measured in information theory to that from conformal prediction is very interesting avenue of exploration.", "weaknesses": "**Clarity and Quality** \n\nIn general, it is confusing to interpret what the results are really saying. In particular, I have the following confusion about the theoretical result that remains after reading the paper:\n1. $H(Y|X)$ only measures aleatoric uncertainty whereas the conformal interval captures both aleatoric and epistemic uncertainty. So then, it is not surprising that the conditional entropy would be upper bounded by something in terms of the conformal size $|C(X)|$. Is this the correct interpretation for the Propositions, or is there something else going on here?\n\nFor the empirical result:\n\n2. In Section 4, the authors state that minimizing the RHS of the Fano bound is equivalent to the ConfTr objective from [7]. However, in the tables, the rows corresponding to ConfTr and Fano admit different efficiency - what is the cause of this?\n\n3. What is the intuition for why minimizing the RHS of the bounds is better than minimizing $|C(X)|$ directly?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments and interesting questions, which we discuss below.\n\n> $H(Y|X)$ only measures aleatoric uncertainty whereas the conformal interval captures both aleatoric and epistemic uncertainty. So then, it is not surprising that the conditional entropy would be upper bounded by something in terms of the conformal size $|C(X)|$. Is this the correct interpretation for the Propositions, or is there something else going on here?\n\nThis intuition is absolutely correct. Yet, even though the cardinality of the prediction set size provides an intuitive notion of uncertainty, quantitatively connecting it to the aleatoric or even total uncertainty is non-trivial. Importantly, the prediction set size varies with the user-defined miscoverage rate $\\alpha$, whereas arguably any notion of uncertainty should not. Our upper bounds account for that, and $\\alpha$ comes up quite naturally in the derivation of all three bounds. Moreover, it is worth noticing $|C(X)|$ only appears explicitly on the simple Fano bound, which is expected to the be the least tight among our three bounds, further illustrating the difficulty in connecting the cardinality of the prediction set size to other established notions of uncertainty.\n\n> In Section 4, the authors state that minimizing the RHS of the Fano bound is equivalent to the ConfTr objective from [7]. However, in the tables, the rows corresponding to ConfTr and Fano admit different efficiency - what is the cause of this?\n\nEquation (8) is equivalent to the ConfTr objective but not to the simple Fano bound of equation (6), and hence why the results are different. We will update the wording in section 4 to make this more evident. In section F.1, we actually prove the simple Fano bound is a tighter upper bound to the conditional entropy than the ConfTr objective, i.e., $H(Y|X) \\leq (6) \\leq (8).$\n\n> What is the intuition for why minimizing the RHS of the bounds is better than minimizing $|C(X)|$ directly?\n\nFrom a theoretical perspective, we argue in Section 4 that minimizing an upper bound to the data aleatoric uncertainty, as captured by $H(Y|X)$, is a reasonable optimization objective. This motivation also justifies the cross-entropy and $\\log |C(X)|$ as learning objectives, but from this angle, our upper bounds are actually tighter bounds to $H(Y|X)$ and thus likely to be more effective: The DPI bound is provably tighter than the cross-entropy (see Remark D.1 in the appendix) and the simple Fano bound is tighter than the ConfTr objective that minimizes $\\log |C(X)|$ directly as mentioned in the answer above.\n\nFrom a practical perspective, $\\log |C(X)|$ alone might not provide a strong enough learning signal to fit complex models (see e.g. ConfTr results for CIFAR in Table 1) and an extra hyperparameter needs to be introduced to balance between optimizing $\\log |C(X)|$ and some other loss function like the cross-entropy which gives the ConfTr class objective. In contrast, our upper bounds, especially DPI and Model-based Fano ones, already capture both efficiency and predictive power of the model, with no need for extra hyperparameters. Moreover, in our experiments, our upper bounds proved to be more robust, whereas ConfTr and ConfTr class failed to converge in some cases even after hyperparameter fine-tuning (see, for example, ConfTr results on THR/MNIST in Table 1).\n\n> Could you connect the theoretical results to epistemic/aleatoric uncertainty?\n\nThat is an important point, and one of our objectives in this paper was indeed to improve the current understanding of how conformal prediction relates to other forms of uncertainty quantification, where the separation between epistemic and aleatoric uncertainty is already more established (albeit still not solved [1]). To the best of our knowledge, this separation has never been made in the conformal prediction literature and remains an entirely open question [2]. The main challenge in the context of conformal prediction is in characterizing the epistemic uncertainty  without further information or assumptions on the model. Since epistemic uncertainty is a property of the model itself and not the data, it requires  an understanding of the model's hypothesis space, for example via a distribution over the model parameters in the Bayesian setting; something that conformal prediction ignores or abstracts away via the scoring function. That is why in this paper we focus on the data aleatoric uncertainty $H(Y | X)$ as its connection to conformal prediction is more tangible, as evidenced by our upper bounds.  \n\n### References\n\n[1] Wimmer, Lisa, et al. ”Quantifying aleatoric and epistemic uncertainty in machine learning: Are conditional entropy and mutual information appropriate measures?.” Uncertainty in Artificial Intelligence. PMLR, 2023.\n\n[2] Hullermeier, Eyke, and Willem Waegeman. ”Aleatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods.” Machine learning 110.3 (2021): 457-506.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xoRUz4KYCE", "reviewer": "Reviewer_oiJy", "summary": "This paper observes a connection between the efficiency of CP (tightness of its prediction sets) and information theory. It uses this to derive 3 bounds on a CP's efficiency depending on the entropy of the label given a data record H(Y|X). It then uses these bounds as the optimization objective for the underlying model (nonconformity scorer). The bounds are empirically shown to be valid (i.e., reasonable) training objectives.", "questions": "Thank you for your submission!\n\nI'm afraid I could not understand how the connection to list decoding was used when deriving your results. I can see this is being discussed in the appendix, but perhaps it'd be best to mention in the main body which ideas are borrowed from that theory, and how they're being used here. (Can you please clarify, in your rebuttal?)\n\nI did not quite understand why federated learning was introduced in this paper; I didn't feel like it was necessary, and it almost feels like an afterthought. Perhaps it'd be best to motivate it better in the introduction.\n\n\"To the best of our knowledge, Bellotti [8] were the first to advance the idea of conformal training.\"\nNote that, concurrently to Bellotti, this idea was also discovered by Colombo and Vovk in \"Training conformal predictors\".\n\n\nWhile your work is the first one to deal with the interesting intersection between information theory and CP efficiency, please note that other works have looked at:\n1. connecting CP efficiency to the goodness of the underlying algorithm; e.g.:\n- (Dhillon et al.) On the Expected Size of Conformal Prediction Sets\n- (Cherubin) How do the performance of a Conformal Predictor and its underlying algorithm relate?\n\nand also\n\n2. how to best characterize the efficiency of a CP: (Vovk et al.) Criteria of efficiency for conformal prediction.", "limitations": "These were appropriately described by the paper.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- This paper is _truly_ well written: it explains extremely well prior literature as well as the concepts being presented. The appendix is also well-curated.\n- The idea behind this paper (to connect information theory and CP) is very interesting, and I'm sure it'll lead to more research.\n- The theoretical analysis is non-trivial and insightful.", "weaknesses": "- Bounds based on Fano's inequality may be loose.\n- Empirically, the method does not outperform SOTA; however, I do think there's more value in this work than just improving CP numerically.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's insightful comments and are encouraged by the positive feedback and recognition of our work's significance. We answer the remaining questions below.\n\n> Bounds based on Fano's inequality may be loose.\n\nThat is definitely true of the simple Fano bound, where we assume a uninformative uniform distribution over the labels. However, the model-based Fano bound should be tight for a model $Q$ that approximates the true distribution $P$ well enough.\n\n> Empirically, the method does not outperform SOTA; however, I do think there's more value in this work than just improving CP numerically.\n\nWhile there was no clear winner among our bounds, they still improve on ConfTr variants in two ways: (i) the DPI and model-based Fano bounds proved more effective than ConfTr on training complex models from scratch (e.g. in the CIFAR results in Table 1) and (ii) our bounds also seem to be more robust than ConfTr, since even after fine tuning hyperparameters as described in Section G.1, ConfTr often failed to converge properly (e.g. ConfTr performance in MNIST in Table 1 was worse than expected due to training instability).\n\n> I'm afraid I could not understand how the connection to list decoding was used when deriving your results. I can see this is being discussed in the appendix, but perhaps it'd be best to mention in the main body which ideas are borrowed from that theory, and how they're being used here. (Can you please clarify, in your rebuttal?)\n\nIndeed, the main results can be derived without resorting to list decoding. We mostly derive our results directly using the data processing or Fano's inequality, as shown in Appendix D. We highlight the connection to list decoding because it is quite natural and might bring more interesting results to both fields in the future. In fact, a slightly looser version of our simple Fano bound can be obtained directly from Fano's inequality for list decoding, see Theorem C.6 and Proposition C.7 in the appendix.\n\n> I did not quite understand why federated learning was introduced in this paper; I didn't feel like it was necessary, and it almost feels like an afterthought. Perhaps it'd be best to motivate it better in the introduction.\n\nThe information theoretic perspective also facilitates the usage of side information in conformal prediction, as we discuss in Section 5. Federated learning just happens to be a natural and elegant application of both conformal training and side information, as the global objective factorizes nicely into local objectives that can be computed locally in each device with the device ID as side information. This scenario can be quite useful in practice, and is perhaps a more convincing use case for side information than assuming access to superclass information like in the experiments in Table 2.\n\n> Note that, concurrently to Bellotti, this idea was also discovered by Colombo and Vovk in \"Training conformal predictors\".\n\nThanks for bringing that work to our attention. We will definitely cite and discuss it in the final version of the paper.\n\n> Related work\n\nThanks for the extra references. We will discuss these contributions in the paper, and the work of Dhillon et al. in particular is also relevant to our experiments in Appendix G.3, where we also use our results to lower bound the expected prediction set size.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aUx9s1bbEi", "reviewer": "Reviewer_XnUM", "summary": "The paper provides a series of upper bounds for the conditional entropy of the labels given the attributes. The right-hand side of the bounds depends on the coverage probability of the corresponding Conformal Prediction sets. The authors propose to use the bound as an alternative objective function for conformal training.", "questions": "- Is the prediction set in Equation 3 calibrated using $P$?  \n- What do you mean by *to learn machine learning models that are more amenable to SCP*?\n- Where is the conditional entropy defined? Is the right-hand side of Equation 3 guaranteed to be positive? \n- Is $Q$ supposed to be an approximation of $P$ learned from data?\n- Is $W$ required to be a stochastic map? What happens if $W$ is deterministic?\n- Would it be possible to add a baseline trained in a standard way, i.e. without conformal training?", "limitations": "I appreciate the authors addressed their work's limitations in a dedicated section. Perhaps, the paper misses a theoretical and intuitive justification for using the bounds for conformal training.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The link between Conformal Prediction (CP) and List Decoding is inspiring, even if it is partly unclear how it is used in the bounds.  \n- Using CP distribution-free and finite sample properties to compute empirical bounds is interesting and may have an impact beyond the CP community.\n- I like the idea of using the bounds for training CP algorithms.", "weaknesses": "- The authors may explain more intuitively the role of the arbitrary distribution $Q$. Later in the paper $Q$ seems to be linked to the underlying point-predictor. An explicit construction (in the Introduction) would help motivate the proposed approach.\n- The practical consequences of the authors' findings could be clarified better.\n- A few practical examples would be helpful. For example, the authors may add a concrete way to define $Q$ at the end of Section 3.1.\n- The technical contribution seems a relatively straightforward consequence of the inequality $H(Y|X) < H(w_Y(Y, X)|w_X(Y, X))$.\n- The challenging part of optimizing a CP algorithm is smoothing the sorting operation. The proposed training method does not seem to solve or address that problem. The authors should justify better the use of conditional entropy instead of ${\\rm E}(|{\\cal C}|)$. In particular, how an upper bound could be more efficient than the original objective function?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments. We address the main concerns below.\n\n> The authors may explain more intuitively the role of the arbitrary distribution $Q$.\n\nOne can think of our results as way to upper bound the (irreducible) data aleatoric uncertainty $H(Y|X)$ of the true data distribution $P$ by leveraging conformal prediction and another distribution $Q$. We present our results in all generality, as they hold for any distribution $Q_{X,Y} = P_X Q_{Y|X}$, but clearly $Q$ will be more informative and lead to tighter bounds if it is a good approximation to $P$.\n\n> Is $Q$ supposed to be an approximation of $P$ learned from data?\n\nIn short, yes. In the conformal training experiments, we directly learn $Q_{Y|X}$ from data to tighten our bounds.\n\n> [...] the authors may add a concrete way to define $Q$ at the end of Section 3.1.\n\nIn Section 3.2, specifically lines 156 to 156, we comment on two good choices for $Q_{Y|X}$, namely the predictive model itself (the very same used to construct the prediction sets) or a uniform distribution, which leads to the model-based (eq. 5) and simple Fano (eq. 6) bounds, resp. We will make this point more evident in the text.\n\n> The technical contribution seems a relatively straightforward consequence of the inequality $H(Y|X) < H(w_Y(Y,X)|w_X(Y,X)).$\n\nCould you clarify what you mean by this inequality on conditional entropies? Unless we are missing something, it does not hold in general; naively taking $w_Y(Y,X) = Y$ and $w_X(Y,X)=Y$, we get $H(w_Y(Y,X)|w_X(Y,X))=0.$ Our results are proven using canonical information theoretical inequalities like Fano and DPI, but they require a tailored choice of distributions as well as considering mathematical subtleties of including marginal coverage guarantees of conformal prediction in the bound.\n\n> The paper misses a theoretical and intuitive justification for using the bounds for conformal training.\n\nWe provide a motivation in section 4, lines 187 to 190, which can be summed up as follows. Our results upper bound the irreducible uncertainty of the true distribution $P$, as given by the conditional entropy $H(Y|X)$. Thus, if we fit a model $Q_{Y|X}$ to minimize our upper bounds, we can argue we push $Q_{Y|X}$ closer to the true conditional distribution $P_{Y|X}$, using the training data to decrease the \"reducible\" uncertainty as much as possible. Although we are not aware of previous work leveraging the same motivation, the same argument could also be used to justify the cross-entropy, which also upper bounds $H(Y|X)$, with equality when $Q_{Y|X}=P_{Y|X}$.\n\n> The challenging part of optimizing a CP algorithm is smoothing the sorting operation. The proposed training method does not seem to solve or address that problem.\n\nOur main contribution is a new connection between notions of uncertainty coming from information theory and conformal prediction. Conformal training is simply a useful application of that connection, where we demonstrate that our methods lead to equivalent or better results than the original ConfTr objective (we use the exact same relaxation of the sorting operator for all methods). The fact that we do not address what is perceived as the main challenge in conformal training does not mean our results are not relevant in that context.\n\n> The authors should justify better the use of conditional entropy instead of $E|C(X)|$. In particular, how an upper bound could be more efficient than the original objective function?\n\nWe provide a justification in section 4 and clarify further in the answers above. The last point seems to be a misunderstanding of our results. We provide upper bounds to the conditional entropy $H(Y|X)$ and not $E|C(X)|$. We also show in the end of section 4 and appendix F.1, that the ConfTr objective, i.e. $\\log E|C(X)|$, is also an upper bound to $H(Y|X)$, but a looser one than the simple Fano bound. Therefore, if we adhere to the motivation of minimizing an upper bound to $H(Y|X)$, our upper bounds should in theory give better results.\n\n> Is the prediction set in Equation 3 calibrated using $P$?\n\nYes. Yet, many recent works have extended conformal prediction to more general settings where calibration and test points are not identically distributed (see e.g. [1,2]), and in principle our results can also be extended to this setting if the conformal prediction method in question still provides lower and upper bounds for $P(Y_{test} \\in C(X_{test})).$\n\n> What do you mean by to learn machine learning models that are more amenable to SCP?\n\nConformal prediction sets ultimately depend on the characteristics of the predictive model used to construct them. For example, two models with the same accuracy could lead to different prediction sets, and in that sense, one could say the model which produces more informative (narrower) sets is more amenable to conformal prediction than the other. The idea of conformal training is exactly to steer the training process towards those models that are more amenable to conformal prediction.\n\n> Where is the conditional entropy defined?\n\nWe will explicitly define $H(Y|X) = -E_{P_{XY}} [\\log P_{Y |X}]$ in the text.\n\n> Is the right-hand side of Equation 3 guaranteed to be positive?\n\nYes, the proof in section D.1 proves this.\n\n> Is $W$ required to be a stochastic map? What happens if $W$ is deterministic?\n\nThe result (Theorem C.3) holds for deterministic maps as well.\n\n> Would it be possible to add a baseline trained in a standard way, i.e. without conformal training?\n\nSuch a baseline is already included in all our results, namely models trained purely via the cross-entropy that we identify by the acronym CE. We will make this more clear in the text.\n\n### References\n\n[1] Barber, Rina Foygel, et al. \"Conformal prediction beyond exchangeability.\" The Annals of Statistics 51.2 (2023): 816-845.\n\n[2] Prinster, Drew, et al. \"Conformal Validity Guarantees Exist for Any Data Distribution (and How to Find Them).\" ICML 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The main idea of the paper is to show how the uncertainty measured by conformal prediction is related to the the uncertainty measured by the conditional entropy. Towards this end, the authors show that miscoverage in CP  corresponds to list decoding error, and using this observation the authors provide an upper bound for the conditional entropy in terms of quantities from conformal prediction. Such bounds/insights are then used from conformal training to improve efficiency.

All the major concerns of the reviewers have been resolved after the rebuttal process, and based on the reviewers' recommendations and my reading of the paper, I would recommend acceptance. The paper provides a novel perspective on CP from the lens of information theory.
Decision: Accept (poster)