Practical Adversarial Multivalid Conformal Prediction
Authors: Osbert Bastani
Varun Gupta
Christopher Jung
Georgy Noarov
Ramya Ramalingam
Aaron Roth
Venue: NeurIPS 2022 Accept (2022)

Abstract: We give a simple, generic conformal prediction method for sequential prediction that achieves target empirical coverage guarantees on adversarial data. It is computationally lightweight --- comparable to split conformal prediction --- but does not require having a held-out validation set, and so all data can be used for training models from which to derive a conformal score. Furthermore, it gives stronger than marginal coverage guarantees in two ways. First, it gives threshold-calibrated prediction sets that have correct empirical coverage even conditional on the threshold used to form the prediction set from the conformal score. Second, the user can specify an arbitrary collection of subsets of the feature space --- possibly intersecting --- and the coverage guarantees will also hold conditional on membership in each of these subsets. We call our algorithm MVP, short for MultiValid Prediction. We give both theory and an extensive set of empirical evaluations. 

Practical Adversarial Multivalid Conformal Prediction
Osbert Bastani', Varun Gupta', Christopher Jung'.
Georgy Noarov', Ramya Ramalingam' Aaron Roth
University of Pennsylvania, Stanford University
fobastani, vgup, gnoarov, ramya23, aaroth)@seas, upenn. edu, caj930atanford.
Abstract
We give simple, generic conformal prediction method for sequential prediction that achieves target empirical coverage guarantees on adversarial data. It is com- putationally lightweight comparable split conformal prediction but does not require having a held-out validation set, and so all data can be used for training models from which to derive a conformal score. Furthermore, gives stronger than marginal coverage guarantees in two ways. First, it gives threshold calibrated prediction sets that have correct empirical coverage even conditional on the thresh- old used to form the prediction set from the conformal score. Second, the user can specify an arbitrary collection of subsets of the feature space - possibly intersect- ing and the coverage guarantees will also hold conditional on membership in each of these subsets. We call our algorithm MVP, short for Valid Prediction. We give both theory and an extensive set of empirical evaluations
Introduction
Consider the problem of predicting labels y ) given examples X. One popular strategy for expressing uncertainty is to allow the algorithm to produce a prediction set T C y rather than an individual label. We give simple, practical algorithm for constructing prediction sets in sequential prediction problems over an arbitrary domain X' x ),, given any data-dependent sequence conformal score functions s, X x Y - Rgo- In each round t, an example represented by feature vector t E X arrives. We can define an arbitrary conformal score St X x y - R20 that can depend on previously observed examples (as well on f' in arbitrary ways. We produce round-dependent threshold Ct. which gives us a prediction set T {y E ) 8e y) S )e We then observe the true label Mr we say our prediction set covers Yr yt E St. Given a coverage target
6, our goal is to produce sets that have correct empirical coverage - i.c. that cover a 1 8 fraction of the labels (we do not want either over-coverage or under-coverage). We wish make as few assumptions as possible, so that our method is robust to arbitrary and unanticipated distribution shift, and applies to e.g. time series data which are very far from exchangeable. We also want our coverage guarantees to be meaningful not just marginally, but at finer granularities: conditional on both the threshold value we choose, and on membership of 2t G for set of groups G E 9 C 2 that can be arbitrarily defined and intersecting. Finally, we want our algorithm to have low computational overhead, so that it can be applied as a wrapper on top of arbitrary prediction methods, for both regression and classification. The algorithm we propose achieves these goals and has several desirable properties:
Worst-Case Empirical Coverage: Our method has worst case adversarial guarantees. The sequence of examples {2x, Mr) ) needs not be drawn from an exchangeable distribution as it does for standard conformal prediction methods (Shafer and Vovk 2008 instead, it can be chosen by an adaptive adversary. The conformal scores 8, can be arbitrary and can depend on data from
Code replicate our experiments be found at http://ggiiiiicooooorpeeeaaaaaar
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

previous rounds (e.g. they can be derived from models trained on all past data, and so there is no need to separate data into training and calibration sets as in split conformal prediction [Lei et al. 2018)). Thus, our method can tolerate time series data, and arbitrary and unanticipated distribution shifts.
Calibrated, Multivalid Coverage: Our prediction sets obtain their target empirical coverage level not just marginally, but in a 1 - 8 coverage on the subsequence of rounds t on which the threshold dr = L We also promise group-conditional coverage. We can specify an arbitrary collection of groups g. each group G e g representing arbitrary Seature-space subset: G C X. These groups can intersect in arbitrary ways. For example, 9 can be a collection of demographic groups based on race, age, income, or medical history, and each data point X could represent member of an arbitrary subset of these groups. Our method promises that simultaneously for every group G E G, on the subsequence of rounds for which Fe E G, our intervals obtain the target empirical coverage rate (again, in calibrated fashion).
fashion: for every threshold g. they approach
Computationally Lightweight: Our method is computationally lightweight. At each round t. relies on simple arithmetic calculations involving the historical empirical coverage rates of finitely many candidate thresholds 4 on groups such that de E G. Hence it is comparable in cost to fast split conformal prediction methods (Lei et al., [0188] despite its ability to use all data for model training. We give an implementation of our algorithm and an extensive empirical evaluation. By contrast, prior work by Gupta et al. (2022) that gets comparable theoretical guarantees (in the special case of regression prediction intervals) does not give a practical algorithm: their approach uses the Ellipsoid method with separation oracle to solve exponentially-sizer linear programs at all rounds.
Nearly Statistically Optimal Rates: For each threshold q and group G, we promise 1 1- empirical
coverage over the rounds I. where v; E G and the predicted threshold gr = q. Let n G. denote the total number of such rounds. Even if the labels y/ were drawn from known distribution and
coverage probability was exactly 1 1 5, we would expect our empirical coverage on these n G. rounds to deviate from 1 - 8 by 11/vnG. term. The prior theoretical coverage guarantees for each and G of Gupta et al. [2022] differ from their target by
which is nearly optimal if Gaa 2 22(7") but sub-optimal otherwise. Our algorithm promises empirical coverage rates for each pair (G, q) that differ from the target by an optimal Ö(1/VnG.)) term.
We give an extensive experimental evaluation of our algorithm in a number of settings, and compare to vanilla split conformal prediction [Lei et al., 2018). as well as prior work that handles limited forms of known distribution shift (Tibshirani et al. [019], , produces conservative groupwise coverage [Foygel Barber et al., 2020), and gives adversarial (but uncalibrated) coverage guarantees [Gibbs and [andes|[021] In each setting, we show that our algorithm is competitive with previous work "on th (i.c. in settings for which their assumptions are satisfied and we use their evaluation metrics). We then go on to show that our method gives substantial improvements when either the setting the evaluation metric becomes more difficult- - e.g. when the distribution shift is unanticipated, when we measure group-wise rather than just marginal coverage, or when the data comes in adversarial ordering. In some cases we improve on standard techniques even in standard "benign" settings: for example, improve on split conformal prediction in online linear regression setting with iid. data when the evaluation metric is just marginal coverage, but the regression function has to be learned from the same stream of data used to calibrate the prediction intervals. This is because split conformal prediction requires using separate splits of the data for training the regression and calibrating the prediction intervals to maintain exchangeability of the conformal scores but are able to use all of the data for both tasks.
their tur!"
CCalibration is especially important in a distribution free setting, when coverage is measured empirically. If we only asked for the target marginal empirical coverage as Gibbs and Candes (202T) do, rather than for threshold-calibratee prediction sets, one could obtain the right coverage rate by "cheating" the following uninformative way: predict the full label set S. = y on a ô fraction of rounds (guaranteeing coverage), and the empty set St = 0 on the remaining ö fraction of rounds (guaranteeing miscoverage of the label). This obtains empirical coverage rate 1 8 + O(1/T') marginally, but not conditional on the prediction sets chosen.
2

---

1.1 Additional Related Work
See Angelopoulos and Bates [021] for an excellent recent survey of conformal prediction methods. The weaknesses of these methods that we seek to address namely, that in the worst case they provide only marginal coverage, and that they rely on strong distributional assumptions (typically exchangeability) have been noted before. For example, |Roaano al. [2020a] note that marginal coverage guarantees are undesirable and give group conditional guarantees for disjoint groups by calibrating separately each group. This fails when the groups can intersect. |Foyeel Barber jet al. 2020] provide guarantees that are valid conditional on membership in intersecting subgroups G. They take conservative approach, by computing prediction sets separately for each group and then taking the union of all these sets over the groups of a new individual. As result, their prediction sets are conservative and do not approach the target coverage level. These results both require exchangeable data. Chernozbukov et al.] (2018) obtain approximate marginal coverage guarantees for exchangnaeeee time series data coming from rapidly mixing process. [Gendler et al. [202]] study conformal prediction for ad adversarially perturbed data: they assume that the dataset drawn exchangeably. but the test examples additionally have their features perturbed by small-norm adversarial noise. Their techniques are different from ours, and leverage the fact that the underlying distribution (except for the perturbations) is exchangeable, which we do not require. [Tibshirani et al.) [2019] study conformal prediction under covariate shift. They adapt conformal techniques to handle the case when both the point of distribution shift and the likelihood ratio between the training and test distribution are known. Gibbs and Candes [222] give method that can guarantee target marginal coverage without any assumptions on the data generating process. In contrast, our prediction sets promise not just marginal coverage, but are
and hold also conditional on membership in arbitrary sub-groups. Further notions of conditional coverage different from ours have been studied before in the batch setting, for instance training-, object-, and label- conditional 2022 for details.
guarantees; see e.g. Vovk [2012]. Bian and Barber
Following a recent resurgence in interest in conformal techniques, number of papers have proposed conformal scores that have desirable properties [Hofi] [021] [ooman al.] 2019 Angelopoulos et al. 2020 Romano et al.) 2020b) Park et al. 2019]. Our work is complementary to this line of work: just like traditional methods conformal prediction, we too take as input arbitrary conformal scores. Thus we can adopt any of these conformal score functions and inherit their properties, while providing the stronger worst-case guarantees of multivalid coverage.
For the special case of prediction intervals, the type of multi-valid prediction that we study was first defined in Dung et al. [202T]. who gave a way of obtaining in the batch setting for i.i.d. data, via producing multicalibrated estimates of label variances and higher moments. Gupta et al. [022] proved that there exists an online prediction algorithm that gives the sort of multi-valid prediction intervals that we consider in this work. The algorithm we give in this paper is both much more efficient (theirs was not implementable) and has substantially better (optimal) convergence bounds.
Finally, multivalidity is related to subgroup faimess constraints [Kearns et al.) 2018 2019 Kim et al., 2018). which ask for statistical "fairness" constraints to hold across all subgroups defined by some rich class G. In particular, it is closely related to multicalibration [Hébert-Johnson et al. 2018).
2 Setting and Notation
We let X' denote a feature domain and Y' label domain. g C 2%x denotes a collection of subsets of X, which we call "groups". For x E X. (zx) = {G E g x G} is the set of groups that contain x. For any integer T > 0, [T] (1. T}.
The probability simplex over a finite set is denoted AA.
Our online uncertainty quantification is based on a bounded conformal score function 8; X'x - TR. which can change in arbitrary ways between rounds 1 [T). Without loss of generality, we assume that the scoring function takes values in the unit interval: (2. y) E [0, 1] for any x E X', y E y. and E [T]. Fix some target coverage rate 1 1- 8. Ideally, the learner wants produce prediction sets (xx = {y E y Sx y) < } that cover the true label y with probability 1 - ô over the randomness of the unknown label distribution: Pryle, E Te(xa)] s 1 8. This is equivalent to choosing conformity threshold o such that Prylz, (9 v) S q:) R 1 5.
We want to model an adversary that can choose an arbitrary sequence of examples s, and labels yt- However, because the adversary may choose the label distribution with knowledge of the conformal
3

---

score function, we will elide the particulars of the conformal score function and the distribution on labels y/ in our derivation, and instead equivalently imagine the adversary as directly choosing z, and a distribution over conformal scores conditional on 2 (representing the distribution over conformal scores 8y (Tt, )). We may thus without loss view the interaction in the following simplified form:
1. The adversary chooses joint distribution over feature vector 2e X' and conformal score 8t E [0, 1]. The learner receives 2, (a realized feature vector), but no information about st-
2. The learner produces a conformity threshold qt-
3. The learner observes the realized conformal score 8t-
As we formally discuss in Definition 3.1 of Section below, the adversary's 's choice of the joint distribution over 2, and st in each round of the above protocol will need to additionally satisfy a mild smoothness property, namely that the score distribution should not be overly concentrated on any subinterval of the (0, 1] range. As we explain there, we can fact enforce this property algorithmically if necessary, by slightly perturbing the observed scores.
For any round [7], write n, (æe; Sex 9e) to denote the realized outcomes in round and Tt;tt for the transcript of the interaction in rounds t S t2: tt ((z,, S,, )=)); To denote a concatenation of two transcripts, we use @: for example, Th# 11#-1 + тr. We write
IT" (X' (0, 1] [0, 1))* as the domain of all transcripts. Fixing learner and adversary induces a probability distribution over transcripts. Our goal is to derive algorithms with coverage guarantees that hold over the transcript randomness, in the worst-case over all possible adversaries.
Given conformity threshold g, we say it covers conformal score 8 if Cover(g, 8) 1, where we define: Cover(q, 8) I[s S q]. To define threshold calibration, we bucket our thresholds using discretization parameter m. For any mi we write B., (i) = ['m] m for each bucket index i [m 1]. and B,, (m)
m--1 1], so that these buckets evenly partition the unit interval [0, i For any group G E G and bucket E [ra]]. we write GT(i) {l [T] Ie E G, Bi) for the set of rounds in the transcript .:. which the feature vectors belonged to the group G and the chosen threshold q was in bucket i.
We can now define our main objective this paper: threshold calibrated multivalid coverage.
Definition 2.1 (Threshold Calibrated Multivalid Coverage). Fix coverage larget 1 - 5 and collection of groups 9 C 2 Given transcript TT.,, sequence of conformity thresholds (4e Tm is said to be (a, mulltvvial with respect to ō and 9 for some function N R if:
Σ (EGr())
(Cover (4t, st) - (1 - [1-))]] (I))
for every i E [m]] and G E G.
Gr((
Note that multivalid coverage is defined by a function a(-) of the length the sequence on which empirical coverage is computed, letting us give fine-graines bounds that scale with the sequence length. In this paper we use the following family of functions, parameterized by a constant e > O:
f(m) where f(x) V (n + lo (nnn++nn++ +
(nn)
Here, f is defined so that up to lower-order terms, (n) :: the logarithmic factor that depends on >>0 0 serves to ensure the technical condition that the series f(n)a is convergent: Σ 1
f(m)a = K
where Kg is constant depending only choice of e, that will later appear in our bounds.
3 Our Algorithm and Analysis
Before we provide the algorithm and its guarantees, we first discuss a needed assumption. Observe that even in the casier setting where the conformal score is drawn from fixed, known distribution: ~ D - there may not be any threshold q E [0, 1] that satisfies the desired target coverage value, i.c. that guarantees that E.~D [Cover(g s) (1 - 8)]l small. Consider for example a distribution that places all its mass on single value s. Then any threshold covers the with probability 1 or 0,
We can handle non-uniform discretizations of the unit interval well, with additional complications.

---

which for å & {0. } is bounded away from our target coverage probability. One could randomize the threshold get the target marginal coverage rate, but this corresponds the "cheating" strategy we outline in Footnote 2 and in particular would not satisfy our notion of threshold calibrated coverage. Of course, if achieving the target coverage impossible in the easier distributional setting, then also impossible in the more challenging online adversarial setting.
With this in mind, just with many other approaches conformal prediction that aim to converge to the correct coverage rate (rather than conservatively over-cover), we will need to assume that our target distributions are not too concentrated on any single point. Following Gupta al. [2022), we define a class of smooth distributions for which achieving (approximately) the target coverage is always possible for some threshold q defined over an appropriately finely discretized range. Our smoothness condition makes sense even for discrete distributions. so we do not need to assume continuity. To denote the uniform grid on [0, 1], we write pam {0, ym rm rm....., 1}.
We show that we can achieve (approximately) our target coverage goals in the online adversarial setting when the adversary is constrained playing smooth distributions, which distributions that do not put too much probability mass on any sufficiently small sub-interval.
Definition 3.1. A distribution Q A 1I) is (p. (m)r))ssmm mmm-smoothh if
Pr [s E [a, b]] S P for any subinterval [a, bj S [0. 1] length S a~
1 ym
A joint distribution D E A(X [0, 11) is (p, rmm-smothhh for every X, the marginal confor- mal score conditional on x, 'Di is (p, rmmoooothh. An adversary is (p, rmm)smooth if the joint distribution over (Iz: St) is (p. rmm-shooth
every round t [T].
Remark 3.1. For any p. the assumption of (p, sm)-shoohsness becomes more mild as r + co. For us, will be muisance parameter that we can take as large as we want
will not have pay for either in our running time or our coverage bounds. We can also algorithmically enforce smoothness by perturbing the conformal scores with small amounts of noise from any continuous distribution, and so we should think of smoothness as a mild assumption. Our experiments bear this oul.
We now present the algorithm (MVP - MultiValio Predictor). It resembles the algorithm for online mean multicalibration given in Gupta et al. [2022]. which in turn is multi- group generalization of the "almost deterministic" calibration algorithm of Foster and Hart (2021)
Algorithm 1: MVP(ó, 1), m. fort= 1, ..... do
Take as input an arbitrary conformal score 8, : X' x y - [0, 1].
Observe N., and for each [m] and G E G(zr)), compute:
G n-
Σ 1 1/ E Bm (m))), x G
Definition 3.2
v
Σ
1[z, E G. E Bm(()] (Cover((r; s7) 8))
Definition 3.3
r=1
Via -11 ))
(zi(zz)= GEG(2t)
exp
eep
From Lemma
f(m211)
if (+)) > 0 for all i E [m] then
Choose threshold qi = 0.
else if (i,((x)) ) < 0 for all E [m]] then
Choose threshold q: = 1.
else
Find 1" [m 1] such that C (wt) Cf+ (3te) 50.
Pt c / ((cit' (xx) (zx)))
Define < Pt S as follows
Choose threshold = Output prediction set T((:;) {s E y (x v) S g:).
with probability P: and gi f.f with probability 1 - Pr.
"Using the convention that 0/0 0.
5

---

First, we give a brief intuitive description of the inner workings of the algorithm. Note that for all groups G and buckets i, MVP maintains historical over- (equivalently, under-) coverage amounts over those rounds when the context was in group G' (that is, Z2 E G), and the threshold played was in bucket (that is, qt E B, (i)). In each round, MVP is confronted with a new context St, and needs to decide which bucket to choose the threshold from. For every candidate bucket i E [m)] MVP performs a certain type of normalized softmax aggregation of that bucket's historical over- or undercoverage over all groups G that xa belongs to. The result is single signed quantity Ci_1 for each bucket i, which summarizes its past coverage performance over all relevant groups G 3 zy: intuitively, if thresholds from bucket have been mostly overcovering the relevant groups in the past, we can expect -²-1 > 0, and in the opposite case of significant undercoverage, we can expect C2-1 < 0. The algorithm then simply finds, if such exist, any two adjacent buckets one of which has historically over-covered and the other under-covered, and randomizes between the two to output a balanced threshold that, it is hoped, neither over- nor under-covers.
Now, we are ready to present main result - the multivalid coverage guarantees for MVP. The proof of this statement is laid out in the following Section 3.1
Theorem 3.1. Against any (p, rmm-shooth adversary and for any adaptively chosen sequence
of conformal scores St, MVP(n, r) with learning rate 17 2k. (Algoritimm 1 produces
[
a sequence of thresholds (4e YE that is ((V4K ln([s][mm)mm))))))) + øT) a(-), m) multivalid in expectation over the randomness of NyT with respect to 8 and g.
Consequently, we have for any small e >> 0 of our choice (with Ke constant that depends only on E):
EiEor(o) (Cover (gt: 8t) - (1-6))
E
max GE
4 (m + pT.
((G ((G) +2)
Remark 3.2. Since we can take to be arbitrarily large, for any continuous distribution we can drive the pT term to zero. Thus this bound establishes nearly statistically optimal convergence rates for con- stant [g] and m. Using simpler analysis analogous that Gupta et al. [2022] for mean multical- ibration, it is also possible establish (a, m)-multivalidity with (n) O(VT log( mm)nn p). which is optimal in [g] and m but has a bad dependence on T. We believe that our sub-optimal dependence on [g] and m an artifact of our analysis, and not a property of our algorithm.
3.1 Analysis
Omitted proofs from this section are presented in full detail in Appendix A Our analysis here can be seen as an extension of the surrogate loss argument developed in Gupta al. (2022) for the problem of mean multicalibration. There are two main novel insights that lead to our algorithm and analysis for multivalid coverage. First, [Gupta et al.) [2022] were unable to extend their simple multicalibration algorithm to prediction interval multivalidity (and instead analyzed an impractical Ellipsoid- based algorithm). Informally this is because they parameterized prediction intervals with two parameters (the lower and upper endpoint), which eliminated the simple minedmmenioonal structure they were able to exploit for mean multicalibration. In contrast, our prediction intervals are parameterized by a single parameter 9. which allows us exploit a simple one- dinensniiio structure.
Second, the bounds in Gupta et al. [2022] uniformly bound the coverage error for each group G g and bucket i [m]] by O(VT), which optimal only for subsequences that have n Q(T). In contrast, we obtain non- con-uniform bounds that depend on nT G. but not on T, and (at least for constant m nT
and [9]) have the optimal
G. dependence. We achieve this by analyzing modified surrogate loss, leading to a significant amount of added complexity which accounts for the bulk of our argument.
Proof sketch for Theorem 3.1 to bound the coverage error the subsequence of rounds in which x, E G and 4- Bn (i) in terms of the length of that sequence. We give the following notation for these sequence lengths:
For each group G E G. bucket E [m]] round /. E [T], we would like

---

Definition 3.2 (Group-bucket size), Given transcript #ia (( ST. =-)))=1- we define the size
for a group G E 9 and bucket i E [m]] at time & to be: n4
Gi (TTx) =
Σ 1lr E Bm()), or E G].
Similarly, for each G G. i E [m] and time E [7], we can define the (unnormalized) coverage error on the sequence corresponding to rounds T S such that 2, E G and q, E [m]]
Definition 3.3. Given transcript ι iia the coverage error group G E G and bucker E [m]] at time
given as: V.l. Σ 1x2, E G, E Bm) (1r S7), where vs vs(g. s) Cover(g, 8) (1-6).
Note that V. just records the deviation of the empirical coverage from its target (1 5) on the subsequence of rounds in which ir G and de Bm (i): it takes positive value if we have over-covered on this subsequence and a negative value we have under-covered.
Observation 3.1. Fix transcript T.T. for all G 9 and E [m]] we have for some conslant vi S <f((n)) G..,, then the resulting sequence of thresholds (qr) is (cax(-), m) mimuliiiillidd with respect and g.
To bound the maximum of our normalized absolute coverage errors across all groups and buckets, i.e. maXGeg.eelm
[V
f(m 2a we use the following surrogate loss:
Definition 3.4 (Surrogate loss). Fix transcript Ti: II and a parameter (0,1/2). Define surrogate coverage loss function at day ffrr bucket i E [n] and group G E G as
G. (T1(a))) cxp Lt
VGG. ((1h
exp (-M
(
where Vi are implicitly functions of Ti:t- The overall surrogate coverage loss function is defined as (T(T) = EGeg,eemm ". (TT:r).
We first show that the increase in the surrogate loss can be bounded in the following way: Lemma 3.1. Fix 7 E (0, ) and transcript F1:t-1.for some t. For any Te. (gt, Izt St), we have
Le(Tu-110 2 TT) L (TL1(TL
Σ
su 0 + Ji
G. (Te-)))
(G)))
where Ax(Tt) = [(G,t) GEG(())) dt E (i)) contains (G,i) pairs "active" at time LE [T), and GG
voo. (1
exp
exp (-1
Now, show that Algorithm Iguarantees E(g.nEA Vo(2,, V1(9,, S1 is small in expectation the randomness of the algorithm.
Lemma 3.2. Fix any [T), n (0. transcript TT--1 recording a realization for the first I rounds and At round I, C distribution over q. such that against any (p, rmm)-mooth distribution over conformal scores 8,, we have:
E
Σ
S G.d ma--
S pla-1
(#1.9c)
(()))
Carefully telescoping the bounded increase surrogate over each round via Lemma 3.1 and 3.2 and noticing that 1n)( forms convergent series yields the result of Theorem 3.1
7

---

100
coverage
MVP
MVF Spil-Canfomal
Spil-Coriermll
60-
80
50-
No. of Rounds
Rounds
60-
40-
40
20-
20
10
0.87
0.88
0.89
0.50
0.91
0.92
0.93
0.750
0.775
0.800
0.825
0.850
0.875
0.900
0.925
Marginal Coverage
Average interval Wioth
Figure 1: Left: histogram of empirical marginal coverage of MVP vs split conformal over 500 repeated trials. Right: histogram of average interval widths. MVP gets both empirical coverage that is more tightly concentrated around target (0.9), and narrower coverage interval widths.
4 Experiments
In this section, we summarize experiment: full details can be found in Appendix B We evaluate NVP and compare it to more traditional conformal prediction methods on a variety of tasks. In each case, for a fair comparison, both MVP and the compared-to method receive input the same predictive model and conformal scores.
Exchangeable data First, in Section B.I we study a synthetic linear regression problem in a simple exchangeable (iid.) setting, and compare split conformal prediction (Lei al. 2018). Given regression model ft(z), we use conformal score st (z. y) = [f(( - y/- The regression function unknown the outset, and must be learned during the interaction. As we show (Figure [). MVP improves over split conformal prediction even in terms of marginal empirical coverage. This is because to keep the conformal scores exchangeable, split conformal prediction must split the data into two sets: one for training the regression model and one for calibrating prediction sets In contrast, our method does not require exchangeability, so we can both train the regression model and calibrate our prediction sets the entire dataset. We are thus able to make better use of the data, and our regression function (and hence our conformal score function) becomes more informative faster. Then, we modify our regression problem so that there are 20 overlapping sub- sub-populations, one of which (consisting of half of the data) has higher label noise. We measure groupwise coverage for MVP, for naive split conformal prediction with no knowledge of to-be-covered groups, and the method of Foygel Barber et al. (2020) which guarantees (conservative) groupwise coverage for intersecting groups We find (Figure that MVP significantly improves on both methods, obtaining correct coverage on all groups and (correctly) obtaining much smaller interval width on the low noise group.
Covariate shift Next, in Section B.2 we study a regression problem in the presence of covariate shift. First replicate experiment of Tibshirani et al. [2019), in which a synthetic covariate shift (with known propensity scores and known changepoint) is simulated on a UCI dataset. The method of Tibshirani et al. [219]] reweighs the calibration set using the propensity scores. MVP can also take advantage of propensity scores warm-start MVP on the same portion of the dataset that split conformal prediction uses for calibration, sampled with replacement after being re-weighted by the propensity scores. Both algorithms are then evaluated on the shifted distribution. We find both algorithms perform comparably. We then experiment with unanticipated covariate shift simulated on datasets derived from 2018 U.S. Census data provided from the Folktables package (Ding et al. 2021]. We use the quantile-regressioon based conformal score proposed by Romano et al. [0199 for both methods. We compare to split conformal prediction calibrated on California data and evaluated on the Pennsylvania data. Similarly, we warm-start MVP on California data and measure its performance on the Pennsyl vania data, finding that MVP gets the correct coverage rate and smaller interval widths compared to the split conformal method despite having no knowledge of the distribution shift.
1 Our experiments are fairly lightweight, and can run e.g. on a standard 12gh RAM Google Colab account. TThi is not only theoretical requirement- split conformal prediction fails badly otherwise.
8

---

Comparisan group coverage: Spiit- Conformal
Comparison group Interval- Split- Conformal MVP
Spiit Conforat Without groups
Splt Conforma: Without groups
Spil-Cooformat Wkh groups, conservative approach
Spit-Cenforma:: With groups conservaiire approsch
MVP
(Madian)
MVP
69
didied
12.5
c.8
10.0
6.7
0.6
7.5
0.5
03
62-
2.5
6.1
0.0
0.0
10.1 15177788
10 1011122300 141516171819
Groups
Groups
Figure 2: Left: median (over 100 indep. trials) per-group coverage of MVP vs split conformal. Right: median group-conditional interval widths. Compared to split conformal, MVP obtains target coverage on each group, and narrower interval widths.
Coverage trials, target coverage
Median Width (50 trials. target coverage .9)
Quantile Regression Folktables Data
Quantile Regression
Folktables Data
50
spilt conformal
split conformal
Frequercy
30
Prequency
30
10
0.900 0585
0.900
0.915
0.920
0.925
0.300
0.935
0.940
72700
72900
73000
73200
73300
73400
Coverage
Interval Width (in
Figure 3: Both MVP and split conformal prediction are initialized on California data and evaluated on Pennsylvania data. On the left-hand is a histogram of the coverage for MVP and split conformal prediction over 50 trials; the right-hand figure is a histogram the prediction interval width.
Time series In Section B.3 we evaluate MVP on time series data - 20 years of stock returns, in
volatility prediction task. We compare MVP the Adaptive Conformal Inference (ACI) method Gibbs and Candes [202T]. which guarantees marginal (but not threshold- or group- calibrated) coverage for adaptively chosen data. When evaluated in terms of marginal coverage, we find that MVP and ACI perform comparably, with ACT's coverage slightly closer to the target, but with MVP's s sequence of predicted thresholds exhibiting more stability (Figure B.6). We then complicate the experiment to exhibit the two advantages of MVP (groupwise and threshold-calibrated coverage). First, we define 20 intersecting groups of trading days: a period-1 sequence (all the days). a period-2 sequence (the even days), .... a period-20 sequence (every 20th day). We add perturbations to the stock returns, such that each day receives an amount of noise commensurate with how many groups it belongs to. The point of adding these perturbations to the stock returns different subsets of the days is to produce a dataset on which the uncertainty of the model is quantifiably different within different groups thus making it nontrivial to obtain valid coverage each of those groups by only enforcing valid marginal coverage. Indeed, we find that MVP obtains the correct group- wise coverage, whereas ACI fails to: as shown in Figure 4a ACI undercovers most groups
As our next experiment, we produce a fully adversarial sequence by presenting examples to ACI and MVP not in time order but in sorted order by their conformal scores (see Figure(4b). By construction, this sequence would cause split conformal prediction methods to have coverage, while both ACI and MVP guarantee correct marginal coverage on it. However, we find (see Figure B.&d) that ACI achieves its correct marginal coverage by violating threshold calibration: namely, by predicting
Too balance out this undercoverage, ACI strongly overcovers on points belonging of groups 2..20.

---

Coverage on Noisy Groups: MVP vs ACI
MVP
destred coverage
0.9
Coverage level
(b) Synthetic sorted scores sequence
01
00
Group number
(a) MVP and ACT median coverage (over 20 indep. trials) groups 1-20 noisy data (group consists of days such that mod j). NVP closely matches desired coverage level on all groups, whereas ACI significantly undercovers (within up to 10-20% from the target).
(c) NVP thresholds on the sorted scores
Figure MVP vs ACI comparison on time-series data
predominantly the trivial coverage interval (all of [0, 1)) and occasionally short, under-covering intervals This strategy both yields thresholds that are uninformative about the input sequence of scores, and produces close-to-man maxemmmmmmmimmmmmmmm average interval widths regardless of the actual magnitude of the input scores. In contrast, MVP, by virtue of its threshold calibration, outputs coverage thresholds that correctly track the input sequence of conformal scores (Figure 4c), and hence produces prediction intervals with the correct widths.
ImageNet Finally, in Section B.4 we compare MVP to the work of Angelopoulos et al. [020] large-scale ImageNet classification task. We find that MVP obtains comparable coverage rates and prediction set sizes, despite the fact that the setting is favorable to Angelopoulos al. 2020 i.e. the data is i.i.d. and measure only marginal coverage.
Classification:
Potential societal impact of our work: When the underlying dataset consists of e.g. labeled indi- viduals, our conformal prediction approach achieves target coverage guarantees not only marginally, but on arbitrary collections of user-specified population groups. Thus, we believe that when used responsibly, our method can serve as key tool for advancing the interests of protected subpopulations, resulting in significant added positive societal impact.
References
Anastasios N Angelopoulos and Stephen Bates. A gentle introduction conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.0755 2021.
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations, 2020.
Michael Bian and Rina Foygel Barber. Training coverage for distribution predictive inference. arXiv preprint 22Xiv:2005.03647, 2022.
Tim Bollerslev, Generalized autoregressive conditional hetcroskedassiccity Journal of econometrics, 31(3):307-327, 1986.
Victor Cheroozhukov, Kaspar Wüthrich, and Zhu Yinchu. Exact and robust conformal inference methods for predictive machine learning with dependent data. In Conference On Learning Theory. pages 732-749, 2018.
CC.. the "cheating" marginal coverage strategy discussed in Footnote 2
10

---

Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34, 2021.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL httphht:ppachhie.eiiiie. uci. edd/ml
Dean P Foster and Sergiu Hart. Forecast hedging and calibration. Journal of Political Economy, 129 (12).3447-3490, 2021.
Rina Foygel Barber, Emmanuel Candès, Aaditya Ramdas, and Ryan J Tibshirani. The limits of distribution-free conditional predictive inference. Information and Inference: A Journal of the IMA, 2020.
Asaf Gendler, Tsui-Was Weng, Luca Daniel, and Yaniv Romano. Adversarially robust conformal prediction. In International Conference on Learning Representations, 2021.
Isaac Gibbs and Emmanuel Candes. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 34, 2021.
Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, and Aaron Roth. Online Multivalid Learning: Means, Moments, and Prediction Intervals. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 82:1-82:22 2022.
Úrsula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Cali- bration for the conpuuaaionalll--deetfffaa masses. In International Conference on Machine Learning, pages 1939-1948, 2018.
Peter Hoff. Bayes-optimal prediction with frequentist coverage control. arXiv:2105.14044 2021.
arXiv preprint
Christopher Jung, Changhwa Lee, Mallesh M Pai, Aaron Roth, and Rakesh Vohra. Moment multical- ibration for uncertainty estimation. In Conference Learning Theory. PMLR, 2021.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In International Conference Machine Learning, pages 2564-2572, 2018
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. An empirical study of rich subgroup fairness for machine learning. Proceedings of the Conference on Fairness, Accountabiliry, and Transparency, pages 109- 2019.
Michael Kim, Omer Reingold, and Guy Rothblum. Fairness through computationnaly--bounded awareness. In Advances in Neural Information Processing Systems, pages 4842-4852, 2018.
Jing Lei, Max G Sell, Alessandro Rinaldo, Ryan Tibshirani, and Larry Wasserman. Distribution-fres predictive inference for regression. Journal of the American Statistical Association, 1 113(3)3): 1094-1111) 2018.
Sangdon Park, Osbert Bastani, Nikolai Matni, and Insup Lee. Pac confidence sets for deep neural networks via calibrated prediction. In International Conference on Learning Representations, 2019.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Advances in neural information processing systems, 32, 2019.
Yaniv Romano, Rina Foygel Barber, Chiara Sabatti, and Emmanuel Candès. With malice toward none: Assessing uncertainty via equalized coverage. Harvard Data Science Review, 2020a.
Yaniy Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 33:3581-3591, 2020b.
Glenn Shafer and Vladimir Vovk. tutorial on conformal prediction, Journal of Machine Learning Research, 9MMar):371-421, 2008

---

Ryan J Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal prediction under covariate shift. Advances in Neural Information Processing Systems, 32:2530- 2540, 2019.
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian conference machine learning, pages 475-490. PMLR, 2012.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts your work? [Yes] Please see the dedicated paragraph on societal impact at the end of the main part of the paper-
we believe that responsible use of our method will lead to significant added positive societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [Yes]
(c) Did you report error bars (e-g., with respect the random seed after running experi-
ments multiple times)? [Yes] Described in detail where appropriate in Appendix B
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [Yes] The supplement will contain our code for the experiments.
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A] We used and cited open access data.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] None of our data contains such content or information.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "Wfr1IhR1vSG", "reviewer": "Reviewer_RP3U", "summary": "The authors propose a calibration method in the spirit of (adaptive) conformal prediction for providing (conditional) coverage guarantees when prediction confidence intervals/sets without necessarily requiring exchangeable examples. Thus, the method is applicable to dependent time series data in addition to standard i.i.d. settings. In comparison to prior work, the method provide coverage conditional on arbitrary subgroups of inputs and conditional on the calibrated threshold in timer series data. To this end, an adversarial setting is assumed where the adversary chooses inputs and conformity scores from a distribution that is assumes to be reasonably smooth (i.e., not concentrated on individual points) – this is the only assumption made as far as I can tell.", "questions": "See weaknesses and conclusion above.", "limitations": "See weaknesses and conclusion above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is generally well-structured and notation is introduced clearly – even though the paper is very notation heavy in general, see weaknesses.\n- The advantages of the proposed method are described fairly clearly in the intro.\n- Generally, the paper addresses an important problem of (conditional) coverage guarantees without exchangeable data. While various papers have addressed individual parts (e.g., group-conditional coverage or calibration set conditional coverage), to the best of my knowledge, obtaining coverage conditioned on arbitrary groups as well as thresholds without requiring exchangeability is not possible so far.\n- The authors demonstrate their approach in various settings similar to previous papers to demonstrate the method on various tasks involving standard classification and regression, time series data or covariate shift, mostly focusing on coverage and inefficiency (set/interval size).\n- A sketch of the proof is provided in the paper.\n- The appendix obtains sufficient details on experimental setup.\n\nWeaknesses:\n- The paper is very dense and notation-heavy. I appreciate that this is necessary for communicating the guarantee and a sketch of the proof, but I believe the authors could improve structure and writing that would make following the paper easier. Here are som individual points that I stumbled over:\n\n    - Lines 39ff, the point of threshold-conditional coverage is not very clear imo.\n\n    - Lines 56ff, this argument is also not very clear when the reader is unfamiliar with Gupta et al. - I skimmed through Gupta et al., but it is a very dense paper itself. \n\n    - Footnote 1 seems rather important in terms of supporting one of the contributions – generally, I think a footnote is not the right place for this even if it might save space.\n\n    - The introduction to notation in section 2 is helpful, but generally I would prefer it the authors would repeat the notation inline at appropriate places. Currently, nearly in every statement, I need to scroll back and check notation. Alternatively, a separate notation section could help, because sometimes it is also not clear where to scroll to to find the notation being introduced.\n\n    - An example of the above is the definition of G_T(i) in definition 2.1.\n\n    - Another example in K_\\epsilon in the theorem.\n\n    - Definition 2.1 is a bit unclear regarding the choice of \\alpha – the choices provided seem somewhat arbitrary in the beginning and there is no discussion of this. It only becomes slightly clearer later in the paper.\n\n    - Surrounding Definition 3.1, I think the authors could do a better job providing an intuition of the adversary. In the beginning it is very unclear what the adversary can do and what not. Also it is unclear what the adversary is supposed to model in practice (i.e., in practice, the scores are computed by the model and the adversary is just a way to model this adversarially in order to obtain a guarantee).\n\n    - Algorithm 1 is typset too early in the paper in my opinion. How it works only becomes clear throughout the proof sketch. In fact, the proof sketch is used to introduce the method very indirectly. I spent half an our on the algorithm assuming that I would have to understand how it works, realizing later that the proof sketch is basically meant to walk me through it. I think this a big flaw structure and notation wise.\n\n    - There should be more discussion on the theorem, what this bound means in practice, how different variables influence it – this is partly done in the following remark but in my opinion not sufficient to give a good understanding. Might also be because the analysis comes later.\n\n    - 3.1 starts using notation from the algorithm, which was very hard to follow without reading 3.1 first. So this is a bit of a circle which should be broken in 3.1 or by moving the algorithm. It is also not made clear in the beginning that 3.1 will actually explains the algorithm.\n\n    - Observation 3.1 is not straight forward. I feel this is by construction but should be worth 1-2 sentences of why this is.\n\n    - In definition 3.4, the index t in L_t, V_t and \\pi_t is unclear. Is the t used in V_t the same as in L_t or \\pi_t (the arguments). This seems relevant as these seem disentangled in Lemma 3.1.\n\n- Regarding related work, this paper seems to build on the work by Gupta et al. Generally, I would appreciate making the similarities clearer without requiring to read Gupta et al. But as the paper is already dense I would actually prefer not going into detail in comparison to Gupta et al. in the main paper but rather deferring that to the appendix and making this clear in the beginning of the main paper, this could also save some space. Nevertheless, can the authors give a concise discussion of the differences to Gupta et al. And what they built on/develop further? In the paper this is very spread and I was unable to get a clear picture.\n- I think that split conformal prediction does provide calibration-set conditional coverage as discussed in detail in [a] and [b] and I think discussing these results would be important. This is because, assuming exchangeability (I know that this work goes beyond exchangeability), the benefit of MVP over split conformal prediction is limited – both are able to obtain calibration set and group-conditional coverage (when groups are known which AFAIK is the case here, too). Can the authors comment on this? (I acknowledge that [b] is very recent and more like concurrent work)\n\n[a] Vovk. Conditional Validity of Inductive Conformal Predictors\n[b] Bian et al. Training-conditional coverage for distribution-free predictive inference\n\n- In figure 2, the groups seem to be very easy, split conformal prediction also provides conditional coverage except for one group. For me it looks like the groups are not really interesting – usually I would expect groups to obtain widely varying coverage levels if these groups are aligned somewhat with difficulty (like classes, fairness attributes or so).\n- In the time series experiments, I am not sure whether I understand the motivation of adding noise. Can the authors comment on this? Is this just to make the task harder and show that MVP works better (because it doesn’t work better without noise)?\n- In figure 3, what are the average lengths for both methods? Also, split conformal prediction always predicting the same interval is mainly due to the coarse histogram, right?\n- In figure 4 a, shouldn’t there be any groups where ACI is overcovering. Marginal coverage is guaranteed but it underestimates coverage on all of them. Am I missing something?\n- On ImageNet, the calibration set is very small, and RAPS still performs better (and RAPS is even less efficient then simpler conformity scores, see [c]). Does this mean that MVP is generally less relevant in split settings with exchangeability? Or does MVP still obtain better class/group-conditional coverage on ImageNet? (These experiments are missing in my opinion.)\n\n[c] https://arxiv.org/abs/2110.09192\n\n- Also, how would the ImageNet results change when performing trials instead of fixing calibration and test set?\n- In any of the non-ImageNet experiments, are there cases where baselines do not provide calibration set/threshold-conditional coverage and could this be evaluated somehow?\n\nConclusion:\nI believe the proposed method is a good contribution to the community. I only see two drawbacks: First, the paper is very difficult to follow, requiring the reader to sit down and be able to annotate the paper and write down definitions/notation to follow the algorithm and discussion. I think this could be improved by devoting more space to it and maybe moving some experiments or discussion of Gupta et al. to the appendix. Second, for some experiments the picture is less clear and this should be discussed a bit better – i.e., in which settings the proposed method really works well/better. This also includes evaluating or commenting the threshold-conditional coverage which is “advertised” in the introduction. While I was unable to check the proof in the appendix in detail, due to density and amount of experiments, the proof sketch seems reasonable and valid as far as I can tell, but it would be good if another review could confirm this.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NAmLlkFpdJd", "reviewer": "Reviewer_3pUm", "summary": "This paper presents an online conformal prediction algorithm, which is proven to satisfy a “threshold-calibrated multivalid coverage guarantee” (Definition 2.1). Compared with prior work, several advantages of the proposed algorithm are: 1) it does not require the exchangeability assumption for proving the coverage guarantee, thus it can be used to model sequential data such as time series; 2) it is claimed to be robust to arbitrary and unanticipated distribution shift; 3) the obtained coverage guarantee is not just marginally but promises group-conditional coverage; 4) it achieves improved statistical rate over the work of [Gupta et al., 2022]. Experiments on synthetic data, time-series data and image data support these advantages over existing methods.\n", "questions": "1. In the experiments, most of the considered tasks are regression tasks. You only compared with Angelopoulos et al. [2020] on marginal coverage, how about the conditional coverage for subgroups? In general, I am curious about the conditional coverage performance of your algorithm for classification tasks.\n\n2. How do you decide the number of buckets m for your algorithm for a practical task?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. The paper is well-motivated, and its contribution is significant to the field of conformal prediction. The proposed method achieves both worst-case empirical coverage and calibrated, multivalid coverage, which clearly advances the existing literature.\n\n2. The paper discusses the comparisons with related works well, and is technically solid with clearly presented definitions, assumptions, theorems, and proofs.\n\n3. The proposed surrogate loss (Definition 3.4) and its induced techniques for proving the threshold-calibrated multivalid coverage is theoretically interesting.\n\n\nWeakness:\n\n1. Section 2 and Section 3 are overloaded with technical notations. The motivations of the proposed coverage guarantee (Definition 2.1) and the specific design of Algorithm 1 are not well-explained, at least intuitively. For example, Definition 2.1 introduces threshold calibration, you may want to explain why you want the marginal coverage to be additionally satisfied for multiple buckets simultaneously, as opposed to the case where there is just a single bucket. \n\n2. In line 32, the authors claimed that the proposed method has worse-case adversarial guarantees, which is very strong in my perspective. However, the threat model is not defined clearly (without a formal definition) at the beginning, thus hard to evaluate its significance. What are the differences between the adversarial setting considered here and the setting of covariate shift such as Tibshirani et al. [2019]? Does the adversary need to satisfy some assumptions (e.g., Definition 3.1)? [1] is a related paper on this, so should be mentioned or discussed in the paper as well.\n\n[1] Adversarially Robust Conformal Prediction, Asaf Gendler and Tsui-Wei Weng and Luca Daniel and Yaniv Romano, ICLR 2022\n\n\nTypos: \n\nLine 148: n is not defined\n\nLine 149: w belongs to -> q belongs to\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ISHdf4AHB_", "reviewer": "Reviewer_w6qw", "summary": "The paper presents a novel, lightweight conformal-inspired algorithm for quantifying uncertainty in an online setting. This is a good contribution: it is highly competitive and even outperforms existing methods for making sequential predictions with valid coverage, even under adversarial settings.", "questions": "See the comments under the weaknesses section.", "limitations": "The authors included a discussion about ethical considerations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe proposed framework has several key advantages: \n\n(1) It uses the entire data for training a predictive model and does not require using holdout data for calibration.\n\n(2) The coverage guarantee holds in an adversarial setting.\n\n(3) The coverage guarantee holds conditionally on the threshold used to form the prediction set.\n\n(4) The coverage guarantee holds conditionally on possibly intersecting groups, which needed to be defined apriori.\n\n(5) Numerical experiments demonstrate the validity of the theory, showing the advantage of this method in a wide variety of settings. In particular, I find the results presented in Section B.3 illuminating.\n\n**Weaknesses**\n\n(1)\tThe paper is written to experts in conformal prediction, and I am worried that this will hurt the deployment of the proposed method. Specifically,\n\na. Consider the introduction for example: what is a non-conformity score? What is $f$? What is $S_t$? \n\nb. Next, moving to Algorithm 1: how the user should interpret each of the steps? Perhaps the authors can name, or explain in words the purpose of each step so that the reader will not lose intuition. \n\nc. Consider Theorem 3.1: it asks to set $\\eta $, but where $\\eta $ is being used? It took me some time to understand that $\\eta$ appears in the surrogate loss. This makes me wonder how does it affect the performance? How should the user set this parameter?\n\nd. Consider pausing after Theorem 1 and explain it in words to ease the interpretation of this result.\n\ne. Section 3.1 starts with a discussion about the differences between the proposed method and the one of Gupta et al. (2022). But, at this point, the reader is still trying to understand the implications of Theorem 1. Consider moving this discussion after sketching the proof. \n\n(2) It is not clear how to check (online, as data arrive) that Definition 3.1 holds for a given triplet (\\rho,r,m). I understand the statement that “We can also algorithmically enforce smoothness by perturbing the conformal scores with small amounts of noise from any continuous distribution, and so we should think of smoothness as a mild assumption”. But this will then reduce statistical efficiency, as algorithmic noise will be added to the scores. And also, how can we even know that we violate Definition 3.1?\n\n(3) Section B.1: If I understand the experiment correctly, I believe the authors should also compare their method to ACI. Compared to split conformal, the gain in performance is due to the fact that MVP is applied online and re-fits the predictive model once a new test point is observed; this setting is more similar to the way that ACI (or its time-series version [ACI-TS]) is implemented.\n\n[ACI-TS] Zaffran, Margaux, Aymeric Dieuleveut, Olivier Féron, Yannig Goude, and Julie Josse. \"Adaptive conformal predictions for time series.\" arXiv preprint arXiv:2202.07282 (2022).\n\n(4) Section B.2.1: same comment as above.\n\n(5) Section B.4: same comment as above.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept