Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Modern machine learning algorithms can extract useful information from text, images and

videos. All these applications involve solving NP-hard problems in average case using heuristics.

What properties of the input allow it to be solved efficiently? Theoretically analyzing

the heuristics is very challenging. Few results were known.

This thesis takes a different approach: we identify natural properties of the input, then

design new algorithms that provably works assuming the input has these properties. We are

able to give new, provable and sometimes practical algorithms for learning tasks related to

text corpus, images and social networks.

The first part of the thesis presents new algorithms for learning thematic structure in

documents. We show under a reasonable assumption, it is possible to provably learn many

topic models, including the famous Latent Dirichlet Allocation. Our algorithm is the first

provable algorithms for topic modeling. An implementation runs 50 times faster than latest

MCMC implementation and produces comparable results.

The second part of the thesis provides ideas for provably learning deep, sparse representations.

We start with sparse linear representations, and give the first algorithm for dictionary

learning problem with provable guarantees. Then we apply similar ideas to deep learning:

under reasonable assumptions our algorithms can learn a deep network built by denoising

autoencoders.

The final part of the thesis develops a framework for learning latent variable models.

We demonstrate how various latent variable models can be reduced to orthogonal tensor

decomposition, and then be solved using tensor power method. We give a tight sample

complexity analysis for tensor power method, which reduces the number of sample required

for learning many latent variable models.

In theory, the assumptions in this thesis help us understand why intractable problems

in machine learning can often be solved; in practice, the results suggest inherently new

approaches for machine learning. We hope the assumptions and algorithms inspire new

research problems and learning algorithms.