Non-Exchangeable Conformal Risk Control
Authors: António Farinhas
Chrysoula Zerva
Dennis Thomas Ulmer
Andre Martins
Venue: ICLR 2024 poster (2024)
Keywords: conformal prediction
conformal risk control
non-exchangeable data
uncertainty
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)

Abstract: Split conformal prediction has recently sparked great interest due to its ability to provide formally guaranteed uncertainty sets or intervals for predictions made by black-box neural models, ensuring a predefined probability of containing the actual ground truth. While the original formulation assumes data exchangeability, some extensions handle non-exchangeable data, which is often the case in many real-world scenarios. In parallel, some progress has been made in conformal methods that provide statistical guarantees for a broader range of objectives, such as bounding the best $F_1$-score or minimizing the false negative rate in expectation. In this paper, we leverage and extend these two lines of work by proposing non-exchangeable conformal risk control, which allows controlling the expected value of any monotone loss function when the data is not exchangeable. Our framework is flexible, makes very few assumptions, and allows weighting the data based on its relevance for a given test example; a careful choice of weights may result in tighter bounds, making our framework useful in the presence of change points, time series, or other forms of distribution drift. Experiments with both synthetic and real world data show the usefulness of our method.

Published as a conference paper at ICLR 2024
NON-EXCHANGEABLE CONFORMAL RISK CONTROL
António Farinhas 12, Chrysoula Zerva 1:2, Dennis Ulmer 34, André F. T. Martins 1,2,5 Instituto de Telecomunicações,
Pnnttituto Superior Técnico, Universidade de Lisboa (Lisbon ELLIS Unit), 'TT University of Copenhagen, *Pioneer Centre for Artificial Intelligence. Unbabel {antonio. fari nhas, chrysoula, zarva, andre.t m...mmiammtteeea co. ul sboa.pt, dennis. ulmer @mai fmailbox.ozz
ABSTRACT
Split conformal prediction has recently sparked great interest due to its ability provide formally guaranteed uncertainty sets or intervals for predictions made by black-box neural models, ensuring predefined probability of containing the ac- tual ground truth. While the original formulation assumes data exchangeability. some extensions handle exchannhaeee data, which is often the case many real-world scenarios. In parallel, some progress has been made in conformal meth- ods that provide statistical guarantees for a broader range of objectives, such as bounding the best F1 Fi-score or minimizing the false negative rate in expectation. In this paper, we leverage and extend these two lines of work by proposing non- exchangeable conformal risk control, which allows controlling the expected value of any monotone loss function when the data is not exchangeable. Our framework is flexible, makes very few assumptions, and allows weighting the data based its relevance for a given test example; a careful choice of weights may result in tighter bounds, making our framework useful in the presence of change points, time series, or other forms of distribution drift. Experiments with both synthetic and real world data show the usefulness our method.
INTRODUCTION
As the use of machine learning systems for automated decision makinn becomes more widespread, the demand for these systems to produce reliable and trustworthy predictions has grown significantly. In this context, conformal prediction (Papadopoulos resurfaced as attractive framework. Instead of providing a single output, this framework creates prediction sets or intervals that inherently account for uncertainty. These sets come with a statistical guarantee known coverage, which ensures that they contain the ground truth in expectation, thereby providing a formal promise of reliability.
al., [002] Vovk al.] 2005) has recently
The standard formulation of conformal prediction has, however, important limitations. First, it as- sumes that all data is exchangeable, a condition which often violated in practice (e.g., when there is correlation over time or space). Second, while the predicted sets/intervals provide guarantees on coverage, they do not bound arbitrary losses, some of which may be more relevant for the sit- uation hand (e.g., the Fi-score the false negative rate in multilabel classification problems). Several works have been proposed to improve over these two shortcomings, namely through non- exchangeable conformal prediction (Tibshirani et al. 2019: Gibbs & Candes] 2021 Barber et al., 2023) and conformal risk control (Bates et al.) [201]] Angelopoulos et al. [202aa CRC). In this paper, we extend these lines of research and propose non-exchangeable conformal risk control (non-X CRC). Our main contributions are:
We propose a new method for conformal risk control that provides formal guarantees when the data is not exchangeable, while also achieving the same guarantees as existing methods if the data is in fact exchangeable (see Table where we position our work in the literature);
Theorem I establishes new bound on the expected loss (assumed to be monotonic and bounded), allowing weighting the calibration data based on its relevance for given test example;

---

Published as a conference paper at ICLR 2024
Table 1: Our framework combines two approaches, non-exchangeable conformal prediction and conformal risk control. Through this combination we are able to control the expected value of arbitrary monotonic loss functions when the data is not exchangeable, extending both frameworks.
Method
Data assumptions
Loss
Papadopoulos et al.
2002
exchangeable
miscoverage
Barber et al. (2023
X
miscoverage
Angelopoulos
2023a
exchangeable
nonincreasing. arbitrary
Angelopoulos al.
2023a
Prop.
covariate shift, known likelihood ratio
nonincreasing, arbitrary nonincreasing. arbitrary
This paper
X
We demonstrate the usefulness of framework three tasks: multilabel classification synthetic data by minimizing the false negative rate; monitoring electricity usage by minimizing the X-insensitive absolute loss; and open-domain question answering by bounding the best Fi-score
Throughout the paper, we use the following definition of exchangeable data distribution, which is weaker assumption than independent and identically distributed (i.i.d)) data.
Definition 1 (Exchangeable data distribution). Let X and y designate input and out- put spaces. A data distribution in X x y is said to be exchangeable if and only if we have (()); Yx(1))....s (Xm(n): Y=(n))
P((X1, Mi),,,),...... (Xas Yn)) for any finite sam- ple {(x,, Y)) S y and any permutation function Note that if the data distribution is i..dd, then it is also exchangeable, since P(((1, Yi),..., (Xn, Yn)) = II==1 P((X;, Y.)).
BACKGROUND
We start by providing background on conformal prediction (Papadopoulos et al. 2002 Vovk al. 2005) in 1 We then discuss recent extensions of the framework- [ discusses the case where the data is non-exchangeable (Barber et al. 2023), which is often the case when models are de- ployed in practice. Another extension pivots from guaranteeing coverage to instead constraining the expected value any monotone loss function (Angelopoulos al. (023a). useful for tasks which the natural notion of eиror is not miscoverage $2.3)
2.1 CONFORMAL PREDICTION
Although other methods exist, this paper focuses on split conformal prediction (Papadopoulos al., 2002 hereinafter referred to simply conformal prediction). We start with pretrained model and measure its performance on calibration set ((X,, Y,) of paired examples. Under the assumption of exchangeable data {(X,, Y.) conformal prediction constructs prediction sets with the following coverage guarantee:
P(Y.+1 E C(X.+1)) 2-aa
(1)
where (Xa+1, Y a new data point and a predefined confidence level. This is accomplished
through the following steps: Let s(x, y) E be a non-conformitt score function, where larger scores indicate worse agreement between and We compute the value as the 1/x[(n + 1)(1 a)] quantile of the calibration scores and construct a prediction set as follows:
C(X.t1) {y: s(Xn+1,3) 4).
(2)
This prediction set satisfies the coverage guarantee in Eq. (I) see e.g., e.g., Angelopoulos & Bates 202 App. D for a proof. While this guarantee helps to ensure a certain reliability of the calibrated model, the assumption of exchangeable data is often not true when models are deployed in practice, e.g., due to distribution drift time series or correlations between different data points.
Our code is available at wtt.aihhh...peeeaatttoooooooeeep
2

---

Published as a conference paper at ICLR 2024
2.2 NON-EXCHANGEABLE CONFORMAL PREDICTION
Let us now consider prespecified weights {w, } E [0, 1]" and define W;; := We take a look generalization of conformal prediction put together by Barber et (2023)
/ Σ
which provides the following coverage guarantee, also valid when exchangeability is violated:
P(Yn+1 E C(Xa+1)) 2 1 1 Σ (d,TvvZ,22)
(3)
where Z (X1, (X (X, Y is sequence of calibration examples fol- lowed by test example, Z' denotes after swapping (X;, Y:) with (X,+1, Yn+1), and drv 2*) the total variation (TV) distance between Z and Z². This accomplished by using
N
i = inf { Σ
(
8 S 2 2 11
(4)
to construct prediction sets the same way in Eq. (2) See Barber et al. 2023 $4) for proof. It is
Besides, if the data is exchangeable, then the distribution of Z is equal to the distribution of Z and thus using a weighted procedure does not hurt coverage according to Eq. (3) since drv Z²) 0 for all Intuitively, the "closer" to exchangeable the data is, the smaller the last term will be in Eq. (3) By choosing wisely the weights w/ e.g., by setting large weights to calibration points (æ,, 3/) such that Z and Z' are similarly distributed and smaller weights otherwise- tighter bounds be obtained. For example, in time series data we may want to place larger weights on more recent observations.
worth noting that this method recovers standard conformal prediction when {w;} |
2.3 CONFORMAL RISK CONTROL
Let us now consider an additional parameter and construct prediction sets of the form Cx(-). where larger À yield larger prediction sets, i.e., < X' = Cx(.) S Cx-() (see Angelopoulos & Bates 2021 $4.3) for an example). Let e be an arbitrary (bounded) loss function that shrinks as C(X++1) grows (i.e., that is monotonically nonincreasing with respect to A). We switch from conformal methods that provide prediction sets that bound the miscoverage P((n++ C(X++1)) I to conformal risk control (Angelopoulos et al. 2023a). which provides guarantees of the form
IE ((C(X=+1),
S a.
(5)
La)1(()
This is accomplished as follows. Let (A) = (X,,, Y,), i= I,.. .......,. + 1, with Lg : A + (-oo, B] and Amux sup A, be an exchangeable collection of nonincreasing functions of X. Choos- ing an optimal X as
x= inf {x:
B n+1 sa),
R,,() 1 n
n (n)
T,(A),
yields the guarantee in Eq. (5) see Angelopoulos et al. 2023a $2) for proof. When ((C(Xn+1), ((-X))),,Y,-)))
n+1 & C(X++1)) is the miscoverage loss, we recover standard con- formal prediction 2.2. Note that, as required, this loss is nonincreasing. Other nonincreasing losses include the false negative rate, X-insensitive absolute error, and the best token-level llss,, all of which used in our experiments in $ A limitation of the construction presented in this sec- tion is that it relies on the assumption of data exchangeability, which might be violated in practical settings. Our work circumvents this requirement, as we show next.
3 NON-EXCHANGEABLE CONFORMAL RISK CONTROL
Up to this point, we have described how to construct prediction sets/intervals with coverage guaran- tees for exchanccaeee data, in $2.2, and how to control the expected value of arbitrary monotone loss functions, when the data is exchangeable, in 22.3 Using the same notation as before, now

---

Published as a conference paper at ICLR 2024
present our method, non-exchangeable conformal risk control, which puts together these parallel lines of research, providing guarantees of the form:
n (X (X + a (B A)
E ú 2*),
where we additionally assume < < oo to be a lower bound on L3 : - [A, BJ. Let us define Nw == =E=
=== Wg. Eq. (7) is obtained by choosing an optimal as
= inf { A {^:
Nw
Nw +1 +a-saa. Ra(A) 1
B
sa.
Nu +1 (A)
Σ Nw 1m1
w. (2..
(8)
We can see how Eq. (7) simultaneously mirrors both Eq. (3) and Eq. (5) for an optimal choice of A, the expected risk for a new test point is bounded by a plus an extra loosening term that depends on the normalized weights (w:))_ and on the total variation distance between Z and Z When the data is in fact exchangeable, we have again drv Z, Z*)
for all i, and we recover Eq. (5) i.e. our method achieves the same coverage guarantees as standard conformal risk control. Although our thcoretical bound in Eq. (7) holds for any choice of weights, this result is only useful when the loosening term is small, i.c., if we choose small weights w, for data points Z' with large total variation distance drv(2, )² While the true value of this term is typically unknown, in some situations, such as distribution drift in time series, we expect it decrease with motivating the choice of weights that increase with i. The same principle can be applied in other domains (e.g.. for spatial data, one may place higher weights points close in space to the test point). We come back to this point in $3.2
The result in Eq. (7) valid when the weights are fixed, i.e., data-independent. However, our result still applies in the case of data-dependent weights w; = w(X, Xn+1) if we replace E. w;dry (Z, Z') by E [Σi=1 ü;dry(22 (Z, Z (wi.... w,)] (see Barber et al. 2003 $4.5) for more information). We experiment with this approach in $4.3 where wy is function of the embed- ding similarity between X; and Xx+1, showing that the new bound is still useful in practice.
3.1 FORMAL GUARANTEES
Now that we have presented an overview of our method, we proceed to providing a formal proof for the guarantee in Eq. (7) We begin with lemma, proved in App. A that establishes TV bound that extends the one introduced by Barber et al. (2023):
Lemma 1. Let f (where A C 2 is a o-algebba) and let P and Q be two probability measures on (S. Then
[A, C be a bounded function on measurable space (S, A)
[r[s] - EolsI| < (B A)drv(P, Q)-
(9)
Note that when f(1) 1f1 E V} for some event V E A, the left-hand side becomes (P(V)-Q(V) and we recover the bound used in the proof of Barber et al. (2023 $6.2).
We now state the main result. The proof technique is similar to that of Barber et al. (2023), but instead of modeling the event of a variable belonging to a "strange set", we model expectations of loss functions that depend on calibration variable. See App. for the full proof.
Theorem 1 (Non-exchangeable conformal risk control). Assume that for all (z, y) E X
y the loss L(x; (x, v)) is nonincreasing in X and bounded as A S L(X: (z, v)) S B for any X. Let
Z : (),,Y)). (X,. (X
be a sequence of calibration examples followed by test example, and let wi...., Wn E [0, 11"d be data-independent weights. Define Nw =E wa w, ww/(NN + 1) for E [n] and wn+1 = 1/ + 1). Let a E [A, B) be the maximum tolerable risk, and define
x = inf { yr:
No
B
Rn()) + N +1
S saj.
(10)
No +
4

---

Published as a conference paper at ICLR 2024
where (A) is the weighted empirical risk in the calibration set:
Rnn()) = N Σ
1
wy W,L(Aa(Ti,,))
(11)
Then, we have
(X Yn+1))) S a (B A) Σ üsdry 2
(12)
where Zt is obtained from Z by swapping (X,, Yi) and (Xn+1, Yn+1).
The next section illustrates how we can make practical use of this result to minimize loss functions beyond the miscoverage loss the presence of non-exchangeable data distributions.
3.2 How TO CHOOSE WEIGHTS
To make practical use of Theorem 1 need procedure to choose the weights wy. We next suggest a strategy based on regularized minimization of the coverage gap g( 1001,,.. (.,) = (B A) w,drv Z²) via the maximum entropy principle (Jaynes 1957). Note first that simply minimizing this gap would lead to ún = for all E [n] and Wn+1 1, which ignores all the calibration data and leads to an infeasible in Eg. (6) In general, if all weights w/s are too small, this leads to very large Wh+1 and an unreasonably large X. On the other extreme, having all weights too large (e.g. Wi for i, which leads to ú;; = 1/(n + 1) for i in + 1) ignores the non-exchangeability of the data and may lead to large coverage gap. Therefore, it is necessary to find a good balance between ensuring small coverage gap but at the same time ensuring that the distribution w...... Wn+1 is not too peaked, i.e., that it has sufficiently high entropy. Since by definition, we must have un+1 2 w; for all E [n]. this can formalized as the following regularized minimization problem:
min yeur Wp-1
(B - A) ü,drv(Z, BH (HW, wn+1)
n+1
subject to
Wi 1 and S w S 1n+1 1 for all e [n].
(13)
where HWi,,... 1n+1) Σn
Wi log w; the entropy function and B > a temperature parameter. The solution of this problem W; x exp(- 3(B A)drv(Z, Zt) for E [n +++1
Although in general (2, ) is not known, it is possible in some scenarios to bound or to es- timate this quantity: for example, when variables are independent but not identically distributed, it can be shown that dTv(Z, Z²) 2dTv Zn+1) (Barber et al. 2023 Lemma 1); and it possible to upper bound the total variation distance as a function of the (more tractable and amenable to estimation) Kullback-Leenn Leibler divergence, e.g., via Pinsker's
Peetagnolle-Huber inequalities (Bretagnolle & Huber 1979; Csiszár & Körner (01T)) which may provide good heuris- tics. For example, in time series under a distribution shift scenario bounded with Lipschitz- type condition drv Zi, 7n+1) < <(n + i) for some e > O (see e.g. (Barber et al. 2023 $4.4)), could replace drv Z, 7 in Eq. (13) by this upper bound to obtain the maxent solution w; x exp(-Be(n + i)) p +11 where
exp(-3e) E (0,1). This exponential decay of the weights was suggested by (Barber et al. 2023);; our maximum entropy heuristic provides further justification for that choice. We use this strategy in some of our experiments in $4
4 EXPERIMENTS
In this section, we turn to demonstrating the validity of our theoretical results in three different tasks using different nonincreasing losses: multilabel classification problem using synthetic time series data, minimizing the false negative rate (64.T). a problem involving monitoring electricity usage, minimizing the X-insensitive absolute loss $4.2) and open-domain question answering (QA)
5

---

Published as a conference paper at ICLR 2024
task, where control the best token-level Fi-score (4.3)
Throughout, report method
alongside conformal risk control (CRC) baseline that predicts Ả following Eq. (6)
4.1 MULL CLASSIFICATION IN A TIME SERIES
We start by validating our approach synthetic data, before moving to real-world data in the following subsections. To this end, we modified the synthetic regression experiment of Barber et al.] [2023] $5.1) to turn it into multilabel classification problem with up M 10 different labels. We consider three different setups:
1. Exchangeable (i.id.) data: We sample = 2000 i..d. data points (X;, e
iid RM IRM, We sample X, from a Gaussian distribution, X; ~ NO IM), and we set Yi sign(W X; + b + .0, IM)). The coefficient matrix W is set to the identity matrix IM and the biases to = 0.5, to encourage sparse set of labels.
2. Changepoints: We follow setting (1) and sample N = 2000 i.i.d data points (X, Yt), setting X, ud (0, I and Y, sign( (Sign((())) (w) -o..b++.1( 10, IM)), again with
00.5.
We start with the same coefficients ( = Ias and for every changepoint k > 0 we rotate
the coefficients such that (( W (k-1) [-1 for > 1 and W W M.j (k-1) Following
Barber et al. (202)), we use two changepoints (k: = 2) at timesteps 500 and 1500.
3. Distribution drift: We follow setting (2) and sample N = 2000 i.i.d. data points (X;, Yi), with X; fid ~ (O IM) and Y; ~ sign(W (R) X, ++ .0, IM)). with as above. Again, we start with W = IM but now we set W to the last matrix setting (2). We then compute each intermediate (()) by linearly interpolating between (7()) and W(N)
After a warmup period of 200 time points, at each time step n 200, N 1 we assign odd indices to the training set, even indices to the calibration set, and we let x be the test point. We fit M independent logistic regression models the training data obtain predictors for each label; we let fm(()) denote the estimated probability of the m label according to the model. Based on
this predictor, we define prediction sets Cxx))) == {m E [M] fm (X,) 2 \}. We compare standard CRC with non-exchangeable (non-X) CRC, for which we use weights w; 0.99-+1-;
and predict À following Eq. (10) In both cases, minimize the false negative rate (FNR)
1 (X [Y]
(X,,
(14)
Note that this loss is nonincreasing in A, required. App. C contains additional experiments sidering À to be the number of active labels and using Cx = top->(((X))).
Fig. shows results averaged across 10 independent trials for a 0.2, summarized in Table We see that the performance of both methods is comparable when the data is i.i.d, with non-X CRC being slightly more conservative. However, when the data is not exchangeable due to the presence of changepoints or distribution drift, our proposed method is considerably better. In particular, after the changepoints in setting (2), non-X CRC is able achieve the desired risk level more rapidly; in setting (3), the performance of standard CRC gradually drops over time problem that can be mitigated by accounting for eonnexchangeability introduced by the distribution drift. Importantly, while the average risk is above the predefined threshold for standard CRC for settings (2) and (3) (0.246 and 0.225, respectively), our method achieves the desired risk level on average (0. 199 and 0.182, respectively).
4.2 MONITORING ELECTRICITY USAGE
We use the ELEC2 dataset (Harries 1999), which tracks electricity transfer between two states in Australia, considering the subset of the data used by Barber et al. (2023). which contains 3444 time points. The data points correspond to the 09:00am 12:00pm timeframe and we use the price (nswprice, ce, vicpri ic) and demand (nswdemand,, vi cdemand) variables as input features,
With some abuse of notation, we Y, C (1,..., : M}+ to denote the set of gold labels with value +1.

---

Published as a conference paper at ICLR 2024
Setting dl..d. data)
Setting 2 (changepoints)
Setting 3 (distribution drift)
0.3
0.1
0.3
0,1
750
1020
1930
1790
910
1210
1950
1750
2000
900
1003
1250
1500
1750
2000
1.0
1.0
0.8
lambda
9.4
0.4
0.4
0.0
230
330
750
1000 1250
1500
1750
2000
230
500
750
3200
1250
1960
1750
2000
250
300
750
1000
1250
1200
1750
2002
time
time
time
CRC
Non-X CRC
Figure 1: Average loss (top) and Å (bottom) over 10 independent trials for settings (1), (2), and (3).
We smooth all the curves by taking a rolling average with a window of 30 time points.
Scalar statistics (mean/median) for settings (1), (2), and (3) for the multilabel classification problem using synthetic time series data reported $4.1
Table 2:
Method
Setting I (i.i.d. data)
Setting 2 (changepoints)
Setting 3 (distribution drift)
CRC
0.191 081
0.246 0.228
0.225 0.218
non-X X CRC
0.181/ / 0.175
0.196 / 0.183
0.182 / 0.175
Ia to predict the target transfer values y:- We also consider a randomly permuted version of the dataset such that the exchangeability assumption is satisfied. We use the same definitions and settings of [4.1 but this time we fit least squares regression model to predict the transfer values, D2 = f f(z)). at each time step. For non-X CRC, we use weights w; 0.99*+1-s and we also experiment with weighted least- squst-s regression, placing weights t, wz each data point (non-X CRC + WLS). For both standard and non-X CRC we control the residual (distance) with respect the confidence interval Cx(x)) [f(x;; X, f(x, AJ, where f(x;) corresponds the predicted values for t. transfer We use the X-insensitive absolute loss, a loss function commonly used in support vector regression (Schölkopf et al. 1998 Vapnik 1999):
[0. (11, = (1f(xs) Vi X,
ff(x)) vil - X, otherwise.
(15)
We experiment using [0, with step of 0.01. Since we using the normalized ELEC2 dataset, transfer takes values in [0, 1], thus L(x; (f(x;) u)) is bounded by B = 1. By definition L(x; (f(z)) 9:)) is nonincreasing with respect X.
Fig. 2 shows results for the aforementioned setup. We can observe that in the original setting, both non exchangeable methods approximate well the desired loss threshold even during the timesteps at which the data suffers from distribution drift. Specifically, as observed by Barber et al. (2023). the electricity transfer values are more noisy during the middle of the time range and we can see that the standard CRC LS method underestimates the À for these data points resulting in increased loss, above the desired one. With respect to the CRC WLS setup, can that it manages to reach the desired loss with a smaller interval width on average, indicating that fitting the weighted least- squares model performs better when the data distribution changes, allowing for smaller À during calibration. For the permuted data that simulates the exchangeable data scenario, we can see that all methods perform similarly, reaching the desired loss, expected.

---

Published as a conference paper at ICLR 2024
Original ELEC2 data
Permuted ELEC2
0.20
0.20
108
0.00
0.00
pred. interval wieth
0.8
0.8
0.6
08
0.4
04
02
02
0.0
0.0
530
1000
1500
2000
2500
3000
3500
800
1000
1900
2000
2500
3000
3500
bme
CRC
Non-X CRC
Non-X CRC WLS
Figure 2: Results ELEC2 data for 0.05 and À defined by the prediction interval width. Presented curves are smoothed by taking a rolling average with a window of 300 data points per timestep.
150
count
100
20
22
24
26
28
30
0.26
0.28
0.32
0.34
size
risk
CRC
Non-X CRC
Figure 3: Fi-score control on the Natural Questions dataset. Average set size (left) and risk (right) over 1000 independent random data splits.
4.3 OPEN-DOMAIN QUESTION ANSWERING
now shift to open-domain QA, a task that consists in answering factoid questions using a large collection of documents. This is done in two stages, following Angelopoulos et al. (2023a): (i) retriever model (Karpukhin et al. 2020 DPR) selects passages from Wikipedia that might contain the answer the question, and (ii) reader model examines the retrieved contexts and extract text sub-spans that serve as candidate answers
Given vocabulary V. each X; 2 is question and Y; 2 of correct answers, where Z = ym (we assume that X; and Y; are sequences composed of up to m tokens). We calibrate the best token-based Fi-score of the prediction set taken over all pairs of predictions and answers,
(X, Y.))
max (F) (a.
C Y.).
C₁ {y: ((X.,)) A}, (16)
which is nonincreasing and upper-bounded by B = 1. We consider CRC baseline that predicts following Eq. (6) For non-X CRC, choose weights {wy) by computing the dot product be- tween the embedding representations of (X,)2_ and X obtained using sentence-transfone model (Reimers & Gurevych 2019) designed for semantic search and predict following Eq. (10)
While standard CRC is the same for each test example, this is not the case for non-X CRC.
Enumerattin all possihle answers is intractable, and thus we retrieve the top several hundred candidate answers, extracted from the top 100 passages (which is sufficient control all risks). used by Angelopoulos et al. (202aa).
*This the same We use the mu 1 qa base---b-e--ebb---tt-o----
model available
sentence- transtrrrasstee www.trrannnooeeeeeieeeeae
mapae--p-------e - base-aaeeeeeeee dot-vl
8

---

Published as a conference paper at ICLR 2024
While Theorem requires the weights to be independent of the test example, relax this assump- tion by setting higher weights for questions in a "neighborhood" of Xn+1 (see (3). Intuitively, we could think of situation where the questions are posed by multiple users, each of which may have a tendency to ask semantically similar questions or from the same domain. In this case, we could choose a priori higher weights for closer domains/users without violating this assumption.
We use the Natural Questions dataset (Kwiatkowski et al. 2019 Karpukhin et al. (020), considering
n 2500 points for calibration and 1110 for evaluation. Following Angelopoulos al. (2023a), we use a = 0.3 and report results over 1000 trials in Fig. While the test risk is similar in both cases (0.30=0.0155, the prediction sets of our method are considerably smaller than those of standard CRC (23.0 = 1.47 vs. 24.6 1.83, respectively). By choosing appropriate weights we can better estimate the set size needed to obtain the desired risk level, while standard CRC tends to overestimate the set size to reach the same value. We thus obtain better estimates of confidence over the predictions.
RELATED WORK
Conformal prediction (Gammerman et al., 1998, Vovk et al. 1999 Saunders et al. 1999) has proven to be useful tool for obtaining uncertainty sets/intervals for the predictions of machine learning models, having found a variety of extensions and applications over the years. Among these are split conformal prediction (Papadopoulos et al., 2002). which does not require retraining the predictor and instead uses a held-out dataset and cross-conformal prediction (Vovk) 2015), which is hybrid between split conformal prediction and cross- valisaaali,iionn. Some of these methods have recently been applied in tasks such as language modeling (Schuster et al.) (022), molecular design (Fannjiang ct al. 2022). pose estimation (Yang & Pavone 2023), and image denoising (Teneggi et al. 2023).
In addition to the works discussed in 22] several extensions to non-exchangeable data have been pro- posed for time series (Chernozhukov et al. 2018 202Tb Xu & Xie| (02T, Stankeviciute et al., 202T
Lin et al. 2022 Zaffran et al.) 2022] Sun & Yu 2022 Schlembach et al. 2022 Angelopoulos al.
2023b), covariate shift (Tibshirani et al. 2019). label shift (Podkopaev & R (202]). and others
(Cauchois al.) 2020 Gibbs & Candes 2021 Chernozhukov et [021[]] & Candès 2022
Oliveira et al., 2022; Guan 2022). Moreover, there is recent work aiming at controlling arbitrary risks in online setting (Feldman al. 2022). The ideas, assumptions, or formal guarantees in these works are different to ours-we refer the reader to the specific papers for further information.
Angelopoulos al. (023a) touch the of conformal risk control under covariate shift (Propo- sition 3; without providing any empirical validation), explaining how to generalize the work of Tibshirani et al. (2019) to any monotone risk under the strong assumption that the distribution of Y|X is the same for both the training and test data and that the likelihood ratio between X and Xpain is known or can be accurately estimated using large set of test data. This result orthogonal to ours. Besides, they quantify how unweighted conformal risk control degrades when there is an arbitrary distribution shift. Our work is more general and differs
several significant ways: we allow for an arbitrary design of weights, the bounds can be tighter, and the losses are bounded in [A, B), not necessarily in [0, B]. Specifically, their Proposition 4 is a particular case of our main bascline in our experiments.
result (choosing A and unitary weights), which
6 CONCLUSIONS
We have proposed new method for conformal risk control, which is still valid when the data is not exchangeable (e.g., due an arbitrary distribution shift) and provides a tighter bound on the ex- pected loss than that of previous work. Our simulated experiments illustrate how non-exchangeable conformal risk control effectively provides prediction sets satisfying the risk requirement in the presence of non-exchangeable data (in particular, in the presence of change points and distribution drift), without sacrificing performance the data is in fact exchangeable. Additional experiments with real data validate the usefulness of our approach.
Our work opens up exciting possibilities for research on risk control in challenging settings. For instance, it is an attractive framework for providing guarantees the predictions of large language models, being of particular interest in tasks involving language generation, medical data (Jalali et al.) 2020), or reinforcement learning (Wang et al. 2023), where the i.i.d. assumption does not hold.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We would like to thank Mário Figueiredo, the SARDINE lab team, and the anonymous reviewers for helpful discussions. This work was built on open-source software; acknowledge Van Rossum & Drake 2009) : Oliphant (006); Virtanen et al. (200); Walt et al. (201 I); Pedregosa et (2.1 I). and
(200))
Paszke et al. 2019). This work was supported by EU's Horizon Europe Research and Innovation Ac- tions (UTTER, contract 101070631), 1). by the project DECOLLAGE (ERC- 2002-0022-ooo 101088763), by the Portuguese Recovery and Resilience Plan through project C645008882-000000 (Center for Responsible AI), and by Fundação para Ciência e Tecnologia through contract UIDB/50008/2020.
REFERENCES
Anastasios N Angelopoulos and Stephen Bates. A gentle introduction conformal prediction and distribution-firt uncertainty quantification. arXiv preprint arXiv:2107.0751, 2021.
Anastasios N. Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Conformal risk control, 2023a.
Anastasios N. Angelopoulos, Emmanuel J. Candes, and Ryan J. Tibshirani. Conformal pid control for time series prediction, 2023b.
Rina Foygel Barber, Emmanuel J. Candès, Aaditya Ramdas, and Ryan J. Tibshirani. Conformal prediction beyond exchangeability. The Annals of Statistics, 51 845, 2023. doi: 10. 1214/23-AO$2276 URL http:///oo...o////////
Stephen Bates, Anastasios Angelopoulos. Lihua Lei, Jitendra Malik, and Michael Jordan. Distribution-freee risk-controlling prediction sets. J. ACM, 68(6), sep 2021. ISSN 0004-5411.
doi: 10.1145/3478535, |RLpttps:: //doi.:://di..ooo org. 1115//111111444788818
Jean Bretagnolle and Catherine Huber. Estimation des densités: risque minimax. Zeitschrift für
Wahhsshhennicckeiisshheeri und verwandte Gebiete, 47:1 19-177, 1979.
Maxime Cauchois, Suyash Gupta, Alnur Ali, and John C Duchi. Robust validation: Confident predictions even when distributions shift. arXiv preprint arXiv:2008.04266, 2020.
Victor Chernozhukov, Kaspar Wüthrich, and Zhu Yinchu. Exact and robust conformal inference methods for predictive machine learning with dependent data. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 732-749. PMIR, 06-09 Jul 2018. URL htttps::/ppooeeeeeeeeeeee
mwr www.ppreessss... chw.rohukvv... wwt.vvllaaa............
Victor Chemozzuuovv Kaspar Wüthrich, and Yinchu Zhu. Distributional conformal predic- tion. Proceedings of the National Academy of Sciences, 118(48):2110779111, 2021a. doi:
2..1733/pas.21077949 URL Utt.httss::/ /ttpp:://wwwww. /wwp://wwppp..ppp....//.pp/aaa.t ppas www. http:ppps...g.popapaobb////o////
2107794118
Victor Chernozhukov, Kaspar Wüthrich, and Yinchu Zhu. An exact and robust conformal inference
method for counterfactual and synthetic controls. Journal of the American Statistical Association,
1166536): doi org http:///....o..oorr00000000/1112 202.4499.22222....
Jun 2021b. ISSN 1537-274X. doi: 10. (0.100000122145522222 1920997. URI.
Imre Csiszár and János Kömnrr. Information theory: coding theorems for discrete memoryless sys-
tems. Cambridge University Press, 2011.
Clara Fannjiang, Stephen Bates, Anastasios N. Angelopoulos, Jennifer Listgarten, and Michael Jordan. Conformal prediction under feedback covariate shift for biomolecular design. Pro- ceedings of the National Academy of Sciences, 1124441122004561199 2022. doi: 10. 0073/pnas.22045699 2204569119
URL. https: ttops://wwirr wwwp://wwww.t.. pnas org doi abs 1073 pnas.
Shai Feldman, Liran Ringel, Stephen Bates, and Yaniv Romano. Achieving risk control in online learning settings, 2022.
10

---

Published as a conference paper at ICLR 2024
Alexander Gammerman, Volodya Vovk, and Vladimir Vapnik. Learning by transduction. In Gre- gory F. Cooper and Serafin Moral (eds.), UAI '98: Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, University of Wisconsin Business School, Madison, Wiscon- Morgan Kaufmann, 1998.
sin, USA, July 24-26, 1998, pp. 148-155.
Isaac Gibbs and Emmanuel Candes. Adaptive conformal inference under distribution shift. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 1660-1672. Curran Associates, Inc., 2021. URL http:::/proceeddngg wtw.:ediiiinnnueeneeeeeu www.ies. ccppppp.rrrccppppprppppppp.pp files//
Isaac Gibbs and Emmanuel Candès. Conformal inference for online prediction with arbitrary distri- bution shifts, 2022.
Leying Guan. Localized conformal prediction: generalized inference framework for conformal prediction. Biometrika, 110(1):33 50, Jul 2022. ISSN 1464-3510. doi: 00.1093/biomeetassc0000... URL 1tt.///.pp///.........//////////
Michael Harries. Splice-2 comparative evaluation: Electricity pricing. In Technical report, Univer- sity of New South Wales, 1999.
Ali Jalali, Hannah Lonsdale, Nhue Do, Jacquelin Peck, Monesha Gupta, Shelby Kutty, Sharon R. Ghazarian, Jeffrey P. Jacobs, Mohamed Rehman, and Luis M. Ahumada. Deep learning for improved risk prediction in surgical outcomes. Scientific Reports, 10(1); 2020. doi: 1031038/ s41598-028 000-0200-622 020-62971-3. 1ttptt/p////all.oo/000000011///0
Edwin Jaynes. Information theory and statistical mechanics. Physical review, 106(4):620, 1957.
Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 6769-6781, Online, November 2020. Association for Computational Linguis- tics. doi: 10. /2655////222..emmmmmmaaaaa
http:sss/aaaaaattelllgoooeooe org/2020.
emm 1ec.1p-mmiin 550
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming-Wei Wei Chang, Andrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. Natural questions: A benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:452-466 2019. doi: 10.1162/tacl..0000 00276.. URL
Zhen Lin, Shubhendu Trivedi, and Jimeng Sun. Conformal prediction intervals with temporal dependence. Transactions on Machine Learning Research, 2022. ISSN 2835-8856. URL
htttps://openrev/ net fow
Alfred Müller Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2)429-443, 1997. ISSN 00018678. URL htll:ttt::/wwe jstor.
org/ stts/ta/bee14200..
Travis E Oliphant. A guide to NumPy, volume 1. Trelgol Publishing USA, 2006.
Roberto I. Oliveira, Paulo Orenstein, Thiago Ramos, and João Vitor Romano. Split conformal prediction for dependent data, 2022.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confi- dence machines for regression. In Tapio Elomaa, Heikki Mannila, and Hannu Toivonen (eds.), Machine Learning: ECML 2002, pp. 345-356, Berlin, Heidelberg, 2002. Springer Berlin Heidel- berg. ISBN 978-3-540-36755-0.
11

---

Published as a conference paper at ICLR 2024
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vito,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buse E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825- 2830, 2011.
Aleksandr Podkopaev and Aaditya Ramdas. Distribution-fiee uncertainty quantification for clas- sification under label shift. In Cassio de Campos and Marloes H. Maathuis (eds.), Proceed- ings of the Thirty-Sevently Conference on Uncertuinty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pp. 844-853. PMLR, 27-30 Jul 2021. URL https: http:::://proceedingg. mlr www.sprssssee.e....... /ansss/viii htt.vvvvllppp/ee wtt.:/pooppaeell...... html
Nils Reimers and Iryna Gurevych. Sentence-BERTI Sentence embeddings using Siamese BERT- networks. In Proceedings of the 2019 Conference Empirical Methods in Natural Lan- guage Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 3982-3992, Hong Kong, China, November 2019, Association for Com- putational Linguistics. doi: 10.18853/1//D1--10 14100 URL
org
D19 1410
Craig Saunders, Alexander Gammerman, and Volodya Vovk. Transduction with confidence and credibility. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelli- gence, IJCAI '99, pp. 722-726, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. ISBN 1558606130.
Filip Schlembach, Evgueni Smirnov, and Irena Koprinska. Conformal multistep-ahead multivariate time-series forecasting. In Ulf Johansson, Henrik Boström, Khuong An Nguyen, Zhiyuan Luo, and Lars Carlsson (eds.), Proceedings of the Eleventh Symposium Conformal and Probabilistic Prediction with Applications, volume 179 of Proceedings of Machine Learning Research, pp.
316-318. PMLR. 24-26 Aug 2022. URL https: pettps://proceedingg mlr ptwss/v179/ sch 1 ee 2t.mmmll.11...m.m
Bernhard Schölkopf, Peter Bartlett, Alex Smola, and Robert C Williamson. Shrinking the tube: new support vector regression algorithm. Advances in neural information processing systems, 11, 1998.
Tal Schuster, Adam Fisch, Jai Gupta, Mostafa Dehghani, Dara Bahri, Vinh Q. Tran, Yi Tay, and Donald Metzler. Confident adaptive language modeling. Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL httpttttss//ppeeeeeeeaeeee
net wwwt//eettteeeeeeeeeeeeeee www.iuniddul
Kamile Stankeviciute, Ahmed M Alaa, and Mihaela van der Schaar. Conformal time-series fore- casting. Advances in neural information processing systems, 34:6216-6228, 2021.
Sophia Sun and Rose Yu. Copula conformal prediction for multi-step time series forecasting, 2022.
Jacopo Teneggi, Matthew Tivnan, Web Stayman, and Jeremias Sulam. How to trust your diffu- sion model: A convex optimization approach to conformal risk control. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 139940-33960 PMLR, 23-29 Jul 2023. URL https: https://proceeddngg mlr www.s//eesseee. v202 wttp2222/eeeen22eeeeeee htmmmmm.....mmm......mmmm..
Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal predic- tion under covariate shift. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bue, E. Fox,
12

---

Published as a conference paper at ICLR 2024
and R. Garnett (eds.). Advances in Neural Information Processing Systems, volume 32. Cur- files/ http://u....a...oo.oeeeeee2aaaa3 haaaaaa2222222255555553323233222
ran Associates, Inc., 2019. URL http:: htt.ttpss//ppoceeddnseeeeooo....
paper/2019/Eile 8 www.llleetee.....e......eoo eee
Guido Van Rossum and Fred L.. Drake. Python Reference Manual CreateSpace, Scotts Valley,
CA, 2009, ISBN 1441412697.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 1999.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Courna- pean, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. Nel- son, Eric Jones, Robert Kern, Eric Larson, CJ Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake Vand erPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1. Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python Nature Methods, 2020. doi: https:///oo.org/
Vladimir Vovk. Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence, doi: 10. 10.1007//10442--13-99333 URL htttps:://eee ottp:////o/...g/11.1111
74(1):9-28, 2015,
1704720013-3300
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in a Random World. Breinger-Verlage Berlin, Heidelberg, 2005. ISBN 0387001522.
Volodya Vovk, Alexander Gammerman, and Craig Saunders. Machine-learning applications of al- gorithmic randomness. In Proceedings of the Sixteenth International Conference on Machine Learning. ICML '99, pp. 444-453, San Francisco, CA, USA, 1999. Morgan Kaufmann Publish- ers Inc. ISBN 1558606122.
Stéfan van der Walt, S Chris Colbert, and Gael Varoquaux. The NumPy array: a structure for efficient numerical computation Computing in Science & Engineering, 13(2)22-300 01.22223..0000 2011.
Jun Wang, Jiaming Tong, Kaiyuan Tan, Yevgeniy Vorobeychik, and Yiannis Kantaros. Conformal temporal logic planning using large language models: Knowing when to do what and when to ask for help, 2023.
Chen Xu and Yao Xie. Conformal prediction interval for dynamic time-series. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11559-11569. PMLR, 18-24 Jul 2021.
h/tp:e//dr/ccedeee igg ml wtw.s/s.seeeoo..... 19mm
Heng Yang and Marco Pavone. Object pose estimation with statistical guarantees: Conformal key- point detection and geometric uncertainty propagation. 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Jun 2023. doi: 10. 2023. 00864
URL
http: //tp:///xx..m doi. wttp://o......01111////////
10.
Margaux Zaffran, Olivier Feron, Yannig Goude, Julie Josse, and Aymeric Dieuleveut. Adaptive conformal predictions for time series. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedingy of Machine Learning Rexearch, pp. 25834-25866, PMLR, 17-23 Jul 2022. URL https: htttp:://ppcceeinggs. mlr. .tt../gsss.m...sss/ 2162/zaffran22a.11
A PROOF OF LEMMA 1
The TV distance can be written as an integral probability metric Müller 1997>
drv
sup 11 $1
(Epig) Eg(g)).
(17)
13

---

Published as a conference paper at ICLR 2024
Now, we define m (A+ B)/2, v (B-A)/ and f (f mm/p S - [-1, 1]. Noticing
that for any c E R, we have - = Erlf+ -edl-Blle [f + c). we can evaluate the difference in expectations as
Epiʃ] - Kolf] = (Eplfl (e(ff)
(18)
B A
sup
[Ep Eo(g])
(19)
2
g: |aall S1
= (B - A) drv (P, Q)
(20)
Repeating with f= (m - f)/v (which is also in |-, 1). yields a similar upper-bound for Ro(s]] Ep[f], from which the result for [Ep[f] E follows.
B PROOF OF THEOREM
The proof adapts elements of the proofs from Barber et al. (2023) and Angelopoulos al. (2023a).
Let z obtained from by swapping (Xx, Yk) and (Xn+1, Xnt1). where K random variable where P(K = i} W, (note that z = Z). Let
a+1
N (A) + I(A; (on+1.3a41))
R (A) = Σ w; (e)
(21)
Nw +1
be the weighted empirical risk the calibration set plus the additional test example. Let us define
x = inf {x: Rn R (A) sa..
(22)
Given the random variable Z, we can think (Z) as another random variable which is a transfor- mation of Z. Moreover, define the random variable P.(Z) L(>((Z); (X,, Y.)) for [n+ + 1],
as well as the vector of random variables F F(2) = [F] (Z). Fat1 (2)). From Lemma we have
(Z)) < E[F + (B A)drv (F()),
(23)
bound that will use later. Writing (,()) L(>: (X,, Y.) for convenience, we also have, for any \ and for any & E [n + 1].
inti(2; (2;
Σ Ly wr Lnn (A) + wn
Σ
i (,)) (Lx + Lm+1 (w wxx L (A)
20
Wy L, Wh (Ax + B) (wa+1 - w w B
(=1,
W; Li(A) + B
t=1
No
B
N +1 ();
+ No +
(24)
14

---

Published as a conference paper at ICLR 2024
Setting (l..d. data)
Setting (changepoints)
Setting 3 (distribution drift)
www
502
750
1000
1250
1500
1750
2020
230
500
2000
1250
1500
1750
2020
280
1000
1250
1500
1750
2020
10
10
lambda
230
300
750
1000 1250
1590
1/50
2000
230
300
750
1000
1250
1500
1/50
2000
250
500
750
1000 1250
1590
1/50 2000
time
time
time
CRC
Non-X CRC
Figure 4: Average loss (top) and Å (bottom) over 10 independent trials for settings (1), (2), and (3). In this case, À represents the number of predicted labels. We smooth the curves by taking a rolling average with window of 30 time points.
Therefore, setting A Å and using Eq. (10) we obtain i (A; 2d) S
No Nu+1
N Rr (A: 2)+ Nw S
a, which, from Eq. (22) implies X* AzZ²) A(Z). Since the loss nonincreasing with A, we get
E| (A(2);2) < B 1 (X~ 2)] ([Lx(A"(Z*);
P(K i (A
=2(F
ELL.(A +(B++++BB--) +(B-+)+BBB)) ((IB-)))(((2)
1=1
[(F((2))
= E
L. Z)
+ +B--A (88-)
w (F())
= [Rnt1(M((2))] + (B--)) (.dTv(F(()
a a (B A) Σ w (F (F( F(Z)))
(25)
The result follows by noting that drv (F(Z),F(Z') < drv [2, Z
Eq. (25)
actually a tighter
bound, similarly what has been noted by Barber al. 2023
C MULTILABEL CLASSIFICATION IN A TIME SERIES
Fig. shows results averaged across 10 independent trials for 0.2 and setting À in slightly different way than that of 84.1 In this case, À represents the number of active labels and we use (X2) top->(f(X;)) "he main takeaways remain the same: both methods perform similarly when the data is exchangeable, in setting (1). Accounting for the non son---hhanncablitty introduced by changepoints and distribution drift using our method enables lowering the risk to the desired level
in settings (2) and (3).
15


Reviews:
[{"review_id": "qKuiMh1dno", "reviewer": "Reviewer_2JpW", "summary": "The paper describes how to perform conformal risk control for non-exchangeable data in the split conformal setting. It is shown that the proposed method has adaptive coverage guarantees, and performs well on a mixture of real-world and synthetic settings.", "questions": "Please look at questions in the \"Weaknesses\" section.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper connects two modern techniques in conformal prediction, and is thus very relevant for the community. It is well-written and easy to follow as an expert. The writing is simple, and I expect the paper will also be easy-to-follow for readers unfamiliar with conformal prediction.", "weaknesses": "The method combines previous work in a relatively straightforward way. The proof of Theorem 1 does not introduce new techniques. The experiments follow settings proposed in previous works. The paper is solving a completely new problem, and naturally, there are no baselines for it. \n\nThus, while the proposed method is novel and useful, the paper would be strengthened with a more in-depth theoretical/experimental study. Some suggestions are,\n- Writing down full-conformal and cross-conformal versions of the proposed method\n- Considering new experimental settings, such as established ML distribution shift datasets\n- Discussion on how one can set the weights in practice\n- An interpretation of Theorem 1 for a non-expert in conformal\n- A discussion around the implication of Theorem 1 for specific types of distribution shift\n\nFor instance, for the synthetic experiment in Sec 4.1, some questions that can be considered are, \n- What is the exact coverage guarantee of Theorem 1? Could you put it on the plot and compare it to the obtained coverage? \n- Are there some \"optimal\" weights that give close-to optimal coverage? \nSimilar questions can be considered for the other experiments, although the true TV is not known, so the authors would have to think of other ways of analyzing the experiment. \n\n## Small errors/questions: \n- Just below eq. (5), C_\\lambda' should be C_{\\lambda'}\n- Sec 2.3: \"loss is nonincreasing\": nonincreasing in which parameter and in what sense?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "FU8VV5F9ID", "reviewer": "Reviewer_wGbj", "summary": "This paper expands on the non-exchangeable setting for conformal risk control by Angelopoulos et. al. (2023). Conformal risk control is a generalization of conformal prediction that expands control of coverage losses to control of any monotonic, upper-bounded, exchangeable function $L \\colon \\Lambda \\rightarrow [0, B]$, where $\\Lambda$ is the space of single-dimensional inputs to ${L}$. Most often ${L}$ is some deterministic function $\\mathcal{L}$ of a parametrized, conformal set $\\mathcal{C}(X; \\lambda)$ and the label $Y$ that obeys $\\lambda_1 \\leq \\lambda_2 \\implies \\mathcal{C}(X; \\lambda_1) \\subseteq \\mathcal{C}(X; \\lambda_2) \\implies \\mathcal{L}(\\mathcal{C}(X; \\lambda_1), Y) \\geq \\mathcal{L}(\\mathcal{C}(X; \\lambda_2), Y) $.\n\nAs the paper by Angelopoulos et. al. (2023) showed, conformal risk control is considerably more flexible than standard conformal prediction, while still retaining nearly identical guarantees. The work by Angelopoulos et. al. (2023) briefly touched on straightforward extensions to conformal risk control, including proving a bound on the degradation in guaranteed risk as a function of $\\sum TV(Z_i, Z_{n+1})$, where $Z_i = (X_i, Y_i)$, similar to the work of Barber et. al. (2022). This paper further includes the use of data _weight_ functions (as in Barber et. al. (2022)), and shows that this can have good empirical impact on several experimental domains.\n\n[1] Conformal Risk Control. Anastasios N. Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, Tal Schuster. 2023.\n\n[2] Conformal prediction beyond exchangeability. Rina Foygel Barber, Emmanuel J. Candes, Aaditya Ramdas, Ryan J. Tibshirani. 2022.", "questions": "- 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 = \\textrm{sim}(X_i, X_{n+1})$. \n- Otherwise, it's also unclear what the best strategy should be for selecting weighting functions (this seems rather adhoc in the experiments).\n- Note that we can get the same bound in Lemma 1 directly from the analysis of Angelopoulos et. al. by defining $\\tilde{g}(Z) = g(Z) - A$, which then has range $[0, B - A]$ for $g(Z) \\in [A, B]$, and then it follows that\n$| \\mathbb{E}[g(Z)] - \\mathbb{E}[g(Z')] | =  | \\mathbb{E}[g(Z) - A] - \\mathbb{E}[g(Z') - A] | = | \\mathbb{E}[\\tilde{g}(Z)] - \\mathbb{E}[\\tilde{g}(Z') ] |$,\nand then we proceed directly with the proof in Angelopoulos et. al. to get\n $| \\mathbb{E}[\\tilde{g}(Z)] - \\mathbb{E}[\\tilde{g}(Z') ] | \\leq (B-A) TV(Z, Z').$", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper is clear, and does a good job at deriving bounds for how weighted conformal risk control performs under non-exchangeability. Non-exchangeability will happen often in practice, so it is impactful to explore more robust weighting schemes and their implications. The empirical results are encouraging. It's a bit unclear as to how _useful_ the guarantees are, in the sense that they can be too loose if $\\sum w_i TV(Z, Z^i)$ is very large, or more likely yet, simply unknown. When some practical knowledge about the domain is available, however, designing an appropriate weighting scheme can be effective (which is demonstrated for some of the experiments here).", "weaknesses": "While, again, the paper is nicely written, it is a somewhat incremental step from previous work in Barber et. al. and Angelopoulos et. al. 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})$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "U2ZaCXPhJo", "reviewer": "Reviewer_aj7z", "summary": "This paper extends conformal risk control (CRC) under the exchangeable setup to the non-exchangeable setup, i.e., converting “Angelopoulos et al. (2023a)” to the “Barber et al. (2023)”-style. In particular, the coverage guarantee under non-exchangeability is stated and proven in Theorem 1 and the proof follows techniques by Barber et al. (2023) and Angelopoulos et al. (2023a). The efficacy of the proposed algorithm is empirically demonstrated by using synthetic and real data with multiple shifts.", "questions": "1. Can you draw plots such that CRC is clearly broken under the non-exchangeable setup?\n2. Can you provide the concrete scenario on why we need to consider the non-exchangeable setup in open-domain QA experiments? You also can replace the experiments. \n3. Can you justify why weights are generated in a data-dependent way in open-domain QA experiments?\n4. 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?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Originality: This paper combines the results by Barber et al. (2023) and Angelopoulos et al. (2023a), leading to a new result. \n\nQuality: the claim is well-justified via Theorem 1 and its proof. \n\nClairity: the paper is mostly well-written. \n\nSignificance: considering that the conformal prediction can be extended to the non-exchangeable setup by Barber et al. (2023), so it is not surprising that conformal risk control can be extended in a similar way. But, it is still a new result.", "weaknesses": "The following includes my concerns. \n\n1. Under the non-exchangeable setup, the CRC should be broken, and this is why we need non-exchangeable extension of CRC. But, I cannot see the trend in Setting 3 in Figure 1 and Figure 3, which is unsatisfactory. In particular, I’m not convinced why open-domain QA experiments (related to Figure 3) fit the non-exchangeable setup – the concrete scenario on why we need to consider the non-exchangeable setup here is required. Moreover, the way to generate w_i is not correct – by Barber et al. (2023), w_is prespecified but not data-dependent (see Section 4.5. by Barber et al. (2023) for a careful discussion on the data-dependent weights). This may demonstrate that open-domain QA is not a proper target of this method. \n\n2. It would be more readable if the controlled loss is summarized in scalar statistics. For example, in Setting 3 in Figure 1, I cannot see why the proposed approach is good.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "MBPPVQCtvx", "reviewer": "Reviewer_r1o1", "summary": "The paper shows how to perform conformal risk in a non-exchangeable setting --- i.e. for any given loss l, providing a threshold such that the true loss is less than some pre-specified alpha. Unlike the typical conformal prediction setting that assumes that data satisfies the exchangeable assumption (i. e. any permutation of the data is equally likely), it tries to relax such assumption. Also, unlike the typical conformal prediction that provides a prediction set that's supposed to contain the true label, it studies a more general form usually referred to as conformal risk control.\n\nThe paper achieves the above goal by combining Barber et al. (Conformal Prediction Beyond Exchangeability) and Angelpoulos et al. (Conformal Risk Control). \n\nFinally, the paper tests the idea on three datasets.", "questions": "-In Equation (3) where Z_i is defined, shouldn’t Z_i be what you get by swapping the test point (X_{n+1}, y_{n+1}) with (X_i, y_i) as opposed to the nth calibration data point (X_n, y_n)? This is how things are defined in Barber et al. as well.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "-The idea proposed here seems to actually work in practice as shown by their experiments.", "weaknesses": "-The main contribution of the paper seems to be just a combination of two techniques, conformal prediction beyond exchangeability and conformal risk control. Once one understand the idea behind conformal prediction (i.e. finding an (1-alpha) quantile of the conformal score in the calibration data set), the idea of conformal risk control follows pretty naturally (finding some alpha-cut off for some monotonic loss in the calibration data set). And hence, techniques known for conformal prediction can be easily translated to conformal risk control — i.e. handling distribution shift. In this specific case, the paper is leveraging the technique of conformal prediction beyond exchangeability. Also, 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 in applying the beyond the exchangeability idea to the conformal risk control setting compared to applying the idea to the typical conformal prediction setting, it would be great if the authors can emphasize that and how this difficulty was overcome.  \n-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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)