Research map / Bandits and online learning / Online convex optimization and games

Online Set Learning from Precision and Recall Feedback

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Online learning with feedback graphs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Characterizes online learnability of unknown subsets from random precision/recall feedback, showing learnability iff finite VC dimension, with O(d log^2 T) realizable and Õ(d^{1/4}T^{3/4}) agnostic regret.

Problem

Learning an unknown target subset of a domain online when the learner only receives item-level precision feedback (on a sampled predicted item) or recall feedback (on a sampled target item), with the goal of maximizing cumulative precision-recall reward.

Approach

Abstracts set prediction evaluation into a bandit-style precision and full-information-style recall feedback model; shows recall feedback alone suffices in the realizable case via a minimum-size consistent hypothesis, and in the agnostic case uses an improper fallback (empty set) plus an estimator of target set size to estimate precision from recall and precision feedback.

Key results

• Realizable setting: a minimum-size recall-consistent hypothesis achieves regret O(d log^2 T) (Theorem: (d log T + log(T/δ)) log T), with an Ω(d) lower bound.
• Agnostic setting: the APRIL algorithm achieves regret Õ(d^{1/4} T^{3/4}), and O(sqrt(Td log(T/d))) when the optimality margin is at least a constant.
• Proper learning fails in the agnostic setting: for a VC-dimension-1 class there is an instance where any proper learner incurs regret at least C·T.

Surprising findings

• Arbitrary recall-consistent ERM fails in the realizable setting; only a minimum-size consistent hypothesis works.
• Proper learning rules cannot achieve sublinear regret in the agnostic setting even for VC dimension 1 classes.

Limitations

• Gap of log^2 T between upper and lower regret bounds in the realizable case.
• Agnostic regret Õ(d^{1/4}T^{3/4}) is likely suboptimal relative to the sqrt(dT) target.
• Analysis assumes the available set X is known and that both feedback types are observed per round (simplification).

Experimental setup

Metrics: regret

Baselines: EXP3 ERM over recall-consistent hypotheses

Builds on: Empirical Risk Minimization Littlestone dimension mistake bound (Halving-type online learning) EXP3 PAC learning

Closest papers by meaning

• Understanding the Role of Feedback in Online Learning with Switching Costs (ICML 2023 · similarity 0.88)
• Probably Approximately Precision and Recall Learning (NeurIPS 2025 · similarity 0.88)
• Online Learning with Unknown Constraints (ICML 2025 · similarity 0.87)
• Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · similarity 0.87)
• Online Learning with Sublinear Best-Action Queries (NeurIPS 2024 · similarity 0.86)
• From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.86)