Course number: TTIC 41000
Time: M 34:20pm
Location: TTIC Room 526
Office hours: M 4:305pm
Course description.
This special topics course will examine techniques that use eigenvalues/eigenvectors of a matrix (and more generally, any linear algebraic tools) to solve or understand problems in modern machine learning.
The course will be accompanied by lectures on technical materials required to understand and derive spectral techniques.
As part of the course, students will take turn to present papers on recent research in this area.
Goals.
 Achieving an understanding of the foundational concepts and tools used in modern spectral methods
 Obtaining an ability to accurately evaluate new works in this area at conferences
 Finding new research projects that persist beyond this course
Audience and prerequisites.
The expected audience is student researchers in machine learning who are interested in learning about and doing novel research on this topic.
The main prerequisite is general mathematical maturity and familiarity with basic notions in linear algebra, statistics, and optimization.
Grading.
The course will be passfail. Students who actively engage in the class will receive a pass.
A significant part of this evaluation will also be the technical quality of the student presentation.
Tentative plan.
Oct 1 
Introduction, Vector Space Review 
Oct 3 (Wed) 
Hilbert Space, Matrix Decomposition (Dudeja and Hsu, 2018) 
Oct 8 
Spectral Learning of HMMs (Hsu et al., 2008; Foster et al., 2012; Balle et al., 2014) 
Oct 15 
Canonical Correlation Analysis (Golub and Zha, 1992; Andrew et al., 2013)
Some notes on deep CCA
Comparing matrix ranges

Oct 22 
Paper Discussion (Wang et al., 2015b) 
Oct 29 
Paper Discussion (Chapter 2 of Peyre and Cuturi) 
Nov 5 
Paper Discussion (Chapter 4 of Peyre and Cuturi; Peyre et al., 2016; AlvarezMelis and Jaakkola, 2018; Zhang et al., 2017) 
Nov 12 
Paper Discussion (Von Luxburg, 2007, Belkin and Niyogi, 2002) 
Nov 19 
Paper Discussion (TBD) 
Nov 26 
Paper Discussion (TBD) 
Dec 3 
Paper Discussion (TBD) 
Papers.
Please expand recursively for a more complete list.
Topic 
Papers 
Efficient algorithms 

Analysis of CCA 

Subspace identification 
 A spectral algorithm for learning mixture models (Vempala and Wang, 2004)
 On Spectral Learning of Mixtures of Distributions (Achlioptas and McSherry, 2005)
 A Spectral Algorithm for Learning Hidden Markov Models (Hsu et al., 2008)
 Toward Learning Gaussian Mixtures with Arbitrary Separation (Belkin and Sinha, 2010)
 Spectral dimensionality reduction for HMMs (Foster et al., 2012)
 Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (Hsu and Kakade, 2012)
 Hilbert Space Embeddings of Predictive State Representations (Boots et al., 2013)
 Generalized Topic Modeling (Blum and Haghtalab, 2016)
 Multitask Spectral Learning of Weighted Automata (Rabusseau et al., 2017)
 Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning (Rabusseau et al., 2018)
 Learning SingleIndex Models in Gaussian Space (Dudeja and Hsu, 2018)

Tensor decomposition 

Optimal transport 

Neural networks 

Clustering/graph cuts 

Kernel approximation 

Misc. 

Other resources.
