Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Conformal prediction (CP) allows for the selection of a set of candidate answers guaranteed to contain the correct answer with some probability. The authors propose two extensions to CP, 1. To extend validity for all admissible answers, 2. Using prediction cascades to improve computational efficiency. The authors show that their approaches provide similar guarantees on accuracy like CP but with lowered predictive efficiency and computational cost.


Reasons to accept: 
1.  The approaches are simple, novel, and interesting and they come with theoretical guarantees 
2. The proposed methods allow for CP to be extended to some realistic tasks
3. Impressive results showing lowered predictive efficiency and computational cost
4. The paper was well written and the approaches and experiments seem technically sound

Overall, I believe that this would be a useful paper for the community, and based on the reasons given above I would recommend acceptance. 
review_title: Interesting and exciting direction, proposed method comes with theoretical guarantees and boasts empirical efficacy on large scale applications

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

This paper presents two advances in conformal prediction, a field with information retrieval applications in which a set of candidate responses to a query is presented and the objective is to return a small set of responses with at least one of the responses being the correct response.  The first contribution is a method in which the possibility of several admissible responses is modeled (rather than there being just one response) with the system being calibrated against the odds that a particular response is the "most admissible", i.e. most conforming to the joint query/response distribution being learned from data. The second contribution is a cascaded prediction system in which simpler and less computationally expensive models are used for initial filtering and then more sophisticated and more expensive models are used downstream to further refine the response set. Rigorous statistical adjustments are used to account for multiple-hypothesis-test issues arising from using the cascading system.

Pros:

Reasonably thorough experimental results demonstrating performance gains in terms of sensitivity/specificity as well as in terms of computational cost are presented.

The paper is mostly well written and the theory is presented with a good amount of rigor. 

Cons:

I feel that the cascading technique is only of moderate significance. It's a good idea and there's some value in promoting it, but it also feels like a solution that might get arrived at by a savvy, practical-minded machine learning engineer in industry rather than a particularly profound ML research concept. The rigorous multiple hypothesis corrections (Bonferroni , etc) are certainly appreciated and are something which a less sophisticated practitioner might not know to apply, so that aspect of it feels more like an academic-paper-level contribution, but the basic idea of cascading feels like an applied, industry systems solution that someone with common sense might arrive at on her/his own.

Further suggestions:

I strongly suggest changing the definition of "predictive efficiency" on page 6.  Defining it such that lower "efficiency" is better will confuse many readers. Efficiency has a well-established common-language meaning as something which is desirable. Why not define the efficiency as (for instance) the percentage of the entire candidate Y set which is eliminated, so that higher efficiency is better?

I also think that it would broaden the appeal and accessibility of the paper to spend more time relating conformal prediction to more widely known information retrieval concepts like precision and recall and maybe also learning-to-rank. I suspect far more readers will be familiar with basic information retrieval, precision, recall, etc than with conformal prediction. I acknowledge that one of the appendices connects conformal prediction back to some of these concepts. I think maybe some of that appendix content belongs in the main paper. 
review_title: Solid experimental results, moderate significance/novelty, some presentation improvements suggested

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper propose a conformal prediction (CP) approach in which the prediction output is not necessarily unique; and will be assumed to belong to a finite set. Then, the authors analyze how the classical CP set can be modified wrt to a relaxed requirement that it is sufficient to contains an admissible answer. This lead to a smaller set in expectation and a coverage guarantee is established, proving the validity of the method. Authors also provide a computational methodology to screen out non promising candidate. The paper is well written and provide practical numerical experiments that demonstrate usefulness of the introduced CP in "real" world.

- Assumption 4.1 should be probabilistic since $A_g(X, Y)$ is a random set. Is the inclusion required *almost surely*? Note also that ${\bar Y^j}$ is not defined here. It is also unclear how the sequence of admissible answers $(\bar Y_{i}^{j})_{j \in [k], i \in [n]}$ is included in the datasets (both training and testing). This leads to the following confusion

- In Eq. 1, P is the distribution of $(X, Y)$. However in Eq. (5), it seems that P is the distribution of $(X, {\bar Y^j}_{j \in [k]})$ (whose sample is assumed exchangeable).

- Computational complexity of CP:
The comment in the beginning of section 5 seems inexact: the cost of computing CP is not linear in $|\mathcal{Y}|$ otherwise it would be impossible to compute in regression case where $\mathcal{Y}$ is the real line $\mathbb{R}$.

- How this cascade strategy could be used in regression setting? For instance, despite the limitation of statistical estimator that can be used, full conformal prediction set can be computed by using parametric programming (without loss in the coverage guarantee): 
(J. Lei 2019): Fast exact conformalization of Lasso using piecewise linear homotopy.
(Ndiaye and Takeuchi, 2019): Computing Full Conformal Prediction Set with Approximate Homotopy. For instance in the latter, one could consider cascade parameterized by the optimization error. How this cascade approach can improve the computational efficiency of full CP in regression?

- In section 2, CP paragraph, these two papers might be relevant:
(Chernozhukov etal 2019): Distributional conformal prediction. And (Kivaranovic etal 2019): Adaptive, distribution-free prediction intervals for deep neural networks

- In section 3, the notion of conformity measure is not well defined (S must be symmetric wrt permutation of the data).

- epsilon in (0, 1) in the introduction.

- Given g, *x and y*, any prediction that is a member ...

- Is Eq. 5 equivalent to $P(\exists j \in [k]: \bar Y_{n+1}^{j} \in C(X_{n+1})) \geq 1 - \epsilon$? (which seems more explicit)
review_title: The paper offers an interesting extension of conformal prediction set framework and provide valuable computational methodologies. Some imprecisions need to be clarified but the overall contributions is well presented and interesting for the ICLR conference. 

Meta-review: This paper presents an approach for conformal prediction where, in its standard paradigm, a set of prediction candidates is identified as opposed to a single one.  The authors advance the CP framework by presenting a rigorous methods that allows for a smaller set of admissable predictions with a covergae quarantee. Their further contribution is a methodolgy based on cascading that filters out non promising candidates.

After the discussion period, _all_ the reviewers are in favour of accepting the manuscript with the average being marginally above acceptance.  My recommendation is therefore to accept the paper. 

Strong points:
The advance of a smaller set of admissible predictions in the CP framewrok is quite useful especially in scenaria where the set can grow (expensively) large. 
Thorough experimental analysis with good presentation of performance gain and usefulness in real world data. 

Weak points:
Lack of novelty in the techniques make the work a weaker candidate compared to the rest of submissions. 
Decision: Accept (Poster)