Time and Place:
MonWed 5  6:20 PM in Peter 103 (Peterson Hall).
Instructor:
Raef Bassily
Email: rbassily at ucsd dot edu
Office Hrs: Thu 56 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 *

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 *

Week 4: 4/ 18, 20 
 Set Shattering: Intro to VapnikChervonenkis (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). *
 Boosting: Weak vs. Strong Learnability 
Week 6: 5/ 2, 4 
 Boosting: Adaboost *
 AgnosticPAC 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 ConvexLipschitzBounded Problems *
 Stochastic Gradient Descent:
* Basic GD Algorithm and Convergence Guarantees.
* Projected Stochastic Gradient Descent.
 Learning via Stochastic Gradient Descent. **

Weeks 9 & 10: 5/ 23, 25 & 6/ 1 
 Regularization and Stability
* Regularized Loss Minimization and Balancing BiasComplexity
* Regularization as a Stabilizer: Stable algorithms do not overfit.
* Learning via RLM *  Other suggested topics and Concluding Remarks 
Announcements:
 Introductory Lecture: Course overview and Administrative Information can be found here.
 Homework 1 is up (due April 20).
 Homework 2 is up (due May 4).
 Bonus Quiz (due with the Final exam submission)
 Midterm: You have the option to resubmit the midterm as an additional assignment by May 18. For those who are willing to resubmit their midterm solution, a fraction of the midterm 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 inclass 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 miniproject 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 4unit course. The evaluation in this course will be based on
 Homeworks (potentially including one miniproject): 45%
 A midterm exam: 20%
 A Final TakeHome exam: 35%
 A bonus of up to 5% for those who actively engage in discussions and answer questions on piazza!
Discussion Forum:
Please signup 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. ShalevShwartz, S. BenDavid,
Understanding Machine Learning: From Theory to Algorithms.

