Jerry Li (Microsoft Research)

Oct 19, 2020

Title and Abstract

Faster and Simpler Algorithms for List Learning

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\). 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.

In our work, we have two main contributions. First, we give a very simple polynomial time algorithm for this problem which achieves optimal error. Second, we then build off of these insights to develop a somewhat more sophisticated algorithm based on lazy mirror descent which runs in time \(\widetilde{O}(n d / \alpha + 1/\alpha^6)\), and which also achieves optimal error. Our algorithm improves upon the runtime of previous work for all \(1/\alpha = O(\sqrt{d}\). The goal of this talk is to give a more or less self-contained proof of the first, and then explain at a high level how to use these ideas to develop our faster algorithm.

Joint work with Ilias Diakonikolas, Daniel Kane, Daniel Kongsgaard, and Kevin Tian

Bio

Jerry Li is a Senior Researcher at Microsoft Research. He completed his PhD at MIT under the supervision of Ankur Moitra, after completing his Masters at MIT and his undergraduate at UW. Subsequently, he did a postdoc at the Simons Institute at UC Berkeley. His work focuses largely on high dimensional statistical learning theory and machine learning, with a particular focus towards understanding how and why learned models are robust. For his work, he has been awarded the George Sprowls award for Outstanding Thesis in EECS at MIT, various special issue invitations, and an invitation to appear in the Communications of the ACM. Outside of work, he enjoys being killed first in Among Us, and being really bad at playing the imposter