An Information Theoretic Perspective on Conformal Prediction

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.

Paper

References (74)

Scroll for more · 38 remaining

Similar papers

Peer review

Reviewer XnUM5/10 · confidence 3/52024-07-02

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.

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. - Using CP distribution-free and finite sample properties to compute empirical bounds is interesting and may have an impact beyond the CP community. - 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. - The practical consequences of the authors' findings could be clarified better. - 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. - The technical contribution seems a relatively straightforward consequence of the inequality $H(Y|X) < H(w_Y(Y, X)|w_X(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. 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?

Questions

- Is the prediction set in Equation 3 calibrated using $P$? - What do you mean by *to learn machine learning models that are more amenable to SCP*? - Where is the conditional entropy defined? Is the right-hand side of Equation 3 guaranteed to be positive? - Is $Q$ supposed to be an approximation of $P$ learned from data? - Is $W$ required to be a stochastic map? What happens if $W$ is deterministic? - Would it be possible to add a baseline trained in a standard way, i.e. without conformal training?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

2

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.

Reviewer oiJy8/10 · confidence 4/52024-07-11

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.

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. - The idea behind this paper (to connect information theory and CP) is very interesting, and I'm sure it'll lead to more research. - The theoretical analysis is non-trivial and insightful.

Weaknesses

- Bounds based on Fano's inequality may be loose. - Empirically, the method does not outperform SOTA; however, I do think there's more value in this work than just improving CP numerically.

Questions

Thank you for your submission! 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?) 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. "To the best of our knowledge, Bellotti [8] were the first to advance the idea of conformal training." Note that, concurrently to Bellotti, this idea was also discovered by Colombo and Vovk in "Training conformal predictors". While 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: 1. connecting CP efficiency to the goodness of the underlying algorithm; e.g.: - (Dhillon et al.) On the Expected Size of Conformal Prediction Sets - (Cherubin) How do the performance of a Conformal Predictor and its underlying algorithm relate? and also 2. how to best characterize the efficiency of a CP: (Vovk et al.) Criteria of efficiency for conformal prediction.

Rating

8

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

These were appropriately described by the paper.

Reviewer T2Vh6/10 · confidence 2/52024-07-13

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: 1. They observe that the miscoverage quantity from conformal prediction is the same as the decoding-error quantity from list decoding in information theory. 2. They exploit this observation to upper bound the conditional entropy $H(Y|X)$ in terms of quantities from conformal prediction. 3. They use these bounds as objectives for conformal training in order to maximize efficiency i.e keep the prediction sets as small as possible. 4. They empirically verify that their modifications to conformal training using their upper bounds improve efficiency.

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** In 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: 1. $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? For the empirical result: 2. 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? 3. What is the intuition for why minimizing the RHS of the bounds is better than minimizing $|C(X)|$ directly?

Questions

1. Could you answer W1 above, and in general connect the theoretical results to epistemic/aleatoric uncertainty? I am happy to change my assessment/confidence if the authors are able to alleviate my concerns through discussion.

Rating

6

Confidence

2

Soundness

2

Presentation

2

Contribution

2

Limitations

Yes --------- EDIT POST REBUTTAL: After 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: 1. Modify the exposition of the paper to discuss the role of these categories of uncertainty. 2. In the discussion section, be upfront about the looseness of the bounds when epistemic uncertainty is high. 3. In the discussion, mention the challenges to quantifying the epistemic uncertainty theoretically.

Reviewer aseq5/10 · confidence 3/52024-07-17

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.

Strengths

(1) Detailed background information about conformal prediction helps readers build basic understanding easily. (2) Extensive theoretical works are presented, demonstrating the soundness of proposed upper bound of the inefficiency of CP for a given model. (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. (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. (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.

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). Setting alpha=0.01, as stated in the caption of Table.1, is a very limited experiment setup.

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

N/A

Reviewer XnUM2024-08-12

thank you for your answers

The rebuttal clarifies my doubts. Sorry for the strict inequality typo in my question. I meant <= instead of <. After reading the authors' answers and the other reviewers' comments, I tend to confirm my score. But I would not vote against acceptance.

Authorsrebuttal2024-08-13

We are grateful that the reviewers went through our answers and happy that we could address the reviewer's doubts. We are also happy that the reviewer is not voting against acceptance. In that light, we would like to kindly ask what needs to be changed in the paper so it passes the acceptance bar. We are under the impression that the current requests are addressable with minimal changes in the camera ready version, but we would be happy to be aware of bigger changes the reviewer has in mind.

Reviewer oiJy2024-08-12

Thank you for your response. > Indeed, the main results can be derived without resorting to list decoding. I do appreciate the intellectual honesty in the above comment. But if that's the case, you may want to: 1) remove the list decoding discussion (sorry!), or put it in a separate section that isn't part of the main discussion (e.g., a section before conclusions), 2) or, try and rephrase your proofs to actually use it. (If you do go down this root, you should of course mention that your results don't actually _need_ the list decoding theory.) The latter would of course be preferable, especially because the connection to list decoding is indeed quite interesting. Please treat the above as a recommendation, not a requirement. I will keep my positive score.

Authorsrebuttal2024-08-13

Thanks for the suggestions. We will move the discussion on list decoding to the final stages of the paper to improve readability.

Reviewer T2Vh2024-08-13

Rebuttal response

I thank the authors for clarifying my questions. I think that the goal of relating conformal intervals to epistemic and aleatoric uncertainty is a very well-motivated goal, and conceptually very useful for the ML community -- given the application of UQ in safety-critical applications. Additionally, it is a theoretically challenging pursuit, so I commend the authors on their efforts. However, I still think the results are confusing to interpret, and does not appropriately shed much light on this motivating question. Additionally, the discussion of the authors in the rebuttal around AU and EU appears a bit confused. In particular, the authors mention that "epistemic uncertainty is a property of the model itself and not the data". However, even the paper [1] that the authors link mentions that: > EU then refers to a lack of knowledge about the discrepancy between $p$ and $\hat{p}$ that can – in contrast to AU – be alleviated by gathering more training samples. This is the more standard definition of EU that I am aware of. So either the authors are using the terminology incorrectly or defining things differently, but these new definitions are not clear. For these reasons, I will stick with my score. I would encourage the authors to motivate their paper from the perspective of AU, EU and frame the results explicitly in these terms as well, by addressing these confusions.

Authorsrebuttal2024-08-13

We would like to thank the reviewer for engaging in the discussion. First of all, we must clarify that we share the same the notion of epistemic uncertainty; it is indeed given by the gap between $p$ and $\hat p$, and can be alleviated with more training samples. In that sense, for a fixed $p$, the epistemic uncertainty is only a function of the model $\hat p$. We apologize if stating epistemic uncertainty is a property of the model created confusion, but such characterization is also common in the literature (see e.g. the discussion in the introduction in [3]). While the general definition of epistemic uncertainty might be simple on the surface, actually quantifying this gap does involve assumptions about the model. The same reference quoted by the reviewer [1], states in section 2.1 > To capture EU [epistemic uncertainty], the learner must be able to express uncertainty about $\theta$ [model parameters], which can be accomplished by a (second-order) probability distribution over (first-order) distributions $\theta$. Conformal prediction methods pose no assumptions on the underlying machine learning model and typically leverages a single predictor/scoring function. In that setting, there is no clear way to represent the uncertainty over the model parameters (or more generally over the model's hypothesis space) and capture epistemic uncertainty, as also highlighted in [2]: > Machine learning methods for probability estimation, i.e., for training a probabilistic predictor, often commit to a single hypothesis learned on the data, thereby ignoring epistemic uncertainty. As we mentioned in our rebuttal, that is why we focused on the data aleatoric uncertainty, since quantifying epistemic uncertainty would require assumptions about the model hypothesis space that, at least for now, are not directly connected to any conformal prediction method, and thus are outside the scope of this work. We share the reviewer's appreciation for the goal of connecting conformal prediction to other notions of uncertainty, and we would argue that relating it to the data aleatoric uncertainty, as we have in this paper, is a valid contribution and a solid first step towards that goal. Further, we would like to emphasize that there are important contributions to uncertainty quantification without epistemic and aleatoric decomposition, and conformal prediction is a notable example. We see our work within this line of research, and as we showed in the paper, our results already proved useful in practical applications, namely conformal training and incorporation of side information. We hope to have addressed the reviewer's concerns around this topic. ### Extra references [3] Bengs, Viktor, Eyke Hüllermeier, and Willem Waegeman. "Pitfalls of epistemic uncertainty quantification through loss minimisation." Advances in Neural Information Processing Systems 35 (2022): 29205-29216.

Reviewer T2Vh2024-08-13

Response

Thank you for the ongoing discussion. To clarify, the confusion was stemming from the fact that you mentioned that "epistemic uncertainty is not a property of the data", whereas the learned model $\hat{p}$ depends on both the model family as you mention but also the training data - which you later seem to agree with. Here is my remaining question: If the learned model is bad (due to small or biased data for e.g), the conformal interval will increase in size since the residuals used in constructing the interval will increase. So it is capturing some notion of epistemic uncertainty. Even if the aleatoric uncertainty were $0$ but the data is bad, the conformal interval would not shrink to 0. Having small aleatoric uncertainty is pretty common in ML settings when the labels are assumed to be a deterministic function of the inputs (perhaps with some small additive noise) e.g in image classification. In such a case, the bounds appear to be saying that the noise level $\leq$ log of conformal set size. Which could be an arbitrarily loose inequality. Could you comment on the tightness of the provided bounds in different settings? And how the level of epistemic uncertainty may play into the looseness of the bound.

Authorsrebuttal2024-08-14

Thanks again for the interesting discussion. Those are good questions. We start with the question around the tightness of the bounds, having small aleatoric uncertainty, and whether it leads to an arbitrary loose inequality. It is important to distinguish among our three bounds. **Simple Fano bound**. The reviewer is correct that the simple Fano bound (eq. 6) can be loose in general, since the expected prediction set size would not shrink to zero, even when $Y$ is a deterministic function of $X$. It would not be arbitrarily loose because all the terms are bounded, but in the limit, for a completely uninformative model with $|C(X)|=|\mathcal Y|$, it will essentially converge to $H(Y|X) \leq H(X) \leq \log(|\mathcal Y|).$ Conversely, in the case of lower epistemic uncertainty, the bound would be tighter, since the more capable model would lead to narrower prediction set sizes, as the reviewer pointed out. **DPI bound**. This bound directly leverages the model, as represented by the distribution $Q$. It is easy to verify that the DPI bound is tight in the case of zero epistemic uncertainty, i.e. $P=Q$. This is evident in eq. 18, where the KL term would be zero and the cross-entropy would be $H(Y|X)$ by definition. Epistemic uncertainty plays a role here, since for $P\neq Q$ the cross-entropy is only an upper bound to $H(Y|X)$, which in principle can be arbitrarily loose for a very bad $Q$. Curiously, the KL term in eq. 18, actually tightens the bound in comparison to the cross-entropy alone, which is an interesting aspect of this result. Note that this argument is general and holds for any $H(Y|X)$, even when $H(Y|X)=0$. **Model-based Fano**. The model-based Fano bound follows a similar pattern, and the role of epistemic uncertainty is clear in eq. 21, where it is captured in the two KL divergence terms in the second equality. For $P=Q$, these KL terms are exactly zero, tightening the bound. Now, we address the second question around the role of epistemic uncertainty in our bound. In all three cases, epistemic uncertainty definitely plays a role in the tightness of the bounds, either via the expected prediction set size or directly via the model distribution in $Q$. While the role of epistemic uncertainty might be clear qualitatively, what we tried to convey in the rebuttal is that quantifying it exactly is quite challenging using conformal prediction alone (it is already complicated in other contexts as discussed in the references we shared), and that is why we refrained from touching on the aleatoric/epistemic decomposition in the paper. However, we are happy to include the discussion above in the text, if the reviewer thinks it would add to the paper.

Reviewer aseq2024-08-13

Rebuttal received and read

The limitation of using just alpha=0.01 is addressed by Table 10. Thank the authors for pointing this out. I raised my rating to 5.

Authorsrebuttal2024-08-13

Thank you again for your thoughtful review. We're glad our clarifications were helpful and appreciate you raising your score, having a more positive outlook on the paper.

Program Chairsdecision2024-09-25

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC