**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.

- 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 Johnson-Lindenstrauss Lemma.
- 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, and Hinge-loss.
- 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 elements, sampling.
- 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.