Time and Place:
Mon-Wed 5 - 6:20 PM in Peter 103 (Peterson Hall).
Instructor:
Raef Bassily
Email: rbassily at ucsd dot edu
Office Hrs: Thu 5-6 PM, Atkinson Hall 4111.
Course Schedule: (Times and contents may slightly vary depending on the class progress)
| Week 1: 3/ 28, 30 |
- Introduction and Course Overview
- Probability Tools and Concentration Inequalities
Lecture notes (Part 1)
|
| Week 2: 4/ 4, 6 |
- Framework of Statistical Learning, Empirical Risk Minimization
- PAC Learning Model |
| Week 3: 4/ 11, 13 |
- PAC Learning, Occam's Razor
- Agnostic PAC Learning and the Uniform Convergence Principle
Lecture notes (Part 2)
|
| Week 4: 4/ 18, 20 |
- Set Shattering: Intro to Vapnik-Chervonenkis (VC) dimension
- VC dimension: Examples, Discussion and Implications, and the Growth function |
| Week 5: 4/ 25, 27 |
- VC dimension: Sauer's Lemma
- The Fundamental Theorem of Learning (Characterization of Learnability via VC dimension).
Lecture notes (Part 3)
- Boosting: Weak vs. Strong Learnability |
| Week 6: 5/ 2, 4 |
- Boosting: Adaboost
Lecture notes (Part 4)
- Agnostic-PAC Learning in the Generalized Loss Model |
| Week 7: 5/ 9, 11 |
- Midterm (on May 9th)
- Brief Intro to Convex Analysis: Convex, Lipschitz functions.
|
Week 8: 5/ 16, 18 |
- Learnability of Convex-Lipschitz-Bounded Problems
- Stochastic Gradient Descent:
* Basic GD Algorithm and Convergence Guarantees.
* Projected Stochastic Gradient Descent.
- Learning via Stochastic Gradient Descent.
SGD Part I
SGD Part II |
| Weeks 9 & 10: 5/ 23, 25 & 6/ 1 |
- Regularization and Stability
* Regularized Loss Minimization and Balancing Bias-Complexity
* Regularization as a Stabilizer: Stable algorithms do not overfit.
* Learning via RLM
|
Announcements:
- Introductory Lecture: Course overview and Administrative Information can be found here
- Calibration Quiz: Solutions
- Homework 1 is up (due April 20).
- Homework 2 is up (due May 4).
- Bonus Quiz (due with the Final exam submission)
- Mid-term: You have the option to resubmit the mid-term as an additional assignment by May 18. For those who are willing to resubmit their mid-term solution, a fraction of the mid-term final grade will be awarded based on the resubmission. This is completely optional (if you are not willing to resubmit, your grade will be based entirely on your first in-class submission).
- Homework 3 (the mini project) is up (due June 1).
- Final Exam (Due June 9, by 1 PM).
Course Overview:
The course will be aiming mainly at explaining the main 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 contain rigorous mathematical proofs and analyses. The class will cover wide array of topics starting from the basic models and concepts: PAC learning, uniform convergence, generalization, VC dimensions, and building on those to discuss more complex models and algorithmic techniques, e.g., Boosting, Convex Learning, Regularization, and Stochastic Gradient Descent.
Prerequisites:
Decent 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:
- There will be at least 3 homework assignments.
- Each homework assignment will be posted on this page when enough material is covered in class. An announcement will be made in class and on this page when a homework is up and a due date will also be specified.
- Students should return their homework in class on the specified due date before the lecture starts (if you arrive late, then please, wait until the lecture ends).
- No late homeworks will be accepted.
- Solutions of most problems will involve proofs. Grading will be based on both correctness and clarity. Also, solutions need to be concise.
- The last homework will potentially include a mini-project on implementation/evaluation of one of the algorithmic techniques discussed in class.
- Each student can choose one homework partner to collaborate with in solving the homeworks.
- It is up to you whether you want to have a homework partner or work by yourself. However, if you choose not to have a homework partner, please, do not expect any extra credit for that.
- Each homework group needs to send me their names by email no later than April 13.
- Collaboration with students other than your homework partner is not allowed. However, discussion of the class material (not including homework problems) among students is encouraged (outside the classroom as well as on piazza).
Grading Policy:
- This is a 4-unit course. The evaluation in this course will be based on
- Homeworks (potentially including one mini-project): 45%
- A mid-term exam: 20%
- A Final Take-Home exam: 35%
- A bonus of up to 5% for those who actively engage in discussions and answer questions on piazza!
Discussion Forum:
Please sign-up here to join the discussion forum of this class on Piazza.
Supplementary readings:
- M. J. Kearns, U. V. Vazirani, An Introduction To Computational Learning Theory.
-
S. Shalev-Shwartz, S. Ben-David,
Understanding Machine Learning: From Theory to Algorithms.