49 citations · 234 across the 21 of their papers we have counts for
14 papers · 1 filter
Adversarially-Robust Inference on Trees via Belief Propagation
Samuel B. Hopkins, Anqi Li
We introduce and study the problem of posterior inference on tree-structured graphical models in the presence of a malicious adversary who can corrupt some observed nodes. In the w…
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination
Clément L. Canonne, Samuel B. Hopkins, Jerry Li +2
We consider the question of Gaussian mean testing, a fundamental task in high-dimensional distribution testing and signal processing, subject to adversarial corruptions of the samp…
Robustness Implies Privacy in Statistical Estimation
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid +1
We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to…
Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid
We give the first polynomial-time algorithm to estimate the mean of a -variate probability distribution with bounded covariance from independent samples subject t…
Matrix Discrepancy from Quantum Communication
Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty
We develop a novel connection between discrepancy minimization and (quantum) communication complexity. As an application, we resolve a substantial special case of the Matrix Spence…
Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks
Jingqiu Ding, Samuel B. Hopkins, David Steurer
We study symmetric spiked matrix models with respect to a general class of noise distributions. Given a rank-1 deformation of a random noise matrix, whose entries are independently…
Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization
Samuel B. Hopkins, Jerry Li, Fred Zhang
We study the problem of estimating the mean of a distribution in high dimensions when either the samples are adversarially corrupted or the distribution is heavy-tailed. Recent dev…
Robustly Learning any Clusterable Mixture of Gaussians
Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane +1
We study the efficient learnability of high-dimensional Gaussian mixtures in the outlier-robust setting, where a small constant fraction of the data is adversarially corrupted. We…
Subexponential LPs Approximate Max-Cut
Samuel B. Hopkins, Tselil Schramm, Luca Trevisan
We show that for every , the degree- Sherali-Adams linear program (with variables and constraints) approximates the…
Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection
Yihe Dong, Samuel B. Hopkins, Jerry Li
We study two problems in high-dimensional robust statistics: \emph{robust mean estimation} and \emph{outlier detection}. In robust mean estimation the goal is to estimate the mean…
Mixture Models, Robustness, and Sum of Squares Proofs
Samuel B. Hopkins, Jerry Li
We use the Sum of Squares method to develop new efficient algorithms for learning well-separated mixtures of Gaussians and robust mean estimation, both in high dimensions, that sub…
The power of sum-of-squares for detecting hidden structures
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin +3
We study planted problems---finding hidden structures in random noisy inputs---through the lens of the sum-of-squares semidefinite programming hierarchy (SoS). This family of power…
Bayesian estimation from few samples: community detection and related problems
Samuel B. Hopkins, David Steurer
We propose an efficient meta-algorithm for Bayesian estimation problems that is based on low-degree polynomials, semidefinite programming, and tensor decomposition. The algorithm i…
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi +1
We consider two problems that arise in machine learning applications: the problem of recovering a planted sparse vector in a random linear subspace and the problem of decomposing a…