# Probably Approximately Precision and Recall Learning

arXiv: https://arxiv.org/abs/2411.13029 · HTML: https://mlsanity.com/paper/2411.13029/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 37 references that are in the map.
- First posted on arXiv 20 Nov 2024.

## Builds on (most cited first, 10 of 10)

- [Assessing Generative Models via Precision and Recall](https://mlsanity.com/paper/1806.00035/) (2018)
- [Learning from positive and unlabeled data: a survey](https://mlsanity.com/paper/1811.04820/) (2018)
- [Metrics for Multi-Class Classification: an Overview](https://mlsanity.com/paper/2008.05756/) (2020)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Precision and Recall for Time Series](https://mlsanity.com/paper/1803.03639/) (2018)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Language Generation in the Limit](https://mlsanity.com/paper/2404.06757/) (2024)
- [Comprehensive Comparative Study of Multi-Label Classification Methods](https://mlsanity.com/paper/2102.07113/) (2021)
- [Multi-Label Learning with Stronger Consistency Guarantees](https://mlsanity.com/paper/2407.13746/) (2024)
- [The Optimal Approximation Factor in Density Estimation](https://mlsanity.com/paper/1902.05876/) (2019)

## Built on by (most cited first, 5 of 5)

- [Learning to Answer from Correct Demonstrations](https://mlsanity.com/paper/2510.15464/) (2025)
- [Private List Learnability vs. Online List Learnability](https://mlsanity.com/paper/2506.12856/) (2025)
- [Online Set Learning from Precision and Recall Feedback](https://mlsanity.com/paper/2605.09565/) (2026)
- [Ambiguous Online Learning](https://mlsanity.com/paper/2506.19810/) (2025)
- [On Imbalanced Regression with Hoeffding Trees](https://mlsanity.com/paper/2602.22101/) (2026)

## Abstract (arXiv)

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.