A hypothesis class is learnable in this online precision-recall feedback model if and only if it has finite VC dimension, with algorithms achieving regret bounds in realizable and agnostic settings despite ERM failing.
Machine learning , volume=
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
fields
cs.LG 3years
2026 3verdicts
UNVERDICTED 3representative citing papers
A dynamic pruning reduction from agnostic to realizable online learning via weak-consistency oracles achieves O(T^{d_VC+1}) query complexity with near-optimal regret and supplies matching upper and lower bounds on the regret-oracle tradeoff.
Defines mistake-bounded generation and gives an algorithm for finite classes achieving optimal last-mistake time Cdim(L) with floor(log2 |L|) mistakes, plus a trade-off for infinite classes and noisy extensions.
citing papers explorer
-
Online Set Learning from Precision and Recall Feedback
A hypothesis class is learnable in this online precision-recall feedback model if and only if it has finite VC dimension, with algorithms achieving regret bounds in realizable and agnostic settings despite ERM failing.
-
Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
A dynamic pruning reduction from agnostic to realizable online learning via weak-consistency oracles achieves O(T^{d_VC+1}) query complexity with near-optimal regret and supplies matching upper and lower bounds on the regret-oracle tradeoff.
-
Mistake-Bounded Language Generation
Defines mistake-bounded generation and gives an algorithm for finite classes achieving optimal last-mistake time Cdim(L) with floor(log2 |L|) mistakes, plus a trade-off for infinite classes and noisy extensions.