Online Set Learning from Precision and Recall Feedback

We consider the problem of learning an unknown subset $N^{target}$ of a domain in an online setting. % In each round $t$, the learner predicts a set of items ${N}_t$ and receives one of two types of feedback, each with equal probability: {\it precision feedback}, in which a randomly chosen item from the predicted set $N_t$ is revealed and the learner is told whether it belongs to $N^{target}$ (incurring a reward if it does), or {\it recall feedback}, in which a randomly chosen item from the target set $N^{target}$ is revealed and the learner is told whether it belongs to $N_t$ (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.