Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper develops an online predictive inference technique motivated by conformal inference. The proposed method achieves the target coverage rate ($1-\alpha$) as $T \to \infty$. For finite $T$, the coverage is at most $O(1/T)$ away from $1-\alpha$. Experiments on two real datasets illustrate that the method exhibits improved behavior as compared to a non-adaptive baseline.

I feel that the main insight/contribution of the paper is to draw an elegant connection between two apparently disjoint areas, namely 1) post-hoc uncertainty quantification and 2) online learning. The methodology of the paper is mostly inspired from a post-hoc uncertainty quantification setup inherent in split conformal, where some part of the model is treated as 'fixed' and only a few parameters are optimized towards some goal (in this case, a single parameter, the quantile level $\alpha_t$ is learnt). On the other hand, the theoretical analysis is very different from other conformal papers. It is in the adversarial setting and the technical tools used are similar to those used in the online learning literature. 


main_review: As mentioned above, I think that the work is an original and significant contribution to the conformal literature. The experiments, although not extensive, nicely supplement the theory. Being quite familiar with conformal inference, I found the paper easy to follow (except the theorems in Section 4.2; see more below). However, I felt that the paper lacked a certain 'attention to detail' or 'polish' that the technical ideas are highly worthy of. I have made some suggestions below. 

_Major comments regarding writing:_
- Line 30: This is not true for many recently popular conformal techniques: jackknife+ [1], cross-conformal [2], and out-of-bag conformal [3], all of which (roughly) get $1 - 2\alpha$ coverage. Please update or qualify this claim. 
- Section 4.2: I was unable to really understand Theorems 4.1 and 4.2 due to the little t's which are not qualified as part of the statement. I am not sure what the expectation is over in defining $B$ and $\sigma_B$. Similarly I am not sure what the expectation is over on the LHS and RHS of eq. (7). Could the authors please clarify this? 
- Line 279: Since Neurips is an international conference, I believe it should be specified that the authors mean the 2020 United States of America presidential election. The description of the dataset (until line 291) strongly assumes that the reader is familiar with the US election system: Who is Joe Biden? What is election night? The west (east) coast of what? 

_Minor/subjective comments:_
- I felt that the paper was heavy on notation, which could be overwhelming for readers unfamiliar with conformal inference. The authors can consider reducing notation in order to reach a larger audience. I also propose a different way of looking at the algorithm proposed by the authors in the next section, which would probably require less notation. 
- Section 2.2: I felt that this section broke the flow of the rest of the paper 
- Title of Section 4.1: what is the meaning of 'general results'? 
- Line 221: “there is little doubt that the theory can be extended, recall our main goal [is] to get useful and simple results”: Did the author mean to say that it is unlikely that the theory can be extended to practical settings? What they have said conveys the opposite meaning (there is no doubt that the theory can be extended to practical settings).
- Initially the subscript to M denotes ‘time’. Later, in Theorem 4.2, it denotes ‘action’. I suggest using slightly different notation (such as bracketing) for the two. 

**_A reinterpretation of the methodology proposed in the paper_**:

I had a reinterpretation of the method proposed by the authors, based on 3 technical tools: pinball loss [4], online subgradient descent [5], and nested conformal [3].

First, for any time i, define a family of nested sets ${F_t}$ based on [3]; such a family can be defined for any nonconformity score. Then define $ t_i := \inf t: Y_i \in F_t(X_i)$. Suppose $F_{s_i}$ is the predicted prediction set at time step i, then for $1-\alpha$ coverage, what is needed is that $s_i \geq t_i$, at least $1-\alpha$ of the times. In other words, for optimal coverage, **$s_i$ should be the $1-\alpha$ quantile of $t_i$**. A popular way to optimize for quantiles is to use the pinball loss. The proposed method (2) optimizes $\sum_{i=1}^T \text{pinball-loss}(1-\alpha,s_i, t_i)$ using online subgradient descent.

Do the authors agree with this interpretation? If yes, including it would enhance the paper, maybe even in an Appendix. I personally found this to be a cleaner way to understand the main idea: it requires less notation and alludes to other ideas that readers may already be familiar with. 

_References:_

[1] https://arxiv.org/abs/1905.02928

[2] http://proceedings.mlr.press/v91/vovk18a.html

[3] https://arxiv.org/abs/1910.10562

[4] http://www.econ.uiuc.edu/~roger/research/rq/QRJEP.pdf

[5] https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf

limitations_and_societal_impact: To the best of my understanding, the approach proposed does not guarantee that C_T(\alpha_T) has 1-\alpha coverage for a fixed time T, no matter how large T is. Proposition 4.1 only holds on _average_ across time. The authors make the following claim in the abstract, "our adaptive approach provably achieves the desired long-term coverage frequency irrespective of the true data generating process". I think that this claim needs to be (transparently) supplemented with the limitation described above.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposed an adaptive method to estimate a confidence set such that the target value falls into (conformal with) the set within a given probability. It adjusts the coverage level \alpha_t in the current round t based on the error from previous rounds (see Eq.(2)). Empirical demonstrations on stock markets and the 2020 presidential election poll show that the proposed adaptive conformal inference (ACI) method can better reach the targeted coverage level than using a fixed alpha.
main_review: Pros
- A straightforward method that is well-explained
- Theoretical justification under certain assumptions

Cons
- The theoretical analysis does not lead to practical guidance
- Insufficient discussion and comparison with related papers

Detailed comments

Overall, it is an interesting paper demonstrating the possibility and advantage of using an adaptive method to handle distribution shifts in conformal inference. However, I have the following concerns.

1. Regarding the theoretical analysis, it lacks practical guidance on choosing the step-size gamma. More specifically, the step size in Thm.4.2 relies on a future quantity that is unknown in practice. Given that the Markov chain is assumed to be mixed, wouldn't it be possible to derive a more practical choice of gamma based on the history?

2. The current paper discussed the coverage but lacks a discussion on the interval width, which is also important in practice. For example, see Kivaranovic et al. (2020) and Chen et al. (2021), which provide more thorough treatment for the problem and it would be necessary to discuss/compare.

- Kivaranovic, D., Johnson, K.D. and Leeb, H., 2020, June. Adaptive, distribution-free prediction intervals for deep networks. In International Conference on Artificial Intelligence and Statistics (pp. 4346-4356). PMLR.
- Chen, H., Huang, Z., Lam, H., Qian, H. and Zhang, H., 2021, March. Learning prediction intervals for regression: Generalization and calibration. In International Conference on Artificial Intelligence and Statistics (pp. 820-828). PMLR.

3. Empirical studies. 

- L145 mentioned that "These stocks were selected out of a total of the 13 stocks that we examined because they showed a clear failure of the non-adaptive method". However, it seems to me the non-adaptive alpha works fine for AMD. If ACI is indeed performing well for the rest out of 13 stocks, it would be helpful to see the actual improvement (maybe in Appendix) instead of simply claim it without evidence. 

- For the results in Fig.2, it would be informative to see the deviation from the ideal 0.9 as sigma changes for the two methods. Currently, only specific values are chosen and it is not clear why.

- There is no comparison to competitive methods in the literature other than a fixed-alpha baseline. It would be more convincing if the proposed method can be compared to the methods mentioned in the above reference.

Minors

- Appendix A.2, it might be better to put both curves (using (2) and (3) respectively) in one figure so that they can be compared more directly.
- The alpha in the GARCH(1,1) model (Equation below L127; also the \hat{\alpha}_t in L132) has a different meaning from the alpha in most parts of the paper (E.g., in L137), which is likely to confuse readers.
- L294, sigma>0 should be sigma>=0 as seen in the leftmost of Fig.2.
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper proposes a conformal inference based technique that is an online adaptation to handle distribution shifts over time that has statistical guarantees for coverage of predictive distributions. The technique discretizes the updates and adapts marginal coverage with respect to limitations observed in prior steps. The authors demonstrate its usage in predicting market volatility and 2020 presidential elections.
main_review: Originality: The authors propose an online adaptation of conformal inference to handle distribution shifts. There have been work on this front by Tibrishani  et al. and Cauchois et al. which were cited but I found the comparison of the proposed technique with respect to these techniques limited. The novelty on top of conformal quantile regression can be argued to be minimal and the authors propose a simple modification of these techniques to propose an online version. This modification is a well-known adaption of various techniques in general. 

Quality: The paper provides theoretical analysis of the claims; however, I think there is a bit of a room for improvement in experimental results through comparisons with prior work. 

Clarity: The paper is very well written and organized.

Significance: Online extension of conformal inference provides an interesting research direction. However, the models used in practice are generally frequently trained. Applying the adaptive version proposed in this paper on frequently trained models can still be applicable but the paper is lacking the experiments that provides comparisons to illustrate the added benefit of applying adaptive conformal inference in such scenarios. I think these additions would further validate the significance of the proposed approach.

Specific comments:
-	I think comparisons with respect to online trained models would be a highly important comparison to support the general usability of this technique. 
-	I would recommend comparisons with respect to prior work that is already cited. For instance for the experiments with election results, the assumption of conditional distribution being constant between training and test sets by Tibrishani et al. is a valid assumption and it would have been interesting to see the predictions in comparison.
-	The proposed method is effective if the distribution shift happens gradually so that it is able to maintain it’s coverage over the shift period. The method will provide coverage guarantees when this change does not happen abruptly. This might be an important limitation to mention in the paper and discuss extensions. 
-	The paper focuses on marginal coverage but conditional coverage (https://arxiv.org/pdf/2006.02544.pdf) is an important metric to illustrate statistical properties. If shown to have nice properties, this might make the results more powerful. I would recommend adding results with conditional coverage as well which will make the results more compelling.
-	Please comment on the jump from 84% to 95% local coverage level for Figure 2a.

limitations_and_societal_impact: The authors discuss the limitations in the manuscript. I also provided more suggestions above to further enhance this discussion.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides a method for calibrating prediction sets in an online setting. The method adjusts the level of an underlying conformal prediction algorithm according to the number of miscoverage events observed previously in the trajectory. The authors prove that the empirical miscoverage rate never exceeds the desired level, regardless of the data-generating distribution at each step. The authors also provide an additional analysis of the tails of the empirical empirical error count in the setting where the data-generating distribution is a hidden Markov model (confirming that several intuitions apply in this case), as well as two applications involving real data.
main_review: This paper is cleanly written, and easy and enjoyable to read. The idea is interesting, and the strong guarantee provided by Proposition 4.1 in general settings is very nice. The results in section 4.2 nicely confirm several intuitions presented earlier in the paper.  Finally, the two real-world examples seem worthy and interesting applications, and additionally show some interesting failure modes of existing conformal prediction methods.

The empirical results provided, while thought provoking, could be improved by providing some details as to what the actual prediction intervals returned by the method look like (as opposed to just the miscoverage rates). This seems crucial given the generality of the method, which Proposition 4.1 shows would be correct (i.e. would produce the specified miscoverage rates) even if $\hat{Q}_t$ were a very poor approximation to the true quantile function.

Separately, while overall the paper is extremely well-written, I found the final paragraph of section 4.1 a little confusing. At a low level, my own calculations suggest the left-hand side of the equation under line 192 should be
$$
\mathbb{E}[\mathrm{err}_t] - \alpha
$$
instead of what is written, and the right-hand side of the equation under line 193 should
be
$$
\frac{1 - (1 - \gamma)^T}{T \gamma}|\alpha_1 - \alpha|
$$
instead of what is written (unless I have made a mistake).  I then do see an underlying similarity between the resulting bound and the right-hand side of (5), but I didn't understand the relationship between $\mathrm{max}\{\alpha_1, 1 - \alpha_1\}$ and $|\alpha_1 - \alpha^\ast|$ described (although I agree that the latter is an upper bound to it).

Finally, minor typos:

* Line 48 -- "points predictions"
* Equation under line 181 -- $\infty$ should be $-\infty
limitations_and_societal_impact: The authors include an interesting and broad discussion of the limitations of their method. They do not discuss potential negative societal impact, but their justification for not doing so in the Checklist seems reasonable.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes a method for online adaptive conformal prediction, where the data generating distribution is unknown, and varies over time. Conformal prediction is a distribution-free uncertainty quantification methodology that forms prediction sets $\hat{C}$ for an input $X$ such that the response variable $Y$ is covered with probability $1 - \epsilon$. (This is similar in spirit to confidence intervals.) The foundational assumption supporting the majority of conformal inference techniques is exchangeability of calibration data and test data. This work departs from that limiting assumption, and develops a simple but rigorous approach that models continual distribution shift over time. 
main_review: === Strengths ===

- The paper is well-written, clear, and well-motivated. Distribution drift can be a significant issue in many real problems, and therefore adaptive confidence algorithms that can account for this are necessary.

- The main algorithm of the paper is simple and easy to implement (which is a strength!). It reminds me of proportional control for PID controllers, though the analysis and applications differ.

- The experiments are interesting and clearly real world tasks, that also clearly have distribution shift. This is great for illustrating to the community examples of problems the proposed approach helps solve. Empirically, the adaptive technique here performs well (especially compared to non-adaptive baselines that can fail catastrophically).

- The extended analysis in the hidden Markov model in Section 4.2 is helpful in illustrating what sort of performance we might be able to expect on a more precise level (as the guarantee in Section 4.1 is somewhat loose).

=== Weaknesses/Limitations ===

- The main drawback is that without further assumptions (such as those modeled in 4.2), we only have asymptotic control of the average error. In intermediate time intervals, we might have very conservative or anti-conservative predictions. That said, the theory in Section 4.2 is helpful in giving some intuition on these aspects, combined with the positive empirical results in Section 5.

- Returning to the control theory view, I wonder if it would be helpful to incorporate full PID control to achieve better dynamics (i.e., more quickly adjusting to sudden, but permanent shifts in distribution, or alternatively, dampening out adjustments due to outlier disturbances).

- The assumptions that this paper makes are minimal, which makes the possible approaches fairly limited. Though I agree that it would be out of the current scope, it would be interesting to see if some techniques from other recent distribution-shift conformal inference (e.g., Tibshirani et. al. and Cauchois et. al.) could be incorporated as part of the wrapped model to improve empirical performance. For example, if *batches* were observed at time t so that a flawed but decent likelihood ratio model could be fit (maybe with regularization on importance weights), perhaps the importance weighting technique of Tibshirani could be approximately used to improve estimation of $\hat{Q}_t$.

=== Justification for score ===

I think that this paper would make a good contribution to the NeurIPS program.

=== Minor comments ===
- typo in the proof of Lemma A.2 (double note denote).
limitations_and_societal_impact: I do not forsee any negative societal impact (other than that inherited by the blackbox models the conformal inference package wraps).
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: In this paper, the authors introduce an extension to (split) conformal prediction under distributional shift over time known as adaptive conformal inference (ACI). Instead of relying on exchangeability, the method relies on tracking a scalar parameter $\alpha_t$ which compensates for the discrepancy between the empirical miscoverage and target miscoverage $\alpha$. The authors provide theoretical coverage guarantees on long-run error rates under weak assumptions, and further provide concentration inequalities and single time coverage guarantees under stronger Markov conditions. The adaptive method is compared to usual conformal prediction on two examples.

main_review: Strengths:

I really enjoyed reading this paper. The writing is very clear, and the authors provide clear intuition for the theoretical results.  Although the method is simple, relying on adapting the miscoverage level $\alpha_t$ in an online manner instead of exchangeability is novel. The method remains very general like regular conformal prediction, requiring only a predictor. The generality of the theoretical results is also impressive, as the assumptions are quite weak for Section 4.1 and the Markov setup of Section 4.2 is sufficiently complex. The Propositions/Theorems are also easy to interpret.  The experiments convincingly demonstrate the correct coverage achieved by ACI under time-varying distribution shift, and the role of the sequence $\alpha_t$ is easy to interpret. The empirical results match nicely with theory in terms of long-run coverage. 

#####################################################################

Weaknesses/Questions:

I only have minor suggestions:

1.) In the discussion, it may be worth including a brief discussion on the empirical motivation for a time-varying $\hat{Q}_t$ and $S_t$, as opposed to a fixed one as in Section 4.2. For example, what is the effect on the volatility of $\alpha_t$ and also on the average lengths of the predictive intervals when we let $\hat{Q}_t$ and $S_t$ vary with time?

2.) I found the definition of the quantile a little confusing, an extra pair of brackets around the term
\begin{equation}
\left(\frac{1}{|\mathcal{D}|} \sum_{\left( X_r,Y_r\right)\in \mathcal{D}} \mathbf{1}_{S(X_r,Y_r) \leq s}\right)
\end{equation}
might help, or maybe defining the bracketed term separately if space allows.

3.) I think there are typos in Lines 93, 136, 181 (and maybe in the Appendix too): should it be $\hat{Q}_t(1-\alpha_t)$ instead?


#####################################################################

Overall:

This is a very interesting extension to conformal prediction that no longer relies on exchangeability but is still general, which will hopefully lead to future work that guarantees coverage under weak assumptions. I believe the generality also makes this method useful in practice.

limitations_and_societal_impact: The authors have described the limitations of their theory, e.g. having a fixed $\hat{Q}$ with time.
review_title: null

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

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

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