Non-Exchangeable Conformal Risk Control

(1) Novelty beyond Barber et al. and Angelopoulos et. al.

Maybe this has to do with me not having read Barber et al. and Angelopoulos et al. very closely, and I’m missing some nuances in technical details. I understand the proof that is described in the response is not in Barber et al. and additional arguments will be needed to handle conformal risk control aspect of the paper. However, my understanding was that what is in the described proof sketch in the response is essentially the main insights in Angelopoulos et al.

Let me try to clarify with more specific details, and please correct me if I’m wrong.

As said in the response, talking about non-coverage of a test point doesn’t make sense the conformal risk control, and the set of “strange points” has to be thought through more carefully. And the original conformal risk control paper shows how one can define a set of strange points not just via non-coverage but via thresholding a monotonic loss, thereby going from vanilla conformal prediction to conformal risk control. The insight here I guess is realizing that given a monotonic non-conformal score, the prediction set is monotonic in the threshold.

Therefore, one can just go to the proof that’s outlined on page 32 of Barber et al. (right before section 7) and instead of miscoverage (a point in the prediction set or not), one can write down the monotonic loss and the rest of the proof follows; my impression is that this swapping of miscoverage with a monotonic loss has been already done in Angelopoulos et al.

In fact, the proof of Theorem 1 of this paper looks like the proof of Theorem 2 in Barber et al. (specifically the proof on page 32 right before section 7) except for the swapping of the miscoverage with the monotonic loss. And one can see this connection of miscoverage and monotonic loss in Section 2 of Angelopoulos et al.

Let me know if I'm missing more subtle nuances.

(2) Choice of Weights

Thank you for adding more discussion on this topic of how to go about choosing these weights.

Thank you for your review. We address below your concerns about our paper.

The main contribution of the paper seems to be just a combination of two techniques, conformal prediction beyond exchangeability and conformal risk control (...) techniques known for conformal prediction can be easily translated to conformal risk control — i.e. handling distribution shift. (...) there isn’t inherent difficulty in applying the beyond the exchangeability idea to this conformal risk control setting to my knowledge. If there is additional difficulty (...) it would be great if the authors can emphasize that and how this difficulty was overcome.

We respectfully disagree with the claim that our paper is “just” a combination of two techniques and that “there isn’t inherent difficulty in applying the beyond the exchangeability idea to this conformal risk control setting”. For example, one nontrivial aspect in our proof was to generalize / replace the step in Barber et al.'s proof (their Eqs. 24-26) which involves defining the set of “strange” points and showing that noncoverage implies strangeness of point K. In conformal risk control, “noncoverage of a test point” does not make sense, since we are upper bounding the risk and not modeling coverage. To overcome this difficulty and prove our theorem in the context of risk control, we handled this by (1) defining random variables $F(Z)$ which contain the losses as a function of $\lambda^*(Z)$, and (2) deriving a bound that includes a TV distance using $F(Z)$, and (3) invoking the non-monotonicity of the loss to obtain the final result. These elements are specific to our paper and absent in Barber et al. (2023) and Angelopoulos et al. (2023)’s proofs. In short, the proof style is similar but some of the key steps are substantially different and nontrivial. We invite the reviewer to compare the proofs and check the differences in case any doubt remains.

As pointed out by Reviewer wGbj, non-exchangeability happens frequently in practice, and thus it is important to explore robust weighting schemes and their implications. As explained, our method and proofs use techniques from Barber et al. (2023) and Angelopoulos et al. (2023), but their combination is not straightforward and has not been done before. We address the problem of risk control under non-exchangeable settings, which is highly relevant, yet the existing literature doesn't offer comprehensive solutions (please see Reviewer 2JpW’s comment on this topic). In addition to the theoretical results, our experiments show that the proposed method is useful in practice in both synthetic and real-world settings.

We hope this clarifies our goals and the significance of our contributions and alleviates your concerns.

There’s no clear guideline as to how to go about setting these weights and one has to resort to heuristics. But I think this point is not necessarily specific to the approach in this paper but with the original conformal prediction beyond exchangeability of Barber et al.

As pointed out in the answer to Reviewer wGbj, although our theoretical bound on $\mathbb{E}[L(\hat{\lambda}; (X_{n+1}, Y_{n+1}))]$ holds for any choice of weights, its usefulness relies on the coverage gap in Eq. 7 being small, i.e., on our ability to choose small weights $w_i$ for data points $Z^i$ with large total variation distance $d_{\mathrm{TV}}(Z, Z^i)$. In Barber et al. 2023 (Lemma 1) it is shown that $d_\mathrm{TV}(Z, Z^i) \le 2d_\mathrm{TV}(Z_i, Z_{n+1})$, and while the true value of this term is unknown, in some cases it can be properly modeled or approximated. For instance, in the presence of distribution drift in time series, we expect $d_{\mathrm{TV}}(Z_i, Z_{n+1})$ to decrease with $i$, therefore we should choose weights that increase with $i$. Our experiments (e.g., $\S4.1$, Setting 3) empirically validate this assumption for the case of distribution drift. The same principle can be applied in other domains (e.g., for spatial data, one may place higher weights to points close in space to the test point).

We agree that the paper benefits from more discussion on this topic, and for that reason we updated it accordingly (please see $\S3$ after Eq. 8). In particular, we included a new subsection ($\S3.2$) that suggests a practical strategy for choosing the weights based on knowledge or assumptions about how the TV distance $d_{\mathrm{TV}}(Z, Z^i)$ varies over time, via a regularized minimization of the coverage gap using the maximum entropy principle. We also show in this subsection that this principle provides further justification for the use of weights with an exponential decay in time series under a distribution shift, which we use in our experiments of $\S4.1$ and $\S4.2$. We hope this addresses your main concerns.

(continues in a follow-up comment)

Thank you for your thoughtful review and suggestions. We address the main points below.

Under the non-exchangeable setup, the CRC should be broken (...); (...) in Setting 3 in Figure 1, I cannot see why the proposed approach is good.; Can you summarize / provide scalar statistics on the controlled loss such that we can see whether the proposed approach controls the risk but the baseline fails to control it?

Please note that Figure 1 shows that the CRC baseline fails at providing the desired risk level in the presence of distribution drift (setting 3), whereas the proposed approach does not: the orange curve (CRC) is mostly above the black dotted line, while the green one (our method) tends to be below. We rescaled the axes in this figure for clarity. We also followed your suggestion and added scalar statistics (mean/median) to the paper, which further strengthen this point (see Table 2, reproduced below). We also included some of these values in the main text (last paragraph of $\S4.1$) for further clarity. We hope to have clarified your concern.

In particular, I’m not convinced why open-domain QA experiments (related to Figure 3) fit the non-exchangeable setup (...) the way to generate w_i is not correct – by Barber et al. (2023), w_is prespecified but not data-dependent (...); Can you justify why weights are generated in a data-dependent way in open-domain QA experiments?

For an intuitive scenario where non-exchangeability provides a good framework for the QA experiment, imagine a situation where the questions are posed by multiple users, with the same user having a tendency to ask semantically similar questions. Our results in this experiment suggest that choosing weights based on question similarity leads to smaller prediction sets while attaining the same risk level (see Figure 3 (left)). We believe this is an interesting result potentially useful in future research.

You are right that Theorem 1 requires the independence $K \perp Z$ as in Barber et al. (2023). For the other experiments ($\S4.1$ and $\S4.2$), we always assume data-independent weights. Our goal with the QA experiment is to assess whether the framework still works in practice when this assumption is relaxed (in cases where prior information about the domain of the questions or the user who asked them is available, one could choose a priori higher weights for closer domains/users without violating this assumption). Furthermore, note that it is possible to generalize our bound to allow data-dependent weights by conditioning the TV distance on the weights as described by Barber et al. (2023), $\S4.5$ (paragraph “Fixed versus data-dependent weights'').

To sum up, we believe that the results of $\S4.3$ are still interesting and useful. We agree, however, that the paper would benefit from a clearer discussion about this point along with a justification for that experiment. Therefore, we added this information in $\S3$ (last paragraph before $\S3.1$) and $\S4.3$ and updated the abstract/introduction accordingly. We hope this alleviates your concern.

Thank you for your review and suggestions. We are glad that you found the paper nicely written. We address the main points below.

It's also a bit of an over-claim to say that risk is controlled in a non-exchangeable setting, rather what the paper does is develop a conservative upper bound for the risk under non-exchangeability that depends on quantiles that we cannot realistically know, i.e., TV(Z_i, Z_{n+1}).”

You are right that our upper bound contains a coverage gap that is not easy to control, and we updated the manuscrit to make this more clear (see $\S3$). Nevertheless, we believe the upper bound derived in our paper can still be practically useful and it can motivate heuristics for reducing this coverage gap via a suitable choice of the weights. We added a discussion in a new subsection ($\S3.2$), where we also provide a maxent heuristic that, among other things, justifies exponentially decaying weights in distribution shift scenarios. We hope this clarifies your concerns.

“I'm unclear if Theorem 1 holds for data-dependent weights? A similar requirement of independence is in Barber's results, and it would seem that it should be required here too. Particularly in the iterated expectation step here, I think this assumes K \perp Z. This is a major claim in the paper (e.g., "[...] allows weighting the data based on its statistical similarity with the test examples" in the abstract), and in the QA experiment, the weights are a function of the data points, w_i=sim(X_i, X_{n+1}).”

Indeed, our Theorem 1 requires the independence $K \perp Z$ as in Barber et al. (2023). Our goal with the QA experiment is to assess whether the framework still works in practice when we relax this assumption (we set higher weights for questions in a “neighborhood” of $X_{n+1}$). For the other experiments ($\S4.1$ and $4.2$), we always assume data-independent weights. Note that it is possible to generalize our bound to allow data-dependent weights by conditioning the TV distance on the weights as done by Barber et al. (2023), $\S4.5$ (paragraph “Fixed versus data-dependent weights''). While we believe that the results of $\S4.3$ are still interesting and useful in practice, we agree that the paper would benefit from more discussion about this point. We added a note in $\S3$ (last paragraph before $\S3.1$) and in $\S4.3$ to clarify this and we also updated the abstract/introduction accordingly.

“Otherwise, it's also unclear what the best strategy should be for selecting weighting functions (this seems rather adhoc in the experiments).”

Although our theoretical bound on $\mathbb{E}[L(\hat{\lambda}; (X_{n+1}, Y_{n+1}))]$ holds for any choice of weights, its usefulness relies on the coverage gap in Eq. 7 being small, i.e., on our ability to choose small weights $w_i$ for data points $Z^i$ with large total variation distance $d_{\mathrm{TV}}(Z, Z^i)$. In Barber et al. (2023), Lemma 1, it is shown that $d_\mathrm{TV}(Z, Z^i) \le 2d_\mathrm{TV}(Z_i, Z_{n+1})$, and while the true value of this term is unknown, in some cases it can be properly modeled or approximated. For instance, in the presence of distribution drift in time series, we expect $d_{\mathrm{TV}}(Z_i, Z_{n+1})$ to decrease with $i$, therefore we should choose weights that increase with $i$. Our experiments (e.g., $\S4.1$, Setting 3) empirically validate this assumption for the case of distribution drift. The same principle can be applied in other domains (e.g., for spatial data, one may place higher weights to points close in space to the test point).

We agree that the paper benefits from more discussion on this topic, and for that reason we updated it accordingly (please see $\S3$ after Eq. 8). In particular, we included a new subsection ($\S3.2$) that suggests a practical strategy for choosing the weights based on knowledge or assumptions about how the TV distance $d_{\mathrm{TV}}(Z, Z^i)$ varies over time, via a regularized minimization of the coverage gap using the maximum entropy principle. We also show in this subsection that this principle provides further justification for the use of weights with an exponential decay in time series under a distribution shift, which we use in our experiments of $\S4.1$ and $\S4.2$. We hope this addresses your main concerns.

Thank you for your time reviewing our paper. We hope you had the chance to look at our answers and updated version of the paper. Since the author response period is almost ending, we kindly request your feedback on wether we addressed your concerns. Please do let us know if further clarification is needed.

Thank you for your positive reviews! We already incorporated some of your suggestions in the updated manuscript. In particular, we added some discussion following our main result in $\S3$, after Eq. 8, giving some intuition on which circumstances our results are useful; we also included a new subsection ($\S3.2$) that suggests a strategy for regularized minimization of the coverage gap inspired by the maximum entropy principle, providing further justification for the use of weights with an exponential decay in time series under a distribution shift, which we use in the experiments of $\S4.1$ and $\S4.2$.

Just below eq. (5), C_\lambda' should be C_{\lambda'}

Thanks for pointing this out, we fixed the typo.

Sec 2.3: "loss is nonincreasing": nonincreasing in which parameter and in what sense?

The loss should be nonincreasing with respect to $\lambda$. In practice, if we construct predictions sets of the form $\mathcal{C}\_{\lambda}(\cdot)$, with larger $\lambda$ yielding larger prediction sets, then the loss function must shrink as $\mathcal{C}\_{\lambda}(\cdot)$ grows. We clarified this in the manuscript ($\S2.3$).