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.

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

• Chapter 2: High Dimensional Space.
• Chapter 3: Singular Value Decomposition (SVD).
• Chapter 4: Random Graphs.
• Chapter 5: Random Walks and Markov Chains. Additional notes.
• Chapter 6: Machine Learning.
• Chapter 7: Streaming and Sketching.
• Chapter 12: Appendix (background material and more).

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.

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.