research
∙
05/17/2023
Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions
We study robust community detection in the context of node-corrupted sto...
share
research
∙
02/21/2023
Robust Mean Estimation Without a Mean: Dimension-Independent Error in Polynomial Time for Symmetric Distributions
In this work, we study the problem of robustly estimating the mean/locat...
research
∙
01/11/2023
Private estimation algorithms for stochastic block models and mixture models
We introduce general tools for designing efficient private estimation al...
research
∙
12/11/2022
Algorithms approaching the threshold for semi-random planted clique
We design new polynomial-time algorithms for recovering planted cliques ...
research
∙
11/14/2022
Higher degree sum-of-squares relaxations robust against oblivious outliers
We consider estimation models of the form Y=X^*+N, where X^* is some m-d...
research
∙
02/14/2022
Fast algorithm for overcomplete order-3 tensor decomposition
We develop the first fast spectral algorithm to decompose a random third...
research
∙
12/10/2021
Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures
We consider mixtures of k≥ 2 Gaussian components with unknown means and ...
research
∙
11/16/2021
Robust recovery for stochastic block models
We develop an efficient algorithm for weak recovery in a robust version ...
research
∙
11/04/2021
Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers
We develop machinery to design efficiently computable and consistent est...
research
∙
01/05/2021
SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation
We develop a general framework to significantly reduce the degree of sum...
research
∙
11/12/2020
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
We study efficient algorithms for Sparse PCA in standard statistical mod...
research
∙
09/30/2020
Regress Consistently when Oblivious Outliers Overwhelm
We give a novel analysis of the Huber loss estimator for consistent robu...
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
∙
06/17/2020
Playing Unique Games on Certified Small-Set Expanders
We give an algorithm for solving unique games (UG) instances whose const...
research
∙
07/30/2018
High-dimensional estimation via sum-of-squares proofs
Estimation is the computational task of recovering a hidden parameter x ...
research
∙
04/23/2018
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture
Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (...
research
∙
11/30/2017
Outlier-robust moment-estimation via sum-of-squares
We develop efficient algorithms for estimating low-degree moments of unk...
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
∙
06/27/2017
Fast and robust tensor decomposition with applications to dictionary learning
We develop fast spectral algorithms for tensor decomposition that match ...
research
∙
02/21/2017
Exact tensor completion with sum-of-squares
We obtain the first polynomial-time algorithm for exact tensor completio...
research
∙
12/08/2015
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
We consider two problems that arise in machine learning applications: th...
research
∙
07/06/2014