Adaptive Conformal Inference Under Distribution Shift
Authors: Isaac Gibbs
Emmanuel Candes
Venue: NeurIPS 2021 Oral (2021)
Keywords: Online Learning
(Other) Statistics

Abstract: We develop methods for forming prediction sets in an online setting where the data generating distribution is allowed to vary over time in an unknown fashion. Our framework builds on ideas from conformal inference to provide a general wrapper that can be combined with any black box method that produces point predictions of the unseen label or estimated quantiles of its distribution. While previous conformal inference methods rely on the assumption that the data are exchangeable, our adaptive approach provably achieves the desired coverage frequency over long-time intervals irrespective of the true data generating process. We accomplish this by modelling the distribution shift as a learning problem in a single parameter whose optimal value is varying over time and must be continuously re-estimated. We test our method, adaptive conformal inference, on two real world datasets and find that its predictions are robust to visible and significant distribution shifts.

Adaptive Conformal Inference Under Distribution Shift
Isaac Gibbs Department of Statistics Stanford University igibbs@stanf ord. edu
Emmanuel Candès Department of Statistics
Department Mathematics
Stanford University
candes@stanford edu
Abstract
We develop methods for forming prediction sets in an online setting where the data generating distribution is allowed to vary over time in an unknown fashion. Our framework builds on ideas from conformal inference to provide a general wrapper that can be combined with any black box method that produces point predictions of the unseen label or estimated quantiles of its distribution. While previous conformal inference methods rely on the assumption that the data points exchangeable, our adaptive approach provably achieves the desired coverage frequency over long-time intervals irrespective of the true data generating process. We accomplish this by modelling the distribution shift as a learning problem in a single parameter whose optimal value is varying over time and must be continuously re-estimated. We test our method, adaptive conformal inference, on two real world datasets and find that its predictions are robust to visible and significant distribution shifts.
1 Introduction
Machine learning algorithms are increasingly being employed in high stakes decision making pro- cesses. For instance, deep neural networks are currently being used in self-driving nearby objects 2 and parole decisions are being made with the assistance of complex models that combine over hundred features [1. As the popularity of black box methods and the cost of making wrong decisions grow is crucial that we develop tools to quantify the uncertainty of their predictions.
detect
In this paper we develop methods for constructing prediction sets that are guaranteed to contain the target label with high probability. We focus specifically on an online learning setting which we observe covariate-response pairs {(X,, Y.) C Rd x R in a sequential fashion. At each time step I E N we are tasked with using the previously observed data {(xr, hsssssss-- along with the new covariates, X₁, to form prediction set Ó2 for Y, Then, given target coverage level a E (0, 1) our generic goal is to guarantee that Y, belongs to Ct at least 100(1 - a % of the time.
Perhaps the most powerful and flexible tools for solving this problem come from conformal inference [see e.g. 34 16 32 22
B1 15 3 This framework provides generic methodology for transforming the outputs of any black box prediction algorithm into a prediction set. The generality of this approach has facilitated the development of large suite of conformal methods, each specialized to a specific prediction problem of interest [e.g. 30
21 With only minor exceptions all of these algorithms share the same common guarantee that if the training and test data are exchangeable, then
the prediction set has valid marginal coverage P(Y; E C,) =
While exchangeability is common assumption, there are many real-world applications in which we do not expect the marginal distribution of (X₂, Y2) to be stationary. For example, in finance and economics market behaviour can shift drastically in response new legislation major world
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

events. Alternatiell,, the distribution of (X,, Y.) may change as we deploy our prediction model in new environments. This paper develops adaptive conformal inference (ACT), method for forming prediction sets that are robust to changes in the marginal distribution of the data. Our approach is both simple, in that it requires only the tracking of single parameter that models the shift, and general as it can be combined with any modern machine learning algorithm that produces point predictions or estimated quantiles for the response. We show that over long time intervals ACI achieves the target coverage frequency without any assumptions the data-generating distribution. Moreover, when the distribution shift small and the prediction algorithm takes a certain simple form we show that ACI will additionally obtain approximate marginal coverage at most time steps.
1.1 Conformal inference
Suppose we are given a fitted regression model for predicting the value of Y from X. Let y be a candidate value for Y, To determine if y is reasonable estimate of Y,, we define conformity score S(X, Y) that measures how well the value y conforms with the predictions of our fitted model. For example, if our regression model produces point predictions (xX) then we could use conformity score that measures the distance between ((x)) and yy One such example
S(X:. v) = (x())) - yl-
Alternatively, suppose our regression model outputs estimates q(X; of the pth quantile of the distribution of X|X. Then, we could use the method of conformal quantile regression (CQR) 28 which examines the signed distance between y and fitted upper and lower quantiles through the score
S(X,, y) max(
y. 4(X,; 1(X;;1-a)) ax/2)}
Regardless of what conformity score chosen the key issue is to determine how small S y) should be in order to accept that is different from the data that was used fit the regression model. Using this calibration set we define the fitted quantiles of the conformity scores to be
reasonable prediction for Yg. Assume we have calibration set
Deal S (,),,,,))
@()) = inf {0: (Deall
Σ
1(s(x.,X))9)
2P
(X..
and say that is a reasonable prediction for Y; if ((x,() & Q(1 ax)
The crucial observation is that if the data Deat U {(X,, Y.) are exchangeable and we break ties uniformly at random then the rank of S(X,, Y,) amongst the points (S(X,, Y.). U (5(X,, Y,) will be uniform. Therefore,
(()-a)) a)) [[acil a)]
P(S(X,, YJ) & (1-
[Deal +1
Thus, defining our prediction set to C = {y: ((X,,0) S Q(1 201-00 aa) gives the marginal coverage guarantee
P(Y, E Ć.) = P(S(X,, Y)) s Q(1 -a) [[ (1-
[Deal +
By introducing additional randomization this generie procedure can be altered slightly to produce set Ć, that satisfies the exact marginal coverage guarantee P(Y, E C.)
a 34 For the purposes of this paper this adjustment is not critical and so we omit the details here. Additionally, we remark that the method outlined above is often referred to split or inductive conformal inference (27 34 26 This refers to the fact that we have split the observed data between a training set used to fit the regression model and withheld calibration set. The adaptive conformal inference method developed in this article can also be easily adjusted to work with full conformal inference in which data splitting is avoided at the cost of greater computational resources 2
2 Adapting conformal inference to distribution shifts
Up until this point we have been working with a single score function S(.) and quantile function Q--) In the general case where the distribution of the data is shifting over time both these functions should

---

be regularly re-estimated to align with the most recent observations. Therefore, we assume that at each time i we are given fitted score function S,(-) and corresponding quantile function (.)-). We define the realized miscoverage rate of the prediction set Ci(a) == {y: Sx v) Qo - a)} as
My(a)) == (X, Y.) > Qx - a));
where the probability is over the test point (X,, Yt) as well as the data used to fit S.(:) and (+)-).
Now, since the distribution generating the data is non-stationary we do not expect Mc(a) be equal, or even close to, a. Even so, we can still postulate that if the conformity scores used fit Q.(+) cover the bulk of the distribution of St (x,, Yt) then there may he an alternative value oz E [0. 1] such that Mc(a;) _ More rigorously, assume that with probability one, Q.(-) is continuous, non-decreasing and such that (0) = -oo and (1) co. This does not hold for the split conformal quantile functions defined in T but in the case where there are no ties amongst the conformity scores we can adjust our definition to guarantee this by smoothing over the jump discontinuities in Q-).. Then, M&(-) will be non-decreasing on [0, 1] with M, (0) and M, (1) = 1 and so we may define
of su [0. 1] M.(0) a).
Moreover, if we additionally assume that
P(S,((x, Yi) Q - =,
then we will have that M((a)) argument Q+(-)
So, in particular we find that by correctly calibrating the achieve either approximate exact marginal coverage.
To perform this calibration we will use a simple online update. This update proceeds by examining the empirical miscoverage frequency of the previous prediction sets and then decreasing (resp. increasing) our estimate of o the prediction sets were historically under-covering (resp. over-covering) Y,. In particular, let denote our initial estimate (in our experiments we will choose a). Recursively define the sequence of miscoverage events
1, if & Co(ar);
enr,
where Ci(a:) = (y S,(X,,)) S Qe(1 (1)}
0. otherwise,
Then, fixing step size parameter we consider the simple online update
a++1 == a + (
(2)
We refer this algorithm as adaptive conformal inference, Here, err, plays the role our estimate of the historical miscoverage frequency. A natural alternative to this is the update
0++1 aq + 7
Σ w.eIf, s=1
where (w,, tirahsage C [0, is a sequence of increasing weights with Σ W. = This update has the appeal of more directly evaluating the recent empirical miscoverage frequency when deciding whether or not to lower or raise an In practice, we find that @ and 3 produce almost identical results. For example, in Section A.3 in the Appendix show some sample trajectories for on obtained using the update 3 with
0.95
W/ E 0.95t-*
We find that these trajectories very similar to those produced by 2 The main difference is that the trajectories obtained with B are smoother with less local variation in 04- In the remainder of this article we will focus on for simplicity.
2.1 Choosing the step size
The choice of y gives tradeoff between adaptability and stability. While raising the value y will make the method more adaptive to observed distribution shifts, it will also induce greater volatility in
3

---

the value of ag. In practice, large fluctuations in ae may be undesirable as it allows the method to oscillate between outputting small conservative and large anti-conservative prediction sets.
In Theorem 4.2 we give an upper bound on (o)) that is optimized by choosing 7 proportional
to vlat+1 af While not directly applicable in practice, this result supports the intuition that in environments with greater distributional shift the algorithm needs to be more adapatable and thus ? should be chosen to be larger. In our experiments we will take 7 0.005. This value was chosen because it found give relatively stable trajectories for on while still being sufficiently large as to allow ag to adapt to observed shifts. In agreement with the general principles outlined above we found that larger values of y also successfully protect against distribution shifts, while taking y to be too small causes adaptive conformal inference to perform similar to non-adaptic con-adaptive methods that hold ar a constant across time.
2.2 Real data example: predicting market volatility
We apply ACI to the prediction of market volatility. Let (Pi) denote sequence of daily open prices for stock. For all t 2 2, define the return R, := (P: Pt-1)/P,-1 and realized volatility V = R2. Our goal is to use the previously observed returns X; = [Rs] [ to form prediction sets for Y == Vz. More sophisticated financial models might augment X, with additional market covariates (available to the analyst at time & 1). As the primary purpose of this section is to illustrate adaptive conformal inference we work with only a simple prediction method.
We start off by forming point predictions using GARCH(I,11) model R2 oge with ,g....,ff fT taken to be i.i.d. .N (0, 1) and o satisfying the recursive update
This method assumes that
of = w + -V, + Bo7-1-
This is common approach used for forecasting volatility in economics. In practice, shifting market dynamics can cause the predictions of this model to become inaccurate over large time periods. Thus, when forming point predictions we fit the model using only the last 1250 trading days (i.e. approximately 5 years) of market data. More precisely, for all times t >> 1250 we fit the coefficients Wi, ft, 3t as well as the sequence of variances {0T)isssi- using only the data [f--h-12500-ee Then, our point prediction for the realized volatility at time t is
(o.)² == W -v-1 1²
To form prediction intervals we define the sequence of conformity scores
1/, (o))²
S
(of)²
and the corresponding quantile function
(p) inf 20 1250
Σ 1=t-1250
1s.50 2p
Then, our prediction set at time
Co(ar) = 2: 1
(0:)²
S Qi((1 <
(o))²
where } is initialized with 0 = a = 0.1 and then updated recursively as in
We compare this algorithm to non-adaptive alternative that takes a fixed. To measure the performance these methods across time we examine their local coverage frequencies defined as the average coverage rate over the most recent two years, i.c.
localCov, :=
1
2
Σ
eIT,-
500
250+1
If the methods perform well then we expect the local coverage frequency to stay near the target value 1 across all time points.

---

Acaplive Apha
Fixed Alpha
Bemouli Sequenoe
Nvidia
AMD
Local Coverage Level
te
BlackBerry
Fannie Mae
Local Coverage Level
200
2066
2010 2016
20h0
2000 8606
aho
2016 2000
Time
Figure I: Local coverage frequencies for adaptive conformal (blue), a non-adaptive method that holds a₂ fixed (red), and i.i.d. Bernoulli(O.1) 1) sequence (grey) for the prediction of stock market volatility. The coloured dotted lines mark the average coverage obtained across all time points, while the black line indicates the target level of 1 = 0.9.
Daily open prices were obtained from publicty available datasets published by The Wall Street Journal. The realized local coverage frequencies for the non- -daativee and adaptive conformal methods on four different stocks are shown in Figure [ These stocks were selected out of total of 12 stocks that we examined because they showed a clear failure of the non-adaptive method. Adaptive conformal inference was found to perform well in all cases (see Figure 9 in the appendix).
As a visual comparator, the grey curves show the moving average sequences (T) that are i.i.d. Bernoulli(O.1), We see that the local coverage frequencies obtained by adaptive conformal inference (blue lines) always stay within the variation that would be expected from an i.i.d. Bernoulli sequence. On the other hand, the non-adaptive method undergoes large excursions away from the target level of right panel we can see that the non-adaptive method fails to cover the realized volatility of Fannie Mae during the 2008 financial crisis, while the adaptive method robust this event (see Figure in the Appendix for plot of the price of Fannie Mae over this time period).
500 2 J, for
(+250
0.9 (red lines). For example, in the bottom
3 Related Work
Prior work on conformal inference has considered two different types of distribution shift 33 10 both cases the focus was on environments in which the calibration data is drawn i.i.d. from a single distribution Po. while the test point comes from a second distribution Pt. In this setting Tibshirani et al. (33 showed that valid prediction sets can be obtained by re-weighting the calibration data using the likelihood ratio between Pt and Po. However, this requires the conditional distribution of Y|X to be constant between training and testing and the likelihood ratio (X))Pa( to be either known or very accurately estimated. On the other hand, Cauchois et al. [T0 develop methods for forming prediction sets that are valid whenever Pi and Po are close in f-divergence. Similar to our work, they show that if (Pill I p then there exists conservative value a, (0, such that
In
M(a,) == P(S,, X) Q - Q())a,)) a.
The difference between our approach and theirs is twofold. First, while they fix single conservative value ap our methods aim estimate the optimal choice a* satisfying M(a") ) a. This is not possible in the setting of [10] as they do not observe any data from which the size of the distribution shift can estimated. Second, while they consider only one training and one testing distribution we work in fully online setting in which the distribution is allowed to shift continuously over time.
5

---

Coverage guarantees
4.1 Distribution-free results
In this section we outline the theoretical coverage guarantees of adaptive conformal inference. We will assume throughout that with probability one d1 E [0, 1] and Qe is non-decreasing with Qx -00 for all x < 0 and (x) = do for all x > 1. Our first result shows that over long time intervals adaptive conformal inference obtains the correct coverage frequency irrespective of any assumptions on the data genteaannn distribution.
Lemma 4.1 With probubility we have that VI N, az E [->,1++]]
Proof: Assume by contradiction that with positive probability {ae)ten is such that inf, 0z < -y (the case where sup, o₁ > + y is identical). Note that sup; [0411 02 = sup, 7 emry < 7 Thus, with positive probability we may find N such that 0ş 0 and 0x+1 < ag. However,
err, = 0 a++1 o₁ 7 emr,) az and thus P(3/ such that 0++1 < at < 0) = O. We have reached contradiction.
Ot
(1 04)
Proposition 4.1
With probability one we have that all T E N,
erre al
max (0x, - on +7
(5)
Ty
In particular, lim T E erry a
Proof: By expanding the recursion defined in and applying Lemma 4.1
we find that
T
[-,,1+0] a ar+1 = an + Σ raa - err.).
1=1
Rearranging this gives the result.
Proposition puts constraints the data generating distribution. One may immediately ask whether these results can be improved by making mild assumptions on the distribution shifts. We argue that without assumptions on the quality of the initialization the answer to this question is negative. To understand this, consider setting in which there is a single fixed optimal target a* E [0, 1] and assume that
a 1 a²), ifp
(p) = M(p)
a (p-aa) if
Suppose additionally that E|err, ((re) In order to simplify the calculations consider the
noiseless update 0'e+1 ar + 7a (ax)) 0g + 7(a Eferr, (az]). Intuitively, the noiseless
update can be viewed as the average case behaviour of Now, for any initialization ân and any 7 S 1-a
minf L-o". e there exists a constant c E { II-a* I-a So, we have that E[err,)
a such that for all t, M (ax) - = c(aa a²).
cBfo, a²) = cB + 7(a M, a*) a(1 cy)BBar - -a)
Repeating this calculation recursively gives that E[em, a = c(1 e7)² Elan
a a²1= = c(1 -3) cyy)- (a) - a²)
and thus,
T
(1 -1 .y) Tyy
E e
a
la - aa'
T
The comparison of this bound to is self-evident. The main difference is that we have replaced max (1 0n, 01 } with [ai a= This arises from the fact that a" (0, 1) is arbitrary and thus
max (1 - 01, 01 } is the best possible upper bound on (oj a²). I. So, we view Proposition 4. as both agnostic guarantee that shows that method gives the correct long-term empirical coverage frequency irrespective of the true data generating process, and as an approximately tight bound on the worst-case behaviour immediately after initialization.
TTii last assumption is in general only true if Qe(-) and a fit independently of another.

---

4.2 Performance in hidden Markov model
Although we believe Proposition 4.1 is an approximately tight characterization of the behaviour after initialization, we can still ask whether better bounds can be obtained for large time steps. In this section we answer this question positively by showing that if a is initialized appropriately and the distribution shift is small, then tighter coverage guarantees can be given. In order to obtain useful results we will make some simplifying assumptions about the data generating process. While we do not expect these assumptions to hold exactly in any real-world setting, we do consider our results to be representative of the true behaviour of adaptive conformal inference and we expect similar results to hold under alternative models.
4.2.1 Setting
We model the data coming from a hidden Markov model. In particular, we let {Athen S A denote the underlying Markov chain for the environment and we assume that conditional on {AtHEEN {(X,, Jee is an independent sequence with (X,; Ya) ~ PA, for some collection of distributions {Pa : a E A}. In order to simplify our calculations, we assume additionally that the estimated quantile function (.(-) and score function S-(-) do not depend on and we denote them by Q() and S(.). This occurs for example in the split conformal setting with fixed training and calibration sets.
In this setting, {(a,, hee forms a Markov chain on |-7, 1 + x A. We assume that this chain has unique stationary distribution и and that (4) ~ х. This implies that (at, A,, err,) is a stationary process and thus will greatly simplify our characterization of the behaviour of err, While there is little doubt that the theory can be extended, recall our that main goal is get useful and simple results. That said, what we really have in mind here is that {Ar]eeN is sufficiently well- behaved to guarantee that (ax: Ac) has a limiting stationary distribution. In Section A.5 we give an example where this is indeed provably the case. Lastly, the assumption that (a), A1 π is essentially equivalent to assuming that we have been running the algorithm for long enough to exit the initialization phase described in Section
4.2.2 Large deviation bound for the errors
Our first observation that emr, has the correct average value. More precisely, by Proposition 4. we
have that lim T-1 Σ err, a.s. a and since err, is stationary it follows that E(err,] = a. Thus,
to understand the deviation of T-1 ΣT 1= err, from a we simply need to characterize the dependence structure of (err, heN.
We accomplish this in Theorem which gives a large deviation bound on 7 Σd_ 1= emr, - al. The idea behind this result is to decompose the dependence in (err)her into two parts. First, there is dependence due to the fact that a₁ is a function of (err, Jisrsts-s-- In Section A.7 in the Appendix we argue that this dependence induces negative correlation and thus the errors concentrate around their expectation at a rate no slower than that of an i.i.d. Bernoulli sequence. This gives rise to the first term in (6). which is what would be obtained by applying Hoeffding's inequality to i.i.d. sequence. Second, there is dependence due to the fact that A, depends on A,-1- More specifically, consider setting in which the distribution of Y|X has more variability in some states than others. The goal of adaptive conformal inference is to adapt to the level of variability and thus return larger prediction sets in states where the distribution of Y|X X is more spread. However, this algorithm is not perfect and as a result there may be some states a E A in which Eferr, A = a] is biased away from a. Furthermore, if the environment tends to spend long stretches of time in more variable (or less variable) states this will induce a positive dependence the errors and cause 7-1 T-' Σ err, to deviate from To control this dependence we use a Bernstein inequality for Markov chains to bound T DT=1Eeen [A,] - al. This gives rise the second term in
Theorem 4.1 Assume that {Ar) has non-zero absolute spectral gap 1) > 0. Let
B = sup A = a) d]-al aal and oB := ([ Ar] ) aAA
Then,
T
T(2 a 2 22ep (-8)
T(1 n))²
PPP
emT
2exp
8(1 + 7) 2/ + 20
(6)
7

---

A formal proof of this result can be found in Section A.7 The quality of this concentration inequality will depend critically on the size of the bias terms B and B- Before proceeding, we emphasize that the definitions of B and o are independent of the choice of l owing to the fact that (as,, Ar, err)) is assumed stationary. Now, to understand these quantities, let
important that
M(paa == , Yi) > Q(1 - -) = a)
denote the realized miscoverage level in state E A obtained by the quantile Q(1 - p). Assume that M(pla) is continuous. This will happen for example when Q(-) is continuous and S(X,, Y.)l continuously distributed. Then, there exists an optimal value o such that [(aaaa = a. Lemma A.4 in the Appendix shows that if in addition M-laa admits second order Taylor expansion, then
B C (7 (++ sup sup ElJa - -AA, =a] and o B².
aEAKEN
Here, the constant C' will depend how much M (-la) differs from the ideal case in which Q(-) is the true quantile function for S(X,, AA In this case we would have that M (-Ja) is the linear function (pla) p. Vp E [0, 1] and C' 2.
We remark that the term El4. the size of the distribution shift in terms of the change in the critical value az Thus, we interpret these results as showing that if the distribution shift is small and Ya E A, Q(-) gives reasonable coverage of the distribution of (X,, Y.) A, = a, then 7-1 Σ err, will concentrate well around a.
AA al can be seen as a quantitative measurement of
4.2.3 Achieving approximate marginal coverage
Theorem bounds the distance between the average miscoverage rate and the target level over long stretches of time. On the other hand, it provides no information about the marginal coverage frequency at a single time step. The following result shows that if the distribution shift is small, the realized marginal coverage rate M (t))At) will be close to on average.
Theorem 4.2 Assume that there exists constant L > O such fhttfor all and all a1, 02 E R.
[M(azaa) M(aala)] < L -al-
Assume additionally for all A there exists o (0, 1) such that (aaaaa a. Then,
L E[(M(a,)A)) a) L(1 + 7) Bla'A. a'A,l n
7
Once again we emphasize that holds for any choice of t owing to the fact that (a,, Ac, emr,) is assumed stationary and thus the quantities appearing in the bound are invariant across f. Proof of this result can found in Section A.8 of the Appendix. We remark that the right-hand side of minimized by choosing
7
(2 o A 11
a 1)) which gives the inequality
E (MM
a) L(VE V BBlaa - a
As above we have that in the ideal case Q(-) is perfect estimate of the quantiles of S(X,, Ar and thus (pla) and L = 1. Moreover, we once again have the interpretation that BI[a A
at, is a quantitative measurement of the distribution shift. Thus, this result can be interpreted as bounding the average differennce between the realized and target marginal coverage in terms of the size of the underlying distribution shift. Finally, note that the choice & = (2BlIa l)) 1/2 formalizes our intuition that y should be chosen to be larger in domains with greater distribution shift, while not being so large as to cause az to be overly volatile.
5 Impact of Sz(-) on the performance
The performance of all conformal inference methods depends heavily on the design of the conformity score. Previous work has shown how carefully chosen scores even explicit optimization of the

---

Acaptve Ajpha
Fived Alpha
Bernoull Sequence
Nvidia
Local Coverage Level
0.4
64-
BlackBerry
Local Coverage Level
0.-
0.-
84
206
2010
3610 2016 2000
Figure Local coverage frequencies for adaptive conformal (blue), non-adaptive method that holds O₂ = a fixed (red), and i.i.d. Bernoulli(0.1) sequence (grey) for the prediction of stock market volatility with conformity score Š, The coloured dotted lines mark the average coverage obtained 0.9.
across all time points, while the black line indicates the target level of
interval width can be used to obtain smaller prediction sets [e.g. 28
Adaptive conformal Sz(.) and quantile function Q+(-) and thus can be
29
20
inference work with any conformity directly combined with other improvements in conformal inference to obtain shorter intervals. One important caveat here is that the lengths of conformal prediction sets depend directly the quality of the fitted regression model. Thus, to obtain smaller intervals one should re-fit the model at each time step using the most recent data to build the most accurate predictions. This exactly what and
have done in our experiments in Sections
In addition to this, the choice of S.(-) can also have direct effect the coverage properties of adaptive conformal inference. Theorems and 4.2 show that the performance of adaptive conformal inference is controlled by the size of the shift in the optimal parameter at across time. Moreover, of itself is in one-to-one correspondence with the 1 - a quantile of S, (X,,, Yi). Thus, the coverage properties of adaptive conformal inference depend how close S, Y)) is to being stationary.
For simple example illustrating the impact of this dependence, note that in Section prediction sets using the conformity score
we formed
S, V of
o7
An priori reasonable alternative to this is the unnormalized score
S, V -
However, after a more careful examination it becomes unsurprising that normalization by of is critical for obtaining an approximately stationary conformity coverage properties. Figure 2 shows the local coverage frequency (see of adaptive conformal inference using $, In comparison to Figure ! the coverage now undergoes much wider swings away from the target level of 0.9. This issue can be partially mitigated by choosing larger value of yy that gives greater adaptivity to the algorithm.
and thus S, leads to much worse
Real data example: election night predictions
During the 2020 US presidential election The Washington Pos/ used conformalized quantile regression (CQR) (see T and Section LJ to produce county level predictions of the vote total on election night Here replicate the core clements of this method using both fixed and adaptive quantiles.

---

Adaptive Alpha
Fixed Alpha
Bernoulli Sequence
Local Coverage Level
0.079
VPL
0.825
500
1000
1500
2000
Time
Figure 3: Local coverage frequencies of adaptive conformal (blue), a non-adaptive method that holds 0₂ a fixed (red), and i..dd Bernouli((..) sequence (grey) for county-level election predictions. Coloured dotted lines show the average coverage across all time points, while the black line indicates 0.9.
the target coverage level of
To make the setting precise, let 1Yihs denote the number of votes cast for presidential candidate Joe Biden in the 2020 election in each approximately T 3000 counties in the United States. Let X₁ denote set of demographic covariates associated to the tth county. In our experiment X, will include information on the make-up the county population by ethnicity, age, sex, median income and education (see Section AA.6.] for details). On election night county vote totals were observed as soon as the vote count was completed. If the order in which vote counts completed was uniformly random {(x,, Yi)l would be exchangeable sequence standard conformal inference methods. In reality, larger urban counties tend to report results later than smaller rural counties and counties the coast of the US report earlier than those the west coast. Thus, the distribution of (X,, Y,) can be viewed as drifting throughout election night.
which we could run
We apply CQR predict the county-level vote totals (see Section A.6.2 for details). To replicate the east to west coast bias observed on election night we order the counties by their time zone with eastern time counties appearing first and Hawaïian countics appearing last. Within each time zone counties are ordered uniformly at random. Figure shows the realized local coverage frequency over the most recent 300 counties (see for the non-adaative and adaptive conformal methods. We find that the non-adaptive method fails to maintain the desired 90% coverage level, incurring large troughs in its coverage frequency during time zone changes. On the other hand, the adaptive method maintains approximate 90% coverage across all time points with deviations its local coverage level comparable what is observed in Bernoulli sequences.
7 Discussion
There are still many open problems this area. The methods we develop are specific to cases where Y, is revealed at each time point. However, there many settings in which we receive the response delayed fashion or large batches. addition, our theoretical results Section 4.2 are limited to single model for the data generating distribution and the special case where the quantile function Q.(.) is fixed across time. It would be interesting determine if similar results be obtained in settings where Qe(-) is fit in an online fashion on the most recent data. Another potential area for improvement is in the choice of the step size 7. In Section 2. we give some heuristic guidelines for choosing 7 based on the size of the distribution shift in the environment. Ideally however we would like to be able determine 7 adaptively without prior knowledge. Finally, our experimental results are limited to just two domains. Additional work is needed determine if our methods can successfully protect against wider variety of real-world distribution shifts.
10

---

8
Acknowledgements
E.C. supported by Office of Naval Research grant N00014-20-12157, by the National Science Foundation grants OAC 1934578 and DMS 2032014, by the Army Research Office (ARO) under grant W91 INF-17-1-0304 and by the Simons Foundation under award 8 814641. We thank John Cherian for valuable discussions related to Presidential Election Night 2020 and Lihua Lei for helpful comments on the connection online learning.
References
[1] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias: There's software used across the country to predict future criminals. and it's bi- URL
http://wwwwpppopbiica.cca proppblica..rg//rtiicc.... ased against blacks, 2016. -tw.---rmmmmll--sttttttiiia
machine-bias
[2] Claudine Badue, Rånik Guidolini, Raphael Vivaequa Carneiro, Pedro Azevedo, Vinicius B. Cardoso, Avelino Forechi, Luan Jesus, Rodrigo Berriel, Thiago M. Paixão, Filipe Mutz, Lucas de Paula Veronese, Thiago Oliveira-Santos, and Alberto F. De Souza. Self-driving cars: A survey. Expert Systems with Applications, 165:1 13816, 2021. ISSN 0957-4174, doi: https:
1tool.or//1.1001/..sswww.. 133816. https:tt: www.ncedirectt.c..mcmmcmm ccm/ncinnce/ /tt.cc/e/p11//005777740000000000
[3] Rina Foygel Barber, Emmanuel Candès, Aaditya Ramdas, and Ryan J. Tibshirani. Predictive inference with the jackknife+. The Annuls of Statistics, 49(1):486 - 507, 2021. doi: 10.1214/
A0-AOS1965. URL httpp:tts////oiorr
1tt..//../...///00..... 1214/20-1--1 ADS1965
[4] Tim Bollerslev. Generalized autoregressive conditional heteroskedasticity Journal of Econometrics, 31333307--327,
1986. ISSN 0304-4076.
doi: htpp:///oi.org/100.
0304-4076686)90066-- URL
p11/08004006866906631
[5] United States Census Bureau. County characteristics resident population espiaatioonsssimmttssss, 2019. data retrieved from https://rm //www. www.ss.cccsuuueeeeee
2010s-counties-eee det.esddetail.heee html
[6] United States Census Bureau. 2015-2019 american community survey 5-year average county- level estimates, 2019. data retrieved from /tttps://www..... Suunry--lrrr--dttt-settt//oodod
[7] United States Census Bureau. Small area income and poverty estimates: 2019, 2019. data retrieved from https://www.cr ers. usda. www..ua.ooo/aatta-rooeeeeeeeeeee
Soanty-leeel-dat--See wttpttss/dooooaadd-odm
(8) Emmanuel J. Candès, Lihua Lei, and Zhimei Ren. Conformalized survival analysis. arXiv
preprint, 2021. arXiv:2103.099: 03.6666..
[9] X. Cao, J. Zhang, and H. V. Poor. On the time-varying distributions of online stochastic optimization. In 2019 American Control Conference (ACC). pages 1494-1500, 2019. doi: 10.23919/ACC.201 11119998888899
[10] Maxime Cauchois, Suyash Gupta, Alnur Ali, and John C. Duchi. Robust validation: Confident predictions even when distributions shift. arXiv preprint, 2020. arXiv:2008.0444 044667.
[11] Maxime Cauchois, Suyash Gupta, and John C. Duchi. Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction. Journal of Machine Learning Research, 22(81 11:1))11422, 2021. URL http://jmlr
753. html
[12] Haoxian Chen, Ziyi Huang, Henry Lam, Huajie Qian, and Haofeng Zhang. Learning prediction intervals for regression: Generalization and calibration. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 820-822 828. PMLR, 13-15 Apr 2021.
[13] John Cherian and Lenny Bronner. How the washington post estimates outstanding votes for the 2020 presidential election. https://elex-mooeee www.mmodddldddd..ee-eeom- s3. amazonaws com/ 2020- tttpgraa/rmrrrttppeleeeetttooooo httprrioooooooeeeeerreeueeppppp
2020.
[14] MIT Election Data and Science Lab. County Presidential Election Returns 2000-2016, 2018.
URL https://doi. 10. /tt.:////////.../0//////////

---

[15] Rina Foygel Barber, Emmanuel J Candès, Aaditya Ramdas, and Ryan J Tibshirani. The conditional predictive inference. Information and Inference: Journal of the IMA, 08 2020. ISSN 2049-8772. doi: 10.1093/imaial/naa001.. URL https //doi.org/10 1093/
limits of distribution-
httpg//....00//mmaaaaaaaaaaa /maiai/iaaa011 iaaa017.
[16] Alexander Gammerman and Vladimir Vovk. Hedging predictions in machine learning. The Computer Journal, 10-2):151-163,, 2007. doi: 10. 10.100//omjn///x0065.
[17] Elad Hazan. Introduction to online convex optimization.
arXiv preprint, 2019.
arXiv:1909.05200
[18] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30) 1963. doi: 10.1080/01621459.1966
10500830.
[19] Bai Jiang, Qiang Sun, and Jianqing Fan. Bernstein's inequality for general markov chains. arXiv preprint, 2020. arXiv: 1rXiv:1805.10 1e01118000.....
[20] Danijel Kivaranovic, Kory D. Johnson, and Hannes Leeb. Adaptive, distribution-free prediction intervals for deep networks. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 4346-4356. PMLR, 26-28 Aug 2020.
[21] Danijel Kivaranovie, Robin Ristl, Martin Posch, and Hannes Leeb. Conformal prediction intervals for the individual treatment effect. arXiv preprint, 2020. STti::2000001447..
[22] Jing Lei and Larry Wasserman. Distribution- free prediction bands for non non-parametrie regression. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 76, 01 2014. doi: 10.1111/rssb. 12121
[23] Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry Wasserman. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 1 11365233:1094411111 2018. doi: 1118000661449922171111111 https://doi. http::://doooor/1100 110.11111...0011115.1.... 10771
URL
[24] Lihua Lei and Emmanuel J. Candès. Conformal inference counterfactuals and individual treatment effects. arXiv preprint, 2021. arXiv:2006.061138.
[25] David Leip. Dave leip's atlas of u.s. presidential elections., 2020. http::/useeeectionat.
org
[26] Harris Papadopoulos. Inductive conformal prediction: Theory and application to neural net- works. Tools Artificial Intelligence, pages 315-330, 2008
[27] Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In Tapio Elomaa, Heikki Mannila, and Hannu Toivonen, editors, Machine Learning: ECML 2002, pages 345-356, Berlin, Heidelberg. 2002. Springer Berlin Heidelberg. ISBN 978-3-540-36755-1
[28] Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regres- sion. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Gar- nett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httpps//prroeeedings 254.:64440004444111166666666ee
pdf
[29] Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. In Advances in Neural Information Processing Systems, volume 33, pages 3581 35911 2020. URL atttps:/pproceedingss 244cd778850811602776663 0owerr/07555555-555 .pdf
[30] Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adap- tive coverage. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, ed- itors, Advances in Neural Information Processing Systems, volume 33, pages 3581-3591. Curran Associates, Inc., 2020. URL httl/hhhppe//pppcccegggggeeenppp .tceurr/ps.ccppppe///0000
.pdf
[31] Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous vallll classifiers with bounded error levels. Journal of the American Statistical 11450)2000001111225222222333333 2019. doi: 1201080006224459200772
URL htR.sttts:...m http:///000.....//a/////////////
1395841
12

---

[32] Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(12):31--21, 2008. htL.apppp//mmrrrorrr/ppa/rr///// er
html
[33] Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal prediction under covariate shift. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc,
E. Fox, and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httpss/pprocceddnngggg
pdf
[34] Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in a Random
World. Springer-Veriee Berlin, Heidelherg, 2005. ISBN 0387001522.
[35] Jingyi Zhu and James Spall. Tracking capability of stochastic gradient algorithm with constant gain. 2016 IEEE 55th Conference on Decision and Control (CDC), pages 4522-4527, 12 2016. doi: 10. RtL.L////DC...1..7999999999
13


Reviews:
[{"review_id": "sWmLG5ebdWu", "reviewer": "Reviewer_vCi2", "summary": "This paper provides a method for calibrating prediction sets in an online setting. The method adjusts the level of an underlying conformal prediction algorithm according to the number of miscoverage events observed previously in the trajectory. The authors prove that the empirical miscoverage rate never exceeds the desired level, regardless of the data-generating distribution at each step. The authors also provide an additional analysis of the tails of the empirical empirical error count in the setting where the data-generating distribution is a hidden Markov model (confirming that several intuitions apply in this case), as well as two applications involving real data.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is cleanly written, and easy and enjoyable to read. The idea is interesting, and the strong guarantee provided by Proposition 4.1 in general settings is very nice. The results in section 4.2 nicely confirm several intuitions presented earlier in the paper.  Finally, the two real-world examples seem worthy and interesting applications, and additionally show some interesting failure modes of existing conformal prediction methods.\n\nThe empirical results provided, while thought provoking, could be improved by providing some details as to what the actual prediction intervals returned by the method look like (as opposed to just the miscoverage rates). This seems crucial given the generality of the method, which Proposition 4.1 shows would be correct (i.e. would produce the specified miscoverage rates) even if $\\hat{Q}_t$ were a very poor approximation to the true quantile function.\n\nSeparately, while overall the paper is extremely well-written, I found the final paragraph of section 4.1 a little confusing. At a low level, my own calculations suggest the left-hand side of the equation under line 192 should be\n$$\n\\mathbb{E}[\\mathrm{err}_t] - \\alpha\n$$\ninstead of what is written, and the right-hand side of the equation under line 193 should\nbe\n$$\n\\frac{1 - (1 - \\gamma)^T}{T \\gamma}|\\alpha_1 - \\alpha|\n$$\ninstead of what is written (unless I have made a mistake).  I then do see an underlying similarity between the resulting bound and the right-hand side of (5), but I didn't understand the relationship between $\\mathrm{max}\\{\\alpha_1, 1 - \\alpha_1\\}$ and $|\\alpha_1 - \\alpha^\\ast|$ described (although I agree that the latter is an upper bound to it).\n\nFinally, minor typos:\n\n* Line 48 -- \"points predictions\"\n* Equation under line 181 -- $\\infty$ should be $-\\infty", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors include an interesting and broad discussion of the limitations of their method. They do not discuss potential negative societal impact, but their justification for not doing so in the Checklist seems reasonable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "lzuVcIjkkOX", "reviewer": "Reviewer_2Sne", "summary": "In this paper, the authors introduce an extension to (split) conformal prediction under distributional shift over time known as adaptive conformal inference (ACI). Instead of relying on exchangeability, the method relies on tracking a scalar parameter $\\alpha_t$ which compensates for the discrepancy between the empirical miscoverage and target miscoverage $\\alpha$. The authors provide theoretical coverage guarantees on long-run error rates under weak assumptions, and further provide concentration inequalities and single time coverage guarantees under stronger Markov conditions. The adaptive method is compared to usual conformal prediction on two examples.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nI really enjoyed reading this paper. The writing is very clear, and the authors provide clear intuition for the theoretical results.  Although the method is simple, relying on adapting the miscoverage level $\\alpha_t$ in an online manner instead of exchangeability is novel. The method remains very general like regular conformal prediction, requiring only a predictor. The generality of the theoretical results is also impressive, as the assumptions are quite weak for Section 4.1 and the Markov setup of Section 4.2 is sufficiently complex. The Propositions/Theorems are also easy to interpret.  The experiments convincingly demonstrate the correct coverage achieved by ACI under time-varying distribution shift, and the role of the sequence $\\alpha_t$ is easy to interpret. The empirical results match nicely with theory in terms of long-run coverage. \n\n#####################################################################\n\nWeaknesses/Questions:\n\nI only have minor suggestions:\n\n1.) In the discussion, it may be worth including a brief discussion on the empirical motivation for a time-varying $\\hat{Q}_t$ and $S_t$, as opposed to a fixed one as in Section 4.2. For example, what is the effect on the volatility of $\\alpha_t$ and also on the average lengths of the predictive intervals when we let $\\hat{Q}_t$ and $S_t$ vary with time?\n\n2.) I found the definition of the quantile a little confusing, an extra pair of brackets around the term\n\\begin{equation}\n\\left(\\frac{1}{|\\mathcal{D}|} \\sum_{\\left( X_r,Y_r\\right)\\in \\mathcal{D}} \\mathbf{1}_{S(X_r,Y_r) \\leq s}\\right)\n\\end{equation}\nmight help, or maybe defining the bracketed term separately if space allows.\n\n3.) I think there are typos in Lines 93, 136, 181 (and maybe in the Appendix too): should it be $\\hat{Q}_t(1-\\alpha_t)$ instead?\n\n\n#####################################################################\n\nOverall:\n\nThis is a very interesting extension to conformal prediction that no longer relies on exchangeability but is still general, which will hopefully lead to future work that guarantees coverage under weak assumptions. I believe the generality also makes this method useful in practice.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have described the limitations of their theory, e.g. having a fixed $\\hat{Q}$ with time.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "e_fY4FngRCF", "reviewer": "Reviewer_jzW6", "summary": "This paper develops an online predictive inference technique motivated by conformal inference. The proposed method achieves the target coverage rate ($1-\\alpha$) as $T \\to \\infty$. For finite $T$, the coverage is at most $O(1/T)$ away from $1-\\alpha$. Experiments on two real datasets illustrate that the method exhibits improved behavior as compared to a non-adaptive baseline.\n\nI feel that the main insight/contribution of the paper is to draw an elegant connection between two apparently disjoint areas, namely 1) post-hoc uncertainty quantification and 2) online learning. The methodology of the paper is mostly inspired from a post-hoc uncertainty quantification setup inherent in split conformal, where some part of the model is treated as 'fixed' and only a few parameters are optimized towards some goal (in this case, a single parameter, the quantile level $\\alpha_t$ is learnt). On the other hand, the theoretical analysis is very different from other conformal papers. It is in the adversarial setting and the technical tools used are similar to those used in the online learning literature. \n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As mentioned above, I think that the work is an original and significant contribution to the conformal literature. The experiments, although not extensive, nicely supplement the theory. Being quite familiar with conformal inference, I found the paper easy to follow (except the theorems in Section 4.2; see more below). However, I felt that the paper lacked a certain 'attention to detail' or 'polish' that the technical ideas are highly worthy of. I have made some suggestions below. \n\n_Major comments regarding writing:_\n- Line 30: This is not true for many recently popular conformal techniques: jackknife+ [1], cross-conformal [2], and out-of-bag conformal [3], all of which (roughly) get $1 - 2\\alpha$ coverage. Please update or qualify this claim. \n- Section 4.2: I was unable to really understand Theorems 4.1 and 4.2 due to the little t's which are not qualified as part of the statement. I am not sure what the expectation is over in defining $B$ and $\\sigma_B$. Similarly I am not sure what the expectation is over on the LHS and RHS of eq. (7). Could the authors please clarify this? \n- Line 279: Since Neurips is an international conference, I believe it should be specified that the authors mean the 2020 United States of America presidential election. The description of the dataset (until line 291) strongly assumes that the reader is familiar with the US election system: Who is Joe Biden? What is election night? The west (east) coast of what? \n\n_Minor/subjective comments:_\n- I felt that the paper was heavy on notation, which could be overwhelming for readers unfamiliar with conformal inference. The authors can consider reducing notation in order to reach a larger audience. I also propose a different way of looking at the algorithm proposed by the authors in the next section, which would probably require less notation. \n- Section 2.2: I felt that this section broke the flow of the rest of the paper \n- Title of Section 4.1: what is the meaning of 'general results'? \n- Line 221: “there is little doubt that the theory can be extended, recall our main goal [is] to get useful and simple results”: Did the author mean to say that it is unlikely that the theory can be extended to practical settings? What they have said conveys the opposite meaning (there is no doubt that the theory can be extended to practical settings).\n- Initially the subscript to M denotes ‘time’. Later, in Theorem 4.2, it denotes ‘action’. I suggest using slightly different notation (such as bracketing) for the two. \n\n**_A reinterpretation of the methodology proposed in the paper_**:\n\nI had a reinterpretation of the method proposed by the authors, based on 3 technical tools: pinball loss [4], online subgradient descent [5], and nested conformal [3].\n\nFirst, for any time i, define a family of nested sets ${F_t}$ based on [3]; such a family can be defined for any nonconformity score. Then define $ t_i := \\inf t: Y_i \\in F_t(X_i)$. Suppose $F_{s_i}$ is the predicted prediction set at time step i, then for $1-\\alpha$ coverage, what is needed is that $s_i \\geq t_i$, at least $1-\\alpha$ of the times. In other words, for optimal coverage, **$s_i$ should be the $1-\\alpha$ quantile of $t_i$**. A popular way to optimize for quantiles is to use the pinball loss. The proposed method (2) optimizes $\\sum_{i=1}^T \\text{pinball-loss}(1-\\alpha,s_i, t_i)$ using online subgradient descent.\n\nDo the authors agree with this interpretation? If yes, including it would enhance the paper, maybe even in an Appendix. I personally found this to be a cleaner way to understand the main idea: it requires less notation and alludes to other ideas that readers may already be familiar with. \n\n_References:_\n\n[1] https://arxiv.org/abs/1905.02928\n\n[2] http://proceedings.mlr.press/v91/vovk18a.html\n\n[3] https://arxiv.org/abs/1910.10562\n\n[4] http://www.econ.uiuc.edu/~roger/research/rq/QRJEP.pdf\n\n[5] https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "To the best of my understanding, the approach proposed does not guarantee that C_T(\\alpha_T) has 1-\\alpha coverage for a fixed time T, no matter how large T is. Proposition 4.1 only holds on _average_ across time. The authors make the following claim in the abstract, \"our adaptive approach provably achieves the desired long-term coverage frequency irrespective of the true data generating process\". I think that this claim needs to be (transparently) supplemented with the limitation described above. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "PLMb1lpFSx", "reviewer": "Reviewer_apoZ", "summary": "The paper proposes a conformal inference based technique that is an online adaptation to handle distribution shifts over time that has statistical guarantees for coverage of predictive distributions. The technique discretizes the updates and adapts marginal coverage with respect to limitations observed in prior steps. The authors demonstrate its usage in predicting market volatility and 2020 presidential elections.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The authors propose an online adaptation of conformal inference to handle distribution shifts. There have been work on this front by Tibrishani  et al. and Cauchois et al. which were cited but I found the comparison of the proposed technique with respect to these techniques limited. The novelty on top of conformal quantile regression can be argued to be minimal and the authors propose a simple modification of these techniques to propose an online version. This modification is a well-known adaption of various techniques in general. \n\nQuality: The paper provides theoretical analysis of the claims; however, I think there is a bit of a room for improvement in experimental results through comparisons with prior work. \n\nClarity: The paper is very well written and organized.\n\nSignificance: Online extension of conformal inference provides an interesting research direction. However, the models used in practice are generally frequently trained. Applying the adaptive version proposed in this paper on frequently trained models can still be applicable but the paper is lacking the experiments that provides comparisons to illustrate the added benefit of applying adaptive conformal inference in such scenarios. I think these additions would further validate the significance of the proposed approach.\n\nSpecific comments:\n-\tI think comparisons with respect to online trained models would be a highly important comparison to support the general usability of this technique. \n-\tI would recommend comparisons with respect to prior work that is already cited. For instance for the experiments with election results, the assumption of conditional distribution being constant between training and test sets by Tibrishani et al. is a valid assumption and it would have been interesting to see the predictions in comparison.\n-\tThe proposed method is effective if the distribution shift happens gradually so that it is able to maintain it’s coverage over the shift period. The method will provide coverage guarantees when this change does not happen abruptly. This might be an important limitation to mention in the paper and discuss extensions. \n-\tThe paper focuses on marginal coverage but conditional coverage (https://arxiv.org/pdf/2006.02544.pdf) is an important metric to illustrate statistical properties. If shown to have nice properties, this might make the results more powerful. I would recommend adding results with conditional coverage as well which will make the results more compelling.\n-\tPlease comment on the jump from 84% to 95% local coverage level for Figure 2a.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the limitations in the manuscript. I also provided more suggestions above to further enhance this discussion.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "GPggXmmVP1j", "reviewer": "Reviewer_uBLA", "summary": "This paper proposes a method for online adaptive conformal prediction, where the data generating distribution is unknown, and varies over time. Conformal prediction is a distribution-free uncertainty quantification methodology that forms prediction sets $\\hat{C}$ for an input $X$ such that the response variable $Y$ is covered with probability $1 - \\epsilon$. (This is similar in spirit to confidence intervals.) The foundational assumption supporting the majority of conformal inference techniques is exchangeability of calibration data and test data. This work departs from that limiting assumption, and develops a simple but rigorous approach that models continual distribution shift over time. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "=== Strengths ===\n\n- The paper is well-written, clear, and well-motivated. Distribution drift can be a significant issue in many real problems, and therefore adaptive confidence algorithms that can account for this are necessary.\n\n- The main algorithm of the paper is simple and easy to implement (which is a strength!). It reminds me of proportional control for PID controllers, though the analysis and applications differ.\n\n- The experiments are interesting and clearly real world tasks, that also clearly have distribution shift. This is great for illustrating to the community examples of problems the proposed approach helps solve. Empirically, the adaptive technique here performs well (especially compared to non-adaptive baselines that can fail catastrophically).\n\n- The extended analysis in the hidden Markov model in Section 4.2 is helpful in illustrating what sort of performance we might be able to expect on a more precise level (as the guarantee in Section 4.1 is somewhat loose).\n\n=== Weaknesses/Limitations ===\n\n- The main drawback is that without further assumptions (such as those modeled in 4.2), we only have asymptotic control of the average error. In intermediate time intervals, we might have very conservative or anti-conservative predictions. That said, the theory in Section 4.2 is helpful in giving some intuition on these aspects, combined with the positive empirical results in Section 5.\n\n- Returning to the control theory view, I wonder if it would be helpful to incorporate full PID control to achieve better dynamics (i.e., more quickly adjusting to sudden, but permanent shifts in distribution, or alternatively, dampening out adjustments due to outlier disturbances).\n\n- The assumptions that this paper makes are minimal, which makes the possible approaches fairly limited. Though I agree that it would be out of the current scope, it would be interesting to see if some techniques from other recent distribution-shift conformal inference (e.g., Tibshirani et. al. and Cauchois et. al.) could be incorporated as part of the wrapped model to improve empirical performance. For example, if *batches* were observed at time t so that a flawed but decent likelihood ratio model could be fit (maybe with regularization on importance weights), perhaps the importance weighting technique of Tibshirani could be approximately used to improve estimation of $\\hat{Q}_t$.\n\n=== Justification for score ===\n\nI think that this paper would make a good contribution to the NeurIPS program.\n\n=== Minor comments ===\n- typo in the proof of Lemma A.2 (double note denote).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not forsee any negative societal impact (other than that inherited by the blackbox models the conformal inference package wraps). ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "9c_HGe2qNW", "reviewer": "Reviewer_SBVj", "summary": "This paper proposed an adaptive method to estimate a confidence set such that the target value falls into (conformal with) the set within a given probability. It adjusts the coverage level \\alpha_t in the current round t based on the error from previous rounds (see Eq.(2)). Empirical demonstrations on stock markets and the 2020 presidential election poll show that the proposed adaptive conformal inference (ACI) method can better reach the targeted coverage level than using a fixed alpha.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros\n- A straightforward method that is well-explained\n- Theoretical justification under certain assumptions\n\nCons\n- The theoretical analysis does not lead to practical guidance\n- Insufficient discussion and comparison with related papers\n\nDetailed comments\n\nOverall, it is an interesting paper demonstrating the possibility and advantage of using an adaptive method to handle distribution shifts in conformal inference. However, I have the following concerns.\n\n1. Regarding the theoretical analysis, it lacks practical guidance on choosing the step-size gamma. More specifically, the step size in Thm.4.2 relies on a future quantity that is unknown in practice. Given that the Markov chain is assumed to be mixed, wouldn't it be possible to derive a more practical choice of gamma based on the history?\n\n2. The current paper discussed the coverage but lacks a discussion on the interval width, which is also important in practice. For example, see Kivaranovic et al. (2020) and Chen et al. (2021), which provide more thorough treatment for the problem and it would be necessary to discuss/compare.\n\n- Kivaranovic, D., Johnson, K.D. and Leeb, H., 2020, June. Adaptive, distribution-free prediction intervals for deep networks. In International Conference on Artificial Intelligence and Statistics (pp. 4346-4356). PMLR.\n- Chen, H., Huang, Z., Lam, H., Qian, H. and Zhang, H., 2021, March. Learning prediction intervals for regression: Generalization and calibration. In International Conference on Artificial Intelligence and Statistics (pp. 820-828). PMLR.\n\n3. Empirical studies. \n\n- L145 mentioned that \"These stocks were selected out of a total of the 13 stocks that we examined because they showed a clear failure of the non-adaptive method\". However, it seems to me the non-adaptive alpha works fine for AMD. If ACI is indeed performing well for the rest out of 13 stocks, it would be helpful to see the actual improvement (maybe in Appendix) instead of simply claim it without evidence. \n\n- For the results in Fig.2, it would be informative to see the deviation from the ideal 0.9 as sigma changes for the two methods. Currently, only specific values are chosen and it is not clear why.\n\n- There is no comparison to competitive methods in the literature other than a fixed-alpha baseline. It would be more convincing if the proposed method can be compared to the methods mentioned in the above reference.\n\nMinors\n\n- Appendix A.2, it might be better to put both curves (using (2) and (3) respectively) in one figure so that they can be compared more directly.\n- The alpha in the GARCH(1,1) model (Equation below L127; also the \\hat{\\alpha}_t in L132) has a different meaning from the alpha in most parts of the paper (E.g., in L137), which is likely to confuse readers.\n- L294, sigma>0 should be sigma>=0 as seen in the leftmost of Fig.2.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an adaptive conformal inference (ACI) that relaxes the classical exchangeability assumption by leveraging the online learning framework, and proposes a simple algorithm that achieves the target coverage rate as the number of steps approaches infinity. There is a consensus among the expert reviewers, with which I also concur, that the main idea of combining conformal inference with online learning is novel and interesting, and that the paper provides a fundamental contribution to the field of conformal inference. Hence, I recommend an acceptance.

One of the reviewers raised the concern regarding experimental results, which I consider a minor point. Nevertheless, improving the clarity of this paper, e.g., by making the paper accessible to broader audience, and providing thorough discussion with respect to the related work, as suggested by the reviewers, will further increase the impact of this work. 

The authors provided a rebuttal which was also positively acknowledged by the reviewers.
Decision: Accept (Oral)