Ankur Moitra : Linear Inverse Problems

Abstract: Parametric inference is one of the cornerstones of statistics, but much of the classic theory revolves around asymptotic notions of convergence and relies on estimators that are hard to compute (particularly in high-dimensional problems).

In this tutorial, we will explore the following questions:

(1) For some of the fundamental problems in statistics, are there surrogates for the maximum likelihood estimator that also converge at an inverse polynomial rate to the true parameters, but in contrast can be computed efficiently?

(2) Can we establish tradeoffs between sample complexity and computational complexity? And what types of hardness assumptions allow us to explore this space?

We will cover topics such as the method of moments, learning mixture models, tensor decomposition, sparse PCA and matrix/tensor completion.

Recording during the thematic meeting: «Nexus of Information and Computation Theories » theJanuary 28, 2016 at the Centre International de Rencontres Mathématiques (Marseille, France)

Filmmaker: Guillaume Hennenfent