182 citations · 328 across the 20 of their papers we have counts for
23 papers
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…
Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs
Ian A. Kash, Lev Reyzin, Zishun Yu
Reinforcement learning generalizes multi-armed bandit problems with additional difficulties of a longer planning horizon and unknown transition kernel. We explore a black-box reduc…
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…
On the Geometry of Stable Steiner Tree Instances
James Freitag, Neshat Mohammadi, Aditya Potukuchi +1
In this note we consider the Steiner tree problem under Bilu-Linial stability. We give strong geometric structural properties that need to be satisfied by stable instances. We then…
Reconstructing Arbitrary Trees from Traces in the Tree Edit Distance Model
Thomas Maranzatto
In this paper, we consider the problem of reconstructing trees from traces in the tree edit distance model. Previous work by Davies et al. (2019) analyzed special cases of reconstr…
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…