Many tasks in machine learning are computationally intractable. Nevertheless, researchers have developed
heuristic algorithms that successfully solve these problems in practice. This phenomena can be explained using
average case complexity. However, in many situations the details supporting this explanation are still missing: what
properties of the input make it possible to be solved efficiently? What is the chance that real-life inputs satisfy
these properties and how robust is the algorithm if they don't?

In this talk I use topic modeling as an example to show our attempts of answering these problems. The first
part of the talk gives a new algorithm for learning topic models with provable guarantees. This algorithm
relies on a reasonable simplifying assumption, and runs 20 times faster than existing software like mallet
with comparable output quality. The second part of the talk gives a new analysis for method of moments
algorithms (AHK12, AFHKL12) using tensor decomposition. The new algorithm has a better perturbation
analysis and can therefore tolerate more modeling error.