Conformal Prediction for Time-series Forecasting with Change Points

We thank the reviewer for their positive assessment of our work, acknowledging the clarity, experimental rigor, theoretical soundness, and novelty of our method. We address the points raised below.

Weakness1 / Q1. Could authors explain when the assumption for the time series holds?

The SDS assumption (Equation 5) is appropriate for time series that exhibit regime-switching behavior - i.e., periods where the underlying data-generating process remains relatively stable, punctuated by abrupt shifts to different regimes. This includes:

• Naturally regime-switching domains: Electricity demand (day/night cycles), traffic flow (weekday/weekend patterns), financial markets (volatility regimes), and manufacturing systems (operational modes)
• Time series with predictable change points: Where shifts correlate with observable covariates or temporal patterns
• Systems with discrete operational states: Industrial processes, biological systems with distinct phases, or any domain where the underlying process can be characterized by a finite set of behaviors

Importantly, our method doesn't require perfect adherence to the SDS assumption. Theorems 4.2-4.3 show robustness to (1) imperfect state predictions (Theorem 4.3) (2) model misspecification, and (3) unknown shift mechanisms. This means that even if the learned states are not perfectly aligned with true underlying "modes," or if the assumption of distinct switching states is only an approximation, our adaptive calibration mechanism ensures overall coverage validity, as experiments show in Section 5.2. The trade-off, as shown in Table 3 (page 9), is that less accurate state predictions might lead to wider prediction intervals, even if coverage remains valid. This highlights the practical utility of our method: it offers a robust solution even when the "true" underlying states are not perfectly known or precisely modeled.

We will highlight the above points in the paper’s discussion section to further clarify. We thank the reviewer for raising this important discussion.

2. Could authors explain how to select the number of possible regimes in predicting the states? Would that affect the performance of the method?

We designed the number of latent states to be a hyperparameter given by the user. Our method ensures that the validity guarantee still holds even if the state cardinality is incorrect (theorem 4.2), as incorrect state cardinality can be formulated as a case of incorrect classification. Determining state space cardinality is a well-studied problem (see for example [3]), and we consider it to be beyond the scope of our paper.

Regarding the effect on performance, our ablation studies (Section 5.2, page 9, Tables 2 and 3) demonstrate that while the validity (coverage) of CPTC is robust to errors in state prediction, the sharpness (width of prediction intervals) can be affected. Table 3 explicitly shows that "the more accurate the state prediction is, the sharper the intervals." This implies that selecting a more appropriate number of regimes that better captures the true underlying dynamics would lead to narrower and more efficient prediction intervals.

[3] Branicky, Michael S. "Stability of switched and hybrid systems." Proceedings of 1994 33rd IEEE conference on decision and control. Vol. 4. IEEE, 1994.

3. If the state predictor works very poorly, will the performance of the method be similar to the performance of ACI?

Yes, exactly. There will be Z (depends on the number of states specified by the user) concurrent ACI processes.

We thank the reviewer again for the thoughtful review; please let us know if our response answers your questions.

Thank the authors for their careful answers, and I will keep my rating of 4.

We thank the reviewer for their insightful comments and appreciation of our work. We address the points raised below:

1. In table 1, why is the coverage of ACI invalid? It seems that both theoretical and empirical results in other papers (see [1] and [2]) show that ACI will achieve long-term coverage despite fluctuations and inefficient intervals. Does this correlate to the choice of learning rates ? The authors should discuss it in depth.

We appreciate this crucial question. The authors of ACI themselves acknowledge failures in their original ACI method in their follow up work [5]: "Previous approaches to this problem [including their original ACI] suffer from over-weighting historical data and thus may fail to quickly react to the underlying dynamics." ACI’s slowness to adapt to abrupt changes is also analyzed in [6]. ACI needs a long horizon for it to balance the under-coverage with over-coverage, as seen in the case of [2] where T= 2000, and in [1] where T=3000 (election) or 5000+ (stocks). As expected, in the case of longer time horizons, ACI achieves near-valid coverage on our datasets (table 4 in Appendix).

We mention in our analysis (lines 305-306, page 7), "In the pretense of change points, ACI's coverage fluctuates dramatically and does not converge within the horizon." While ACI is asymptotically valid, the coverage can fluctuate significantly in shorter time horizons, especially in the presence of abrupt distribution shifts or change points, as observed in our experiments.

This brings us to the main contribution of CPTC: We show that fast adaptation is important for shorter time series (T = 200 for our synthetic datasets, 400 for electricity and traffic, and 60 for bees), where the ability to anticipate distribution shifts can significantly improve both coverage and efficiency. Time series of < 500 length is common in practice (health time series, user activity of web services or apps, and physical/chemical/biological systems with distinct phases), and we developed CPTC to be a practical and sound CP variant for these situations.

[5] Angelopoulos, Anastasios, Emmanuel Candes, and Ryan J. Tibshirani. "Conformal pid control for time series prediction." Advances in neural information processing systems 36 (2023): 23047-23074.

[6] Gibbs, Isaac, and Emmanuel J. Candès. "Conformal inference for online prediction with arbitrary distribution shifts." Journal of Machine Learning Research 25.162 (2024): 1-36.

2. The experiment section is outdated.

We thank the reviewer for bringing these two important works to our attention. We have now added these baselines to our experimental comparison in Table 1 (see table below). We will add more analysis with visualizations in the finalized version of our paper.

We would like to emphasize that these methods, just like the ones reported in table 1 of the paper, are reactive. The question we try to address with CPTC is - what happens when we can anticipate distribution shift? CPTC is designed such that it greatly improves coverage compared to purely reactive methods, while still maintaining the ability to adapt to unknown shifts. To our knowledge, there are no other models that explore the same problem; CPTC provides practitioners with a simple and sound solution, when they have the ability (such as via a state space model) to predict shifts.

3. CPTC assumes the system consists of several underlying states, such as day/night. However, in the area of conformal prediction, it seems more appropriate to use group-conditional-based methods like [4] and the baseline should add such methods. How do the authors comment about this?

Thank you for bringing this work to our attention! We have added L-ARC (with miscoverage as loss function) as a baseline in the table below. We see that in the case of shorter time series with switching uncertainty dynamics CPTC outperforms the baseline.

L-ARC shares commonalities to our setting and result, but it differs in that:

The localization of L-ARC comes from adjusting the threshold using a kernel function for the inputs $X_t$ (RBF kernel in most of the paper’s experiments). That means (1) the kernel weighting would need to be learned online, and the more complex/localized the landscape is, the more samples the algorithm needs, and (2) the kernel needs to be hyper parameter-tuned to fit the data’s latent space. These properties make L-ARC less sample-efficient compared to our method, and more similar to the online regression-based CP methods like HopCPT and SPCI. These works provide approximate (sample-)conditional coverage guarantees similar to L-ARC; CPTC merely provides group-conditional guarantees.

We thank the reviewer again for the thoughtful review; please let us know if our response answers your questions.

We thank the reviewer for their insightful comments and appreciation of our work. We address the points raised below:

1. Probabilistic model inconsistency

We choose the mean of the forecaster output as the deterministic forecast. This is common practice in time series CP works, such as the use of DeepAR in [1,2]. We will clarify the usage in the paper per the reviewer’s suggestion. Yes, thank you for your correction. We will use P(z_t|x_{0:t}) to indicate the predicted probability of states in our paper, in order to stay consistent with the SDS model introduced in the background section.

[1] Xu, Chen, and Yao Xie. "Conformal prediction interval for dynamic time-series." International Conference on Machine Learning. PMLR, 2021. [2] Xu, Chen, and Yao Xie. "Sequential predictive conformal inference for time series." International Conference on Machine Learning. PMLR, 2023.

2. Larger number of latent states vs. two aggregation metrics.

This is a great observation. We found that the difference between the two aggregation methods does not depend on the number of states, but the discrepancy of (1) behavior and (2) magnitude of uncertainty between the most likely states. In the case where there are many states and the behaviors vary a lot, equation (11) outputs over-covering large intervals during state transitions. As this result is hard to present with tables, we will include qualitative visualizations in the finalized version.

3. What are the effects of the size of the latent state? How do you know what's going to be the right number of latent states for each data set?

We designed the number of latent states to be a hyperparameter given by the user. Our method ensures that the validity guarantee still holds even if the state cardinality is incorrect (theorem 4.2), as incorrect state cardinality can be formulated as a case of incorrect classification. Determining state space cardinality is a well-studied problem (see for example [3]), and we consider it to be beyond the scope of our paper.

Please see table below for results on our Z-mode system synthetic setting with misspecified states - when Z is misspecified, the uncertainty sets becomes larger, in line with the behavior we see for state predictors with large misclassification rate in Appendix B.4.

[3] Branicky, Michael S. "Stability of switched and hybrid systems." Proceedings of 1994 33rd IEEE conference on decision and control. Vol. 4. IEEE, 1994.

4. The expectation notation taken in Theorem 4.2

The expectation is taken over the data generation process at time $t$ for $(x_t, y_t)$. The notation is consistent with derivation in the ACI paper by Gibbs & Candes. it simply means $E[err_t] =P (Y_t\not\in \Gamma_t (\alpha_t))$. We will clarify before introducing the expectation in our proofs.

5. “Deterministic latent states” and “stochastic continuous states”

We thank the reviewer for capturing this error, it was a typo during writing. We will change the sentence at line 600-602 to “We sample $N=100$ of ${(z_t, x_t, y_t)}_{t=1}^k$ triplet trajectories from the trained model by Monte Carlo sampling, and use the samples to calculate prediction quantiles for table 1, in accordance to the original paper.”

6. What is the effect of the data set size?

Our model is purely online, so the effective data set is the warm start window $w$ and the total time series length. We study the effect of a longer horizon and warm start in section B.4.

Intuitively, larger training data will result in a better prediction and state-transition model. We have proven in the paper that the validity guarantee will hold regardless of the performance of the base models.

7. Multivariate time series

Our method does apply to multivariate time series. The Bee dataset is an example - the time series is 6 dimensional, and the prediction is on the first 2 dimensions. Under the conformal prediction framework, the nonconformity score is always a scalar. Many papers explore the topic of tailoring CP to be efficient for multivariate data [4,5]. They are orthogonal to our method and can be used in combination. To incorporate the reviewer's suggestion, we will add the above paragraph to the appendix to clarify.

[4] Xu, Chen, Hanyang Jiang, and Yao Xie. "Conformal prediction for multi-dimensional time series by ellipsoidal sets." arXiv preprint arXiv:2403.03850 (2024).

[5] Messoudi, Soundouss, Sébastien Destercke, and Sylvain Rousseau. "Copula-based conformal prediction for multi-target regression." Pattern Recognition 120 (2021): 108101.

8. Organization

We appreciate the reviewer’s suggestion. Equation 9 was included in section 4.1 for clarity and completeness, but we will introduce the online update algorithm in the background section as well.

We thank the reviewer again for the thoughtful review; please let us know if our response answers your questions.

1. Could the authors provide the computational complexity of the proposed method and compare it with that of previous approaches?

We provided computation complexity comparisons in Appendix B.2, as follows:

“All experiments are done on a server machine with an Nvidia A100 GPU, with some data processing 607 and analytics performed on an Apple Macbook Pro laptop computer with M1 chip. As running time varies greatly depending on implementation and hardware, we provide a rough range of algorithm 609 runtime. Training the RED-SDS base model (1 seed) takes 2-5 hours for our datasets, and inference takes around 15-20 minutes for all datasets. Among the conformal prediction baselines, SPCI is the most computationally demanding, taking 8-10 hours for inference on our benchmarks. HopCPT follows, taking around 1 hour. CP, ACI, and our method CPTC do not require extensive inference-time computation, completing all inference within 5 minutes”.

Being computationally light and fast is a strength of CPTC - no fitting or re-fitting of residual prediction models is needed after each time step, as in the case of previous works HopCPT and SPCI.

2. How is warm start data selected?

The warm start window is the first $w$ steps of each test time series. There is no selection in the sense of choosing some data over others. We report the metrics averaged over horizon $T$ and then over the N test samples.

he length of the warm-start window, $w$, is 25% of the length of the time series in our datasets. In baseline methods, the warm start window is typically very large - HopCPT uses 15-33% of time series of length in the thousands to tens of thousands for calibration.

3. Could the authors clarify how the state transition model is constructed? Specifically, is the transition matrix learned offline, and is the probability of switching between states kept fixed during all test-time steps?

Yes! The discrete latent states are extracted from a base model that is learned offline. Namely, we use the RED-SDS model ([8] in the paper) for all of our data sets because of its performance on time series datasets. The state transitions are not updated online, and the adaptive updates to the conformal thresholds are designed primarily to correct for state prediction errors. We do not assume the probability of switching states is kept the same, but we do assume the resulting state distribution to be stationary (assumption 1 in paper).

The motivation of our algorithm is that, for many systems that require UQ, the model already models a discrete state. In this paper we study how such information can be utilized to anticipate distribution shifts in prediction behavior and thereby improve validity of UQ. Studying the more complex setting of updating/adapting switching states would be a great direction for future work.

4. Compare to previous works [1] and [2]

We thank the reviewer for bringing these two works into our attention. We have added [1] as a baseline (see table below), and will provide more analysis with visualizations in the finalized version of our paper.

[2] (Hajihashemi and Shen, 2024) introduces a multi-model ensemble conformal prediction (SAMOCP) framework, and the focus of their work is on optimizing model selection within a pool of experts, combining them to achieve coverage. This is different from our setting where the SDS is a single integrated model. We acknowledge the similarity in the motivation and will cite [2] in our literature review.

The drawback of both these methods compared to CPTC is that they are reactive. The question we try to address with CPTC is - what happens when we can anticipate distribution shift? CPTC is designed such that it greatly improves coverage compared to purely reactive methods, while still maintaining the ability to adapt to unknown shifts. To our knowledge, there are no other models that explore the same problem; CPTC provides practitioners with a simple and sound solution, when they have the ability (such as via a state space model) to predict shifts.

I see! sorry for the misunderstanding. We provide a comprehensive analysis below, comparing the aggregation methods in Equations 10 and 11 and with baselines.

Notation

• $T$: Total timesteps, $K$: Number of states, $M$: State prediction model inference complexity
• Score sets $\mathcal{S}_z$ maintained in sorted order (quantile computation in $\mathcal{O}(1)$, insertion $\mathcal{O}(\log T)$)

Complexity Per Timestep

1. Computing quantile $Q^{1-\alpha_{z,t}}(\mathcal{S}_z^{(t)})$ for each state, totaling $\mathcal{O}(K)$.
2. State Prediction: computing $\hat{p}(z_t|x_t)$ and sampling a state, totaling $\mathcal{O}(M)$.
3. Aggregation

• Eq. 10, Weighted Level-Set: $\mathcal{O}(K \cdot \lceil 1/\delta \rceil^d )$ where $\delta$ is discretization resolution
• Eq. 11, Union: $\mathcal{O}(K \log K)$ for sorting states by probability

4. Updates: $\mathcal{O}(\log t)$ for inserting new score into sorted set.

Therefore, the total complexity of CPTC with horizon $T$ is:

$\mathcal{O}(T \cdot (M + K \cdot \left\lceil \frac{1}{\delta} \right\rceil^d)+ T \log T)$ if we use the Weighted Level-Set as aggregation in Eq. 10, and

$\mathcal{O}(T \cdot (M + K \log K) + T \log T)$ if we use the more efficient Union aggregation in Eq. 11.

In practice, both $M$ (inference cost) and $K$ (number of discrete states) are small. For applications where $K = \mathcal{O}(1)$ and $M = \mathcal{O}(1)$, CPTC achieves near-linear scaling $\mathcal{O}(T \log T)$, the same as ACI (see table below).

If we use the more precise weighted level set aggregation method, the runtime largely depends on the discretization resolution $\delta$, output dimension $d$, and the number of states $K$. We remark the level set approach scales poorly if the resolution, dimension, or number of states are high.

We will incorporate this analysis into the appendix of the paper. We thank the reviewer again for the constructive feedback, which has helped enhance the overall quality of our work.