Probably Approximately Precision and Recall Learning

We thank the reviewer for their positive and insightful feedback. In what follows, we address comments and questions.

• Clarity for Non-Theorists: Thank you for the feedback. We will add more details and provide intuition to clarify the proofs for future readers.

• 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.

• On Practical Impact and Real-World Feasibility: Thank 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.

• 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. The 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.

• 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.

• Improving Accessibility: We will add more intuitive explanations after each result.

We thank the reviewer for their feedback. In what follows, we address comments and questions.

Finite hypothesis class

Note 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.

In 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.

For 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.

PU learning

Thanks. We’ll add a discussion in the related work on PU learning. In particular, while there are only positive examples in the PU model, the unlabeled examples provide significant information about the (potentially) negative examples.

Why ERM fails

When 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

As noted in Line 190, the observed label $v_i$ is drawn uniformly at random from the ground-truth set $G_{\text{target}}(x_i)$.

In 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$).

Thus, 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.

Computational complexity

Our 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.

While 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.

Moreover, 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.

We 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.

Definitions of G' and G'' in algorithm 2

$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]$.

Each entry of the vector $v_G$ corresponds to a pair $(G', G'') \in \mathcal{H} \times \mathcal{H}$ and can be written explicitly as

where $n_G(x_i) = |G(x_i)|$. We will clarify this in the revised version.

Why obtaining an unbiased estimation of precision loss is not possible

We’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)$. As 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.

``at line 100…''

Thanks 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.

Despite 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.

In 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.

Computational complexity of algorithm 1

Like 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.

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.

We thank the reviewer for their positive and insightful feedback.

Regarding the optimal multiplicative constant: we agree that precisely characterizing this constant is an intriguing open problem, which we leave for future exploration.

We 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.

[1] Devroye and Lugosi, “Combinatorial Methods in Density Estimation,” Springer, 2001.

[2] Bousquet, Kane, and Moran, “The Optimal Approximation Factor in Density Estimation,” COLT 2019.