research
∙
07/30/2023
Towards Practical Robustness Auditing for Linear Regression
We investigate practical algorithms to find or disprove the existence of...
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
∙
12/09/2022
Robustness Implies Privacy in Statistical Estimation
We study the relationship between adversarial robustness and differentia...
research
∙
11/01/2022
Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation
We establish a simple connection between robust and differentially-priva...
research
∙
05/19/2022
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
Many high-dimensional statistical inference problems are believed to pos...
research
∙
03/05/2022
A Robust Spectral Algorithm for Overcomplete Tensor Decomposition
We give a spectral algorithm for decomposing overcomplete order-4 tensor...
research
∙
11/25/2021
Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
We give the first polynomial-time algorithm to estimate the mean of a d-...
research
∙
10/19/2021
Matrix Discrepancy from Quantum Communication
We develop a novel connection between discrepancy minimization and (quan...
research
∙
09/13/2020
Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
Researchers currently use a number of approaches to predict and substant...
research
∙
08/31/2020
Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks
We study symmetric spiked matrix models with respect to a general class ...
research
∙
07/31/2020
Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization
We study the problem of estimating the mean of a distribution in high di...
research
∙
07/21/2020
Smoothed Complexity of 2-player Nash Equilibria
We prove that computing a Nash equilibrium of a two-player (n × n) game ...
research
∙
05/13/2020
Robustly Learning any Clusterable Mixture of Gaussians
We study the efficient learnability of high-dimensional Gaussian mixture...
research
∙
12/23/2019
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
We study efficient algorithms for linear regression and covariance estim...
research
∙
11/23/2019
Subexponential LPs Approximate Max-Cut
We show that for every ε > 0, the degree-n^ε Sherali-Adams linear progra...
research
∙
06/26/2019
Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection
We study two problems in high-dimensional robust statistics: robust mean...
research
∙
03/19/2019
How Hard Is Robust Mean Estimation?
Robust mean estimation is the problem of estimating the mean μ∈R^d of a ...
research
∙
09/19/2018
Mean Estimation with Sub-Gaussian Rates in Polynomial Time
We study polynomial time algorithms for estimating the mean of a heavy-t...
research
∙
09/19/2018
Sub-Gaussian Mean Estimation in Polynomial Time
We study polynomial time algorithms for estimating the mean of a random ...
research
∙
11/20/2017
Mixture Models, Robustness, and Sum of Squares Proofs
We use the Sum of Squares method to develop new efficient algorithms for...
research
∙
10/13/2017
The power of sum-of-squares for detecting hidden structures
We study planted problems---finding hidden structures in random noisy in...
research
∙
09/30/2017
Bayesian estimation from few samples: community detection and related problems
We propose an efficient meta-algorithm for Bayesian estimation problems ...
research
∙
12/08/2015