SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation
This work provides a significant speedup for sum-of-squares based algorithms in clustering and robust moment estimation, benefiting researchers and practitioners working with high-dimensional data.
The authors developed a framework to reduce the degree of sum-of-squares proofs by introducing new variables. This framework was applied to clustering and robust moment estimation, achieving the same statistical guarantees as previous best algorithms but with significantly faster running times, improving from (d*n)^O(l) to d^O(l) * n^O(1).
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-$\ell$ moments in time $d^{O(\ell)}\cdot n^{O(1)}$, whereas a naive implementation requires time $(d\cdot n)^{O(\ell)}$. Since for the aforementioned applications, the typical sample size is $d^{Θ(\ell)}$, our framework improves running times from $d^{O(\ell^2)}$ to $d^{O(\ell)}$.