Online Selective Conformal Inference: Errors and Solutions
Authors: Yusuf Sale
Aaditya Ramdas
Venue: Accepted by TMLR ()

Abstract: In online selective conformal inference, data arrives sequentially, and prediction intervals are constructed only when an online selection rule is met. Since online selections may break the exchangeability between the selected test datum and the rest of the data, one must correct for this by suitably selecting the calibration data. In this paper, we evaluate existing calibration selection strategies and pinpoint some fundamental errors in the associated claims that guarantee selection-conditional coverage and control of the false coverage rate (FCR). To address these shortcomings, we propose novel calibration selection strategies that provably preserve the exchangeability of the calibration data and the selected test datum. Consequently, we demonstrate that online selective conformal inference with these strategies guarantees both selection-conditional coverage and FCR control. Our theoretical findings are supported by experimental evidence examining trade-offs between valid methods.

Published in Transactions on Machine Learning Research (07 (07/2025)
Online Selective Conformal Inference: Errors and Solutions
Yusuf Sale
sasuff.sal@rfii.mma
Institute of Computer Science Ludwig-Marimiiien Universität München Munich Center for Machine Learning (MCML)
Aaditya Ramdas
wramdas@stat. edu
Departments of Statistics ond Machine Learning Carnegie Mellon University
Reviewed on OpenReview: https: openreview. pdd
Abstract
In online selective conformal inference, data arrives sequentially, and prediction intervals are constructed only when an online selection rule is met. Since online selections may break the exchangeabilitty between the selected test datum and the rest of the data, one must correct for this by suitably selecting the calibration data. In this paper, we evaluate cxist- ing calibration selection strategies and pinpoint some fundamental errors in the associated claims that guarantee selection-conditions coverage and control of the false coverage rate (FCR). To address these shortcomings, we propose novel calibration selection strategies that provably preserve the exchangeability of the calibration data and the selected test datum. Consequently, we demonstrate that online selective conformal inference with these strategies guarantees both selection-conditiona coverage and FCR control. Our thcoretical findings are supported by experimental evidence examining trade-offs between valid methods.
1 Introduction
Conformal prediction Vook al. 2005) has gained significant traction in recent years method for uncertainty quantification equipped with statistical guarantees. Conformal prediction provides prediction intervals (or sets) that achieve predefined coverage level, regardless of the underlying data distribution. In contrast to the full (or transductive) conformal procedure, the computationally more efficient split (or inductive) conformal prediction (Papadopoulos et al. 2002 Tei et al., (008)) splits the available data into two parts: one for model training and another for calibration. More formally, suppose a pro-trained model à X' y is given, mapping features X X' to predictions of the label Y V. Further, denote by [(X, Y)) independently labeled calibration data set. Given the current feature Xn+1, the goal is to construct prediction interval for the unseen label Ya+1- If the data sequence ((X,, Y is exchangeable, the constructed prediction interval č₂ (Xn+1) contains Yx+1 with high probability (viz. the prediction interval (X,()))) is valid). Specifically, we have
P(Y+1 E C, (X 2 az,
(1)
where the probability is taken over {(X,, Y) emphasizing the marginal nature of ①
Conformal prediction has also been successfully adapted for online applications. Assume that the data soquence {(X,, Yo) S X y is observed sequentially: at each time t, we observe the previous label Y-1 and the current feature vector X,. While much of the literature has focused on addressing cases where exchangeability does not hold proposing generalizations relaxations of this assumption (Tibshirani et al.

---

Published in Transactions on Machine Learning Research (07/200) 2025)
X
5
2s
1y
1g C10
11
ta
ts
Cg
0g
81o
time
Figure 1: An illustrative example of the online selective (conformal prediction) setting. (a) Usual online conformal prediction setting, where one constructs for each time t 2 O prediction interval. (b) In the online selective conformal predictive sctting, we only report prediction intervals for selected (o) times, while no prediction intervals are constructed for those that are not selected (x).
2019 Gibbs & Candes 2021 Barber et al. 2023 our focus is different: for us the data exchangeable,
but challenges (indeed, deviations from exchangeability) are caused by selective querying/reporting. To elaborate, suppose data arrive sequentially, and wish to selectively report prediction intervals (see Figure [ for illustration). The selection process (formally defined in Section 2 might, for instance, dictate that prediction interval for Y, is reported only if X, > 2. More generally, the selection rule may depend on past decisions (in a restricted way formalized later) for example, whether prediction interval was reported for previous observations. Conscquently, prediction intervals are not constructed for every observation, adding a layer of selective decision-making online conformal inference, referred to as online seleclive conformal inference.
In the online selective sctting, it is natural to require that prediction intervals valid conditioned the relection-conditionall conditional coverage:
selection event-a metric called selection-
Wt 2 0 P(Y: E O,())S 1 1-a
(2)
Intuitively, a prediction interval should be valid whenever a selection is made, that is, whenever S = Since the data itself is exchangeable, this requirement might seem innocuous at first glance. However, it is important to highlight critical aspect. The (potential) dependence between online selections and the prediction intervals can give rise to temporal mulliplicily. In the statistical literature, this issue was previously recognized in the context of constructing confidence sets. It was first noted in the offline setting by Benjamnini
& Yokutieli (2005) and later addressed in the online regime by Weinstein & Ramdas (2020). Recently, Bao 20224a] addressed the same problem and proposed procedure called calibration after adaptive pick
ct al.
2024a), we demonstrate that the proposed method does not, in fact, guarantee selection-conditional CCAP)
to construct conformal prediction intervals that satisfy (2 However, despite the claims of Bao
et al.
coverage.
Other metrics to assess the errors associated with the reported prediction intervals the false coverage proportion (FCP) and false coverage rate (FCR) (Weinstein & Ramdas 2020
FCP(T) Er S,1(Y, & C,(X,)) FCR(T)- = ΣT S,1 C.(X)))
(3)
I IVE. S.
1 IV
where a V b- = max(a, b) for a, R. The FCP measures the proportion of selected instances where the true label Y, falls outside the prediction interval Či()),, while the FCR is the expected value of the FCP.
2

---

Published in Transactions on Machine Learning Research (07 (07/)025)
Weinstein & Ramdas (0200) proposed a method called LORD-CI. CI, which effectively controls the FCR below larget level a. Although originally proposed for confidence sets, the authors note that the LORD-CT procedure can be adapted to the online conformal prediction framework. We find that their claim is true in a particular restricted sctting, but that a broader extension is not straightforward and highlight the difficulties involved.
The key challenge in the online selective conformal inference setting is the selection of calibration data to form C, when S, = 1. Specifically, since the selected data point might not be exchangeable with all preceding data (due to the selection), how should calibration data be chosen so as to restore the exchangeability of the test datum and the calibration data? To address this, we discuss various calibration selection strategies within the framework of online selective conformal inference, evaluating their ability to ensure selection- conditional coverage. Our theoretical results reveal that many existing calibration selection strategies fail to meet this quite stringent criterion. To bridge this gap, we propose novel calibration selection strategies with thcoretical guarantoes for selection-conditional coverage, supported by simulation studics. Beyond selection-conditional coverage, we further investigate whether the (seemingly) weaker metrie of FCR can be successfully controlled by online selective conformal prediction algorithms instantiated with both existing and novel calibration selection strategies. Interostingly, we find that no existing strategy achieves this, while our proposed methods provide provable guarantees.
The remainder of the paper is organized as follows. Section 2 formally defines the problem and introduces necessary notation. In Section g we outline the online selective conformal inference procedure and discuss several calibration selection strategies, including both existing and novel approaches. Section ! assesses, empirically and theoretically, whether existing calibration selection strategies ensure selection-conditional coverage and provides theoretical guarantees for proposed methods. Section investigates FCR control, followed by discussion of other related conformal methods. We conclude with a summary of related work and a brief discussion. Omitted proofs are deferred to Appendix
2 Problem Setup
Consider data {(x,, Yi) X'x x y arriving sequentially: at time t, we observe the previous label Y,-1 (if > 0) and the new feature X,. For brevity, we also write Z = (X, and 2 = XxY, We assume that a pre- trained model f X' + 3/ is given, where Y; = (x,,) denotes a prediction of the label Y, Let Se : X + [0.1] be an online selection rule, and correspondingly denote by S. = S,(X,) the selection indicator. Here, St = indicates that a prediction interval for Y, will be reported. Further, we denote by F = ( (So..... St-1) the filtration generated by past selection decisions. We focus on a restricted but reasonably rich class of decision driven rules:
Definition 2.1. A selection rule S, : X 10, is called decision driven if S is Fe-r-measuralle.
For example, when X = RR the following selection rule is clearly decision driven, as it depends only past selections (Sihig-i 1 and constants To, TI:
[-1
x x 1 I < Ti
Σ i=0
S
The resulting sequence of selection decisions (Se) is then defined recursively. At time t= 0, the threshold equals Ti, 80 Sn 1 if X, < Ti, and S, 0 otherwise. At time t= the threshold becomes т₁ + Sy; we then set S = 1 if Xi < T + So, and S = 0 otherwise. This recursive procedure continues analogously for all t 2 0. For now, let C x' x(0, 1] + 2 denote a generic prediction interval for Y,, with details on its construction and validity addressed in the next scction (for simplicity we omit its second argument corresponding to the target miscoverage level). Define (Cr(X.) S. = 1)220 as the collection of prediction intervals produced by an ouline selective procedure (namely, only reporting (,)))) whenever
1). Let R : X 1x) y + R denote generic non-conformity score, such absolute residuals R, Ip(x,) - Y/-. We refer to {(X,,)) : i E D.) as calibration data at time t. For E (0, 1). the empirical quantile of the non-conformity scores (RD) denoted by Q.
3

---

Published in Transactions on Machine Learning Research (07 2025)
Now, define the index set
= Jt U Tt.o:
where Jff = --n....., with n E N, the set of indices of some offline data, and Jr.on = ft.....t- 1 the indices of the online data up to time t, respectively. Additionally, let N Noat where Nof = To and No. To Furthermore, assume that the offline and online data exchangeable, though this assumption will be relaxed later. Additionally, following Bao et al. (0024a), we make the following assumption through the paper:
(A) All decision driven selection rules (2: are independent of the offline data (Zi)iE
We adopt Assumption mirror the setting of [ao et al. (2024),, who operate under the same assumption. This aligument enables a direct and transparent comparison between existing and novel calibration selection strategies. Importantly,
that the selection rules independent of the offline calibration pool-to to
if Assumption [A] is violated, post-selection exchangeability may no longer hold, and the formal validity guarantees presented in this paper do not apply in general. Finally, we note that Assumption [A] necessary whenever oflline data is used the calibration selection process: without it, the select ion rules may depend on the offline pool, breaking the permutation invariance required for our exchangeability arguments.
From time t ==0 0 onward data arrives sequentially, and selections are performed for this newly arriving data. Lastly, we formally introduce the ouline calibration (data) selection protocol. Let KG X - {0, 1 denote the calibration selection strategy (strategy for short). Consequently, we define the calibration selection protocol (mapping data to calibration indicos) as
1: N + +
(Z......,Z2) {j T:: KG(x))= 13.
(P)
Thus, we have D: (Z n..... Zz) T. Specifically, (x,X)) =1 indicates that, at time the candidate calibration datum 2, = (X,,Y) will be included in the calibration set. Note that, we only perform calibration selection, if S,(,,) = 1. Otherwise, calibration data is unnecessary, as prediction intervals are constructed and thus require a calibration set only when the test datum is selected. Importantly different choices of K, influence both the size and composition of the calibration set, which in turn impacts the validity and informativeness of the resulting prediction intervals.
3 Online Selective Conformal Inference
An online selective (split) conformal inference procodure involves the following steps. Up to time 2 O, we observe the data (Xo, Yo,.... Xx-i), which consists of feature-response pairs from previous time points. Then, in the vein of split conformal prediction, we proceed as follows (Bao et al. 2024a):
1. Specify the selection rule S, E Ft-1, and calibration selection strategy Kr before observing the current feature X
2. Observe X,, and if S 1 decide to report a prediction interval for the yet unobserved Y,-
3. Obtain the calibration indices D, via
4. Compute the non-conformity scores (RilieD, for the calibration set.
5. Report the prediction interval
- R(X.v)) (())((R)))
A crucial aspect to address is the selection of calibration data. In standard (online) conformal prediction, the calibration data is typically chosen as D. = Tt which corresponds to choosing the calibration selection stratogy (X,)) 1 in the calibration selection protocol (P). However, using the entire available data for calibration poses challenges in the selective setting. Roughly speaking, the selection rule introduces asymmetric dependence between the current. data point. and past. data through the selection process.
4

---

Published in Transactions on Machine Learning Research (07/2025)
Recall that we focus on decision driven selection rules; while the selection rule itself does not depend Xt, it does rely past decisions and therefore depends on (Xi)ien. Such dependencies typically violate exchangeability, the workhorse of conformal prediction. As a result, naively applying standard conformal methods can lead to violations of desired coverage guarantecs. Mitigating this requires carefully designing calibration selection strategies that account for the dependence introduced by the selection mechanism. The challenge, therefore, to "design" calibration selection strategies that preserve exchangeability while maintaining a sufficiently large calibration set. As we will see soon, different strategies impose varying trade-offs between statistical guarantees and practical applicability. Some approaches prioritize preserving exchangeability at the cost of reducing the calibration set size, while others aim to retain more calibration points but risk violating exchangeability.
A natural question that arises is: given that a test point has been selected, can we identify a suitable calibration selection strategy that ensures exchangeability between the calibration data and the test datum? The answer is affirmative but also pinpoints the challenges inherent the selective sctting.
3.1 Existing Calibration Selection Strategies
To address this question, we first discuss both existing and novel calibration selection strategies. A natural point of departure is the full strategy (FULL):
Kx(X)) -1, for J.
In other words, at each selected time the calibration data consists of all previously observed data, i.e., D. = Jt. While this strategy yields the largest calibration set, typically breaks exchangeability because the test datum is selected via rule, whereas the calibration set unaffected by the rule, consisting of all previous observations.
Another strategy, the selection-full strategy (S-FULL) selects calibration data according to the selection rule given at time t, i...
xx(x))= S,(,), for j E J.
However, because we restrict ourselves to decision driven selection rules, the test datum at time is selected independently of future outcomes, while this is not true of the calibration set. This asymmetric dependency leads a violation of exchangeability.
Similarly, we define the selection-ftred strategy (S-FIX), which selects calibration data (according to the selection rule given at time t) solely from the offline data:
K((X,) { (x2))) for Je,off, for j E Je
(i
If Assumption (A) holds, this stratogy is unproblematic, as the offline data remains independent of the selection rules. However, caveats exist: when no offline calibration data is available or when Assumption (A) does not hold. Additionally, even if Assumption matter how large t is.
A] is satisfied, very few calibration points may be selected,
Recognizing these limitations, Bao et al. 2024a recently introduced an alternative strategy. The aduptive calibration selection strategy (ADA) is defined as follows:
(x)))) ka(X,)
for j E Jr,off = -x)
(iv)
for j E Jr
Bao al. (2024a) claim that this adaptive calibration selection strategy ensures selcction-conditional cover- age. However, we soon provide both theoretical and empirical evidence demonstrating that this is, in fact, not the case.
5

---

Published in Transactions on Machine Learning Research (07 (07/2025)
3.2 Novel Calibration Selection Strategies
To address such issues, we introduce the exchanngeaabillttyyrreeeeee strategy (EXPRESS), defined follows:
=
I = for jerjec J.
(
iEJe.om
Clearly, this strategy is quite stringent, as it requires identical past selection decisions for both the candidate calibration point and the selected test datum. Consequently, the calibration data includes only points that have undergone the same selection process as the test datum, strictly preserving exchangeability. However, this restrictiveness significantly reduce the calibration set size, potentially rendering it empty in some cases.
To relax the strict constraints of the previous strategy, we introduce variant called the k-erchangeable preserving strategy (K-EXPRESS), which considers only the last k 2 1 points:
[-1 kx(X)) SX,) II ( ((x)) for J
(vt)
13. Instead of enforcing consistency with all past selection decisions, K-EXPRESS restricts the comparison to the last k points. This variant mitigates the risk of an excessively small calibration set while still preserving exchangeability.
where J.H off Uft-k....,;
Our final strategy, called EXPRESS-M, M, applies both S-FIX and EXPRESS separately and then merges the result- ing prediction intervals. That is, prediction intervals are constructed independently using both strategies, and their interscction is taken. While various merging schemes are possible, we use an uneven split of a between the Iwo methods for constructing the final prediction interval. Specifically, for >> 0 we allocate (1/Vt)a to S-FIX, while the remaining (1 - 1/vE)a is assigned to EXPRESS. To make this construction ex- plicit, let asr (1/vt) a and agx = (1 1/vt) a, so that asp + ogx a. At each time t, we construct intervals ÖFF and CF at levels 1 - OSF and - OEX,, respectively, and define the final prediction interval as
C. C n CEX
This merging approach mitigates the restrictiveness of EXPRESS which can result in too few calibration data and, consequently, excessively large prediction intervals by leveraging the more inclusive nature of S-FIX.
Remark 3.1. One might naturally ask why we do not adopt a strategy that applies Sr(X,) for j E Jr,off while applying the wewannaaabblityypreerriie restrictive, and therefore yield larger calibration set. While this may seem unproblematic at first glance, we show that it subtly violates the exchangeability between the (offline) calibration data and the test datum.
strategy (u) for j E Jn.o- This strategy would indeed be less
4 Selection-Conditione Coverage
In this section, we show shortcomings of existing calibration selection strategies in ensuring selection- conditional coverage. Additionally, demonstrate that online selective conformal inference, when instan- tiated with our novel strategies, guarantees selection-conditionaall coverage. First, we evaluate both existing and novel calibration selection strategies empirically with the following simulation:
Simulation 4.1. In each iteration of the simulation, we generate data of size N Noir + Now. For the following results, we set Nair 10 and Non 20. We generate univariate feature X Unif(0, 2] and model the response as
Y= +x{x))++ +e with x(X)= = X3,
where we assume a heterogencous noise distribution, ie., elx V(O,X/2) For simplicity, we assume i 1. Since we are in synthetic setting, we have direct. access to the true function and use it model;

---

Published in Transactions on Machine Learning Research (07/200) 20225
0.50
0.45
0.35
0.30
0.000
0.000
0.000
0.000
0.171
0.009
0.058
0.605
0.633
30.000
10.000
30. 000
23.581
560
9.760
10.585
0.25
FULL
S-FIX
S-FULL
ADA
EXPRESS
EXPRESS-M
S-EXPRESS
|Bao al.. 2024) (ours)
(ourst
lourst
Figure 2: Miscoverage (x) is shown alongside the number of calibration points (m), median interval length
(m) and the fraction of infinite length prediction intervals and the target level (--). All metrics are averaged over 1 10 runs.
We highlight provably correct methods (V)
specifically, we have (T-) v(.). Further, the select ion rules are defined as
a < 1+
Ei s for st-1 --1
x +
S.2 m
for = t,
where we choose To = 20 and 71 = 16. We then perform online selective conformal prediction with both existing and novel strategies. All reported metrics are averaged over = 1 x 10 runs.
Results. Figure summarizes the performance of different calibration selection strategies in online selective conformal prediction. With the exception of S-FIX, all existing strategies fail to provide valid selection- conditional prediction intervals, as they do not maintain the target miscoverage level of a 0.4. In contrast, strategies achieve exact coverage. From a practical
both S-FIX and the family of exchanggeabllty-ppreee standpoint, while EXPRESS yields the smallest prediction intervals, its restrictive nature results in a significant fraction (*= 17.71%) of infinite-lnngth intervals. Its variants, EXPRESS-M and K-EXPRESS, mitigate this issue and perform comparably well.
These results empirically highlight the fundamental shorteomings of existing calibration selection strategies in ensuring selection-condie conditional validity. To reiterate, the axchangeability-preeevvvi approaches not only achieve the desired theoretical guarantees but also offer practical advantages by balancing interval tightness and calibration set size. While EXPRESS is the most conservative, its variants effectively address its limi- tations, making them viable alternatives in real-world applications. In Appendix D we present additional simulations using alternative decision driven selection rules.
We now proceed to the theoretical results of this section. First, we define the selection procedure, which maps data to the augmented calibration indices
IzZZ [t) if S,(x)) 1, Ij(Z-n...., ,.) otherwise.
i. N+ + 231100 (Z n.... Z,)
7

---

Published in Transactions on Machine Learning Research (07 (07/2025)
where [+) denotes the calibration selection protocol
P So
E Iz if and only if S,(X,) = 1.
(4)
Now, let D. .......... 2,) and let a be a permutation of the indices in Dr. Define the extended permutation of the indices in {-m,..., tt as
#(1) 11 T(1) for i Dr,
(5)
for i of Dr.
Whether not (Z, (i.e., the selected calibration data, and the selected test datum) are exchangeable depends on the calibration selection protocol Recall that {Zi are exchangeable if for any set of indices D such that P(D, D) > O, and any permutation л of indices in (equivalently, any extended permutation मे in 5 and any measurable A S (X D1, we have
P((Z))ED A, D} P ( (1))
E AAD, D).
(6)
To demonstrate 60, it is sufficient to show that
P((Z))iED E A, A, IZ m.... Zo) D) P((ZT())EED E A, (ZZ(()=(-)) (,)))))) D}
( P((Zz())i E A, (Z (
While the first equality follows from exchangeability of (Z-n.... Zi), the important argument lies in step (*). Specifically, (+) holds true if
(7 74) = ( 770))
(S)
Lemma 4.2. Let (Si)12a be sequence of decision driven selection rules and denote by {St J:20 the sequence of selection rules generated when operating on Zū)--).... Za(e)- The selection rule sequences {S: and {S heo are identical, if SX,) = =x(( for all j E Jr.on
Proof. Assume S,(X,) = Sy(X for all j E Ji Now, let j = 0. By assumption, we have Se(Xp) = (o(X) This yields S = S₁; in other words the rules at time 1 are identical. Then, the claim follows by induction. This completes the proof.
The following lemma demonstrates that the selection procedure, when instantiated with strategies (fv), does not necessarily satisfy symmetry (S). While this may be apparent for the full and selection-full calibration selection strategy, we explicitly demonstrale that symmetry also fuils for the recently proposed adaptive rule.
Lemma 4.3. Without additional assumptions, the selection strotegies metry
and iv do not satisfy sym-
Proof. Let (8 h:20 be the sequence of selection rules generated when operating Zū(-n); ... Z Now, let the permutation be transposition such that T(t) s, rTs)) t and T(j) = for * s,t. Fix DD Jr.n- For strategies (t), and ( the claim follows immediately, since we have S(())) # (Xx) without additional assumptions. By definition of strategy iibh S, = S,(X.)) 1. If symmetry holds, expect that
(X X x()) = Sx =1
(7)
8

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Again, by definition of 22 have Sx,),) Sx(X)). Hence, Lemma 4.2
ensures that the selection
sequences (St)120 and {St 1:20 are indeed identical. Consequently, Equation
can reformulated as
(( = ()(+(())) =1.
(8)
Given that m(}) E De, it follows by definition of the extended permulation that S((Xat)) 1. However, the issue in lies in the fact that
((())))) (X((t)
cannot be guarantced without additional assumptions. This completes the proof.
What Lemma 1.3 shows is that the selection strategies
and iu do not satisfy symmetry S in
general. However, note that (S) is sufficient but not necessary condition for (+) in the above display. This leaves open the possibility that these strategies might still satisfy (+) in certain cases. Nevertheless, as demonstrated by the counterexample in Simulation I.I they do not satisfy it in general.
Now we turn to our positive results. Specifically, we show that the exchangeablitt--prservvi strategies satisfy symmetry, thereby implying exchangeability and, via classical conformal arguments (as demonst.rated in Appendix B). selection-conditione coverage.
Lemma 4.4. The selection procedure instantiated with strategies Thas, the random voriables {Zi),e are ezchangeable.
OT
satisfies symmetry
S
Proof. Due to Assumption
A)
the claim for strategy
283
holds trivially true. For strategy
consider any
arbitrary permutation æ and let j Dr. By definition, follows that
1-1
( II - 1.
(9)
meaning that all the above indicators equal to one. Applying the same observation to & E D,, see that
Vj D.: 0 S,(X)) = S((X;) = SX(i)..
(10)
Then, by Lemma 4.2 we know that the selection rule sequences {S, and {S h20 are identical. Conse- quently, we can rewrite 9 as follows:
S (X,)
= -x)
==
Since T(j) E Dr, we also have S,(X,) = S((Xa(n) from
10
Thus,
Si
II
= (X = 1.
1=0
Analogous reasoning yields the claim for strategy (er)
Since
is sufficient for (x), the random variables
{ [7:) (Z,), are exchangeable. This completes the proof.
In fact, we can show that online conformal inference with the exchangeabilltt- strategies ensures an even stronger notion of selection- conditional coverage:
selection-conditionaa Theorem 4.5. Online selective conformal inference with strategies conditional prediction intervals. Specifically, we have
M
or
produces strong selection-
P C( So su, ..... S.11 S, 1 2 1
for any 2 0 and any (So..... st-1) E 10.1)--1, when P(Su Su...., S St-1, St 1) 0. Thus, relection-conditiona coverage 2 is fulfilled.
9

---

Published in Transactions on Machine Learning Research (07/2025)
Theorem 4.5
proved in Appendix B Since Theorem 4.5 ensures (strong) selection-condtiionl validity for
strategies and ( applying the Bonferroni inequality [Bonferron] 1936) guarantees that the intersection of the corresponding prediction intervals remains valid. Hence, the merging strategy also produces (strong) selection-conditional prodiction intervals.
To summarize, we have shown that while (most) existing strategies fail to ensure selection-conditionaa cover- age; our novel proposals successfully achieve it. An equally important takeaway that achieving selection- conditional coverage is nontricial, as exchangeability can be violated in many ways, necessitating fully symmetric strategy one that, we have shown, can be quite restrictive (in terms of selecting suitable calibration data).
5
FCR Control
Another metric for evaluating the errors in reported prediction intervals is the false coverage rate (FCR), defined in (3). We evaluate whether online selective conformal prediction, with both existing and novel strategies, effectively controls the FCR below specified target level.
Simulation 5.1. The data generation follows the same sctup in Simulation 4.1 Here, however, consider longer time horizon by choosing Na# 50 and Non 200. For 1 2 0, the selection rule is given by
+ THII<N
<
S
(11)
where we choose = 200 and 1.
Results. Figure 3 provides comparison of existing and novel strategies in terms of FCR control, growth of calibration sets, and the informativeness of prediction intervals over time. We discuss the results in the following:
Subplot (a) illustrates the FCR as time progresses. All novel strategies successfully control the FCR at the target level a 0.4, while ADA fails to do so. Although other existing strategics appear to control FCR in this specific simulation, Appendix D we present cases where they do not. This highlights key insight: depending on the data-generating process and selection rule, some strategics may incidentally control FCR, even though they do not provably do so.
Subplot (b) reports the number of calibration points over time. As expected, all strategies exhibit their charactcristic behavior: S-FIX selects calibration points exclusively from the offline set, preventing any growth beyond its initial size Not = 50, while FULL and S-FULL accumulate calibration points unrestrictedly. Notably, EXPRESS-M emerges as compromise between EXPRESS and S-FIX, balancing the benefits of more restrictive approach that leverages online data with the need for a sufficiently large calibration set to construct informative prediction intervals.
Subplot (c) reports the fraction of prediction intervals that are of infinite length. The EXPRESS strategy exhibits a steadily increasing fraction of such intervals over time, highlighting its restrictive nature, which often leaves too few calibration points to construct finite prediction intervals. contrast, variants such as EXPRESS-M and 10-EXPRESS, demonstrate substantial improvements. This highlights their viability as more flcxible alternatives that control FCR while ensuring the prediction intervals remain informative.
Subplot (d) shows the median length of prediction intervals as function of time. Although FULL accumulates the largest calibration set, it produces the widest intervals because it includes all previous examples without considering the sclection mechanism, leading clearly to selection bias. In this simulation, S-FULL, S-FIX, 10-EXPRESS, and ADA all exhibit a steady increase in median interval size. By contrast, EXPRESS-M gradually converges to the behavior of EXPRESS, which maintains the shortest intervals overall. However, it is important to note that EXPRESS incurs an increasing fraction of infinite intervals (as seen subplot (c)), which is not reflected by the median lengths. In contrast, EXPRESS-> M manages to avoid these infinite intervals while still preserving relatively short intervals, providing more practical alternative.
10

---

Published in Transactions on Machine Learning Research (07 /025)
b
S-EXX
250
FULL
S
10-EXPRESS (+)
0.35
EXPRESS
200
S-FULL
EXPRESS-M
callbration data
FCR
0.25
FULL
150
ADA
EXPRESS
(X)
0.15
EXPRESS (2)
10-EXPRESS
S-FIX
0
40
90
120
160
200
0
40
90
120
160
200
time
time
d
0.16
EXPRESS
(1)
FULL
0.14
0.70
0.32-
0.65
infinit length (%)
median length
0.60
S-FIX
S-FULL 10-DXPRESS
0.09
0.55
0.50
0.04
0.15
0.02
10 O-EXPRESS (?)
0.40
EXPRESS M (2)
EXPRESS
EXPRESS-M (+)
0
40
90
120
160
200
40
80
120
160
200
time
time
Figure 3: (a) FCR as a function of time T. The dashed black line represents the target level a = 0.4. We highlight provably correct methods (V). (b) Number of calibration data points used over time. Strategies accumulating more calibration data tend yicld shorter prediction intervals. (c) Fraction of prediction intervals of infinite length over time. A high fraction suggests strategy often fails to provide informative intervals. Only reported for novel strategies.
(d) Median prediction interval length time. Shorter intervals indicate higher informativeness. All metrics are averaged over N 11xxxx x 10 runs.
Overall, these results highlight the trade-offs in calibration selection strategies. Methods that strictly enforce exchangeability, such as EXPRESS, offer theoretical guarantees but at the cost of increasingly frequent infinite- length intervals. More flexible approaches like EXPRESS-M and 10-EXPRESS mitigate this issue by maintaining a larger calibration set while still controlling FCR. Notably, strategies that ignore selection bias, such as FULL, S-FULL, and ADA may appear reasonable in some cases but lack thcoretical guaranteos, making them unreliable in general.
In fact, even the conditional expectation of FCP given that at least selection is made,
(FC = FCP(T) Σ St o)
(12)
is controlled when using our proposed strategics. The above metric is called posétive FCR WWiisttein & Ramdas 2020), in analogy to the positive false discovery rate (FDR) (Storey) (003)..
Proposition 5.2. Strong
coverage implies that pFCR(T) I for any T 2 0. More- over, if strong selection-conditional coverage holds exactly, then pFCR(T) = Thus, calibration selection strategies [ or vii) guarantee that FCR(T) S for any T 2 0. If E. > 0 holds almost surely, then FCR(T) under the same exact coverage condition.
With similar arguments as for (strong) selection-con coniitionnn coverage, follows that the merging strategy also controls the FCR at user-defined target level.
11

---

Published in Transactions on Machine Learning Research (07 (07/2025)
6 Other Conformal Methods
Our discussion so far was only concerned about online selective conformal prediction algorithm in the sense of Section [ In principle, other conformal methods can also be applied to this problem. We first outline two of those: conformal LORD-CI (Weinstein & Ramdas 2020) and adaptive conformal inference (ACI) (Gibbs & Candes )021), and discuss (potential) use-casos of such algorithms. We give more details about these methods in Appendix C
We also note that related discussion can be found in Bao et al. 2024a). However, want to highlight crucial distinction: while Bao et al. (2024a) consider adaptive conformal inference algorithms to address scenarios where the exchangeabilic bibity of the underlying data itself is violated, our perspective differs. We argue that when the selection mechanism disrupts exchangeability between the test datum and the calibration data, this too constitutes a form distribution shift induced not by the mata-generating process itself, but by the selective nature of the inference procodure.
6.1 Conformal LORD-CI
The LORD-CI algorithm was originally proposed by Weinstein & Ramdas (2020). Let a (0, 1) be a measurele coverage level, then conformal prediction interval constructed
(x().) (u EY: R(X.,)) v) s - (0-a,((R))) ((R
(13)
The marginal level or is updated dynamically by maintaining the invariant
El ar Sa, for any T 0.
(14)
Ei= St
Any online protocol maintaining the invariant 14 is called (conformal) LORD-CT procedure.
Proposition 6.1. Any conformal LORD-CI procedure with calibration indices De = Jr ensures that FCR(T) S a for all T 20.
The constraint D. = Jofoft is critical, and causes the method to be conservative in practice. We are presently unsure if the result can be expanded to allow utilizing Jr
6.2 Adaptive Conformal Inference
widely used conformal prediction algorithm, particularly suited for scenarios where exchangeability is violated, such as online settings with distribution shifts. The ACI algorithm adjusts the miscoverage level based historical under- or over-coverage feedback. Specifically, for a target miscoverage level a, it updates a, according to
Adaptive conformal inference (ACI) (Gibss & Candes 2021
1(v-1 at a + ( 1 (((((--)))=1)))
where > > 0 is fixed step-size parameter. Here, (x,,,, 11) denoles the prediction interval constructed at time t --1 1 with nominal miscoverage level a:-1- This adaptive scheme increases a whenever the previous prediction interval fails to cover Y (indicating under-coverage) and decreases a₃ otherwise (indicating over-coverage). thereby steering the empirical miscoverage rate toward the specified target a.
Recently, Gibbs & Candès (2024) proposed an extension of ACI, termed AtACI, by employing an exponential re-weighting scheme estimate the parameter y. Another recent work in this regard is Angelopoulos et al. (2024b).
Proposition 6.2 (adapted, Gibbs & Candes 2021
For all T 2 0 have that
[C) al max - an) +
(15)
Σ, S.7
almost surely. Particularly, limr-zes FCR a.s.
12

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
b
3.0
0.5
ACI DEACI 50-EXPRESS (X)
median length
LORD-CI
FCR
0.3
ACI
0.1
1.0
DIAII
EXPRESS (A)
LORD-CI
0
300
600
900
1200
1500
300
600
900
1200
1500
Figure 4: (a) FCR as a function of time T. The dashed black line represents the target level a = 0.4. We highlight provably correct methods (V). (b) Median prediction interval length over time. Shorter intervals indicate higher informativeness. All metrics are averaged over N x 10 rums.
The proof of Proposition 6.2 follows directly from Gibbs & Candes 2021 Proposition 4.1). We also note that Bao et al. (2024a) established similar result for DtACI adapted to the selective setting.
Simulation 6.3. The setup is the same in Simulation 5.1 with the only difference that we choose here Not 200 and Non 1500. For t 2 0, the selection rule is again given by 11 where choose here To 1500 and T = 1.
Results. Figure g compares other conformal methods with online selective conformal prediction using the 50-EXPRESS strategy terms of FCR control and median prediction interval length over time.
Subplot (a) illustrates the FCR as lime progresses. ACT and DLACT gradually approach the nominal target as time increases albeit only asymptotically while LORD-CI strictly controls FCR for all T 0, but only in notably conservative manner.
Subplot (b) shows the median length of prediction intervals over time. Here, LORD-CT starts off with the largest intervals, mirroring its conservative nature in FCR control. Over time, however, all methods converge toward a similar interval size, suggesting that while they differ in short-term behavior, their long-term median interval lengths stabilize to comparable levels.
While LORD-CI offers finite-sample FCR control, does so at the cost of conservativeness. In contrast, adaptive approaches such as ACI and DiACI produce shorter intervals but only guarantee FCR control asymptotically.
As already noted by Bao et al. (2024a). ACI is particularly useful when the data is not exchangcable. While this often holds in online settings, this comes at the cost. of forgoing selection-comdiiional coverage guarantees and finite FCR control (since only asymptotic FCR control would be guaranteed) when the data is exchangeable. On the positive side, ACI can be applied directly without modification, making it convenient off the-shelf solution. However, this convenience comes at the expense of leveraging the exchangeability of the data (when this is the case), which could otherwise be exploited for stronger theoretical guarantees.
13

---

Published in Transactions on Machine Learning Research (07/ (025)
7 Other Related Work
As previously noted, our paper is closely related to [ao et al. (2024a) and Weinstein & Ramdas 2020). To the best of our knowledge, the literature on the online selective conformal inference is limited to these. We provide a brief discussion of other work, which are only related to our paper in a broader sense.
Traditional selective inference provides valid statistical inference after data-driven selection (e.g. model se- lection). These methods condition on the selection event to correct for "cherry--pcking" and avoid overstated significance. A prominent example is the exact post-selection inference framework for the Lasso by Lee et al. (2016). Such classical approaches, including Fithian et al. (2014), guarantee nominal Type I error given the selection, typically under parametric assumptions (e.g. Gaussian noise). However, they often require spe- cialized derivations for each procedure and may be limited in scope (e.g. specific to linear models). Recently, this motivated distribution--ee selective inference, where conformal prediction plays a key role. However, most of these works (discussed below) are in the offline setting.
A central idea is to create selection-aware conformal p-values or intervals that account for the fact that one only reports results selected instances or hypotheses. Several recent works implement this idea. [Jin & Candès (2023) introduced conformal p-values for identifying instances with large outcomes while controlling false discoveries. The method wraps around any predictive model to output p-values for each test instance that its outcome exceeds a specified threshold. By applying a Benjamini- Hochberg 1995) procedure to these p-values, one can select a subset of candidates and control the false discovery rate (FDR) in finite samples.
(BH) (Benjamini &
Bao ct al. 2024b) construct prediction intervals for selected individuals while controlling the FCR. They develop split-conformal procedure called SCOP (Selective COnditional conformal Predictions) that uses a held-out calibration set to mimic the selection on the test set. By performing the same selection on calibration data and constructing conformal intervals on those subsets, SCOP achieves exact FCR control under exchangeability. Notably, it improves interval efficiency: whereas a naive FCR adjustment (Benjamini & Yekutieli 2005) would inflate all intervals uniformly, SCOP yields narrower intervals in practice while still guaranteeing that a chosen proportion of the reported intervals covers the truth.
Wang al. 2025 tackle selection effects in multiple hypothesis testing powered by conformal prediction. They introduce a selective conformal p-value that adjusts for broad class of selection procedures (for instance, selecting top-scoring instances for testing). The key idea is to use a holdout set to simulate the selective distribution elfectively, recalibrating conformal p-values on data that underwent a similar selection rule. By adaptively choosing the calibration data based on the stability of the selection rule, they ensure the calibration set is exchangeable with the selected test point. This yields valid post-selection p-values which, when plugged into BH, control the FDR on the selected subset.
Another recent work, Bai & Jin 20244). addresses a practical challenge: how to perform model selection or tuning within a conformal inference procedure without invalidating the guarantees. Typically, if one uses the same data to choose a predictive model (or conformity score) and to calibrate prediction sets, the exchangeability needed for conformal validity can be broken. Existing solutions often demand data splitting or a fixed model choice independent calibration data. They provide a general framework for valid post-sclection inference even when models or scores are optimized on the data.
As mentioned earlier, all these above works are in the offline setting, and thus extending the above papers to the online setting seems ripe direction for future work.
8 Discussion
Our findings highlight that the choice of calibration strategy is crucial in ensuring key inferential guarantecs namely, selection-conddiionall coverage and FCR control. The theoretical results presented in this paper reveal that existing calibration selection strategies, such as the recently proposed adaptive strategy (ADA), do not necessarily preserve the exchangcability between the calibration set and the selected test datum. As result, they fail provide valid selection-conditione coverage guarantees in general. In contrast, the proposed family of exchangeabllityprrsery calibration selection strategies provides selection-conditional coverage.
14

---

Published in Transactions on Machine Learning Research (07 (07/2025)
There are several avenues for future research. First, there appears to be trade-off between strict theoretical guarantees (via exchangeability preservation) and practical efficiency (in terms of calibration set size and interval width). Investigating adaptive or hybrid selection strategies that balance these objectives (like K-EXPRESS or EXPRESS-M) is a promising direction. Second, while our analysis assumes decision driven selection rules, extending the framework to other (potentially more general) selection rules remains an important challenge. Third, empirical studies across diverse applications- such as medical docision-making and finance could provide insights into the real-world applicability of these methods.
Acknowledgments
The authors thank Margaux Zaffran for helpful comments. Yusuf Sale is supported by the DAAD program Konrad Zuse Schools of Excellence in Artificial Intelligence, sponsored by the Federal Ministry of Education and Research.
References
Anastasios N Angelopoulos, Rina. Foygel Barber, and Stephen Bates. Thcorctical foundations of conformal prediction. arXiv preprinl arXiv:441.11182, 2024a.
Anastasios Nikolas Angelopoulos, Rina Barber, and Stephen Bates. Online conformal prediction with de- caying step sizes. In International Conference Machine Learning, pp. 1616-1630. PMLR, 2024b.
Tian Bai and Ying Jin. Optimized conformal selection: Powerful selective inference after conformity score optimization. arXiv preprint 11. 1993, 2024.
Yajie Bao, Yuyang Huo, Haojie Ren, and Changliang Zou. CAP: A General Algorithm for Online Selective Conformal Prediction with FCR Control. arXiv preprint ar 2ix: (i.:2403.077288, 2024a.
Yajie Bao, Yuyang Huo, Haojie Ren, and Changliang Zou. Selective conformal inference with false coverage- statement rate control. Biometrika, 111(3))727-742, 2024b.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Conformal prediction beyond exchangeability. The Annals of Statisties, (2):8816 845, 2023.
Yoav Benjamini and Yosef Hochborg. Controlling the false discovery rate: a practical and powerful approach multiple testing. Journal of the Royal stotistical society: series B (Methodological)) 57(1):289 300, 1995.
Yoav Benjamini and Daniel Yekutieli. False discovery rale adjusted multiple confidence intervals for selected parameters. Journal of the American Statistical Association, 100(469):71-8)) 2005.
Carlo Bonferroni. Teoria statistica delle classi calcolo delle probabilita. Pubblicazioni del R istituto superiore di science economiche e commericiali di firenze, 8:3 62, 1936.
William Fithian, Dennis Sun, and Jonathan Taylor. Optimal inference after model selection. arXie preprinl arXiv:1410. 2597, 2014.
Isaac Gibbs and Emmanuel Candes. Adaptive conformal inference under distribution shift. Advances in Newral Information Processing Systems, 34:1660-1672, 2021.
Isaac Gibbs and Emmanuel J Candès. Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research, 25(162):1-36 36, 2024.
Ying Jin and Emmanuel J Candès. Selection by prediction with conformal p-values. Journal of Machine Learning Research, 242244):1-41, 2023.
Jason D. Lee, Dennis L. Sun, Yuckai Sun, and Jonathan E. Taylor. Exact post-selection inference, with application to the lasso. The Annals of Statistics, 44(3):907 927, 2016.
15

---

Published in Transactions on Machine Learning Research (07/2025)
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution-fres predictive inference for regression. Journal of the American Statistical Associalion, 11366233:1094-1111, 2018.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence chines for regrossion. In 13th European Conference Machine Learning, pp. 345-356. Springer, 2002.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Advances in
Neurul Information Processing Systems, 32, 2019.
John D Storey. The positive false discovery rate: a bayesian interpretation and the q-value. The Annals of Statistics, 31(6):2013 2035, 2003.
Ryan J Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal prediction under covariate shift. Advances in nearal information processing systems, 32, 2019.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorillmicc learning a random world, vol- ume 29, Springer, 2005.
Xiaoning Wang, Yuyang Huo, Liuhua Peng, and Changliang Zou. Conformalized multiple testing after data-dependent selection. Advances in Neural Information Processing Systems, 37:58574 -7669,, 2025.
Asaf Weinstein and Aaditya Ramdas. Online control of the false coverage rate and false sign rate. In International Conference on Machine Learning, pp. 10193-10202. PMLR, 2020.
16

---

Published in Transactions on Machine Learning Research (07 (025)
A Preliminaries
For completeness, we provide basic results quantile and related concepts, which are already well- documented in the conformal prediction literature (Vovk et al. 2005 Lei et al. 2018 Romano et al. 2019
Barber et al. 2023 For a comprehensive overview of the theoretical foundations of conformal prediction, see Angelopoulos et al. (2024a).
Let Z be random variable with cumulative distribution function (cdf) Fz. The quantile function Q(a) is defined the (generalized) inverse of Fz, for E (0, 1). Formally,
Q(a) (a) E F2(=) 2 a).
Equivalently, ((a) is the smallest real number such that Fz(z) 2 Now suppose have sample Zi.... Zn drawn from the distribution of Z. The empirical edf F, is defined by
1 Σ 12 n
(=)
where ( denotes the indicator function. Then the empirical quantile function Qn (ax) is given the inverse of Fx:
inf(2 R: Pn(2) a).
More explicitly, if we denote the order statistics by Z(1) S Z(2) S ... S Z(n), then
@m(a) Z (Inal)'
where [na] is the ceiling of na.
Lemma A.1 (Quantile lemma). Let ......,
, 7n be exchangeable random variables. Then, for any a E (0, 1)
P(Zn < Qn(a)) 2 a.
Additionally, if the random variables Zi...., Zn are almost surely distinct, then
P(Z, < (a)) sat
Lemma A.2 (Quantile inflation). Let Zi.... Znt1 be exchangeable random variables. Then, for any a e
1)
P(Z, & (11 1/n)a)) 2 a. Additionally, if the random voriables Zi,... Zo+1 are almost surely distinct, then
PPnn (n 1//)o)) S n+1
17

---

Published in Transactions on Machine Learning Research (07 (07/2025)
B
Omitted Proofs
The proof of Theorem 4.5 follows from Lemma 4.4 and classical conformal arguments (see in particular Angelopoulos et al. (2024a and references therein).
Lemma B.1. Let the selection procedure be instanliated with stralegy
Them, {Zi) are
ezchangeable conditional on the event that So = , St-1 = St-1, where (So..... St-1) E {0, (0.1)--
Proof. Let (80....,8:-) 81-1) E [0,1)--1 and D any set of indices. Further, denote by & the event that Zi) = D and So = so...., S St-1, and assume P(E) > O. For any measurable A C (X' x D1 let (=-m...., m) E (X' x y) (Z))iE E A, Iz(z-ng...,,a 2)) = D, Sy(Ø;) = 8j. 0 0sist-13 Thus, f(2-.....,22)
Z,) E B) = {(2)) E A, E). By Lemma 4.4 both Σ(.) and S,(-) are
permutation invariant, for $ jt-tt11 This yiclds [Z-...... .2) E B} {(Zz( ((-))).... 22()) E B) and with that
Ze) E B) P ((Z))ED E A, =
= (Z Zi(e)) E B
= =P((Z(())EED A, E)
where the second equality follows from exchangeability {2:);=1.
Lemma B.2. Let the selection procedure be instantiated with strategy {0, 10-- If we have P(Su- Su..... S = St-1, St = 1) > 0, then
or vi and (so....,
Σ Σjed. 1 2 Rd}
Pō.
(16)
[D#
S = 84 = S for any E [0, is valid p-ualue, ie.,, P(Ps, S Sa s
Proof. Let & denote the event that E D. = (z .Z........ Ze), which by 4 is equal to the event that S₁ 1, and So so...., S.-1 8t-1, for (So,..., 8t-1) ) {0, 10
Conditional &,, the non-conformity scores
{R) are exchangeable. This implies that
Σ jeD 1[ 2 R₂} P5.
(17)
[D,
is a valid p-value, i.e. P (ps, S a E.) s a, implying that P (ps, Sa = ,o...., = St-1, = 1) s
Proof of Theorem 4-5 Since we have Y, E (..))) = Pb. by construction and classical conformal
arguments, the strong selection-conddiionaal coverage guarantec follows by Lemma B.2
18

---

Published in Transactions on Machine Learning Research (07 (225))
The proofs of Proposition 5.2 and Proposition 6.1 adapted from Theorem and Theorem 5 in Weinstein respectively, with modifications to align with the conformal framework.
& Ramdas 2020
8T) E {0, 10,1)-1 be any sequence, such that E, > 0. Now, assume that P Y E Cx,),) So 80, 80......
Proof of Proposition 5.2 First, let
, St-1 1, = 1 2 1 - for any 2 0. Then,
T -
S.1 & C((x))
E
So -., ST
Σj=0 Sj
E
Σ
(
So :....., Sr ST
Σj=0 8j
E
Σ
1(6 & C((X)) So .u....,,p" Sp ST
Σj=0 8j
1ST::m1
Σ P(x, (x.)))
So = =0.- -8 = =88
Σj=o$ Ej (STie
(2)
P x So = 80, so,..,, S =
S, St
Σj- 9j 1sTs
Σラ= 8j 15T:==1
=0
where (a) follows since given (So...., S₁) the selection decisions (S.+ ST) are independent of {Yr & (X))). Inequality (b) follows from strong celection-condition. coverage. Now, taking the expectation over the conditional distribution of SI....,yy ST given E, S; > 0 yields
(TC =E E S,1YY, & C((x5aae) Σ >0 sa
Σ/=0 S
With that
VL S,1YY, & (x(x;:0))
Σs .P ($S>))
FCR(T) E
Σ/ Sj
Σr SiT(Y, & (((x;a0))
|Es
E
Ej
aa
Thus, FCR(T) S a. Clearly, if (a) holds with equality, then pFCR(T) = a. Additionally, if P(, S,> 1, then FCR(T) a. This completes the proof.
19

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Let T 2 0 and {5 1520 be sequence of selection decisions {S,);20, where we Proof of Proposilion 6.1
set St = 1 deterministically. Now, define J o S4 ST) Then, we have
T Σ E
S.A(Y, & (((x:a)))
FCR(T) 1=0
1V
(Y, & ((((i)))
E
1=U
(0)
(Y2 & (():)))))
Sj S
1=0
T
11,, & (((xiaai)) smn]]
E
E
ビi=0 s(0)
1=0
T
E [[ > (
E
Σ j=0 s(t)
Ot
E
Σ == }
s(()
1=0
a22
E
Σラ S3
0
Here (a) follows since S, s 1, and (b) since is Feer-ueaerralle, we have for a fixed as E (0, that E LiRe > Q1-a, ((Bbee)))) F = [ > ( ((RA)ED))) Finally, (c) is due to the monotonic-
ity of the selection rules and the last inequality (d) follows from the invariant 14
20

---

Published in Transactions on Machine Learning Research (07 (07/2025)
C
Other Conformal Methods
C.1
LORD-CI
For completeness, we provide a brief overview of the LORD-CI algorithm in this section, slightly altered from its original presentation for confidence sets to fit the conformal framework. The algorithm was initially proposed by Weinstein Ramdas (2020), to which we refer for a more comprehensive treatment. Let a E (0, 1) be Fi-mcasurable coverage level, then a conformal prediction interval constructod
(x,),) (v ey: R(X.,)) v) s
The marginal level or is updated dynamically by maintaining the invariant
Ei at S a. for any T O. Σi St
Algorithm 1 is an explicil instantiation of LORD-CI, which maintains the above invariant. Initially, before any selection, the algorithm only has the small budget Wo E (0, to spend (spread out over time by 7)). Once the first interval is reported, the algorithm gains an additional "crror wealth" of size (a- Wo) After the first selection, any future time point t gets an increment of (a - Wohn, in its threshold. Similarly, every subsequent selection contributes an additional a distributed over future times. Thus, by time 4, a is the sum of contributions from the initial budget and all past selections' budgets allocated time t. This mechanism selection occurs, future a-levels increase
guarantecs that a is non-decreasing over time whenever stay the same.
Algorithm LORD-CI procedure (Weinstein & Ramdas 2020 modified)
offline data Tof;; sequence {Z₂} observed sequentially; deterministic sequence {*} summing to one; constant Wo E (0, a)); selection rules (S:); E 10
Input:
2: Output: online FCR-adjusted selective prediction intervals
3: 1+1
4: for j 1;==,,,,, 1,2,... do while S,(X,) do 1+(+1
end while
Tj t
at
+ 7 + (a- Woh-- + E 7h
> Monotone update rule
10: Report C((x,) = (v E y: R(X..v) S Q1-ai (f
11:
1+1+1
12: end for
C.2 Adaptive Conformal Inference
The ACI algorithm Gibbs & Candes 2021 adjusts the miscoverage level based on historical under- or over-coverage feedback. Specifically, for a target miscoverage level a, the algorithm updates a according
at = o a +7 1(Y-1 (((()-1,)-1)))
where 7 > 0 is fixed step-size parameter. Here, (X,xx1,,041 denotes the prediction interval constructed at time f --1 with nominal miscoverage level 04-1- We note that, the performance of ACT heavily rolics on a well-specified step-size parameter. Gibbs & Candes (2021) recommend that the step-size should be chosen proportionally to the underlying rate change in the environment, which is unknown in practice.
21

---

Published in Transactions on Machine Learning Research (07 (02))
D Additional Simulations
We provide additional simulation results to complement those presented in the main part of the paper. First, we recall the following (decision driven) selection rules:
Selection rule (A)
Selection rule (B)
Selection rule (C)
1 E S: for js--1
1-1 S
71
x> min
1 E/
S m for =t
70
70 1=0
1=0
We evaluate several calibration selection strategies for online selective conformal prediction, which were discussed earlier. The aim is to generate prediction intervals for a test point based on previously selected calibration points, while ensuring valid accumulate metrics, such as miscoverage and calibration set size. In each iteration of the simulation, a data set of size N Not + Non. where Not = Tooff and Non -e,n is generated. The generated data serve potential I-calibration data.
coverage. We conduct Monte Carlo simulations
In the simulations that follow, we generate X Unif(O, 2), and Y = =x(X + e, where v(X) = XB. Addi- tionally, we assume El X ~ (O0 X/22.
D.1 Condition Coverage
Rule (B)
Rule (C)
X
0.40
0.35
X
0.30
0.0000
0.000
0.000
0.000
0.139
0.037
0.053
0.000
0.000
0.000
0.000
0.139
0.037
0.053
0.719
0.594
0.573
0.543
0.413
0.553
0.536
0.730
0.930
0.935
0.975
1.202
1 4.46
020
30.000
8.057
23.898
19.033
8.637
B.847
9.585
30.000
8.060
23.897
19.028
6.624
8.842
8.585
0.25
FULL
S-FIX
S-FULL
ADA
EXPRESS Iburst//
EXPRESS-M (ours)/
5-EXPRESS
FULL
S-Fix
S-FULL
ADA
EXPRESS toursi/
EXPRESS-M (cunsi/
5-EXPRESS
tourst/
tourst/
Figure 5: Miscoverage (x) is shown alongside the number of calibration points (m), median interval length (m) and the fraction of infinite length prediction intervals and the target level (--). All metrics are averaged over
We highlight provably correct methods (V)
10 runs.
Simulation D.I. We set Nott 10 and No. 20. We perform two separate simulations, using rule (B) and the other using rule (C), We then perform online selective conformal prediction with both existing and novel strategies. All reported metries are averaged over N = 1 x 10 runs.
22

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
b
0.6
0.5
0.5
FULL
ADA
Miscoveragy
0.4
EXPRESS S-FIX 10-EXPRESS S-FULL
3 SSS
Miscoverage
0.4
EXPRESS S 10-EXPRESS
S-FULL
EXPRESS-M
ADA
0.3
FULL
0.3
EXPRESS-M
0.2
0.2
0.1
0.1
0
40
80
120
160
200
40
80
120
160
200
Figure 6: Miscoverage over time. The dashed black line represents the target level a 0.4. We highlight provably correct methods (V). (a) Miscoverage for selection rule (B). (b) Miscoverage for selection rule (C). Averaged over N = 10* runs.
Simulation D.2. We set Not 50 and No 200. We run two separate simulations, one using rule (B) and the other using rule (C). We then perform online selective conformal prodiction with both existing and novel strategies. At each time T report the miscoverage, averaged over N 11x 10a runs.
23

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
D.2
FCR Control
250
FULL
FULL
200
S-FULL
0.5
callbration data
FCR
150
ADA
10-EXPRESS
121
EXPRESS
5-FULLL
ADA
100
0.3
EXPRESS-M 1/]
EXPRESS
EXPRESS-M
10.EXPRESS
S-FIX
0
40
80
120
160
200
120
160
200
time
time T
0.16
EXPRESS
1.
infinite length 1%6
0.12
1.6
median length
0.10
144
0.08
EXPRESS-M (2)
0.06
1.2
EXPRESS
10
EXPEXSSSSS
0.02
10EEXPESSS
0.8
0.00
EXPRESS-M
90 120
160
200
time
time T
Figure 7: (a) FCR as function of time T. The dashed black line represents the target level a 0.4. We highlight provably correct methods (V). (b) Number of calibration data points used over time. Strategics accumulating more calibration data tend to yield shorter prediction intervals. (c) Fraction of prediction intervals of infinite length over time. A high fraction suggests a strategy often fails to provide informative intervals. Only reported for novel strategics.
(d) Modian prediction interval length over time. Shorter intervals indicate higher informativeness. All metrics are averaged over x 10 runs.
Simulation D.3. We set Norr 50 and No. = 200. Here, we use selection rule (C). We then perform online selective conformal prediction with both existing and novel strategies.
24

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
b
50-EXPRESS ACI
3.0
0.35
0.30
0.25
median length
2.0
RCR
0.35
LORD-CI
1.5
0.10
LORD-CI
0.5
DLACI
0.00
ACI
300
600
900
1290
1500
360
600
900
1200
1500
time
time
Figure 8: (a) FCR as function of time T. The dashed black line represents the target level = 0.4. We highlight provably correct methods (V). (b) Median prediction interval length over time. Shorter intervals indicate higher informaliveness. All metrics are averuged over N = x 10a runs.
Simulation D.4. We Noff 200 and Non 1500. Here, we use selection rule (C). We compare online selective conformal prediction with 50-EXPRESS strategy, ACI algorithms and LORD-CI.
25


Reviews:
[{"review_id": "bqo5nldTyd", "reviewer": "Reviewer_EKuR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- This is a strong paper from a theoretical point of view. The results are strong and extensive. The authors carefully study the properties of 6 selection rules in online conformal prediction, highlighting which of them guarantee \"symmetry\" (a property they show is crucial to the problem at hand) and hence lead to selection-conditional coverage.\n- The message is clean: many of the existing selection techniques do not provide the desired coverage guarantees. In turn, part of the contribution of this work is also to introduce and develop novel selection strategies, on top of proving their properties. \n- There are additional results in Section 5 that also study when a weaker notion of FCR control is satisfied, so the picture given by the paper is fairly complete.\n- This is, to me, an especially important paper to accept because it corrects misconceptions and mistakes from previous work, and in that sense should prove to be an impactful paper to the conformal prediction community.\n\nWeakness: \n- This is mostly a theory paper so I think this is not too much of an issue here, since the experiments seem to mostly be illustrative, but I did find the experimental results weak in places. The setups of simulations 4.1 and 5.1 feels very specific and a bit arbitrary.\n\nTo me, this is a clear accept. I do want to note that my review is medium confidence, as, while I am familiar with conformal prediction, this is not my primary area of research.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies online conformal inference in settings where there is a selection process---i.e., predictions are only given for selected time steps. This selection process can break the exchangeability property that is crucial to conformal prediction and to ensure that prediction intervals are valid conditional on the selection process. \n\nThe work studies how to select calibration data be chosen to ensure exchangeability and they discuss/evaluate six main calibration selection strategies.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "N/A", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BjawTIy3Ew", "reviewer": "Reviewer_8mFZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This paper clearly identifies one sufficient (yet not necessary) condition for the exchangeability to hold under online selective conformal prediction. It also points out the missing part ignored by current works.\n\n2. This paper proposes one algorithm (EXPRESS) and two practical variants that achieve the exchangeability.\n\n3. The authors show the connection to a broader family of online conformal prediction algorithms in Section 6.\n\nWeaknesses:\n\n1. The assumption A is too strong. Only considering the decision rules purely dependent on the online data limits the applicability.\n\n2. The sufficient condition for exchangeability is too restrictive. The practical value of the proposed algorithms is somewhat limited due to a non-zero fraction of infinite-length prediction intervals. The simulation results only focus on the median of the length rather than the mean of the length, further verifying that point.\n\n3. The empirical evidence is purely synthetic.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of online conformal prediction under the online selection rule. The prediction intervals need to be correct for the selected data, while the online selection may break the exchangeability between the test datum and the rest. This paper points out that the exchangeability is actually violated in existing strategies and proposes a sufficient condition for exchangeability. The authors also provide an algorithm (EXPRESS) and its variants that satisfy this condition and verify its effectiveness via simulation.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Can you provide some more discussions on Assumption A? I don't quite see why it doesn't hurt the applicability of your algorithms. What if the assumption is violated? Is this assumption necessary for online selective conformal prediction?\n\n2. Can you provide some more numerical experiments? For example, on real data, or based on some other selection rules than (11).\n\n3. Can you provide a little more explanation on EXPRESS-M at the end of Section 3? I'm still confused about how you merge S-FIX and EXPRESS. The fractions don't add up to 1.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Yr8iLC24N4", "reviewer": "Reviewer_rVzn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n- The paper is well-written and, with the addition of the information in the appendix, relatively easy to follow. There is a clear presentation of key results.\n- The setup of the synthetic examples is simple enough for an interested reader to reproduce. \n- Good theoretical results tying intricacies of the various calibration strategies with coverage guarantees, with a good mix of positive and negative results. \n- The buildup from EXPRESS, to K-EXPRESS, and then EXPRESS-M helps to understand what each method brings to the table (which can also be seen in the toy examples).\n\n\n## Weaknesses\n\n- I think readers would have appreciated a realistic example  (like in the work by Bao[^1], et al., 2024) to highlight any other difficulties that are not seen in the synthetic examples. \n\n[^1]: Bao, Y., Huo, Y., Ren, H. and Zou, C., 2024. Cap: A general algorithm for online selective conformal prediction with fcr control. _arXiv preprint arXiv:2403.07728_.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This is a work on conformal prediction in which the authors review a few different calibration selection strategies in the setting where data arrives in an online fashion and for which there is a requirement that  \n\n$$\n\\forall t\\geq 0:\\ P(Y_t\\in \\hat{C}_t(X_t)|S_t=1)\\geq 1-\\alpha,\n$$\n\nwhere $S_t$ is a particular selection rule and $\\hat{C}$ are the prediction intervals. \n\nThe authors show that three particular calibration strategies either violate exchangeability or are too stringent in doing so in the setting discussed. The authors also propose a series of calibration strategies, called EXPRESS, K-EXPRESS, and EXPRESS-M (“M” for “merge”, as the authors merge intervals from EXPRESS and S-FIX), that have varying degrees of stringiness and performance in terms of number of calibration points needed, size of intervals, percentage of unbounded intervals, etc. \n\nAll methods are compared in terms of synthetic toy experiments that showcase various metrics, e.g., miscoverage, interval length, etc. The authors provide theoretical results for when some strategies do not satisfy symmetry, as well as when they do (including guarantees on the false coverage rate).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Requested Changes\n\nSome minor suggestions to strengthen presentation; they are not necessary for recommendation. \n\n- Perhaps because of inexperience with the online setting, I didn’t immediately understand where $S_i$ come from in the synthetic examples (examples of selection rules are provided as a function of the selections $S_i$, but how selections are constructed, e.g., in the experiments, is left implicit for the reader at the moment). This may be standard in conformal prediction, but a sentence or two on may help readers. \n- Typo: Above Equation (8), “Consequently, *display* (7)” → “Consequently, Equation (7)”.\n- Although I enjoyed the miscoverage plots, I wonder if there's a more visual way to compare the methods, e.g., a parallel coordinates plot.", "broader_impact_concerns": "NA.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)