Schedule

Week 1: Basics

• 1.4:

  • Logistics

  • Supervised learning setup

  • Neural network basics

  • Error decomposition

• 1.6:

  • Optimization basics

  • Generalization basics: union bound, covering number

• Readings:

  • Chapter 1,2,4 of Theory of DL Book

Week 2: Approximation Theory

• 1.11:

  • Empirical observations of over-parameterized neural networks

  • Piecewise constant function approximation, bump function

  • Universal approximation by Stone-Weierstrass

• 1.13:

  • Barron's Theory

• Readings:

  • Understanding deep learning requires rethinking generalization

  • Chapter 2 -6 of Matus Telgarsky's notes

Week 3: Non-convex Optimization

• 1.18:

  • No class.

• 1.20:

  • Landscape analysis introduction

  • Unique local minimum

  • Locally optimizable function, second order stationary point, strict saddle point

• Reading:

  • Chapter 7 of Theory of DL Book

Week 4: Non-convex Optimization

• 1.25:

  • Asymptotic convergence of gradient descent to local minimum (Stable Manifold Theorem)

  • When gradient descent can take exponential time to escape saddle points

• 1.27:

  • How perturbed gradient descent finds a second-order-stationary-point in polyinomial time

• Readings:

  • On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points

  • Gradient Descent Converges to Minimizers

  • Gradient Descent Can Take Exponential Time to Escape Saddle Points

Week 5: Neural Tangent Kernel

• 2.1:

  • Review of kernel methods

  • Gradient descent from a kernel point of view

• 2.3:

  • Equivalence between neural network and neural tangent kernel (two-layer)

  • Empirical performance of neural tangent kernel

• Readings:

  • Neural Tangent Kernel: Convergence and Generalization in Neural Networks

  • Gradient Descent Provably Optimizes Over-parameterized Neural Networks

  • On Exact Computation with an Infinitely Wide Neural Net

  • Chapter 8 of Matus Telgarsky's notes

Week 6: Kernel (Cont'd), Implicit Regularization

• 2.8:

  • An exponenetial lower bound for kernel methods

  • Clarke differential

  • Positive homogeneity

• 2.10:

  • Gradient flow automatically balances layers

  • Margin and smoothed margin

  • gradient flow maximizes the margin of linear predictor

• Readings:

  • What Can ResNet Learn Efficiently, Going Beyond Kernels?

  • Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced

  • Characterizing the implicit bias via a primal-dual analysis

  • Chapter 6 of Theory of DL Book

  • Chapter 14 and 15 of Matus Telgarsky's notes

Week 7: Implicit Regularization (Cont'd), Generalization

• 2.15:

  • No class

• 2.17:

  • Non-decreasing of smoothed margin in postive homogeneous models

  • Rademacher complexity definition and its generalization theorem

• Readings:

  • Chapter 18 of Matus Telgarsky's notes

  • Rademacher and Gaussian Complexities: Risk Bounds and Structural Results

Week 8: Generalization

• 2.22:

  • Proof of generalization theorem based on Rademacher complexity

  • Generalization bounds for logistic regression

• 2.24:

  • Generalization bounds for norm-bounded neural networks

• Readings:

  • Chapter 4 of Theory of DL Book

  • Chapter 18 and 19 of Matus Telgarsky's notes

Week 9: Generalization

• 3.1:

  • Generalization bound for Frobenius norm bounded neural networks

  • Basics of covering number

• 3.3:

  • Generalization bounds of neural networks via covering number

• Readings:

  • Size-Independent Sample Complexity of Neural Networks

  • Spectrally-normalized margin bounds for neural networks

  • Chapter 20 and 21 of Matus Telgarsky's notes

Week 10: Course Project Presentations