Talk by Sam Hopkins (UC Berkeley)
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
