CSE 291: Topics in learning theory (Fall 2014)

TuTh 3.30-4.50 in CSE 4109

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. Hardness of inference.

Oct 9. Learning under separability.

II. Independent component analysis

Comon. Independent component analysis, a new concept?. Signal Processing, 1994.
Frieze, Jerrum, Kannan. Learning linear transformations. FOCS 1996.
Arora, Ge, Moitra, Sachdeva. Provable ICA with unknown Gaussian noise, and implications for Gaussian mixtures and autoencoders. NIPS 2012.

Oct 14. Identifiability and a local search procedure.

III. 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 16. Sparse recovery: hardness and a greedy approach.

Oct 21. Dictionary learning under incoherence conditions.

Oct 23. An alternating-minimization algorithm.

IV. 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 28. Simple mixture models.

Oct 30. Phylogenetic trees and hidden Markov models.

V. Speeding up matrix computations

Nov 4. Sampling for fast SVD.

Nov 6. Random Fourier features.

Nov 11. No class: Veteran's day.


Nov 13.

Nov 18.

Nov 20.

Nov 25.

Nov 27. No class: Thanksgiving.

Dec 2.

Dec 4.

Dec 9.

Dec 11.

Related papers

Anandkumar, Foster, Hsu, Kakade, Liu. A spectral algorithm for latent Dirichlet allocation. NIPS 2012.
Hsu, Kakade. Learning mixtures of spherical Gaussians: moment methods and spectral decompositions. ICS 2013.
Anandkumar, Ge, Hsu, Kakade. A tensor approach to learning mixed membership community models. JMLR 2014.
Bhaskara, Charikar, Moitra, Vijayaraghavan. Smoothed analysis of tensor decompositions. STOC 2014.
Arora, Bhaskara, Ge, Ma. Provable bounds for learning some deep representations. ICML 2014.
Arora, Bhaskara, Ge, Ma. More algorithms for provable dictionary learning.
Voss, Rademacher, Belkin. Fast algorithms for Gaussian noise invariant independent component analysis. NIPS 2013.