12 papers
PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
Steve Hanneke, Qinglin Meng, Shay Moran +1
We study the problem of multiclass PAC learning with bandit feedback in the realizable setting. In this framework, there is an unknown data distribution over an instance space $\ma…
On the Learning Curves of Revenue Maximization
Steve Hanneke, Alkis Kalavasis, Shay Moran +1
Learning curves are a fundamental primitive in supervised learning, describing how an algorithm's performance improves with more data and providing a quantitative measure of its ge…
Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End
Steve Hanneke, Idan Mehalel, Shay Moran
Modern large language models generate text autoregressively, producing tokens one at a time. To study the learnability of such systems, Joshi et al. (COLT 2025) introduced a PAC-le…
An Optimal Sauer Lemma Over -ary Alphabets
Steve Hanneke, Qinglin Meng, Shay Moran +1
The Sauer-Shelah-Perles Lemma is a cornerstone of combinatorics and learning theory, bounding the size of a binary hypothesis class in terms of its Vapnik-Chervonenkis (VC) dimensi…
List Sample Compression and Uniform Convergence
Steve Hanneke, Shay Moran, Tom Waknine
List learning is a variant of supervised classification where the learner outputs multiple plausible labels for each instance rather than just one. We investigate classical princip…
A Theory of Universal Agnostic Learning
Steve Hanneke, Shay Moran
We provide a complete theory of optimal universal rates for binary classification in the agnostic setting. This extends the realizable-case theory of Bousquet, Hanneke, Moran, van…