MCS548: Mathematical Theory of Artificial Intelligence

Fall 2021

Basic Information

Instructor: Aditya Potukuchi

Lecture: MWF 1:00PM-1:50PM 215 LH

Office hour: MW 4:00PM-5:00PM 628 SEO (also let me know if you want to meet via zoom)

Problem sets

Schedule

8/23: Introduction, probability recap; Reading: Chapter 1, Appendix C

8/25: Hoeffding's inequality, McDiarmid's inequality; Reading: Appendix D.1, D.2, D.7

8:27: Intro to PAC learning, guarantees for finite hypothesis classes; Reading: Chapter 2 (Ch. 2.4 optional)

8/30: PAC guarantees for finite hypothesis classes contd.., Intro to Rademacher Complexity; Reading: Chapter 2, Chapter 3.1

9/1: PAC guarantees for classes with low Rademacher complexity; Reading: Chapter 3.1

9/3: Intro to SVM, separable case; Reading: Chapter 5.1 - 5.2.3

9/6: NO CLASS: Labor day

9/8: SVM separable case contd.., learning guarantees; Reading: Chapters 5.2, 5.3

9/10: SVM non-separable case; Reading: Chapter 5.3

9/13: SVM margin guarabtees; Reading Chapter 5.4

9/15: Intro to boosting; Reading: Chapter 7.1, 7.2

9/17: student project presentations

9/20: ADABOOST analysis; Reading: Chapter 7.2

9/22: ADABOOST analysis contd.., coordinate descent POV, margin guarantees; Reading: Chapter 7.3

9/24: student project presentations

9/27: Introduction to online learning, Weighted Majority Algorithm; Reading: Survey by Arora-Hazan-Kale

9/29: Multiplicative Weight Update analysis, intro to hypergraph discrepancy; Reading: Survey by Arora-Hazan-Kale

10/1: student project presentations

10/4: MWU algorithm for discrepancy minimization; Reading: Paper by Levy-Ramadas-Rothvoss

10/6: Intro to regression, generalization bounds; Reading: Chapter 11.2

10/8: student project presentations

10/11: Linear regression, kernel ridge regression, Lasso; Reading: Chapter 11.3

10/13: Perceptron algorithm; Reading: Blum-Hopcroft-Kannan, Chapter 5.2

10/15: student project presentations

10/18: Intro to stochastic gradient descent; Reading: Blum-Hopcroft-Kannan, Chapter 5.9

10/20: Analysis of stochastic gradient descent; Reading: Blum-Hopcroft-Kannan, Chapter 5.9

10/22: Intro to VC-dimension, sample complexity; Reading: Alon-Spencer (4th ed.), Chapter 14.4

10/25: Optimal sample complexity for bounded VC-dim; Reading: paper by Steve Hanneke

10/27: Optimal sample complexity for bounded VC-dim contd..; Reading: paper by Steve Hanneke

10/29: student project presentations

11/1: Intro to stochastic block model + spectral clustering; Reading: Blum-Hopcroft-Kannan, Chapter 7.5

11/3: Regularization of sparse random matrices; Reading: paper by Le-Levina-Vershynin

11/5: student project presentations

11/8: Backprop algorithm; Reading: Chapter 3 from this book draft

11/10: PAC-Bayes bounds; Reading: Chapter 4 from this book draft

11:12: student project presentations

11/15: Youtube video on talk by Cynthia Rudin

11/17: Universal Approximation by neural networks; Reading: Chapter 2, notes by Matus Telgarsky

11/19: student project presentations

11/22: Second order gradient methods; Reading: TBA