7 citations · 10 across the 21 of their papers we have counts for
27 papers
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…
Optimal Mistake Bounds for Transductive Online Learning
Zachary Chase, Steve Hanneke, Shay Moran +1
We resolve a 30-year-old open problem concerning the power of unlabeled data in online learning by tightly quantifying the gap between transductive and standard online learning. In…
Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
Alon Cohen, Liad Erez, Steve Hanneke +4
The fundamental theorem of statistical learning states that binary PAC learning is governed by a single parameter -- the Vapnik-Chervonenkis (VC) dimension -- which determines both…
Private List Learnability vs. Online List Learnability
Steve Hanneke, Shay Moran, Hilla Schefler +1
This work explores the connection between differential privacy (DP) and online learning in the context of PAC list learning. In this setting, a -list learner outputs a list of $…
Data Selection for ERMs
Steve Hanneke, Shay Moran, Alexander Shlimovich +1
Learning theory has traditionally followed a model-centric approach, focusing on designing optimal algorithms for a fixed natural learning task (e.g., linear classification or regr…
On the ERM Principle in Meta-Learning
Yannay Alon, Steve Hanneke, Shay Moran +1
Classic supervised learning involves algorithms trained on labeled examples to produce a hypothesis aimed at performing well on unseen examples. Meta-learni…
Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem
Simone Fioravanti, Steve Hanneke, Shay Moran +2
This work continues to investigate the link between differentially private (DP) and online learning. Alon, Livni, Malliaris, and Moran (2019) showed that for binary concept classes…
Dual VC Dimension Obstructs Sample Compression by Embeddings
Zachary Chase, Bogdan Chornomaz, Steve Hanneke +2
This work studies embedding of arbitrary VC classes in well-behaved VC classes, focusing particularly on extremal classes. Our main result expresses an impossibility: such embeddin…
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…
Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs
Yuval Filmus, Steve Hanneke, Idan Mehalel +1
Consider the domain of multiclass classification within the adversarial online setting. What is the price of relying on bandit feedback as opposed to full information? To what exte…
A Trichotomy for Transductive Online Learning
Steve Hanneke, Shay Moran, Jonathan Shafer
We present new upper and lower bounds on the number of learner mistakes in the `transductive' online learning setting of Ben-David, Kushilevitz and Mansour (1997). This setting is…
Universal Rates for Multiclass Learning
Steve Hanneke, Shay Moran, Qian Zhang
We study universal rates for multiclass classification, establishing the optimal rates (up to log factors) for all hypothesis classes. This generalizes previous results on binary c…
Adversarial Resilience in Sequential Prediction via Abstention
Surbhi Goel, Steve Hanneke, Shay Moran +1
We study the problem of sequential prediction in the stochastic setting with an adversary that is allowed to inject clean-label adversarial (or out-of-distribution) examples. Algor…
Multiclass Online Learning and Uniform Convergence
Steve Hanneke, Shay Moran, Vinod Raman +2
We study multiclass classification in the agnostic adversarial online learning setting. As our main result, we prove that any multiclass concept class is agnostically learnable if…
Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
Yuval Filmus, Steve Hanneke, Idan Mehalel +1
A classical result in online learning characterizes the optimal mistake bound achievable by deterministic learners using the Littlestone dimension (Littlestone '88). We prove an an…
On Optimal Learning Under Targeted Data Poisoning
Steve Hanneke, Amin Karbasi, Mohammad Mahmoody +2
Consider the task of learning a hypothesis class in the presence of an adversary that can replace up to an fraction of the examples in the training set with arbit…
Fine-Grained Distribution-Dependent Learning Curves
Olivier Bousquet, Steve Hanneke, Shay Moran +2
Learning curves plot the expected error of a learning algorithm as a function of the number of labeled samples it receives from a target distribution. They are widely used as a mea…
A Theory of PAC Learnability of Partial Concept Classes
Noga Alon, Steve Hanneke, Ron Holzman +1
We extend the theory of PAC learning in a way which allows to model a rich variety of learning tasks where the data satisfy special properties that ease the learning process. For e…