UIUC CS 598 (CRN 62819) TOPICS IN ALGORITHMS, Spring 2015
Time: Mon, Wed 12:30-1:45, 1304 SC
Office hours: Wed 4:00-5:00, 3212 SC
This course will cover a collection of topics in theory and algorithms
for analysis of data and networks. Topics will include:
Coursework will consist of 5-6 homework assignments, helping with
grading of one homework assignment, an optional course project or
presentation (can take the place of one homework), plus active participation in class and on the
discussion page (I would like to see at least one
comment by each student related to each chapter).
- The geometry of high-dimensional space including tail inequalities and
- Singular value decomposition and principal component analysis,
- Properties and analysis of random graphs including phase
transitions and the second-moment method, also small-world and
- Random walks and Markov chains. Conductance and rapid mixing.
- Machine learning theory: algorithms and analysis. Uniform
convergence, the Perceptron algorithm, Kernel methods, Boosting.
- Algorithms for streaming and sketching.
- Plus other topics depending on time and interest.
Readings: These readings are from a forthcoming book with John
Hopcroft and Ravi Kannan.
- Homework 1. Due in class (on paper) on Feb 2.
[Problem 4 originally had a typo: sqrt(d-1) should be 1/sqrt(d-1). It's fixed now. For problem 6, pretend that c=1 in the JL lemma]
- Homework 2. Due in class (on paper) on
March 2. [Was Feb 18. Deadline extended!]
- Homework 3. Due in class (on paper) on
- Homework 4. Due in class (on paper) on
- Homework 5. Due in class (on paper) on
- Homework 6. Due in class (on paper) on
- 01/21: [Chapter 2] Getting used to high dimensions, the Perceptron algorithm,
basic properties of high-dimensional objects.
- 01/26: [Chapter 2] Properties of the d-dimensional ball and
Gaussian, selecting from a Gaussian, the Law of Large Numbers.
- 01/28: [Chapter 2] Gaussian annulus theorem, tail bounds for sums
of random variables with bounded moments, the
- 02/02: [Chapter 3] Singular vectors and intro to SVD.
- 02/04: [Chapter 3] Continuing with SVD, orthogonality of left
singular vectors, power method.
- 02/09: [Chapter 3] Power method, Laplacians, PCA.
- 02/11: [Chapter 3,6] Mixture of Gaussians, Batch/PAC learning model, Occam's razor.
- 02/16: [Chapter 6] Uniform convergence, Regularization,
Stochastic Gradient Descent.
- 02/18: [Chapter 6] Online mistake bounds; Perceptron, Margins,
- 02/23: no class.
- 02/25: no class
- 03/02: [Chapter 6] Online to Batch conversion, Kernel functions.
- 03/04: [Chapter 6] Boosting, Sleeping experts.
- 03/09: [Chapter 6] VC-dimension.
- 03/11: [Chapter 7] Streaming algorithms 1: counting distinct
- 03/16: [Chapter 7] Streaming algorithms 2: finding heavy hitters,
estimating the second moment.
- 03/18: [Chapter 7] Length-squared sampling for fast approximate
matrix operations. CUR decomposition.
- 03/30: [Chapter 7] Finish CUR decomposition.
- 04/01: [Chapter 5] Random walks and Markov chains. Fundamental Thm of MCs.
- 04/06: [Chapter 5] Random walks and electrical networks, cover times.
- 04/08: [Chapter 5] Random walks and electrical networks, cover times, contd.
- 04/13: [Chapter 5] Convergence time of random walks on undirected
graphs. Rapid mixing.
- 04/15: [Chapter 5] Finish rapid mixing. Canonical path method.
- 04/20: [Chapter 4] Random graphs and phase transitions. Existence
of triangles. 2nd-moment method.
- 04/22: [Chapter 4] Random graphs and phase transitions. Diameter
at most 2. Connectivity.
- 04/27: [Chapter 4] Random graphs and phase transitions. Finish
connectivity and isolated vertices. General increasing properties.
- 04/29: Resource allocation problems: minimum-congestion routing, offline
(Raghavan-Thompson) and online (Awerbuch-Azar-Plotkin).
- 05/04: Introduction to Game Theory.
- 05/06: Regret minimization,
RWM algorithm, Minimax, Internal Regret and Correlated Equilibrium.