Method of Moments: From Sample Complexity to Efficient Implicit Computations

João M. Pereira Assistant Professor Instituto de Matemática Pura e Aplicada, in Rio de Janeiro, Brazil Abstract: The focus of this talk is the multivariate method of moments for parameter estimation. First from a theoretical standpoint, we show that in problems where the noise is high, the sample complexity, that is, the number of observations necessary to estimate parameters, is dictated by the moments of the distribution. This follows from a Taylor expansion of the KL divergence that holds in the low signal-to-noise ratio regime. Second from a computational standpoint, we develop a method of moments to estimate the parameters of Gaussian Mixture Models (GMMs) implicitly, that is, without explicitly forming the moments. This addresses the curse of dimensionality: while the number of entries of higher-order moments of multivariate random variables scale exponentially with the order of the moments, our implicit approach has computational and storage costs similar to those of expectation-maximization (EM), and opens the door to the competitiveness between the two methods. Bio: João is an assistant professor at Instituto de Matemática Pura e Aplicada, in Rio de Janeiro, Brazil. Previously, he was a postdoc in the Oden Institute at UT Austin, working with Joe Kileel and Rachel Ward, and at Duke University, working with Vahid Tarokh. He obtained is Ph.D. degree in Applied Mathematics at Princeton University, advised by Amit Singer and Emmanuel Abbe. He is interested in algorithms and statistical lower bounds of high-dimensional inverse problems, with a focus on cryo-electron microscopy, tensor data, and learning differential equations.