research
∙
06/03/2023
Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits
We study pure exploration with infinitely many bandit arms generated i.i...
share
research
∙
06/03/2023
On Size-Independent Sample Complexity of ReLU Networks
We study the sample complexity of learning ReLU neural networks from the...
research
∙
06/03/2023
Incentivizing Exploration with Linear Contexts and Combinatorial Actions
We advance the study of incentivized bandit exploration, in which arm ch...
research
∙
04/04/2023
Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
We investigate one of the most basic problems in streaming algorithms: a...
research
∙
03/21/2023
Algorithmic Threshold for Multi-Species Spherical Spin Glasses
We study efficient optimization of the Hamiltonians of multi-species sph...
research
∙
06/10/2022
Tight Bounds for State Tomography with Incoherent Measurements
We consider the classic question of state tomography: given copies of an...
research
∙
03/10/2022
Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization
We consider the Sherrington-Kirkpatrick model of spin glasses at high-te...
research
∙
02/19/2022
The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication
We study the stochastic multi-player multi-armed bandit problem. In this...
research
∙
11/12/2021
Local algorithms for Maximum Cut and Minimum Bisection on locally treelike regular graphs of large degree
Given a graph G of degree k over n vertices, we consider the problem of ...
research
∙
10/15/2021
Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
We study the problem of algorithmically optimizing the Hamiltonian H_N o...
research
∙
06/18/2021
Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments
Domain generalization aims at performing well on unseen test environment...
research
∙
05/26/2021
A Universal Law of Robustness via Isoperimetry
Classically, data interpolation with a parametrized model class is possi...
research
∙
11/23/2020
Functions that Preserve Manhattan Distances
What functions, when applied to the pairwise Manhattan distances between...
research
∙
11/08/2020
Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions
We consider the cooperative multi-player version of the stochastic multi...
research
∙
10/29/2020
Algorithmic pure states for the negative spherical perceptron
We consider the spherical perceptron with Gaussian disorder. This is the...
research
∙
09/17/2020
Metrical Service Systems with Transformations
We consider a generalization of the fundamental online metrical service ...
research
∙
07/15/2020
Vertex Sparsification for Edge Connectivity
Graph compression or sparsification is a basic information-theoretic and...
research
∙
04/15/2020
Online Multiserver Convex Chasing and Optimization
We introduce the problem of k-chasing of convex functions, a simultaneou...
research
∙
02/03/2020
Sample Complexity of Incentivized Exploration
We consider incentivized exploration: a version of multi-armed bandits w...
research
∙
10/23/2019
Vertex Sparsifiers for c-Edge Connectivity
We show the existence of O(f(c)k) sized vertex sparsifiers that preserve...
research
∙
05/28/2019
Chasing Convex Bodies Optimally
In the chasing convex bodies problem, an online player receives a reques...
research
∙
04/28/2019
Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without
We consider the non-stochastic version of the (cooperative) multi-player...
research
∙
02/02/2019
First-Order Regret Analysis of Thompson Sampling
We address online combinatorial optimization when the player has a prior...
research
∙
11/02/2018
Chasing Nested Convex Bodies Nearly Optimally
The convex body chasing problem, introduced by Friedman and Linial, is a...
research
∙
11/02/2018
Competitively Chasing Convex Bodies
Let F be a family of sets in some metric space. In the F-chasing problem...
research
∙
10/31/2017