Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes conformal methods for learning a predictive confidence set that is guaranteed to be nearly the most statistically efficient among predictive confidence sets produced by a parametric class of learning algorithms. To explain, many wrapper methods for assessing prediction uncertainty assume that the user has already committed to one particular learning algorithm and aim to quantify uncertainty in predictions produced by using *this* learning algorithm. By contrast, the methods proposed here assume that the learning algorithm has been specified only up to some parameter $\theta$ so that it makes sense to optimize $\theta$ with respect to the precision of the resulting predictive confidence sets.

From the point of view of practical implementation, the obvious challenge is the optimization of $\theta$ (as well as the associated prediction sets) over an arbitrary and large space of possible values of $\theta$, as the optimization involves a hard constraint. Thus, one main contribution of the paper is to propose a differentiable proxy that allows an efficient search over the parameter space. Regarding theoretical guarantees, the paper proves that the original, non-differentiable formulation of one of the methods achieves approximately valid coverage and nearly optimal statistical efficiency when the class of learning algorithms has a low capacity.
main_review: ## Strengths

The paper is a useful sequel to the earlier work of Yang & Kuchibhotla (2021). Now that more people are aware of conformal methods, it makes sense to develop methods that incorporate tuning of learning algorithms with the goal of obtaining the most precise predictive confidence sets.

## Weaknesses

1. *Clarity*: Definitions or details that are important for understanding the paper are frequently postponed without warning.

- The explicit meaning of *parameter* (as in "a single parameter" or "multiple learnable parameters") is left unspecified till p. 4, where the problem is formally described. At the same time, it seems eminently possible to communicate the content of earlier pages using more intuitive language. For example, consider the following sentence: "Conformal prediction is a powerful technique for learning prediction sets with valid coverage, yet by default its conformalization step only learns a single parameter, and does not optimize the efficiency over more expressive function classes." All this is saying is that the existing approaches treat the learning algorithm as completely fixed (so that conditional on the observed data, there is only one set prediction map for each confidence level), whereas the proposed methods aim to find the most precise set prediction map over a *collection* of learning algorithms, where the collection is allowed to be uncountably infinite.

- Similarly, the question of where the extra parameter $\theta$ is coming from or how it may arise is not addressed till p. 8. For example, Figure 1 has less impact because it cannot be clear to the reader at the time what $\theta$ represents in the context of CQR. As a result, the paper reads mainly like a purely theoretical exercise until concrete instances of $\theta$ are finally given in the last sections. (This is just a suggestion, but consider starting the paper with a concrete example from Section 5 that is well-defined.)

- The descriptions of the experimental setups ought to be more clear, too. For example, it is doubtful how much of Section 5.1 can be understood *without* Romano et al. (2019). The symbols $\hat F$, $\hat f_{\text{lo}}$, $\hat f_{\text{hi}}$, etc. do not appear to be defined anywhere, and the symbol $d_h$ is defined 7 lines after its first occurrence. I also do not understand what the authors mean by "1r decay."

- I am confused about the experiment in Section 5.2. In light of the stated motivation for the proposed method, I would have thought that the interesting comparisons are the ones in which first, a parametric family of learning algorithms is fixed, and then the method that does this for a fixed $\theta_0$ is compared to the proposed method that learns an optimal $\hat \theta$. It is not clear to me if the two baseline methods are comparable in this manner. (By the way, a slightly less naive method that adapts to the correlation structure would probably utilize the maximum statistic, e.g., $\|Y - \hat f(X)\|_\infty$, rather than a Bonferroni bound.)

2. *Balance / Completeness*: The paper actually proposes *two* meta-algorithms: CP-Gen and CP-Gen-Recal. The theory sections are almost exclusively concerned with CP-Gen (with the exception of Section 3.3), whereas the experimental results are only reported for CP-Gen-Recal. This has created an odd imbalance in the manuscript. I feel like either the experimental results for CP-Gen ought to be included in the paper as well as the content of Appendix G.3, or most of the material pertaining to CP-Gen ought to be moved to the appendix.

3. *Originality*: As of writing, I am still trying to decide whether the contributions of this paper are substantial enough in light of the contributions of earlier works. From the point of view of theoretical validity, many of the ideas here appear to be already present in, say, Yang & Kuchibhotla (2021), although it is true that they have not been worked out at this level of detail. On the other hand, from the point of view of practical implementation, optimizing over an arbitrary and large $\Theta$ is a nontrivial challenge, and the authors do well to borrow from a different line of uncertainty quantification literature. This may well be a matter of emphasis or branding. In any case, I would like to hear other opinions on this point.

## Typos
- (p. 5. The line above Section 3.2) $\epsilon = 0$ -> $\epsilon_0 = 0$.
- (p. 9. The line after the itemized list) Our datasets is -> Our datasets are
- (p. 9. **Additional experiment**) The citation for the ImageNet dataset is incorrectly given as (Angelopoulos et al., 2020).
- (Section B.2 from after Eq. (11)) $\hat L_{\text{coverage}}$  -> $\hat L_{\text{eff}}$ and $L_{\text{coverage}}$  -> $L_{\text{eff}}$ throughout
- (Section B.3) $R_n(\mathcal{C})$ is used, but $R^{\text{eff}}_{n{\text{cal}}}(\mathcal{C})$ was given on p. 6.
- (p. 16, Paragraph 4) a shortest prediction interval -> the shortest prediction interval
- (p. 17. The last unnumbered display equation) Remove , from the subscript.
- (p. 18. The line after the first unnumbered display equation) Add "by" between "and" and "the assumption."
- (p. 18) $F_{\hat \theta}$, $\hat F^{\text{cal}}_{\hat \theta}$, etc. all look too similar, making the proof unnecessarily difficult to read.
- (p. 21) On p. 3, $K$ was used to denote the number of classes. Here, $L$ is used to denote the number of classes, and $K$ now represents the number of base predictors in an ensemble.
- (p. 21) $p$ in the exponent can be confused with $p_\theta$.
- (p. 21) In **Methods for learning prediction sets**, $i$ denotes the epoch count. However, $i$ is already being used to denote a single base predictor in an ensemble.
summary_of_the_review: Overall, I think the paper is a useful extension of some earlier works on uncertainty quantification with an eye towards statistical efficiency. I tentatively recommend it for acceptance with some reservations.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers to improve efficiency of conformal prediction (measured in the "size" of prediction sets). To this end, this paper uses multiple-learnable parameters by generalizing single-parameter conformal prediction. By doing so, the paper demonstrate that the proposed approach can improve the efficiency of conformal predictors while satisfying valid coverage. The efficacy of the proposed approach is demonstrated over regression, multi-output regression, and classification.
main_review: **Strengths:**
1. The paper considers an important and interesting issue (i.e., maximizing efficiency of conformal prediction).
2. The proposed approach is evaluated over various setups and datasets (i.e., 9 regression datasets, 7 multi-out regression datasets, and 2 classification datasets).


**Concerns:**
1. I agree that reducing size in conformal prediction is important issue, but the way that this paper considers this issue is currently less motivational; one beauty of (inductive) conformal prediction is that it isolates the issue of choosing the score function and the issue of constructing a conformal predictor---i.e., the guarantee of the constructed conformal prediction holds for any score functions. This implies that we can isolate the task of learning the score function by empirical researchers and the task of conformal predictor construction by theory researchers. Moreover, as we have a better score function (e.g., by devising better network architectures), the size of a conformal predictor is naturally reduced---this can be easily verified if the score function is perfect (e.g., true classifier in classification). However, the proposed approach mixes up the two isolated procedures and making it complex for getting better conformal predictors. What's the problem of designing a better score function to get efficient conformal predictors?

2. Related to above issue, important motivational experiments are missing; for example, in the experiment of Table 1, CQR could be more efficient in terms of interval size by including D_{cal} into D_{train} (i.e., improving the score function by having more training samples); here hyperparameters can be chosen as the paper chooses for \theta. (1) what's the performance of CQR where the quantile regressor is trained over D_{cal} + D_{train} with pinball loss? (2) what's the performance of CQR where the quantile regressor is trained over D_{train} with pinball loss and then the last layer is fine-tuned over D_{cal} with the same pinball loss?

3. for all experiments, I think the variance statistics over random trials would be necessary to show the significance of the proposed approach. Also, the current number of random trials (i.e., 8) is small; I do believe that the paper could be stronger if the proposed approach is evaluated over larger trials (e.g., 100), which is possible if a score function is trained only once with a fixed training set as in inductive conformal prediction. As in the current form, I'm not sure if we can compare lengths among approaches without having the same or very similar coverage---as mentioned in the paper, coverage also affects on the efficiency, so the better efficiency could be due to some randomness of calibration splits.

4. Section 1.1 "Both works formulate this task as a risk minimization problem": I think the earlier work [R1] already consider conformal prediction in the ERM framework, where it also allows any function class and efficiency loss, along with one-parameter special case as their approach; it's better to acknowledge similar prior work and mention differences.

5. "3.2 Theory" is not well connected to the final algorithm; basically the proposed algorithm is (1) fine-tune the score function with a proper efficiency loss and (2) run a known conformal prediction for coverage guarantee. What's the novelty compared to known analyses on the generalization bound? 

6. In Table 5, it's better to add comparison results to make the results stronger; the standard conformal prediction can be applicable here.

*[R1]: https://arxiv.org/abs/2001.00106
summary_of_the_review: This paper considers interesting and important problem, and the proposed approach is broadly evaluated; but as mentioned in the main review, I lean to reject though I'm willing to adjust my understanding and score.



==== POST-REBUTTAL ==== 

Thanks for the additional discussion and experiments; I think the response mostly addressed my concerns so raise my score to 6. To my understanding, the key message of this paper is that finetune a base predictor with respect to a desired length metric (along with a coverage constraint) if we want to improve the efficiency (in the same length metric) of the final conformal predictor given fixed sample size; this is likely to be true and is more convincing given the additional experiments. As one minor note, [R1] is applicable to both classification and regression as demonstrated in their experiments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper generalizes the standard conformal prediction calibration setup to a constrained empirical risk minimization problem. Specifically, this work seeks to optimize some efficiency loss, while satisfying coverage constraints. This formulation allows for the introduction of multiple, learnable parameters which can help find a better set-based predictor. The paper explains the implications of this approach by analyzing the generalization error that may occur when transferring the solution learned by constrained ERM to a test population. It also explains practical ways of learning this problem via differentiable surrogate losses and Lagrangians. Contributions-wise, the paper contributes validating theoretical analysis that proves that this method can achieve approximate coverage and near optimal efficiency for certain set-function classes. It also empirically shows that the proposed method can improve over baselines that are not directly optimized for efficiency. 
main_review: There are a number of strengths that I quite like about this paper: 
- The paper is exceptionally well written and clear to read. 
- The core idea itself is appealing: strict adherence to proving marginal (or other) coverage for set-based classifiers, which generally relies on preserving exchangeability, is generally a good thing, but can be limiting/overly conservative. It is useful to formalize what practitioners stand to gain/lose by directly optimizing conformal predictors for efficiency.
- The framework itself is fairly simple (which is a nice thing), and empirically improves over a good CQR baseline. 

There are, however, some weaknesses, and I do have a few questions/concerns. 

- A minor point: though it is nice to formalize Propositions 2-4 (and they are nicely stated and proven), from a practical point of view $\epsilon_{\mathrm{coverage}}$ and $\epsilon_{\mathrm{eff}}$ are still quite loosely bounded and its unclear how much value they really add. As a practitioner, as a rule of thumb I already know that my train performance will roughly generalize well to my test performance if my model is low capacity and my data sample is large. The bounds given in Props. 3 & 4 might be too large to be practically useful, i.e., if I was setting $\alpha' = \alpha - \epsilon_{\mathrm{coverage}}$ based on this analysis. (I also appreciate the use of absolute constant C to clean up notation, but it does make the bound looser/not directly computable). 
That said, I understand that as positioned in this paper, these theoretical results are intended to formalize that stated "rule of thumb", i.e, that "we may expect $\texttt{CP-Gen}$ to generalize well [...] whenever it learns $K \ll n_{\mathrm{cal}}$ parameters," though it may be good to qualify this result more.

- I don't think this was mentioned: the proof of Proposition 2 (and others) relies on $D_\mathrm{cal}$ being i.i.d., which is slightly stricter than exchangeability (required for standard CP).

- It is interesting from Table 1 that the quantile loss increases after optimizing $\texttt{CP-Gen}$. An advantage of CQR is that it is adaptive to local variability. In this sense, it can achieve better approximate conditional coverage than a fixed interval. Do you lose any of this when you train $\texttt{CP-Gen}$?

- The length numbers in Table 1 seem quite a bit lower than those reported in the CQR paper (for example, Fig. 3 in CQR lists the best meps_19 result at 2.36, vs the 1.167 reported in your Table 1). Can you explain this difference? At the same time, it would be good to understand how much optimizing for $\texttt{CP-Gen}$ actually helps over choosing better base predictors with favorable properties (e.g., see [Conformal Prediction using Conditional Histograms](https://arxiv.org/abs/2105.08747) which improves over CQR on many of the same datasets reported here).



=== Minor Comments ===

- At the start of Sec. 3.2 you define $L_{\mathrm{eff}, \mathrm{coverage}}$  as the expected i.i.d. sample mean, which is equal to the true population average. However, I do find the notation slightly confusing (in terms of expectation over $D_{\mathrm{cal}}$) with what would be the train accuracy on $D_{\mathrm{cal}}$ after solving the optimization problem. In Section B.2 you write L in terms of $\mathbb{E}[l_\mathrm{eff} (C_{\theta, t}); (X, Y))]$ which I find preferable and would recommend that you could simply use here as well.

-  Typo: when bounding $\epsilon_{\mathrm{eff}}$ in the proof Prop. 3, it should be $L_{\mathrm{eff}}$ instead of $L_{\mathrm{coverage}}$.

- For clarity, it might be good to formally define $\epsilon_i$ as Rademacher r.v.'s when applying the symmetrization argument in the proof of Prop 3.  

- I would suggest reconsidering the use of "exact coverage" in Section 3.3, as this can be conflated for the case where the bound $\mathbb{P}(Y \in C(X)) \geq 1 - \alpha$ holds with equality.

- Typos, bottom of page 7: "$\hat{t}_{\mathrm{recal}}$ to _guarantee_ coverage" and "emphasize that the _approximation_ in (8)".

- Typo, Section 5.1: I believe you mean to include $+ t$ in the upper interval bound of $C_{\theta, t}$.
summary_of_the_review: In general, the paper is well-written and the idea is appealing. As mentioned in the main review, it would be good to understand more about the solutions that the proposed method finds and what (if anything) they might be sacrificing (e.g., conditional coverage). It would also be good to compare to somewhat more recent baselines (e.g., CHR for regression, RAPS for classification).
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper introduces an extension of conformal prediction with a different formulation. Instead of guaranteed coverage for a finite calibration set, the authors solve a constrained optimization problem where the length of prediction intervals is minimized subject to a coverage constraint. As a result, coverage is only asymptotically guaranteed, but instead the length of the prediction intervals can be shortened compared to traditional split conformal prediction. 

The authors present theoretical results in the form of coverage bounds for specific function classes. 

In the experiments classical regression datasets are analyzed, as well as multi-output regression problems and one multi-class classification problem. 
main_review: In my review I would like to address each of the evaluation criteria.

Technical novelty and significance: 

The presented idea is novel and interesting. It is well supported by theoretical arguments and experimental results. It is interesting to see that the bound on coverage becomes weaker when the complexity of the space over which is optimized increases. This is in fact a natural result.

The presented idea is in fact quite similar to this ICML paper: https://arxiv.org/pdf/1802.07167.pdf. Similarly as the Lagrange formulation in Eq. 8, in that paper an optimization problem that incorporates both efficiency and coverage is introduced, but the objective function is a bit different. It would be interesting to compare empirically with that method.

Empirical novelty and significance: 

The experiments show what they need to show, i.e. that the proposed method is better than conformalized quantile regression. However, the results reported for CQR are a bit worse than those reported in https://arxiv.org/pdf/2107.00363.pdf (look for the datasets that are reported in the two papers). It is not so clear why that is the case.

The experiments for multi-output regression and multi-class classification are a nice add-on to illustrate the broad applicability of the presented method, but they are not essential for the paper.

Correctness: 

The theoretical look correct, but at some stages the readability could be improved:

Proposition 2a looks a bit awkward because the inequality has on the left side an average over all randomly drawn calibration sets, whereas the right hand side is about a specific calibration set. I would suggest to add "for any calibration set D_cal" to the beginning of the proposition.
I don't understand why epsilon_zero is included in Algorithm 1. The authors mention in Section 3.1 "for analysis purposes", but which analysis is this? Perhaps this could be removed to improve readability.
The experimental results have some minor issues w.r.t. which baselines are considered and how these baselines are tuned (see above). However, I don't see a problem with the main message of the paper.
summary_of_the_review: Interesting paper. Some minor issues w.r.t. comparison with existing work.
review_title: null

Meta-review: This paper describes a few practically relevant extensions of the conformal prediction framework, that has recently become popular in the ML community for providing (marginally valid) prediction sets without making distributional assumptions. The conceptual contributions are not major, given existing work --- without recalibration, the main idea of optimizing over two parameters was explored by Yang and Kuchibhotla (and is well understood even before YK, albeit not fleshed out). The current paper generalizes YK, and with the additional recalibration dataset, it is again simply an instance of standard conformal prediction. The optimization via Lagrangians is a nice addition, but it is ultimately a heuristic that performs well in practice. Nevertheless, the paper is well written, and the experiments are well done, making this a good contribution for practitioners. I recommend acceptance, and congratulate the authors on a nice work. 

As a minor note, Remark 1 should not be attributed to [AB21], since it is a well known fact and deserves an earlier reference.
Decision: Accept (Poster)