Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally
share
In this work, we revisit the problem of estimating the mean and covariance of an unknown d-dimensional Gaussian distribution in the presence of an ε-fraction of adversarial outliers. The pioneering work of [DKK+16] gave a polynomial time algorithm for this task with optimal Õ(ε) error using n = poly(d, 1/ε) samples. On the other hand, [KS17b] introduced a general framework for robust moment estimation via a canonical sum-of-squares relaxation that succeeds for the more general class of certifiably subgaussian and certifiably hypercontractive [BK20] distributions. When specialized to Gaussians, this algorithm obtains the same Õ(ε) error guarantee as [DKK+16] but incurs a super-polynomial sample complexity (n = d^O(log(1/ε)) and running time (n^O(log(1/ε))). This cost appears inherent to their analysis as it relies only on sum-of-squares certificates of upper bounds on directional moments while the analysis in [DKK+16] relies on lower bounds on directional moments inferred from algebraic relationships between moments of Gaussian distributions. We give a new, simple analysis of the same canonical sum-of-squares relaxation used in [KS17b, BK20] and show that for Gaussian distributions, their algorithm achieves the same error, sample complexity and running time guarantees as of the specialized algorithm in [DKK+16]. Our key innovation is a new argument that allows using moment lower bounds without having sum-of-squares certificates for them. We believe that our proof technique will likely be useful in developing further robust estimation algorithms.
READ FULL TEXT