Teaching Assistant: Alex Shkolnik
Class time and Location:
Prerequisites: Basic understanding of Algorithms (e.g., CS161), Linear Algebra (e.g., Math51), and Probability Theory (e.g., CS109), or equivalent.
Course requirements: Most likely, three homeworks (ca. 15-20% each), scribe two lectures (ca. 5%), and a major project (ca. 50%, which includes initial proposal, then intermediate report, then final report).
Syllabus: pdf
Primary references: Although there are many good books on related topics, there is not a single reference covering the topics we will cover. Thus, we will be reading primary sources from the literature. Relevant papers for each lecture are listed in the Lectures section. A more detailed list of relevant references is also provided below.
Homeworks:
Major project: pdf
Important Note: These scribed notes have been put up in real time to aid dissemination and complement class notes, but they have not been fully edited---Caveat emptor!
Lecture Notes: pdf
References: See the detailed list of references below, especially references under "Algorithmic and statistical perspectives on data problems."
Lecture Notes: pdf tex scribed by Gourab Mukherjee & Ben Newhouse
Main References:
(*)
Dasgupta and Gupta,
"An elementary proof of a theorem of Johnson and Lindenstrauss"
(*)
Achlioptas,
"Database-friendly random projections: Johnson-Lindenstrauss with binary coins"
Lecture Notes: pdf tex scribed by Meghana Vishvanath & Erik Goldman
Main References:
(*)
Papadimitriou, Raghavan, Tamaki, and Vempala,
"Latent semantic indexing: a probabilistic analysis"
Lecture Notes: pdf tex scribed by Richa Bhayani & Daniel Chen.
Main References:
(*)
Drineas, Kannan, and Mahoney,
"Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication"
(*)
Drineas, Kannan, and Mahoney,
"Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix"
Lecture Notes: pdf tex scribed by Jacob Bien & Noah Youngs
Main References:
(*)
Alon, Krivelevich and Vu,
"On the Concentration of Eigenvalues of Random Symmetric Matrices"
(*)
Achlioptas and McSherry,
"Fast Computation of Low-Rank Matrix Approximations"
Lecture Notes: pdf tex scribed by Mengqiu Wang & Kshipra Bhawalkar
Main References:
(*)
Drineas, Mahoney, Muthukrishnan, and Sarlos,
"Faster Least Squares Approximation"
(*)
Drineas, Mahoney, and Muthukrishnan,
"Relative-Error CUR Matrix Decompositions"
Lecture Notes: pdf tex scribed by David Fong & Ya Xu
Main References:
(*) Muller, Mika, Ratsch, Tsuda, and Scholkopf, "An Introduction to Kernel-Based Learning Algorithms"
(*) Daume, "From Zero to Reproducing Kernel Hilbert Spaces in Twelve Pages or Less"
Lecture Notes: pdf tex scribed by Mark Wagner & Weidong Shao
Main References:
(*) Cortes and Vapnik, "Support-Vector Networks"
(*) Scholkopf, Smola, and Muller, "Nonlinear component analysis as a kernel eigenvalue problem"
(*) Scholkopf, Herbrich, Smola, and Williamson, "A Generalized Representer Theorem"
Lecture Notes: pdf tex scribed by Gourab Mukherjee & Deyan Simeonov
Main References:
(*) Saul, Weinberger, Ham, Sha, and Lee, "Spectral methods for dimensionality reduction"
(*) Belkin and Niyogi, "Laplacian eigenmaps for dimensionality reduction and data representation"
Lecture Notes: pdf tex scribed by Yunting Sun & Meghana Vishvanath
Main References:
(*) Ham, Lee, Mika, and Scholkopf, "A kernel view of the dimensionality reduction of manifolds"
(*) Bengio et al., "Learning Eigenfunctions Links Spectral Embedding and Kernel PCA"
(*) Belabbas and Wolfe, "On landmark selection and sampling in high-dimensional data analysis"
Lecture Notes: pdf tex scribed by Richa Bhayani & Erik Goldman
Main References:
(*) Sections 2, 3, 4, and 13 of Hoory, Linial, and Wigderson, "Expander graphs and their applications"
Also worth skimimng:
(*) Linial, London, Rabinovich, "The geometry of graphs and some of its algorithmic applications"
(*) Gkantsidis, Mihail, and Saberi, "Conductance and congestion in power law graphs"
(*) Leskovec, Lang, Dasgupta, and Mahoney, "Statistical Properties of Community Structure in Large Social and Information Networks"
Lecture Notes: pdf tex scribed by Bahman Bahmani & Daniel Chen
References:
Same readings as last time.
Lecture Notes: pdf tex scribed by Noah Youngs & Weidong Shao
Main References:
(*) Schaeffer, "Graph Clustering"
Lecture Notes: pdf tex scribed by David Fong & Rajendra Shinde
Main References:
(*) Guattery and Miller, "On the Quality of Spectral Separators"
(*) Chung, "Four proofs of Cheeger inequality and graph partition algorithms"
Also worth skimming:
(*) Shi and Malik, "Normalized Cuts and Image Segmentation"
(*) von Luxburg, "A Tutorial on Spectral Clustering"
(*) Section 7 of Spielman (and Teng), "Fast Randomized Algorithms for Partitioning, Sparsification, and Solving Linear Systems"
(*) Andersen and Lang, "Communities from seed sets"
Lecture Notes: pdf tex scribed by Jacon Bien & Ya Xu
Main References:
(*) Shmoys, "Cut problems and their application to divide-and-conquer"
(*) Andersen and Lang, "An algorithm for improving graph partitions"
Also worth skimming:
(*) Leighton and Rao, "Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms"
(*) Linial, London, Rabinovich, "The geometry of graphs and some of its algorithmic applications"
Lecture Notes: pdf tex scribed by Kshipra Bhawalkar & Deyan Simeonov
Main References:
(*) Arora, Rao, and Vazirani, CACM article, "Geometry, flows, and graph-partitioning algorithms"
Also worth skimming:
(*) Khandekar, Rao, and Vazirani, "Graph partitioning using single commodity flows"
(*) Orecchia, Schulman, Vazirani, and Vishnoi, "On Partitioning Graphs via Single Commodity Flows"
Lecture Notes: pdf tex scribed by Mark Wagner & Yunting Sun
Main References:
(*) Arora, Hazan, and Kale, "The multiplicative weights update method: a meta algorithm and applications"
(*) Freund and Schapire, "Game Theory, On-line Prediction and Boosting"
Also worth skimming:
(*) Lang, Mahoney, and Orecchia, "Empirical Evaluation of Graph Partitioning Using Spectral Embeddings and Flow"
(*) Dietterich, "Ensemble Methods in Machine Learning"
(*) Freund and Schapire, "Adaptive game playing using multiplicative weights"
Lecture Notes: pdf tex scribed by Meghana Vishvanath & Rajendra Shinde
Main References:
(*) d'Aspremont, El Ghaoui, Jordan, and Lanckriet, "A Direct Formulation for Sparse PCA Using Semidefinite Programming"
(*) Mahoney and Drineas, "CUR Matrix Decompositions for Improved Data Analysis"
Lecture Notes: pdf tex scribed by Bahman Bahmani & Weidong Shao
Main References:
(*) Fazel, Hindi, and Boyd, "A Rank Minimization Heuristic with Application to Minimum Order System Approximation"
(*) Srebro, Rennie, and Jaakkola, "Maximum Margin Matrix Factorizations"
Also worth skimimng:
(*) Kulis, Sustik, and Dhillon, "Low-Rank Kernel Learning with Bregman Matrix Divergences"
(*) Bell and Koren, "Lessons from the Netflix Prize Challenge"
Papers marked (*) should be read; they are either useful background or will provide the basis for the lectures. Other papers are provided for additional background; this may be useful for helping you to scribe up the lectures and also for initial pointers for your project.
You should be able to find all of these online, given the title and authors. If there are any you can't find relatively easily, please let the instructor or TA know and we will provide a copy or pointer.
A note on reading papers: Research papers (especially conference versions in computer science) have a tendency to be terse, hard-to-read, and error-prone. To make matters worse, papers in different areas often refer to similar concepts by very different names. A good way to start is to peel apart the paper like an onion: read the introduction, and maybe read the introduction of related papers subsequent to it, to get a general idea; then get a sense of the main technical results (e.g., the main theoretical or empirical claims); and then go into the details of what is proved and how it is proved (or of how the empirical claims are validated). It may be hard to understand every technical detail of certain papers you're reading, but with effort you should develop a good understanding of the main technical contributions, the gist of how they are proved or evaluated, and a detailed understanding of at least one or two results.