COMS 4995-1 Spring 2020 (Machine Learning Theory)

Course information

• Time: Mon/Wed 8:40am–9:55am
• Venue: Zoom
• Instructor: Daniel Hsu
• Teaching/course assistants: Chao Qin, Sihyun Lee
• Office hours: See Piazza
• Internal links: syllabus (amendments), project instructions, scribing instructions, readings
• External links: Piazza, Courseworks, Gradescope

Please note that class is cancelled on Monday, March 9; Monday, March 23; and Wednesday, March 25. Lectures and office hours for the remainder of the semester will be conducted remotely via Zoom.

Homework assignments

• HW4 due 5/4
• HW3 due 4/1
• HW2 due 3/6
• HW1 due 2/19
• HW0 due 1/31

Lecture & reading schedule

Statistical learning

• Overview (1/22)
  • Reading: UML Chapter 1
  • Perceptron demo
• Concentration of measure (1/27, 1/29)
  • Reading: UML Appendix B (through B.4); moment bounds; proof of McDiarmid’s inequality
  • External notes: Akshay’s notes; Matus’s notes; Daniel’s notes
• Statistical learning (2/3, 2/5)
  • Reading: UML Chapters 2-4
  • Optional reading
• Empirical process theory (2/10, 2/12, 2/17, 2/19, 2/24, 2/26)
  • Reading: UML Chapters 6, 26-27; notes on Rademacher process, including contraction lemma
  • External notes: Akshay’s notes 1, 2, 3; Matus’s notes 1, 2
  • Optional reading
• Boosting and margins (2/26, 3/2, 3/4)
  • Reading: UML Chapter 10; notes on boosting
  • External notes: Akshay’s notes 1, 2; ensemble methods lecture from 4771; AdaBoost handout from 4771
  • Optional reading
• Convex surrogate losses (3/11, 3/30)
  • Reading: UML Chapter 12 (12.2 is optional)
  • External notes: Akshay’s notes; Matus’s notes; notes on gradient descent from 4771
  • Optional reading
• Approximation theory (3/30, 4/1)
  • Reading: UML Chapters 16, 20; Weierstrass approximation theorem
  • External notes: Akshay’s notes; Matus’s notes
  • Optional reading

Online learning

• Online learning with experts (4/6, 4/8)
  • Reading: Avrim Blum’s survey article (pdf) Section 2
  • Optional reading
• Multi-armed bandits (4/13, 4/15)
  • Reading: OLOCO Chapter 4
  • Optional reading
• Online convex optimization (4/20)
  • Reading: OLOCO Chapter 2

Unsupervised learning

• Mixtures of Gaussians (4/22)
  • Reading: FDS Chapter 2
  • Optional reading
• Best-fit subspaces (4/27, 4/29)
  • Reading: FDS Chapter 3, 12.7.8
  • External notes: notes on Davis-Kahan
  • Optional reading
• Spectral clustering (4/29, 5/4)
  • Reading: FDS Chapter 7.5
  • Optional reading