55 citations · 62 across the 9 of their papers we have counts for
9 papers
Uniform Convergence Beyond Glivenko-Cantelli
Tanmay Devale, Pramith Devulapalli, Steve Hanneke
We characterize conditions under which collections of distributions on admit uniform estimation of their mean. Prior work from Vapnik and Chervonenkis (1971) h…
Learning from Snapshots of Discrete and Continuous Data Streams
Pramith Devulapalli, Steve Hanneke
Imagine a smart camera trap selectively clicking pictures to understand animal movement patterns within a particular habitat. These "snapshots", or pieces of data captured from a d…
A Complete Characterization of Learnability for Stochastic Noisy Bandits
Steve Hanneke, Kun Wang
We study the stochastic noisy bandit problem with an unknown reward function in a known function class . Formally, a model maps arms to a probability dis…
The Dimension of Self-Directed Learning
Pramith Devulapalli, Steve Hanneke
Understanding the self-directed learning complexity has been an important problem that has captured the attention of the online learning theory community since the early 1990s. Wit…
Universally Consistent Online Learning with Arbitrarily Dependent Responses
Steve Hanneke
This work provides an online learning rule that is universally consistent under processes on (X,Y) pairs, under conditions only on the X process. As a special case, the conditions…
Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?
Steve Hanneke
This open problem asks whether there exists an online learning algorithm for binary classification that guarantees, for all target concepts, to make a sublinear number of mistakes,…
Actively Avoiding Nonsense in Generative Models
Steve Hanneke, Adam Kalai, Gautam Kamath +1
A generative model may generate utter nonsense when it is fit to maximize the likelihood of observed data. This happens due to "model error," i.e., when the true data generating di…
The Optimal Sample Complexity of PAC Learning
Steve Hanneke
This work establishes a new upper bound on the number of samples sufficient for PAC learning in the realizable case. The bound matches known lower bounds up to numerical constant f…
A Compression Technique for Analyzing Disagreement-Based Active Learning
Yair Wiener, Steve Hanneke, Ran El-Yaniv
We introduce a new and improved characterization of the label complexity of disagreement-based active learning, in which the leading quantity is the version space compression set s…