Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: After author response:

I disagree with the discussion on MSE. For the empirical estimator you mention, we have:
$$E[(Y - \hat{P}(X))^2] = E[(Y - A(X))^2] + E[(A(X) - \hat{P}(X))^2]$$
Importantly, $E[(Y - A(X))^2]$ is a fixed value regardless of what $\hat{P}$ you use. So while you can’t compute $E[(A(X) - \hat{P}(X))^2]$, you can compare whether this is higher or lower for a particular $\hat{P}$ by just comparing $E[(Y - \hat{P}(X))^2]$.

By the way, this is directly analogous to classification. In classification, Y | X is stochastic, it is 1 with some probability A(X) and 0 with probability 1 - A(X). Indeed, we cannot measure $E[(A(X) - \hat{P}(X))^2]$ directly - instead we estimate $E[(Y - \hat{P}(X))^2]$, but that’s just off by some fixed value (which does not depend on $\hat{P}$).

At a higher level, there isn’t really a distinction between classification and the setting here. Let f(X) be your confidence interval, and introduce a random variable A given by A = 1 if Y \in f(X) and A = 0 if Y \not\in f(X) be a random variable, then we are precisely estimating P(A = 1 | X). This exactly corresponds to classification, where the label A is either 0 or 1, and we are estimating P(A = 1 | X).

As such, it’s important to compare with standard baselines (e.g. the 2 stage approach). Use the neural network features instead of training the coverage estimation model from scratch in the second stage, and show the MSE and calibration error values.

I still think it’s unclear there is much interaction between the “high quality” confidence interval and coverage estimation. As the author response says, setting $\lambda_2 = 0$ and turning off the Ca-module, would not affect the confidence intervals produced.

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

Summary:

This paper tackles two problems:
1. Providing high quality prediction intervals for regression problems. In particular, they want prediction intervals that have a desired marginal coverage (e.g. true output is in prediction interval 95% of the time), and average interval width is small.
2. Estimating the coverage of a prediction interval (conditional coverage estimation).

For (2) they propose measuring the calibration of the coverage estimator. They propose training (1) and (2) jointly using a sum of 3 losses. On the theoretical side, (a) they show that the log loss upper bounds the calibration error motivating its use as a surrogate loss, and (b) they show that given enough data objectives (1) and (2) can be trained jointly with low generalization error on the calibration error. They show experimentally that their approach mostly gets smaller interval widths for the same coverage level, than prior work.

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

Reasons for score:

The paper has a lot of interesting ideas, but they seem rather disconnected to me. A key missing ingredient is that the paper does not explain why jointly estimating the coverage improves the quality of prediction intervals. Their theory only motivates that they can estimate the conditional coverage. On the experimental side, they don’t have ablations without the coverage estimation (that is, with only losses L_IW and L_CP in their notation) to check whether the coverage estimation loss L_CA helps. I’m unconvinced about the experimental protocol (more details below), the setup and architectures seem different from Pearce, and it’s unclear if results are from a single split which hyperparameters are tuned on. On the plus side, the method seems to have narrower intervals so could be useful for practitioners if some of these concerns are ironed out.

I believe this work could have solid contributions if these issues are cleared up and the paper is made cohesive, and my assessment is based on the current state of the paper as opposed to the research direction. Keep up the good work!

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

Pros:

- The idea of outputting not only an interval but also a coverage estimate sounds interesting and potentially useful, e.g. it can allow us to identify cases where the intervals do not have the desired coverage. Measuring calibration of the coverage estimator makes sense (it is weaker than a pointwise guarantee, but stronger than a marginal guarantee).

- The (L_IW and L_CP) loss used to train prediction intervals seems sensible. It looks related to Rosenfeld et al, but uses a sigmoid instead of a hinge to penalize predictions that fall out of the prediction interval. Intuitively this makes sense to me for neural nets, since anecdotally my experience is that sigmoid style losses work better. Although if using softmax instead of hinge is being positioned as a major point (I didn’t think it was) there should be a comparison with hinge loss.

- This paper seems to get better results than prior work, which is definitely a positive.

- I skimmed the proof of Theorem 1 and it looks correct, and Theorem 2 sounds likely true.

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

Cons:

- The main missing ingredient is the connection between predicting coverage and getting tighter intervals. Why does predicting the coverage (the L_CA loss) make the intervals tighter? Taking a step back, does it even make the intervals better? The theory does not address this, and there aren’t any experiments that this L_CA component specifically helps. My judgement (not in the paper) is that the L_CA loss is indeed lower if the prediction intervals have high coverage (if \hat{k}_i is close to 1 and \hat{P} is accurate). However, the L_CP term already encourages high coverage, so it’s unclear if L_CA is doing anything. If I only use L_IW and L_CP can I get the same results? Would need to do grid search to choose the right hyperparameters lambda_1 and lambda_3, which would be different after removing L_CA.

- Experimental protocol is unclear. Peirce et al do 20 random splits into 90% train - 10% test, and report means and standard deviations. This paper says the split is 80% train - 20% test. Is there just one split, otherwise what are the standard deviations? The numbers for Peirce et al are quoted directly from their paper as well, so under a different setting. It looks like multiple hyperparameters (lambda1, lambda2, lambda3) are being tuned on the same validation set that the final results are measured on?

- Experiments use different models from prior work and make multiple changes to the losses (sigmoind instead of hinge) and architectures. For example, Peirce et al use one hidden layer and 50 nodes (except for Protein and Song Layer where they seem to use 100). Where are the gains really coming from? Is it just from making the network deeper?

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

Questions and things to improve:

I’ll certainly reconsider my score if at least some of the above are addressed, especially 1. the experimental setup needs to be clarified (hyperparameter tuning, use 20 random splits, report std-devs, 80%-20% split), 2. Need to have ablations without coverage prediction (tune lambda1 and lambda3 in this case), to see if it actually helps. The paper oversells a little in claims of “theoretically justified” since it only justified why the coverage assessment is accurate, but not why coverage assessment helps get better intervals - this needs to be edited.

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

Additional comments on theory:

- Theorem 1: shows log loss is an upper bound for cal error. It shows that the log loss to a suitable power upper bounds the lp calibration error. This looks like a nice and useful result, and I at least haven’t seen this before. I skimmed the proof and it looks correct. The naive way to upper bound say the l2 calibration error is using the MSE, but it does look like the log loss is tighter in many interesting cases. I could see this being positioned as a more important contribution of the paper if there is some argument (or examples motivating) for why the bound is tighter than alternatives (like MSE for l2 calibration error)

- Theorem 2: VC dim argument to show that log loss is approximated correctly by finite samples. I haven’t studied the proof of this theorem. My main questions are 1. An alternative to joint training is you can train the lower bound and upper bound estimator first, and then train the coverage module later on held out data. That should also have an exponential rate, with C* being a function of V_0. The theorem doesn’t seem to explain the advantage of joint training vs the split procedure?, 2. If we just want an exponential tail bound, we could also use a parameter space eps-cover, e.g. assuming the neural network is say L-Lipschitz. What’s the advantage of the VC dimension argument?

review_title: Useful contributions but disconnected, main ideas not explored theoretically or experimentally

final_score: rating: 7: Good paper, accept
review_content: ##########################################################################

Summary:

 
In the paper, the author addresses a calibration-based conditional coverage error in order to avoid the difficulty of conditional coverage, which provides a middle ground between marginal (no conditional information) and conditional coverage (high computational cost). The author generates the idea building on prior work and designs a new loss function combining the high-quality criterion and a coverage assessment loss. The theoretical framework about the loss function is laid out clearly, and the performances on benchmark datasets provide accurate results which outperform the other baseline algorithms on high-quality prediction intervals generation.

Not directly estimating conditional coverage probability due to the challenge of approximating conditional distribution, the author develops a metric called calibration-based error to measure the estimation and its empirical counterpart is easy to compute. However, non-differentiable empirical counterpart of calibration-based error metric hinders the algorithm implementation when using gradient-based method, the author replaces it with Kullback-Leibler divergence and theoretically demonstrates this divergence is a tight upper bound of coverage error, which makes the optimization tractable.


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

Reasons for score: 

 
Overall, I vote for accepting. The theoretical study is carried out clearly and smoothly. The method proposed, which provides more opportunities for broad application, is creative and well-demonstrated. My major concern is about the clarity of the paper in terms of the order of the presentation, and the possibility of a decoupled method. Hopefully the authors can address my concern in the rebuttal period. 

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

Pros: 

 
1. This paper considers calibration of the coverage incidence, which is important information for real deployment of any prediction interval method. 
 
2. The proposed loss is clear, intuitive and easy to understand.

3. Nice concentration bound for the calibration part.


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

Cons: 

 
1. Lemma A.2 (a) is an important argument for constructing the subsequent error metric. I think the statement appears to be too strong in general therefore can not be achieved in practice.

2. The authors should make it crystal clear that they are not proposing a PI with conditional coverage guarantee; instead, just try to provide an estimate of the conditional coverage guarantee given the feature. Somehow I had the impression that the goal was the former, until late in the paper. 

3. The methodology in Section 3 is not naturally motivated from the many discussions and definitions about the coverage estimation error starting from Definition 2.1 to the end of Section 2. Their connection is really in the back-end which is not shown until Section 4. It may be better to reshuffle the order of the presentation, or adding some explanation in Section 3 when Loss_CA is introduced. The main gap is that one cannot see how Loss_CA should be defined as in (3.3) after reading all these discussion about CE in Section 2.

4. Is there any advantage to consider the PI problem and the calibration problem in the same network? What is wrong with first estimate the PI, and then estimate the coverage incident given the PI as a separate problem? In this de-coupled framework, Loss_IW and Loss_CO will be used in the PI problem and Loss_CA will be used in the calibration problem, and they do not need to share the same network. More to the point: when a shared total loss is the goal of minimization, it would seem that the PI would evolve to make the task of calibration easier (to have small calibration error); there may be some cost to pay for this joint training, either in terms of IW or coverage. However, it is not clear to me what price we have to pay in the joint problem in (3.4)

 5. Table 1: why 1.13 in the second row is bold face when the IW for QD_Ens has a smaller IW of 1.09?

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

Questions during rebuttal period: 

Please address my comments in cons above plus the followings.

For the total loss (3.4), since the non-coverage probability is incorporated into the loss, we have to manually or adjust these tune parameters until the marginal coverage probability is satisfied. This does not seem to be trivial. Will this reduce the computation efficiency? Will a constrained optimization instead be faster than this? What is the hyper-parameter $\lambda_3$ used for?

The proof on VC-dimension and coverage assessment approximating Kullback-Leibler divergence are well-organized and detailed. However, perhaps supplying the proof on excess risk would be helpful too.


####

Minor comments:

I think a useful insight that the author can consider is that the calibration problem can be viewed as a classification problem in which the response is the event that the PI covers the Y value (\ind{ Y \in PI}). Then it would be class that the total loss is a PI problem joint with a classification problem. 
review_title: Review of Conditional Coverage Estimation for High-quality Prediction Intervals 

final_score: rating: 4: Ok but not good enough - rejection
review_content: ## Summary
The paper proposes a new framework that computes "high-quality" prediction intervals (PIs) _and_ an estimate of their conditional coverage. The latter may be regarded as an analogue of [1] for PI estimation. A theoretical justification of the loss is given under some regulatory conditions.

The problem of conditional coverage estimation is certainly well-motivated. However, there are some potential issues / questions that I would like to see clarified / answered.

---
## Strengths
1. The idea of estimating conditional coverage is an interesting one. Many methods with strong finite-sample performance are only capable of offering coverage guarantees that hold marginally. A method that is able to estimate conditional coverage with high accuracy has a potential to be useful as a diagnostic tool.

## Weaknesses / Questions
1. It isn't clear to me at all how to set $\lambda_1$ to achieve a desired coverage level. It would appear that the $L_{CP}$ component of the loss merely tracks the proportion of covered / uncovered points, so that a larger value of $\lambda_1$ is associated with more coverage, and vice versa. What is unclear to me is whether the $\lambda_1 = \lambda_1(\alpha)$ that would achieve a fixed target marginal confidence level $1-\alpha$ is known or have to be estimated via some sort of a tuning procedure. If the latter, doesn't it make the method prone to overfitting? Also, doesn't it rather invalidate the experimental results, as the comparison methods use a pre-specified target level of $1-\alpha$?
2. Is it necessary to estimate the PI and the conditional coverage simultaneously? The form of the total loss in Eq. (3.4) implies a potential tradeoff between obtaining a good PI and a good estimate of conditional coverage, but I do not see why the two objectives need to compete. On a related note, in the PI estimation problem, isn't it more interesting to estimate conditional coverage _conditional_ on a particular output of $L$ and $U$, and therefore, estimate $\hat P$ _after_ obtaining $L$ and $U$? After all, the target $A$ is already defined conditional on $L$ and $U$.

---
## Recommendation
The problem of estimating conditional coverage is an interesting one. The proposed method is not a convincing solution to the proposed problem.

---
## Additional Feedback
1. The version of the split conformal learning (SCL) implemented in experiments is somewhat outdated. [2,3] are rather more current, and produces PIs with adaptive widths, which can lead to narrower intervals in certain situations.
2. On a related note, in comparing methods that produce PIs with adaptive widths, I am not sure if the average width is interesting as a performance metric. For instance, if I somehow had access to the conditional coverage $A$ and the conditional distribution $Y | X$, I would want to compare to the width of the shortest interval with the conditional coverage. Of course, this information is unknown, but this at least suggests that the average width may be too crude.
3. Is there a typo in Eq. (3.3)? Also, the abuse of notation later in Theorem 4.5 is slightly confusing.
4. There is a typo in the line immediately above Assumption 4.2 on p. 5: $L_{CA}$ approximate -> approximate**s**
5. How difficult is it to tune the hyper-parameters? How sensitive is the method to the hyper-parameter choice?

---
## References
1. Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. ICML 2017.
2. Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. NeurIPS 2019.
3. Daniel Kivaranovic, Kory D Johnson, and Hannes Leeb. Adaptive, distribution-free prediction intervals for deep networks. AISTATS 2020.

---
## Update
I have read the revision and the rebuttal. I have also re-read the initial submission for comparison.

In the revised version, the authors have added "(4) Tune $\lambda_1$ such that $CP_{\mathcal{D}'} > 1-\alpha$  where $\lambda_2$ and $\lambda_3$ are fixed from (3)." after (3) in Algorithm 4, which substantiates their claim about the marginal coverage guarantee. As my other questions under #1 were all in response to the apparent absence of a valid calibration procedure, with the introduction of this line in the revised version, I have no further complaints about the correctness of the procedure itself. I still strongly recommend including Algorithm 1 in the main part of the paper, as a prediction interval is rather meaningless unless the associated coverage level is also known.

The biggest reason why I am keeping my score as is that after going through all the reviewing material, some of the recurring questions appear to be pointing at a larger issue with the submission.

1. It is repeatedly emphasized that the proposed method "outperforms the state-of-the-art algorithms on high-quality PI generation." This is great, except that it is hard to see *what* about the method is causing this improvement in performance. Is it the $L_{CA}$ component? Is it some non-obvious differences in architecture or in hyper-parameter tuning? Why should there be such a difference in practical performance for the simultaneous training vs a "decoupled" approach, leaving aside the practical concerns such as the computational cost?

Now that I have been thinking about this paper for awhile, I suspect that a great deal of the questions that the other reviewers and I have been asking are really about this need for *some* explanation for the improved performance. In my opinion, the current version does not provide enough evidence to *convince* the readers that the excellent empirical performance reported in Section 5 is an inevitable consequence of their novel method. This makes me cautious.

2. Throughout the review process, I couldn't escape the sense that the authors themselves have not settled on the central message. On this point, I am with R3. There is a lack of clear messaging on whether the focus is on (a) high-quality PI generation or on (b) estimating conditional coverage or on (c) both. About 3/4 of the way into the paper in my initial reading, I received the impression that the paper was definitely about (b). However, I revised my opinion and switched to (a) after going through the experimental section. After reading the first batch of the comments posted by the authors, I thought that the paper must have been about (b) all along. The last comment posted by the authors threw me into doubt yet again, however, as it seemed to indicate (c) as the correct conclusion.

In my opinion, both these issues need to be addressed before this otherwise interesting paper can be ready for publication.
review_title: An interesting problem, but the solution does not convince

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary: 

In the submitted paper, the authors study high-quality prediction intervals (PIs). The paper proposes a novel design of loss functions to generate PIs and conditional coverage estimates. The theoretical justification for using the conditional coverage error (in Ca-module) is presented and the numerical experiments with promising results are provided on multiple benchmark datasets.

Pros:

- The high-quality and reliable PI becomes more critical than ever as machine learning models have been used in the real-world decision-making process. This paper considers this important topic and provides a simple yet principled solution.
- The paper is well organized and theoretical results are well explained.
- Numerical experiment results on multiple synthetic and real datasets justify the practical advantages of the proposed algorithm.

Suggestion:

- Although the Bayesian framework focuses on the parameter uncertainty, as the authors mentioned in Section 6, it can be applied to generate the PIs. (Note that the posterior predictive distribution can be directly derived from the posterior distribution). A comparison study with Bayesian methods will help readers understand the advantages (or disadvantages) of the proposed method.


I vote for acceptance. 

review_title: A novel approach for high-quality prediction intervals

Meta-review: The paper studies the problem of estimating high quality prediction intervals for deep regression models. The paper argues that one (relatively under-studied) avenue to improve these intervals is to accurately estimate conditional coverage -- traditional PIs only reason about marginal coverage. The paper argues that in the presence of heteroskedastic errors or model mis-specification, conditional coverage can be dramatically different than marginal coverage. Concrete examples for each of these cases would be useful to establish the claim -- a synthetic experiment later in the paper illustrates the gap using heteroskedastic errors. The paper introduces a "Confidence Assessment" module that estimates the probability that the model's confidence interval is correct. In spirit, this is akin to learning a calibrated probabilistic classifier. Theoretical analysis shows that the CA-module can provably assess the reliability of the confidence intervals while jointly training the confidence interval method -- some reviewers appreciated the rigor in this analysis.

However, the reviewers also pointed out that the main message of the paper is muddled, and the confusion spills over into the experimental execution of the paper. Many of the complaints about baselines and experiment setup can be traced back to this confusion.
There are several claims in the paper:
- Conditional coverage estimation is useful. The synthetic experiments demonstrate this sufficiently.
- The CA-module achieves conditional coverage estimation reliably and efficiently. There are missing baselines (e.g., other approaches implementing a probabilistic classifier) in the experiments to establish this claim. The authors added an experiment to address this, but reviewers are concerned that the baseline classifier is unnecessarily handicapped (e.g., training a new coverage model from scratch instead of using existing learned features). Reviewers also note that there are missing metrics -- the existing metrics can plausibly be gamed by simply outputting the marginal coverage estimate.
- Incorporating CA-module leads to better prediction intervals. Some experiments suggest that this is not the case, and that there is negligible improvement (the lambda_2 = 0 setting that the authors describe). On the other hand, it is heartening to note that adding the CA-module did not adversely affect the quality of the prediction intervals either.

Since a two-stage procedure (estimate intervals, followed by estimating CA-module) is empirically inferior to joint training, reviewers rightly ask for some insight into why estimating conditional coverage jointly would reliably lead to prediction intervals that are more precise on average. The theoretical analysis in the paper applies to the 2-stage procedure too (proving that the 2nd stage CA-module indeed estimates the reliability of the confidence intervals); so there is some missing insight on why joint training could be beneficial.

A clearer message, making weaker claims and experiments that clearly back those claims will make the paper stronger.
For example, (softening claims about CA-module:) The paper introduces one ad-hoc procedure (CA-module) and shows that it is fit for purpose. No claim that it is efficient relative to baselines, but it still needs to justify why CA-module should be preferred compared to any other probabilistic classification approach. (softening claims about better intervals:) joint training works better than stage-wise training (which, by definition, leaves the prediction intervals unaffected). Unclear as to why that should happen in general; two special cases are mis-specification and heteroskedasticity. 

Decision: Reject