Essentials

Schedule

Date. Topics. Notes. Coursework.
8/28 Administrivia; perceptron. pdf. hw0 out: tex, pdf.
8/30 Perceptron; decomposition of learning problems. pdf.
Representation.
9/6 Failure of linear; box apx (linear over boxes, decision trees). pdf. hw0 due!
9/11 End of box apx: boosted decision trees, branching programs, 3-layer ReLU nets. Start of poly-fit: Stone-Weierstrass! pdf.
9/13 Polynomial fit via Stone-Weierstrass: sums of exponentials, RBF kernels, 2-layer networks. pdf.
9/18 RKHS interlude. pdf.
9/20 RKHS remarks; tent maps and fractional parts. pdf. hw1 out: tex, pdf.
9/25 Depth hierarchy theorems for ReLU networks; multiplication and polynomials with ReLU networks. pdf.
9/27 Wasserstein distance, probability modeling, and GANs. pdf. hw1v2: tex, pdf, diff.
Optimization.
10/2 Convexity I: sets, functions, subdifferentials, first-order conditions. pen.
10/4 Convexity II: conjugacy and duality. pen.
10/9 Gradient descent when smooth. pen.
10/11 Gradient descent when smooth, strongly convex. pen.
10/16 Gradient descent and noise. pen.
10/18 Maurey sparsification and Frank-Wolfe. pen.
10/23 Convex risk minimization and classification. pen.
10/25 Continuation; start of online learning. pen.
10/30 Online learning. pen.
Generalization.
11/1 Concentration of measure. pen.
11/6 Finite classes and primitive covers. pen.
11/8 Symmetrization and Rademacher complexity. pen. hw2 out: tex, pdf. project proposal out: tex, pdf
11/13 Properties of Rademacher complexity. pen.
11/15 Classification bounds. pen.
11/27 VC dimension or linear functions and linear threshold networks. pen. hw2v3: tex, pdf, diffpdf.
11/29 VC dimension of ReLU networks. pen.
12/4 Possibly Definitely no class!
12/6 Definitely no class!
12/11 Rademacher and covering number bounds for neural networks I. pen.
12/13 Rademacher and covering number bounds for neural networks II. hw3 out: tex, pdf.
Final presentations and homework.
12/14 Reading day: project presentations!

Homework policies

Project policies

Resources

Other learning theory-ish classes. All of these courses are different, and all have good material, and there are many I neglected to include!

Textbooks and surveys. Again, there are many others, but here are a key few.