5 papers
A Complete Characterization of Learnability for Adversarial Noisy Bandits
Steve Hanneke, Kun Wang
We study adversarial noisy bandits given a known function class . In each round, the adversary selects a function , the learner chooses an arm, and…
What is Learnable in Valiant's Theory of the Learnable?
Steve Hanneke, Anay Mehrotra, Grigoris Velegkas +1
Valiant's 1984 paper is widely credited with introducing the PAC learning model, but it, in fact, introduced a different model: unlike PAC learning, the learner receives only posit…
Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
Idan Attias, Steve Hanneke, Arvind Ramaswami
Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner. However, the S…
Revisiting Agnostic PAC Learning
Steve Hanneke, Kasper Green Larsen, Nikita Zhivotovskiy
PAC learning, dating back to Valiant'84 and Vapnik and Chervonenkis'64,'74, is a classic model for studying supervised learning. In the agnostic setting, we have access to a hypoth…
Localization of VC Classes: Beyond Local Rademacher Complexities
Nikita Zhivotovskiy, Steve Hanneke
In this paper we introduce an alternative localization approach for binary classification that leads to a novel complexity measure: fixed points of the local empirical entropy. We…