Method of Moments: From Sample Complexity to Efficient Implicit Computations

Joao Pereira (The University of Texas at Austin)

In this talk, I focus on the multivariate method of moments for parameter estimation. First from a theoretical standpoint, we show that in problems where the noise is high, the number of observations necessary to estimate parameters is dictated by the moments of the distribution. Second from a computational standpoint, we address the curse of dimensionality: the d-th moment of an n-dimensional random variable is a tensor with nd entries. For Gaussian Mixture Models (GMMs), we develop numerical methods for implicit computations with the empirical moment tensors. This reduces the computational and storage costs, and opens the door to the competitiveness of the method of moments as compared to expectation maximization methods. Time permitting, we connect these results to symmetric CP tensor decomposition and sketch a recent algorithm which is faster than the state-of-the-art and comes with guarantees. Collaborators include Joe Kileel (UT Austin), Tamara Kolda (MathSci.ai) and Timo Klock (Deeptech).

João is a postdoc in the Oden Institute at UT Austin, working with Joe Kileel and Rachel Ward. Previously, he was a postdoc at Duke University, working with Vahid Tarokh, and obtained is Ph.D. degree in Applied Mathematics at Princeton University, advised by Amit Singer and Emmanuel Abbe. This summer, he will join IMPA, in Rio de Janeiro, Brazil, as an assistant professor. He is broadly interested in tensor decompositions, information theory and applied mathematics.