Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: **Summary:**
* The paper puts forth a greedy algorithm that maximizes the true discovery rate w.r.t. a set of labels (akin to coverage), subject to a user-specified restriction (i.e., constraint) on the false discovery rate, for the goal of building small but nevertheless valid prediction sets.
* A few calculations/results are worked out showing that the method works as advertised (i.e., TDR maximized, FDR controlled).
* Some empirical results are presented, where the method's TDR and FDR (along with those of one baseline from some other work) on three real-world data sets are evaluated.
main_review: **Strong points:**
* The framing of the problem is natural, and I like it (i.e., Sec 4.1 onwards).
* I like the idea of using the deep sets methodology.
* The three real-world data sets seem reasonably interesting / well-motivated.
* The paper is a pleasure to read.

**Weak points:**
* Experimental evaluation:
    * To me, the results are a little hard to interpret.  Your stated motivation (page 1, first paragraph) is to reduce the size of conformal prediction sets.  I may have missed it, but what are the sizes of the sets you get in Sec 5?  In particular, I think you should also report the conformal set sizes required to attain, say, 90% marginal coverage; otherwise, it's hard to say what exactly you are improving on.  It does seem though, from Figs 2,3, that to get 90% coverage on the in-silico example, you effectively need to include half the label set.  That's ... not great?
    * Along these lines, you seem to be "cheating" a little bit -- your stated motivation, i.e., cases when when the label space $\mathcal Y$ is large, seems to require ... $\mathcal Y$ to be large.  Yet you effectively truncate $\mathcal Y$ to 100 in all the experiments.  What happens if you don't do that?  Statistically?  Computationally?  I think it's OK to show when the method fails.
    * Also, it doesn't seem totally fair to not use CQC for the "Inner Sets" baseline, b/c then that baseline produces constant width intervals.  Meanwhile, yours can depend on $x$.

* Methodology: it seems the accuracy of deep sets as a conditional density estimator hinges on: (i) can $P_{Z \mid X}$ be decomposed in an additive way? and (ii) has the curse of dimensionality kicked in?  Accordingly, can you say how many dimensions there are in each of your examples?  Sorry if I missed it.

**Questions:** see my "Weak points" and "Additional feedback" sections.

**Additional feedback:**
* You seem to have switched between $S$ and $\mathcal S$ to denote a set on page 6.
* On page 6 -- "beach search" $\rightarrow$ "beam search".
* It's hard to tell what exactly is going on in the top row of Fig 2.
* Part (c) of Figs 2,3 -- TDR appears to asymptote at 0.8.  Why?
* I may have missed it, but how big is $\mathcal Z$ in each of the experiments?
* How do you set any tuning parameters for the deep sets neural network?  Doesn't this require additional data?
* I have what I think is a dumb question regarding the motivation of the paper.  Both your method and standard conformal will return a set.  But at the end of the day the practitioner still needs to use a single point to make a prediction.  How exactly does your method help with that problem?  I mean I get that you are trying to produce smaller sets, but you are still returning a set (i.e., more than one) of plausible values.
summary_of_the_review: **Recommendation:** reject.  I like the paper.  But I think there are some issues w/ the experimental evaluation that need to be sorted out before it gets accepted.  Happy to change my mind if I missed something.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: A new conformal method for multi-class prediction problems is proposed in which the number of false discoveries is capped while the proportion of true discoveries is maximized. The approach is shown to achieve the desired control in finite samples. The claim is further supported by experimental results.
main_review: ## Strengths

The method is well-motivated from a practical standpoint. It is also well-grounded in theory without burdensome assumptions.

## Weaknesses

The main issue has to do with clarity. The writing is difficult to follow, almost always unnecessarily so.

1. *Inconsistent or ill-defined notations*: The following is not meant to be an exhaustive list.

- On p. 1, $(X_i, Z_i) \in \mathcal{X} \times 2^{\mathcal{Y}}$, but $\mathcal{Y}$ has not been defined.
- Both $Z_{n+1}$ and $\mathcal{Z}_{n+1}$ as used. As far as I can see, they represent the same quantity.
- Similarly, both $S_{i}$ and $\mathcal{S}_{i}$ are in use.
- $B$ in Algorithm 1 is a hyper-parameter that caps the number of different values of $y$ that is considered. $B$ on p. 6 is a bound on the cardinality of $|\mathcal{Y}|$. The two definitions are in conflict. There is also $m$ in Remark 4.4, which appears to have the same meaning as the first $B$.
- It is confusing to have the same index $i$ be used to index many different quantities. It is initially introduced as indexing observations, e.g., $(X_i, Z_i)$. It is next used to index candidate labels, e.g., $\phi(x, y_i)$. It is again used to index sets in a nested sequence of sets, e.g., $\mathcal{S}_{i}$.
- The situation is made worse when there is a need for double-indexing, e.g., $\mathcal{S}_{i, j}$. All this is easily avoidable by introducing a different index whenever the meaning changes.
- The same comment applies to the remark about $k$ in Top-$k$.
- $t^*$ and $T_*$ appear to have the same meaning.
- Is $\operatorname{SSFD}_k$ in Eq. (14) the same as $\operatorname{WCSS}$ in Figures 2 and 3?

2. I do not think the paper ever explicitly spells out the precise meta-algorithm (the FD-CP algorithm) for either $k$-FD validity or $(k, \delta)$-FDP validity that can represent the proposed method. Algorithm 1 is only a particular *instance* of the proposed method that relies on specific choices of learners (MPNN and DeepSets) for the problem of in-silico screening. On a related note, the discussion in Section 4 does not appear to sufficiently differentiate between the general construction (e.g., nonconformity scores for nested sequences of sets) versus a particular example (e.g., the scores of Eq. (9)).

3. In Section 5, four baseline methods are described, but the reason behind the choice is never explicitly given. In particular, one of the baseline methods is not expected to have validity, raising the obvious question of why the method was considered in the first place. The last two (max and avg) were probably included as alternative scoring methods to the scoring method using DeepSets, but this is an educated guess. Also, if this was indeed the intention, then I feel like more space should have been devoted to a discussion of what makes DeepSets an appropriate choice, especially in light of Remark 4.5.

4. Both figures are hard to read. The plotting areas are too small, the lines overlap too much, and the colors are too similar. This appears to be due in part to imposing the same scale on the $y$-axes. Also, the top and the bottom panels are misaligned.

5. Overall, I feel like the current version of the manuscript does the bare minimum when it comes to explaining the intuition underlying the approach.

## Minor
- (p. 1. The 1st line of Section 1) instead of single prediction -> instead of a single prediction
- (p. 2. The 4th line after Eq. (2)) Spell out the initialisms.
- (p. 5, The 1st line after Eq. (8)) What are enc and dec?
- (p. 6. Theorem 4.3) $\tilde{\mathcal{F}}(X_{n+1}, \mathcal{S}_{n+1, j}) \leq T_k$ or $T_{k, \delta}$, rather?
- (p. 7. **In-silico screening for drug discovery**) I think the correct usage places the comma before the end quote and not after.
- (p. 7. **Entity extraction**) The letter $l$ has already been used earlier in the text.
- (p. 9. The 2nd line of Section 7) can be a critical in -> can be critical in
- (Appendix) Please check the punctuations in display equations.
- (p. 14) In Eq. (24), is $t$ in the middle expression $T'(\gamma; g)$? Do we take the expectation over $E_f$ before using Eq. (23)?
- (p. 14) w.l.o.g. -> W.l.o.g.
- (p. 14. The 2nd line after Eq. (26)) $\mathcal{S}_{n+1, j} \leq T_k$ -> $\tilde \mathcal{F} (X_{n+1}, \mathcal{S}_{n+1, j}) \leq T_k$
- (p. 14. The last line of the proof) $\mathcal{S}_{n+1, j} \leq T_{k, \delta}$ -> $\tilde \mathcal{F} (X_{n+1}, \mathcal{S}_{n+1, j}) \leq T_{k, \delta}$.

## Additional Comments

I am not sure if the title "Trading Coverage for Precision" is a good fit for the method being proposed. I would say that the method is more about using achieving a different target for validity. It looks to me whether the effect is to produce more precise prediction sets would depend on the dataset as well as the model being used.
summary_of_the_review: As of writing, I am on the fence about whether to recommend this paper for acceptance or rejection. On the one hand, the underlying ideas do appear to be sound and of merit. However, the issues of clarity are such that I cannot be sure of having evaluated them correctly.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Being capable of quantifying uncertainty is critical in various applications of ML systems. Conformal prediction is a framework that allows building a wrapper around a predictive model. Subsequently, a point prediction (corresponding to the top-ranked label) is replaced by outputting a set of labels that provably contains the true label of a test point with high probability (with the guarantees being only marginal). In particular, split conformal prediction proceeds by scoring every possible label of a test point and comparing these scores against the ones computed on a held-out set, followed by the decision of whether a particular label has to be included in the prediction set. However, in many applications due to present noise, the resulting prediction sets are larger / more conservative than expected, with many incorrect labels being included, and the presence of many false positives could be an unfavorable event in many real-world scenarios from the actionability standpoint (e.g., drug discovery, where adding an extra element to the prediction set corresponds to a significant cost increase of an experiment). The current paper studies a way of trading off coverage for precision, from both theoretical and practical standpoints.
main_review: In general, the paper is well-written, with a detailed review of relevant prior works in the literature. It focuses on uncertainty quantification for settings where certain budget constraints are imposed by a particular application, e.g., when adding an extra element to a prediction set has to be subsequently verified experimentally. The approach roughly boils down to: (a) fitting a multi-label predictor, (b) fitting a model that estimates the number of false discoveries, (c) using a proposed non-conformity score and a held-out set for calibrating a final threshold (subsequently used for constructing prediction sets) that allows provably controlling the number of false discoveries.

--- I was wondering whether the authors could elaborate more on the advantages of controlling the total number of false discoveries when compared against controlling its normalized version, false discovery rate, for which actually results have been established recently. The question arises mainly due to choosing $k$ in practice. While controlling FDR at level 0.1 is easy to interpret, what happens when one considers the total number of false discoveries?

--- A side notes about some typos: 
a. Several typos in Theorem 3.1: in equation 3, $x_{n+1}$ should be replaced with $x$. Also, in the line that follows equation 3, $C_\epsilon(X_{n+})$ should be replaced with $C_\epsilon(X_{n+1})$.
summary_of_the_review: The current paper represents a solid piece of work. The main reason for lowering the score is that several papers have considered post-hoc uncertainty quantification procedures for multi-label classification settings (possibly a more detailed lit review with focus on this is necessary). The authors propose a way of controlling the total number of false discoveries (either in expectation or with high probability) based on conformal inference. The score could be updated once the questions mentioned in the main review are answered.

**Update after rebuttal**

I would like to thank the authors for the detailed responses. Taking into account the general contribution of this work and points mentioned in this and other reviews, I tend to keep the current score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a new calibration procedure that builds upon the framework of Distribution free, risk-controlling prediction sets (RCPS) by Bates et al. (2020). The latter trades off the coverage guarantees of conformal prediction in favor of precision guarantees. While in RCPS the authors of RCPS show how to control the rate of false positives (false discovery rate, FDR), this paper presents a modification that puts a limit on the number of false positives that are contained in the constructed prediction sets. In other words, here the focus is on controlling the k family-wise error rate (k-FWER) instead of the FDR. The second contribution is the formulation of a deep net model that estimates the distribution of false positives in a candidate prediction set. This model is plugged into the proposed calibration scheme, used to find a threshold for rejecting or accepting candidate sets generated by the model. Lastly, in a series of experiments, the authors confirm the validity of the theoretical guarantees presented in the paper as well as the advantage of the proposed deep net model over baseline methods.
main_review: Overall, the paper is well-written and I enjoyed reading it. I believe it is a good contribution to the ever-growing literature on conformal inference. Below, I entail several comments about the proposed method.

The first comment is about the apriori choice of k in k-FWER. How can the user pre-specify this value? This is one of the limitations of using this proposed error rate compared to the choice of FDR. Currently, the paper does not discuss this issue, which I believe is central for deploying the proposed technique in real-world applications.

Still in that context, can you explain what is the outstanding theoretical challenge in proving the k-FWER control compared to the FDR-based procedure suggested in the original RCPS paper?

I understand that forming $\phi(x,y_i)$ as the marginal likelihood of $y_i$ being a correct label for $x$ is simple to implement. However, this seems to be suboptimal. To me, one of the major contributions of this work is the formulation of the deep net model to estimate the distribution of $S$, and therefore it will be a plus to explore other methods for estimating $\phi(x,y_i)$ beyond this simplistic approach (or, at least, discuss other options). Similarly, it will be interesting to understand when the greedy approach to identifying a sequence of nested candidate sets (described on page 5 bottom to page 6 top) will fail. Here, a synthetic simulation can be very useful.

As for $\Psi$ (eq. 8), the authors stated that they use labeled sets sampled from auxiliary training data. Can you elaborate more on that?

Regarding Remark 4.4: can you provide a small synthetic experiment that illustrates this issue? Also, when |\mathcal{Y}| is large, it seems to me that using the FDR control procedure is more natural and can be more powerful (as long as the number of true positives is large).

Experiments: the authors mentioned (Section 2) that “[...] as most of our target applications have relatively few true positives, FDR control can be somewhat volatile and lead to many empty predictions.” I believe it will be valuable to demonstrate this issue in experiments, to support the need for k-FWER control.

Lastly, please include in the Supplementary Material more details on the data sets used in the experiments.

summary_of_the_review: I believe this paper can be improved by addressing the above comments, e.g., how to pre-specify k (if possible), discussing alternative options to build the nested sets (that may be more complex), and explaining possible failure cases of the greedy approach. Also, discussing (e.g., via simulated data) the advantages and limitations of k-FWER over FDR seem to be important for the users to better understand which error metric is preferred, given the nature of the data at hand (and the existence of prior work).
review_title: null

Meta-review: This paper suggests that in multi-label classification (where there are multiple y that could be correct), the usual conformal prediction setup could be too conservative (too large a set with too many false positives), because it asks for "full" coverage. They propose to change the error metric from coverage to precision, to instead output a smaller set, with higher precision, potentially with the loss of coverage. The paper thus produces two variants of conformal prediction: guaranteeing that the expected number of false positives is at most k, and that the probability that the #false positives being > k is < \delta. The experimental study is interesting.

I followed the extensive discussion thread, and appreciate the authors' and reviewers' willingness to engage. However, in the end, the (excellent) reviewers were somewhat still not enthusiastic about the paper, and with nobody willing to champion the paper, it ended up on the borderline, in the bottom half of my set. Nevertheless, I read through the paper in detail myself to make sure, but I find enough reasons that suggest that the paper is not ready for publication currently, and would benefit from a significant overhaul.

It seems like the final algorithm is a slight variant of nested conformal prediction (a well known and oft-cited paper by Gupta et al, 2020 that the authors seem to miss) in the following sense. The usual conformal-for-classification framework would order the labels in terms of a score (like posterior probability) and then return a set of labels whose score is less than some threshold. (The same style of procedure can be used for the single-label and multi-label case also.) The nesting appears to be the same high level framework used in this paper, except that the threshold is chosen by a different rule from standard conformal prediction (ie same nesting, different threshold). Writing the algorithm more transparently will make for a tighter connection to the conformal literature --- at the moment, the authors claim a fair bit of novelty, but this is partially due to the omission of this reference and the cleaner broad (nested conformal) framework under which this work (as well as standard conformal) sit.

At the same time, I was not fully convinced of the central theoretical claim of the paper, in Proposition 4.6. The authors claim that since Theorem 4.3 is simultaneously valid for all j in B satisfying a condition (the filtered set), the theorem can also be invoked for a data-dependent index (chosen via (12)). This does not appear to the true, and at the very least requires careful justification. At a high level, dropping the conditioning for simplicity, Thm 4.3 reads as "forall j in [B], E[A_j] <= c", but this does not imply that for a data-dependent j-hat, we have E[A_{j-hat}] <= c. It would have been true, if the forall j appeared as a sup_j inside the expectation (or as a forall j inside the probability, rather than outside). The authors may want to clarify more carefully, if it is indeed true.

Minor: I also continue to find typos in the main results and proofs. These are minor, but should be corrected. I believe that in the last line of Theorem 4.3, the X_i should be X_{n+1}. In the display after (25), that should be T_k, and not T_{k,\delta}. There appear to be some other potentially missing references as well. For example, while distribution-free conformal approaches are cited, distribution-free calibration approaches are not, within the related work section. At the same time, some very recent papers, such as by Bates et al, or Angelopoulos et al, appear to be overemphasized in the introduction. A more fair coverage of related work could be useful.
Decision: Reject