7 citations · 10 across the 21 of their papers we have counts for
7 papers · 1 filter
Uniform convergence at optimal rate and scale
Noga Alon, Steve Hanneke, Shay Moran +1
Uniform convergence asks how many random samples suffice for empirical averages to approximate expectations simultaneously over an entire class of functions. It is a central concep…
The optimal information complexity of VC learning
Steve Hanneke, Juexiao Wang
Steinke and Zakynthinou(2020) introduces the Conditional Mutual Information (CMI) framework of analyzing the information complexity of learning algorithms based on algorithm-depend…
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…
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…