Multi-model Ensemble Conformal Prediction in Dynamic Environments

Authors: erfan  hajihashemi
yanning  shen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 05:21:34

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.

Main paper: 
 introduction: 
 Most machine learning algorithm designs aim to enhance label prediction accuracy. Nevertheless, a significant challenge persists as 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 is sometimes more efficient to predict a subset of labels rather than a single label [Levy et al., 2021 , Straitouri et al., 2023] . This necessitates predicting a set of candidate labels with a valid coverage probability, rather than limiting to a single label.One of the most widely used frameworks for set prediction is conformal prediction [Vovk et al., 2005] . Conventional conformal prediction algorithms can achieve the desired coverage assuming the exchangeability of data [Balasubramanian et al., 2014] . However, in many real-world online problems, the distribution of data shifts over time, making the exchangeability assumption no longer applicable. Consequently, adaptive conformal prediction algorithms have been developed [Gibbs and Candes, 2021] , where prediction sets are constructed in a 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 on the model employed, and the historical dataset as a calibration dataset, which is utilized to determine whether a candidate label Y ∈ Y should be included in the prediction set. Consequently, in an online manner, conformal prediction relies on an 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 {S m (X τ , Y true τ )} t-1 τ =1 are introduced. Specifically, each non-conformity score S m (X τ , Y true τ ) assesses the disagreement between the ground-truth label Y true τ and predicted label f m (X τ ). Upon obtaining a new datum X t , the standard conformal prediction algorithm constructs the prediction set for X t as C m α (X t ) = {Y ∈ Y | S m (X t , Y ) ≤ qm α }, where the threshold qm α is obtained asEQUATIONThe Quantile function sorts all non-conformity scores of the historical data and then identifies the ⌈t(1 -α)⌉th smallest score as qm α . Note that 1 -α 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 t and thereby enabling the algorithm to dynamically adapt to potential shifts in the distribution. In such a scenario, qm α can be obtained by replacing α with α t in (1). Then at each time step t, α t is updated after observing Y true t .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 t. To this end, in this work, we introduce a novel adaptive multimodel online conformal prediction algorithm designed to identify the suitable learning model at each time t within dynamic environments. At time slot t, the goal is to construct a prediction set for the new data X t , based on the historical dataset {(X τ , Y true τ )} t-1 τ =1 , such that the true label is included in the prediction set with probability 1 -α. The proposed algorithm for dynamic settings achieves strongly adaptive regret while ensuring valid coverage. 
methodology: 
 In this section, two adaptive algorithms are developed for static and dynamic environments respectively. Subsection 3.1 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.Note that the non-conformity score S m (X τ , Y true τ ) depends on the learning model. Such dependency leads to a model-specific ordering of non-conformity scores, yielding different prediction sets for each model. After observing Y true t , the adaptive miss coverage probability α t must be updated for time t + 1 to cope with distribution shifts effectively. Given that different models achieve different prediction sets, assigning and updating the same α t for different models would be inadequate. Instead, at each time t, we assign a specific miss coverage probability to each model m ∈ [M ], denoted as α m t , and update it based on the corresponding prediction set. Consequently, for M learning models, there are M candidates for miss coverage probability α t at each time t. Each candidate is updated according to a 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 α m t 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 α m t , we adopt the pinball loss [Koenker and Bassett, 1978] , which can be written asEQUATIONwhereEQUATIONis the best possible value of miss coverage probability for model m at time t which constructs the smallest prediction set that covers Y true t .The miss coverage probability α m t+1 can be updated via SF-OGD [Orabona and Pál, 2018] asEQUATION)where η is the learning rate andEQUATIONwitherr m t := I[Y true t / ∈ C m α mt ] equals 1 if the predicted set does not contain the true label Y true t , and 0 otherwise. According to the updating rule outlined in equation ( 4), the adjustment of α m t at each time t is governed by the ∇ α m t L(ᾱ m t , α m t ), as detailed in equation ( 5). When err m t = 1, it signals that the coverage probability 1 -α m t is too small, resulting in a prediction set that can not encompass Y true t . Consequently, there's a necessity to enlarge the coverage probability, effectively achieved by reducing α m t , which would be facilitated by (4); given that the denominator in the second term is always positive and the gradient will be positive in this scenario. On the other hand, when ᾱm t > α m t , 1 -α m t leads to a prediction set that covers Y true t but also includes unnecessary labelsY ′ := {Y ′ ∈ Y | qm ᾱm t < S m (X t , Y ′ ) ≤ qm α m t }.In such cases, optimization necessitates increasing α m t to avoid including unnecessary labels and output a more efficient prediction set. This adjustment is facilitated by the update rule (4).Additionally, the weight w m t is assigned to each model m ∈ [M ], which influences the selection of its corresponding miss coverage probability α m t . MOCP learns which model to select over time based on the performance of each model over previous time steps, as reflected in w m t . The algorithm updates the weight associated with each model after revealing the true label Y true t . This update is performed with respect to the loss function of the corresponding miss coverage probability. Specifically, w m t can be updated byEQUATIONwhere 0 < ϵ < 1 is the step size. 6) and (4), respectively. This entire process is detailed in Algorithm 1. The MOCP algorithm achieves a runtime of O(T ) when the number of models M is constant.Given that the environment is static, there exists a miss coverage probability that can minimize the loss function for each model m ∈ [M ] over [T ], denoted as α m . The best miss coverage probability among {α m } M m=1 can be obtained byEQUATIONThe following theorem demonstrates that MOCP achieves sublinear regret (See proof in A.2).Theorem 1 Algorithm 1 achieves the following regret bound in a static environmentT t=1 M m=1 wm t L(ᾱ m t , α m t ) - T t=1 L( ᾱm * t , α m * ) ≤ √ T (1 + 2η) 2 2η + η 2α + ln M + (1 + η) 2 . (8)Through Algorithm 1, we demonstrated how to select the suitable miss coverage probability of a model that has achieved lower loss compared to other models over previous time steps. However, this approach assumes a static environment that does not change over time, which may limit the algorithm'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, a large ϵ indicates faster adaptation to abrupt changes, whereas a small ϵ is more suitable for environments with less variability. Thus, the efficient choice of ϵ depends on the variability of the environment, which poses a challenge in scenarios with unknown distribution shifts.To address this limitation, we introduce Strongly Adaptive (SA)MOCP. 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 of its lifetime, the expert becomes inactive, ensuring that it no longer affects the decision-making process, refer to Figure 1 for an illustration. This strategy prevents outdated experts from contributing to the selection of the suitable miss coverage probability in dynamic environments. Subsequently, SAMOCP dynamically selects the appropriate expert for each time t 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 it was created and hyperparameter g ∈ N, as [Bhatnagar et al., 2023] .EQUATIONThe active interval of the expert created at time t is defined as [t, t + λ(t) -1]. Consequently, experts considered active at any given time τ 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 t, some active experts might not have adapted to the current data distribution yet, and thus they rely on different models compared to more recently established active experts. In such cases, the miss coverage probability of model m ∈ [M ] chosen by expert n at time t is represented as α mn t , and its best possible value is denoted as ᾱ mn t . To select the suitable miss coverage probability among different experts, we assigned distinct weights to each, with specific initialization and step sizes for updates. Specifically, this weight for expert n at time t is denoted as h n t , and its step size is defined asϵ n := min(ϵ, σ √ λ(n)), where σ > 1 is a constant and λ(n) is the lifetime for expert n that obtained by ( 9). Given that nth expert is activated at t = n, the initialization and update rule for h n t is as follows:EQUATIONwhere r n t = L(ᾱ mn t , α mn t ) -L(ᾱ mn t , α mn t ) represents the loss of the nth expert relative to the loss of the learner who selects expert n. We denote the set of active experts at each time t as A(t). The learner selects the suitable miss coverage probability among all active experts according to the PMF ht := ( hn t ) n∈A(t) , where each hn t represents the normalized version of the weight h n t , calculated ashn t = h n t i∈A(t) h i t , ensuring that hn t ∈ [0, 1].Algorithm 2 summarizes the SAMOCP method. It can be observed from ( 9) that the maximum number of active experts (MOCP instances) at each time t is g⌊log 2 t⌋. Hence, the complexity of SAMOCP is of order O(T log 2 T ).Algorithm 2 Strongly Adaptive Multi-model Ensemble Online Conformal Prediction (SAMOCP) , where mn represents the mth 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).Require: α ∈ [0, 1], hyperparameters η ≥ 0, ϵ ∈ (0,Theorem 2 For any T ≥ 1 and any γ ∈ 1 2 , 1 , Algorithm 2 achieves the coverage error boundEQUATION)where β γ (T ) measures the smoothness of model weights within experts and the cumulative gradient norm for each model within experts. The definition ofβ γ (T ) is provided in detail in equation (31) in the Appendix A.3. If there exists a γ ∈ 1 2 , 1 such that β γ (T ) ≤ Õ(T θ ) where θ < 1 -γ, then the coverage bound (11) will be CovE(T ) ≤ Õ T -min( 1 2 -γ,γ-1+θ) = o T (1).Theorem 3 Algorithm 2 achieves strongly adaptive regret over any interval I ⊆ [T ] and positive constants A, B, as followsEQUATION)whereEQUATION)Note that in equation ( 13), α m * n represents the miss coverage probability assigned to the best model for expert n, as obtained by equation (7).The miss coverage probability α m * n * in (13), is related to specific interval I, which can vary across different intervals with distinct distributions in a dynamic environment. In such settings, there is no fixed miss coverage probability α m * n * 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 ( 16), as demonstrated by the following lemma. The proof is provided in A.5.Lemma 1 By defining the variation of the loss function to beEQUATION)We establish the following bound for the dynamic regret of Algorithm 2EQUATIONwhere Õ suppresses positive constants and polylogarithmic factors, e.g., log T . Also the best miss coverage probability at each time t can be obtained byEQUATIONLemma 1 establishes that the dynamic regret of SAMOCP (15) depends on the variation of the loss functions ( 14). In addition, it can be obtained from (15) that SAMCOP achieves sublinear regret if the variation of the loss function is also sublinear, i.e., V (L(.) T t=1 ) = o(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 a detailed explanation of the experimental settings, followed by a discussion of the results. Note 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 available at hyperrefhttps://github.com/erfanhajihashemi/Multi-model-Ensemble-Conformal-Predictionin-Dynamic-Environments.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 is 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 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 experiment. Also, additional experiments on TinyImageNet-C [Hendrycks and Dietterich, 2019] and synthetic data are provided in the Appendix, Section B.Baselines and experimental settings: We employ ResNet-50, ResNet-18 [He et al., 2016] , GoogLeNet [Szegedy et al., 2015] , and DenseNet-121 [Huang et al., 2017] as candidate learning models. 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 Candès, 2022] , ScaleFreeOGD [Bhatnagar et al., 2023] , and SAOCP [Bhatnagar et al., 2023] . FACI employs a 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. ScaleFreeOGD 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 a 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 a 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 g = 8. While the hyperparameter g is set to 8 for both SAMOCP and SAOCP(MM), it is set to 32 for SAOCP, as in [Bhatnagar et al., 2023] . Since 4 learning models are incorporated in this section, the maximum number of updates at each time t in SAMOCP, M g⌊log 2 t⌋, is equal to that in SAOCP and SAOCP(MM), which is 32⌊log 2 t⌋. Meanwhile, note that randomness might be undesirable in practice, the predicted miss coverage in SAMOCP is calculated in a deterministic fashion, i.e., α t = n∈A(t) M m=1 hn t wmn t α mn t . For every experiment conducted on the synthetic dataset, CIFAR-10C, CIFAR-100C, parameters ϵ, σ, and η 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. LetEQUATIONwhere f m Y (X) denotes the probability of predicting label Y for input X by model m, and U t is a random variable sampled from a uniform distribution over the interval[0, 1]. The term k Y := |{Y ′ ∈ Y | f m Y ′ (X) ≥ f m Y (X)}| denotes the number of labels that have a higher or equal predicted probability than label Y according to the model's output probability distribution, e.g., the softmax output. ρ(X, Y ) :=K Y ′ =1 f m Y ′ (X)I[ f m Y ′ (X) > f m Y (X)] sums up the probabilities of all labels that have a higher predicted probability than label Y . The hyperparameters ξ and k reg are set to 0.02 and 5 for CIFAR-100C, and 0.1 and 1 for Cifar-10C, respectively.Evaluation Metrics: 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.Table 1 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 singlewidth 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 successive 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 a prediction set. Experimental results on CIFAR-10C are detailed in Table 2 , 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 to the target value.To demonstrate that SAMOCP achieves the lowest regret over different intervals compared to existing methods, we illustrate the regret for various interval sizes in Figure 2 . For each existing method, there are 4 different regrets corresponding to the 4 learning models used and the lowest regret is 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 adaptivity in capturing the distribution shift at different time scales. Therefore, Figure 2 indicates that the SAMOCP can adapt faster to distribution shifts compared to benchmarks in various time scales. Furthermore, we include experiments on synthetic data and another real dataset, TinyImageNet-C, using different sets of learning models that do not necessarily contain 4 models in the Appendix, Section B. This demonstrates how SAMOCP can rely on a mixture of learning models over the period [T ] and select the appropriate one for each distribution setting. 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 a coverage rate close to the target value, compared to those created by previous methods using their best baseline models.Lemma 2 For every α ∈ [0, 1] and learning rate η > 0, adaptive miss coverage probability α m t for any model m ∈ [M ] and t ∈ [T ] is bounded asα m t ∈ [-η, 1 + η] .A.1 Proof of lemma 2Based on equation ( 4), we haveEQUATION)We prove this lemma using a contradiction. Suppose there exists a t such that α m t / ∈ [-η, 1 + η], where t ≥ 2 is the smallest such time index. We first prove the case of violating the upper bound; by contradiction, assume α m t > 1 + η. According to equation ( 18), this would necessitate that α m t-1 ≥ 1. Given that we assumed t is the smallest time index to violate the upper bound, it should follow that α m t-1 ≤ 1 + η. However, α m t-1 > 1 > ᾱm t-1 implies err m t-1 = 1. By equation ( 4) we haveα m t = α m t-1 + η α -1 t-1 τ =1 ∥∇ α m τ L(ᾱ m τ , α m τ )∥ 2 2 ≤ α m t-1 ≤ 1 + η,which contradicts our assumption that α m t-1 > 1 + η. Next, assume α m t < -η. By equation ( 18), we have α m t-1 < 0. Given that t is the smallest index that violates the lower bound of the lemma, it must hold that α m t-1 ≥ -η. Considering α m t-1 < 0 < ᾱm t-1 , we deduce that err m t-1 = 0. Therefore, by equation ( 4), we haveα m t = α m t-1 + η α t-1 τ =1 ∥∇ α m τ L(ᾱ m τ , α m τ )∥ 2 2 ≥ α m t-1 ≥ -η,which contradicts our initial assumption that α m t < -η.A.2 Proof of Theorem 1, Regret for MOCP:Algorithm 1 has the following regret boundT t=1 M m=1 wm t L(ᾱ m t , α m t ) - T t=1 L( ᾱm * t , α m * ) ≤ √ T (1 + 2η) 2 2η + η 2α + ln M + (1 + η) 2 ,Where α m * can be obtained via (7). To prove the theorem, we first introduce and prove the following two lemmas Lemma 3 for miss coverage probability assigned to any model m ∈ [M ], we have the following boundT t=1 L( ᾱ m t , α m t ) - T t=1 L(ᾱ m t , α m) ≤ √ T 2η (1 + 2η) 2 + η √ T 2α,where α m = arg min α m t T t=1 L(ᾱ m t , α m t ). Proof: We first begin with (α m t+1 -α m) 2 = (α m t -η ∇ α m t L(ᾱ m t , α m t ) t τ =1 ∥∇ α m τ L(ᾱ m τ , α m τ )∥ 2 2 -α m) 2 .Then define adaptive learning rate η t [Duchi et al., 2011 , Hazan et al., 2007] asη t := η t τ =1 ∥∇ α m τ L(ᾱ m τ , α m τ )∥ 2 2 .So we have(α m t+1 -α m) 2 = (η t ∇ α m t L(α m t , α m t )) 2 + (α m t -α m) 2 -2η t (α m t -α m)∇ α m t L(α m t , α m t ).Therefore,(α m t -α m)∇ α m t L(ᾱ m t , α m t ) = (α m t -α m) 2 -(α m t+1 -α m) 2 2η t + η t 2 (∇ α m t L(ᾱ m t , α m t )) 2 .Since the loss function (2) is convex, we have the following inequalityEQUATIONBy summing (19) over t ∈ [T ] we haveEQUATION(i) used α m t ∈ [-η, 1 + η] by Lemma 2.Lemma 4 For miss coverage probability assigned to any model m ∈ [M ] we have the following boundT t=1 M m=1 wm t L(ᾱ m t , α m t ) - T t=1 L(ᾱ m t , α m t ) ≤ ln M ϵ + ϵ(1 + η) 2 T.Proof: Referring to the definition of wm t in Subsection 3.1 and defining W t := M m=1 w m t , we haveEQUATIONwhere W 1 = 1, (i) follows from the inequality exp(-ϵx) ≤ 1 -ϵx + ϵ 2 x 2 for |ϵ| ≤ 1, and (ii) follows from 1 + x ≤ e x . On the other hand, we haveEQUATIONwhere w m 1 = 1 M . By combining (21) and ( 22) we haveEQUATIONBy taking the logarithm on both sides we have-ϵ T t=1 M m=1 wm t L(ᾱ m t , α m t ) + ϵ 2 T t=1 M m=1 wm t L( ᾱm t , α m t ) 2 ≥ -ln M -ϵ T t=1 L(ᾱ m t , α m t ),which leads toEQUATION)Now, we define the best model in the static environment asm * = arg min m∈M T t=1 L( ᾱm t , α m t ).Then, we replace m with best model m * in Lemma 3 and 4.By setting ϵ = 1 √ T and summing results of two lemmas we have:EQUATIONA.3 Proof of Theorem 2, Coverage error for SAMOCP:We first define expected miss coverage error asE[err t ] = t n=1 M m=1 hn t wmn t err mn t .The proof of this theorem is based on a grouping argument. So we first divide T into ⌈T 1-γ ⌉ group for γ ∈ ( 1 2 , 1), and write the kth group asG k = {t k-1 + 1, . . . , min(t k , T )}.where|G k | ≤ ⌈T γ ⌉.We also define a new variable, H mn n:t , assigned to mth update rule of nth expert as followsH mn n:t := t τ =n ∥∇ α mn τ L(ᾱ mn τ , α mn τ )∥ 2 2 .So the update rule in (4) can be written as:EQUATION)For kth group where 2 ≤ k ≤ ⌈T 1-γ ⌉, by using (26) we haveE[err t ] -α = t n=1 M m=1 hn t wmn t (err mn t -α) = 1 η t n=1 M m=1 hn t wmn t (α mn t -α mn t+1 )H mn n:t .Since at each time t we activate an expert with lifetime as defined in (9), the nth expert will be activated at time t = n. Consequently, hn t will be 0 for t < n. Therefore, we have 1 η t n=1 M m=1 hn t wmn t (α mn t -α mn t+1 )H mn n:t = 1 η t k-1 n=1 M m=1 hn t k-1 wmn t k-1 (α mn t -α mn t+1 )H mn n:t k-1 + 1 η t n=1 M m=1 hn t wmn t (α mn t -α mn t+1 )H mn n:t - 1 η t k-1 n=1 M m=1 hn t k-1 wmn t k-1 (α mn t -α mn t+1 )H mn n:t k-1 = 1 η t k-1 n=1 M m=1EQUATIONWe define β γ (T ) as:EQUATIONThen we have:T t=1 E[err t ] -α = O(T 3 2 -γ + T γ β γ (T )).A.4 Proof of Theorem 3, static regret for SAMOCPWe can write the regret as where I ñ denotes the time interval during which expert ñ is active, starting at time t = ñ. The third and fourth terms in the expression are analogous to the regret experienced by expert ñ, as established in Theorem 1. To evaluate the regret for the first and second terms, we employ Lemma 4. The main difference is in 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 t would be gt. Thus, we derive the following bound for the first and second terms EQUATIONUntil this point, the regret bound we've established applies solely to intervals that start with expert ñ, where each interval's length corresponds to the lifetime of expert ñ. However, to derive a regret bound for any arbitrary time interval I, we need to partition the interval into subintervals in a suitable 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 -p , ..., I 0 ) and (I 1 , ..., I q ), such that |Ir+1| |Ir| ≤ 1 2 for all r ∈ (1, q -1), and |Ir| |Ir+1| ≤ 1 2 for all r ∈ (-p, -1). Subsequently, by employingIn 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 a 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 as brightness, contrast, saturation, and hue in minor increments, we challenge the models to perform reliably under varying lighting conditions and color settings-typical variations that occur due to different times of the day or inconsistencies in camera settings. Additionally, 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 transformation type. These datasets are designed with a fixed number of 20 classes and hyperparameters ξ and k reg 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 a single transformation, while sudden shifts occur when switching between datasets from different transformations. We conducted experiments using a distinct set of learning models. As shown in Table 3 , we incorporated two learning models, Efficientnet_b0 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 is almost five times larger than our method's. We also provide synthetic data analysis using another set of learning models consisting of GoogLeNet, DenseNet-121, and EfficientNet-B0 [Tan and Le, 2019] , as detailed in Table 4 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. Here, we conduct the experiment on a new dataset involving a gradual distribution shift using a new real dataset, TinyImageNet-C, which is a corrupted version of the TinyImageNet [Le and Yang, 2015] dataset that features 200 distinct classes. We have also incorporated a new mixture of learning models-GoogLeNet, DenseNet-121, EfficientNet-B0, and MobileNet-V2 [Li et al., 2021] to demonstrate the performance of our algorithm. In Table 5 , we detail our proposed method's comparison with previous methods, where, once again, our algorithm is able to achieve smaller prediction set sizes while maintaining coverage close to the target value of 1 -α. It is reasonable to study prediction sets in situations where we achieve coverage close to the desired level. The SAOCP(MM) method achieves coverage of less than 85%, which is significantly below the target value. Therefore, we do not consider its prediction sets in our comparison. As demonstrated in the table, SAMOCP obtains smaller prediction sets and operates faster than SAOCP. For the TinyImageNet-C dataset, the parameters η, ξ and k reg 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.  
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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.

2. 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?

3. 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?

4. How is the number of experts chosen?

Minor:
There seems to be a typo in line 134: the miscoverage probability $\alpha_{t+1}^m$ can be updated via ..., instead of $\alpha_{t}^m$. 

For 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: limitations: The authors addressed the limitations of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: The intuition behind the proposed algorithm in the dynamic environment (Section 3.2) is not sufficiently developed.
questions: questions: 1. In Algorithm 1, how should \(\epsilon\) be chosen?

2. How does this multi-model approach perform compared to retraining the non-conformal score after each update?

3. 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.

4. 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: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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?
4. It is suggested to provide a Complexity Analysis of the overall model.
questions: questions: See in the Weaknesses.
limitations: limitations: The limitations of the authors have been pointed out in the Conclusion.
paper_summary: paper_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.
strength_weakness: strength_weakness: Please see questions in the following section.
questions: 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.

2. [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.

3. [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.

4. [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: Limitations are discussed in the paper.

Comments: title: Official Comment by Authors
Question
Follow-up comments
comment: Thank you for your willingness to increase the scores based on our response, and for pointing out the confusion regarding "multimodal" and "multimodel." We understand the concern. According to your comment, we will change "multimodal" to "multimodel" to avoid confusion. We appreciate your insightful comment, and we agree that this change will help improve the clarity of the paper. We would be happy to further clarify any remaining questions or concerns you may have. Please let us know if you have further questions or concerns.
I want to thank the authors for their responses and clarifications. I have read through all of them and am willing to increase my score. However, my confusion still persists: why is the method named "Multimodal Conformal Prediction"? In my view, there is a significant difference between "multimodel" and "multimodal." "Multimodel" typically refers to the use of multiple models, often based on ensemble learning, whereas "multimodal" pertains to multiple types of data, which should account for the interaction between different modalities, leading to different methods or theoretical assumptions.
Thank you to the authors for the detailed responses. I am happy to maintain my current score and have increased my confidence in it.
Thank you for the references and additional simulation studies! I'll maintain my scores at this moment and keep the authors' responses in mind for my evaluation through the discussion period.