CSE 291: Topics in learning theory (Fall 2014)

TuTh 3.30-4.50 in CSE 4258

I. Topic models

Sontag, Roy. Complexity of inference in latent Dirichlet allocation. NIPS 2011.
Donoho, Stodden. When does non-negative matrix factorization give a correct decomposition into parts? NIPS 2003.
Arora, Ge, Halpern, Mimno, Moitra, Sontag, Wu, Zhu. A practical algorithm for topic modeling with provable guarantees. ICML 2013.

Oct 2. Organizational meeting.

Oct 7. Introduction to topic models.

Oct 9. Hardness of inference.

Oct 14. Learning under separability.

Oct 16. Learning topic models, cont'd.

II. Sparse recovery and dictionary learning

Natarajan. Sparse approximate solutions to linear systems. SICOMP 1995.
Arora, Moitra, Ge. New algorithms for learning incoherent and overcomplete dictionaries. COLT 2014.
Agarwal, Anandkumar, Jain, Netrapalli, Tandon. Learning sparsely-used overcomplete dictionaries via alternating minimization. COLT 2014.

Oct 21. Sparse recovery: hardness and a greedy approach.

Oct 23. Sparse recovery under incoherence conditions.

Oct 28. Dictionary learning under incoherence conditions.

Oct 30. Dictionary learning, cont'd.

III. Tensor decompositions

Ankur Moitra's notes on tensor methods: see chapter 3 of this manuscript.
Leurgans, Ross, Abel. A decomposition for three-way arrays. 1993.
Anandkumar, Hsu, Kakade. A method of moments for mixture models and hidden Markov models. COLT 2012.
Mossel, Roch. Learning nonsingular phylogenies and hidden Markov models. Annals of Applied Probability, 2006.

Nov 4. Tensor method for pure topic models.

Nov 6. Tensor decomposition algorithm. Hidden Markov models.

Nov 11. No class: Veteran's day.


Nov 13. Pun.
Arora, Bhaskara, Ge, Ma. More algorithms for provable dictionary learning.

Nov 18. Stefanos.
Candes, Tao. The Dantzig selector: statistical estimation when p is much larger than n. Annals of Statistics, 2007.

Nov 20. Sharad.
Hsu, Kakade. Learning mixtures of spherical Gaussians: moment methods and spectral decompositions. ICS 2013.

Nov 25. Akshay and Zack.
Arora, Bhaskara, Ge, Ma. Provable bounds for learning some deep representations. ICML 2014.

Nov 27. No class: Thanksgiving.

Dec 2. Akshay and Zack, cont'd.

Dec 4. Chicheng and Chris.
Anandkumar, Ge, Hsu, Kakade. A tensor approach to learning mixed membership community models. JMLR 2014.

Dec 9. Chicheng and Chris, cont'd.

Dec 11. Suqi.

Related papers

Anandkumar, Foster, Hsu, Kakade, Liu. A spectral algorithm for latent Dirichlet allocation. NIPS 2012.
Frieze, Jerrum, Kannan. Learning linear transformations. FOCS 1996.
Bhaskara, Charikar, Moitra, Vijayaraghavan. Smoothed analysis of tensor decompositions. STOC 2014.
Voss, Rademacher, Belkin. Fast algorithms for Gaussian noise invariant independent component analysis. NIPS 2013.
Tang, Meng, Nguyen, Mei, Zhang. Understanding the limiting factors of topic modeling via posterior contraction analysis. ICML 2014.