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.

III. Tensor decompositions

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.

Oct 30. Simple mixture models.

Nov 4. Phylogenetic trees and hidden Markov models.

Nov 6. Tensor methods, cont'd.

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. Zack.
Arora, Bhaskara, Ge, Ma. Provable bounds for learning some deep representations. ICML 2014.

Nov 27. No class: Thanksgiving.

Dec 2. Akshay.
Arora, Ge, Moitra, Sachdeva. Provable ICA with unknown Gaussian noise, and implications for Gaussian mixtures and autoencoders. NIPS 2012.

Dec 4. Chicheng.

Dec 9. Suqi.

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

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.