research
∙
08/07/2023
Matrix Completion in Almost-Verification Time
We give a new framework for solving the fundamental problem of low-rank ...
share
research
∙
07/18/2023
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination
We consider the question of Gaussian mean testing, a fundamental task in...
research
∙
07/13/2023
Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems
Recently Chen and Poor initiated the study of learning mixtures of linea...
research
∙
01/23/2023
A New Approach to Learning Linear Dynamical Systems
Linear dynamical systems are the foundational statistical model upon whi...
research
∙
07/25/2022
Minimax Rates for Robust Community Detection
In this work, we study the problem of community detection in the stochas...
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
∙
04/14/2022
Tight Bounds for Quantum State Certification with Incoherent Measurements
We consider the problem of quantum state certification, where we are giv...
research
∙
03/08/2022
Semi-Random Sparse Recovery in Nearly-Linear Time
Sparse recovery is one of the most fundamental and well-studied inverse ...
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
∙
12/13/2021
Robust Voting Rules from Algorithmic Robust Statistics
In this work we study the problem of robustly learning a Mallows model. ...
research
∙
12/01/2021
Clustering Mixtures with Almost Optimal Separation in Polynomial Time
We consider the problem of clustering mixtures of mean-separated Gaussia...
research
∙
11/15/2021
Margin-Independent Online Multiclass Learning via Convex Geometry
We consider the problem of multi-class classification, where a stream of...
research
∙
06/05/2021
Sparsification for Sums of Exponentials and its Algorithmic Applications
Many works in signal processing and learning theory operate under the as...
research
∙
06/04/2021
How to Decompose a Tensor with Group Structure
In this work we study the orbit recovery problem, which is a natural abs...
research
∙
04/19/2021
Learning GMMs with Nearly Optimal Robustness Guarantees
In this work we solve the problem of robustly learning a high-dimensiona...
research
∙
11/06/2020
Settling the Robust Learnability of Mixtures of Gaussians
This work represents a natural coalescence of two important lines of wor...
research
∙
06/04/2020
Tensor Completion Made Practical
Tensor completion is a natural higher-order generalization of matrix com...
research
∙
04/21/2020
Competing Optimally Against An Imperfect Prophet
Consider a gambler who observes the realizations of n independent, non-n...
research
∙
03/03/2020
Contextual Search for General Hypothesis Classes
We study a general version of the problem of online learning under binar...
research
∙
02/19/2019
Fourier and Circulant Matrices are Not Rigid
The concept of matrix rigidity was first introduced by Valiant in [Val77...
research
∙
08/17/2018