Multi-model Ensemble Conformal Prediction in Dynamic Environments
Authors: Erfan Hajihashemi
Yanning Shen
Venue: NeurIPS 2024 poster (2024)
Keywords: uncertainty quantification
conformal prediction
dynamic environments
Primary area: online_learning

Abstract: Conformal prediction is an uncertainty quantification method that constructs a prediction set for a previously unseen datum, ensuring the true label is included with a predetermined coverage probability. Adaptive conformal prediction has been developed to address data distribution shifts in dynamic environments. However, the efficiency of prediction sets varies depending on the learning model used. Employing a single fixed model may not consistently offer the best performance in dynamic environments with unknown data distribution shifts. To address this issue, we introduce a novel adaptive conformal prediction framework, where the model used for creating prediction sets is selected ‘on the fly’ from multiple candidate models. The proposed algorithm is proven to achieve strongly adaptive regret over all intervals while maintaining valid coverage. Experiments on both real and synthetic datasets corroborate that the proposed approach consistently yields more efficient prediction sets while maintaining valid coverage, outperforming alternative methods.

Multi-model Ensemble Conformal Prediction in Dynamic Environments
Erfan Hajihashemi
Department of Electrical Engineering & Computer Science University of California, Irvine ehaj www.hhhc..eeeee
Yanning Shen'
Department of Electrical Engineering & Computer Science University of California, Irvine yannings@uci.ee
Abstract
Conformal prediction is an uncertainty quantification method that constructs a prediction set for previously unseen datum, ensuring the true label is included with a predetermined coverage probability. Adaptive conformal prediction has been developed address data distribution shifts in dynamic environments. However, the efficiency of prediction sets varies depending on the learning model used. Employing single fixed model may not consistently offer the best performance in dynamic environments with unknown data distribution shifts. To address this issue, introduce novel adaptive conformal prediction framework, where the model used for creating prediction sets selected 'on the fly" from multiple candidate models. The proposed algorithm is proven to achieve strongly adaptive regret over all intervals while maintaining valid coverage. Experiments on real and synthetic datasets corroborate that the proposed approach consistently yields more efficient prediction sets while maintaining valid coverage, outperforming alternative methods.
Introduction
Most machine learning algorithm designs aim to enhance label prediction accuracy. Nevertheless, a significant challenge persists many models demonstrate limitations in predicting labels with high certainty, falling short of achieving the desired levels of accuracy and other critical evaluation metrics. In applications such as medical diagnosis, it sometimes
efficient predict subset of labels rather than a single label [Levy et al. 2021 Straitouri et al. 2023). This necessitates predicting set of candidate labels with valid coverage probability, rather than limiting to a single label.
One of the most widely used frameworks for set prediction conformal prediction [Vovk et al. 2005). Conventional conformal prediction algorithms
achieve the desired coverage assuming the exchangeability data (Baalaubraamniin et al.) 2014). However, in many real-world online problems, the distribution of data shifts over time, making the exchangeability assumption longer applicable. Consequently. adaptive conformal prediction algorithms have been developed (Gibss) and Candes [021], where prediction sets constructed in time-varying manner. Despite these advancements, the efficiency (e.g., prediction set size or regret) of previous conformal prediction methods in online settings with distribution shifts heavily depends the model employed, and
"Corresooning author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

single model may not consistently perform well across various distribution shifts. Creating an efficient prediction set size as important as obtaining the desired coverage. Trivial cases may arise where the prediction set alternates between an empty set and the full set of labels, with the full set being created with a probability equal to the desired coverage probability, and empty sets otherwise. This approach achieves the desired coverage but leads to impractical prediction sets [Bhatnagar et al.) 2023). To address this limitation, our proposed algorithm incorporates multiple learning models simultaneously. It dynamically selects the suitable model based on the performance of each model with the most recently received data.
Related work: Conformal prediction (Vovk et al. 2005 Shater and Vovk, 2008 Vovk 2015 is an effective method for uncertainty quantification that has been widely used to predict a set of candidate labels for income data. It treats the learning model as a black box and provides a prediction set for new test data. Conformal prediction is applicable in both Classification (Ding et al. 2024, Shi et al. 2013 Romano et al. 2020) and Regression [Romano et al., 2019 Papadopoulos et al. 201 Boström et al. 2017] problems. In dynamic environments where data distribution shifts over time, using vanilla conformal prediction algorithms may not lead to the desired coverage performance. To cope with this challenge, conformal prediction in dynamic environments has been studied recently. (Tibshirani et al. [019] explored conformal prediction for dynamic settings using a reweighting approach, but their method requires prior information about the data dependency structure; [Barber et al., 2023] resolved this dependency by requiring weights to be fixed. Incorporating varying coverage probability was introduced in [Gibbs and Candes 202T], but determining the appropriate step size remains a significant challenge. One way to address dynamic environments is adopting learning with expert advice (Cesa-Bianchi et al. 1997 Vovk 1995 Littlestone and Warmuth 1994). (Zaffran et al. 2022) suggested that tuning the step size based on expert (base learner) aggregation could be an effective strategy; however, this method causes each expert to receive equal impact from all historical data, which makes the algorithm unable to adapt sharp distribution shifts. Furthermore, (Gibbs) and Candès 2022] introduced an approach that employs multiple experts, each assigned a distinct step size from pool of candidate sizes, resulting in varying coverage probabilities each time t. While [Gibbs and Candès] [022] successfully demonstrated adaptive regret across time intervals of a fixed width, [Bhatnagar et al., 2023]] points out that this approach fails to achieve suitable regret across varying widths of arbitrary time intervals simultaneously. (Bhatnagar et al. 2023) addressed this limitation by establishing strongly adaptive regret (Daniely al.) 2015] across any arbitrary time interval width. Their proposed methodology assigns a specific time interval to each expert. Despite achieving sublinear strongly adaptive regret, the efficacy of this approach depends on the papee-parramter selection that determines each expert's 's lifetime. The proposed method in our study also employs experts who operate within specific time intervals. However, each expert consists of multiple learning models, aiming to select the appropriate model according to the specific data distribution during its operation, resulting in more efficient prediction sets.
Contributions. D) We introduce a novel adaptive conformal prediction algorithm. Strongly Adaptive Multimodel Ensemble Online Conformal Prediction (SAMOCP), designed for dynamic environments with unknown distribution shifts. This algorithm incorporates multiple models and dynamically selects a model based on its performance in previous time steps.
Overall, our contributions can be summarized as follows:
II We demonstrate that SAMOCP exhibits strongly adaptive regret for any arbitrary time interval while ensuring valid coverage.
III) Through experimental tests on classification tasks subject to distribution shifts, we demonstrate that SAMOCP outperforms existing methods by constructing more efficient prediction sets while also achieving a coverage probability closely aligned with the target value.
2 Preliminaries
This section explains standard conformal prediction and adaptive online conformal predictions, where data is collected sequentially. We begin with outlining standard conformal prediction. Given a miss coverage probability
learning model m historical dataset {(X y!!le) } and a new data X, E X, the objective is to construct a prediction set C.T (X,) C y == (1, 2, ...., K). where K denotes the total number of classes, such that CTh (X.) contains the true label Y!ue with probability
1 - a. In the online setting, historical dataset is updated to ((X,, ((re)) { at the end of each time t when true label y,true for input data X, is observed. In this scenario, conformal prediction treats

---

the historical dataset as calibration dataset, which is utilized to determine whether a candidate label Y E 3 should be included in the prediction set. Consequently, an online manner, conformal prediction relies on evolving calibration dataset, which contains all the historical data 'on the fly' to decide which candidate labels should be included in the prediction set. Non-conformity scores (5th(X,,, (imeee) ) are introduced. Specifically, each non-conformity score STn (X,, Y assesses the disagreement between the ground woound-truth label y and predicted label f (X,) Upon obtaining a new datum X,, the standard conformal prediction algorithm constructs the prediction set for X2 as C (Xe)= = (Y E y 1SST (T"(X,,, Y) 2 q% J. where the threshold da is obtained as
[1(1 - [[]1 (X,, Velre))) )
la = Quantile
t-1
The Quantile function sorts all non-conformity scores of the historical data and then identifies the [1(1 -a) |t smallest score as i= Note that 1 1 a is fixed, hence conformal prediction cannot readily cope with potential data distribution shifts in dynamic environments. Adaptive conformal prediction algorithms have been developed to address this issue, allowing the miss coverage probability to vary at each time and thereby enabling the algorithm to dynamically adapt to potential shifts in the distribution. In such scenario, 0 can be obtained by replacing with a; in I Then at each time step i, o₁ is updated after observing Y!rue.
Recent studies on online conformal prediction with distribution shifts have incorporated adaptive miss coverage probabilities to address dynamic environments. However, methods based on a single learning model may not achieve consistently reliable performance in dynamic environments. This underscores the necessity for employing multiple models and adaptive strategies to determine the appropriate model for each time L. To this end, in this work, we introduce novel adaptive multi- model online conformal prediction algorithm designed to identify the suitable learning model at cach time t within dynamic environments. At time slot t, the goal is to construct prediction set for the new data X₁, based on the historical dataset {(x,, ) such that the true label is included in the prediction set with probability a. The proposed algorithm for dynamic settings achieves strongly adaptive regret while ensuring valid coverage.
3 Methodology
In this section, two adaptive algorithms are developed for static and dynamic environments respec- tively. Subsection 3.I develops the Multimodel Ensemble Online Conformal Prediction (MOCP) algorithm to identify the suitable learning model among M distinct candidates in a static environment. Subsequently, in Subsection 3.2 we propose SAMOCP, an adaptation of MOCP tailored for dynamic environments with unknown distribution shifts.
3.1
Multi-model Conformal Prediction in Static Environments
Note that the non-conformity score 5Th (X,, Yttrue depends on the learning model. Such dependency leads to a model-specific ordering of non non-conformity scores, yielding different prediction sets for each model. After observing Y. Y:ras, the adaptive miss coverage probability a must be updated for time L +1 1 to cope with distribution shifts effectively. Given that different models achieve different prediction sets, assigning and updating the same a₁ for different models would be inadequate. Instead, at each time f, we assign a specific miss coverage probability to each model m E [M]. denoted as a,", and update based on the corresponding prediction set. Consequently, for M learning models, there are M candidates for miss coverage probability at at each time t. Each candidate is updated according distinct rule. These M update rules operate in parallel, with each one updating the corresponding miss coverage probability upon observing the true label. Next, the update procedure for at will be examined, followed by a detailed explanation of how each instance of MOCP selects the appropriate miss coverage probability from M distinct options at each time step. To update miss coverage probability a we adopt the pinball loss [Koenker and Bassett 1978.
which can be written as
L(a Th a.r)) = a(a ar)) - min(0,a - o."
(2)
where
a," supla Y.ruc e C (Xi))
(3)
3

---

is the best possible value of miss coverage probability for model m at time t which constructs the smallest prediction set that covers Y The miss coverage probability af+1 can be updated via SF-OGD OOraoona and Pál 2018 as
V aq Li L(a
( a4a)
0++1
m
m
(4)
Van [(a, (
where 1) is the learning rate and
Lam = 1[aa"' < <a," a err? a.
(5)
with err == [[(truue & C equals 1 if the predicted set does not contain the true label Y and O otherwise. According to the updating rule outlined in equation ( the adjustment of a at each time t is governed by the Var" L[āē" a,"" ), detailed in equation (5). When err?" 1, it signals that the coverage probability 1 - ot is too small, resulting in a prediction set that can not encompass Yıtue, Consequently, there's s necessity to enlarge the coverage probability, effectively achieved by reducing of which would be facilitated by ( given that the denominator in the second term is always positive and the gradient will be positive this scenario. On the other hand, when a,"h > a, 1 at"" leads to a prediction set that covers Y but also includes unnecessary labels Y" := (Y' E y I. < STH
5Tm (X,, Y') I Ia.- }. In such cases, optimization necessitates increasing at to avoid including unnecessary labels and output a more efficient prediction set. This adjustment is facilitated by the update rule (
Additionally, the weight w,"" is assigned to each model [M], which influences the selection of its corresponding miss coverage probability the performance of each model over previous time steps, reflected in w/" The algorithm updates the weight associated with each model after revealing the true label Yerue, This update is performed with respect the loss function of the corresponding miss coverage probability. Specifically, wit" can be updated by
learns which model to select over time based on
(6) where 0 < 1 is the step size. At each time t, upon receiving new data X,, MOCP first calculates the normalized weights, denoted as {w]] = For any m E [M], W,
w =w"" exp (-eL (a." oa?")
Σ
ensures that पā E [0. 1] and represents the likelihood of selecting miss coverage probability of"". Then, the algorithm selects miss coverage probability at", where i E [M]. according to PMF w. : ( m== i.c., each miss coverage probability a;" is selected with probability proportional to the corresponding normalized weight w,"" The prediction set for X, is constructed according to the threshold in ( by replacing a and m with at and vi respectively. After receiving Y/true each weight wi"h and miss coverage probability ax are updated according to (6) and (4), respectively. This The MOCP algorithm achieves a runtime of ((T) when
entire process detailed in Algorithm [ the number of models M is constant.
Given that the environment is static, there exists miss coverage probability that can minimize the loss function for each model m E [M] over [T'], denoted as a.. The best miss coverage probability among {a m2 m==1 can be obtained by
T Σ
m
Σ Ma, am) with am = arg min fa (
arg min
L(a
at").
ag"
The following theorem demonstrates that MOCP achieves sublinear regret (See proof in A.2)
Theorem Algorithm Machieves the following regret bound in a static environment
M
W. L(a!", a( Σ
Llar" aaa") a VT (1
27)²
+
+ +I M + (1+
(8)
21
20x
(=1
m=1
t=1
3.2 Multi-model Ensemble Conformal Prediction In Dynamic Environments
Through Algorithm I. we demonstrated how to select the suitable miss coverage probability of model that has achieved lower loss compared to other models over previous time steps. However,

---

Algorithm Multi-modde Ensemble Online Conformal Prediction (MOCP)
Require: a E [0, 1], learning rate 1) 2 0, and step size E (0, 1).
wf <- 37 (Initialization of weight for each model)
a1 t- a (Initialization of miss coverage probability for each model]
for E (T) do
Observe X₁ X.
Calculate normalized weights by wy" Σn "²"
Wi vm [M].
Select one of the miss coverage probabilities [ according to PMF w. (1o²") )
Observe true label Y Y/true and compute optimal value at Vm [M] with (3.
for m [M] do
Obtain loss L(a 0."
Update w with
Update a++1 with
end for end for
2
3
5 Time
8
3
Expert
Figure I: Expert creation over 5 time steps using lifetime formula 9 when 1. At each time f, an expert is created, marked by a filled circle to indicate start of the activity, and an unfilled circle to denote the end of the expert's activity.
this approach assumes a static environment that does not change over time, which may limit the algorithm's 's effectiveness in dynamic environments where data distribution shifts occur. In addition, the selection of stepsize in (6) critically affects the performance. In environments with unknown distribution shifts, large c indicates faster adaptation to abrupt changes, whereas small is more suitable for environments with less variability. Thus, the efficient choice of depends on the variability of the environment, which poses challenge in scenarios with unknown distribution shifts.
To address this limitation, we introduce Strongly Adaptive (SA) Specifically, each instance of MOCP is treated as an 'expert', and multiple experts are created at distinct time steps with specific step sizes and lifetimes to cope with potential distribution shifts. At the end its lifetime, the expert becomes inactive, ensuring that it no longer affects the decision decision-making process. refer to Figure for illustration. This strategy prevents outdated experts from contributing the selection of the suitable miss coverage probability in dynamic environments. Subsequently, SAMOCP dynamically selects the appropriate expert for each time and utilizes its chosen miss coverage probability to construct the prediction set. The lifetime of each expert is determined by the specific time t at which was created and hyperparameter g E N. as [Bhatnagar al. 2023)
A(t) max {2"h : = 0 mod 2"}. wEZ
(9)
The active interval of the expert created at time t is defined as [t, + A(t) 1]. Consequently, experts considered active at any given time 7 are those whose active intervals include т. In a dynamic setting with unknown distribution shifts, the best model may vary across different distributions. This variability results in scenarios where, at each time f, some active experts might not have adapted to the current data distribution yet, and thus they rely different models compared more recently established active experts. In such cases, the miss coverage probability of model m E [M] chosen by expert n at time represented fen and best possible value denoted as a To select the suitable miss coverage probability among different experts, assigned distinct weights to each,
5

---

with specific initialization and step sizes for updates. Specifically, this weight for expert n at time t is denoted as hy. and its step size is defined as e" := min(e, /x(a)"
where 1 constant and
X(2) is the lifetime for expert that obtained by 99 Given that nihh expert is activated at t = the
initialization and update rule for hy is as follows:
c"
ift= n
h
he exp (-E" rP) if [n, A(n) - 1)
(10)
0,
otherwise
where r?" = L(a og a - M(a "aa ax.".
represents the loss of the rith expert relative to the loss of the learner who selects expert ń. We denote the set of active experts each time as A(t). The learner selects the suitable miss coverage probability among all active experts according to the PMF he == (hς) )nE)(t), where each hī represents the normalized version of the weight hy calculated as hg
he Ai k3 ensuring that h2 E [o, 1]. Algorithm summarizes the SAMOCP method. It can be observed from ( that the maximum number of active experts (MOCP instances) at each time / is g Looog 4J. Hence, the complexity of SAMOCP of order O(T logg T).
Algorithm 2 Strongly Adaptive Multi-model Ensemble Online Conformal Prediction (SAMOCP)
Require: a E [0, 1J. hyperparameters 2 0, E (0, 1), and σ > 1. for t E [T'] do
Create new expert n (where L) by Algorithm
1 10--1:11 7/, <))
Remove experts whose lifetime has been finished.
Every active expert selects miss coverage probability from M options.
Calculate normalized weights by hi Eie A.
Select one miss overage probability from active experts according to PMF h, (ht (hf))eee A(0) Construct prediction set for X, using selected miss coverage probability. Observe true label ytrue.
for n E A(t) do
Obtain learner loss La at A.
Update every parameters assigned to each model for expert n via Algorithm 1 Update hi_ with (1O).
end for end for
Let CovF(T) = + E [errr)] a represent the coverage error. In a dynamic setting where multiple experts are incorporated, each including M miss coverage probabilities, the expected error is calculated E(err,] Σx ΣM ","""""rrr"" where mn represents the mtth model by expert n. Using the two following theorems, we prove that SAMOCP has bounded coverage error and achieves strongly adaptive regret across any time interval of arbitrary width (Proofs can be found A.3 and A.4).
Theorem 2 For any T 2 1 and any y E (2. Algorithm 2 achieves the coverage error bound
CovE(T) S 0 inf T (T+ (T+-++T~18,00))
(11)
where B,, (T') measures the smoothness of model weights within experts and the cumulative gradient normfor for each model within experts. The definition of (,(TT) is provided detail in equation (3I) in the Appendix A.3 If there exists y E (G) 1) such that (T) S Õ(T²) where 0 < 1 7;, then the
will be CT) < (T- (r-mmin3 10)+ or()..
coverage bound
Theorem Algorithm 2 achieves strongly adaptive regret over any interval 1 C [T] and positive constants A, B, as follows
Σ Σ NET nEA(())
h Wort mon I(aa at mm)
Σ M(ar"" mmm"")
+ (12)

---

where
th arg min Σ L(atiin aa n)
(13)
on IEI
Note that in equation 13 for expert n, as obtained by equation
am represents the miss coverage probability assigned to the best model
The miss coverage probability "n""" in is related specific interval 7, which can vary across different intervals with distinct distributions in dynamic environment. In such settings, there is no fixed miss coverage probability am m=""" that can be consistently applied over various time intervals. This necessitates establishing that SAMOCP has bounded regret in dynamic environments with respect to the time-varying benchmark in (T6), as demonstrated by the following lemma. The proof is provided in A.5
Lemma By defining the variation of the loss function to be
T
V(LOL))=
max ((E)))
[[a (411) [(a )
(14)
We establish the following bound for the dynamic regret of Algorithm 2
T
ΣΣ>
Σ
h w L(a
Mar Th mman") (0 (15)
O
ME)(())
where Ô suppresses positive constants and polylogarithmic factors, e.g., log T. Also the best miss coverage probability at each time t can be obtained by
m
arg min (ME(M))EAAO)
L( mm )..").
(16)
Lemma esstblishhs that the dynamic regret of SAMOCP (5) depends on the variation of the loss functions (14). In addition, it can be obtained from (15) that SAMCOP achieves sublinear regret if variation of the loss function is also sublinear, i.e., (((()==)) (T)).
Experiments
In this section, the performance of the proposed method, SAMOCP, is assessed within the context of classification tasks. We conduct a comprehensive comparison with recently proposed methods in online conformal prediction for dynamic environments within classification tasks. The section begins with detailed explanation of the experimental settings, followed by discussion that throughout the experiments in this section, the desired miss coverage probability is 0.1. All experiments were performed on a workstation with NVIDIA RTX A4000 GPU, Codes are avail- able at byperrefhttpp::/gihhubb in Doynamic-Environmenn
results. Note
Dataset: We utilize corrupted versions of CIFAR-10 and CIFAR- 100 Krizhevsky 2009 known
as CIFAR-10C and CIFAR- 100C [Hendrycks and Dietterich] 2019]. These datasets consist of 15 generated corruptions spanning 5 distinct levels of severity. The evaluation encompasses two settings: sudden and gradual distribution shifts. For both settings, the data sequence split into batches of 500 data samples each. The severity of corruption changes (increases or decreases) after each batch of data. In the sudden shifts, the severity level alternates between the version of the data without any corruption (severity level 0) and the most severe corruption (severity level 5). In the gradual setting, severity starts at level 0 and increases one by one after each batch until it reaches level After reaching level 5, the severity decreases one by and goes back to level in subsequent batches. This cycle of increasing and decreasing severity continues throughout the experiment. Also, additional experiments on TinylmageNet-C (Hendrycks and Dietterich 2019 and synthetic data provided in the Appendix, Section
Baselines and experimental settings: We employ ResNer-50, ResNet-18 (He et al. 2016 GoogLeNet (Szegedy al. 2015), and 1enseNet-121 (Huang al. [017]] as candidate learning mod- cls. Each active expert consists of all these learning models and needs to select the appropriate model

---

during its active interval. The proposed method is compared with the most recent adaptive conformal prediction algorithms designed for dynamic environments, including FACI [Gibbs and Candes 2022].
ScaleFreeOGID [Bhatnagar et al. 2023), , and SAOCP [Bhatnagar et al. 2023 FACT employs fixed number of active experts over all time steps, with each expert assigned one of the candidate learning rates for updating the miss coverage probability. ScaleFreeOGID reduces the learning rate based on the cumulative norms of gradients [Orabona and Pál 2018). SAOCP allows each expert to have its own active interval, within which it operates similarly to ScaleFreeOGD. In order to show how SAMOCP results in more efficient sets compared to SAOCP in a multi-model setting, we developed multi-model ensemble version of SAOCP, denoted as SAOCP(MM), where each expert consists of M update rules, each corresponding to a different learning model. This approach follows our multi-model approach but employs a similar rule to SAOCP for updating weights. To determine the value of g. we employed grid search approach within the candidates {4,8, 16, 24,32, 48, 64). The one that led to the smallest prediction set size (Avg Width) while maintaining reasonable coverage and runtime was selected, which was = 8. While the hyperparameter g is set to 8 for both SAMOCP and SAOCP(MM), it is set 32 for SAOCP, in [Bhatnagar al. 2023). Since 4 learning mod- els are incorporated in this section, the maximum number of updates at each time t in SAMOCP, M g log, f.. is equal to that in SAOCP and SAOCP(MM), which is 32 [log2 { Meanwhile, note that randomness might be undesirable in practice, the predicted miss coverage in SAMOCP is calculated in deterministic fashion, i.e., 02 = mEA(()) _m=1 h """"""""""" a."". For every experiment conducted on the synthetic dataset, CIFAR- CIFAR- parameters e, o, and 1) were selected through grid search, with values of 0.9, 140, and 0.05, respectively.
Score Functions: We utilized the nonconformity score defined as in Angelopoulos et al. 2020 to construct prediction sets, Let
= V - kregl. 0) + U. (X) + ((X,Y),
(17)
where f(r(X) denotes the probability of predicting label Y for input X by model m, and Ug is a random variable sampled from a uniform distribution over the interval [ò, 1]. The term by = HY E 3 f (X)= 2 (X)H] denotes the number of labels that have higher or equal predicted probability than label Y according to the model's output probability distribution, e.g., the softmax output. p(X, Y)= == = fr.. (X)
> fmm (X)] sums up the probabilities of all labels that have higher predicted probability than label Y. The hyperparameters and kreg are set to 0.02 and 5 for CIFAR-100C, 100C, and 0.1 and 1 for Cifar- 10C, respectively.
K
Coverage measures the percentage of instances where the true label is included in the prediction sets outputted by the conformal prediction algorithm over the period [T]. Avg Width refers to the average size of these prediction sets. Adaptive regret is calculated for time intervals of length 100. The metric Avg Regret represents the average of these regret values across the entire time horizon [T]. Run Time indicates the time required to complete each iteration of the algorithm. Lastly, Single Width measures the probability that prediction sets contain exactly one element while accurately covering the true label, highlighting cases that are most informative for predictions.
Evaluation Metries:
4.1 Results
Table [ presents the performance of SAMOCP for the classification task on the CIFAR-100C dataset under a gradual shift setting, where each method receives 8, 550 data points sequentially. It is evident that the performance of previous methods, particularly in terms of prediction set size and single- width prediction sets, depends on the learning model employed. The proposed method SAMOCP outperforms existing methods by creating smaller prediction sets, lower regret, and more single- width prediction sets that correctly cover the true label, while also achieving coverage close to the targeted level. It is noteworthy that SAMOCP surpasses every variant of previous methods in these aspects. Furthermore, SAMOCP is faster than SAOCP and SAOCP(MM), despite having the same maximum number of updates at each time t.
In dynamic environments, data distribution does not necessarily shift gradually. Instead, we may encounter abrupt distribution shifts, with significant differences between data distributions in two suc- cessive time slots. To demonstrate how SAMOCP behaves in such environments, another experiment was conducted, in which SAMOCP can successfully track these sharp transitions and select a suitable learning model for creating prediction set. Experimental results on CIFAR-1OC are detailed in
8

---

Table I: Results the CIFAR-I00C dataset with gradual distribution shift. The target coverage is 90%, and the average regret is calculated over an interval size 100. Bold numbers denote the best results in each column. SAMOCP achieves the best performance in terms of average width, average regret, and single width.
Method
Coverage (%)
Avg Width
Avg Regret( 9))
Run Time
Single Width
SAMOCP
88.16 + 0.18
5.43 :: 0.28
0.92 + 0,07
34.87 :: 0.67
0.29 = 0.01
0.22
0.27
DenseNet-122
89.64
5.77
+
ScaleProoOGD SAOCP
89,97 = 0,02
6.04 0.10
1.55 = 0.06
3.02 = 0.06
0,26 = 0.01
88.90 0.10
5.80 0.08
2.04 + 0.04
40.74 0.31
0.27 = 0.00
ResNet-50
FACI
89.67 + 0.33
6.50 0.57
1.24 + 0.90
8.45 + 0.09
0.26 + 0.01
ScaleFreeOGD
SAOCP
88.79 + 0.14
6,48 0.13
2.08 + 0.10
41.35 0.34
0.25 = 0.00
ResNet-18
FACI
89,56 + 0.28
6.82 + 0.77
1.17 + 0.75
8.39 = 0.06
0,25 - 0.01
ScaleFreeOGD
89,96 1: 0.02
7.29 0.19
1.55 1: 0.07
3.05 1 0.04
0.23 + 0.01
SAOCP
88.76 0.22
0.17
2.06 +:
41,23 0.26
0.24 + 0.01
GoogLeNet
89.63
SonleFreeOGD
89.96 + 0.01
6.71 2.71:000 0.15
1.52 # 0.06
3.04 = 0.04
0,24 - 0.00
SAOCP
88.68 0.11
6,38 0.12
2.07 =
41.13 0.39
0.26 = 0.01
where the proposed algorithm again outperforms previous methods in terms of prediction set size, regret, and single width prediction sets that accurately cover the true labels while maintaining coverage close the target value.
Table 2
To demonstrate that SAMOCP achieves the lowest regret over different intervals compared existing methods, we illustrate the regret for various interval sizes in Figure 2 are 4 different regrets corresponding to 4 learning models used and the lowest regret depicted. The results show that our method consistently leads to lower regret than the best version of each previous method across different learning models. Note that a lower regret implies that the algorithm adapts faster to changes. The regret calculated over different time intervals indicates the algorithm's s adaptivity in capturing the distribution shift at different time scales. Therefore, Figure lindicates that the SAMOCP adapt faster distribution shifts compared to benchmarks in various time scales. Furthermore, we include experiments on synthetic data and another real dataset, Tiny TinylmageNet-e using different sets of learning models that do not necessarily contain models in the Appendix, Section B This demonstrates how SAMOCP can rely on a mixture learning models over the period (7' and select the appropriate
For each existing method, there
for each distribution setting.
Table 2: Results on the CIFAR- 10C dataset with a sudden distribution shift. The target coverage is 90%, and the average regret is calculated over an interval size of 100. Bold numbers denote the best results in each column. SAMOCP achieves the best performance in terms of average width, average regret, and single width.
Model
Method
Coverage (%)
Avg Width
Regreti 10
Run Time
Single Width
SAMOCP
88.37 0.23
1.24 0.06
+
33.75 0.34
0.69
SACCP(MM)
86.80 + 2.39
1,45 0.13
3.87 + 1.05
47.08 0.19
0.56 + 0.05
DenseNet-121
FACT
89.57 + 0.37
1.30 :1 0.12
1.46 +: 0.73
8.11 1 0.10
0.68 +: 0.05
ScaleFre=OGD
89.99 - 0.01
1.46 0.02
1.71 + 0.04
2.92 - 0.07
0,52 = 0.02
ResNet-50
FACI
89.74 0.35
1.50 0.04
1.35 +
8.11 -
0.55 0.01
ScaleFreeOGD SAOCP
89.98 1 0.01
1,52 0.01
1.71 1: 0.05
2,89 1 0.04
0.54 1 0.01
89.12 + 0.08
1,51 0.01
2.17 0.06
40.25
0.27
0.53 + 0.01
RosNet-18
FACI
89.63 + 0.34
1.36 0.13
1,52 + 0.76
8.11 - 0.08
0.64 + 0.05
ScaleFreeOGD
SAOCP
88.83 1 0.06
1.48 0.02
2.24 1. 0.07
40.16
0.22
0.51 1 0.01
GoogLeNet
FACI
89.73 1 0.34
1.43 0.06
1.41 1 0.89
1: 0.10
0.58 1 0.02
ScaleFreeOGD SAOCP
89.99 + 0.02
1.46 0.01
1.70 0.06
2.89 - 0.04
0.55 + 0.00
89.09 0.14
1.44
0.17
0.55

---

50
40
Avg Regret x10"
SANDOP SAOCHANN
SANDOP SAOCTANNI
Regrat
20
SculdhooOG
10
Interval size
Interval size
(a) CIFAR-10C
(b) CIFAR- 100C
Figure 2: Evaluation average regret over different interval sizes (50, 100, 500). Note for previous methods relying single model, the lowest regret across the 4 learning models is selected.
Acknowledgement
Work this paper is supported by NSF ECCS 2207457 and NSF ECCS 2412484.
Conclusion
In this study, we introduced a novel conformal prediction algorithm designed for online environments undergoing distribution shifts. Recognizing that the selection of baseline models affects the efficiency of conformal prediction, our algorithm incorporates multiple models simultaneously. For each expert, the contribution of each model is dynamically adjusted based on its time-evolving weight. We demonstrated that our proposed method SAMOCP achieves strongly adaptive regret across any time interval of arbitrary width and maintains valid coverage. Experimental results in environments with both gradual and sudden distribution shifts indicated that our algorithm produces more informative prediction sets and achieves coverage rate close to the target value, compared to those created by previous methods using their best baseline models.
References
A.N. Angelopoulos, S. Bates, M. Jordan, and J. Malik. Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations, 2020.
V. Balasubramanian, S.S. Ho, and V. Vovk. Conformal Prediction for Reliable Machine Learning: Theory, Adaptations, and Applications. Newnes, 2014.
R.F. Barber, E.J. Candès, A. Ramdas, and R.J. Tibshirani. Conformal prediction beyond exchange- ability. The Annals of Statistics, 51(2):816-844 2023.
O. Besbes, Y. Gur, and A. Zeevi. Non-stationary stochastic optimization. Operations research, 63(5): 1227-1244, 2015.
A. Bhatnagar, H. Wang, C. Xiong, and Y. Bai. Improved online conformal prediction via strongly adaptive online learning. In International Conference on Machine Learning, pages 2337-2363. PMLR, 2023.
H. Boström, H. Linusson, T. Löfström, and U. Johansson. Accelerating difficulty estimation for conformal regression forests. Annals of Mathematics and Artificial Intelligence, 81:125-144, 2017.
N. Dssa-Bianchi, Freund, Haussler, D.P. Helmbold, R.F. Schapire, and M.K. Warmuth. How to use expert advice. Journal of the ACM (JACM), 44(3):427-485, 1997.
A. Daniely, A. Gonen, and Shalev-Shwartz. Strongly adaptive online learning. In International Conference Machine Learning, pages 1405-1411. PMLR, 2015.
10

---

T. Ding. A. Angelopoulos, S. Bates, M. Jordan, and R.J. Tibshirani. Class-conditional conformal prediction with many classes. In Advances in Neural Information Processing Systems, volume 36, 2024.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7):211-21559, 2011.
I. Gibbs and E. Candes. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 34: 1660-1672 2021.
I. Gibbs and E. Candès, Conformal inference for online prediction with arbitrary distribution shifts. arXiv preprint arXiv:2208.0844 2022.
Elad Hazan, Alexander Rakhlin, and Peter Bartlett. Adaptive online gradient descent. In Advances in Neural Information Processing Systems, volume 20, 2007.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
D. Hendrycks and T. Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. International Conference on Learning Representations, 2019.
G. Huang, Z. Liu, L. Van Der Maaten, and K.Q. Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition. pages 4700-4708, 2017.
R. Koenker and G. Bassett. Regression quantiles. Econometrica: journal of the Econometric Society, pages 33-50, 1978.
A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Y. Le and X. Yang. Tiny imagenet visual recognition challenge. Technical Report 7, CS 231N, 2015.
A. Levy, Agrawal, A. Satyanarayan, and D. Sontag. Assessing the impact of automated suggestions on decision-makinng Domain experts mediate model errors but take less initiative. In Proceediggs of the 2021 CHI Conference on Human Factors in Computing Systems, 2021.
Z. Li, Liu, W. Yang, S. Peng, and J. Zhou. A survey of convolutional neural networks: analysis, applications, and prospects. IEEE Transactions on Neural Networks and Learning Systems, 33 (12):6999-7019, 2021.
N. Littlestone and M.K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):112-261, 1994.
F. Orabona and D. Pál. Scale-free online learning. Theoretical Computer Science, 716:50-69, 2018.
H. Papadopoulos, V. Vovk, and A. Gammerman. Regression conformal prediction with nearest neighbours. Journal of Artificial Intelligence Research, 40:815-88 54000,840010 2011.
Y. Romano, E. Patterson, and E. Candes. Conformalized quantile regression. In Advances in Neural Information Processing Systems, volume 32, 2019.
Y. Romano, M. Sesia, and E. Candes. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 33:3581-3591, 2020.
G. Shafer and V. Vovk. tutorial on conformal prediction. Journal of Machine Learning Research, (3), 2008
F. Shi, C.S. Ong, and C. Leckie. Applications of class-conditional conformal predictor in multi-class classification. In 2013 12th International Conference on Machine Learning and Applications, volume 1, pages 235-239 IEEE, 2013.
Straitouri, I.. Wang, Okati, and M.G. Rodriguez. Improving expert predictions with conformal prediction. In International Conference Machine Learning, pages 32633-32653, PMLR, 2023.

---

C. Szegedy, W. Liu. Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1-9, 2015.
M. Tan and Q Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In Proceedings of the International Conference on Machine Learning pages 6105-61111 6114. PMLR, 2019.
R.J. Tibshirani, R. Foygel Barber, E. Candès, and A. Ramdas. Conformal prediction under covariate shift. In Advances in Neural Information Processing Systems, volume 32, 2019.
V. Vovk. Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence, 74:9-28, 2015.
V. Vovk, Gammerman, and G. Shafer. Algorithmic learning in a random world, volume 29. Springer, New York, 2005.
V.G. Vovk. A game of prediction with expert advice. In Proceedings of the eighth annual conference on Computational learning theory, pages 51-60, 1995.
M. Zaffran, O. Féron, Goude, J. Josse, and A. Dieuleveut, Adaptive conformal predictions for time series. In International Conference on Machine Learning, pages 25834-25866. PMLR, 2022.
12

---

A Proofs
Lemma For every a E [0, 1] and learning rate v > adaptive miss coverage probability of for any model m E [M] and E [T'] is bounded as
af 1-1), 1 1
A.1 Proof of lemma 2
Based on equation
we have
err
10% 1- 1)
ST.
(18)
Von May, 0
We prove this lemma using a contradiction. Suppose there exists i such that az"" & [-7, n/.. where 2 2 is the smallest such time index. We first prove the case of violating the upper bound: by contradiction, assume at > 1 17. According equation (18), this would necessitate that a= 1.
Given that we assumed f is the smallest time index to violate the upper bound, it should follow that [-1 S 11+1 7/. However, a > L-1 implies err 1. By equation ④ we have
m = 1- +1
S a 11 77
Vor Man ((m))
which contradicts assumption that 7-1 1 7. Next, assume a." <1 By equation (18) have F-1 < 0. Given that i is the smallest index that violates the lower bound of the lemma, it must hold that 2 -Ti. Considering x < 0 < o we deduce that err 0. Therefore, by
equation 44 have
0f
1
2 a m 2 1/-
I Vap L(am a a(am
T=l
which contradicts our initial assumption that o < -7
A.2 Proof of Theorem 1 Regret for MOCP:
Algorithm has the following regret bound
T
M
W L(a
m
Σ
T
L(a a a=))))))) SVV
VT
21+2))
+
" +I + (1 (1+ (1+n)²)
2m
2a
m=1
Where am" can be obtained via two lemmas
77. To prove the theorem, we first introduce and prove the following
Lemma for miss coverage probability assigned to any model in E [M], we have the following bound
T Σ
VT
nVT
th a3))
Σ L(a a )
(1 + 2n) 2 +
2m
2a
where th arg .in ΣT L(ar )
Proof: We first begin with
aag L(a , (
m 22 = (a
V
ath L(an of
E+=1
Then define adaptive learning rate tp. Duchi el al.
2011
Hazan et al 2007 as
7
Σ1=
Laath at )|
a
13

---

So we have
(aft)- - )² Vo. L(a,") ;a )²²))²² =a, am 2ncla VV L(a a.").
Therefore,
-a" a. b(a th ;;") (a a 2 (a7 a 1²
+ T (V at L(a ,g, ax,)))
21/
2
Since the loss function
is convex, we have the following inequality
Lio L(o a L(a,"' , ") S (a ah VV oz L(a, aa) a.)
(19)
By summing
19 over L E [T] we have
0i th axt) - L (a)) a)
(a,
- (a -
=2
+
Σ
1tt
V Va
La , ax )² )²
21/t
2
t=l
T
T
((a m
a
22 {at+1 - a a)
+ 1
211 1=1
2
- |V L(a a
|
t=1
T
( VT
nv
(la
0² (af+1- - a= th
(1 + 2n)²
(20)
21
TvT
2n
2a
where (i) used o,, E [-,,, 1 + rj] by Lemma
Lemma 4 For miss coverage probability assigned to any model in E [M] we have the following bound
T
M
T
In + E(1 T).
LT"L",,,a" SLap a.
m=1
1=1
Proof: Referring to the definition of whth in Subsection 3.1 and defining W, = Em= wo", we have
M
M
M
WT+1
WT
wT exp (- a()) = WT
Σ
WT exp (eT(a7,a77)
M
(0)
WT
m (1 -
el(aT, m
07
+ 2 Laa
m=l
M
Wr
1 1- Σ
W7 L(an aT + Σ
W L(a a my²
m=l
m=1
M
< WT exp
W L 0z)
6
Wi
m=1
T M
T M
WW exp
6
m L(a m a
m +
w m L(a a. amm)
(21)
1=1 m=1
1=1
m=1
where W1 1, (i) follows from the inequality exp(-ex) < Ex + 2x2 for |c S 1, and (ii)
follows 1 + x S e On the other hand, we have
T
T
WT+1 2 wT+1- = W II exp ( eaa ,a")) = wfth exp (-e Σ
L(a m aa
(22)
14

---

where w
1
By combining
21 and (2)
we have
M.
1 L(o," oz +
"t L( ,aT)) a?t)²
exp
f=1 m=
m==
exp
-
Ma
th at
(23)
By taking the logarithm on both sides we have
T M
T
M
T
1
,
+ +
-In - Σ ΣΣ ,
I=
m=
which leads to
I M ΣΣ
In
wt L(a a())
La at (
+ Te(1 + +))
(24)
Now, we define the best model in the static environment as
m
arg min mEM
L(a ;a7))
Then, we replace in with best model m in Lemma of two lemmas we have:
and
By setting e /T
1 and summing results
WT L(a," oo
Σ Laa
m
o0
omm") + Σ Maa aam")) - Σ
Man .a")
t=1 m=1
1=1
Σ
T L(a a())
Σ M(a aam)sss VT
(1 ((1+20) 2m)
+ In M (1 + n)²
21
2a
(25)
A.3 Proof of Theorem 2 Coverage error for SAMOCP:
We first define expected miss coverage error as
M
E
(err
hy m err?
mm 7011
The proof of this theorem is based on a grouping argument. So we first divide T into [T' group for y E (,,1), 1), and write the kth group as
G (+x-1 + 1,..., min(ts, T))-
where | < [T?]. We also define new variable, Hmm assigned to mth update rule of nihh expert as follows
H
V amm L(aunn mm3
nit
So the update rule in (4) can be written as:
err
0f mm + n
(26)
nit
For kth group where < < [T ?1, by using 26
we have
M
M
E E[err:] - a
h w. mn (err mn a)
h
ma
(a.
mn
mn
H
m=1
==1
15

---

Since at each time t we activate an expert with lifetime as defined in D the nih expert will be activated at time f n. Consequentl,, he will be for t < n. Therefore, we have
M
M
1 ot men mn
(at
mm H
men W (at
mn H m
m=1
m2
mm
a++1 ) H h t (a
Rig th (az
a2+1 H
mn
7
hn
Wh 1--1
mn
(at
7722
H
H
m=1
M
nits
h
mn
mm b
(a} mnn
-0+1 H
mm mm
(27)
12-1
H
R=1 m=1
Note that according to 26
o(41) S 1.. By summing 27
over & E Gk we have
nd
1
(eeerr
[E]
a))
Hmn
nith-1
Σ
(a (o
@++1
IEE
LEGE
M
H mile-
" BEG₁ n=1 m=
(h
mn
fe-1
mn
Hmn
0x++1
M
f--1 M
n
mm
H
(atu-1t1
mn
at++1
mn
m=1
ΣΣΣ
Σ
H
Hmn
REG2 n= m=1
max 7 {mE|M (eI(M))ellte-ll
Hmn
H
at4-1+1
mn
mn aty+1
M Σ
H ma
+ Gk max
12:4-1
LEGs
< + 2n
max
Σ
M Σ
h
mn
Fn
W
man
H
n:ta-
(28)
BEGr
Hmn
n m
For G1 we have
M Σ
E B(err a
Σ
1 men (err
-0) Σ
hr m
|Gi
[77.
LEG.
IEG.
m=1
LEC, n= m=]
(29)
By summing over all group we have
T
(T'
E E(err:]
a8
=
Σ
Elerra
a
k=1
BEGb
pr'-M Σ
+ 21
M
H ma
< 27 +
VT + 27
max
1 W
mn
A Wxy
mn
n
LEGr
Hmn
k=2
m=1
T1 7
M
1 2m
1
max
hy wmma
hn h
W t
1)
Hum
k=
n= m=1
[T'
M
Hmn
<OIT +T7
1+
max
h W
mn
hn
W
nott
(30)
(EGL
mmn
2=2
m=1
16

---

We define (T) as:
(T)
=
1 +
1
Σ
max
M Σ
h hT mm
Wtx
TAL
H
mitt-11
(31)
IEC2
H nit
n= m=l
Then have:
T
Σ
E Elery
A.4 Proof of Theorem
static regret for SAMOCP
We write the regret
M
M Σ
Σ
h man
a Ma, mn
,0, .aa
mi mm I( -04 ...
IE nE.A(t) m=1
1E m=1
M
+
L(ag ot
Σ tET
I(am" " an
(32)
LET m=1
where In denotes the time interval during which expert n is active, starting at time t = n. The third and fourth terms in the expression are analogous to the regret experienced by expert n, as established in Theorem [ To evaluate the regret for the first and second terms, we employ Lemma 4 The main difference is the number of experts considered: For a looser bound, assuming that experts remain active beyond their designated lifetime, the maximum number of experts at each time step would be gt. Thus, we derive the following bound for the first and second terms
E
Σ
Σ
h k L(a a. mmn)
Σ EET
Σ
wma L(a agt pon
tET: REA(())
v [I In (at)
Inlo(1 + 7)
S Mal (In (gt) + +
(33)
By summing 33
with regret bound of Theorem I we have
M
Σ Σ
1 Wt
mm
L(a mn
,0 a
Σ Maa m'))
BEli RE.((t) m=l
LEtR
(1+ + 2n1)2
$ Taa
+
1)
+ In M + (1 + .))² + V (In (gt) + 01 +)))
2m
2a
(1 + 2m)²
+ In + Ing (1 (1+0)) n) +mn))
(34)
2n
2a
Until this point, the regret bound we've established applies solely intervals that start with expert n, where each interval's 's length corresponds to the lifetime of expert ň. However, to derive regret bound for any arbitrary time interval manner. As proposed in (Daniely et al.) 2015). we can divide an interval I into two sequences of non-overlapping and consecutive intervals, denoted as (I-p3 ..., Io) and (I,,.., Iq), such that for all r E (-p, - Subsequently, by employing 1r,
need to partition the interval into subintervals in a suitable
He+1l < for all E (1,4 - 1), and [T,41] [T,]
17

---

the inequality Σ TT I 4VTo. and by replacing ñ with n² using (33
we have
E
Σ
h w
m L(a,
" at mn)
Σ
Laa
amnn))
TET REA(())
9-1
M
ΣE E
Σ
hy un Ma
Ot
Man =am"a)
LEI, nEA(())
h 1i
mh L(a ma aa aaa
Σ
Σ
Laa
Lamnn ,a" am"n")
== SE-PEE,, m=1
r=-ptEl,
S Given that and are positive constant variables, we have determined the regret bound for our problem, demonstrating sublinear regret for Algorithm
(35)
A.5
Proof of Lemma] 1 Dynamic regret for SAMOCP:
To prove the regret in dynamic environment we adopt a method which was first proposed by [Besbes
et al. 2015). So we can write the dynamic regret in our problem as
Σ
h w L(a
ai
mn
Maa n" "a""n))
nEA(() m=1
Σ
L(a .an"n)
Ma,
(36)
where oz oz"""" is obtained by 116 The first two terms in 36 represent the static regret as defined in Theorem 3 and have been shown be bounded. Consequently,
establish the overall regret bound, is sufficient to find the upper bounds for the third and fourth terms in (36). We begin by dividing the total time interval T into sub-intervals indexed by r 1,-.. [T/ where [7] is the length of each interval. so we can rewrite (36) as
[T/MI]
T
ΣE
Σ
h w
L(a a(
Σ
Σ
Mat
TET, REA(E)
tE
Maainn
n'
.am'n 'n'
Σ
Σ
Marin
'n'
mm momnnn n' o0
(37)
EEI
1E
For the second two terms we have
Llar "mm""" n
mmn"" Σ
L(ap"n .ar"") (L(iE))))
RET.
TET.
where (LL())) is the variability of environment [Besbes et 2015 defined in [4]. So the regret in (36) for any arbitrary [I] will be
Σ
ha L(ayen at ) m
Σ
L(a nn a "onnnn)
nEA(()
[T/1Z]]
BlnT) T
+ (2T1((L()E)) (38)
VIT
Since 35
holds for any interval I C [T], By selecting
17|
T
)
we have
M
T
Σ
h
w. L(a, mn a am))
L(a
In
mn
m "n ,a,
[=1 nEt( m=1
(A Bn (())) 2T ( S (L05)3
(39)
18

---

B Additional Experiments
B.1 Synthetic Dataset
In this subsection, we present our analysis using synthetic data to compare our proposed method, SAMOCP, with recent adaptive conformal prediction methods designed for dynamic settings. We analyze our experiments with a new set of learning models to demonstrate how our proposed method can effectively utilize a mixture of learning models to cope with distribution shifts in dynamic environment with unknown distribution changes. Additionally. experiments with synthetic data also confirm that SAMOCP maintains its advantages when varying the number of learning models. Specifically,, we conducted experiments for cases with 2 and 3 learning models.
Data Generation: To generate synthetic data that mimics real-world scenarios, we employ two distinct transformation sequences. The first transformation sequence introduces visual noise and blur effects through the application of Gaussian blur and random Gaussian noise. This approach aims to subtly degrade image clarity, simulating real-life challenges such as camera focus issues or atmospheric conditions like fog or mist. The Gaussian blur is applied with moderate settings, while random noise is incorporated to simulate sensor noise or digital compression artifacts commonly encountered in digital imagery. The second transformation sequence focuses on color manipulation. By adjusting image attributes such brightness, contrast, saturation, and hue in minor increments, challenge the models to perform reliably under varying lighting conditions and color settings-typicall variations that occur due different times of the day inconsistencies in camera settings. Addition- ally, a random conversion of some images to grayscale is employed to further challenge the models' dependency on color information.
In this experiment, two distinct datasets each containing 3000 images are generated from each trans- formation type. These datasets are designed with a fixed number of 20 classes and hyperparameters and kreg are set to 0.1 and 4, respectively. The variations between the datasets are due to random elements introduced during image processing. such as differences in which pixels are affected by noise or how color properties are altered. This randomness ensures each dataset contains unique instances, even though they stem from the same transformation principles. By concatenating images from the two datasets, the experiment simulates both gradual and sudden distribution shifts. Gradual shifts are seen within the datasets from single transformation, while sudden shifts occur when switching between datasets from different transformations.
Table 3: Results on the generated synthetic dataset for Efficientnet_be b0 and GoogLeNet learning models. The target coverage percentage 90%. Bold numbers denote the best results in each column for methods with coverage in the 85 90 range. Red numbers indicate unacceptable coverage.
Model
Method
Coverage (%)
Avg Width
Avg Regret( x -)
Run Time
SAMOCP
87.90 + 0.26
17.54 + 0.01
0.48 = 0.36
19.51 + 0.03 26.30 0.24
SAOCP(MM))
1.45
6.97
Efficientnet_bh bD
FACI
89.80 80 + 0.31
17.96 + 0.05
0.30 = 0.18
682 = 0.02
ScaleFreeOGD
89,96 = 0.00
18.05 + 0.01
1,61 0.01
2,45 0.00
SAOCP
88.73 + 0.08
17.82 + 0.01
2.18 0.02
34.43 + 0.06
GoogLeNet
FACE
89.66 4: 0.30
18.05 + 0.09
1.36 = 0.79
6.89 : 0.02
ScaleFreeOOID
1:
0.03
0.00
SAOCP
88.39 +: 0.07
17:75 0.02
2.55 0.03
34.78 + 0.06
We conducted experiments using a distinct set of learning models. As shown in Table 3 we incorporated two learning models, Efficientnet_ bo and GoogLeNet, where we achieved the smallest prediction set size with coverage close to the target. The SAOCP for GoogLeNet obtained an average width close to our method: however, it is noteworthy that the maximum number of updates in SAOCP is twice that of SAMOCP, demonstrating that our algorithm achieved this result with lower computational costs. Additionally, its regret almost five times larger than our method's. We also provide synthetic data analysis using another set of learning models consisting of GoogLeNet, DenseNet-12 121, and EffficientNet-B00 [an and Le| 2019), as detailed Table where our method again was able to construct smaller prediction sets. It should also be noted that, due to severely corrupted data in our synthetic dataset, none of the models were able to produce single width prediction sets that cover true labels.
19

---

Table 4: Results the generated synthetic dataset for EfficientNNetBo, CenseNee-1111, and GoogLeNet learning models. The target coverage percentage 90%. Bold numbers denote the best results in each column for methods with coverage in the 85 90 range. Red numbers indicate unacceptable coverage.
Model
Method
Coverage (%)
Avg Width
Avg Regret( x
Ron Time
SAMOCP
88.04 + 0.31
17.60 + 0.04
0.63 = 0.45
26.39 + 0.37
16.29 1.55
Efficienmett
FACT
17.96 0.05
7.37
ScalePrecOOD
89,96 = 0.00
18.05 + 0.01
1,61 0.01
2.65 0.01
SAOCP
88.73 +: 0.08
17.82 0.01
2,18 0.02
37,25 0.15
DenseNet-121
FACI
89.72 +: 0.32
18.04 + 0.07
1U7 = 0.73
7.42 = 0.05
ScaleFreeOGD
SAOCP
88.39 + 0.09
17.72 + 0.01
2,53 0.02
37.83 + 0.16
GoogLeNet
FACI ScaleFreeOOD
89.66 + 0.30
18.05 + 0.09
1.36 = 0.79
7.49 = 0.06
89.95 1: 0.00
18.07 0.03
1,82 0.03
2.66 0.03
SAOCP
88.39 0.07
17.75 0.02
2.55 0.03
37,90 + 0.21
B.2
Tiny ImageNet Dataset
Here, we conduct the experiment on a new dataset involving a gradual distribution shift using real dataset, TinylmageNet-C. which is corrupted version of the ImageNt (Le and Yang, 2015) dataset that features 200 distinct classes. We have also incorporated a new mixture of learning models-GoogLLeNec DenseNet-121, EfficientNet-BO. and MobileNet-V2 (Li al.) 2021] to demonstrate the performance of our algorithm. In Table we detail our proposed method's comparison with previous methods, where, once again, our algorithm able achieve smaller prediction set sizes while maintaining coverage close to the target value of 1 - a. It is reasonable to study prediction sets in situations where we achieve coverage close the desired level. The SAOCP(MM) method achieves coverage of less than 85%, which is significantly below the target value. Therefore, we not consider prediction sets in our comparison. As demonstrated in the table, SAMOCP obtains smaller prediction sets and operates faster than SAOCP. For the EinylmageNet-CC dataset, the parameters 7/s & and kreg are set to 0.025, 0.01 and 20, respectively. Other parameters remain consistent with previous experiments. All real datasets are downloaded from the Zenodo repository.
Table 5: Results on the LinylmageNet-C dataset with a gradual distribution shift. The target coverage 90%, and the average regret calculated over an interval size of 100. Bold numbers denote the best results in each column for methods with coverage in the 85-90 range. Red numbers indicate unacceptable coverage. SAMOCP achieves the best performance in terms of average width and single width.
Model
Method
Coverage (%)
Avg Width
Avg Regret( x10 2)
Run Time
Single Width
SAMOCP
87.73 + 0.35
171.64 + 1.34 165.93
1.28 + 0.20 4.80 0.77
35.22 = 0.72
0
SAOCP(M)
84.91 1.22
3.32
48.55 + 0.15
GoogLeNet
FACI
89.69 1: 0.29
177.93 + 1.11
1,07 1: 0.67
8.48 1: 0.06
0
ScaleFreeOGD
0.49
3,16
SAOCP
88.36 0.07
174.81 + 0.50
2,02 +: 0.08
40,83 + 0.32
0
DenseNet-121 121
FACI ScaleFireOOD
89.68 + 0.31
176.66 + 1.10
1.30 0.74
8.54 0.11
0
89.95 0.02
177.24 1: 0.64
1.53 0.06
3.18 0.05
SAOCP
88.48 0.12
0.57 173.79
2,09 0.04
40.09 0.36
Efficientnet_MM b0
1.03
ScaleFreeOGD SAOCP
89.95 + 0.01
177.23 + 0.63
1.37 0.06
3.17 + 0.05
0
88.30 0.18
173.52 0.63
1,98 0.08
41.06 - 0.15
Mobilenet_y2
FACI
89.69 1 0.30
175.26
0.95
0.98 1: 0.52
8.55 0.07
0
ScaleFreeOGD
89.95 0.01
175.82
0.51
1.36 0.07
3.19 0.04
SAOCP
88.30 1. 0.15
171.8 1 0.55
1.94 1: 0.06
40.60 1: 0.23
0
20

---

B.3 SAMOCP vs. SAOCP (equal lifetimes)
We compared our method with a specific version of SAOCP where the hyperparameter in equation (9) is set to 8, giving both SAOCP and SAMOCP experts the same lifetime. We conduct experiments identical those described in section 4 addressing both sudden and gradual shifts for CIFAR 10C and CIFAR-100C, respectively. Our results are demonstrated in Table CIFAR-IOC, and in Table for CIFAR-100C. For both cases, we observe the advantage of utilizing multiple learning models instead of a single model, as our proposed method, SAMOCP, significantly outperforms SAOCP across all four learning models. SAMOCP achieved better results terms of coverage, average width, average regret, and single width compared to SAOCP.
Table 6: Performance evaluation of SAOCP with same lifetime time SAMOCP for sudden distribution shift setting on CIFAR-IOC.
Method
Coverage (%)
Avg Width
Avg Regret(
Single
SAMOCP
88.37 + 0.23
1.24 0.06
0.98 +
33:75 0.34
0.69 0.03
DenscNet-121
SAOCP
87.16 + 0.10
1.45 + 0.03
4,36 + 0.14
14.73 0.09
0.53 = 0.01
87.87
0.07
ResNet- 18
SAOCP
87.16 1 0.18
1.51 1: 0.02
4,38 1. 0.16
14.85 0.08
0,51 1 0.01
GoogLeNer
+
1.45 0.01
Table 7: Performance evaluation of SAOCP with same lifetime time SAMOCP for gradual distribution shift setting on CIFAR-100C.
Model
Method
Coverage (%)
Avg Width
Avg Regret( x x10
Run Time
Single Width
SAMOCP
88.16 1. 0.18
5.43 1: 0.28
0.92 J: 0.07
34.87
0.67
0.29 J. 0.01
DenseNet-121
SAOCP
87,33 = 0.14
6,12 0,16
4,03 + 0.06
14.89
0.06
0,27 = 0.00
ResNet-50
SAOCP
87.22 = 0.12
6.75 0.16
3,99 + 0.14
15.01
0.07
0.26 0.00
ResNet-18
SAOCP
87.15 1 0.14
7.24
124:1:00 0.22
4,10 1 0.11
15.02 0.08
0.25 1: 0.00
GoogleNe
SAOCP
87.09 + 0.16
0.12 6.78
4.14 + 0.13
14.98
0.09
0.26 + 0.00
B.4 SAMOCP vs. MOCP
To validate the advantage of SAMOCP versus MOCP in dynamic environments, we conducted experiments for both sudden and gradual distribution shifts. see Tables and 9 In both tables. SAMOCP outperforms MOCP in terms of Average Width and Single Width metrics.
Table 8: Comparison of MOCP and SAMOCP on the CIFAR- 10C dataset with sudden distribution shift. The target coverage 90%. Bold numbers denote the best results in each column.
Method
Covergee (%)
Avg Width
Single Width
MOCP 89.96 0.33
1.29 + 0.08
0.67 0.04
SAMOCP
88.37 1: 0.23
1.24 : 0.06
0.69 0.03
21

---

Table 9: Comparison of MOCP and SAMOCP the CIFAR- 100C dataset with gradual distribution shift. The target coverage is 90%. Bold numbers denote the best results in each column.
Method
Coverage (9t
Avg Width
Single Width
d:
SAMOCP
88.16 0.18
5,43 + 0.28
0.29 0.01
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We clearly point out our contribution in the abstract and introduction.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The result tables (sections and B demonstrate that method does not achieve the best coverage and runs slower than single models.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: For each theorem and lemma in section 3.1 and 3.2 we explained our assump- tions and provide clear proof in section A
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide explanation of our experiment procedure in section and also provide full explanation of generating synthetic data set in section B
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: A link to the GitHub repository, containing the full implementation of the method described in the paper, is provided in Section
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In sections and B we determine the values of the hyperparameters.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
22

---

Justification: We did every experiment for 10 different random seeds.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In section B mentioned that used NVIDIA RTX A4000 GPU, and demonstrated the run time for each iteration of our algorithm compared to previous algorithms.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httt::://oorrrss..p/pllll///eeee
Answer: [Yes]
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We do not expect any direct societal impact in our work.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: In section 4 we cited every datasets we employed.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: In section B we mentioned that real datasets are downloaded from Zenodo respiratory.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
23


Reviews:
[{"review_id": "VTgKTCeSY5", "reviewer": "Reviewer_moxN", "summary": "This paper proposes the Strongly Adaptive Multimodal Online Conformal Prediction (SAMOCP) methodology, which constructs adaptive conformal prediction sets by integrating information from multiple learning models in dynamic environments. This is accomplished by creating multiple experts at each time step, where each expert is an online learning algorithm that dynamically updates the weights of each model and has a finite active time interval. The appropriate miscoverage probability at time $t$ for constructing the prediction set in the subsequent step is determined by the miscoverage probability associated with the selected expert among the many active experts.", "questions": "1. Did you try to implement the method on time series data where consecutive data can potentially exhibit continuous distributional shifts? For example, on stock price data, with the response output being 1 if the price goes up and 0 if it goes down.\n\n2. Can you explain how exactly to ‘select one of the miscoverage probabilities ${\\alpha_t^m\\}$ according to the pmf …’? Is it simply selecting the $\\alpha_t^m$ with the highest normalized weight?\n\n3. In the numerical experiments, if my understanding is correct, the sudden shifts setting involves having intact data before a certain threshold and fully corrupted data after that threshold. How exactly does it work for the gradual shifts? For instance, if there are five distinct levels of severity, do you assign all images with level 0 in the first 1/5 of the horizon, level 1 in 1/5-2/5 of the horizon, and so on?\n\n4. How is the number of experts chosen?\n\nMinor:\nThere seems to be a typo in line 134: the miscoverage probability $\\alpha_{t+1}^m$ can be updated via ..., instead of $\\alpha_{t}^m$. \n\nFor completeness and better clarity, I would suggest adding a line in the algorithm between ‘select one miscoverage probability…’ and ‘Observe true $Y_{t+1}$' that says ‘construct prediction set for $Y_{t+1}$ using the selected miscoverage probability.'", "limitations": "The authors addressed the limitations of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The concept of developing a Conformal Prediction framework for dynamic environments using information from multiple learning models is novel. \n\n2. The paper is well-written and well-structured. \n\n3. The performance of the proposed method is analyzed with theoretical justifications and has demonstrated advantages through extensive experiments compared to existing benchmarks.", "weaknesses": "1. As already pointed out in this paper, this new method is much slower compared to other benchmarks. Therefore, it would be beneficial if the authors could conduct a comprehensive computational complexity analysis, in addition to reporting the empirical runtime in the experiments. This would help practitioners understand how well this method can scale to more complex datasets with a larger number of learning models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our submission.\n\nQ1: We did not conduct experiments with time series data. According to the dynamic regret analysis in Lemma 1, achieving sub-linear dynamic regret requires the variation of the loss function to be sublinear. Having continuous distribution shifts in consecutive data violates this requirement. Hence, experiments in this setting were not included.\n\nQ2: The miss coverage probability  $\\alpha_t^m$​ is not simply selected based on the highest probability. Instead, each miss coverage probability $\\alpha_t^m$ is chosen with probability proportional to its normalized weight $\\bar{w}_t^m$. In other words, miss coverage probabilities of models with higher weights are more likely to be selected. Such probabilistic selection enables the algorithm to consider a variety of models.\n\nQ3: For every gradual shift experiment (e.g. Table 1 in section 4), the data sequence was split into batches of 500 data samples each. The severity changes (increases or decreases) after each batch of data. The severity starts at level 0 and increases one by one after each batch until it reaches level 5. After reaching level 5, the severity decreases one by one and goes back to level 0 in subsequent batches. This cycle of increasing and decreasing severity continues throughout the duration of the experiment. To better illustrate the procedure of the gradual shift, please refer to the following sequence, which shows the change of severity through gradual distribution shifts.\n0->1->2->3->4->5->4->3->2->1->0->1->....\nThis setup indicates that the data experiences gradual shifts in both directions, providing a robust evaluation of the algorithm’s adaptability. \n\nQ4: The number of experts is not chosen directly. Instead, the lifetime of each expert is determined by the formula in Equation (9). This formula depends on the parameter g. To determine the value of g, we employed a grid search approach within the candidates {4,8,16,24,32,48,64}. The parameter g that led to the smallest prediction set size (Avg Width) while maintaining reasonable coverage and runtime was selected, which was g=8.\n\nComputational Complexity: For the first proposed algorithm (MOCP), considering there are M models, the overall computational complexity is O(MT). For the SAMOCP algorithm, given that the maximum number of active experts at each time step g[log T], the overall computational complexity is O(MgTlog T).\n\nWe sincerely thank the reviewer for the insightful suggestion. We included your suggestion in our algorithm to improve clarity and completeness.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hRWvHnGq4a", "reviewer": "Reviewer_xzo3", "summary": "This paper investigates online conformal prediction within dynamic environments. The authors introduce a novel adaptive conformal prediction framework that leverages multiple candidate models. The proposed algorithm achieves sublinear regret, and its effectiveness is demonstrated through both real and synthetic datasets.", "questions": "1. In Algorithm 1, how should \\(\\epsilon\\) be chosen?\n\n2. How does this multi-model approach perform compared to retraining the non-conformal score after each update?\n\n3. How quickly can this method adapt to distribution shifts compared to benchmarks in real data studies? Rapidly capturing distribution shifts and making valid prediction sets is crucial in practical applications.\n\n4. Could the authors provide intuition behind the design of the algorithm in a dynamic environment? Specifically, why are many experts retained when \\(t\\) is large, despite having a total of \\( M\\) models?", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed method is novel, with a clear presentation and comprehensive literature review. It demonstrates good performance compared to benchmark methods.", "weaknesses": "The intuition behind the proposed algorithm in the dynamic environment (Section 3.2) is not sufficiently developed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The authors would like to thank the reviewer for their valuable comments and for recognizing the novelty of our work. We will address your questions as follows:\n\nQ1: The parameter $\\epsilon$ was selected via grid search from {0.1, 0.2, …,0.9}.  The one which led to the smallest prediction set size (Avg Width) while ensuring desired coverage was chosen, and $\\epsilon= 0.9$ in all our experiments.\n\nQ2: We would like to clarify that the non-conformal scores are indeed calculated after each update. Specifically,  upon receiving each new data sample, the non-conformity scores for each candidate label are calculated via eq (17). The calibration set is then updated, once the true label is received. \n\nQ3: Our experimental results show that SAMOCP can adapt to distribution shift faster than the benchmarks in real data sets, see Figure 2, which shows that SAMOCP consistently achieves lower regret with different window sizes. Note that a lower regret implies that the algorithm adapts faster to changes. In addition, the regret calculated over a smaller window size characterizes the algorithm’s adaptivity in a shorter time interval, hence faster in capturing distribution shifts. Therefore, Figure 2 indicates that the SAMOCP can adapt faster to distribution shifts compared to benchmarks in various time scales. Thanks for your comments, we will revise the final version to provide more intuition of this experimental results.\n\nQ4: Thank you for your question. The intuition behind the SAMOCP algorithm is to effectively adapt to dynamic environments with unknown distribution shifts. SAMOCP leverages multiple variants of the MOCP algorithm, each treated as an expert with specific values for stepsize $\\epsilon$  and lifetime. This design allows the algorithm to maintain a diverse set of experts, each suited to a different type of shift. Experts with shorter lifetimes can rapidly adapt to quick distribution shifts. On the other hand, experts with longer lifetimes are more suitable for tracking gradual or subtle changes.  \nIn addition, we would like to clarify that the number of experts is not influenced by the number of models in SAMOCP. Instead, SAMOCP treats each instance of MOCP as an expert with a specific lifetime. The reason many experts are retained for large t is that more experts become activated as time increases, and experts with different lengths of lifetime are incorporated to cope with different types of distribution shifts. Such a mechanism enables the SAMOCP to be strongly adaptive to unknown distribution shifts and achieve sub-linear regret.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JcbPpsaEb2", "reviewer": "Reviewer_76a7", "summary": "This paper proposes an online multimodal conformal prediction method named SAMOCP, developed to address data distribution shifts in dynamic environments. Specifically, the method selects the best model from multiple candidates to create prediction sets via strongly adaptive online learning.", "questions": "See in the Weaknesses.", "limitations": "The limitations of the authors have been pointed out in the Conclusion.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The method aims to expand single-modal online conformal prediction to multimodal.\n2. The method achieves better efficiency through the selection from multiple models.", "weaknesses": "1. This paper appears to be a variant of SAOCP [1], utilizing many techniques from [1] to construct candidate sets with multiple models. By optimizing the weight of each model, the final prediction set is obtained from the best model. However, there is insufficient evidence to validate the superiority of SAMOCP compared to SAOCP, both theoretically and empirically.\n2. The authors claim that the method is devised for a multimodal setting. However, both the methodology and experiments seem to involve multiple experts for a unimodal dataset using different deep neural networks, which contradicts the introduction of the method.\n3. There are several concerns regarding the theoretical analyses. What is the meaning of Theorems 1 and 3? Are they intended to demonstrate that the pinball loss will increase with the addition of the optimal single model? What is the strength of these theoretical analyses for decision-making in an online multimodal setting?\n4. It is suggested to provide a Complexity Analysis of the overall model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for reading our manuscript and thoughtful comments and questions. We will address your questions as follows:\n\nQ1: We would like to clarify that our proposed method, SAMOCP, is not simply a multimodal version of SAOCP [1]. SAMOCP includes a distinct approach for updating the weight assigned to each expert and having a specific step size for each expert, which is different from SAOCP. As a result, SAMOCP demonstrates superior performance compared to both the original SAOCP and the multimodal version of SAOCP (referred to as SAOCP(MM)). Specifically, SAMOCP outperforms SAOCP across multiple metrics, including Average Width, Average Regret, Run Time, and Single Width, see Tables 1 and 2. Meanwhile,  SAMOCP achieves similar coverage as SAOCP, with < 1% difference. This indicates that SAMOCP maintains the desired coverage while achieving superior performance in other metrics.  \nIn addition, we conducted comprehensive experiments to compare SAMOCP with SAOCP. In these experiments, the lifetimes of experts were same in both methods, with an equal parameter g in Equation (9). The detailed results of these experiments are presented in Tables 6 and 7. These comparisons validate that SAMOCP consistently achieves better performance in terms of Coverage, Average Width, Average Regret, and Single Width. \n\nQ2: There might be some misunderstanding. The `multimodel’ does not mean the dataset contains multiple modalities. Instead, it refers to the fact that the proposed SAMOCP employs multiple learning models (neural networks in our experiments).\nThe intuition behind the multimodal design is that different learning models exhibit varying behaviors in response to distinct distribution shifts. A single learning model may not consistently provide the best performance across different distribution shifts. By leveraging multiple learning models, SAMOCP dynamically selects the suitable one for the current data distribution.\n\nQ3: Theorems 1 and 3 aim to demonstrate that the proposed method achieves sublinear regret, which bounds the difference between the loss of the proposed online algorithm and that of the best model in hindsight. While the cumulative difference increases over time, sublinear regret indicates that the average difference decreases over time, and converges to zero as time goes to infinity, and henceforth achieves “no regret” on average. Sublinear regret has been a crucial criterion in analyzing various online learning frameworks, see [2,3,4,5,6]. Below we will elaborate in further detail about the meaning of Theorem 1 and 3.\n\nTheorem 1 shows that the Multimodal Online Conformal Prediction (MOCP) algorithm achieves sublinear regret in static environments. Specifically, Theorem 1 analyzes the difference in loss between the MOCP algorithm and the best model in hindsight. This means that as the number of time steps T increases, the average difference in performance between the MOCP algorithm and the best possible model decreases, indicating that MOCP adapts well to the data over time. \n\nTheorem 3 provides the regret analysis for the Strongly Adaptive Multimodal Online Conformal Prediction (SAMOCP) algorithm. Specifically, Theorem 3 evaluates the difference in loss between the SAMOCP algorithm and the best expert (where each expert selects the optimal model) in hindsight over any intervals with arbitrary length. This analysis shows that the loss difference between the SAMOCP method and the best expert converges to zero as time goes to infinity. This indicates that SAMOCP can effectively select the most suitable expert from multiple candidates.\n\nQ4: For the first proposed algorithm (MOCP), considering there are M models, the overall computational complexity is O(MT). For the SAMOCP algorithm, given that the maximum number of active experts at each time step g[log T], the overall computational complexity is O(MgTlog T).\n\n\n[1] A. Bhatnagar et al. \"Improved Online Conformal Prediction via Strongly Adaptive Online Learning.\"\n\n[2] S. Paternain et al. \"Constrained Online Learning in Networks with Sublinear Regret and Fit.\"\n\n[3] Y. Zhou et al. \"Regret Bounds Without Lipschitz Continuity: Online Learning With Relative-Lipschitz Losses.\"\n\n[4] C.A. Cheng et al. \"Online Learning With Continuous Variations: Dynamic Regret and Reductions.\" \n\n[5] S. Ito et al. \"Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression With Limited Observation\"\n \n[6] S. Paternain et al. \"Constrained Online Learning in Networks with Sublinear Regret and Fit.\"", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8syveFIgbr", "reviewer": "Reviewer_4Km4", "summary": "This paper considers conformal prediction in the online setting with multiple fitted models, which is very interesting and in line with real applications. As it remains an active question regarding how to aggregate multiple models, the proposed approach adopts importance sampling to choose the 'best' model at each step. The performance is justified with comprehensive simulations and comparisons with baseline approaches are presented.", "questions": "1. [Choice of weights] The weights defined in (6) follow exponential decay. It would be interesting to explore other choices of the weights: (1) in terms of theoretical guarantee, how will the coverage/accuracy guide the choice of w? (2) choices of w can also be compared via numerical simulations.\n\n2. [Thm 1] Average regret is considered in Thm 1. It remains unknown how will the MOCP approach outperform FACI in terms of the coverage guarantee.\n\n3. [MOCP vs SAMOCP] MOCP would also be capable of the tasks presented in the simulation section, then it could be more informative to compare SAMOCP with MOCP to validate the advantage of SAMOCP.\n\n4. [From adversarial setting to stochastic setting] It would be interesting to study the theoretical performance of the proposed approach under the stochastic setting where observations are i.i.d. to understand the gains of model aggregation. Please see references e.g. (1) Duchi et al. (Adaptive Subgradient Methods for Online Learning and Stochastic Optimization); (2) Hazan et al. (Adaptive Online Gradient Descent); etc.", "limitations": "Limitations are discussed in the paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The problem studied in this paper is well-defined and is of interest in the literature. The theoretical guarantee and numerical performance of the proposed approach are well presented.", "weaknesses": "Please see questions in the following section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q1: The exponential update framework is theoretically justified by its ability to minimize regret, a measure of how well the algorithm performs relative to the best-fixed strategy in hindsight. The exponential update is widely used in many online setting algorithms, see [1,2,3].\nFurthermore, the choice of such an exponential update is rooted in the principles of online mirror descent in the case where the variables are constrained to a probability simplex (non-negative and sum up to one). Hence, it naturally fits the ideal weight update.   \nThat said, we would be happy to evaluate alternative weight update methods that the reviewer may suggest.\n\n\nQ2: We understand the concern. To address this comment, we conduct additional experiments comparing MOCP and FACI methods in terms of Coverage and Regret, see Tables 1 and 2 in the attached file. These experiments involve sudden distribution shifts with CIFAR-10C and gradual distribution shifts with CIFAR-100C, respectively. In both cases, MOCP outperformed FACI, demonstrating the advantage of using multiple learning models over a single model.  \nWhile we did not theoretically analyze the coverage for MOCP, we provided the corresponding analysis guarantee for SAMOCP as shown in Theorem 2. The coverage of FACI was studied for a special case where the step size is diminishing. As mentioned in [1], “We evaluate the long-term coverage in a specialized case where the hyperparameters decay to 0 over time.” However, to provide a coverage guarantee, we did not need to consider such a special case.\n\n\nQ3: Thank you for your suggestion. We conducted experiments to compare MOCP and SAMOCP for both sudden and gradual distribution shifts, see Tables 3 and 4 in the attached file. In both tables, SAMOCP outperforms MOCP in terms of Average Width and Single Width metrics.\n\n\nQ4: We appreciate the reviewer's suggestion to study the theoretical behavior of our approach under the stochastic setting where observations are i.i.d. We agree with the reviewer that it would indeed be an interesting future direction of the present work.  We will cite the references and mention this future direction in the final version. \n\n[1] I. Gibbs and E. Candès, “Conformal inference for online prediction with arbitrary distribution shifts.” \n\n[2] Y. Shen et al. “Random Feature-Based Online Multi-Kernel Learning in Environments with Unknown Dynamics.” \n\n[3] Elad Hazan, \"Introduction to Online Convex Optimization.\"", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their time and effort in reviewing our paper.

Additional experiments have been conducted to compare our first algorithm (MOCP) with benchmarks and SAMOCP. The results can be found in the attached file.

Meta-review: The paper proposes an adaptive conformal prediction algorithm that integrates predictions from multiple learning models in a dynamic environment. The paper provides both theoretical and empirical results.
The paper received four reviews, and after the rebuttal all reviewers are leaning towards accepting the paper. The reviewers note that the proposed algorithm is novel and the theory and the experiments are sound and sufficient. During he rebuttal, the reviewers had a few concerns and questions, including regarding the interpretation of the theorems, the speed of the method, and hyperparameter selection. Those concerns were addressed during the rebuttal, and no major concerns remain. 
One reviewer pointed out that the usage of `multimodal' (including the title) throughout should be changed to `mutimodel', and I agree. 
Overall this is a valuable contribution and good addition to the conference program.
Decision: Accept (poster)