mlsanityData to 14 Oct 2026

SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications

arXiv 2410.21194 ↗First posted 28 Oct 2024cs.DS cs.LG math.STcited by 10

Not on the map. Why?

Abstract (arXiv)

We prove that there is a universal constant C>0 so that for every d ∈ mathbb N, every centered subgaussian distribution mathcal D on mathbb Rd, and every even p ∈ mathbb N, the d-variate polynomial (Cp)p/2 · |v|2p - mathbb EX ~ mathcal D langle v,Xranglep is a sum of square polynomials. This establishes that every subgaussian distribution is SoS-certifiably subgaussian -- a condition that yields efficient learning algorithms for a wide variety of high-dimensional statistical tasks. As a direct corollary, we obtain computationally efficient algorithms with near-optimal guarantees for the following tasks, when given samples from an arbitrary subgaussian distribution: robust mean estimation, list-decodable mean estimation, clustering mean-separated mixture models, robust covariance-aware mean estimation, robust covariance estimation, and robust linear regression. Our proof makes essential use of Talagrand's generic chaining/majorizing measures theorem.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 33 of its 61 references that are in the map. First posted on arXiv 28 Oct 2024.

Builds on

33 of 61 references.

References · 33

  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 125
  4. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  5. 2016Learning from Untrusted Datacited by 90
  6. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  7. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  8. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  9. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  10. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  11. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  12. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
21 more
  1. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 50
  2. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  3. 2019List-Decodable Linear Regressioncited by 42
  4. 2020Robust Linear Regression: Optimal Rates in Polynomial Timecited by 42
  5. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  6. 2020Optimal Robust Linear Regression in Nearly Linear Timecited by 32
  7. 2017Outlier-robust moment-estimation via sum-of-squarescited by 27
  8. 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
  9. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 24
  10. 2014Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Methodcited by 22
  11. 2017Better Agnostic Clustering Via Relaxed Tensor Normscited by 21
  12. 2023Tester-Learners for Halfspaces: Universal Algorithmscited by 17
  13. 2019How Hard Is Robust Mean Estimation?cited by 16
  14. 2021Robust Regression Revisited: Acceleration and Improved Estimation Ratescited by 15
  15. 2021Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimallycited by 14
  16. 2022List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filteringcited by 13
  17. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
  18. 2015Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithmscited by 10
  19. 2016Strongly Refuting Random CSPs Below the Spectral Thresholdcited by 9
  20. 2024Efficient Certificates of Anti-Concentration Beyond Gaussianscited by 4
  21. 2014Strong duality in Lasserre's hierarchy for polynomial optimizationcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 2; 2026: 5.

10 papers.

  1. 2025The Power of Iterative Filtering for Supervised Learning with (Heavy) Contaminationcited by 7
  2. 2024SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and Morecited by 3
  3. 2024Robust Sparse Regression with Non-Isotropic Designscited by 1
  4. 2026Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transformscited by 1
  5. 2024Sparsifying Suprema of Gaussian Processescited by 0
  6. 2025Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussianscited by 0
  7. 2026Corruption-robust Offline Multi-agent Reinforcement Learning From Human Feedbackcited by 0
  8. 2026Algorithms with Polynomially-Improved Approximation Factors for the 2 rightarrow q Norm, and Applicationscited by 0
  9. 2026Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterizationcited by 0
  10. 2026On the SoS Certifiability of Log-Concave Distributionscited by 0