Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models

Abstract

We study the task of learning latent-variable models. A common algorithmic technique for this task is the method of moments. Unfortunately, moment-based approaches are hampered by the fact that the moment tensors of super-constant degree cannot even be written down in polynomial time. Motivated by such learning applications, we develop a general efficient algorithm for implicit moment tensor computation. Our framework generalizes the work of~LL21-opt which developed an efficient algorithm for the specific moment tensors that arise in clustering mixtures of spherical Gaussians. By leveraging our implicit moment estimation algorithm, we obtain the first poly(d, k)-time learning algorithms for the following models. * Mixtures of Linear Regressions We give a poly(d, k, 1/)-time algorithm for this task, where is the desired error. * Mixtures of Spherical Gaussians For density estimation, we give a poly(d, k, 1/)-time learning algorithm, where is the desired total variation error, under the condition that the means lie in a ball of radius O( k). For parameter estimation, we give a poly(d, k, 1/)-time algorithm under the optimal mean separation of (^1/2(k/)). * Positive Linear Combinations of Non-Linear Activations We give a general algorithm for this task with complexity poly(d, k) g(), where is the desired error and the function g depends on the Hermite concentration of the target class of functions. Specifically, for positive linear combinations of ReLU activations, our algorithm has complexity poly(d, k) 2^poly(1/).

Tasks

Reproductions