Faster and Simpler Algorithms for List Learning

Abstract: The goal of list learning is to understand how to learn basic statistics of a dataset when it has been corrupted by an overwhelming fraction of outliers. More formally, one is given a set of points $S$, of which an $\alpha$-fraction $T$ are promised to be well-behaved. The goal is then to output an $O(1 / \alpha)$ sized list of candidate means, so that one of these candidates is close to the true mean of the points in $T$. In many ways, list learning can be thought of as the natural robust generalization of clustering mixture models. This formulation of the problem was first proposed in Charikar-Steinhardt-Valiant STOC’17, which gave the first polynomial-time algorithm which achieved nearly-optimal error guarantees. More recently, exciting work of Cherapanamjeri-Mohanty-Yau FOCS’20 gave an algorithm which ran in time $\widetilde{O} (n d \mathrm{poly} (1 / \alpha))$. In particular, this runtime is nearly linear in the input size for $1/\alpha = O(1)$, however, the runtime quickly becomes impractical for reasonably small $1/\alpha$. Moreover, both of these algorithms are quite complicated.