9 papers
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…