1 citations · 1 across the 17 of their papers we have counts for
21 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…
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…
We Should Separate Memorization from Copyright
Adi Haviv, Niva Elkin-Koren, Uri Hacohen +2
The widespread use of foundation models has introduced a new risk factor of copyright issue. This issue is leading to an active, lively and on-going debate amongst the data-science…
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…
Reconstruction and Secrecy under Approximate Distance Queries
Shay Moran, Elizaveta Nesterova
Consider the task of locating an unknown target point using approximate distance queries: in each round, a reconstructor selects a query point and receives a noisy version of its d…
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 $…
Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness
Bogdan Chornomaz, Yonatan Koren, Shay Moran +1
We study the problem of learning in the presence of an adversary that can corrupt an fraction of the training examples with the goal of causing failure on a specific test point…
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…
Spherical dimension
Bogdan Chornomaz, Shay Moran, Tom Waknine
We introduce and study the spherical dimension, a natural topological relaxation of the VC dimension that unifies several results in learning theory where topology plays a key role…
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…
On Reductions and Representations of Learning Problems in Euclidean Spaces
Bogdan Chornomaz, Shay Moran, Tom Waknine
Many practical prediction algorithms represent inputs in Euclidean space and replace the discrete 0/1 classification loss with a real-valued surrogate loss, effectively reducing cl…
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…
The Bayesian Stability Zoo
Shay Moran, Hilla Schefler, Jonathan Shafer
We show that many definitions of stability found in the learning theory literature are equivalent to one another. We distinguish between two families of definitions of stability: d…