Skip to main content

David Steurer: High-dimensional estimation via sum-of-squares proofs

Time: Thu 2019-04-25 13.15

Lecturer: David Steurer

Location: Room 4523, Lindstedtsvägen 5 - floor 5, KTH

Abstract: Estimation is the computational task of approximately recovering a hidden parameter x associated with a distribution D_x given a draw y from the distribution D_x. Numerous interesting questions in statistics, machine
learning, and signal processing are captured in this way, for example, sparse linear regression, Gaussian mixture models, topic models, and stochastic block models.

In many cases, there is currently a large gap between the statistical guarantees of computationally efficient algorithms and the guarantees of computationally inefficient methods; it is an open question if this gap is inherent in these cases or if better computationally efficient estimation algorithms exist.

In this talk, I will present a meta-algorithm for estimation problems based on the sum-of-squares method of Shor, Parrilo, and Lasserre. For some problems, e.g., learning mixtures of spherical Gaussians, this meta-algorithm is able to close previous long-standing gaps and achieve nearly optimal statistical guarantees. Furthermore, it is plausible that, for a wide range of estimation problems, the statistical guarantees that this meta-algorithm achieves are best possible among all efficient algorithms.

This talk is based on an ICM proceedings article with Prasad Raghavendra and Tselil Schramm.

Coauthors: Prasad Raghavendra and Tselil Schramm

The speaker was invited by Johan Håstad.

For more information about upcoming seminars,

Belongs to: Department of Mathematics
Last changed: Apr 16, 2019