Title: From Proofs to Algorithms for High-Dimensional Statistics

Abstract: I will discuss a novel technique, "Proofs to Algorithms," for designing and analyzing computationally-efficient algorithms for challenging problems in high-dimensional statistics. This technique has recently been used to develop new algorithms with the strongest-known provable guarantees (among polynomial-time algorithms) for a wide array of problems in clustering, regression, heavy-tailed and robust estimation, community detection, and more. Under the hood, Proofs to Algorithms employs the powerful Sum of Squares approach to convex programming, which I will introduce in the talk.

I will illustrate the technique via an application to high-dimensional clustering of samples from Gaussian mixture models, and (time-permitting) discuss some recent developments in heavy-tailed and robust statistics.

Based on joint works with Yeshwanth Cherapanamjeri, Tarun Kathuria, Jerry Li, Prasad Raghavendra, and Nilesh Tripuranenid