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
11/24: Intro to Adagrad; Reading: Chapter 5.6 from this manuscript
11/26: NO CLASS: THANKSGIVING BREAK
11/29: Adagrad contd..; Reading: Chapter 5.6 from this manuscript
12/1: final lecture: video by Sanjeev Arora on mathematics of deep learning
12/3: final student project presentations