Guaranteed Non-convex Learning Algorithms through Tensor Decomposition

Unsupervised learning is the challenging problem of making automated discoveries without external supervision. It requires fitting unlabeled data to large-scale latent variable models. Traditional learning approaches such as expectation maximization or variational inference are slow to converge and get stuck in local optima due to non-convexity of the likelihood function. In contrast, we have developed a method of moments approach, based on decomposition of low order moment tensors, which is guaranteed to learn the correct model under mild conditions with (low order) polynomial sample and computational complexity. In practice, tensor methods significantly outperform previous learning approaches, both in training time and model fitting, on a wide range of problems such as document categorization, social network analysis, discovering neuronal cell types, and learning sentence embeddings. Further, we have established that tensor methods are guaranteed to find globally optimal solution to other challenging non-convex problems such as training multi-layer neural networks and reinforcement learning of partially observable Markov decision processes.  These positive results demonstrate that many learning tasks, previously considered intractable, can be solved efficiently under mild and transparent conditions