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

We study the problem of list-decodable Gaussian mean estimation and therelated problem of learning mixtures of separated spherical Gaussians. Wedevelop a set of techniques that yield new efficient algorithms withsignificantly improved guarantees for these problems.  {\bf List-Decodable Mean Estimation.} Fix any $d \in \mathbb{Z}_+$ and $0<\alpha <1/2$. We design an algorithm with runtime $O(\mathrm{poly}(n/\alpha)^{d})$ that outputs a list of $O(1/\alpha)$ manycandidate vectors such that with high probability one of the candidates iswithin $\ell_2$-distance $O(\alpha^{-1/(2d)})$ from the true mean. The onlyprevious algorithm for this problem achieved error $\tilde O(\alpha^{-1/2})$under second moment conditions. For $d = O(1/\epsilon)$, our algorithm runs inpolynomial time and achieves error $O(\alpha^{\epsilon})$. We also give aStatistical Query lower bound suggesting that the complexity of our algorithmis qualitatively close to best possible.  {\bf Learning Mixtures of Spherical Gaussians.} We give a learning algorithmfor mixtures of spherical Gaussians that succeeds under significantly weakerseparation assumptions compared to prior work. For the prototypical case of auniform mixture of $k$ identity covariance Gaussians we obtain: For any$\epsilon>0$, if the pairwise separation between the means is at least$\Omega(k^{\epsilon}+\sqrt{\log(1/\delta)})$, our algorithm learns the unknownparameters within accuracy $\delta$ with sample complexity and running time$\mathrm{poly} (n, 1/\delta, (k/\epsilon)^{1/\epsilon})$. The previously bestknown polynomial time algorithm required separation at least $k^{1/4}\mathrm{polylog}(k/\delta)$.  Our main technical contribution is a new technique, using degree-$d$multivariate polynomials, to remove outliers from high-dimensional datasetswhere the majority of the points are corrupted.

List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians