An Information Theoretic Perspective on Conformal Prediction

We thank the reviewer for the insightful comments. We address the main concerns below.

The authors may explain more intuitively the role of the arbitrary distribution $Q$.

One 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$.

Is $Q$ supposed to be an approximation of $P$ learned from data?

In short, yes. In the conformal training experiments, we directly learn $Q_{Y|X}$ from data to tighten our bounds.

[...] the authors may add a concrete way to define $Q$ at the end of Section 3.1.

In 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.

The technical contribution seems a relatively straightforward consequence of the inequality $H(Y|X) < H(w_Y(Y,X)|w_X(Y,X)).$

Could 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.

The paper misses a theoretical and intuitive justification for using the bounds for conformal training.

We 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}$.

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.

Our 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.

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?

We 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.

Is the prediction set in Equation 3 calibrated using $P$?

Yes. 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})).$

What do you mean by to learn machine learning models that are more amenable to SCP?

Conformal 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.

Where is the conditional entropy defined?

We will explicitly define $H(Y|X) = -E_{P_{XY}} [\log P_{Y |X}]$ in the text.

Is the right-hand side of Equation 3 guaranteed to be positive?

Yes, the proof in section D.1 proves this.

Is $W$ required to be a stochastic map? What happens if $W$ is deterministic?

The result (Theorem C.3) holds for deterministic maps as well.

Would it be possible to add a baseline trained in a standard way, i.e. without conformal training?

Such 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.

References

[1] Barber, Rina Foygel, et al. "Conformal prediction beyond exchangeability." The Annals of Statistics 51.2 (2023): 816-845.

[2] Prinster, Drew, et al. "Conformal Validity Guarantees Exist for Any Data Distribution (and How to Find Them)." ICML 2024.

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.

Bounds based on Fano's inequality may be loose.

That 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.

Empirically, the method does not outperform SOTA; however, I do think there's more value in this work than just improving CP numerically.

While 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).

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?)

Indeed, 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.

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.

The 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.

Note that, concurrently to Bellotti, this idea was also discovered by Colombo and Vovk in "Training conformal predictors".

Thanks for bringing that work to our attention. We will definitely cite and discuss it in the final version of the paper.

Related work

Thanks 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.

We thank the reviewer for the insightful comments and interesting questions, which we discuss below.

$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?

This 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.

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?

Equation (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).$

What is the intuition for why minimizing the RHS of the bounds is better than minimizing $|C(X)|$ directly?

From 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.

From 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).

Could you connect the theoretical results to epistemic/aleatoric uncertainty?

That 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.

References

[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.

[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.

We thank the reviewer for the comments and useful feedback. We address the main concerns below.

Weaknesses

Lack of clear notation clarification. For example, the subscripts of Q in Eq. (5) is not explained, making it hard to understand

The 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.

I suggest to write it [$H(Y|X)$] explicitly for more clearness.

We will explicitly define $H(Y|X) = -E_{P_{XY}} [\log P_{Y |X}]$ in the text.

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.

There 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.

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.

We 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.

Regarding 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.

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).

This 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)$.

Setting alpha=0.01, as stated in the caption of Table.1, is a very limited experiment setup.

We 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$.

Sketch of Conformal Training Algorithm

for each batch B 
    1. Randomly split B into B_cal and B_test
    2. Use B_cal to compute the empirical 1-alpha quantile using differentiable sorting
    3. Construct a prediction set C(x) for each x in B_test using a smooth assignment (see eq. 29)
    4. At this point we have all we need to compute any of the upper bounds to H(Y|X) in a differentiable manner
    5. Update model parameters to minimize the upper bound to H(Y|X) via gradient descent

Detailed proof of Theorem C.4

Consider 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]): $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}).$ 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}).$

References

[1] Polyanskiy, Y. and Wu, Y. "Lecture notes on information theory". Lecture Notes for ECE563 (UIUC) and, 6(2012-2016):7, 2014. 17, 18

[2] Stutz, David, et al. "Learning Optimal Conformal Classifiers." ICLR 2022.