mlsanityData to 14 Oct 2026

Outlier-robust moment-estimation via sum-of-squares

arXiv 1711.11581 ↗First posted 30 Nov 2017cs.DS cs.LG stat.MLcited by 27

Not on the map. Why?

Abstract (arXiv)

We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers. The guarantees of our algorithms improve in many cases significantly over the best previous ones, obtained in recent works of Diakonikolas et al, Lai et al, and Charikar et al. We also show that the guarantees of our algorithms match information-theoretic lower-bounds for the class of distributions we consider. These improved guarantees allow us to give improved algorithms for independent component analysis and learning mixtures of Gaussians in the presence of outliers. Our algorithms are based on a standard sum-of-squares relaxation of the following conceptually-simple optimization problem: Among all distributions whose moments are bounded in the same way as for the unknown distribution, find the one that is closest in statistical distance to the empirical distribution of the adversarially-corrupted sample.

Key facts. Cited by 27 papers in the map (data through 14 Oct 2026). First posted on arXiv 30 Nov 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 4; 2023: 4; 2024: 7; 2025: 3; 2026: 4.

27 papers.

Sort:

  1. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  2. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  3. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  4. 2024How Does Unlabeled Data Provably Help Out-of-Distribution Detection?cited by 36
  5. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 24
  6. 2023A New Approach to Learning Linear Dynamical Systemscited by 23
  7. 2022List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filteringcited by 13
  8. 2024SoS Certifiability of Subgaussian Distributions and its Algorithmic Applicationscited by 10
  9. 2022List-Decodable Covariance Estimationcited by 8
  10. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7
  11. 2025The Power of Iterative Filtering for Supervised Learning with (Heavy) Contaminationcited by 7
  12. 2021Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixturescited by 5
15 more
  1. 2023Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Errorcited by 4
  2. 2024Efficient Certificates of Anti-Concentration Beyond Gaussianscited by 4
  3. 2024SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and Morecited by 3
  4. 2024Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Errorcited by 2
  5. 2021Conditional Linear Regression for Heterogeneous Covariancescited by 1
  6. 2022Communication-efficient distributed eigenspace estimation with arbitrary node failurescited by 1
  7. 2023Attacking Byzantine Robust Aggregation in High Dimensionscited by 1
  8. 2024Robust Sparse Regression with Non-Isotropic Designscited by 1
  9. 2026Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transformscited by 1
  10. 2026High-Dimensional Gaussian Mean Estimation under Realizable Contaminationcited by 1
  11. 2026Computation-Utility-Privacy Tradeoffs in Bayesian Estimationcited by 1
  12. 2023Robust Mean Estimation Without Moments for Symmetric Distributionscited by 0
  13. 2025Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussianscited by 0
  14. 2025On Learning Parallel Pancakes with Mostly Uniform Weightscited by 0
  15. 2026On the SoS Certifiability of Log-Concave Distributionscited by 0