Trading Coverage for Precision: Conformal Prediction with Limited False Discoveries
Authors: Adam Fisch
Tal Schuster
Tommi S. Jaakkola
Regina Barzilay
Venue: ICLR 2022 Submitted (2022)
Keywords: conformal prediction
confidence
uncertainty estimation
false discovery
natural language processing
computer vision
chemistry

Abstract: In this paper, we develop a new approach to conformal prediction in which we aim to output a precise set of promising prediction candidates that is guaranteed to contain a limited number of incorrect answers. Standard conformal prediction provides the ability to adapt to model uncertainty by constructing a calibrated candidate set in place of a single prediction, with guarantees that the set contains the correct answer with high probability. In order to obey this coverage property, however, conformal sets can often become inundated with noisy candidates---which can render them unhelpful in practice. This is particularly relevant to large-scale settings where the cost (monetary or otherwise) of false positives is substantial, such as for in-silico screening for drug discovery, where any positively identified molecular compound is then manufactured and tested. We propose to trade coverage for precision by enforcing that the presence of incorrect candidates in the predicted conformal sets (i.e., the total number of false discoveries) is bounded according to a user-specified tolerance. Subject to this constraint, our algorithm then optimizes for a generalized notion of set coverage (i.e., the true discovery rate) that allows for any number of true answers for a given query (including zero). We demonstrate the effectiveness of this approach across a number of classification tasks in natural language processing, computer vision, and computational chemistry.


Under review as a conference paper at ICLR 2022
TRADING COVERAGE FOR PRECISION: CONFORMAL PREDICTION WITH LIMITED FALSE POSITIVES
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we develop new approach to conformal prediction in which we aim to output a precise set promising prediction candidates that guaranteed to contain limited number of incorrect answers. Standard conformal prediction provides the ability to adapt to model uncertainty by constructing a calibrated candidate set in place of a single prediction, with guarantees that the set contains the correct answer with high probability. In order to obey this coverage property, however, conformal sets can often become inundated with noisy seeiiddttsswwice can render them unhelpful in practice. This is particularly relevant to large-scale settings where the cost (monetary or otherwise) of false positives is substantial, such as for in-silico screening for drug discovery. where any positively identified molecular compound is then manufactured and tested. We propose to trade coverage for precision by enforcing that the presence of incorrect candidates in the predicted conformal sets (i.e., the total number of false positives) is bounded according to a user-specified tolerance. Subject to this constraint, our algorithm then optimizes for a generalized notion of set coverage (i.c., the true positive rate) that allows for any number of true answers for given query (including zero). We demonstrate the effectiveness of this approach across a number of classification tasks in natural language processing, computer vision, and computational chemistry.
INTRODUCTION
For many classification problems, returning set of plausible responses instead of single prediction is a useful way of representing uncertainty (Gammerman and Vovk, 2007; Lei, 2014; Bates et al., 2020). Aligned with this goal, conformal prediction (Vovk et al., 2005) is an increasingly popular method for creating confident prediction sets that provably contain the correct answer with high probability. Unfortunately, these guarantees do not come for free; in order to achieve proper coverage on difficult tasks, conformal predictors are often unable to rule out an overwhelming number of candidates-makee their prediction sets large and inefficient (Angelopoulos et al., 2021c). This can make conformal predictors unusable in settings in which the cost of false positives is substantial.
Consider the example of in-silico screening for drug discovery (see Figure 1). In-silico screening uses computational tools to identify potentially viable molecular compounds for a particular purpose of interest. For instance, Stokes et al. (2020) recently performed a high-throughput screen of compounds from the multi-million molecule ZINC database (Sterling and Irwin, 2015) using models predictive antibiotic, and were successful. Clearly, guaranteeing
of E. coli inhibition in order to find high hit rates for this task with conformal prediction is an attractive proposition. The catch, however, that each returned candidate must be verified experimentally-and too many false positives can quickly consume the available budget (e.g., of time, funding, or other limited resources). This is especially relevant when valid answer-in this case, an effective drug-migh not even exist.
In this paper, we are interested in creating confident prediction sets that trade off coverage for precision in order to provably constrain the total number of false positives (FP). In other words, we shift the focus of our performance guarantee to be on limiting the number of incorrect answers in our outputs ge.g., s., to < k on average), with the understanding that we can potentially fail to recover some proportion of the true answers i..., we may obtain lower true positive rate (TPR). Concretely, suppose we have been given (possibly) multi-labe classification examples (X,, Z.) X' x 23, i = 1,... n as calibration data, that have been drawn exchangeably from some underlying distribution Pxz- Here consider the generalized scenario where each observation X; may have any number

---

Under review as a conference paper at ICLR 2022
High coverage
Target property Ap+]
Goal full coverage
P1 S C,) 2
Experimencal validation
High precision
True positives (has property Sas))
Goal few false positives
3/JG %aall S
C,
or
211Ces Zomil 5 21-6
Candidata molecules y
Figure 1: A demonstration of our proposed approach trading off standard coverage guarantees
("Goal A") for rigorous limits on the total number of false positives included in the output CR.s ("Goal B²). For in-silico screening for drug discovery, limiting false positives is critical when balancing a budget for experimental validation-even if it means that some true positives may be missed.
of corresponding correct labels (including zero, in the case of having no answer at all). That is, the response Z; be any subset of the full label space y Let Xn+1 E X' be new exchangeable test example for which we would like to predict Zn+1 y. Our goal is to construct a set predictor Cx(X, that maximizes recall with respect to the true Zn+1, but more importantl has an expected false positive budget that is controlled at a user-defined tolerance level l: E Ryo, i.e.,
[x N max( 1n)
maximize E
s.t. E (((C((X==1) Zn-11| S k.
(1)
As additional alternative to bounding the expected number of false positives k; we also seek set predictor Cx.8 that has more direct control of the probability of exceeding l: false positives:
maximize E CC,, (f,,((xn+))) Zn+il
P((Ces((nnt)) > Zuttl s <k)
5,
(2)
max 11)+
where d E (0, 1) is another user-defined tolerance level. Both constructions define different, but useful, operating conditions; the first is more straightforward (c.g.. for the general practitioner), while the second offers a finer, two-parameter level of control. Both are well-known concepts the context of multiple hypothesis testing- i.e., PFER, the per-family error rate, and k-FWER, the familywise error rate (Spjøtvoll, 1972; Romano and Wolf, 2007)-though the setting (multi-label classification) and available tools (conformal prediction) considered here differ substantially (see $2). Note that
both constraints are marginal over the choice of calibration and test data {(X,, 2,) ) however, celibration-conditionall
enforcing calibration conditional constraints requires only minor modification (Bates et al.. 2020).
In order to achieve the desired levels of false positive control, we present an approach that is based on set classification, combined with form of conformal calibration. Specifically, nonconformity measure F: X' x 2 + R to score candidate output sets, S E 2- We learn this function from separate multi-label classification training data. Intuitively, high nonconformity score should reflect the confidence that the candidate set might contain a high number false positives, and vice-versa. To empirically maximize the true positive rate, we then return the largest set among all candidates that have nonconformity scores below a threshold that we set such that our false positive constraints are satisfied. Candidate sets are explored greedily with best-first strategy that adds top-ranked individual labels to growing, nested output set S until our nonconformity threshold is met. This both allows us find efficient solutions for large label spaces V, and to leverage prior theory for calibrating expectations of monotonic losses for set predictors (Angelopoulos et al., 2021b).
use set
Contributions. In summary, main results follows:
A theoretical reframing of conformal prediction that provides rigorous false positive control;
A simple and effective strategy for constructing valid output sets with high true positive rates:
demonstration of the practical utility our framework across a range of classification tasks.
Note that the classification setting typically considered by conformal prediction, where the correct class is assumed to both exist and be unique, special case of this paradigm (i.e., the answer set is always of size one).
2

---

Under review as a conference paper at ICLR 2022
2 RELATED WORK
Uncertainty estimation. In recent years, there has been a growing interest in estimating model uncertainty. A large body of work focuses on calibrating model-based conditional probabilities, po(0n+1 1z+1), such that the accuracy, Mh+1 = In++1. is equal to the estimated probability (Niculescu- Mizil and Caruana, 2005; Kuleshov et al.. 2018: 8: Kumar et al., 2019). In theory, these estimates could be used to create prediction sets with few false positives, but they are not always guaranteed to be accurate (Guo et al., 2017; Ashukha et al., 2020; Hirschfeld et al., 2020). In similar vein, Bayesian formalisms underlie several popular approaches to quantifying predictive uncertainty via computing the posterior predictive distribution over model parameters (Neal, 1996; Graves, 2011; Hrrnnddzz-Lobate and Adams, 2015; Gal and Ghahramani, 2016). However, the quality of these methods can vary depending on the suitability of the presumed prior and on any approximation error.
Conformal prediction. As introduced in $ conformal prediction (Vovk al., 2005) provides finite-sapple. distribution free method for obtaining prediction sets C with guarantees on the event 1(Y,+1 E ((xx+))). Most efforts in CP focus on improving the predictive efficiency, B[I of the conformal sets (Vovk et al., 2016; Sadinle et al., 2019; Romano et al., 2020; Angelopoulos et al., 2021c; Fisch et al., 2021; Hoff, 2021). As coverage is guaranteed by design, improving efficiency will naturally lead to more precise sets with fewer false positives-but but not to specifiable level. Cauchois et al. (2021) develop a conformal approach to multi-label classification that can guarantee that the prediction set only contains true labels (i.e., =P= 0), but does not offer fine-grained control. Most relevant to our work, Bates et al. (2020) gives a flexible framework for controlling the risk, E(C(Y, T(X)),, of set-valued predictor T with an arbitrary loss function L-as as long the loss respects a monotonic nesting property, S C S' + L(S) 2 L(S"), for any two prediction sets S and S'. The calibration strategy we use here for marginal expectations is based the recent extension in Angelopoulos et al. (2021b). Concurrent to this work, Angelopoulos et al. (2021a) proposed methods to rigorously control non- non-monotonic losses, including the related false discovery rate (FDR), which normalizes the number of false positives over the size of the prediction set. However, as most of our target applications have relatively few true positives, FDR control can be somewhat volatile and lead to many empty predictions (making controlling total false positives more natural fit for this work).
Multiple testing. Controlling the number of false positives/discoveries over collection of hypothe- sis tests is a well-studied problem in statisties (Dunn, 1961; Benjamini and Hochberg, 1995; Lehmann and Romano, 2005; Romano and Wolf, 2007, etc.). Recently, FDR control has also been studied for outlier detection in a conformal inference setting (Bates et al., 2021). Most statistical approaches to false discovery control operate over p-values for each hypothesis test that have specific dependency structures (e.g., independent or positively dependent), or otherwise use more conservative corrections. Though similar, our multi-label classification setting slightly different from standard multiple testing in that there is (1) an unknown dependency structure between candidate labels for the same query, but also (2) an extra layer of exchangeability over the n queries. Our approach is able to ignore (1) by leveraging (2) within a conformal calibration framework to obtain desirable guarantees.
Selective classification. Our work also bears some relation to selective classification (El-Yaniv and Wiener, 2010), where models have the option to abstain from answering. In particular, Geifman and Ya- (2017) propose a strategy for finding classifiers with specific selective risks (i.e., the expected accuracy over answered examples). In our setting, this is analogous to controlling false positives using k se O. If uncertain, the model would have to "abstain" by outputting an empty set.
3 BACKGROUND
We begin with a review of conformal prediction (see Shafer and Vovk, 2008). Here, and in the rest of the paper, upper-case letters (X) denote random variables; lower-case letters (ar) denote constants, and script letters (X)) denote sets, unless otherwise specified. Proofs are deferred to the appendix.
Given a new example x, for every candidate label y V, single label conformal prediction (where Va+1 is a scalar) either accepts or rejects the null hypothesis that the pairing (x. y) is correct. The test statistic for this test a nonconformity measure, .M ((x, y), D), where D is a dataset of exchangeable, labeled examples. Informally, lower value of M reflects that point (I, y) "conforms" to D, whereas a higher value of M reflects that (xry) is atypical relative to D. A practical choice for M is a model- based loss, e.g., log po (y) (r), where 0 is model fit to D. For conformal prediction to work, is important that M preserves the exchangeability of its inputs: i.e., M should be symmetric with respect to permutations. In order to avoid retraining M every time new candidate label is
3

---

Under review as a conference paper at ICLR 2022
considered, "split" conformal prediction (Papadopoulos, 2008) uses proper training set Dirain to learn a fixed M.. This preserves exchangeability the calibration and test points without further modification- and is popular and computationally efficient strategy (which follow in this work).
To construct prediction set for new test point 2n+1, the conformal classifier outputs all y for which the null hypothesis (that pairing (I, y) is correct) is not rejected. This is achieved by comparing the scores of the test candidates the scores computed over the first calibration examples.
Theorem 3.1 (Split CP, Vovk et al. (2005); Papadopoulos (2008)). Assume that examples (X,, Y,) X x V, i == -...., n are drawn exchangeably from a distribution Pxy. For a fixed nonconformity measure M, let random variable V; (M,,, Y:) be the nonconformity score of (Xi, Y.). For c E (0, 1), define the conformal set (based on the first n examples) at x E X as
Ce(x)) = {u E:: M(x,D) M( < Quantile(1 V1. ((o0))}
(3)
Then (x(xx+1) satisfies P(Y++1 E (Xn+1)) C-c
Remark 3.2. Cauchois et al. (2021) recently extended conformal prediction to the multi-label case to obtain guarantees of the form P(C (Xn+1) S Zn+1 S Conter (Xn-1)) 2 1 - c. Their approach constructs bounding sets using modified version of the single label algorithm (i.e., Eq. (3)).
The motivation for our work quickly evident from Eq. (3): if we are unable reject most candidates E y based on their nonconformity scores M[I++1, v). then C. (x) can contain many false positives.
CONFORMAL PREDICTION WITH FALSE POSITIVE CONTROL
We now introduce our strategy for trading off coverage for precision by imposing constraints on the number of false positives that are contained in our output sets. To briefly remind the reader of our setting, we assume that we have been given n exchangeable multi-label classification examples, (X,, 74) E X' x 2", i ..... calibration data, that are drawn from distribution Pxz. The response Z, is treated as generalized set of correct labels for input X., and is a subset of y, where y finite. For prediction ((xn+1) y evaluated a point In+1 E X with true label set Zn+1 V we define the true positive proportion (TPP) as the ratio of correct labels that are recovered:
(((x+11) n Zn41l
(((n+)))
(Note that TPR := E[TPP),
(4)
max([zn41] 1,
and the number of false positives (FP) the total count of incorrect labels in C(Fn+1):
(P(zn+1,C(an+t))) = [C(x.+1) #n-1/-
(5)
Our goal, as stated $1, is to maximize the expected TPP (in standard classification, this would equate to accuracy; power in statisties), while constraining the FP in either of two ways:
Definition 4.1 (k-FP validity). A conformal classifier C2 evaluated at test point (Xn+1: Zn+1) k-FP valid the expectation of its FP satisfies [E[FP(Zn+1, Ca Cu(Xn41)) S k.
1) is
Definition 4.2 ((k, 8)-F validity). A conformal classifier Cx,5 evaluated at test point (Xn+1. Zn+1) (k. FPP valid if the CDF of its satisfies P(FP(Zn+1, Ck, C( (x,+1)) S k) Z
4.1 AN ORACLE SET PREDICTOR
To motivate our approach, imagine an oracle with access to Pz|x, the conditional distribution of the lubti-label set Z given the input X. Given this information, for any input X' and candidate set 2", such an oracle would be able to exactly calculate both the expectation and the conditional distribution of the number of false (and true) positives in S given x. In order to maximize the TPR while meeting k-FP and (k:, 8FP validity, it could then yield the following set predictions:
Coracle (x)
arg max (E(TPP(S) x) (Z, x] < k). and
(6)
SC2V
Coracle (z) := arg max (E(TPP(S) x] ((FP((.
|]] k) < 5}.
SC2y
where ties in the arg max are broken by set size (smaller is better). This oracle has the advantage of only being marginally valid, but also being conditionally valid given the test input X,+1 1r+1-
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Conformal prediction with false positive control (in expectation case. see Eq. (1)).
Definitions:
#n+1 is the test point, Darain is a training set, Dewl is an exchangeable calibration set, A is the FP tolerance, and B is a parameter for considering only the top individually ranked candidates y E y. MultilabelModel is an abstract model that provides individual label predictions. SetModel an abstract FP- prediction model operating over sets (where in this work we propose to use DeepSets (Zaheer et al., 2017)).
1: function TRAIN(Derain. k)
2: D(1) D(2) + SPLIIT(Desia)
3: # Use part of the training set to learn individual label likelihood polue 7 x).
4:
polye E 7 x)) t- TRAIN(MultilabelMMas
(isiin)
5:
Use the other (smaller) part learn the FP-predictive set function F F(z, S).
6:
F(x, S) <- TRAIN(SetModel, D
7: Manually define to be monotonic for nested sets Si S ... S..
8:
F(x, Sm) f (xx, ((I,
9:
return Po. -F
10:
function CALIBRATE(PE. Dent,, k. B)
Teal =
12:
for (Ii, Deal do
13:
# *Rank candidates y E y by top (y E Z. xx). up to bound B.
14:
(St.a.-.,,S. ) + (OOOR(Y'PPop)) & 7a 2:)) z:));;: E (1...., .......P)) B}} # +Implicitly define MFP based this ordering.
15:
16:
MFP(2;,22 21) + INIT Z;, R.F, ,..S...... Sz})
17:
Teat - Teal J [MFP Iz, 2.]]
18:
ta + HND__HRESHOLLD Teal B, k) # Using Eq. (10).
19:
return &
20:
function PREDICT(E=+1, po, F, te. B)
21:
Rank new candidates y E y by top pe (ye E 7n In+1). up to bound B (as in line 14).
22:
(S.411)....,S4t
< {SORI (Pppoyy E Zn41 an+1 1).f j E B))
23:
Return largest prediction that passes threshold tg.
24:
Cs Cx(xn+1) +- arg S............. (1S]: F(In41, 5) 5(
25:
return Cx (Ia+1)
4.2
APPROXIMATING THE ORACLE USING SET FUNCTIONS
Of course, computing such an oracle is not practical, Pzix is not known. Instead, let F be set function F: X' x 2> + R that generates a score for the candidate set S given In+1. Importantly, F can be any function (as will later show), but to best replicate the oracle's 's behavior for k-FP and (k, -)P valid predictions, F should be a good estimator of the distribution of false positives in S.
We now describe simple approach to modeling F using DeepSets (Zaheer et al., 2017). DeepSets a popular method which is known to be a universal approximator for continuous set functions. Let (œ(xr, y1).... obI, vs)} featurize a candidate set S C y, where 6(x, yc.) E Rdd is function of (x, Vo), for ye E S. In practice, we find that taking o(x, yo) to be (fixed) estimate of po E 2 x). the marginal likelihood of yo being correct label, performs well and is simple to implement. These (uncalibrated) prediction scores can be provided by any backbone model. For example, in our in-silico screening task, we define using directed MPNN (Yang et al., 2019) that independently classifies molecules as active or inactive for the target property. Given Φ the DeepSets model is defined as
V (r, S) := -sotmax (dec
Σ enc(ó(æ, (:)0)))
B.ES
where enc(-) and dec(-) are two neural encoder/decoder models parameterized by 0, and 02, respec- tively, and softmax(-) is taken over the total possible number of false positives, () v is trained to predict the number of false positives in S via cross entropy, using labeled sets sampled from held-out training data. We then compute Fù and Fi,s (for either k-FP or (k, 8)F validity) as min(k.||S)
[S] S) = Σn (x, and F2.s =3 5)) Σ T (x,
where (xx S),, denotes the 17 index of the softmax (i.c., the estimated probability that FP= 17). In the next section will refer only to F, with the understanding it differs based the validity goal.
5

---

Under review as a conference paper at ICLR 2022
4.3 IDENTIFYING VALID CANDIDATE SETS
Although our set predictor F is trained to model either the expected FP or its CDF, it is not nec- essarily accurate. If J were simply substituted into Eq. (6) or Eq. (7), may not produce valid set predictions. To remedy this, we carefully calibrate a threshold for accepting candidate sets based on F. First, we greedily identify a sequence of nested candidate sets, S1 C S2 C ... CV. by ranking individual labels Vc E Y by their estimated likelihoods of being true positives, i.e., polye E 2 | æ), and include them one by one. Next, each of these candidate sets is given a score by F, which we treat "nonconformity score." We manually enforce that the scores produce ranking consistent with their size: for set S we compute its adjusted nonconformity score F(x, S)) as F(I, S max S1).... F(x, 8,)}. For efficiency (see Remark 4.4), only take the top B I [ sets (although this doesn't come for free: a smaller B may result in fewer true positives).
Let MFP 2,1] := max { (FP S F(e, S₁) S 1} denote the maximum number of false posi- tives over all nested sets Sj for an input that have nonconformity scores less than I. If this thresh- olded set is empty, then the MFP is defined to be O. Since the sets are ordered by size, this quantity is guaranteed to be monotonically nonddccraasing in i..., S t' = MFP(xx, t) S MFP(x, 2, z,t"). Using this property, we can calibrate & to create a set filter with controlled MFP, as formalized next:
Theorem 4.3 (FP-CP). Assume that examples (X,, 74) E X x 2", exchangeably from distribution Pxy. For each example i, let Sty. j- I.... B (where B S | is a finite typer-parameter be nested sets with non-decreasing, lower-bounded nonconformity scores F(X,,Sis): For l E Rzo and 8 E (0, define the random variables Tp and TR.s as
1, n + 1 are drawn
Ty == sup { E R:
B
MF 2,, s kk and
(10)
n
T3,6 sup {t R:
kk) n 1/MFP t,, 1k} 2 11
(11)
Then for any j E (1,..., (, S k| ((,,,, S Tx,6) 2 8.
BB..,,B). B}. we have that (E Sat1,) [i,, Sn+1s) S Ta. $ k, and
The proof, given in Appendix A, uses results from marginal RCPS (Angelopoulos et al., 2021b).
Remark 4.4. The hyper-parameter B plays an important role. T. may be very conservative if B D and | is very large, to the point where T3- 0o always if [>] > * (n + 1). It can be beneficial to truncate the considered label space y for an example to only the top B < k (n + 1) individual candidates. fg1.... yB} } E y For example, for text generation tasks (like machine translation), the label-space y is infinite, but we can instead restrict our predictions to a subset of the top B beam search candidates (where B can still be large to a reasonable degree).
put on the underlying F in Theorem 4.3; it is model- agnostic, and need not even be a DeepSets architecture of the form of Eq. (8). If, however, F is a good estimator of FP 8) | X, then T& and Ta. are likely to identify sets that are approximately valid conditional on Xat1, which we show empirically for our choice of DeepSets models in $6.
Remark 4.5. Note that constraints
4.4 SELECTING THE FINAL OUTPUT SET
The main result of Theorem 4.3 is that, using the calibrated nonconformity threshold Ta Tk.s t", we can construct a collection of sets that are simultaneously valid. In other words, we are free to select any set in the filtered set of candidates {Sn+13 : greedy, but simple and robust, approach we simply take the largest set in our filtered set of candidates as our final output. That is, for an input x E X and calibrated threshold 1" RR
S t²} valid output. As
{1S): F(x, S F)x,
Co (x, == arg max
(12)
SE(S
where C. is either Cs Cs,8 (i.e., they are constructed the same way, but for different thresholds t'), and where we define arg max to return Ø if the set {S E (S,...., Sp] F(x, 8) S (3} is empty. Proposition 4.6 (Greedy FP-CP). As defined in Eq. (12), the set (x Tx) is k-FP valid, and the set Te.6) is (k. 8)-FP valid. Furthermore, among sets Sn+1, E (SS411....... S....p))))) that have nonconformity scores & T. Tk or TR.o, the set Co (Xn+1; To) maximizes the TPR.
6

---

Under review as a conference paper at ICLR 2022
5 EXPERIMENTAL SETUP
In this section, we briefly outline our evaluation tasks and associated models. We also describe our evaluation and baselines. For all experiments, we set B 100 (recall Remark 4.4), which caps the number of considered labels per example to the top 100. Appendix C contains additional details.
5.1 TASKS
In-silico sereening for drug discovery. As introduced in $1, the goal of in-silico screening is to identify potentially effective drugs to manufacture and test. We use the ChEMBL database (Mayr et al., 2018) to screen molecules for combinatorial constraint satisfaction, where given a constraint such as "has property A but not property B," we want to identify the subset of molecules from a given set of candidates that have the desired attributes. We partition the dataset both by molecules and property combinations, that at test time the model must make predictions on combinations it has never been tested on before, over a pool of molecules that it has never seen before. Scores for individual candidate molecules are obtained via combining independent property assignment probabilities predicted by an ensemble of directed MPNNs (Yang et al., 2019) using a naive independence assumption.
Object detection. The goal of object detection is to place bounding boxes around all objects of a certain type that are present in an image (of which there may be few, many, or none). We use the MS-COCO dataset (Lin et al., 2014), a large scale object detection dataset with images of complex everyday scenes containing 80 object categories (such as person, bicycle, dog, car, etc). We extract typed bounding box candidates (i.e., tuples of both location and category) using an EfficienDDet model (Tan et al., 2020) with non mon-maximum suppression. True positives are defined as boxes that have an intersection over union (loU) >
0.5 with a gold annotation of the same type.
Entity extraction. In entity extraction, are interested in identifying all named entities that appear in a tokenized sentence I of length 4, x {WI,... w A named entity is a contiguous span (Wstart..... ... Wend] x of the input sentence that refers to a real-world object (such person, location, organization, or product) that can be denoted with a proper name. We report results on the CoNLL NER dataset (Tjong Kim Sang and De Meulder, 2003), where we use the PURE span-based entity extraction model of Zhong and Chen (2021) to predict scores for all O(t2) candidate spans. We consider exact span predictions the correct category to be true positives, and all others to be false positives. Not all sentences are guaranteed to have entities (in fact, many do not contain any).
5.2 EVALUATION
We use proper training, validation, and test set for each task. We use the training set learn all models, i.e., Po (v. E Z 2) and F.2 We do model selection on the validation set, and report final numbers as the average over 1000 random trials on the test set, where in each trial we partition the data into 80% calibration (I11.) and 20% prediction points (In+1). To compare aggregate performance across tolerance levels, we plot each metric as a function of & (up to k = B), and compute the area under the curve (AUC). Shaded regions show the 16-84th percentiles across trials. In addition to TPR and FP, inspired by Angelopoulos et al. (2021c), we compute the size-stratified k-FP violation:
(Ca SSFPx(C, (1)=_1) sup max [R(FP(Zn+ (E
E A.) k. 0)
(13)
where (A]]= forms partition of (1,..., [D']], and È denotes the empirical average over our test trials. SSFPk.. for (k, 6)PF violation is defined similarly, where we compare the worst-case average number of predictions with more than & false positives the tolerance 5. As argued in Angelopoulos et al. (2021c), lower size-stratified violation suggests that a classifier has better conditional coverage. As marginal validity already theoretically guaranteed by our procedure, we focus on this metric.
5.3 BASELINES
For all experiments, we compare our conformalized DeepSets model (NN), to the following baselines:
1. Top-k. We naively take the top k' fixed predictions for any Ta+1, where k' is found using average performance on the calibration set (without any correction factors, so it is not generally guaranteed to be valid). Note that k'' can be (and mostly is) different than the user-specified & for FP.
If training data is limited, we learn the DeepSets model for F with fixed hyper- paramparaseterss. on the validation data, after we have finished performing any other model selection for the base multi-label model, po E Z x).
7

---

Under review as a conference paper at ICLR 2022
22-F-M0 Mooi 2604
555
5579.5
TIRL
TPR
1440 (1:041)
20:0
(a) In-silico screening
(b) Object detection
(c) Entity extraction
Figure 2: (k-6) results function of k for 8 0.1 (up to k B 100). The top row plots SSFPx,a R.,8 violation (lower is better). The bottom row plots TPR (higher is better). We see that compared to the other baselines, our conformal deep sets approach (NN) has the best (or close the best) TPR AUC across tasks, while having the lowest (or close to the lowest) SSFP violation.
Outer Sets @ 90. We use the (one-sided) multi-label conformal prediction technique of Cauchois et al. (2021) to bound P(Zn+1 S. Ce (X)+1)) 2 0.90. Though not directly comparable, we use this to benchmark our method against sets that preserve marginal coverage (at typical level). For simplicity, we use the direct inner/outer method without dynamic CQC quantiles."
Inner Sets. Again, we use the (one-sided) method of Cauchois et al. (2021), this time to bound P(C, (Xn+1) C. 1n+ 2 1-6 at level eter, and the FP upper bound) for k-FP control and at level e = for (ks, 8) control. It is straightforward to show that these levels of e conservatively achieve k-FP and (k, 6FF control.
B (recall that B S | is the truncation param-
Independent scoring (max). We take F(x, S) to be the maximum individual label uncertainty in S, max (ye Z æ): Me E S}. This is equivalent choosing labels independently. The full model is calibrated using the same FP-CP algorithm (it is a drop-in replacement for the NN).
5. Average scoring (avg). We take S)x to be the average individual label uncertainty in S, "SI''E,ess 1 - po (ye E x). We calibrate po (yee E Z 2) using Platt scaling (Platt, 1999). As with the max score, the full model is calibrated using the same FP-CP algorithm.
Baseline (1) contrasts our approach with what is normally a "first thought" in practice; (2) and (3) test the efficacy of our system over existing techniques; (4) and (5) compare to simpler scoring variants.
6 EXPERIMENTAL RESULTS
Constraining false positives. The top rows of Figures 2 and show the size-stratifics violation (Eq. (13)) for (k, F) and k-FP, respectively. Across levels of k. our approach hased on DeepSets (NN) achieves substantially lower worst-case violations than either of the max or average score baselines. The Top-k and Inner Sets approaches also prevent large violations (though, by itself, this result is not necessarily impressive-as simply always returning an empty set will lead to zero SSFP). When accounting for TPR (bottom rows), we see that our FP-CP model does considerably better.
Maximizing true positive rates. The top rows of Figures 2 and 3 plot TPR rates and AUC across many values of k. while Table details results for the in-silico screening task for several representative configurations. On the screening task, see that our FP-CP (NN) method provides significantly higher TPR than other basclines. For example, allowing no more than 5 false positives leads to a TPR of 36.1% with k-FP. In comparison, the TPR of Top k is only 29.8%. Differences in TPR are less pronounced on the object detection and entity extraction tasks, however, all FP-CP methods (with max, avg, or NN scoring) provide high TPR (exceeding non FP-CP methods) even at low values of k.
Preliminary studies indicated that including CQC quantiles did not lead significantly different results.
8

---

Under review as a conference paper at ICLR 2022
BEHIE FS.P Buledtl
MASTORO 10.00 pa
SEP
TPRL
Stuect
2.07 00-00
(a) In-silico screening
Object detection
Entity extraction
Figure 3: k-FP results function of for (up k: B 100). The top row plots size-stratified k-FP violation (lower is better). The bottom row plots the TPR (higher is better). As the number of allowed false positives grows, our methods quickly achieve high power. Consistent with Figure our conformal DeepSets approach (NN) demonstrates high TPR and low SSFPs & across tasks.
Top k
Inner Sets
FP-CP (Max)
FP-CP (Avg)
FP-CP (NN)
R-FP:
Avg. FP
TPR
Avg.
FP
TPR
Avg.
TPR
Avg.
TPR
Avg. FP
k:
4.59
29.8
0.14
2.5
4.98
27.5
4,99
24.1
4.98
36.1
14.47
53.4
0.88
14.98
14.98
43.8
14.99
59.9
25
24.51
68.0
1.49
13.4
24.98
66.8
24.98
58.9
24.99
73.2
k 35
34.54
78.2
2.45
18.4
34.97
78.4
34.96
71.2
34.99
82.5
(ks FP with
0.9:
FP < k
TPR
FP & k
TPR
FP S k
TPR
FP < A
TPR
FP S A:
TPR
k = 5
100.0
20.5
96.6
6.36
90.0
15.8
90.0
14.0
90.0
31.6
k 15
94.7
42.4
99.5
6.36
90.0
26.7
90.0
22.3
90.0
55.3
k 25
96.6
55.7
100.0
6.36
90.0
37.4
90.0
29.3
90.0
69.0
97.5
66.2
100.0
6.36
90.0
49.1
90.0
36.9
90.0
79.0
Table 1: Results for the in-silico screening task over the ChEMBL dataset. TPR and FP < are expressed as percents (i.e., x x100). We see that our FP-CP methods meet our target thresholds; using the Inner Sets formulation does too, but is conservative (as expected). Applying FP-CP calibration with our DeepSets model (see NN) yields substantially higher TPR across various tolerance levels k.
Comparison conformal coverage methods. Table B. gives the results of the coverage-secking Outer Sets method at level 0.90 (a typical tolerance). Indeed, we achieve strong TPR (97.2% for the in-silico screening task), but also incur a high false positive cost in the process (63.6 average FP for in-silico screening). In contrast, method allows directly modulate false positives, without losing high TPR (e.g., equivalently controlling for < 63.6 FP, we acheive 97.0% TPR on screening).
CONCLUSION
Conformal prediction, in its standard formulation, already grants theoretical performance guarantees that can be critical in many machine learning applications. Naively applying CP, however, can yield disappointing results. Even the target coverage indeed upheld, the predicted sets may be too large, and include too many false positives to be practical. In this paper, we proposed method for trading coverage guarantees in favor of precision guarantees, where we enforce limit to the number of false positives that are contained in prediction sets. Our results show that method yields classifiers that (1) still achieve strong true positive rates compared to their coverage-secking counterparts, and (2) provide meaningful output sets with effectively controlled total false positive counts.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
Our FP control methods are general and can be applied to many applications and on top of any model for computing nonconformity scores, It's worth noting that any undesirable biases exhibited by underlying models can still propagate the prediction sets of our methods. While our methods provide marginal performance guarantees, we recommend that any application to perform controlled evaluation across target populations ensure faimess.
REPRODUCIBILITY STATEMENT
All datasets used in this paper are publicly available (see $5.1). Also, we use publicly available models for computing the nonconformity scores. For drug discovery, we use the ensemble of directed MPNNs from chemprop ject detection, we use tf efficientdet d2 from https: / qithub. com/ wwwpghtaag////////cc/////mm efficiientdet--ytooae //github.
com/ chemprop/ chemprop). For ob-
For entity extraction, we train the PURE entity model (https: on the ConLLO3 dataset using a context window of 100, batch size 32, albert-base- encoding model, and the suggested learning rate of 1e-5, and task learning rate 4. Default values were used for all other parameters. The results in Section 6 are all based on the experimental setting described in Section 5, We will release our code for running these experiments and for reproducing all plots and tables.
REFERENCES
Anastasios Nikolas Angelopoulos, Stephen Bates, Emmanuel Candès, Michael I. Jordan, and Lihua Lei. Learn then test: Calibrating predictive algorithms to achieve risk control. ArXiv preprint: 2/.001052, 2021a.
Anastasios Nikolas Angelopoulos, Stephen Bates, and Lihua Lei. Risk control in expectation: A proof and counter example, 2021b. URL btctt://angellee opoulos wotossaa/puubi /ipppblli iiaaiiiiionn downloads saaaaddrrreeeoeeeeee pdf.
Anastasios Nikolas Angelopoulos, Stephen Bates, Jitendra Malik, and Michael Jordan. Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations (ICLR), 2021c.
Arsenii Ashukha, Alexander Lyzhov, Dmitry Molchanov, and Dmitry Vetrov. Pitfalls of in-domain uncertainty estimation and ensembling in deep learning. In International Conference on Learning Representations (ICLR), 2020.
Stephen Bates, Anastasios Nikolas Angelopoulos, Lihua Lei, Jitendra Malik, and Michael I. Jordan. Distribution free, risk controlling prediction sets, ArXiv preprint: 2101.02703, 2020.
Stephen Bates, Emmanuel Candès, Lihua Lei, Yaniv Romano, and Matteo Sesia. Testing for outliers with conformal p-values. ArXiv preprint: 2104. 08279, 2021.
Yoav Benjamini and Yosef Hochberg. Controlling the false discovery rate: A practical and pow- erful approach to multiple testing. Journal of the Royal Statistical Society Series (Staristical Methodology), 1995.
Maxime Cauchois, Suyash Gupta, and John C. Duchi. Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction. Journal of Machine Learning Research (JMLR), 2021.
Olive Jean Dunn. Multiple comparisons among means. Journal of the American Statistical Associa- tion, 56(293). 1961.
Ran El-Yaniv and Yair Wiener. On the foundations of noise-free selective classification. Journal of Machine Learning Research (JMLR), 11, 2010.
Adam Fisch, Tal Schuster, Tommi Jaakkola, and Regina Barzilay. Efficient conformal prediction via cascaded inference with expanded admission. In International Conference on Learning Representations (ICIR), 2021.
10

---

Under review as a conference paper at ICLR 2022
Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. In International Conference on Machine Learning (ICML), 2016.
Alexander Gammerman and Vladimir Vovk. Hedging Predictions in Machine Learning: The Second
Computer Journal Lecture. The Computer Journal, 50(2), 2007.
Yonatan Geifman and Ran Elniv..v. Selective classification for deep neural networks. In Advances in Neural Information Processing Systems (NeurIPS). 2017. 2017.
David L. Gold, Jeffrey C. Miecznikowski, and Song Liu. Error control variability in pathway-base microarray analysis. Bioinformatics, 25(17):2216-222) 2009.
Alex Graves. Practical variational inference for neural networks. In Advances Neural Information Processing Systems (NeurIPS), 2011.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning (ICML), 2017.
José Miguel Hernández-Looee and Ryan P. Adams. Probabilistic backpropagation for scalable learning of bayesian neural networks. In International Conference Machine Learning (ICML), 2015.
Lior Hirschfeld, Kyle Swanson, Kevin Yang. Regina Barzilay, and Connor W. Coley. Uncertainty quantification using neural networks for molecular property prediction. ArXiv preprint: 2005.10036, 2020.
Peter Hoff. Bayes-optimal prediction with frequentist coverage control. ArXiv preprint: 24045, 2021.
Volodymyr Kuleshov, Nathan Fenner, and Stefano Ermon. Accurate uncertainties for deep learning using calibrated regression. In International Conference Machine Learning (ICML), 2018.
Ananya Kumar, Percy Liang, and Tengyu Ma. Verified uncertainty calibration. In Advances in Neural Information Processing Systems (NeurIPS). 2019.
Zhenzhong I Lan, Mingda Chen, Sehastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. Albert: A lite bert for self-supervised learning of language representations. In International Conference on Learning Representations (ICLR), 2020.
E. L. Lehmann and Joseph P. Romano. Generalizations of the familywise error rate. Annals of Statistics, 33(3), 2005.
Jing Lei. Classification with confidence. Biometrika, 101(4), 2014.
Tsung-Y Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick. Microsoft coco: Common objects in context. In ECCV, 2014.
Andreas Mayr, Günter Klambauer, Thomas Unterthiner, Marvin Steijaert, Joerg Wegner, Hugo Ceulemans, Djork-Amé Clevert, and Sepp Hochreiter. Large-scale comparison of machine learning methods for drug target prediction chembl. Chemical Science, 9(24), 2018.
Radford M. Neal. Bayesian Learning for Neural Networks. Springer-Verlag. 1996. ISBN 0387947248.
Alexandru Niculescu-Mizil and Rich Caruana. Predicting good probabilities with supervised learning. In International Conference on Machine Learning (ICML). 2005.
Harris Papadopoulos. Inductive conformal prediction: Theory and application to neural networks. In Tools Artificial Intelligence, chapter 18. IntechOpen, Rijeka, 2008
John C. Platt. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In ADVANCES IN LARGE MARGIN CLASSIFIERS, pages 61-74. MIT Press, 1999.
Joseph Romano and Michael Wolf. Control of generalized error rates in multiple testing. Annals of Statistics, 35(4), 2007.
11

---

Under review as a conference paper at ICLR 2022
Yaniv Romano, Matteo Sesia, and Emmanuel J. Candès. Classification with valid and adaptive coverage. Advances in Neural Information Processing (NeurIPS), 2020.
Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of American Statistical Association, 2019.
Glenn Shafer and Vladimir Vovk. tutorial on conformal prediction. Journal of Machine Learning Research (JMLR), 9:371-421, June 2008
Emil Spjøtvoll. On the Optimality of Some Multiple Comparison Procedures. The Annals of Mathematical Statistics, 43(2):398 411, 1972. doi: 10.21444am//1177696661. URL httpa:
//doi. oro 10. aomss 1177692621.
Teague Sterling and John Irwin. Zinc 15 ligand discovery for everyone. Journal of Chemical Information and Modeling, 55(11):2324-23337 11 2015.
Jonathan Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruii Nina Donghia, Craig MaeNair, Shawn French, Lindsey Carfrae, Zohar Bloom-Ackerman, Victoria Tran, Anush Chiappino-Pepe, Ahmed Badran, Ian Andrews, Emma Chory, George Church, Eric Brown, Tommi Jaakkola, Regina Barzilay, and James Collins. A deep learning approach antibiotic discovery. Cell, 380:688-702..13, 02 2020.
Mingxing Tan, Ruoming Pang, and Quoc V. Le. Efficientdet: Scalable and efficient object detection. 2020 IEEE/CVE Conference on Computer Vision and Puttern Recognition (CVPR), pages 10778- 10787, 2020.
Erik Tjong Kim Sang and Fien De Meulder. Introduction to the CoNLL-2003 shared task: Language-indepente named entity recognition. In Proceedings of the Seventh Conference on Natural Language Learning at HI.T-NAACL 2003, pages 142-147, 2003. URL https:
//aclantho wowloggyooooo orgg//03-0419
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in Random World. Springer-Verlag. Berlin, Heidelberg, 2005.
Vladimir Vovk, Valentina Fedorova, Ilia Nouretdinov, and Alexander Gammerman. Criteria of efficiency for conformal prediction. In International Symposium on Conformal and Probabilistic Prediction with Applications Volume 9653, 2016.
Kevin Yang, Kyle Swanson, Wengong Jin, Connor Coley, Philipp Eiden, Hua Gao, Angel Guzman- Perez, Timothy Hopper, Brian Kelley, Miriam Mathea, Andrew Palmer, Volker Settels, Tommi Jaakkola, Klavs Jensen, and Regina Barzilay. Analyzing learned molecular representations for property prediction. Journal of Chemical Information and Modeling, 59(8):3370-3383 2019.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Zexuan Zhong and Danqi Chen. A frustratingly easy approach for entity and relation extraction. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 50-61, Online, June 2021. Association for Computational Linguistics. doi: 10.18653/v1/202 maacl-main.5. URL https: //a //aclanthe ho logy org/2021. saacl-maing
12

---

Under review as a conference paper at ICLR 2022
Appendix
A PROOFS
A.1 PROOF OF THEOREM 3.1
Proof. This is a well-known result; we prove here for completeness. Since the nonconfornity scores Vi are constructed symmetrically, then
((x1, V1), ...................... (Xn+1, Y Y++1) _ ((Xo(1), Vo(i)).... (Xo(n+1), Yo(n+1))) - (V...... ..... Vn+1) & (Vo(1)..... Vo(nt))) for all permutations (o(1). ................................ (n 1)). Therefore, {(x,, Y)) are exchangeable, then so too their nonconformal scores {Vi)
By the construction of C, we have
Ya+1 E Cx(xn+1) = Va+1 & Quantile(1 - e, Vin U {oo}).
This implies that V44+ is ranked among the (1-e) -). (n + 1)] smallest of Vi,..,, Vn, 0o. Since Vi exchangeable, this happens with probability least
A.2 PROOF OF THEOREM 4.3
Our proof will use Theorem of Angelopoulos al. (2021a), which state here:
Theorem A.1 (Marginal RCPS, monotonic non-increasing case). Let L;: IR + RRi== 1.. n
be exchangeable functions, where L,(t) is non-increasing
Also, take g: + R where g(x)
non-decreasing in Further assume that g L, is right-continuous, and
inf ((L((t) <, sup g (t))) s B < co almost surely. t
(14)
For any 7 2 0, define the random variable T(7.g) 9) as
T(r:g) = inf t:
o(L,(t)
o(L,(t)) s
(15)
n +
Then Elg Lnt1 (T(rg))) 7 .+I
Corollary A.2 (Marginal RCPS, adjusted). Under the same setting as in Theorem A.I,
Elg o An41(T((7:0))) S.
(16)
where
T(1:g) inf
B B+ Σ ((L(())
sM7.
(17)
n+1
Following their analysis, we give a second corollary for lower bounding function R where R1, Rn+1 are now non-decreasing functions.
Corollary A.3 (Marginal RCPS, monotonic non-decreasing case). Similar to the setting in Theo- rem A.1, let R R R. 1,..., n a be exchangeable functions, where R&(t) is non-decreasing in t. Also, take g: R + where g(x) is non-decreasing in x. Further assume that g o R4 is right-continuous, and
inf (Ra(())) 2 0, sup ((,g(R((()) C 7 almost surely.
(18)
For any 7 S. 0, define the random variable T(r,g) as
T(1g) = inf t: ((a((t)) (7) )
(19)
where define inf co. Then Blg Ba417((7 2
13

---

Under review as a conference paper at ICLR 2022
Proof. Let
a+1
g' inf
Σ
g (R) ?
(20)
n +
Since inf; g ((,()t)) 2 0, sup, ((R,(t)) > C 7/ T (r: and T(,, g) are both well-defined almost
surely. Since inf, (R,()))))))))))))))))))))))))( 2 0,
1
((,(tt) 21 27 n+l Σ 2()()))
(21)
Thus, g) S g) Since (t), is non-decreasing
Elg R (T( 9)) Elg o R (T')(TT))))))
(22)
Let Ey be the unordered set (bag) of { Rx+1]. Then T (1::g) is a function Ey, and is a constant conditional on Ey. Exchangeability of R; and figh-cootinuity of R. imply
a+1
Elg o IT Eyl
Σ go RT (76 27.
(23)
The proof is completed by taking the expectation over F and then applying Eq. (22).
We now prove our main theorem.
Proof. W.l.o.g. let us the flip signs of our non-confornity measures such that
-F S.) -F(a)):==(aaaee MFP(a, 2,4) == max (FP(2, (.53):=max(FF..F9..
(24)
and Tg. 5k.5 are instead defined via inf.
We are given that the sets S are nested, and is clear from its definition that FP non-decreasing for S C Sj. Since the ranking of S) is consistent with that of -|S] and monotonically non-increasing, MFP is therefore also monotonically non-increasing in t.
We prove T3 first.
Since B is constrained to be finite, we have that sup, MFP(,, 2,0) < B <<a oo. Furthermore, since -F(X,, St.) is upper-bounder by assumption, we have that inf, MFP Z,t) = < k E R>o-
Finally, as evident from its definition in Eq. (24), MFP 2,t) right-continuous. Let L,(t)
MFP(X,, Z,, f) and g(x) = x. We can then directly apply Corollary A.2 to obtain
EIMPP(X.+1, 2n+1, Tx) S k.
(25)
The proof for Tę is completed by the fact that MFP(X,,4 +1 11 Tx) 2 FP Swt1ig) condi- tioned on (X Tk.8-
We proceed similarly for Tk.6-
Let (,( = 1/MFP (z. 2,1) kJ. Since MFP is non-increasing and right-continuous, (((() is non-decreasing and right-continuout Let =
(0,1) 1). By the same argument as before concerning MFP, and from the fact that (t) E 10, we can apply Corollary A.3 to get
E (MPP(XX.+ Zn+i, Tr.6) < k}] = P(MFP(X..+) Zo+i, 1 TR.8) S k) 2 -
(26)
This gives P(MFP(XX Zn41, Tk.s) < k) Z 1-5. The proof for Th is then completed by the fact that MFP(X.+H) (x,+1, Z Tk,6) 2 FP 1 conditioned on F(X,, +1, Snt1,) & Tk.s- n
14

---

Under review as a conference paper at ICLR 2022
A.3 PROOF OF PROPOSITION 4.6
Proof. By definition, we have F(X Co (Xx+1; To)) S To where is placeholder for l or k. By Theorem 4.3, we can then conclude that
Ci, S
(27)
and
P(FP(Zn+1,,C.d
T2,6)) 1 k) S Tk,6) 2 21-6.
(28)
Finally, S C S' then ye E = ye E S' for any E 2 C y. Since the candidate sets are nested,
S < S - TPP(2, TP'
(29)
Thus picking the biggest candidate set maximizes the TPP for given Z = as well as its expectation over random Z, i... the TPR.
B CONFORMAL COVERAGE RESULTS
Task
TPR
Avg. FP
Avg. Size
In-silico screening
97.2
63.6
86.6
Object detection
96.1
32.4
38.2
Entity extraction
75.0
0.77
2.31
Table B.I: I: Outer Sets results applied at coverage level 1 = 0.90. Note that since some examples do not have any positives, full coverage in the typical sense isn' 't always achievable.
C IMPLEMENTATION AND DATASET DETAILS
Dataset
Input
# Examples
# Negatives
# Positives
% Empty
In-silico screening
SMILES
5,000
85 (50-97)
15 (3-50)
0.0
Object detection
Image
3,000
96 (89-98)
(2-11))
1.1
Entity extraction
Text
3,453
99 (97-100)
1 (0-3)
20.2
Table C.I: Dataset statistics (test split). Numbers are reported with respect to the top B = 100 candidates per example. The median number of positives and negatives per example is given, in addition to their 16th and 84th percentiles. Examples with no positives ([2) = 0) are treated as empty.
In-silico screening. We construct molecular property screening task using the ChEMBL dataset (see Mayr et al., 2018). Given a specified constraint such "is active for property but not property B," want to retrieve at least one molecule from given set of candidates that satisfies this constraint. The input for each molecule its SMILES string, notational format that specifies its molecular structure. The motivation of this task is to simulate in-silico screening for drug discovery, where it is often the case where chemists are searching for a new molecule that satisfies several constraints (such as toxicity and efficacy limits), out of pool of many possible candidates.
We split the ChEMBL dataset into a 60-20-20 split of molecules, where 60% of molecules are separated into train set, 20% into a validation set, and 20% into test set. Next, we take all properties that have at least 50 positive and negative examples (to avoid highly imbalanced properties). Of these properties, we take all N choose K combinations that have at least 100 molecules with all K properties labelled (ChEMBL has many missing values), We set to 2. For each combination, we randomly sample assignment for each property (i.e., factive, inactive] ). We discard combinations for which more than 90% of labeled molecules satisfy the constraint. We keep 5000 combinations for the test set, 767 for validation, and 4375 for training. The molecules for each of the combinations only sourced from their respective splits (i.c., molecular candidates for constraints in the property combination validation split only come from the molecule validation split). Therefore, inference
15

---

Under review as a conference paper at ICLR 2022
time, given combination we have never seen before, on molecules have never seen before, must try to retrieve at least one molecule that has the desired combination assignment.
Our directed Message Passing Neural Network (MPNN) is implemented using the chemprop repos- itory (Yang et al., 2019). The MPNN model uses graph convolutions learn a deep molecular representation, that is shared across property predictions. Each property value (active/inactive) is pre- dicted using an independent classifier head. The final prediction is based on an ensemble of models, trained with different random seeds. Given combination assignment (Z1 21. Ze 2k.), we compute the joint likelihood independently, i.e.,
po 11 21, Z* = = II po Po = 22).
Object detection. As discussed in $5, we use the MS-COCO dataset (Lin et al., 2014) to evaluate our conformal object detection. MS-COCO consists of images of complex everyday scenes containing 80 object categories (such as person, bicycle, dog, car, etc.), multiple of which may be contained in any given example. Since the official test set is hidden, we use the 5k examples from the development set and randomly partition them into sets of size 1,. 1k, and 3k for calibration, validation, and testing, respectively. The EfficientDet model (Tan et al., 2020)* for extracting bounding boxes uses a pipeline of three neural networks to extract deep features, and then predict candidates. The model also uses a non-maximum suppression (NMS) post-processing step to reduce the total number of predictions by keeping only the one with the maximum score across highly overlapping prediction boxes. We merge the predictions of all classes into a unified set, where each element is a tuple of (class, bounding box). This means that multiple class predictions can be included for the same bounding box (i.e., there is class uncertainty), and multiple bounding boxes can be found for the same class (i.e., there are multiple objects in one image). We define true positives as predictions that have intersection over union (IoU) value > 0.5 with gold bounding box annotation, and that match the annotation's 's class.
Entity extraction. Entity extraction is a popular task in natural language processing. Given a sentence, such as "Barack Obama was born in Hawaii"" the goal is identify and classify all named entities that appear-i.e., ("Barack Obama", Person) and ("Hawaii", Location). We use the CoNLL NER dataset (Tjong Kim Sang and De Meulder, 2003), and extract 1 examples for calibration out of the 3.3k development set, and report test results on the 3.5k test set. For our base model, we the entity extraction module of PURE (Zhong and Chen, 2021), that predicts span scores with a classifier head on top of Albert-base (Lan et al., 2020) contextual embeddings. The classification head has two non-linear layers and uses the learned contextual embeddings of the span start and end tokens, concatenated with a learned span width embedding. We train the model on the training set of the CoNLL NER dataset. We use the official code repository" and the following parameters: le- - 5 learning rate, 5e 4 task learning rate, 32 train batch size, and 100 context window. Similar to our object detection task, we treat exact span predictions of the correct category as true positives, and any other entity predictions as false positives. As illustrated in Table C.I, a fairly large number of sentences do not contain any entities at all, while other sentences may contain several.
D PRACTICAL CONSIDERATIONS
In this section we address a number of practical considerations for our FP-CP method.
D.1 CHOOSING SUITABLE k:
An outstanding question practitioner faces is how to choose the value of k for k-FP and (k, 8)-FP objectives. The value of k in our method has a reliable and easy interpretation: it is the total number of incorrect answers. For many tasks, such as in-silico screening, there is a direct relation between the number of noisy predictions (e.g., failed experiments conducted during wet-lab validation) and total "wasted" cost. Therefore, for example, given some approximate budget Q and cost per noisy prediction c, a reasonable approach is to then set k zs Q/c. Of course, the advantage of our approach is that the user may set whatever they wish-this might change based on their needs.
D.2 CHOOSING BETWEEN F-FWER AND FDR CONTROL
A related question to D.I is when to target F-FWER (i.e., our k-FP and (k, 8)-FP objectives) or FDR (c.g., using Angelopoulos et al. (2021a)). This choice is well discussed in the multilple testing
*We use if ff__efficienteet_22 from httmm/httt:///ghh// wttpiithu.coooooeoeeeeeeeee www./oon//wio.oe wttthh//sfficiienneeee/eeee/eeee
'https: thwb. httpgg/tt.....ooeeeeenooooooooo/ PURK.
16

---

Under review as a conference paper at ICLR 2022
literature (Lehmann and Romano, 2005; Romano and Wolf, 2007; Gold et al., 2009). An important aspeet to consider is the size of the label space y. natural rate of true and false positives, and the efficiency of the base model at separating true positives from false positives. When the total number of true positives is large and |>] is large then is reasonable to control the FDR. If, however, the natural rate of true positives is low, they are not well separated from false positives, then the FDR can be quite high and hard to control, especially for smaller prediction sets (as the ratio of positive to negative labels can be quickly driven down even with the addition of only few false positives). As intuition illustration, suppose for a given example there is one true positive that is ranked 10th by the base model. For many applications, 10 total predictions (with false positives) not overly burdensome. However, the lowest FDR cutoff that allows for this positive to be discoverable is 0.9 (which, for other examples, may allow for hundreds of false positives- an outcome which may not be so desirable for some applications, even given a high number of accompanying true positives). To satisfy a lower FDR rate, the algorithm must output an empty set (with FDR = 0). This remains true even if there a few (but not many) other true positives: for instance, in the previous example, if predictions 10-20 were also all true positives then the lowest FDR is still only 0.5 --5cciffynn a FDR tolerances any lower than this would force empty set prediction.
D.3 LEARNING MORE EXPRESSIVE SET FUNCTIONS
Our choice of DeepSets model is motivated by its property of being a universal approximator for continuous set functions. Of course, its realized accuracy depends on its exact parameterization and optimization. In terms of input features, in $4.2, we chose a simplistic 6(I yc) for two reasons: (I) we view it's simplicity probabilities, or other scalar conformity scores, that most out-of-the-bol methods provide into a general framework without having do any more work for providing additional features), and (2) it is easy to train this discard potentially helpful information about the underlying input z, and any dependencies between labels ye and y²- For example. if ye and y². are mutually exclusive, then the number of false positives if both are included in S has to be least 1. Using more expressive & that able to capture and take advantage of this sort of side information about r and ye is subject for future work.
advantage (practitioners can simply plug-in individual multi-label
model on smaller amounts of data. This approach, however, can
D.4 CONSTRUCTING
CANDIDATE SETS
Our careful construction of nested prediction sets that have bounded, non-decreasing, and right- continuous risks is key to our calibration procedure. It is, however, limited by the underlying ranking of labels Ve E y by the individual likelihood model po po(ye E Z x). In theory, the set function F may be able to identify higher quality outputs sets S E 2 by jointly considering all of the included elements (rather than ranking them one-by-one). That said, the search process over 2 expensive, and the FP risk is no longer non-decreasing, which necessitates more involved calibration methods that can account for non-monotonic risks, such as that of Angelopoulos et al. (2021a)). Nevertheless, this is promising subject for future work, and one that can potentially be combined with efficient search or candidate space pruning methods (e.g., such as in Fisch et al. (2021)).
D.5 FAILURE CASES OF GREEDY OUTPUT SELECTION
In $4.4 we greedily select the largest candidate set that passes our filter threshold. A downside of this approach is that it may include more false positives than necessary (i.c., to achieve the same TPR). Ideally, would be able to follow the oracle strategy in returning the smallest set with the highest true positive proportion. This would make our predictions efficient, in the sense that we are not including more false positives than necessary (even if the total number is still < k). A reasonable choice to then choose S,- where j = arg max; |S - F(x. Sz); but this can be sub-optimal if F not accurate, which motivates our greedy strategy. Nevertheless, non-greedy set selection may be more efficient if F is indeed accurate- can be tested on a validation set.
17


Reviews:
[{"review_id": "u6W9k_E9Ug4", "reviewer": "Reviewer_KRhW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n\nThe method is well-motivated from a practical standpoint. It is also well-grounded in theory without burdensome assumptions.\n\n## Weaknesses\n\nThe main issue has to do with clarity. The writing is difficult to follow, almost always unnecessarily so.\n\n1. *Inconsistent or ill-defined notations*: The following is not meant to be an exhaustive list.\n\n- On p. 1, $(X_i, Z_i) \\in \\mathcal{X} \\times 2^{\\mathcal{Y}}$, but $\\mathcal{Y}$ has not been defined.\n- Both $Z_{n+1}$ and $\\mathcal{Z}_{n+1}$ as used. As far as I can see, they represent the same quantity.\n- Similarly, both $S_{i}$ and $\\mathcal{S}_{i}$ are in use.\n- $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$.\n- 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}$.\n- 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.\n- The same comment applies to the remark about $k$ in Top-$k$.\n- $t^*$ and $T_*$ appear to have the same meaning.\n- Is $\\operatorname{SSFD}_k$ in Eq. (14) the same as $\\operatorname{WCSS}$ in Figures 2 and 3?\n\n2. 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)).\n\n3. 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.\n\n4. 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.\n\n5. Overall, I feel like the current version of the manuscript does the bare minimum when it comes to explaining the intuition underlying the approach.\n\n## Minor\n- (p. 1. The 1st line of Section 1) instead of single prediction -> instead of a single prediction\n- (p. 2. The 4th line after Eq. (2)) Spell out the initialisms.\n- (p. 5, The 1st line after Eq. (8)) What are enc and dec?\n- (p. 6. Theorem 4.3) $\\tilde{\\mathcal{F}}(X_{n+1}, \\mathcal{S}_{n+1, j}) \\leq T_k$ or $T_{k, \\delta}$, rather?\n- (p. 7. **In-silico screening for drug discovery**) I think the correct usage places the comma before the end quote and not after.\n- (p. 7. **Entity extraction**) The letter $l$ has already been used earlier in the text.\n- (p. 9. The 2nd line of Section 7) can be a critical in -> can be critical in\n- (Appendix) Please check the punctuations in display equations.\n- (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)?\n- (p. 14) w.l.o.g. -> W.l.o.g.\n- (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$\n- (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}$.\n\n## Additional Comments\n\nI 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "fSes1Wo7wBK", "reviewer": "Reviewer_2ZTR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strong points:**\n* The framing of the problem is natural, and I like it (i.e., Sec 4.1 onwards).\n* I like the idea of using the deep sets methodology.\n* The three real-world data sets seem reasonably interesting / well-motivated.\n* The paper is a pleasure to read.\n\n**Weak points:**\n* Experimental evaluation:\n    * 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?\n    * 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.\n    * 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$.\n\n* 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.\n\n**Questions:** see my \"Weak points\" and \"Additional feedback\" sections.\n\n**Additional feedback:**\n* You seem to have switched between $S$ and $\\mathcal S$ to denote a set on page 6.\n* On page 6 -- \"beach search\" $\\rightarrow$ \"beam search\".\n* It's hard to tell what exactly is going on in the top row of Fig 2.\n* Part (c) of Figs 2,3 -- TDR appears to asymptote at 0.8.  Why?\n* I may have missed it, but how big is $\\mathcal Z$ in each of the experiments?\n* How do you set any tuning parameters for the deep sets neural network?  Doesn't this require additional data?\n* 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_paper": "**Summary:**\n* 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.\n* A few calculations/results are worked out showing that the method works as advertised (i.e., TDR maximized, FDR controlled).\n* 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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "aybXyTXPVrC", "reviewer": "Reviewer_yMiK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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.\n\nStill 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?\n\nI 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.\n\nAs for $\\Psi$ (eq. 8), the authors stated that they use labeled sets sampled from auxiliary training data. Can you elaborate more on that?\n\nRegarding 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).\n\nExperiments: 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.\n\nLastly, please include in the Supplementary Material more details on the data sets used in the experiments.\n", "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.", "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).\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MmccEWW5_LS", "reviewer": "Reviewer_dWtw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n--- 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?\n\n--- A side notes about some typos: \na. 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_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.", "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.\n\n**Update after rebuttal**\n\nI 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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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