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/

Zendy Plus

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

Zendy Tools

Zendy Open

We study the problem of list-decodable mean estimation, where an adversarycan corrupt a majority of the dataset. Specifically, we are given a set $T$ of$n$ points in $\mathbb{R}^d$ and a parameter $0< \alpha <\frac 1 2$ such thatan $\alpha$-fraction of the points in $T$ are i.i.d. samples from awell-behaved distribution $\mathcal{D}$ and the remaining $(1-\alpha)$-fractionare arbitrary. The goal is to output a small list of vectors, at least one ofwhich is close to the mean of $\mathcal{D}$. We develop new algorithms forlist-decodable mean estimation, achieving nearly-optimal statisticalguarantees, with running time $O(n^{1 + \epsilon_0} d)$, for any fixed$\epsilon_0 > 0$. All prior algorithms for this problem had additionalpolynomial factors in $\frac 1 \alpha$. We leverage this result, together withadditional techniques, to obtain the first almost-linear time algorithms forclustering mixtures of $k$ separated well-behaved distributions,nearly-matching the statistical guarantees of spectral methods. Priorclustering algorithms inherently relied on an application of $k$-PCA, therebyincurring runtimes of $\Omega(n d k)$. This marks the first runtime improvementfor this basic statistical problem in nearly two decades.  The starting point of our approach is a novel and simpler near-linear timerobust mean estimation algorithm in the $\alpha \to 1$ regime, based on aone-shot matrix multiplicative weights-inspired potential decrease. Wecrucially leverage this new algorithmic framework in the context of theiterative multi-filtering technique of Diakonikolas et al. '18, '20, providinga method to simultaneously cluster and downsample points using one-dimensionalprojections -- thus, bypassing the $k$-PCA subroutines required by prioralgorithms.

Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation