English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this work, we revisit the problem of estimating the mean and covariance ofan unknown $d$-dimensional Gaussian distribution in the presence of an$\varepsilon$-fraction of adversarial outliers. The pioneering work of [DKK+16]gave a polynomial time algorithm for this task with optimal$\tilde{O}(\varepsilon)$ error using $n = \textrm{poly}(d, 1/\varepsilon)$samples.  On the other hand, [KS17b] introduced a general framework for robust momentestimation via a canonical sum-of-squares relaxation that succeeds for the moregeneral class of certifiably subgaussian and certifiably hypercontractive[BK20] distributions. When specialized to Gaussians, this algorithm obtains thesame $\tilde{O}(\varepsilon)$ error guarantee as [DKK+16] but incurs asuper-polynomial sample complexity ($n = d^{O(\log(1/\varepsilon)}$) andrunning time ($n^{O(\log(1/\varepsilon))}$). This cost appears inherent totheir analysis as it relies only on sum-of-squares certificates of upper boundson directional moments while the analysis in [DKK+16] relies on lower bounds ondirectional moments inferred from algebraic relationships between moments ofGaussian distributions.  We give a new, simple analysis of the same canonical sum-of-squaresrelaxation used in [KS17b, BK20] and show that for Gaussian distributions,their algorithm achieves the same error, sample complexity and running timeguarantees as of the specialized algorithm in [DKK+16]. Our key innovation is anew argument that allows using moment lower bounds without havingsum-of-squares certificates for them. We believe that our proof technique willlikely be useful in developing further robust estimation algorithms.

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