Theory Seminar - Iterative Methods for Efficient Statistics, in High Dimensions

Abstract:

We consider the classical statistical problem of estimating to arbitrary accuracy the parameters of a multidimensional Gaussian distribution under the following real-world obstacles: (1) truncated samples, (2) inhomogeneous population. 

(1) Statistical estimation from truncated samples is a classical problem, going back to Galton, Pearson, and Fisher. Truncated samples are samples that are only revealed if they fall in some subset S of the multi-dimensional Euclidean space. We provide and analyze an iterative algorithm with almost optimal sample and time complexity that recovers the parameters of a Gaussian distribution with arbitrary accuracy, from truncated samples.

(2) We prove the fast convergence of the celebrated iterative algorithm EM to efficiently estimate the means of Gaussian distributions in the inhomogeneous case of mixture of two Gaussian distributions.

 Abstracting the use of iterative algorithms in the previous important statistical problems, we consider the general question of analyzing the convergence of iterative algorithms. We prove that contraction maps provide a universal analysis tool for proving global convergence of iterative maps.

Based on joint works with: Constantinos Daskalakis, Themis Gouleakis and Christos Tzamos.