# Online Set Learning from Precision and Recall Feedback

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 26 references that are in the map.
- First posted on arXiv 10 May 2026.

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

- [Assessing Generative Models via Precision and Recall](https://mlsanity.com/paper/1806.00035/) (2018)
- [Metrics for Multi-Class Classification: an Overview](https://mlsanity.com/paper/2008.05756/) (2020)
- [Precision and Recall for Time Series](https://mlsanity.com/paper/1803.03639/) (2018)
- [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)
- [Probably Approximately Precision and Recall Learning](https://mlsanity.com/paper/2411.13029/) (2024)

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

- [Multiscale Reward Hedging from Correct Demonstrations](https://mlsanity.com/paper/2608.06825/) (2026)

## Abstract (arXiv)

We consider the problem of learning an unknown subset Ntarget of a domain in an online setting. In each round t, the learner predicts a set of items Nt and receives one of two types of feedback, each with equal probability: precision feedback, in which a randomly chosen item from the predicted set Nt is revealed and the learner is told whether it belongs to Ntarget (incurring a reward if it does), or recall feedback, in which a randomly chosen item from the target set Ntarget is revealed and the learner is told whether it belongs to Nt (incurring a reward if it does). The goal is to maximize the cumulative reward over time. This simple online set learning problem abstracts a variety of learning scenarios with precision- and recall-type feedback. We show that a hypothesis class (a family of subsets of the domain) is learnable in this setting if and only if it has finite Vapnik-Chervonenkis (VC) dimension, mirroring the classical PAC characterization. However, the resulting algorithmic structure is markedly more intricate: in contrast to standard Probably Approximately Correct (PAC) learning -- where the algorithmic landscape is governed by the simple principle of Empirical Risk Minimization (ERM) -- our partial feedback model can invalidate ERM and even all proper learning rules. We develop algorithms to address the dependencies induced by the feedback, obtaining regret guarantees in both the realizable and agnostic settings. Our results provide a qualitative characterization of learnability in this model, addressing its most basic question, while pointing to a range of natural and intriguing open questions, including the determination of optimal regret rates.