Course number: TTIC 41000
Time: MW 34:20pm
Location: TTIC Room 526
Office hours: MW 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 first supply the mathematical foundation required to understand and derive spectral techniques.
It will then cover some of the most recent developments in the literature in a tutoriallike manner.
In the latter part of the course, the course will "flip" and students will take turn to present a paper on recent research in this area, potentially with an extension of his/her own.
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 and result in publications
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 (attendance, asking questions, etc.).
A significant part of this evaluation will also be the technical quality of the student presentation which will require a deep understanding of the overall topic.
Tentative plan.
Weak of 
Monday 
Wednesday 
Oct 1 
Introduction: Subspace, Linear Transformation, Inner Product 
Eigendecomposition and Singular Value Decomposition 
Oct 8 
Matrix Decomposition Algorithms 
Matrix Perturbation Theory 
Oct 15 
Canonical Correlation Analysis (CCA) 
CCA Continued, Other Related Problems (PCA, LDA, Orthogonal Procrustes) 
Oct 22 
Model Estimation by Subspace Identification 
Model Estimation by Subspace Identification (Continued) 
Oct 29 
Spectral Clustering 
Kernel Approximation Methods 
Nov 5 
Online Algorithms for Spectral Methods 
Optimal Transport 
Nov 12 
HigherOrder Tensor Decomposition, Markov Chain Mixing Time 
Neural Networks, Summary 
Nov 19 
Student Presentations 
Student Presentations 
Nov 26 
Student Presentations 
Student Presentations 
Dec 3 
Student Presentations 
Student Presentations 
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)
 Learning SingleIndex Models in Gaussian Space (Dudeja and Hsu, 2018)

Tensor decomposition 

Optimal transport 

Neural networks 

Clustering/graph cuts 

Kernel approximation 

Misc. 

Other resources.
