Lev Reyzin
YOU?
Author Swipe
View article: On sample reuse methods for answering k-wise statistical queries
On sample reuse methods for answering k-wise statistical queries Open
This paper examines the computational and sample complexity of answering $$\varvec{k}$$ -wise statistical queries, which were introduced by Blum et al. (J. ACM 50 (4), 506–519, 2003) as a generalization to the standard statistical query…
View article: Learning-Augmented Algorithms for Boolean Satisfiability
Learning-Augmented Algorithms for Boolean Satisfiability Open
Learning-augmented algorithms are a prominent recent development in beyond worst-case analysis. In this framework, a problem instance is provided with a prediction (``advice'') from a machine-learning oracle, which provides partial informa…
View article: Non-adaptive Learning of Random Hypergraphs with Queries
Non-adaptive Learning of Random Hypergraphs with Queries Open
We study the problem of learning a hidden hypergraph $G=(V,E)$ by making a single batch of queries (non-adaptively). We consider the hyperedge detection model, in which every query must be of the form: ``Does this set $S\subseteq V$ contai…
View article: Applications of Littlestone Dimension to Query Learning and to Compression
Applications of Littlestone Dimension to Query Learning and to Compression Open
In this paper we give several applications of Littlestone dimension. The first is to the model of [Angluin and Dohrn, 2017], where we extend their results for learning by equivalence queries with random counterexamples. Second, we extend t…
View article: On the Geometry of Stable Steiner Tree Instances
On the Geometry of Stable Steiner Tree Instances Open
No description supplied
View article: Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs
Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs Open
Reinforcement learning generalizes multi-armed bandit problems with additional difficulties of a longer planning horizon and unknown transition kernel. We explore a black-box reduction from discounted infinite-horizon tabular reinforcement…
View article: A Unified Analysis of Dynamic Interactive Learning
A Unified Analysis of Dynamic Interactive Learning Open
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 interactive learning as a way to model non-static user preferenc…
View article: Communication-Aware Collaborative Learning
Communication-Aware Collaborative Learning Open
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 learning with the goal of reducing communication cost at esse…
View article: Reconstructing Arbitrary Trees from Traces in the Tree Edit Distance Model
Reconstructing Arbitrary Trees from Traces in the Tree Edit Distance Model Open
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 reconstructing labeled trees. In this work, we significantly expand…
View article: Communication-Aware Collaborative Learning
Communication-Aware Collaborative Learning Open
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 learning with the goal of reducing communication cost at esse…
View article: On the Complexity of Learning a Class Ratio from Unlabeled Data
On the Complexity of Learning a Class Ratio from Unlabeled Data Open
In the problem of learning a class ratio from unlabeled data, which we call CR learning, the training data is unlabeled, and only the ratios, or proportions, of examples receiving each label are given. The goal is to learn a hypothes…
View article: On the Complexity of Learning from Label Proportions
On the Complexity of Learning from Label Proportions Open
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. The goal is to learn a hypothesis that predicts the proport…
View article: Statistical Queries and Statistical Algorithms: Foundations and Applications
Statistical Queries and Statistical Algorithms: Foundations and Applications Open
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 fundamental theory statistical queries and how how it connects to …
View article: On Biased Random Walks, Corrupted Intervals, and Learning Under\n Adversarial Design
On Biased Random Walks, Corrupted Intervals, and Learning Under\n Adversarial Design Open
We tackle some fundamental problems in probability theory on corrupted random\nprocesses on the integer line. We analyze when a biased random walk is expected\nto reach its bottommost point and when intervals of integer points can be\ndete…
View article: On Learning a Hidden Directed Graph with Path Queries
On Learning a Hidden Directed Graph with Path Queries Open
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 can access information about it with path queries. For a sou…
View article: Crowdsourced PAC Learning under Classification Noise
Crowdsourced PAC Learning under Classification Noise Open
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 workers who operate under classification noise, each with t…
View article: Crowdsourced PAC Learning under Classification Noise
Crowdsourced PAC Learning under Classification Noise Open
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 workers who operate under classification noise, each with t…
View article: On the Resilience of Bipartite Networks
On the Resilience of Bipartite Networks Open
Motivated by problems modeling the spread of infections in networks, in this paper we explore which bipartite graphs are most resilient to widespread infections under various parameter settings. Namely, we study bipartite networks with a r…
View article: Network Construction with Ordered Constraints
Network Construction with Ordered Constraints Open
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 realistic properties of real-world problems that are not ref…
View article: Sublinear-Time Adaptive Data Analysis
Sublinear-Time Adaptive Data Analysis Open
In this work, we study how to use sampling to speed up mechanisms for answering adaptive queries into datasets without reducing the accuracy of those mechanisms. This is important to do when both the datasets and the number of queries aske…
View article: Sampling Without Compromising Accuracy in Adaptive Data Analysis
Sampling Without Compromising Accuracy in Adaptive Data Analysis Open
In this work, we study how to use sampling to speed up mechanisms for answering adaptive queries into datasets without reducing the accuracy of those mechanisms. This is important to do when both the datasets and the number of queries aske…
View article: On the Complexity of Learning from Label Proportions
On the Complexity of Learning from Label Proportions Open
In the problem of learning with label proportions (also known as the problem of estimating class ratios), the training data is unlabeled, and only the proportions of examples receiving each label are given. The goal is to learn a hypothesi…
View article: Network Construction with Ordered Constraints
Network Construction with Ordered Constraints Open
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 realistic properties of real-world problems that are not ref…
View article: A simple spectral algorithm for recovering planted partitions
A simple spectral algorithm for recovering planted partitions Open
In this paper, we consider the planted partition model, in which n = ks vertices of a random graph are partitioned into k “clusters,” each of size s. Edges between vertices in the same cluster and different clusters are included with const…
View article: A Simple Spectral Algorithm for Recovering Planted Partitions
A Simple Spectral Algorithm for Recovering Planted Partitions Open
In this paper, we consider the planted partition model, in which $n = ks$ vertices of a random graph are partitioned into $k$ "clusters," each of size $s$. Edges between vertices in the same cluster and different clusters are included with…
View article: Shift-Pessimistic Active Learning Using Robust Bias-Aware Prediction
Shift-Pessimistic Active Learning Using Robust Bias-Aware Prediction Open
Existing approaches to active learning are generally optimistic about their certainty with respect to data shift between labeled and unlabeled data. They assume that unknown datapoint labels follow the inductive biases of the active learne…