Conformal Risk Control

We thank the reviewer for their careful review and thoughtful comments. We provide answers to specific questions and remarks (quoted) below.

Some motivating examples of cases where such conformal risk control would be desirable over the traditional coverage guarantee. One can think of cases where F1-score is more appropriate to measure than coverage. It would be great to mention these examples in the introduction so that the reader understands more the motivation of this generalization.

Great idea; thanks for the suggestion! Another reviewer agreed here, and we have bolstered the motivating example to the introduction.

Why is a bounded loss function reasonable? What examples of loss functions violate this or satisfy this? Obviously, a coverage guarantee satisfies this, but what other metrics satisfy this?

In our Examples section, we give several instances of such loss functions, including the best-in-set F1 score (lower-bounded by 0, so that 1 - F1 is lower-bounded by 1), the false negative rate (upper bounded by 1), graph distance (upper bounded by the depth of the graph), as well as any other clipped loss, such as Tukey's biweight loss.

Furthermore, any unbounded loss can be transformed to a bounded loss. For example, any unbounded loss on the positive reals can be transformed by taking the inverse tangent. As long as the transformation is monotone, a loss of $\alpha$ on the original loss corresponds exactly to a loss of $\alpha’$ on the new loss; thus, controlling the transformed risk may be enough in practice.

We added text to the paper to make this clear; see page 2, footnote 1.

The operator is quite confusing.

We introduced $\Lambda$ in a confusing way. $\Lambda$ is just the space of all inputs (‘thresholds’) to the function $L(\lambda)$. It is usually a subset of the real line, but can also be a discretized grid (for example, np.linspace(0, 1, 100)). We have clarified this in the paper.

In the buildup of section 1.1, I find the intuitive explanation of the method and why it works lacking. I believe a strong reason of why conformal prediction is so popular is its intuitiveness. I find these definitions unintuitive and the provided explanation lacking. I would spend more time describing the intuition of the constants and claims defined. Provide more intuition on the proof as to the meaning of each step in section 2.1. I found it very difficult to parse.

Thanks for another good suggestion. We have added more intuition to the explanation of the method in Section 1.1, which hopefully will help with the proof intuition as well. We would appreciate any further guidance from the reviewer as to what was unintuitive. (It is hard to add much more content to the proof due to the page constraints.)

One of my main concerns is the computability of $\hat{\lambda}$.

It is computationally trivial to compute $\hat{\lambda}$ (in our new experiments, it takes a fraction of a second). Since the loss is monotonic, it is simple to find by binary search to arbitrary precision. Usually this requires fewer than ten evaluations of the empirical risk.

We added an explanation of this fact in text (see page 2).

In the related works section, I find the differences between existing and current work confusing. You mention the guarantee in this paper is in expectation. Why is this better than existing works? Do existing works do worst-case analysis or high probability analysis? The technical similarity between different methods is not a sufficient difference in my opinion. In the second paragraph, I miss what the existing conformal risk works do. Is it possible that existing conformal risk works do not directly generalize conformal predictions or are often less tight? I believe more details on the differences between existing conformal risk papers and this paper are needed.

Thank you for this important criticism, which we took very seriously. Please see the main response comment for a detailed discussion. See also the related work section and Appendix B of the updated paper.

The practical difference between our approach and the existing ones is massive --- it is substantially more effective, sample-efficient, simpler, and provides a direct theoretical contribution to conformal prediction as opposed to the existing risk-control algorithms. As the reviewer mentioned, the other approaches are high-probability bounds that do not generalize or build on the standard theory of conformal prediction.

We thank the reviewer for their careful review and thoughtful comments. We provide answers to specific questions and remarks (quoted) below.

...establish good empirical performance of conformal risk prediction relative to Learn-then-Test, which appears both very tractable just as the proposed framework here, but also handles arbitrary losses... it should be easy to make this comparison quite direct, from a practical standpoint.

Thank you for your suggestion; please cross-reference the main response comment. We took this comment quite seriously and added a new subsection to the paper on this comparison, as well as a new experiment showing substantial practical advantages to our approach; see Appendix B. The practical gains are massive compared to RCPS/LTT.

As a very minor point, the experiment on F1 score control in open-domain question answering, in contrast to other experiments in this paper, seems less useful and set up in a somewhat stylized way that doesn't seem to aim to capture any of the linguistic difficulties in tackling open domain question-answering --- which makes the plotted performance graph seem not very interesting...

We tend to agree that the F1 score that we compute for open-domain QA is simplistic, though it is a common metric in the QA literature (see, e.g., Table 3.7 in the GPT-3 paper, and the definition of F1 evaluation in the popular SQuAD dataset); which is the reason for why we use it. That said, we note that many other metrics relevant to natural language are possible to use instead of F1 similarly. These include things like BERTScore, or the output of a Bradley-Terry style reward model trained from human feedback, as is commonly used in RLHF. Unfortunately, translating from such real-valued scores to what constitutes a desirable target risk score is less intuitive than things like false negative rate, however, and typically requires domain expertise getting a feel for the perceived "quality". Alternatively, we can also directly use human ratings based on Likert scales, though these are more expensive to annotate on a calibration set.

We thank the reviewer for their careful review and thoughtful comments. We provide answers to specific questions and remarks (quoted) below.

...the paper is more a collection of lots of theoretical results (c.f. Section 4. "Extensions": distribution shift, quantile risk, adversarial risk..) than a real important contribution to a particular problem. This somewhat blurs the main contribution of the paper...

Theorems 1 and 2 are our main contributions, and we believe they are substantial contributions to the theory of conformal prediction. The main observation is that conformal-type proof strategies leveraging exchangeability can be extended to a broader mathematical setting; specifically, they can be used for any bounded, monotone loss function, not just coverage.

Section 4 is a bit more scattered, but shows the generality the approach by demonstrating its application to a few popular settings elsewhere in the conformal literature.

We don’t feel it is fair to say that our paper is not an important contribution to a particular problem. Theorems 1 and 2 are fundamental contributions; the rest are extensions. If the reviewer feels we have muddied our contribution by including Sec. 4, we are happy to discuss moving it to the appendix.

The experimental results are not analyzed at all. In addition, the extensions in section 4 have not been the subject of any experiments.

We have added analyses of our experimental results, and an example of covariate shift to Appendix D.

No limits are indicated in the conclusion. In my opinion, comments on the limitations of the proposed approach are lacking.

We have added a new limitations section, as mentioned in the main response comment. It is copied below for convenience.

Under the distribution shift setting, the weights need to be estimated. How can this be done?

We now include an experiment that estimates the covariate shift weights in Appendix D. It is done by training a binary probabilistic classifier to distinguish the training (Y=0) and test data points (Y=1). The LR estimate is taken to be $f(x)/1-f(x)$. This approach tends to work fairly well in practice (see our new experiment and those in [3]), but further theory on this topic would be very interesting.

[3] Tibshirani, R. J., Foygel Barber, R., Candes, E., & Ramdas, A. (2019). Conformal prediction under covariate shift. Advances in neural information processing systems, 32.

Is there a link between quantile risk control and training-conditional guarantee in standard conformal prediction?

There is no link between these topics. This is because expectations and quantiles are fundamentally different objects and cannot be related without distributional assumptions.

Training conditional guarantees, give bounds on the conditional distribution of $\mathbb{E}[L_{n+1}(\hat{\lambda}) \mid L_1, \ldots, L_n]$. Quantile risk control gives a guarantee of the form $\mathrm{Quantile}(L_{n+1}(\hat{\lambda})) \leq \alpha$. Relating these two guarantees is not generally possible.

Can you give a real situation where we want to control risks defined by adversarial perturbations?

An example could be when a machine learning system is serving exchangeable user queries, but, during deployment, adversaries may have injected bounded perturbations to the test queries. A real such situation might be an image recognition system guiding a car, with a threat of adversarially placed markings on road signs. The adversarially-robust version of conformal risk control maintains exchangeability of the worst case risk in this class of perturbations.

The assumption that P(J(Li, ) > 0) = 0 appears to be the CP equivalent of continuous score assumption. Is this true?

Yes, these assumptions are analogous. We previously noted this in Appendix A, and edited the main text to include this as well.

It is said in the paper that in "monotonizing" a loss will only be powerful if the loss is near-monotone. Although this seems intuitive, do you have any numerical evidence for this? (or/and a basic example).

We are happy to present a basic example. Consider the example loss function where $L(\lambda) = 0$ if $\lambda > 1 - \epsilon$, $L(\lambda) = B$ if $\lambda \in [a_i, 1 - \epsilon]$, and $L(\lambda) = 0$ if $\lambda < a_i$. Then we have that $\hat{\lambda} = 1 - \epsilon$, regardless of the distribution of $a_i$. The intuition here is that if there are big, non-monotone blips in the loss for certain $\lambda$, the $\sup_{\lambda' \geq \lambda} L(\lambda')$ version of the loss will be driven high early on, and can remain very conservative relative to the non-monotone $L(\lambda)$ at lower values of $\lambda$.

We thank the reviewer for their careful review and thoughtful comments. We provide answers to specific questions and remarks (quoted) below.

In all examples presented in section 3, the authors only show the satisfactory performance of the proposed method. No comparison against other baselines is provided. If this is due to a lack of existing methods for similar tasks, it would be helpful to highlight this, explain why this is the case, and include doing so as future directions.

Thank you for the good point; we have used this as an opportunity to implement a comparison to LTT/RCPS [1,2], which are high-probability versions of our technique. See the main response comment for details.

Initially, we had not included them because they will clearly be much more conservative than conformal risk control. However, we agree that it is good to understand the gains of our new procedure. We have made major efforts towards understanding this in the revision.

It is worth noting that no other existing methods provide guarantees of risk control in expectation. The main purpose of Section 3 is to demonstrate the flexibility and empirical effectiveness (i.e., validity and tightness) of the proposed algorithm as a tool for risk control, as there are no competing strategies. We have clarified this in the related work.

For tasks mentioned in the extensions, it would be helpful to also illustrate the effectiveness of the proposed method on a subset of them.

Agreed; to deal with the space constraints, we have added an experiment on covariate shift to Appendix D. It includes estimated covariate weights.

What are limitations and future directions? It would be helpful to discuss these in the conclusion as well.

We have added a section on the limitations of our work in the discussion; it is copied below for convenience.

This generalization of conformal prediction broadens its scope to new applications, as shown in Section 3. Still, two primary limitations of our technique remain: firstly, the requirement of a monotone loss is difficult to lift. Secondly, extensions to non-exchangeable data require knowledge about the form of the shift. This issue affects most statistical methods, including standard conformal prediction, and ours is no different in this regard. Finally, the mathematical tools developed in Sections 2 and 3 may be of independent technical interest, as they provide a new, and more general, language for studying conformal prediction, along with new results about its validity.

[1] Angelopoulos, A. N., Bates, S., Candès, E. J., Jordan, M. I., & Lei, L. (2021). Learn then test: Calibrating predictive algorithms to achieve risk control. arXiv preprint arXiv:2110.01052.

[2] Bates, S., Angelopoulos, A., Lei, L., Malik, J., & Jordan, M. (2021). Distribution-free, risk-controlling prediction sets. Journal of the ACM (JACM), 68(6), 1-34.

[3] Tibshirani, R. J., Foygel Barber, R., Candes, E., & Ramdas, A. (2019). Conformal prediction under covariate shift. Advances in neural information processing systems, 32.

We thank the reviewer for their careful review and thoughtful comments. We provide answers to specific questions and remarks (quoted) below.

clarify why obtaining expectation-based bounds is more challenging than applying risk-control algorithms, e.g. [1].

Please cross-reference the main response comment for a detailed comparison of our approach against [1,2].

The expectation bounds in this paper are a novel and direct contribution to the theory of conformal prediction. From that perspective, we believe they are valuable. The high-probability bounds of [1] rely on extensive existing theory for deriving concentration bounds (e.g. the Hoeffding bound). Our manuscript contributes more directly to the theoretical foundations of conformal prediction than [1,2], which are applications of empirical process theory/multiple testing and not standard conformal prediction.

Compare to other works; clarify similarity of setup to [1]

See the main response comment and edits to related work Basically, the setups are almost the same, but the algorithms and theory are entirely different and the proofs are mathematically unrelated.

Theorem 1 seems to be a straightforward reformulation of the standard validity proof for CP prediction intervals.

Theorem 1 is not a reformulation of the validity theorem of conformal prediction, and the extension of conformal prediction to this setting is mathematically nontrivial. Our algorithm handles a strictly larger class of problems. When the loss function is binary, it reduces exactly to conformal prediction; see Appendix A for a detailed explanation.

In the writing of the proof of Theorem 1, highlighted the similarities to the original conformal validity proof for pedagogical reasons; however, this proof is not the same as the standard proof of conformal prediction’s validity involving score functions. For non-binary loss functions, no score function exists; hence the standard proof is inapplicable.

“Impossible to recast risk control as coverage control.” The statement is not proven or supported by examples.

Thank you for raising the point. All examples in Sec. 3 are impossible to equivalently cast in terms of coverage control.

It is not hard to see that risk control is not the same as coverage control. Comparing the form of equations (2) and (1), if you take $\ell$ to be any non-indicator function, (2) cannot be rewritten in the same form as (1). This is because (1) measures the probability of a miscoverage event, and when $\ell$ is not an indicator, there is no such event to measure.

However, (2) recovers (1) in the case of a binary loss (see intro+Appendix A).

Why does $\hat{R}_n$ carry an index?

$\hat{R}_n = \frac{1}{n}(L_1 + \ldots + L_n)$ is a standard notation from empirical process theory for an empirical risk on $n$ points ($L_1, \ldots, L_n$).

Can $R(\lambda)$ be interpreted as a parameterized conformity score and $\hat{\lambda}$ as the quantile of the corresponding distribution?

Good question; no, it cannot. The conformal score only exists for binary losses.

If $L_i$ is binary, the conformity score can be equivalently expressed as a discontinuity in the indicator function, $s_i = \inf \{ \lambda : L_i(\lambda) = 0 \}$. In that case, $\hat{\lambda}$ is the standard conformal quantile, as in Appendix A. In this setup, $R(\lambda)$ can be interpreted as the empirical miscoverage when sets are constructed using parameter $\lambda$.

However, when $\ell$ is not an indicator function, the conformity score can no longer be defined at all, and this correspondence ceases to exist. To see this, suppose there is a conformity score; then the corresponding loss function has at most one turning point at the threshold of the conformity score. Clearly, this does not hold for general monotone loss functions.

[1] addresses the case of non-monotonic risks. How is this compatible with Proposition 2?

Proposition 2 does not apply to the algorithm in [1], which is different (much more conservative and complicated) and applies to non-monotonic risks. See the main response comment for a full comparison of these algorithms.

Does the method apply to the outputs of a regression model?

Certainly! See Appendix D.

Are the extensions of Section 4 straightforward consequences of Theorem 1 and existing CP theory?

None of the extensions in Section 4 are literally corollaries of existing results + Theorem 1. Some are straightforward to an expert, and some are not.

Most of the results in Section 4 follow by arguing that some modified loss function satisfies the conditions required for Theorem 1 to hold. Propositions 4 and 8, however, use different proof techniques. Of all the propositions, we believe that 4 and 8 are the least straightforward.

We are hoping to have a discussion today before the deadline passes. Have we addressed your comments?

Thank you again for the review.

We thank the reviewer for their careful review and thoughtful comments. We provide answers to specific questions and remarks (quoted) below.

I suggest adding detailed discussions of differences to related work [1,2].

Thank you for your suggestion; please cross-reference the main response comment. We took this comment quite seriously and added a new subsection to the paper on this comparison, as well as a new experiment showing the advantages of our approach. The edits are extensive and we hope they satisfy your concern.

Theorem 1 is not well presented.

We appreciate the comment. We have defined $\lambda_{\mathrm{max}}$ and $L_i$ in the theorem for the purpose of clarity and rigor, so a reader can understand the result without having to comb through surrounding text. Hopefully this addresses your concern.

It is interesting to discuss whether we can have inverse relations of Theorem 1?

While we cannot bound $\mathbb{E}[L_{n+1}(\lambda)]$ directly, we can give a probabilistic bound. For example, given a fixed $\lambda$, we can show that $\mathbb{P}(L_{n+1}(\lambda) \leq \mathrm{Quantile}(1 - \delta, \{L_1(\lambda), \ldots, L_{n}(\lambda), B\}) \geq 1 - \delta$. The proof is analogous to that of standard conformal prediction.

Estimating risk functions like $E[L_{n+1}(\lambda)]$ is a well-studied problem in the area of empirical process theory. It is well-known to be an intrinsically $1/\sqrt{n}$ problem (by the Central Limit Theorem, for example), and can be addressed by various concentration inequalities, but not by any conformal method, because they do not estimate population parameters of the data distribution.

Thank you for the clarifications. My concerns are addressed. I raised my score to 6.

We are hoping to have a discussion today before the deadline passes. Have we addressed your comments?

Thank you again for the review.