Sam Hopkins: How to Estimate the Mean of a Heavy-Tailed Vector in Polynomial Time

Speaker: Sam Hopkins, UC Berkeley

Date: Tuesday, April 09, 2019

Time: 4:00 PM to 5:00 PM

Public: Yes

Location: Patil/Kiva G449

Event Type: Seminar

Room Description:

Host: Ankur Moitra

Contact: Deborah Goodwin, 617.324.7303,

Relevant URL:

Speaker URL: None

Speaker Photo:
Sam headshot informal

Reminders to:,

Reminder Subject: TALK: Sam Hopkins: How to Estimate the Mean of a Heavy-Tailed Vector in Polynomial Time

We study polynomial time algorithms for estimating the mean of a multivariate random vector under very mild assumptions: we assume only that the random vector X has finite mean and covariance. This allows for X to be heavy-tailed. In this setting, the radius of confidence intervals achieved by the empirical mean are exponentially larger in the case that X is Gaussian or sub-Gaussian. That is, the empirical mean is poorly concentrated.
We offer the first polynomial time algorithm to estimate the mean of X with sub-Gaussian-size confidence intervals under such mild assumptions. That is, our estimators are exponentially better-concentrated than the empirical mean. Our algorithm is based on a new semidefinite programming relaxation of a high-dimensional median. Previous estimators which assumed only existence of finitely-many moments of X either sacrifice sub-Gaussian performance or are only known to be computable via brute-force search procedures requiring time exponential in the dimension.

Based on to appear in Annals of Statistics

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Seminar (ToC) 2019.

Created by Deborah Goodwin Email at Friday, April 05, 2019 at 2:15 PM.