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 sparse mean estimation. Specifically,for a parameter $\alpha \in (0, 1/2)$, we are given $m$ points in$\mathbb{R}^n$, $\lfloor \alpha m \rfloor$ of which are i.i.d. samples from adistribution $D$ with unknown $k$-sparse mean $\mu$. No assumptions are made onthe remaining points, which form the majority of the dataset. The goal is toreturn a small list of candidates containing a vector $\widehat \mu$ such that$\| \widehat \mu - \mu \|_2$ is small. Prior work had studied the problem oflist-decodable mean estimation in the dense setting. In this work, we develop anovel, conceptually simpler technique for list-decodable mean estimation. Asthe main application of our approach, we provide the first sample andcomputationally efficient algorithm for list-decodable sparse mean estimation.In particular, for distributions with ``certifiably bounded'' $t$-th moments in$k$-sparse directions and sufficiently light tails, our algorithm achieveserror of $(1/\alpha)^{O(1/t)}$ with sample complexity $m =(k\log(n))^{O(t)}/\alpha$ and running time $\mathrm{poly}(mn^t)$. For thespecial case of Gaussian inliers, our algorithm achieves the optimal errorguarantee of $\Theta (\sqrt{\log(1/\alpha)})$ with quasi-polynomial sample andcomputational complexity. We complement our upper bounds with nearly-matchingstatistical query and low-degree polynomial testing lower bounds.

List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering