Probably Approximately Precision and Recall Learning
Authors: Lee Cohen
Yishay Mansour
Shay Moran
Han Shao
Venue: NeurIPS 2025 poster ()
Keywords: PAC learning
multi-label learning
sample complexity
Primary area: theory
TL;DR: We study learning set functions under one-sided feedback in the PAC learning framework.

Abstract: *Precision* and *Recall* are fundamental metrics in machine learning tasks where both accurate predictions and comprehensive coverage are essential, such as in multi-label learning, language generation, medical studies, and recommender systems. 
A key challenge in these settings is the prevalence of one-sided feedback, where only positive examples are observed during training—e.g., in multi-label tasks like tagging people in Facebook photos, we may observe only a few tagged individuals, without knowing who else appears in the image. To address learning under such partial feedback, we introduce a Probably Approximately Correct (PAC) framework in which hypotheses are set functions that map each input to a set of labels, extending beyond single-label predictions and generalizing classical binary, multi-class, and multi-label models. Our results reveal sharp statistical and algorithmic separations from standard settings: classical methods such as Empirical Risk Minimization provably fail, even for simple hypothesis classes. We develop new algorithms that learn from positive data alone, achieving optimal sample complexity in the realizable case, and establishing multiplicative—rather than additive—approximation guarantees in the agnostic case, where achieving additive regret is impossible.

Probably Approximately Precision and Recall Learning
Lee Cohen" Stanford Leecohenes@gmal..com
Yishay Mansour
Tel Aviv University and Google Research mansour yishay@gmail com
Shay Moran Technion and Google Research smoran@technion ac. il
Han Shao
University of Maryland, College Park hanshaoCumd. edu
Abstract
Precision and Recall are fundamental metrics in machine learning tasks where both accurate predictions and comprehensive coverage essential, such as in multi-label learning, language generation, medical studies, and recommender systems. A key challenge these settings the prevalence of one-sided feedback, where only positive examples are observed during training-e.. tasks like tagging people in Facebook photos, we may observe only a few tagged individuals, without knowing who else appears in the image. To address learning under such partial feedback, we introduce a Probably Approximately Correct (PAC) framework in which hypotheses are set functions that map each input to a set of items, extending beyond single-label predictions and generalizing classical binary, multi-class, and multi-label models. Our results reveal sharp statistical and algorithmic separations from standard settings: classical methods such as Empirical Risk Minimization provably fail, even for simple hypothesis classes. We develop new algorithms that learn from positive data alone, achieving optimal sample complexity in the realizable case, and establishing multiplicative-raatee than additive additive-approxinee approxmmaiinn guarantees the agnostic case, where achieving additive regret is impossible.
in multi-label
Introduction
Precision and Recall are fundamental metrics in many machine learning applications, including multi- label learning, medical studies, generative models, information retrieval, and recommender systems, where the goal is to learn set for each input and both accurate prediction and comprehensive coverage are critical. For example, in multi-label learning-wlee where each input may correspond to multiple labels (e.g., image containing multiple objects a group photo containing multiple tho objective is to return the complete set of labels associated with each input. Recommender systems also rely heavily on precision and recall; for instance, Netflix aims recommend a list of shows that includes all those a user would enjoy and excludes those they would not. In medical studies, precision, called positive predictive value (PPV), and recall, called sensitivity. are key performance metrics. For instance, if a test predicts that 10 patients have a condition and 9 truly have it, its PPV (precision) is 90%. 5 patients actually have the condition and the correctly identifies of them, its sensitivity (recall) is 80%. In language identification and generation in the limit Gold (1967);
Authors ordered alphahetically. Work done while at Harvard.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Kleinberg & Mullainathan (2024); Kalavasis et al. (2024), hallucinatiin denotes failure of precision, where the model produces strings outside the true language, whereas mode collapse denotes failure of recall, where the model's outputs become so constrained that valid, previously unseen strings are never generated.
A critical aspect of designing such systems is balancing two key metries:
Precision the proportion of output items that are in the ground-truth set. Low precision loss means that most output items are correct.
Recall the proportion of ground -ruth items that are included in the output. Low recall loss means the system captures most of the correct items.
Precision and recall are often at odds. Increasing the size of output set can improve recall but may reduce precision. In an ideal scenario, we might consider a full information model where, for each input in the training data, the algorithm has access to the set of all the ground-truth items. This setup implicitly includes negative examples, as items not the set are known to be incorrect. At test time, the algorithm would then predict a set of items for each given input. Such a setting aligns well with the standard Probably Approximately Correct (PAC) framework Valiant (1984), allowing us to apply standard PAC solutions (e.g., Empirical Risk Minimization).
However, the assumption of full information often unrealistic in many applications. In real-worke scenarios, we typically observe only small fraction of the ground ground-truth -ruth items (e.g., some objects in an image) during training, with no explicit information about unobserved items (e.g.. which objects are not in the image). This situation is better characterized as partial-infon -inrrmaiinooonooionn model. For instance, on Facebook, for each photo in the training data, we might only know some of the tagged individuals, without knowing whether any untagged person appears in the photo or not. To formalize this setting, we consider a simple abstraction: during training. for each input, we observe only a single item sampled uniformly at random from its ground-truth set. At test time, given random input, the model is expected to return the full set of associated items, not just one.
standard practice in learning theory, given an input space X' and a label space ), we consider a hypothesis class H. Each hypothesis a set function g : X' + 2² that maps each input in X' to a set of labels in y. For example, in the context of multi-label learning, inputs may be images and items may be objects; a hypothesis maps an image to the set of objects contains. Our goal is to find set function that minimizes both precision and recall losses. These losses are defined with respect to a target hypothesis g grrger, which captures the ground-trume label sets, using the standard counting measure:
Following
[g(x)
(x)) [g(z)]
[gg (xgr)) (x) \ g(x)) Igtarper (I)
gprecision (g) = EEgND
and grecall (reaal(g) == E
where DD denotes the distribution over inputs. Precision and recall are equal to minus the precision and recall losses, respectively. Binary and multiclass PAC learning can be viewed as special cases of our model, where we restricted the set size to be 1. Note that, for each given x. we adopt the standard counting measure to quantify the difference between (zx) and g (xr). While other measures are possible, is often challenging to define more sophisticated alternatives a principled and intuitive way. To the best of our knowledge, the only generalization of precision and recall beyond counting measure proposed by Sajjadi et al. (2018), though the resulting notions are relatively complex. Hence, we will be focusing on the counting measure in this paper and leave a more general notion of precision and recall as a open question.
We distinguish between two settings- realizable and agnostic. In the realizable setting, we assume the target hypothesis graget is in the class H. and, aim to find a hypothesis with small precision and recall losses. In the agnostic setting, we do not assume that perfect hypothesis is in the class. Instead, we aim to compete with the "best" hypothesis in the class, acknowledging that some error is unavoidable. In the context of the agnostic setting, defining the "best" hypothesis is subtle. One hypothesis might have high precision but low recall, while another has the opposite. Depending on the application 'ss needs, one may prefer higher precision over recall or vice versa.
This naturally leads us to the concept of Pareto-loss objective, which captures the trade-offs between precision and recall along the Pareto frontier.3 3
'The term "Pareto" originates from Vilfredo Pareto, an economist who observed that certain distributions followed pattern where improvements in one dimension often involved trade-off's in another. The concept

---

Namely, the "best" hypotheses are on Pareto frontier, which is the set of hypotheses where no other hypotheses are better in both precision and recall simultaneously (see, e.g., Figure 1). Here, we try. given desired precision and recall losses parameters (p)r) to return a hypothesis whose precision and recall losses (p', r") satisfy p' S p and r' S r. For example, one might aim to optimize precision while keeping recall below specific threshold (e.g., at most 0.5).
Our goal is design algorithms whose sample complexity is polynomial in the log size of the class and the inverses of the aceuracy and confidence parameters, and in some cases, on the maximum size of the output (which is ar- guably small in certain applications). We focus on finite hypothesis classes and aim for sample complexity bounds that depend logarithmically. rather than linearly, on the size of the class. This goal is motivated by standard sam-
Recall loss
ple complexity bounds PAC learning and partieularly relevant when training data is costly to obtain, as is often the case with human-provided feedback." 4
Precision loss
Our learning problem is significantly more challenging than standard supervised learning tasks due to the absence of negative examples that is, input-label pairs where the label not in the ground-truth set. We observe only pos- itive examples, making it impossible to estimate precision loss directly: without knowing which labels are incorrect, we cannot determine how many incorrect labels a hypoth- esis might output. This limitation undermines standard supervised learning approaches, which rely on access to both positive and negative examples.
Figure 1: Example of hypotheses with varying precision and recall losses. Each point is a distinct hypothesis, with red points on the Pareto frontier, showing op- timal trade-off's between precision and recall losses. The empty set function (which always return the empty set) al- ways achieves zero precision loss (but has no guarantee on the recall loss), while the complete set function (which always return the entire label space y for any given input æ)) always achieves zero recall loss (but has no guarantee on the precision loss).
In standard supervised learning, a classical solution known as Empirical Risk Minimization (ERM) involves finding hypothesis that best fits the data by minimizing the average loss over all observed examples. However, in our case, the absence of negative examples means that ERM cannot be applied effectively, as there no way to determine how well hypothesis avoids incorrect labels. For example, the complete set function (where g(x) = y outputs all items) is consistent with every training set, since we have no negative examples to contradict it. However, such hypothesis might have poor precision. Without negative examples the training set, any hypothesis that covers all observed positive examples appears equally valid, even if it recommends many irrelevant items and incurs a high precision loss. The failure of the ERM principle is not unique to our learning problem; it also occurs in other learning problems, such multi-class classification Daniely et al. (2015), density estimation Devroye & Lugosi (2001); Bousquet et al. (2019), and partial concept learning Alon et al. (2022).
In fact, it is not just that ERM would fail; we provide an example in which two hypotheses have nearly the same recall loss but very different precision losses, making it impossible to determine which hypothesis has better precision loss based solely on the training data (see Example I for more details). These challenges necessitate novel approaches to learning and evaluating hypotheses.
Our Contributions
Learning Model: We propose a learning model that operates under partial information, where the algorithm observes only positive examples. For each input drawn from unknown distribution D, observes one label sampled uniformly random from its ground-truth set. This model reflects
of Pareto frontier, inspired by this principle, represents optimal trade-offs between competing objectives. Our Pareto loss captures the balance between precision and recall, aiming to improve both while acknowledging the trade-off.
*While it would interesting to explore infinite hypothesis classes and characterize them via combinatorial measure in the style of VC dimension, the findings in Lechner & Ben-David (2024) suggest that such a dimension may not exist in this setting. We leave this as an intriguing open question, as addressing it falls beyond the scope of this work, which focuses the finite case setting that is already challenging.
3

---

real-world constraints and is more practical than assuming access to complete ground ground-truth set as done in multi-label learning.
Realizable Setting: We design algorithms that, given sample of size
log Log((HH/0)
achieve recall and precision losses of at most e with probability least 1 8. We propose two distinct approaches to achieve this goal: the first circumvents the challenge of estimating precision by minimizing an appropriate surrogate loss, while the second takes more intuitive approach inspired by the maximum likelihood principle Shalev-Shward & Ben-David (2014). In essence, this second algorithm, when presented with two hypotheses consistent with the data, prioritizes the one with smaller output sizes in a suitably quantified sense.
Agnostic Setting: We demonstrate that achieving a vanishing additive error, as is standard in learning theory, is impossible in this setting by providing lower bounds on the sum of precision and recall losses, with multiplicative factors greater than 1. In the other direction, we show that constant multiplicative factor guarantees are indeed achievable by adapting our realizable setting algorithms to the agnostic case. Closing the gap between our upper and lower bounds on the best achievable multiplicative factor (5 vs. 1.05) remains an open question. For the Pareto-loss case, we establish both upper and lower bounds for the following question: Given that there exists a hypothesis in the class with precision and recall losses r), which guarantee pairs (p', rr) are achievable? Finally, we pose open questions about the optimal factors in the agnostic setting.
Related Work Precision and recall are natural and standard metrics used broadly in machine learning, spanning applications from binary classification (Juba & Le, 2019; Diochnos & Trafalis, 2021), multi-class classification (Grandini et al., 2020), regression (Torgo & Ribeiro, 2009), and time series (Tatbul et al., 2018) to information retrieval (Arora et al., 2016) and generative models (Sajjadi et a0, Beyond precision-recall, another related metric- the area under the ROC curve (AUC)- has also been extensively studied in the history of binary classification (Cortes & Mohri, 2003, 2004; Rosset, 2004; Agarwal al., 2005), with a focus on generalization. Our work, however, studies different problem of multi-label learning where the goal is to output a list of labels for each input. In the context of recommender systems, recommending list of items has also been addressed in cascading bandits (K (Kveton et al., 2015). However, while our objective is to identify the items that each input likes, their focus is on learning the top K items that are liked by most inputs. Another feature of our learning problem is that we can only learn from positive examples. PAC learning for binary classification from positive examples has been studied in the literature (Denis, 1998; De Comité et al., 1999; Letouzey et al., 2000; Bekker & Davis, 2020).
Multi-label learning (McCallum, 1999; Schapire & Singer, 2000) has been an area of study in machine learning, with various, primarily experimental approaches (see, e.g., (Elisseeff & Weston, 2001; Petterson & Cactano, 2011; Kapoor et al., 2012) and (Zhang & Zhou, 2014; Bogatinovski 2022) for surveys). In multi-label learning, the training set consists of examples, each associated with multiple labels rather than just one. The goal is train a model that can learn the relationships between the features of each example and all its labels. At test time, the learner predicts a list of labels for new examples, aiming to capture all the relevant labels, rather than just a single one.
al..
Some works have examined multi-label learning from a theoretical standpoint, focusing in particular on the Bayes consistency of surrogate losses. Bayes-consistency in multi-label learning ensures that minimizing a surrogate loss also leads to minimizing the true target loss, which is crucial in multi-label settings where optimizing the actual loss is often computationally infeasible it is non- convex, discrete losses in multi-label settings. Initiated by Gao & Zhou (201 1) who first addressed Bayes-consistency for Hamming and ranking losses, showing binary relevance's 's consistency with Hamming loss but highlighting ranking loss difficulties. Extensions include rank-base metrics like precision @ and recall @ k (Menon al., 2019), which are loss functions defined under the constraint that the number of labels predicted by the model is limited to k. Recently, Mao et al. (2024) established H -coosisttency bounds for multi-labed learning, offering stronger guarantees than coyes-consistency by providing non-an -symppttiooicc guarantees that apply to finite number of samples. Our model is inherently more challenging than traditional multi-label learning because our training set consists of examples, each associated with only single correct label rather than all possible correct labels, with no negative feedback. Yet, at test time, the learner still needs to predict a list of relevant labels for new examples.
4

---

2 Model
As is standard in learning theory, we assume hypothesis class H of set functions, our goal is to design algorithms whose sample complexity is polynomial in the log size of the class and the inverses of the accuracy and confidence parameters. More specifically, we given input space X, label space y and a hypothesis class H. in which every hypothesis h X' + 2 maps each æ: to a set of labels in Vi We denote an unknown target hypothesis glaget The training set consists of a sequence (Ii, 04 oi) with (I; v;) E X' x y. The inputs ...... Zm are drawn IID from unknown distribution D. For each input Vi, random label v; is drawn uniformly from its ground-truth set, , ( defined by the target hypothesis. The algorithm then outputs hypothesis g and the goal is to minimize the expected precision and recall losses:
gimpptt (x) \. target (x)
gurecision
goupptt) BEND (g
Tepiatur xx)
1 (xx) \ qupprr (x:)
grecall outpu = BEND
Tigitsn (x)
where for any hypothesis 9, (x)( = !9(x)| denotes the set size of g at
We focus on designing learning rules that can compete with the "best" hypothesis in H. Specifically, if there is hypothesis E H with precision and recall losses and r, respectively, can we output a hypothesis g nd whose precision and recall losses are comparable to p and r? To answer this question we consider two natural metrics: scalar loss and Pareto loss.
Scalar-Loss Objective
The scalar loss is defined as the average of precision and recall losses
escalar s + grecal((g)
For any a > O, we say a-apppoximate optimal scalar loss is achievable if there exists polynomial P such that, for any finite hypothesis class H. there is an algorithm such that the following holds: For any e, 5 >> 0 and any distribution DD if A is given an IID training set of size P(log (H) 1/s, 1/8), with probability at least 6, it outputs a hypothesis with scalar loss satisfying
pscalar (g ourpory S a min pscalar (g) + gEH
Our primary focus is on finite hypothesis classes, where we discuss dependencies on the cardinality of the hypothesis class, is common in standard learning theory. We emphasize that the average loss a natural way to combine precision and recall losses. Other scalarizations, such as the Fl score, are also possible. Several results in this paper extend to alternative definitions of scalar loss functions, which we discuss in the Discussion section.
Pareto-Loss Objective Let p.p', r,r' E [0. 1]. We write (p.r) = (p',r') to denote the following statement: there exists polynomial such that, for any finite hypothesis class H. there is an algorithm A such that the following holds: If D is distribution for which there exists hypothesis in with precision and recall losses (p. r). then for any E, > 0, if is given p, r and an IID training set of size P(log] H. 1/e, 1/5), with probability at least 1 - 8, it outputs hypothesis with precision and recall losses at most p' + e and +
We are asking the following a question for each of our losses:
What the smallest a such that a-approximate optimal scalar loss is achievable? Given p, E [0, 1], which pairs (//rr)) satisfy (p,r) - (p',r')²
This hypothesis learning problem is considerably more challenging than standard supervised learning. If the entire ground-truth set (x;)) were observed in the training set rather than a random label
Wa U (r:)), the task would reduce standard supervised learning. However, observing
only a random label prevents an unbiased estimate of precision loss, complicating the problem. We demonstrate it in the following example.
'The results can be generalized to any weighted sum of precision and recall losses via grecission (g) + Wy grealll (g) & 2 max(w1, w2) g (g).
AAttallyy algorithms only requires the knowledge of r.
5

---

Example 1. In Fig 2, the target hypothesis associates input x; with large number r. of labels. Our hypothesis class contains two hypotheses, each predicting exactly one label for input 24. In the red hypothesis 91, the predicted label is always true positive (i.e., it belongs to the ground-truth set), while the blue hypothesis 92, the predicted label is a false positive (i.e., it is not the ground-truth set). Both hypotheses incur high recall loss: gecall (91) a-1 and grecall (02) = 1. However, they differ significantly in precision loss: 91 has a precision loss of as always predicts a correct label, whereas 92 has a precision loss of 1, as it always predicts incorrect label. Since is large, the probability of observing either predicted label in the training data very low, making it impossible distinguish between these two hypotheses despite their drastically different precision losses.
21
U22
U3
Up
w
Figure 2: The target hypothesis (black) outputs g glmgdl (x+) = fuI,..., .., Un where n huge. The hypothesis In (red) outputs only label in ( while d2 (blue) outputs only one label u' $ grrge (I;).
One might argue that the issue in the above example arises from the large size of the ground-truth set; however, we will later show that even when the ground-truth set has small size, accurately estimating and optimizing precision remains impossible.
We emphasize that, unlike in other supervised learning settings, such PAC learning, where minimizing empirical risk is often straightforward (e.g., by outputting any classifier that is consistent with the training set), here the learner only observes single label vs per input 24, rather than its entire ground-truth set. As result, minimizing empirical precision loss in this context is far from trivial. For instance, regardless of the ground-truth set, complete set function, which outputs the entire label space y for any input, is always consistent with the training data but can still incur high precision loss.
Main Results
The Realizable Setting We begin by presenting our results in the realizable setting, where the target hypothesis belongs to the hypothesis class H. In this case, there is no distinction between optimizing the scalar-loss objective and the Pareto-loss objective. We propose two new algorithms that achieve both the scalar-loss and Pareto-loss objectives: one based on maximum likelihood estimation, and the other on minimizing surrogate loss.
Theorem 1. In the realizable setting, there exist algorithms such that given an III) training set of with probubility at least 8, the output hypothesis gruput satisfies
size m 2 ( 1og(174168)
greaatl (g naspu Se, gorecision ( S
Since (wv $ g(x:)) is an unbiased estimate of the recall loss (g)all(g). any consistent hypothesis (i.e., hypothesis g with Em 1(v; & g(x;)) = 0) will have low recall loss. But ERM does not work as the training set contains only positive examples, and complete set function consistent with any training set but can incur high precision loss. Hence, the main challenge lies in minimizing the precision loss. Below are high-level descriptions of two algorithms designed to tackle this problem.
Algorithm 1: Maximum Likelihood. One of our proposed algorithms is based on the natural idea of maximum likelihood. At a high level, although multiple hypotheses may be consistent with the training set, for any observed input-label pair (æt, v.), if vs is contained in g(xx). the probability of observing this label is (x4))) when g is the target hypothesis. The maximum likelihood method
returns nuppat = arg max,EH gEH I 1g(x))( which is equivalent to returning the hypothesis with (a,)))

---

the minimum sum of log output sizes among all consistent hypotheses, i.e.
g gouput
arg min
Σ log(nn (x:4).
9:9 consistent
Consequently, we can rule out the complete set function, as its sum of log output size Ei log(nn (og(mg(z)) (2:)) is huge. Any consistent hypothesis will have low empirical recall loss by applying standard concentration inequality and thus, gresall (gampett is small and we only need show that the empirical precision loss is small. The main technical challenge in the analysis is how to connect precision loss with likelihood.
The other algorithm is more directly aligned with the scalar-loss objective. While we cannot obtain an unbiased estimate of the precision loss, and hence the scalar loss, we introduce surrogate loss that both upper- and lower-bounds the scalar loss within a constant multiplicative factor. Then we output hypothesis minimizing this surrogate loss.
Algorithm 2: Minimizing Surrogate Loss.
For any hypothesis 9, we define a vector Bg H x H + [0,1]b]
1
vgld = m
Un-f(((((( (o E g (2x) \ (x)))
Intuitively, (g gg") represents the fraction of correct labels that are output by g but not by g" in the counterfactual scenario where g is the target hypothesis. g is indeed the target hypothesis. then this quantity should be consistent with our training data, (g' g²) as vz(g g"), where ğ is the observed (empirical) hypothesis; i.e., the hypothesis in which every æ; is only associated with the random label 2 which is observed in the training set.
We then define metric du between two hypotheses 91 and Ø2 by
(91 || "gaale loo
Surprisingly, we show that d g) is a surrogate for the scalar loss, providing both lower and upper bounds on the scalar loss with a constant multiplicative factor.
The Agnostic Setting In the agnostic setting, we show in the next two theorems that it is impossible achieve an additive error for both scalar-loss and Pareto-loss objectives is standard in learning theory.
Theorem 2. There exists a class H = (91,9)) of two hypotheses, such that for any (possibly randomized improper) algorithmm, there exists a target hypothesis gaarget with bounded output set size (that is, there exists a constant C' such that (r (x)l S C for all x E X) and a data distribution DD with mingeM (gealar (g)) s.t. for any sample size m the expected (over the randomness of the algorithm) loss of the output g ouupat
with probability over the training set,
gscalarr (g cumpur)] 2 1.05 min( gacalar min(eecdaar (g)).
gEH
Theorem 3. There exists class H = {91,92) of two hypotheses, such that for any (possibly randomized improper) algorithm given the knowledge of (p,r) ( 4) there exists target hypothesis garger with bounded output set size and a data distribution D for which there exists hypothesis g¹ e with greall (g') 1/ and gprecision (gt) = 1s s.t. for any sample size >> with probability 1 over the training set, the expected (over the randomness of the algorithm) precision and recall losses of the output numpa satisfy
(T6:
12
E grecall
( (urpi)) >
E
gprecision (g outpar)
5
5
Remark 1. Hence the output hypothesis either suffers grecall (g (goupp >
1 grecalt (g") or
pprecision cutpue
23 gerecision (g'iiioonng)))) Thus (To }) A (7s + 0.01, + 0.01).
For any hypothesis g, it's precision loss at any input x is (x) and we only get a random
label (arstt)))))))))))) (x)). If we given the knowledge of the output size nguas (x) of the target
7

---

hypothesis, then we can obtain an unbiased estimate of the precision loss, i... ((x)). But the difficulty lies in that we don't know Rigurn (2)).
"googe (2) (g(()))
1(w
Based these two lower bounds, in the scalar-loss case, allow for multiplicative factor In the Pareto-loss case, we ask a more general question: which pairs of guarantees (p',r") are achievable, given that there exists hypothesis in the class with precision and recall losses r)? Since the recall loss is optimizable, for any given r, if there exists a hypothesis in the class with recall loss r, we can always achieve that recall loss. Therefore, we refine question as follows: given any p, r [0, 1]. what is the minimum precision loss p' such that (p.r) > (p',r)?
Since the recall is estimable, when we have algorithm achieving a-approximate scalar loss, we can first eliminate all hypotheses with recall loss higher than and then run this algorithm over the remaining hypotheses. Then we achieve (p, > (a(p + r),
Theorem 4. There exist an algorithm such that given an IID training set of size m 2 0 Ing (gg(1H//8) with probability at least 1 - 5, the output hypothesis grlupur satisfies
gocabar (g )urpur) I 5 min gocalar (g) E.
gEH
This implies that for any p.r E [0, 11. (p.r) (5(p+r).r).
This result is achieved using the same surrogate loss idea the realizable setting. However, in the agnostic setting, applying maximum likelihood directly no longer works. This is because it is possible that none of the hypotheses in the hypothesis class are consistent with the training set and thus all hypotheses have zero likelihood. Instead, we make some modifications adapt the maximum likelihood idea work for Pareto-loss objective.
As mentioned earlier, the maximum likelihood method is equivalent to returning the hypothesis with the minimum sum of log output sizes among all consistent hypotheses. Hence, it can be decomposed into two steps: minimizing the recall loss and then regulating by minimizing the sum of log output sizes. In the agnostic setting, given any r, we first find the set H. of all hypotheses in the hypothesis class with recall loss at most r + 2s, and then regulate by minimizing the sum of log truncated output sizes by returning
1
log Regg (24) A (ng(1s)
guupp
arg min max- OEA m xE(m]
ng (2x) A 4ng (x:)
g'E
where A b == min(a, b). The truncation plays important role here. Intuitively, let gf denote the hypothesis with precision and recall losses p and r, respectively. there exists an ø; such that ng (ara) is very large, minimizing the sum of log-untruncated output sizes will never return g². By applying truncation, we limit the effect of a single input with a very large output size.
As we can see, there is gap between the upper and lower bounds in the agnostic case, leaving an open question: What is the optimal multiplicative approximation factor a in the scalar case, and what is the optimal p' such that (p,r) + (p',r')
The Semi-Reallee Realizable Setting The results the agnostic setting fail to offer meaningful guarantees in certain natural scenarios, such as = O and r (i.e., when there exists a hypothesis that captures half of ground ground-truth labels without outputting any incorrect labels). We are therefore interested in the following question: whether (p 0)r) = (w' = 0,r' r)?
We propose algorithm with sample complexity depending output size of the target hypothesis and show that it is impossible to achieve zero precision loss with sample complexity independent of the target hypothesis's 's output set size.
As discussed previously, it's impossible for us to estimate the precision loss. However, we can still separate hypotheses with zero precision loss and non-zero precision loss if the the target hypothesis's output set size is bounded. If the precision loss of hypothesis at input x is 0, ie.,
(g(()) (arget (x))
(.((())))) n g (1rge((())
preeiiioon (g. x))
0,
(x)(
(x)
have
(g(x)) C g target (x))
pprecisiio (g.x)
n. (x) Mygunee (x)
Meguna (x))
Magina (x)
8

---

If the precision loss gprecision (g, is positive, we have
(1(z) n g(uness(()
gorecision (g, x)
B2 (z) ( Mgrron (x)
nigurgn (x)
nigingn (x)
La(a)nn (x)]
Hence, we can use the quantity Ez~D (2(2)) (2))- (2))
to separate hypotheses with zero and non-zero
precision loss, and it is estimable. For each hypothesis g. when the gap of this quantity between
[a(z))y (w)
hypothesis with zero precision loss and g is g. EEwD
EewD
>
(3r)
My (n()),n, uunge (ar)
then by obtaining - samples of æ, we can tell that g has nonzero precision loss. Let Ap be the
9.2 smallest gap of this quantity between hypotheses with zero and nonzero precision losses:
D
min g.
g.
>
Then we can have sample complexity dependent on this gap.
Theorem 5. There exists an algorithm such that if there exists a hypothesis g' E H with goveiision (g') O and greail (g') r, then given an IID) training set of size O log( Hl/0)) with probability 6, it outputs a hypothesis with gerecision (goupu)) = 0 and grecall (gouput) =
Ab
When the target hypothesis's output size niguan (z) bounded by C almost everywhere, we have
19(x)) O o ( (x)]
grrecision (g, x)
grrecision (g. x)
E
E
S IE
E
ng(2)) Tigar
Therefore, we have Dg.D >
This implies that when the target hypothesis has bounded output size, are able to find the hypothesis with zero precision loss. However, when the target hypothesis's output size becomes too large, we show that is impossible to achieve precision-recall of (O,
greciison
[g]
Theorem 6. There exists class H fgi, 92) ) of two hypotheses, for any > O and any (possibly randomized improper) algorithm A. there exists target hypothesis gearger and a data distribution 'D for which there exists hypothesis g H with goecisioo (g') 0 s.t. with probability 1 - 8 over the training set, the expected (over the randomness of the algorithm) precision and recall losses of the outpul goupue satisfy either E [grecall (g cmppr)) 2 miigge grecalt (g) (11) or E [gprecision (ampury ((1).
In the proof of the theorem, we construct a target hypothesis with output size much larger than the sample size m, as well as hypotheses 91 and g2 with output size In this setup, regardless of whether has perfect precision (i.c., the output of is subset of the ground-truth set) or very poor precision, we cannot distinguish between these two cases because we never observe a label in the output of being sampled. Therefore, the only way to achieve zero precision loss is to output the empty set function, which, however, results in a high recall loss.
Discussion
One of the main goals of this paper is to study the Pareto front of precision and recall, which reflected in our Pareto-loss objective. There are other scalar measures of predictive performance, the Fi and the F3 scores. F1 and F3 are direct functions of precision and recall, which is weaker than our Parcto-loss objective, and thus, the hardness results can be extended directly. We also note that in the realizable setting, we can minimize other alternatives for scalar losses as we can optimize both precision and recall simultaneously. Nevertheless, hypotheses with optimal P1 or F's scores are specific points on this Pareto front, and will be interesting for future work to find them efficiently.
Beyond that, there are two natural open questions. First, there is gap between the upper and lower bounds. For the scalar-loss objective, we demonstrate that an a = 5 approximate optimal scalar loss is achievable, while a 1.05 is not, leaving it unclear what the optimal is. For the Pareto-loss objective, we establish an upper bound of (p. r) = (5(p- + r),r) and a lower bound of (p, r) # (p + 0.01, 0.01), again suggesting gap that we do not yet know how close.

---

Second, it remains an open question whether there exists combinatorial measure, similar to the VC dimension in standard PAC learning, that characterizes the learnability of precision and recall. Fach hypothesis implicitly defines distribution at each node sade--pecificallyy over its neighborhood. In Section B.3, we also link the scalar loss to the total variation distance, thus reducing the scalar loss learning problem to a special case of distribution learning. However, as shown Lechner Ben-David (2024), there is no such a dimension characterizing the sample complexity of learning certain distribution classes (in their case, mixture of point mass and uniform distributions). This result suggests a potential limitation in identifying a combinatorial measure for learning problem.
uniform distribution
Acknowledgements
Lee Cohen is supported by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness, the Sloan Foundation Grant 2020- 1220-13941, and the Simons Foundation investigators award 689988.
Yishay Mansour supported by funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation, the Yandex Initiative for Machine Learning at Tel Aviv University and a grant from the Tel Aviv University Center for Al and Data Science (TAD).
Shay Moran is Robert J. Shillman Fellow; he acknowledges support by ISF grant 1225/20, by BSF grant 2018385, by Israel PBC-VATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the the European Union (ERC, GENER GENERALIZATION ALIZZATION, 101039692). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
Han Shao was supported by Harvard CMSA.
References
Agarwal, S., Graepel, T., Herbrich, R., Har-Peled, S., & Roth, D. (2005). Generalization bounds for the area under the ROC curve. Mach. Learn. Res., 6, 393 425.
Alon, N., Hanneke, S., Holzman, R., & Moran, S. (2022). A theory of pac learnability of partial concept classes. In 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), (pp. 658-671), IEEE.
Arora, M., Kanjilal, U., & Varshney, D. (2016). Evaluation of information retrieval: precision and recall. International Journal of Indian Culture and Business Management, 12(2). 224-236.
Bekker, J., & Davis, J. (2020). Learning from positive and unlabeled data: A survey. Machine Learning, 109(4), 719-760.
Bogatinovski, J.. Todorovski, L., Džeroski, S., & Kocev, D. (2022). Comprehensive comparative study of multi-label classification methods. Expert Systems with Applications.
Bousquet, O., Kane, D., & Moran, S. (2019). The optimal approximation factor in density estimation. In Conference on Learning Theory, (pp. 318 318-341). PMLR.
Cortes, C., & Mohri, M. (2003). AUC optimization vs. error rate minimization. In Advances in Neural Information Processing Systems 16 [Neural Information Processing Systems, NIPS 2003, December 8-13, 2003, Vancouver and Whistler, British Columbia, Canada], (pp. 3 313-320), MIT Press.
Cortes, C., & Mohri, M. (2004). Confidence intervals for the area under the ROC curve. In Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, NIPS 2004, December 13-18, 2004, Vancouver, British Columbia, Canada], (pp. 305-312).
Daniely, A., Sabato, S., Ben-David, S., & Shalev-Shwartz Shwartz, S. (2015). Multiclass learnability and the erm principle. J. Mach. Learn. Res., 16(1), 2377-2404.
10

---

De Comité, F., Denis, F., Gilleron, R., & Letouzey, F. (1999). Positive and unlabeled examples help learning. In Algorithmic Learning Theory: 10th International Conference, 9LT Tokyo, Japan. December 6 8, 1999 Proceedings 10, (pp. 219-230). Springer.
Denis, F. (1998). PAC learning from positive statistical queries. In International conference algorithmic learning theory, (pp. 112-126). Springer.
Devroye, L., & Lugosi, G. (2001). Combinatorial methods in density estimation. Springer Science & Business Media.
Diochnos, D. I., & Trafalis, T. B. (2021). Learning reliable rules under class imbalance. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), (pp. 28-36). SIAM.
Elissefff, A., & Weston, J. (2001). A kernel method for multi-labelled classification. In Advances in Neural Information Processing Systems.
Gao, W., & Zhou, Z.-H. 1). On the consistency of multi-label learning. In Proceedings of the 24th Annual Conference on Learning Theory, Proceedings of Machine Learning Research.
Gold, E. M. (1967). Language identification the limit. Information and control, 10(5), 447-474.
Grandini, M., Bagli, E., & Visani, G. (2020). Metrics for mulli-class classification: an overview. arXiv preprint 2Xxv:2008.00556.
Juba, B., & Le, S. (2019). Precision-recall versus accuracy and the role of large data sets. In Proceedings of the AAAI conference artificial intelligence, vol. 33, (pp.
Kalavasis, A., Mehrotra, A., & Velegkas, (2024). On the limits of language generation: Trade-offs between hallucination and mode collapse. arXiv preprint MoXiv:2411.096644
Kapoor, A., Viswanathan, R., & Jain, P. (2012). Multilabel classification using bayesian compressed sensing. Advances in Neural Information Processing Systems.
Kleinberg, J., & Mullainathan, S. (2024). Language generation in the limit. Advances in Neural Information Processing Systems, 37, 66058-66079.
Kveton, B., Szepesvari, C., Wen, Z., & Ashkan, A. (2015). Cascading bandits: Learning to rank in the cascade model. International conference machine learning, (pp. 767-776). PMLR.
Lechner, T., & Ben-David, (2024). Inherent limitations of dimensions for characterizing learnability of distribution classes. In The Thirty Seventh Annual Conference Learning Theory, (pp. 3353- 3374). PMLR.
Letouzey, F., Denis, F., & Gilleron. R. (2000). Learning from positive and unlabeled examples. In International Conference on Algorithmic Learning Theory, (pp. 71-85). Springer.
Mao, A., Mohri, M., & Zhong, Y. (2024). Multi-label learning with stronger consistency guarantees.
McCallum, A. K. (1999). Multi-label text classification with a mixture model trained by em. AAA1'99 workshop on text learning.
Menon, A. K., Rawat, A. S., Reddi, S., Kumar, S. (2019). Multilabel reductions: what my loss optimising? In Advances in Neural Information Processing Systems.
Petterson, J., & Caetano, T. (2011). Submodular multi-label learning. Advances in Neural Information Processing Systems.
Rosset, S. (2004). Model selection via the AUC. In C. E. Brodley (Ed.) Machine Learning, Proceedings of the Twenty-first International Conference (ICMI. 2004), Banff, Alberta, Canada, July 4-8, 2004, vol. 69 of ACM International Conference Proceeding Series. ACM.
Sajjadi, M. S., Bachem, O., Lucie, M., Bousquet, O., & Gelly, S. (2018). Assessing generative models via precision and recall, Advances in neural information processing systems, 31.
11

---

Schapire, R. E.,, & Singer, Y. (2000). Boostexter: A boosting-basd -bate system for text categorization. Machine Learning.
Shalev-Shwartz, S., Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press.
Tatbul, N., Lee, T. J., Zdonik, S., Alam, M., & Gottschlich, J. (2018). Precision and recall for time series. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, (pp. 1924-1934).
Torgo, L., & Ribeiro, R. (2009). Precision and recall for regression. In Discovery Science: 12th Internaiional Conference, DS 2009, Porto, Portugal, October 3-5, 2009 12, (pp. 332-346). Springer.
Valiant, I.. G. (1984). A theory of the learnable.
Zhang. M.-L., & Zhou, Z.-H. (2014). A review multi-labed learning algorithms. IEEE Transactions on Knowledge and Data Engineering.
12

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: Our abstract and introduction provide a summary of contributions that accu- rately reflect the new model and the results this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
13

---

Justification:
See discussion.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sellispecifiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provided all the assumptions and complete proofs (some are in the ap- pendix).
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: The paper does not include experiments. All results are carefully proven and do not require experiments establish correctness.
Guidelines:
14

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered inputs), but should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This is a theoretical paper. All results are carefully proven and do not require experiments to establish correctness.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/
httpc///ggiiiee//eeebiiiiiii (Co.eeumiissieieecococ ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
15

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is theoretical paper. All results are carefully proven and do not require experiments establish correctness.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: This is theoretical paper. All results are carefully proven and do not require experiments establish correctness.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This is theoretical paper. All results are carefully proven and do not require experiments to establish correctness.
16

---

Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http:///nrrissssceeeoo
ines?
Answer: [Yes]
Justification: We have carefully read and comply with the NeurIPS code of ethics. This work is theoretical and we do not foresee harmful consequences.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification:
We note that our work is theoretical. We do not foresee any societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
17

---

Answer:
[NA]
Justification:
The work is entirely theoretical; we do not release new data models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that inputs adhere usage guidelines or restrictions access the model or implementing safery filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
We do not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
18

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: We only used LLMs for editing.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.MM policy (https: /ttp///een...///ee ce/Connferences//000 /LLM)LLM for what should or should be described.
19

---

A Proof Overview
Given sequence of IID inputs 2ı, ......y Im let
Fprecision (
1 m
m
(g( (cx))
(x(()))
and
gugger (3r;) g(xe)
Freeall (g)
Migiron (Iza)
denote the empirical precision and recall losses. suffices to focus on empirical precision and recall losses minimization since by standard concentration bounds, minimizing these empirical losses leads to the minimization of the expected recall and precision losses.
Minimizing Precision Loss Through Maximum Likelihood The maximum likelihood method (v:Eg((r:)) which is equivalent to returning the hypothesis with returns nduupai arg max I (1s)))
minimum sum of log output sizes among all consistent hypotheses, i.e..
gomput
arg min
Σ Iog(nn
9:g consistent
Any consistent hypothesis will have low empirical recall loss by applying standard concentration inequality and thus, frecall (gu) is small and we only need to show that the empirical precision loss small. The main technical challenge in the analysis how connect precision loss with likelihood.
Since ghnget is contained in the hypothesis class the realizable setting and is consistent with the training data, due to our algorithm, we have
m
log Log(ngoruu (Mgrru (xx)) S
log(nguue (xx)).
(1)
We first prove that for any hypothesis g, its empirical precision loss can be bounded by term of log output size and the empirical recall loss follows:
Tpreiision (g) S
2
Σ "gieed (or
log (x:) + f (g)
nguuoal (I:;)
iE[m]
By combining Eq (1) and (2), we have
2
gorrpun (xx) Mgana (x:)) + 2 (uuruuy
Tenciision (g ourput)
log
m
Murua (xgg) Lagg
<1
n1 mmge (xx) nanna (x,]
However, with high probability, the first term because, for any hypothesis g, the probability of outputting g is
log
is small. This is
page (=a)
ng (244)
IP Pm Cuuipu
9) P Pry... consistent)
T Rigurger (I:)
For any hypothesis g with large- hypothesis is low.
Σg mg(ta)
"gorge (54) <1 log (arz)
the probability of outputting such
nyann (z.))
20

---

Modifying Maximum Likelihood in the Agnostic Setting In the agnostic setting, all hypotheses in the hypothesis class may have zero likelihood of being the true hypothesis; thus, the standard maximum likelihood method doesn't work. However, we can make slight modifications to the maximum likelihood method to make work for the Pareto-loss objective.
As mentioned earlier, the maximum likelihood method is equivalent to returning the hypothesis with the minimum sum of log output sizes among all consistent hypotheses. Hence, it can be decomposed into two steps: minimizing the recall loss and then regulating by minimizing the sum of log output sizes. In the agnostic setting, given any r, we first find the set H of all hypotheses in the hypothesis class with recall loss at most r + 2e, and then regulate by minimizing the sum of log truncated output sizes by returning
1
log (gg(x;) A 4ng (x:)
g Quinu arg min max g'ER
9ER m xE(m] ny (2r) A 4ng (I:)
where a A == min(a, b). The truncation plays an important role here. Intuitively, let gf denote the hypothesis with precision and recall losses p and r, respectively. If there exists an such that ng (2+) very large, minimizing the sum of log-untrun unguuntreeette output sizes will never return g¹. By applying truncation, we limit the effect of single input with very large output size.
Minimizing the Surrogate for the Scalar Loss Here we consider an alternative learning rule based on two simple principles for discarding sub-optimal hypotheses. We illustrate these principles with the following intuitive example: consider music recommender system, and assume we are considering two candidate hypotheses, o and g". Both hypotheses recommend classical music; however, g recommends pieces by Bach 20% of the time and pieces by Mozart 10% of the time, while y" never recommends any pieces by Mozart or Bach.
Now, suppose that in the training set, users frequently choose to listen pieces by Mozart. This observation suggests that g" should be discarded, as it never recommends Mozart. This leads to our first rule: if a hypothesis exhibits a high recall loss, it can be discarded. The second rule addresses precision loss, which is more challenging because it cannot be directly estimated from the data. To illustrate the second rule, imagine that in the training set, users tend pick Bach pieces only 5% of the time. This suggests that g' is over-vecomeeeee vve-rrecommendin Bach pieces, and therefore, g' might also be discarded based on its likely precision loss.
We formally capture this using a metric defined in the following. For any hypothesis g. let U. denote the uniform distribution over the output set g(x;) at mg. Then, for any hypothesis g. define vector Vg H x H + 10 by
1 m
1 m m
"glo' m Σ (P
Σ P Poy (u (x;)) (x.)).
Intuitively, "g(g''9" g")) represents the fraction of items inputs like that are recommended by g' but not by g" in the counterfactual scenario where g is the target hypothesis. If g indeed the target hypothesis, then this quantity should be consistent with our training data, Vg "g''' "u'' RJ vg(g', g"), where ÿ is the observed (empirical) hypothesis; i.e., the hypothesis in which every 2; is mapped to the random number is which is observed in the training set. In the above example, dg (g ("""") is 20% while vg(g', .''''99. gg") is 5% and thus g is unlikely to be the target hypothesis.
We define a metric dx between two hypotheses 91 and g2 by
(x 92) -1l0, loo
Surprisingly, we show that ta g) is a surrogate for the scalar loss, providing both lower and upper bounds on the scalar loss with a constant multiplicative factor:
(a g) S pecalr (g) < (d target .g) + 2 min gacalar (g').
D'EN
A standard union bound argument yields that with probability at least 1 - 6,
d/v (g. target) so (
log [7]| + log(1/5)
m
21

---

By triangle inequality, we have
Vlog
[H] + (1/(
( tareet 9)) S dx( + +0
m
Then, we return hypothesis goulpu E such that
du du outuut min dx (g.g).
DEH
The Hardness of No Knowledge of the Target Hypothesis's Output Size For any hypothesis g- it's precision loss at any input is [o(=)))g"un and we only get random label v ~ Unif "M (g")) (z)). (x()))
If we are given the knowledge the output size Rypros (Ir) of the target hypothesis, then we can obtain
unbiased estimate of the precision loss, i.e., 1 "gonge (x) 1 [ E g(x)). But the difficulty lies in
(x)
that we don't I know Viginge (r)).
Consider the following example illustrated in Fig 3. For given input x, there is set of items equally divided into two sets (x) and N2(x). Consider two hypotheses with output set 9i (z) N2 (z) and J2 with output set g2(x) (z) U N2(x) being all n items.
In world characterized by 3 E g. 3.. the target hypothesis is generated in the following random way: Randomly select ] .Bn items from Ni (a:) and fn items from (2().. No matter what / is, w.p. 4- v is sampled uniformly at random from Nı (x) and w.p. 1 is sampled uniformly at random 3. from (2).). That is, every item in (x) has probability 2n of being sampled and every item in (2(x) has probability of being sampled. Hence, if we have never seen the same input twice, we cannot distinguish between different H's.
3
For any gag generated from the above process, the scalar loss of gi at x is
lg target (a:) n (x))
g target x O gg (x))
3/4 3n
3/4 ,n
pscalar (g),
x)
1
2gg (x))
hargott
n1
2,3n.
5 3
and the scalar loss of ya at x is
(ggurget (x) gg)())]
Ig (xx)
(xr) n g2 (22(x))
8n
|n
pacalar x2
=1 =21--
=1
2 8.
[xg2(x)
2 gurget (x)
2n
28n
2
When 3 is large, 91 has smaller loss; when small, 92 has smaller loss. With huge input space X' and the distribution 'D being uniform over such huge space X' it is almost sure that we will never observe the same input twice and, therefore, cannot distinguish between different values. Consequently, it's impossible to determine which of the two hypotheses has smaller loss. We show that, in this example, even if algorithms are allowed to be randomized and improper, still impossible to compete with the best hypothesis in the hypothesis class.
22

---

120
0000000
(1)
N2(x)
Nx)
(2
Figure 3(a): gl æ
Figure 3(b): 92
æ2
3.0
100 0
2
100
(1)
N₂
N1 (1)
N₂
Figure 3(c): g graret for small 8
Figure 3(d): g for large 8
Figure Illustration of 9ı, 92 and randomly generated gagget
B Algorithms and Proofs
Notations Let gprecision (g, a)) and grecall x) denote the precision loss and recall loss of hypothesis g at input a:
gprecision (g, x)) = 1g(x) \ (x))
ng(x)
precall (g,x) x) lg taget (x) [(()
Miginnn (x)
Then the empirical precision and recall losses are pprecision (g) m Σ precall (g, æi). Let a A = min(a, b).
gprecision (g, x.) and grecall (g)
B.1 Maximum Likelihood Method in the Realizable Case
In the realizable setting, the target hypothesis glarge is in the hypothesis class. Given the IID training data (z1, U1),... (Im, U,), the maximum likelihood method returns the hypothesis
(oz g((x)))
g outpur
arg max gEH
ng(x:)
In other words, ourpet is a hypothesis in satisfying
consistency: Σ (m & (x,)) O;
regulation: among consistent hypotheses, the output hypothesis satisfies that output arg minggg is consistent Σ (z.)n.
Theorem 1. In the realizable setting, there exist algorithms such that given an HID training set of size 2 0 (()(()))8)) ), with probability at least - 8, the output hypothesis gumpun satisfies
greaat g maspia Se, gorecision muepary S.
Proof of Theorem 1. It suffices to prove that for any fixed (01,-.. Tmm) when m > 12 (2/ w.p. least 1 1 8/2 over V1.m- the empirical values of recall and precision small, grocall (g onnput < e/2 and (Frecision (g output) < s/2. Then we can show greaall (guuppt) < e and frecision (auppl) < by applying empirical Bernstein bounds to both precision and recall losses. Now prove this statement.
the base of log in this work is 2.
23

---

Bounding recall loss is easy as E 1l's & g(x;)) is an unbiased estimate of recall loss. With probability 1 8/4 4 over the randommess of is Unif(g for all [m]] the empirical loss for recall is
m
g garget (x;,
g
Procall (g)
(0 & g(z;)) + E/6 = E/6,
(3)
m
Neginger (2:g)
for all consistent with E (mr & ((x))) Hence, w.p. 1 5/4, ( - <e/6.
Bounding precision loss is more challenging. Let Ag = {i E (unna S 2ng (x+)). Then we can decompose the empirical precision loss
fprecision
(((2))) 5 g (x:)
Tg((Ta)
(a(x)))
g g (xx))
m
+ m Σ
1 & Ag)
m
ny (Ix))
iEA,
2(g(zz)
targer (x::)
2
19 gg (I;) g(()))
min
1
m71 iE
Myproo (2::)
m
grgr (xx;)
Ag
2
Σ min
(g( + gg (ax) \ g(2x))
9 Jurgel (I,)
2
garget (xx²) \ gxx))
m
Ugguro (3r²)
m1 A
Miguznn (204)
iEA,
2
Σ min
(g(
+ 2
uage (xx;) g(x))]
2
(2ra) g(x;))
1,
m
Mgginnn (x:²)
m
Neginen (Ii)
m
Negirgn (24)
tEA,
iE
2
Σ
min
Mg(
1,
+
2 (g).
m AEAg
Nigiuaa (Ir4)
2)
The second term the empirical loss for recall, which is upper bounded by Eq (3).
For the first term,
1
Rz(
1, 2
Σ
min
m
Aguaa (zi)
A
1
Σ
min
1,
Aginenl (2:)
melay) tage (xg) 2
Σ
ng (21)
1, 1 2
min
m
Migis (I:))
nglzy! 21
in Suger (rg)
my (1;)
log
Niguanl (z4)
where the last inequality adopts the following fact: for all 2 1, min(z 1, 1) S log z. On the other hand, we have
1
log
(2g Ngunnal (I;))
Σ
log
Rigisse (z4)
m
m
Lrggn (x2) 21
nyting
mylag) "njorpe (2a)
when g satisfies Σ 1 log(n,(Zz)) < Em log(ng (xx)). Hence, for any hypothesis g with
Fprecision (g) > and precall (g) < 5. we have
Σ
log Nggaaes (Ii)
2 m
(mociision (g) - 2occll (g)) > m E/12 2 log(4 (41))))
ng (xx)
2
Mig (xg) Srgee
24

---

The probability of outputting such a hypothesis is
By (1(
Fenm (g (guippl
I IP mt (g is consistent)
W/
Rgguan (204) < 4/Hr
180 <1
Hence, with probability at least - 6//2 over U1.,, g g will satisfy
(rocall ( cupptt S e/6, Mrecission (umpptt S 8/2.
Then done with the proof.
B.2 Modified Maximum Likelihood Method in the Agnostic Case
In the agnostic setting, we shift our goal from finding a hypothesis with nearly zero precision and recall losses to determining, given any p. E [0, 1], the minimum precision loss p' such that (p. r) (p'.r) r).
In fact, we can show something stronger: we do not need to know p. Specifically, given any r E [0, 1]. let p min (g))) gpecision (g) be the optimal precision loss among all hypotheses with recall loss most r. What is the smallest p' such that we achieve (g S r and ( (gomp S p'?
{91 of two hypotheses, such that for any (possibly randomized improper) algorithm given the knowledge of (p,r) = I 4). there exists a target hypothesis garget with bounded output size and a data distribution DD for which there exists hypothesis g¹ E H with greaal (g') = å and gprecision (g') 16 s.t. for any sample size > O, with probability 1 over the training set, the expected (over the randomness of the algorithm) precision and recall losses of the output gomp satisfy
Theorem 3. There exists class
12 E gprecision (g cutpur
E grecalt (g goupu))
Recall that in the realizable case, the maximum likelihood method selects the consistent hypothesis with the smallest empirical log output size, i.e., nuuppt arg min 9:g consistent Σ log(ng (2;)). Basically, the consistency guarantees small recall loss and the empirical log output size is used as regulation term to bound precision loss. In the agnostic setting, the maximum likelihood method fails as there may be consistent hypothesis. We present modified version of the maximum likelihood method, which still has the "consistency" component and adopts log output size as a regulation term. The algorithm operates follows.
Algorithm:
1. Finding a set of plausible hypotheses which make at most m (r+ mistakes: For any hypothesis g. let 1, (ilps g(x;)} denote the indices of training points that the hypothesis g is inconsistent with. Then let fl = {g E H||4,1 S m (r + <)} be the set of hypotheses making most (r + e) mistakes.
2. Returning the hypothesis with low empirical log truncated output size: Return
My (2:) A (mg
gutpur
arg min max - g' gER sE[m]
log
(4)
ny (1(x)) A 4ng
Theorem 7. Given any E [0, 1] and m 2 O (o(( IID training data, the modified maximun likelihood method can return hypothesis satisfying
grecell (gcclll(gmmnng (uupu))) <r+s, gprecision ouppir) 28r + 15p +
where p min gro Eprecision (g)-
Proof Sketch. Let g to be the hypothesis with recall loss at most and precision loss p. Let F r 23 and p p 25. Similar to the realizable setting, we build connection between precision
25

---

and recall with empirical log output size (Lemma 2), i.e., for any constant c (0,1). It suffices to upper bound Σ
:orecision (
l
Σ
log m (2i) 2M (2::)
1 1+ c Grocall (g)
+
m
Myuro (14)
" "olnean 21
"g(ng)
log (m, (unaa Mgorou (x,)
Le((m]
We first decompose it into
x "areae (104) 21
ng ((ta) ) g (IrA)
Σ
log
Megrrgu (Ii)
iE(m]: *plos) "yurgn (a.) 21 mg (204) 2n g (Ii)
log ng (x1 y (xi)
log
E
Niguaa (34)
n ganes (Is)
iEB: mg(e,) "Jura (ea)
<1
(a)
where B = {il (x:)
The term (b) is lower bounded by the recall loss in Lemma 4. is small, the recall loss must be large while any hypothesis in H. has
Intuitively, if ny (m)))n ( (1ra)
small empirical recall loss.
For term (a), since (geen)) S F and @rrocision (g*) p. at most training points, n ngage (z+) (if it's too large at Iú, precision loss large; if it's too small, recall loss is large). Also, for any hypothesis in H. the empirical recall loss is small and thus, at most training points,
nut (x()
is in [
(=(
2
At these training points satisfying n, (
[ 2] and Poepp (2:)
Buuue (zs) 2 1. we have
ng (xx) pro (xx))
mg (3x4) A 4ng (244)
log
log
Migiroor (I:;)
Migira (x:)
ng (x:) 41gt (I:;)
net (2xz) 4
= =log
+ loog
ngt (x:;) A 4m (x;;)
Migroon (IZ))
"g (I:a) A 4ngy (I:))
neyt (Irs)
< log
log
Nig1 (x:) A 41gg(x;))
Tiginn (I;)
The first term is bounded due to our algorithm while the second term is bounded by the empirical
precision (in Lemma 5). Intuitively, if (x)) is large, the empirical precision of g is large.
B.2.1 Proof of Theorem
Proof of Theorem 3. Consider the size the input space X' being infinite and D being the uniform distribution over it. For each input x, there is an individual set of 12 items, denoted as ((x) =
(v,,1, .2.2..... 1. The hypothesis 91 outputs the first 8 items 91 (1(x) {Uz,1 Vz.2. 8r.8) and the hypothesis outputs the last 8 items (2(x)) {U2.5, 62,6..... 12 There are two worlds which the target hypothesis grarget is generated differently:
World W.p. 2. (x))=*(() = (I);; w.p. 2. g (x) = {u,, U2} where un is sampled uniformly from (W2,5, Ux,6,-... . 82 and u2 is sampled uniformly from (Vr,9, Ve,10,...,, 12,12).
World H: W.p. 1/2 (x) = 92(ar); w.p. 2. (x) (u1, u2) where is sampled uni- formly from (W,,5; 1r,6: 12,8) and u2 is sampled uniformly from (V,,1, 22,2.-..; V.,4).
These two worlds are symmetric. In world I,
1 1 1
3
1
1
1
9
recall(g))
precision(g1)
1
4'
2
16
3
1
3
recall(g2)
2 + -
1=
precision(g2)
4'
2
2
4
8
26

---

Both 91 and 92 have the same recall and has a better precision in the world In world II, 91 and 92 switch their losses. Hence, in either world, we have
7
min
grecall (g) SEH
min greccision (g) 16 JEH
1 is sampled from Uni (x)) and In both worlds, the distribution of e is identical, i.e., w.p. 2. w.p. 2: is sampled from Unif(g2(x)) Hence, if no has been sampled twice, no algorithm can distinguish the two worlds. Since the input space is huge, we will not sample the same input twice almost surely. For any output hypothesis gruuput, we let
I
n (x)) n (Ur,1, U2, Cr 3 {0, 1, ...,, 4]
n2 g output (x)) n (Ur,5, U2,6, (. {0, 1, 4)
n outputt (x)) n (1 10,10 ................................ 12 E {0, 1, 4}
Then in world I, the expected recall and precision of gouput is
1
R2 + 12
12 + 13
721 + 2n2 + 123
(recallgg
qupput x)]
=
2
8
8
16
11 + 122
122 + 113
4n + 5mg + n13
(g
x>)
712 +
4(m + 112 + na))
8(mi + 122 + m1a)
Then suppose randomly choose one of the two world. By taking expectation over the world, and the randomness of the algorithm, we have
711 + 2mz +
5(n)
+ 2nl + 133)
E (recall( pr ))
=E
16
16(n:
n12
.13))
n1 + 2mz +
5
5
=E
+
16
16
16
71 n2
113
Let's denote by r(n1, n2, na) = ai 22 tis and p(n1, n2 na)
5
5
Then for any
16
16
m1
(n1, n2, n3) {0,... ....... 4 we have
12
r(n,, n2, ng)
+
p(p 1 n2; ng)
2n2
133
3
3
16
11 + n2 + 13
711
+
11g
3
+
(maximized at n2 = 4)
16
4
11
+
4
n3
<2.
(maximized at + n2 = 0 or 8)
Hence, we have
12
E (reaall ourput)
+ precisionn output < 2.
This is equivalent to
12
E recall (g output } +
E
Eprecision (g ouuptt]] >
5
B.2.2 Proof of Theorem
Proof of Theorem 7. Let A logt (88 7 = + 2A and 7 = p + 2A. Let Y denote the
hypothesis with precision and recall losses (p.r) r). We know that with probability least 1 - 5, all hypotheses in H have empirical recall loss no greater than r and gt also has ppoccision (gt) S p. Then the proof is divided into two parts:
27

---

(i) hypothesis g satisfies that
ngt (2x) A 4ng(x.)
2 m
max SEA m iE[m]
Σ
log
ng (xs) a 4ng' (xi) 1 67 4p
Therefore, we have max 1 Lielm log " (aupu(ti)A4mn(6 (mi))Add (2z)
6r + 44p + 2
9ER
(ii) any hypothesis g' satisfying max GeR Exe(m] log (x((a)))dnn((a)) Tprecision (g') I 28r + 15p + o(1) Hence, goupir can achieve good precision.
S 6mF + 4mp + 2 has
ngla,)ndn
We prove part (i) by Lemma and part (ii) by combining Lemma 2 and 3.
Lemma 1. For any , Im and hypothesis 9 with E (g) S. we have
ngg (2x4) A (21)
2
log (ri) A 4ng: (2:²)
S 65 + 4p
m
iE [m]
Proof. Let E {i) (w,)
2
1 S
nyonn (x.) S 2}. According to Lemma 6, we know
no (ws))
oegeer (2c)
2
| & 4m7 + 2mp.
log ngg (I:) A 41g(1:))
log Mi (2zz) A (1tg((;))
+ ---
ng (I:) 4n111(10
Ny (It) A 4n (xx:)
E
ngt (2xe)
log My (3x) A Miguzal (IrA)
+ 4rreF + 2mn
EEE
negt (xzz)
ng (g(())) Mggre (2:)
Σ log
Σ
log
+ 4rrr + 2mp
Mggroon (I:)
Migien (x.))
IEE
VEE
<6mF + 4mp + 2.
(Applying Lemmas and 5)
Lemma 2. For any Ti....y I'm any hypothesis g, and any positive constant E (0, 1], the empirical loss for precision (precssion (g) satisfies
1 Aomcision (g) 5
Σ
log T2 (xi) 2 (I:)
+ C Pinccall (g)
+
m
Mywma (I:))
c
:E/m]: Pofo 21 goneer (5,)
28

---

Proof of Lemma 2. Let Ag = {å E [m]]/ggunn (I;) - (1 + e)mg(z;)).
Then we have
pprecision (g)
(g(are) \ g(anpo((z)))
(xx)
1g(x;) g(mme(( (24))
1(i $ Ag)
EEA
==1
(1 (1+c)lgg(ar)) \ garrgs (x:)) 1) +
1 1
[gtarget(s:) g(xx))
min
m
ng Nyuna (I:)
c. m
Nguma (20z)
Ag
iEAg
+ m
(g(21)) + |g bagg (xx) \ g(xx))
n nyuan (I1) ( 1)
1 1
glargee (xxs) g(x+))
min
Nggurer (I;)
c.
nigura (I;)
i
iE
1 c
Σ
min
ng(2;) 1,1
1
Ig (204) (xx)))
1
Ig (3;) \ g(xx))
m 1 +
Rggroe (I:s)
m
Ngiion (21)
c. m
Tggnen (xx))
A
ie
A
Σ
min
(2)
1,1
+ Proccall
m i
Tggarge (Ii)
c
Now we upper bound the first term.
(g((3s)
Σ i
min
1,1
Miguaal (x:)
ng (2x) Teginge (2:s)
min
1,
*gle,) iE[m]: "qlmattn 2 1ta
ny (21e) Neginger (Iis)
Σ Rylng) 8E/m]: a bigeteyy (ry) 21
min
1,
min log my (2iz)
Σ
Mggnn (II:)
"g(ey) iE(m): in bag 21
ng (xx)) A 2M (I:)
Σ
log
mg (I:;)
iE|m]: in pangett
21
where the last inequality adopts the fact: for all = 2 1, min(= 1,1) S log 2.
Lemma 3. For any g satisfying freccal(g) 7 and 1 Σ [m[m]] log Re(xs)dn,,1G (mx)
< 67 + 47
n,, (e,(n,))
have m Eie(m)) malx)) (17) 21 log ny (2)))
18r
12p 4.
m
29

---

(x) (xx)) monn (mr) S 23.
Proof of Lemma 3. Let B
{il
2 and
{
S
For any E B,
glage (xx)
na (z: anna (1rs)
the value of log
[-1, 1].
Then we have
"ounn (14)
ny (xi) g (x:)
Σ mgles) 21
log
Nggumal (I:)
iE(m):
ng (1:s) A 2 (x4)
ni (2((1)) 2m g (204)
log
Σ
log
nguuan (24,)
nigiae (x:s)
iEB
iEB: Pplae) <1 (agg
no (25) g (2+)
Rg (2,)) A n nyuna (x:)
$
log
+ +|-1|
Σ iEB
log
Miuua (24g)
Migoreo (I:)
ieCnB
(2i)) A Amgi (x:s)
mg (a(())) A nguuaal (2i)
log
+1-C1 - Σ
log
Neginnl (24)
Nggurnn (xzz)
IENпB
VEB
ng (1() Amgt (x2))
nig (3:s) A 4ng + 1-0
Σ BECnB
log
log
Nitt (Ii) A 4ng ( (x:)
oggioe (1:)
iECnB
ng (I:; A Mggmenn (2x)
Σ log iEB
Mguunal (x:;)
< m
ny (1:) Ang1 (I:)
log ng (2:)
log
+ + +
Σ
+ |-0
ngt (I:) A (2g(
Nguar (2:)
i=1
iECnB
ni ng(az)) A Migursa (1:z)
log
ngunal (I,)
E
318mF + 12mp + 4.
(Applying Lemmas 4, 5 and 6)
Note that in the second last inequality, adopt the fact that
EA4z
[ 4] for all x, y 0.
y/4z
Lemma 4, For any hypothesis g with Frecall (g) S and any subset C [m]] we have
log ng(37)) A Tiguno (x4)) -2n 1.
Σ
Niguar (Ix:)
iESnB
where B
(2:)
}
pt,pppe (Z.)
Proof of Lemma 4. Now let's focus on the rounds S. B. We have
(1-") ng(3:)) Migiamn (x:)
Σ
greaal (recall 2:) S mr.
Nguna (x;)
NEsnB
iESNB
Our problem becomes computing
ng (xg( A nywma (2+)
min
log
Mguaa (I::)
łESnB
mg (x4) A Mggin (vrs)
8.1.
1 mr.
Ngguaer (I%s)
iESnB
By applying Lemma 7, we know
ng (Ix)) A Rygio (I:)
min
Σ
log
2 22m - 1.
Milssel (xr4)
iESnB
Thus, we have
Σ log (g(x)) A Nguna (xi)
Ng (2t)) A Mggaas (2x)
min Σ
log
-|-B| 4mF 1.
(x
Nggnee (z:)
iEShB
30

---

Lemma 5. For any hypothesis with (precision)) (g) S P and any subset S C [m], we have
(2i)
log
S 2mp + 1.
nigiael (3:)
IESAA
where A - (n(1:) Mygorell (2:)
2}.
Proof of Lemma 5. Since the empirical precision loss is bounded by p. we have
Rygepa (xxs) A ng (T()))
Σ
eprecision (g: xz,) S mp.
ng (24)
IESDA
IESDA
By re-arranging terms, we have
Y gign (xi) A nog (1.)
2 ISn mp.
ng(
YESnA
By applying Lemma 7, we have
Mggrro (I:) A ni (
min
log
2 -2mp - 1.
ng (x()
iESTA
Hence, we have
log Rg([z))
ng (24)
log
S 2mm + 1.
Miqusss (2:4)
Myguzze (2:) ng (Ix)
VESNA
VESNA
Lemma 6. For any withe Frecail (g) I r, we have
Σ 11 ngg
< ) < 2mF
Mgmnor (11))
2
For any withe Pprecision (g) S P. we have
E1 1 ng((x)
> 2) < 2mp.
Rigiorl (1i)
Proof of Lemma 6. When
(x(2.)
2' we have
Bogn (as)
grecall (g. x4.) mg(xx) A ngwrr (xt)
ng (x:)
2
Thus, we have E, 1 ng (1r)
< 2) < 2mnr. Similarly, when ng(aa) pane (2:)
> 2, we have
nymee (3:)
(g, 2 12((2;) nggnnp (x:)
1
goracision
(z)
2
(mr)) Thus, we have E, 1( n tagel (2:)
> 2mp.
Lemma 7. For any l N4, let OPT denote the optimal value to the following constrained
optimization problem:
min R11
log 0s
8.1.
0; k: C,
< < 1, Vi [+]
We have OPT > -2c 1.
31

---

Proof of Lemma 7. We prove the lemma by showing that in the optimal solution, there will be at most one entry of 6is not in ( 1). In this case, there are [2c] many 's and one [2c] Then, we have
log 0; -2c
Hence, it suffices to prove that in the optimal solution, there will be most one entry of 0ik not in
(..1 1}. Suppose that there are two entries a1 < 02 E ( 1). For any > 0 stt a A 02 + A
[ IJ, we have
0/2 + < log(
d1
log(
02
01
A
which is due to -+ is monotonically decreasing in z. By re-arranging terms, we have
log(a1 A) + log(a2 A} log(o1) + log(02)
Hence, we can always decrease the function value by changing 41, 02 to aj A, + A. By setting = (1 - a2) A (a) 2), either a, is changed to 2 or 02 is changed to 1. We reduce the number of entries not being or 1. We are done with the proof.
I
B.3 Surrogate Loss Method Both Realizable and Agnostic Cases
Again we focus empirical precision and recall losses minimization. Let .......,,... Zm E X denote sequence of inputs. For each hypothesis g. let U.¹ denote the uniform distribution over the output g(xn4). For any pair of hypotheses g': g."", define the following:
precision.loss(f) [gg recall.loss(g' (9) = Σ U (g((z)) (x.))
Here precision.loss(/ g²) is the precision loss of hypothesis o' when the target hypothesis g" and recall.lossig" g') is the recall loss of hypothesis g" when the target hypothesis is g'. Thus, the goal is to output a hypothesis with small precision.loss(g | glanget) and recall.loss(g) gurget).
Our learning rule is based on two simple principles for discarding sub-optimal hypotheses. We illustrate these principles with the following intuitive example: consider a music recommendation system, and assume we are considering two candidate hypotheses, 91 and Both hypotheses recommend classical music; however, 91 recommends picces by Bach 20% of the time and pieces by Mozart 10% of the time, while 92 never recommends any pieces by Mozart.
Now, suppose that in the training set, users frequently choose to listen pieces by Mozart. This observation suggests that J2 should be discarded, as it never recommends Mozart. This leads to our first rule: if hypothesis exhibits a high recall loss, it can be discarded. The second rule addresses precision loss, which is more challenging because it cannot be directly estimated from the data. To illustrate the second rule, imagine that in the training set, users tend pick Bach pieces only 5% of the time. This suggests that is reommeecomnn Bach pieces, and therefore, might also be discarded based on its likely precision loss.
We formally capture this using the following metric. Definition 1. For a hypothesis g define a vector Vg x H - [0, by
"g 1 Σ (g (x:))
Define a metric du between hypotheses by dix 92) = ||ug 2g2lloc.
Let be the observed (empirical) hypothesis; i.e. the hypothesis which outputs {w.) at æ; for all (xa,, 02) the training set and outputs the empty set for all unobserved input. A standard union bound argument yields:
32

---

g Then, with Lemma 8. Let gorre denote the true hypothesis (i.e. the data is generated from from
probability least 8:
dx G. g S (v log H + log(1/6)
We now present our algorithm. We present two variants, one in the realizable setting (when glagel E H) and one the general (agnostic) setting.
Algorithm (realizable case): Let denote the desired error. Output hypothesis gullp H such that
1. For all 9 E H. Vg(9, goupptt = O.
2. For all g E H. U Vo (g quipull g) 2E
"uuup g) 0,
Notice that Item I corresponds the first principle for discarding suboptimal hypotheses described earlier in this section, while Item corresponds to the second principle.
Algorithm (agnostic case): output hypothesis n E H such that
dx 6x (uppt) = min (g.
gEW
We prove that Theorem 8. Let glaree denote the target hypothesis. Then, for
m = 0 log H +
the agnostic-case algorithm outputs a hypothesis go such that with probability at least 5,
grealar (uuput)
S 5im grealar (g) +
9EH
Remark 2.
the realizable setting, our algorithm achieves a quadratic improvement in sample com-
plexity: learning with recall and precision losses at most can be achieved with O log]H (log(1/8) examples.
B.3.1 Proof of Theorem
Proof of Theorem 2. For simplicity, we adopt payoff's instead of losses here. The payoff of hypothesis at x is
turget (x) (g(x))
Ig (arga (2)) ng(x)]
u(g, x)
2lg(2:)
gagget (x:)
g(x) and (agge(s)) + 0, u(g, 2r) : if both are empty set u(g, x:) The expected payoff
u(g) = E (u(g, x] = gscalar (g)
Construction of garget and D Let's start by focusing
single input æ. There items (z) = and (2( = B + I...., n). Consider two hypotheses 91 with (x) = (z and
92 with (2( Ni (x) N2(x). So (z) contains half of the items in 92(x).
world characterized by 3 E [ 2. (xrget(()) is generated in the following random way: Randomly select 3 3n items from N₁ N1(2) and Br items from N2(x). We denote this distribution by P3. No matter what 3 is, w.p. a v sampled uniformly at random from (x))) and w.p. 7 sampled uniformly at random from (z).. That is, every item in N1 (z) has probability 2n and every item in N₂ (z) has probability 2n of being sampled.
3 of being sampled
33

---

For any grr generated from the above process, the payoff of 91 at x: is
u(01,20 2) lg gg (a) (g) and the payoff of O2 at x is
(x)))()) (x) n (g
3/4 Bon
3/4. 3n
3
3
3
(
g (x)
23n
4 8
u(92,z) (g (x) n 92(x)]
lg Lgggeet (ar) 0 g1)(())
3n
8n
2
2(g2(z))
2[ghuret(11) (x)
2n
2
2
We make infinite copies of (a,, Ni (z)). In each of the copy, 91 ()()) (1) and g2(x)
Ni (x) U (a))... For each x, we independently sample (x) from Pg. Let the data distribution over all of such copies of x. Then almost surely, there is no repentance in the training data, i... there does not exist i * j such that 24 Zz. And for any random sampled test point, w.p. 1, it has not been sampled in the training set.
Analysis For any unobserved x of {æzli E [m]]] let a [2n and ag Note that 1 0r are in [0, = and are possibly random variables if A is randomized. Then the expected (over the randomness of g garrget) payoff of gouppr at x is
lg "u (x))
(x: n gomput (x)]
Ig ( n (ouppat())) (x)
Egena [u(g output [ = Egg
g gutput (z)]
((gtar))((x))
ain 3 + agn B
ain 5 + agn 333
2(a1 + 422)
23n
a18
8
3
1
2(on =2)
4
a1 +
702
4
(5)
which is monotonically increasing a1. Hence Egzn [u(g output xT] is maximized at 01 2-
1 Then
1 02-
Egguses
[u(gourg outpul
x)] -
( + +
+ 1)
Note that /3 is not observable if we never sample the same x more than once (and thus the distribution of conditional 3 is identical for any (3). Hence gouput is independent of 3.
If P ( (x) s 1) 2 when 3 3.4 Eo [u(grrpput .r] I { 4480z + .22) +
13
is
32
monotonically increasing in a2. Hence,
1 9
49
5
5
u(g2) Exgre [upgoutput)]
pacalar (g2).
2
16
192
84
If Pa~D(a2(1) > 1) ス :: when 1 maximized at 02 = 2 for E [1:2) }. Hence,
3. Eguns (up x)]
+ J02 +
is
34602
21
7
5
1
u(g)) Eygne [uput)
peaalar (g))
8
48
Therefore, for any algorithm A, for any Tisms Viim Eggre [ is worse than 1.05 min (acalar (g1) gsealar (92)} } at either / 1 pocalar (g output Z 1.05 min m
g or B 2. So there exists a target hypothesis such that pacalar (g)), gealarr (gz)}
B.3.2 Proof of Theorem
We use the following auxiliary metric between hypotheses: Definition 2. For hypotheses g'.g" define
dp.rlg'g'' ."') =recission.oss(dggee (g") recall.loss(glob)
precision.loss recall.loss(g
34

---

For any hypothesis 9, the scaler loss (g) 2 (g "g g In the remainder of this section, we focus on proving Theorem 8. The basic idea show that dy can be used as surrogate for dp.r. The following lemma plays crucial role in our proof.
Lemma 9, For every pair of hypotheses 92.
(91.99)) S (01
in addition 91, 92 H, have:
(p. I 2d 92).
We first use Lemma 9 to prove Theorem 8, and later prove the Lemma.
Proof of Theorem 8. Assume m = O log 1 +loo()(1)))) is such that (g g g < e/4 with probability least 1 6, and assume the latter event holds. Let g E H. by the triangle inequality:
c²
d : _garret) I ( .9) + dp.r gmmget).
We upper bound the first term the right-hand side as follows:
(g ounpur g) 2d (g output .9)
(Lemma 9)
s 2dH (g gotput garget) 2d trgge .9)
4dx (g gurgel
9) +
(see below)
x uurge
(9) +
(Lemma 9)
Altogether,
dp,x (g ouppor g g 5dp. (g, g +e.
remains to explain the second to last inequality above. follows by two applications of the triangle inequality:
dx (g ouipul )
S dr oulppu - e/4
(d .9) S E/4) (g E arg mingen gEN dx(), (d arget . $ E/4)
S (g, D E
s dx (g, b + E/2.
Proof of Lemma 9. For the first inequality, note that both of the distributions U and U. are uniform their supports and hence TV(U,", U!4) max (g) (Ix)) (2()))), 0 (ga(x:) ( (x:))) Thus, for every g' g'"g" E H::
(g \. (2 ((x))))()))))
STV(U?" U
S (g1( (z,) \ (e()x)) + (g((z)) (2)(x;) (z.))..
Hence, by averaging the above inequalities over 1.....
(x1.19922
TV(U,) U?? < dp.r (91, 92),
which yields the first inequality.
For the second inequality, assume 01.92 E H. Thus,
U (ar (x:) \ (2())))) 1 Σ (g((x)))) ( (z()))))
(x( max
U (a)(2s) \ (e((:)) + UP (oa(x:) ()(()))
2
1=1
1
dp..
2
35

---

B.4 Algorithm and Proofs in the
Case
In the semi-realizablee case, there exists a hypothesis the class with zero precision loss. The question is whether we achieve zero precision loss while allowing for the worst recall loss in the class.
Theorem 5. There exists an algorithm such that if there exists a hypothesis g' E H with goncision (g') = O and grecall (g') then given an IID training set of size O log (1/61) ), with probability 1 1 8, outputs hypothesis with gprecision ( (grpptt))
2/
0 and greaal (g
The algorithm works as follows.
Algorithm: output
( g(x,))
g
output
arg min gEH
ni (1;))
If there multiple solutions, break ties by picking the hypothesis with smallest empirical recall loss.
Proof of Theorem 5. For any hypothesis g. 1(u, E g(x;)) is an unbiased estimate of the recall (9(a,) ng undt (z.)) Thus, [(vcEg(z.)) is an unbiased estimate of [o(x;)ng" ny [y(2a)-n,enme(44
Regg (22)
my(#:)
la(a la(a;) ((g")))
Since g' has zero precision loss,
1 almost everywhere. Thus, we have
(ws)
m
(vz g(()))
log (H)) + 1og(1/6)
E
m
(g())))
Mgwuer (z)
m
for all 9 E H. Then if Ap > O. we need I
samples to separate g' from other hypotheses in the A
hypothesis class.
Theorem 6. There exists class H. {91, 92) of two hypotheses, for any > 0 and any (possibly randomized improper) algorithm A. there exists target hypothesis glang and a data distribution D for which there exists hypothesis g H with goeeision (g' 0 s.I. with probability 1 over the training set, the expected (over the randomness of the algorithm) precision and recall losses of the output goupu satisfy either E. [grecall ( (umprr) Z .minge grecall (g) (1) E [gurecision gonputt ((1).
Proof of Theorem 6. Let's start by focusing on one single input x. Let N = (ui,.... vn) for some >> Let 91 (xx) {w1) and g2(x)) (12). In world garreet (1:) is generated in the following way.
* w.p. 2' g " (z) N {
1
w.p. 1. g arga (x) = v2)
We construct a symmetric world II by switching en and 02, i.e.,
w.p. 2: g tageet (z) N (u1}.
1
w.p. J. g aagett (r) (v1,22)
We make infinite independent copies of (x, N) and let D to be the uniform distribution over such z's. Hence, in world (peccision (g1 0 and grecall (g1) When + oo, can't inn't distinguish between two worlds. In order to achieve grrecision auuppt)) in
2 gpeecision (g2) 1 and grecall (gz) 3
both worlds, we need to make (xx) = ( for almost every æ. Then the recall loss would be 1. 0
36


Reviews:
[{"review_id": "XFbO7qNjov", "reviewer": "Reviewer_PCHe", "summary": "This paper studies PAC learning for the scenario where the hypotheses are set functions that map each input to a set of labels, instead of traditional single-label predictions. The authors consider realizable and agnostic settings. For realizable setting, they prove the sample complexity upper bound $O(\\frac{\\log|H|/\\delta}{\\epsilon})$ to achieve both $\\epsilon$ precision and recall rate. They give two algorithms to achieve this rate: one is maximum likelihood estimation and the other is minimizing surrogate loss. In the agnostic setting, they prove that achieving additive error is impossible by providing two lower bounds. Instead, they prove the sample complexity to achieve a multiplicative excess risk. The algorithm achieving this rate is the adapted version of  the realizable setting algorithms to the agnostic case.", "questions": "Please see the weakness part.", "limitations": "This is a theory paper so I did not see potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\nThis paper for the first time studies the PAC learnability of precison and recall losss, which is very novel and useful, since in practice, people care more about PR rate of an algorithm rather than the overall misclassification rate. The theory is neat and interesting, and the algorithms are intuitive and natural---the authors show that the traditional ERM will fail but MLE is a PAC learner for precision and recall loss. They further provide impossibility results for agnostic setting, which match with my intuition that one cannot do well both in precision and recall rate.\n\nWeaknesses:\nThe authors claim that the additive excess risk bound is not achievable, and a multiplicative factor is unavoidable. However, the constant in lower bound and upper bound is rather large (1.05 vs 5). Hence I am curious what will be the optimal constant. Is that achievable by refining your techniques?", "was_revised": true, "final_justification": "In rebuttal, the authors discussed the potential solution to my question about the constant in upper and lower bound. This is a good theory paper and I recommend acceptance.", "rebuttal": "We thank the reviewer for their positive and insightful feedback.\n\nRegarding the optimal multiplicative constant: we agree that precisely characterizing this constant is an intriguing open problem, which we leave for future exploration.\n\nWe note a connection between our setting and the problem of hypothesis selection (i.e., distribution learning with respect to the total variation metric), which may offer some useful intuition. Consider the special case of our model with a single input: here, each hypothesis corresponds to a subset of labels, and the learning problem specializes exactly to a hypothesis selection problem where both the target distribution and all distributions in the hypothesis class are uniform over subsets. Determining the optimal multiplicative factor such hypothesis selection problems was posed as an open question in the book by Devroye and Lugosi [1], and was only recently fully resolved [2]. This connection suggests that identifying the optimal factor in our setting may similarly be challenging, yet potentially approachable by leveraging techniques from the study of density estimation and hypothesis selection. We believe this is an interesting direction for future research.\n\n[1] Devroye and Lugosi, “Combinatorial Methods in Density Estimation,” Springer, 2001.\n\n[2] Bousquet, Kane, and Moran, “The Optimal Approximation Factor in Density Estimation,” COLT 2019."}, {"review_id": "38Flm6m4CT", "reviewer": "Reviewer_hDwa", "summary": "This paper introduces a novel PAC learning framework for precision-recall optimization under partial feedback, where algorithms observe only positive examples during training (e.g., a single randomly sampled label from the ground-truth set) but must predict complete label sets at test time. The authors demonstrate that classical approaches like Empirical Risk Minimization provably fail in this setting, even for simple hypothesis classes, due to the inability to estimate precision loss without negative examples. They propose two new algorithms for the realizable case achieving optimal $O(\\log|H|/\\epsilon)$ sample complexity, and establish fundamental limitations in the agnostic setting where additive approximation guarantees are impossible, requiring multiplicative approximation factors instead.", "questions": "See weaknesses.", "limitations": "the authors adequately addressed the limitations and potential negative societal impact", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThis paper proposes an interesting problem: how can models optimize to achieve good precision and recall when only partial positive labels are available, which is meaningful in real-world applications.\n\nWeaknesses:\nThe paper has certain relevance to \"Revisiting Pseudo-Label for Single-Positive Multi-Label Learning\". That paper proves the learnability under single-positive multi-label learning through ERM and proposes two assumptions (the assumption of pseudo-label accuracy and the assumption of data distribution sampling). The authors should provide some discussion regarding that paper. In addition, the related work section should include discussion of articles related to multi-label learning with missing labels, such as [1-5].\n[1] Revisiting Pseudo-Label for Single-Positive Multi-Label Learning\n[2] Multi-Label Learning from Single Positive Labels\n[3] Label-Aware Global Consistency for Multi-Label Learning with Single Positive Labels\n[4] One Positive Label is Sufficient: Single-Positive Multi-Label Learning with Label Enhancement\n[5] Large Loss Matters in Weakly Supervised Multi-Label Classification", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback and for bringing these references to our attention. We agree that discussing these papers would strengthen our related work section, and we will gladly add an appropriate discussion of these works in the revised version."}, {"review_id": "XjTTEGlmfM", "reviewer": "Reviewer_k9sU", "summary": "This work focuses on a learning setting where the learning data consists of partial feedback and the goal is to learn to predict a set of labels. Specifically, it considers two settings, realizable setting and an agnostic setting, depending on whether the ground truth hypothesis is in the hypothesis class. It further presents the theoretical results on the learnability for both settings, including both positive and negative results.", "questions": "In addition to those raised in [Strengths And Weaknesses]:\n- why obtaining an unbiased estimation of precision loss is not possible in this setting (line 216)? My understanding is that as long as the sample is large enough, all the target labels would be observed.\n- at line 100, it is mentioned that in the partial feedback setting, it is impossible to estimate precision loss while later the scalar-loss objective is defined as the combination of recall and precision loss. Can the authors clarify on what metrics can be computed exactly and if there are any approximations?\n- what's the computational complexity of algorithm 1?", "limitations": "Yes.", "rating": 2, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The problem of learning from partial labels considered in this work is interesting since such scenarios can happen when labeling is costly. However, a few concerns arise when reading this work:\n- the assumption that the hypothesis class is finite weakens the theoretical results in this work since it doesn't hold in practice. \n- missing related work: the problem setting is closely related to the PU learning setting [1,2] where only positive labels are observed.\n- in this work, it compares with ERM a lot but it's unclear to me how ERM is defined in this work and why ERM would fail in this case. In the paragraph from Line 121, the authors claim that the reason ERM would fail is because two hypotheses can have the same recall loss but different precision loss, which is further illustrated by Example 1. However, in example 1, recall losses are not impossible to compute since it requires the ground truth label set {u_1, ..., u_n}, which is not accessible since the training datapoints only reveal one label, while only precision loss is possible. Further, precision loss can actually distinguish the two hypotheses in this case, so ERM could possibly work. Can the authors elaborate more on this?\n- Theorem only proves about PAC learnability but not the efficiency of the proposed algorithm. For the first algorithm maximum likelihood, the idea is standard and not really a technical contribution; also, it doesn't seem that the optimization problem can be efficiently solved.\n- the definitions of G' and G'' in algorithm 2 are unclear. Can the authors provide an example to show how this vector is computed?\n- minor: at line 189, should the domain be X*Y instead of X^2?\n\n[1] Bekker, Jessa, and Jesse Davis. \"Learning from positive and unlabeled data: A survey.\" Machine Learning 109.4 (2020): 719-760.\n[2] Xu, Yixing, et al. \"Multi-Positive and Unlabeled Learning.\" IJCAI. 2017.", "was_revised": true, "final_justification": "As mentioned in the discussion, I still don't see how the theoretical insights lead to a practical algorithm, and there's a lack of empirical results. Since the authors didn't reply to my concerns, I'll keep my score.", "rebuttal": "We thank the reviewer for their feedback. In what follows, we address comments and questions.\n\n\n**Finite hypothesis class**\n\nNote that in many real-world applications, the feature space is effectively finite—for instance, in image classification, where each input is a fixed-size array of pixels, or in recommender systems and user modeling, where individuals are represented by a finite collection of features. In such cases, the log |H| bounds we provide can offer meaningful performance guarantees. Additionally, in many natural parametrized classes, bounds for infinite hypothesis classes can often be derived by reducing to the finite case via a suitable covering argument. For example, in geometric settings, the cover size typically scales as (1/ε)^d, where d is a natural notion of dimension—yielding bounds that scale with d and an additional log(1/ε) factor.\n\nIn addition, many of our results—particularly the negative ones—highlight structural barriers that are not tied to the assumption of finiteness. For example, we show that ERM fails while MLE succeeds, and that additive excess risk bounds are unachievable in the agnostic setting already for finite classes. \n\nFor the positive results, we agree that it is interesting to extend the analysis to infinite classes, potentially via combinatorial parameters analogous to the VC dimension. This remains an open direction (see also the discussion section and Footnote 2), and we hope our work helps identify the right questions—for instance, whether learnability in this setting can be characterized by a new type of dimension.\n\n\n**PU learning**\n\nThanks. We’ll add a discussion in the related work on PU learning.\nIn particular, while there are only positive examples in the PU model, the unlabeled examples provide significant information about the (potentially) negative examples.\n\n**Why ERM fails**\n\nWhen we refer to **ERM** in this work, in the realized setting, we mean the selection of an arbitrary hypothesis that is consistent with the observed data. Specifically, since the training data only reveals one label $v_i$ per input $x_i$, we define ERM as selecting\n$$\n\\arg\\min_{G \\in \\mathcal{H}} \\sum_{i=1}^m \\mathbf{1}(v_i \\notin G(x_i)).\n$$\n\nAs noted in Line 190, the observed label $v_i$ is drawn uniformly at random from the ground-truth set $G_{\\text{target}}(x_i)$.\n\nIn **Example 1**, $G_2(x_i) = \\{u’\\}$ does not contain any correct label, so $v_i \\notin G_2(x_i)$ for all $i$. $G_1(x_i) = \\{u_n\\}$ contains onecorrect label $u_n$, but when the size of the ground-truth set $n$ is large, the probability that the observed $v_i$ matches this single predicted label $u_n$ is vanishingly small. With high probability, for all $i$, we will observe a label $v_i$ that does *not* belong to either $G_1(x_i)$ or $G_2(x_i)$, causing both to incur maximal empirical loss (i.e., a loss of 1 for each $i$).\n\nThus, ERM cannot distinguish between them based on the training data, even though $G_1$ has perfect precision and $G_2$ has zero precision. This illustrates that ERM fails to identify the better hypothesis in this setting.\n\n**Computational complexity**\n\nOur focus in this work is on **statistical complexity**, not computational efficiency. The central questions we aim to answer are: (1) whether learning with precision and recall is *statistically* possible under positive feedback, and (2) how many samples are needed to achieve this. From an algorithmic standpoint, we also investigate whether classical ERM works in this setting—and show that it does not—and identify alternative principles that do, such as maximum likelihood.\n\nWhile the idea of using maximum likelihood (MLE) is standard, its behavior in this partial-information setting is non-trivial and has not been analyzed before. \n\nMoreover, establishing the applicability of a classical and intuitive principle like MLE is an advantage—especially since the more naive ERM approach fails in our setting. More broadly, we see theoretical value in rigorously analyzing simple and natural algorithms, particularly when the analysis is non-trivial. In our view, this makes the result even more interesting.\n\nWe view our contribution as highlighting its effectiveness in a regime where ERM provably fails. That said, the question of *efficient* optimization is indeed important, and we see it as an important direction for future work.\n\n**Definitions of G' and G'' in algorithm 2**\n\n$G'$ and $G''$ are not special hypotheses—they are simply elements of the hypothesis class $\\mathcal{H}$ and serve as inputs to the definition of the vector $v_G: \\mathcal{H} \\times \\mathcal{H} \\to [0,1]$.\n\nEach entry of the vector $v_G$ corresponds to a pair $(G', G'') \\in \\mathcal{H} \\times \\mathcal{H}$ and can be written explicitly as\n$$\nv_G(G', G'') = \\frac{1}{m} \\sum_{i=1}^m \\frac{|G'(x_i) \\setminus G''(x_i)|}{n_G(x_i)},\n$$\nwhere $n_G(x_i) = |G(x_i)|$. \nWe will clarify this in the revised version.\n\n**Why obtaining an unbiased estimation of precision loss is not possible**\n\nWe’d like to clarify that in our setting, the inputs $x_i$ are i.i.d. samples from a data distribution with potentially infinite support. Each input $x_i$ is associated with a ground-truth label set $G_{\\text{target}}(x_i)$, but we observe only a single label $v_i$, drawn uniformly at random from $G_{\\text{target}}(x_i)$.\nAs a result, each $x_i$ is typically seen only once, and we do not observe the full set $G_{\\text{target}}(x_i)$. This makes it fundamentally impossible to determine whether the *unobserved* labels predicted by a hypothesis are correct. Therefore, we cannot obtain an unbiased estimate of precision loss under this partial feedback model.\n\n**``at line 100…''**\n\nThanks for the question. To clarify: in our setting, **recall loss can be estimated with vanishing additive error**, because we observe whether the sampled label $v_i$ is included in the predicted set $G(x_i)$. However, **precision loss cannot be estimated in an unbiased way**, since we do not know which predicted labels (other than the observed $v_i$) are actually correct or incorrect.\n\nDespite this, we show that in the **realizable setting**, where there exists a hypothesis with both zero precision and recall loss, it is still possible to identify such a hypothesis using the MLE-based algorithm—even without being able to directly estimate precision loss.\n\nIn contrast, in the **semi-realizable setting**, where there exists a hypothesis with zero precision loss but non-zero recall loss, we prove that no algorithm can achieve both vanishing precision and optimal recall loss (see Theorem 6). This demonstrates the inherent difficulty of optimizing precision under partial feedback, especially outside the realizable case.\n\n**Computational complexity of algorithm 1**\n\nLike MLE in other learning settings, Algorithm 1 requires evaluating a score for each hypothesis in $\\mathcal{H}$ based on the training data. This results in a total computational cost of $O(m |\\mathcal{H}|)$, where $m$ is the number of samples."}, {"review_id": "eO6ImkirD5", "reviewer": "Reviewer_sqyN", "summary": "As traditional learning paradigms fail when only positive labels are observed, a new PAC-learning framework is presented to optimize precision and recall losses under partial feedback. This setup in practice applies to multi-label learning tasks, such as tagging people in photos, where only some tagged names are observed, but not the full set of people.  The paper shows that optimizing precision is fundamentally more difficult than optimizing recall in this setting because of the absence of negative feedback. Two algorithms are presented, the maximum likelihood-based algorithm, and the surrogate loss minimization algorithm, which are shown to achieve upper and lower bounds. Two settings are analyzed: i. Realizable Setting, when the true hypothesis is in class H; ii. Agnostic Setting, when the true hypothesis not necessarily in H.", "questions": "1.\tOn Practical Impact and Real-World Feasibility: Could the authors elaborate more on how their algorithms might be adapted to real-world tasks (e.g., recommender systems or tagging applications)? If possible, implementation on some toy datasets, including some commentary on feasibility under partial observability assumptions. These would strengthen the paper’s significance.\n2.\tClarification on Output Size Assumptions: Several results depend on the assumption that the output size n_G^{target} is bounded or known. In many practical applications, this is not directly available. Could the authors discuss how their methods behave when this size is unknown or only loosely bounded?\n3.\tIntuition and Use Cases for Scalar vs. Pareto Loss: The distinction between scalar-loss and Pareto-loss objectives is theoretically clear. Could the authors clarify what kind of applications might naturally benefit more from optimizing for one versus the other?\n4.\tLower Bounds Interpretation: The paper proves lower bounds like \\alpha ≥1.05 for the scalar loss and impossibility of achieving additive error for Pareto loss. Could the authors comment on whether these lower bounds are tight in any known cases? Are there scenarios where existing heuristics approach these bounds?\n5.\tImproving Accessibility: While the main ideas are well-explained, could the authors consider adding more intuitive commentary or diagrams near the formal results to guide non-theory readers (e.g., explaining the significance of each key theorem in words, or linking them to the motivating examples)?", "limitations": "Authors only discussed the theoretical limitations of the paper. As this is almost purely a theoretical paper, the authors did not discuss any societal impact aspects of this work.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n•\tOriginality: The paper tackles a novel and important learning setting, which is learning under one-sided (positive-only) feedback. This is highly relevant in real-world applications like multi-label learning and recommender systems. The formalization of this setup into a new PAC-learning framework is a meaningful and original contribution.\n•\tSignificance: By highlighting fundamental differences between learning precision and recall under partial supervision, the work sheds light on overlooked aspects of supervised learning theory. In particular, the hardness of estimating precision loss without negative labels is both practically and theoretically significant.\n•\tTheoretical Quality: The paper demonstrates a high level of rigor in constructing new learning guarantees. It provides both upper and lower bounds, separating realizable and agnostic settings, and analyzes both scalar-loss and Pareto-loss objectives. These contributions form a solid theoretical foundation.\n•\tAlgorithmic Contributions: Two learning algorithms, based on maximum likelihood estimation and surrogate loss minimization, are clearly described and motivated. They show that learning from only positive feedback is tractable in some settings, but fundamentally limited in others.\n•\tClarity of High-Level Ideas: Despite the complex theoretical nature, the paper does a good job of motivating the problem and building intuition through illustrative examples (e.g., the indistinguishable hypotheses with vastly different precision losses).\nWeaknesses:\n•\tClarity for Non-Theorists: While the high-level concepts are well-motivated, the technical sections, especially the proof sketches may be hard to parse for readers not familiar with PAC learning theory or sample complexity analysis. A bit more intuitive commentary around key lemmas and theorems would help make the results more broadly accessible.\n•\tNo Empirical Results: The paper is entirely theoretical. Although this is acceptable for NeurIPS theory tracks, some small-scale synthetic experiments (even toy data) could help reinforce the practical relevance and intuition behind the proposed hardness results or algorithmic strategies.\n•\tAssumptions on Output Size Knowledge: Some results depend on knowing or bounding the output size n_G^{target}, which may be non-trivial in practice. The practical implications of this assumption are not fully explored.\n•\tPractical Impact Path Not Fully Developed: Although the authors claim relevance to real-world domains, there is a gap between the theory and potential practical implementation guidance. It would be helpful to bridge that more directly, even if via discussion or future work.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive and insightful feedback. In what follows, we address comments and questions.\n\n- **Clarity for Non-Theorists:** Thank you for the feedback. We will add more details and provide intuition to clarify the proofs for future readers.\n\n- **Assumptions on Output Size Knowledge**: We only assume that the output size of the target hypothesis is **bounded**, but not necessarily known, in Theorem 5. This mild assumption enables us to achieve zero precision loss in the semi-realizable setting. We complement this with the **impossibility result in Theorem 6**, which shows that without any such bound on the output size, it is impossible to achieve an additive guarantee on precision loss. Together, these results characterize the role of output size in a sharp and principled way.\n\n- **On Practical Impact and Real-World Feasibility**: \nThank you for this suggestion. As noted, our paper is intended as a theoretical contribution—specifically, it defines an analog of PAC learning for precision and recall—focused on rigorously modeling learning problems with asymmetric loss under partial feedback. We introduced a general framework for studying such problems, proved basic results about the statistical expressiveness of classical algorithmic templates (such as ERM and MLE), and highlighted key algorithmic and information-theoretic phenomena that arise in this setting. Our goal is to lay a *theoretical foundation* for precision/recall learning under partial observability. While adapting these ideas into concrete implementations and empirical studies is an important direction, it lies beyond the scope of this work. We hope that the framework we propose will serve as a basis for future research into practical algorithms that operate under similar constraints.\n\n- **Intuition and Use Cases for Scalar vs. Pareto Loss**: The scalar loss is appropriate when there’s a known trade-off between precision and recall—for example, in medical screening, one may weigh recall more heavily to avoid missing true positives. \nThe Pareto loss, on the other hand, is useful when one metric must meet a strict operational threshold while optimizing the other. For instance, in spam detection, a system may be required to maintain precision above 95% to avoid frustrating users with false positives. Within that constraint, the goal is to maximize recall. Such asymmetric constraints cannot be naturally encoded by a fixed convex combination, making Pareto-based optimization the more appropriate tool in these scenarios.\n\n- **Lower Bounds Interpretation**: We prove a lower bound showing that no algorithm can achieve a multiplicative factor smaller than 1.05 for scalar loss, and we give an upper bound of 5 using our surrogate loss approach. It remains an open question whether this gap can be closed, and identifying the tight constant is, in our view, an interesting technical challenge. That said, we want to emphasize that the key takeaway from our lower bound is *qualitative rather than quantitative*: it establishes that achieving an *additive* error bound is fundamentally impossible in this setting. This marks a sharp departure from standard PAC learning and highlights the need for new learning principles under partial feedback.\n\n- **Improving Accessibility**: We will add more intuitive explanations after each result."}]

Author rebuttal:

Meta-review: This paper makes two key contributions. First, it provides a corrective result by showing that ERM provably fails under one-sided feedback, ruling out an entire line of approaches that would otherwise mislead future research. Second, it introduces a constructive Pareto-loss perspective, giving optimal sample complexity bounds, and thereby guiding how future algorithms should be designed to balance precision and recall in this setting.

Across three positive reviews (scores 5, 4, and 4), there is clear consensus on the importance of these insights for shaping future work. Reviewers recognized the significance of establishing ERM’s failure and of formalizing Pareto trade-offs, and all agreed that the theoretical results are rigorous and impactful. The concerns raised by these reviewers focused on clarity, related work, or the absence of experiments, but none questioned the validity of the results, and all maintained positive scores.

The remaining reviewer gave a score of 2, concerning on the lack of experiments and practical algorithms as the main reason for rejection after rebuttal. While they recognized the theoretical contributions, they did not consider them sufficient in isolation. This reflects a mismatch of expectations: the paper is explicitly a theoretical contribution, and NeurIPS has long valued fundamental theoretical insights even without empirical validation. No reviewer identified flaws in the theory itself after rebuttal. Given the solid positive consensus from three reviewers and the potential lasting impact of the insights provided, I support acceptance despite the borderline mean score.
Decision: Accept (poster)