mlsanityData to 7 Oct 2026

Robust Sparse Mean Estimation via Sum of Squares

arXiv 2206.03441 ↗First posted 7 Jun 2022cs.DS cs.LG math.STcited by 23

Not on the map. Why?

Abstract (arXiv)

We study the problem of high-dimensional sparse mean estimation in the presence of an ε-fraction of adversarial outliers. Prior work obtained sample and computationally efficient algorithms for this task for identity-covariance subgaussian distributions. In this work, we develop the first efficient algorithms for robust sparse mean estimation without a priori knowledge of the covariance. For distributions on mathbb Rd with "certifiably bounded" t-th moments and sufficiently light tails, our algorithm achieves error of O(ε1-1/t) with sample complexity m = (klog(d))O(t)/ε2-2/t. For the special case of the Gaussian distribution, our algorithm achieves near-optimal error of tilde O(ε) with sample complexity m = O(k4 polylog(d))/ε2. Our algorithms follow the Sum-of-Squares based, proofs to algorithms approach. We complement our upper bounds with Statistical Query and low-degree polynomial testing lower bounds, providing evidence that the sample-time-error tradeoffs achieved by our algorithms are qualitatively the best possible.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Builds on 34 of its 64 references that are in the map. First posted on arXiv 7 Jun 2022.

Builds on

34 of 64 references.

References · 34

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2016Agnostic Estimation of Mean and Covariancecited by 131
  3. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
  4. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  5. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  6. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  7. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 82
  8. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  9. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  10. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  11. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  12. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
22 more
  1. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  2. 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 50
  3. 2020Outlier Robust Mean Estimation with Subgaussian Rates via Stabilitycited by 50
  4. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 49
  5. 2015Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Modelcited by 47
  6. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  7. 2020Robust Linear Regression: Optimal Rates in Polynomial Timecited by 42
  8. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
  9. 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
  10. 2019Robust subgaussian estimation of a mean vector in nearly linear timecited by 37
  11. 2020Settling the Robust Learnability of Mixtures of Gaussianscited by 32
  12. 2019Faster Algorithms for High-Dimensional Robust Covariance Estimationcited by 28
  13. 2020Robustly Learning any Clusterable Mixture of Gaussianscited by 28
  14. 2017Outlier-robust moment-estimation via sum-of-squarescited by 27
  15. 2019Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filteringcited by 23
  16. 2017Better Agnostic Clustering Via Relaxed Tensor Normscited by 21
  17. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  18. 2020List-Decodable Mean Estimation via Iterative Multi-Filteringcited by 18
  19. 2020List-Decodable Mean Estimation in Nearly-PCA Timecited by 17
  20. 2021Outlier-Robust Sparse Estimation via Non-Convex Optimizationcited by 14
  21. 2021Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimallycited by 14
  22. 2019A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Ratescited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 6; 2024: 8; 2025: 3; 2026: 2.

23 papers.

Sort:

  1. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  2. 2022Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problemscited by 16
  3. 2022List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filteringcited by 13
  4. 2022Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributionscited by 13
  5. 2022Estimation Contracts for Outlier-Robust Geometric Perceptioncited by 11
  6. 2023Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCAcited by 10
  7. 2024SoS Certifiability of Subgaussian Distributions and its Algorithmic Applicationscited by 10
  8. 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
  9. 2024Efficient PAC Learning of Halfspaces with Constant Malicious Noise Ratecited by 5
  10. 2023Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noisecited by 3
  11. 2024SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and Morecited by 3
  12. 2024Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contaminationcited by 2
11 more
  1. 2024Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Errorcited by 2
  2. 2024A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimationcited by 1
  3. 2024Robust Sparse Regression with Non-Isotropic Designscited by 1
  4. 2025PTF Testing Lower Bounds for Non-Gaussian Component Analysiscited by 1
  5. 2023Flag Aggregator: Scalable Distributed Training under Failures and Augmented Losses using Convex Optimizationcited by 0
  6. 2023Sparse Mean Estimation in Adversarial Settings via Incremental Learningcited by 0
  7. 2024Sparse Linear Regression when Noises and Covariates are Heavy-Tailed and Contaminated by Outlierscited by 0
  8. 2025Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussianscited by 0
  9. 2025Batch List-Decodable Linear Regression via Higher Momentscited by 0
  10. 2026Algorithms with Polynomially-Improved Approximation Factors for the 2 rightarrow q Norm, and Applicationscited by 0
  11. 2026Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterizationcited by 0