49 citations · 234 across the 21 of their papers we have counts for
28 papers
Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares
Gavin Brown, Jonathan Hayase, Samuel Hopkins +5
We present a sample- and time-efficient differentially private algorithm for ordinary least squares, with error that depends linearly on the dimension and is independent of the con…
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…
Towards Practical Robustness Auditing for Linear Regression
Daniel Freund, Samuel B. Hopkins
We investigate practical algorithms to find or disprove the existence of small subsets of a dataset which, when removed, reverse the sign of a coefficient in an ordinary least squa…
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…
Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions
Gavin Brown, Samuel B. Hopkins, Adam Smith
We present a fast, differentially private algorithm for high-dimensional covariance-aware mean estimation with nearly optimal sample complexity. Only exponential-time estimators we…
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…
Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation
Kristian Georgiev, Samuel B. Hopkins
We establish a simple connection between robust and differentially-private algorithms: private mechanisms which perform well with very high probability are automatically robust in…
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins +3
Many high-dimensional statistical inference problems are believed to possess inherent computational hardness. Various frameworks have been proposed to give rigorous evidence for su…
A Robust Spectral Algorithm for Overcomplete Tensor Decomposition
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi
We give a spectral algorithm for decomposing overcomplete order-4 tensors, so long as their components satisfy an algebraic non-degeneracy condition that holds for nearly all (all…
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…
Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
Matthew Brennan, Guy Bresler, Samuel B. Hopkins +2
Researchers currently use a number of approaches to predict and substantiate information-computation gaps in high-dimensional statistical estimation problems. A prominent approach…
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…
Smoothed Complexity of 2-player Nash Equilibria
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins +1
We prove that computing a Nash equilibrium of a two-player () game with payoffs in is PPAD-hard (under randomized reductions) even in the smoothed analysis set…
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…
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria +2
We study efficient algorithms for linear regression and covariance estimation in the absence of Gaussian assumptions on the underlying distributions of samples, making assumptions…
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…
How Hard Is Robust Mean Estimation?
Samuel B. Hopkins, Jerry Li
Robust mean estimation is the problem of estimating the mean of a -dimensional distribution from a list of independent samples, an -fraction of which…
Mean Estimation with Sub-Gaussian Rates in Polynomial Time
Samuel B. Hopkins
We study polynomial time algorithms for estimating the mean of a heavy-tailed multivariate random vector. We assume only that the random vector has finite mean and covariance.…
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…