Pravesh Kothari: Outlier-Robust Moment Estimation via Sum-of-Squares

Speaker: Pravesh Kothari

Date: Tuesday, December 05, 2017

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: G449

Event Type: Seminar

Room Description:

Host: Ankur Moitra

Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL:

Speaker Photo:
Picture

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Pravesh Kothari: Outlier-Robust Moment Estimation via Sum-of-Squares

Abstract:

We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers. The guarantees of our algorithms improve in many cases significantly over the best previous ones, obtained in recent works. We also show that the guarantees of our algorithms match information-theoretic lower-bounds for the class of distributions we consider. These better guarantees allow us to give improved algorithms for independent component analysis and learning mixtures of Gaussians in the presence of outliers.

Our algorithms are based on a standard sum-of-squares relaxation of the following conceptually-simple optimization problem: Among all distributions whose moments are bounded in the same way as for the unknown distribution, find the one that is closest in statistical distance to the empirical distribution of the adversarially-corrupted sample.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) 2017.

Created by Deborah Goodwin Email at Thursday, November 30, 2017 at 3:25 PM.