UIUC CS 598 (CRN 62819) TOPICS IN ALGORITHMS, Spring 2015

Instructor: Avrim Blum /// Time: Mon, Wed 12:30-1:45, 1304 SC /// Office hours: Wed 4:00-5:00, 3212 SC

Course description: This course will cover a collection of topics in theory and algorithms for analysis of data and networks. Topics will include:

• The geometry of high-dimensional space including tail inequalities and random projection,
• 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 preferential-attachment models.
• 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.
Coursework: 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 Piazza discussion page (I would like to see at least one comment by each student related to each chapter).

Readings: These readings are from a forthcoming book with John Hopcroft and Ravi Kannan.

Homeworks:

• 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 March 18.
• Homework 4. Due in class (on paper) on April 15.
• Homework 5. Due in class (on paper) on April 27.
• Homework 6. Due in class (on paper) on May 4.
Lectures:
1. 01/21: [Chapter 2] Getting used to high dimensions, the Perceptron algorithm, basic properties of high-dimensional objects.
2. 01/26: [Chapter 2] Properties of the d-dimensional ball and Gaussian, selecting from a Gaussian, the Law of Large Numbers.
3. 01/28: [Chapter 2] Gaussian annulus theorem, tail bounds for sums of random variables with bounded moments, the Johnson-Lindenstrauss Lemma.
4. 02/02: [Chapter 3] Singular vectors and intro to SVD.
5. 02/04: [Chapter 3] Continuing with SVD, orthogonality of left singular vectors, power method.
6. 02/09: [Chapter 3] Power method, Laplacians, PCA.
7. 02/11: [Chapter 3,6] Mixture of Gaussians, Batch/PAC learning model, Occam's razor.
8. 02/16: [Chapter 6] Uniform convergence, Regularization, Stochastic Gradient Descent.
9. 02/18: [Chapter 6] Online mistake bounds; Perceptron, Margins, and Hinge-loss.
10. 02/23: no class.
11. 02/25: no class
12. 03/02: [Chapter 6] Online to Batch conversion, Kernel functions.
13. 03/04: [Chapter 6] Boosting, Sleeping experts.
14. 03/09: [Chapter 6] VC-dimension.
15. 03/11: [Chapter 7] Streaming algorithms 1: counting distinct elements, sampling.
16. 03/16: [Chapter 7] Streaming algorithms 2: finding heavy hitters, estimating the second moment.
17. 03/18: [Chapter 7] Length-squared sampling for fast approximate matrix operations. CUR decomposition.
18. 03/30: [Chapter 7] Finish CUR decomposition.
19. 04/01: [Chapter 5] Random walks and Markov chains. Fundamental Thm of MCs.
20. 04/06: [Chapter 5] Random walks and electrical networks, cover times.
21. 04/08: [Chapter 5] Random walks and electrical networks, cover times, contd.
22. 04/13: [Chapter 5] Convergence time of random walks on undirected graphs. Rapid mixing.
23. 04/15: [Chapter 5] Finish rapid mixing. Canonical path method.
24. 04/20: [Chapter 4] Random graphs and phase transitions. Existence of triangles. 2nd-moment method.
25. 04/22: [Chapter 4] Random graphs and phase transitions. Diameter at most 2. Connectivity.
26. 04/27: [Chapter 4] Random graphs and phase transitions. Finish connectivity and isolated vertices. General increasing properties.
27. 04/29: Resource allocation problems: minimum-congestion routing, offline (Raghavan-Thompson) and online (Awerbuch-Azar-Plotkin).
28. 05/04: Introduction to Game Theory.
29. 05/06: Regret minimization, RWM algorithm, Minimax, Internal Regret and Correlated Equilibrium.