Combinatorics and Probability Seminar - Anup Rao (formerly Yale, now GaTech)

Event time: 
Thursday, April 21, 2016 - 4:00pm
LOM 215 See map
12 Hillhouse Avenue
New Haven, CT 06511
Event description: 

Anup Rao (formerly Yale, now GaTech).

Title: Agnostic Estimation of Mean and Covariance

In this talk, we consider the problem of estimating the mean and covariance of a distribution from iid samples in $\R^n$, in the presence of an $\eta$ fraction of malicious noise; this is in contrast to much recent work where the noise itself is assumed to be from a distribution of known type. We will give polynomial-time algorithms to compute estimates for the mean, covariance and operator norm of the covariance matrix, and show that the dimensional dependence of the error is optimal up to a $O(\sqrt{\log n})$ factor. This gives polynomial-time solutions to some of the questions studied in robust statistics. No background other than linear algebra and probability will be required for the talk. 

This is a joint work with Kevin Lai and Santosh Vempala.