119 citations · 128 across the 7 of their papers we have counts for
8 papers · 1 filter
Applications of Littlestone dimension to query learning and to compression
Hunter Chase, James Freitag, Lev Reyzin
In this paper we give several applications of Littlestone dimension. The first is to the model of \cite{angluin2017power}, where we extend their results for learning by equivalence…
A Unified Analysis of Dynamic Interactive Learning
Xing Gao, Thomas Maranzatto, Lev Reyzin
In this paper we investigate the problem of learning evolving concepts over a combinatorial structure. Previous work by Emamjomeh-Zadeh et al. [2020] introduced dynamics into inter…
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…