Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance\n of Gaussians Optimally

In this work, we revisit the problem of estimating the mean and covariance of\nan unknown $d$-dimensional Gaussian distribution in the presence of an\n$\\varepsilon$-fraction of adversarial outliers. The pioneering work of [DKK+16]\ngave a polynomial time algorithm for this task with optimal\n$\\tilde{O}(\\varepsilon)$ error using $n = \\textrm{poly}(d, 1/\\varepsilon)$\nsamples.\n On the other hand, [KS17b] introduced a general framework for robust moment\nestimation via a canonical sum-of-squares relaxation that succeeds for the more\ngeneral class of certifiably subgaussian and certifiably hypercontractive\n[BK20] distributions. When specialized to Gaussians, this algorithm obtains the\nsame $\\tilde{O}(\\varepsilon)$ error guarantee as [DKK+16] but incurs a\nsuper-polynomial sample complexity ($n = d^{O(\\log(1/\\varepsilon)}$) and\nrunning time ($n^{O(\\log(1/\\varepsilon))}$). This cost appears inherent to\ntheir analysis as it relies only on sum-of-squares certificates of upper bounds\non directional moments while the analysis in [DKK+16] relies on lower bounds on\ndirectional moments inferred from algebraic relationships between moments of\nGaussian distributions.\n We give a new, simple analysis of the same canonical sum-of-squares\nrelaxation used in [KS17b, BK20] and show that for Gaussian distributions,\ntheir algorithm achieves the same error, sample complexity and running time\nguarantees as of the specialized algorithm in [DKK+16]. Our key innovation is a\nnew argument that allows using moment lower bounds without having\nsum-of-squares certificates for them. We believe that our proof technique will\nlikely be useful in developing further robust estimation algorithms.\n