Name
Abstract | ||
|---|---|---|
We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. Specifically, we are given a set T of n points in R-d and a parameter 0 < alpha < 1/2 such that an alpha-fraction of the points in T are i.i.d. samples from a well-behaved distribution D and the remaining (1 - alpha)-fraction are arbitrary. The goal is to output a small list of vectors, at least one of which is close to the mean of D. We develop new algorithms for this problem achieving nearly-optimal statistical guarantees, with runtime O(n(1+epsilon 0)d), for any fixed epsilon(0) > 0. All prior algorithms for this problem had additional polynomial factors in 1/alpha. We leverage this result, together with additional techniques, to obtain the first almost-linear time algorithms for clustering mixtures of k separated well-behaved distributions, nearly-matching the statistical guarantees of spectral methods. Prior clustering algorithms inherently relied on an application of k-PCA, thereby incurring runtimes of Omega(ndk). This marks the first runtime improvement for this basic statistical problem in nearly two decades. The starting point of our approach is a novel and simpler near-linear time robust mean estimation algorithm in the alpha -> 1 regime, based on a one-shot matrix multiplicative weights-inspired potential decrease. We crucially leverage this new algorithmic framework in the context of the iterative multi-filtering technique of [41, 15], providing a method to simultaneously cluster and downsample points using one-dimensional projections - thus, bypassing the k-PCA subroutines required by prior algorithms. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1145/3519935.3520014 | PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22) |
Keywords | DocType | ISSN |
robust statistics, clustering, mixture models, list-decodable learning | Conference | 0737-8017 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ilias Diakonikolas | 1 | 776 | 64.21 |
| Daniel M. Kane | 2 | 743 | 61.43 |
| Daniel Kongsgaard | 3 | 0 | 1.01 |
| Jerry Li | 4 | 229 | 22.67 |
| Kevin Tian | 5 | 0 | 0.68 |