mlsanityData to 7 Oct 2026

SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation

arXiv 2101.01509 ↗First posted 5 Jan 2021cs.DS cs.LG stat.MLcited by 7

Not on the map. Why?

Abstract (arXiv)

We develop a general framework to significantly reduce the degree of sum-of-squares proofs by introducing new variables. To illustrate the power of this framework, we use it to speed up previous algorithms based on sum-of-squares for two important estimation problems, clustering and robust moment estimation. The resulting algorithms offer the same statistical guarantees as the previous best algorithms but have significantly faster running times. Roughly speaking, given a sample of n points in dimension d, our algorithms can exploit order-ℓ moments in time dO(ℓ)· nO(1), whereas a naive implementation requires time (d· n)O(ℓ). Since for the aforementioned applications, the typical sample size is dTheta(ℓ), our framework improves running times from dO(ℓ2) to dO(ℓ).

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 15 of its 31 references that are in the map. First posted on arXiv 5 Jan 2021.

Builds on

15 of 31 references.

References · 15

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2016Agnostic Estimation of Mean and Covariancecited by 131
  3. 2016Learning from Untrusted Datacited by 90
  4. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  5. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  6. 2019List-Decodable Linear Regressioncited by 42
  7. 2017Robustly Learning a Gaussian: Getting Optimal Error, Efficientlycited by 39
  8. 2015Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectorscited by 38
  9. 2019List Decodable Learning via Sum of Squarescited by 37
  10. 2015Tensor principal component analysis via sum-of-squares proofscited by 35
  11. 2017On Learning Mixtures of Well-Separated Gaussianscited by 30
  12. 2018High-dimensional estimation via sum-of-squares proofscited by 25
3 more
  1. 2014Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Methodcited by 22
  2. 2016Polynomial-time Tensor Decompositions with Sum-of-Squarescited by 22
  3. 2017Fast and robust tensor decomposition with applications to dictionary learningcited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 1; 2023: 4; 2024: 0; 2025: 0; 2026: 1.

7 papers.

  1. 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
  2. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  3. 2023Learning quantum Hamiltonians at any temperature in polynomial timecited by 20
  4. 2022List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filteringcited by 13
  5. 2023Robust Mean Estimation Without Moments for Symmetric Distributionscited by 0
  6. 2023SQ Lower Bounds for Learning Bounded Covariance GMMscited by 0
  7. 2026Algorithms with Polynomially-Improved Approximation Factors for the 2 rightarrow q Norm, and Applicationscited by 0