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.