182 citations · 328 across the 20 of their papers we have counts for
5 papers · 1 filter
Communication-Aware Collaborative Learning
Avrim Blum, Shelby Heinecke, Lev Reyzin
Algorithms for noiseless collaborative PAC learning have been analyzed and optimized in recent years with respect to sample complexity. In this paper, we study collaborative PAC le…
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…
On Learning a Hidden Directed Graph with Path Queries
Mano Vikash Janardhanan, Lev Reyzin
In this paper, we consider the problem of reconstructing a directed graph using path queries. In this query model of learning, a graph is hidden from the learner, and the learner c…