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 { \em implicit moment tensor computation}. Our framework generalizes the work of~\cite{ 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 $\mathrm{ poly}(d, k)$-time learning algorithms for the following models. * { \bf Mixtures of Linear Regressions} We give a $\mathrm{ poly}(d, k, 1/\epsilon)$-time algorithm for this task, where $\epsilon$ is the desired error. * { \bf Mixtures of Spherical Gaussians} For density estimation, we give a $\mathrm{ poly}(d, k, 1/\epsilon)$-time learning algorithm, where $\epsilon$ is the desired total variation error, under the condition that the means lie in a ball of radius $O(\sqrt{ \log k})$. For parameter estimation, we give a $\mathrm{ poly}(d, k, 1/\epsilon)$-time algorithm under the { \em optimal} mean separation of $\Omega(\log^{ 1/2}(k/\epsilon))$. * { \bf Positive Linear Combinations of Non-Linear Activations} We give a general algorithm for this task with complexity $\mathrm{ poly}(d, k) g(\epsilon)$, where $\epsilon$ 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 $\mathrm{ poly}(d, k) 2^{ \mathrm{ poly}(1/\epsilon)}$.
Categories: cs.DS cs.LG math.ST stat.ML stat.TH