119 citations · 128 across the 5 of their papers we have counts for
6 papers
Statistical Queries and Statistical Algorithms: Foundations and Applications
Lev Reyzin
We give a survey of the foundations of statistical queries and their many applications to other areas. We introduce the model, give the main definitions, and we explore the fundame…
On the Complexity of Learning from Label Proportions
Benjamin Fish, Lev Reyzin
In the problem of learning with label proportions, which we call LLP learning, the training data is unlabeled, and only the proportions of examples receiving each label are given.…
On Biased Random Walks, Corrupted Intervals, and Learning Under Adversarial Design
Daniel Berend, Aryeh Kontorovich, Lev Reyzin +1
We tackle some fundamental problems in probability theory on corrupted random processes on the integer line. We analyze when a biased random walk is expected to reach its bottommos…
Crowdsourced PAC Learning under Classification Noise
Shelby Heinecke, Lev Reyzin
In this paper, we analyze PAC learnability from labels produced by crowdsourcing. In our setting, unlabeled examples are drawn from a distribution and labels are crowdsourced from…
Network Construction with Ordered Constraints
Yi Huang, Mano Vikash Janardhanan, Lev Reyzin
In this paper, we study the problem of constructing a network by observing ordered connectivity constraints, which we define herein. These ordered constraints are made to capture r…
Efficient Optimal Learning for Contextual Bandits
Miroslav Dudik, Daniel Hsu, Satyen Kale +4
We address the problem of learning in an online setting where the learner repeatedly observes features, selects among a set of actions, and receives reward for the action taken. We…