Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This article proposes a novel approach to constructing prediction intervals with approximately correct frequentist coverage, even on misspecified models.  The basic idea is to employ the conformal prediction technique using the Bayesian posterior predictive density as the conformity (goodness-of-fit) measure.  The main innovation of the article is to use an importance sampling approximation to the posterior predictive density at candidate values of outcome $y$.  This leads to a computationally fast and generally applicable algorithm for using samples from the standard Bayesian posterior to construct well-calibrated prediction intervals, even under misspecification of the Bayesian model.  An extension to hierachical models is also provided, and empirical results are presented demonstrating the performance of the method.
main_review: This is an elegant idea.  The innovation of using importance sampling is pretty simple, but it works out really nicely and I find it quite compelling.  The paper is clear and well-written.  I especially appreciate the clear and concise explanation of the full conformal prediction technique in Section 2.1.  In terms of significance, I could see this becoming a standard part of predictive analysis when using Bayesian models -- it is both powerful and seems easy to implement.

COMMENTS
1. How should one choose $T$ (the number of importance samples)?  How should one choose $\mathcal{Y}_\mathrm{grid}$ (the grid of $y$ points)?  The choices of $T$ and $\mathcal{Y}_\mathrm{grid}$ used in the examples are made without much explanation.  More guidance would be helpful here.
2. On lines 333-337, the paper mentions that conformal Bayes is limited by Monte Carlo error and the quality of the posterior predictive as a proposal distribution.  Does the severity of misspecification affect coverage?  Are there other factors that affect the coverage performance?
3. What role does the choice of model have on the quality of the prediction intervals obtained using conformal Bayes?
4. Does conformal Bayes provide a mechanism for diagnosing misspecification?



limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper introduces Bayesian and importance sampling techniques into a previously known conformal prediction framework.

I had troubles identifying what exactly is the novel contribution of this paper. It could use a brief section stating "our own contributions are A, B , C". In my understanding the conformal prediction framework was known before and the novel items are using the Bayesian posterior predictive density as a conformity score and additionally estimating the predictive distribution given new data from a weighted importance sampling where the weights are just the likelihoods of the prameter draws based on the new data point.

There are modelling extensions from completely exchangeable models to partial exchangeability, i.e., where we have groups and complete exchangeability is still valid in the groups, but not outside the groups. From this flat hierarchical structure there is a further extension to hierarchical models that may model deeper hierarchies and via hyperpriors may share information between groups.


main_review: I think the paper describes fairly straightforward ideas and there is not much surprising or interesting work here. I might be misunderstanding or missing some points, but the main questions that arise are not even attempted to be answered.

For instance the discretization into a discrete finite grid: What is its size, or more specifically, what is the trade-off between its size and the accuracy of approximation. The same question arises for me when I think of the parameter T for approximating an integral by an empirical average. how large should I choose T such that the error is within an eps error or within a multiplicative (1+-eps) error? Shouldn't the sample size be highly dependent on the dimension d of the parameters? I mean like a large polynomial in d or even 2^d.

The answer given by the paper is that those values are constants so it's easy for me to say that the paper introduces arbitrarily complicated models and their algorithm is only a heuristic without any guarantees. I think the modeling efforts are nice but too straightforward for a top conference like this. The only theoretical claim/proof is also more like an observation.

In the experimental part the distributions are concretized with quite simple distributions. Would it be possible to quantify the computational efforts here in those special cases?
limitations_and_societal_impact: no
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a scalable method for conformal Bayesian prediction, by estimating the modified posterior predictive density using "add-one-in" importance sampling.  On several tabular datasets with sparse and hierarchical models, estimation is shown to be efficient for non-extreme miscoverage levels, and the produced credible intervals have good coverage.

**Post-rebuttal update:** Thank you for the response.  I am keeping my score unchanged: on the plus side, the method is sensible and easy to implement; on the other hand, there are some (understandable) limitations when scaling to large datasets or applied on approximate posterior samples; and some reviewers raised questions about novelty, which I'm not most suited to judge, as I'm not an expert in this field.  In aggregate, the rating of "marginally above the acceptance threshold" still describes my opinions well.
main_review: 
The proposed method assumes that a large number of samples from the (original) posterior can be produced efficiently, after which prediction on a single test input can be carried out in O(N_{samples} * N_{train} * N_{grid}) time.  While there is no guarantee on the number of posterior samples needed, diagnostics is possible by looking at the effective sample size.  As the method is easy to implement and diagnostics is always possible, it can be a sensible choice as a "first attempt" at moderately-sized problems, especially when Bayesian modeling is also being considered.

Still, the time complexity above can still be expensive for large-scale datasets.  Also the efficiency of the importance sampling procedure is not fully clear, even though the authors provided some informal discussion: as reported in the first experiment, importance sampling is more difficult when the desired miscoverage level is more extreme, or when the prior is misspecified; the latter setting can be relevant in practical applications.  It is also unclear how the sample size requirement changes as the model becomes more complex.

The experiments demonstrate consistent improvement over standard Bayesian modeling, but it is not fully clear if the method outperforms other scalable conformal prediction methods based on alternative scores: for example, in the first two experiments, the split conformal method has comparable or only slightly worse (CI 5% wider) performance than the proposed method, while being significantly cheaper computationally.  It will strengthen the paper if the authors provide more comparison between these two methods, by e.g., evaluating the split method on a grouped dataset.

The paper is well written, I didn't find any unsubstantiated claims, and it seems that relevant prior work has been discussed; although I'm not an expert in this field, so I'm not fully confident.

Minor: L123: thinner -> thicker


limitations_and_societal_impact: The methodological limitations (requiring the original posterior to be a good IS proposal) is discussed in the paper.

As mentioned above, the work will be strengthened if there are more empirical comparisons of scalable conformal prediction methods using alternative scores.

Potential societal impacts are adequately discussed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors present an approach to using a Bayesian model to provide predictive intervals with  frequentist coverage within the framework of conformal prediction.  This work generalizes existing Bayesian methods for conformal inference that apply only to conjugate models.  The authors provide a straightforward generalization of their approach to partially exchangeable data.  Empirical validation on several datasets, and comparison to a baseline approach is provided.
main_review: The approach to extending conformal intervals beyond conjugate models is a sensible, simple and novel contribution.  The overall exposition and description of the method are very clear.   The work appears potentially significant and may be impactful within the Bayesian community by virtue of its simplicity and clear exposition.

However the benefits of the conformal Bayes in comparison to the broader space of non-Bayesian methods for conformal inference and methods for constructing prediction intervals beyond conformal prediction are not clear; it is not clear what (if anything) the authors provide which is not provided by Barber et al. (2021), for example.  A more detailed comparison to existing conformal prediction methods (both in pros and in experimental validation) is needed.

Additionally, the use of the “add one in” (AOI) posterior predictive density as the conformity score was surprising to me.  Can the authors clarify when this will and will not work usefully as a conformity score?

Assuming I understand the set-up correctly, the score will break down, for example, when predicting with a noiseless Gaussian process regression:
theta ~ GP(0, k)
X_i   \overset{i.i.d.}{\sim} N(0,1)
Y_i = theta(X_i)
In this case, the density in the first display equation of section 2.2 does not exist (i.e. you cannot define it w.r.t Lebesgue) because for any i satisfying 1<i <= n+1, theta(X_i) | X_i,  Z_{1:n+1} is no longer random once we condition on Z_{1:n+1}.

In any case, the authors would strengthen the paper by clarifying what is meant by the first display equation of section 2.2; if since (X_i, Y_i) is an element of Z_{1:N+1} (following lines 75-76 of the paper), how should p(Y_i | X_i, Z_{1:N+1}) be interpreted?



Relatedly, the preference for AOI predictive densities rather than leave one out densities was surprising to me.  And the discussion of this choice on lines 123-131 appeared to me as a bit of a red herring; the three bulleted claims are neither obvious nor supported with evidence or references.  Could the authors comment on whether these observations are part of their contribution, or if these differences to LOO are already known?  In any case, I would have appreciated an empirical comparison to LOO predictive densities used to define the conformity score (again using IS).

It would greatly strengthen the paper to include (as a theorem) explicit conditions under which the CB intervals have the correct coverage.  Such a statement would help the practitioner/reader understand when the method should be applied.

limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary:  The authors develop a fast conformal Bayesian computation approach.  The original conformal prediction method can be computationally intensive:  It often requires refitting the model for every augmented value y. The authors avoid this refitting step by using importance sampling. The authors also show the extension to conditionally exchangeable data, which is especially useful for hierarchical data. The resulted conformal interval has finite sample correct coverage and is immune to model misspecification or distribution assumptions.
main_review: The paper is well structured and easy to follow. I also agree with the authors that prediction calibration is crucial in the M-open world, which is arguable always the case. The prospered conformal Bayesian computation method sheds some light on this direction. 

However, I am concerned about whether the novelty of the proposed method can be distinguishable from its existing building blocks. Conformal inference/distribution-free Predictive Inference—and thereby the main algorithm considered in this paper—are not new ideas. It is also not a new idea to use (regularized) importance sampling to avoid model refitting and obtain posterior integrals in the context of either the leave-data-out (LOO) or the add-one-data-in (AOI, e.g. Bürkner et al. 2020 used this importance-sampling-AOI idea in time series).  It appears the only methodology contribution this paper is making is to apply the importance sampling strategy to the model refitting step in conformal Bayesian inference. I am not convinced that such incremental contribution would grant a publication. 

In terms of its practical usefulness, I have two concerns. First, throughout the paper, the authors seem to emphasize the situation in which x_{n+1} is fixed. But this is not a typical perdition task in which we have a known x_{n+1}. In the words of Lei  (2018): “In some applications, where Xn+1 is not necessarily observed, prediction intervals are build by evaluating 1{y ∈ Cconf (x)} over all pairs of (x,y) on a fine grid“. Perhaps x_{n+1} can also be evaluated on a grid, but then that method is rather related to jackknife-conformal-inference, which itself can be computed by importance sampling.  

Second, the “correct frequentist coverage” is a probabilistic statement averaged over all observed data and x_{n+1}. This does not mean the interval estimate derived from conformal Bayes is exact for y_{n+1} conditional on a fixed x_{n+1}, nor necessarily optimal for interval predictions (optimal in the sense of interval scoring rules). Think about the Jackknife case in which the bandwidth is a constant across x_i. I suggest the author clearly state the definition of frequentist coverage as not all audience in the machine learning community can immediately tell the subtle difference.

Minor:
* L-82: why is the rank normalized by n+1? I think the rank statistic should the integer. 

* How is the grid of y chosen? Could you use Bayes prediction to design the grid?

* What is the advantage of AOI against jackknife used in conformal Bayes? Is the only difference that IS-AOI is computationally easier than IS-LOO?

* “The CB and Bayes methods have comparable run-times” I think it is misleading. CB can have an arbitrarily larger running time if x_{n+1} is evaluated at many values.

* Overall, the experiment section is relatively weak. The sample sizes in all three examples are too small to reflect a modern big data challenge. It is not common to see all MCMC running time < 1 second from ML conferences.

* L-336: I think “leverage” is the wrong concept here. The leverage only depends on x. Here you have the influence of y too.

* "If only approximate posterior samples are available, e.g. through variational Bayes (VB), then an AOI scheme may still be feasible, where one includes an additional correction term in the IS weights for the VB approximation". I disagree. Note that Magnusson et al. (2019) are on the LOO of exact Bayes when there are only VB samples. In your context, you need not only adjust for the VB approximation for sigma_{n+1}, but also all sigma_{1}, ... sigma_{n} for lack of exact posteriors. Such a task is generally not feasible.

limitations_and_societal_impact: The  authors have adequately addressed potential negative societal impact of their work.
I have listed more limitations in my main review.
review_title: null

Meta-review: This article presents a novel method for constructing prediction intervals with correct frequentist coverage, based on combining frequentist ideas from conformal prediction with a Bayesian model.  The main idea is to use the Bayesian posterior predictive density as the conformity measure in the standard conformal prediction framework, and employ importance sampling to avoid having to re-fit the model for every data point.  The method uses "add-one-in" importance sampling rather than leave-one-out, which is advantageous in that it lowers the variance of the importance weights, leading to more stable results.  The computational cost is also significantly reduced by approximating the outcome space with a discrete grid of points, following Chen *et al* (2018).

The idea is relatively simple but very generally applicable, and has the potential to be high impact in the Bayesian community.  The simplicity with which it can be implemented is attractive, and the computational cost is modest: it takes less than 2x the time as the standard Bayesian technique (Tables 1-3). Further, the performance guarantees are quite general, and the experiments demonstrate a striking improvement in coverage performance compared to standard Bayes (Tables 1-3). The paper is well-written and sound.

In my view, the main limitations are:

1) Novelty. The method combines standard techniques for conformal prediction, importance sampling, and Bayesian inference.  Thus, the constituent parts are not novel, and they are integrated in a fairly straightforward way.  The novelty lies in bringing these pieces together and recognizing its utility.

2) Need to appropriately choose the grid of $y$ points, $\mathcal{Y}_\mathrm{grid}$.  The paper provides a reasonable default recommendation for this, which is to use 100 evenly spaced points between $y_\mathrm{min}-2$ and $y_\mathrm{max}+2$.  However, it seems that this choice may require application-specific tuning.

3) Model misspecification may increase the variance of the importance sampling approximation, resulting in more unstable inferences.

There was a fairly wide range in the reviewers scores.  There were two ratings of 4 from reviewers tEpY (with a low confidence of 2) and dTHk (with a medium confidence of 4).  I have carefully examined the paper, the reviews, and the authors' reply, and I believe the main criticisms can be addressed as follows:

- Regarding novelty, reviewers tEpY and dTHk criticize the article for providing incremental improvement upon existing approaches.  While it is true that the method can be viewed as combining existing methods, I would argue that the utility of the proposed method —  in comparison with existing alternatives — justifies its simplicity.  Reviewer dTHk also states that Bürkner *et al* (2020) already introduced the idea of using add-one-in importance sampling for approximating posterior integrals; however, I have examined the Bürkner *et al* (2020) paper and while they use importance sampling, I do not see any use of a technique resembling the method in the present paper.

- Regarding the choice of $\mathcal{Y}_\mathrm{grid}$:  Reviewer tEpY criticizes the article for outsourcing the problem of choosing the grid, and the associated tradeoff between computational cost and accuracy, to Chen *et al* (2018).  Since the use of a discrete grid for conformal prediction is not the main novel contribution of the paper, this outsourcing seems reasonable in my opinion.

- Reviewer dTHk is concerned that the assumption of a known $x_{n+1}$ may not be practical, and discusses making predictions for a grid of $x_{n+1}$ points.  However, as the authors state in their reply, the coverage guarantees are for random $X_{n+1}$, not a given fixed $x_{n+1}$. Thus, in fact, the method effectively considers all possible $x_{n+1}$ values.

- Additionally, reviewer dTHk felt that the article should emphasize more clearly that the coverage guarantees hold in expectation, when averaging over the entire dataset as well as the future datapoint $x_{n+1}$.  This is a good suggestion, which is easily addressed via a minor edit, which the authors have volunteered to do in their reply.


Bürkner, P. C., Gabry, J., & Vehtari, A. (2020). *Approximate leave-future-out cross-validation for Bayesian time series models.* Journal of Statistical Computation and Simulation, 90(14), 2499-2523.

Chen, W., Chun, K.-J., and Barber, R. F. (2018). *Discretized conformal prediction for efficient distribution-free inference.* Stat, 7(1):e173.


Decision: Accept (Poster)