SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation

with Stefan Tiegel. SODA 2021.



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 nn points in dimension dd, our algorithms can exploit order-\ell moments in time dO()nO(1)d^{O(\ell)}\cdot n^{O(1)}, whereas a naive implementation requires time (dn)O()(d\cdot n)^{O(\ell)}. Since for the aforementioned applications, the typical sample size is dΘ()d^{\Theta(\ell)}, our framework improves running times from dO(2)d^{O(\ell^2)} to dO()d^{O(\ell)}.


  • high-dimensional estimation
  • sum-of-squares
  • clustering