Time and Place:
Tue-Thu 5 - 6:20 PM in HSS 1330 (Humanities and Social Sciences Bldg).
Instructor:
Raef Bassily
Email: rbassily at ucsd dot edu
Office Hrs: Thu 3-4 PM, Atkinson Hall 4111.
TAs:
- Andrew Leverentz (aleveren@eng.ucsd.edu) - Office Hrs: Wed 4-5 PM (CSE Basement B260A)
- Chicheng Zhang (chz038@cs.ucsd.edu) - Office Hrs: Mon 11 AM - 12 PM (CSE Basement B240A)
Course Schedule: (Times and contents may slightly vary depending on the class progress)
Week 1-2:
- Introduction and Course Overview
- Probability Tools and Concentration Inequalities
Week 2:
- Framework of Statistical Learning, Empirical Risk Minimization
- PAC Learning Model
Week 3:
- PAC Learning: Examples
- General Bound on Sample Complexity for Finite Hypothesis Classes (Occam's Razor)
Week 4:
- Agnostic PAC Learning and the Uniform Convergence Principle
- Set Shattering: Intro to Vapnik-Chervonenkis (VC) dimension
- VC dimension: Examples, Discussion and Implications, and the Growth function
Week 5:
- VC dimension: Sauer's Lemma
- The Fundamental Theorem of Learning (Characterization of Learnability via VC dimension).
Week 6:
- Boosting: Weak vs. Strong Learnability
- Adaboost
Week 7:
- Agnostic-PAC Learning in the Generalized Loss Model
- Intro to Convex Analysis: Convex, Lipschitz functions.
- Learnability of Convex-Lipschitz-Bounded Problems
Week 8:
- Stochastic Gradient Descent:
* Basic GD Algorithm and Convergence Guarantees.
* Projected Stochastic Gradient Descent.
- Learning via Stochastic Gradient Descent.
Weeks 9 & 10:
- Regularization and Stability
* Regularized Loss Minimization and Balancing Bias-Complexity
* Regularization as a Stabilizer: Stable algorithms do not overfit.
* Learning via RLM
Suggested Future Topics & Concluding Remarks
Announcements:
Course Overview:
The course main goal is to explain the fundamental concepts underlying machine learning and the techniques that transform such concepts into practical algorithms. The main focus will be on the theoretical foundations of the subject, and the material covered will include rigorous mathematical proofs and analyses. The class will cover wide array of topics: starting from basic concepts such as PAC learning, uniform convergence, generalization, Vapnik-Chervonenkis (VC) dimension, and will build upon those to study more complex concepts and algorithmic techniques such as: boosting, convex learning, stochastic gradient descent, regularization and stability.
Prerequisites:
Good knowledge of probability and multivariate calculus is required. Students should be comfortable working with mathematical abstractions and proofs. Some previous exposure to machine learning is recommended.
Homeworks:
Grading Policy:
Class Forum on Piazza:
Please sign-up here to join the discussion forum of this class on Piazza. Do not miss the important announcements and discussions that take place there!
Supplementary readings: