ARC - ACO Lecture Series
featuring Pravesh Kothari (CMU)
February 15 & 17 - Groseclose 402 - 11:00AM
February 18 - Groseclose 402 - 1:00PM
Title: High-Dimensional Statistical Estimation via Sum-of-Squares
Abstract: One exciting new development of the past decade is the evolution of the sum-of-squares method for algorithm design for high-dimensional statistical estimation. This paradigm can be viewed as a principled approach to generating and analyzing semidefinite programming relaxations for statistical estimation problems by thinking of the duals as proofs of statistical identifiability -- i.e., proof that the input data uniquely identifies the unknown target parameters.
In this sequence of three lectures, I will give an overview of the sum-of-squares method for statistical estimation. Specifically, I will discuss how strengthening (via semidefinite certificates) of basic analytic properties of probability distributions such as subgaussian tails, hypercontractive moments, and anti-concentration yield new algorithms for problems such as learning spherical and non-spherical Gaussian mixture models and basic tasks in algorithmic robust statistics.
Bio: Pravesh Kothari is an Assistant Professor in the Computer Science Department at CMU. He is broadly interested in algorithms and algorithmic thresholds for average-case computational problems with a specific focus on problems at the intersection of theoretical computer science and statistics. His prior work has focused on developing the Sum-of-Squares method for algorithm design leading to progress on problems such as learning mixtures of Gaussians, refuting random constraint satisfaction problems, and problems in algorithmic robust statistics. His research has been recognized with a Google Research Scholar Award and an NSF Career Award.
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836