Course Information

• Course Info: CS7545, Spring 2024
• Course Time&Place: TuTh 3:30-4:45pm, Weber SST III (Lecture Hall 1)
• Course Staff:
  • Jacob Abernethy
    • Office: Coda S1221
    • Email: prof_at_gatech_dot_edu
    • Office Hours: Friday 2pm-3pm(1/19, 1/26, 2/2)
  • Tyler Labonte
    • Email: tlabonte_gatech_dot_edu
    • Office Hours: Friday 3pm-5pm(2/16, 2/23, 3/1)
  • Guanghui Wang
    • Email: gwang369_at_gatech_dot_edu
    • Office Hours: Friday 2pm-4pm(3/8, 3/15, 3/29, 4/5)
  • Yeojoon Youn
    • Email: yjyoun92_at_gatech_dot_edu
    • Office Hours: Friday 3pm-4pm(1/19, 1/26), Friday 9am-11am(2/2), Friday 3pm-5pm(2/9)

Course Description

This course will study theoretical aspects of prediction and decision-making probelms, and to explore the mathematical underpinnings of machine learning. We hope to bring students to the frontiers of research and to develop tools that can be used to contribute to emerging literature. The course will cover, among other things, concentration inequalities, uniform deviation bounds, Vapnik-Chervonenkis Theory, Rademacher Complexity, boosting, some theoretical aspects of deep learning, online learning theory, regret minimization, multi-armed bandit algorithms, and connections to convex optimization. Additional topics may be covered if time permits, including reinforcement learning theory, federated learning, etc.

Prerequisites: Familiarity with the analysis of algorithms, probabilistic analysis, and several similar topics. CS7641 (Machine Learning) may be helpful but not strictly necessary. The material will be about 90% “theory” and thus students must have a strong mathematical background. We shall rely heavily on techniques from calculus, probability, and convex analysis, but many tools will be reviewed in lecture.

Grade Breakdown:

• 60% Exams (in-class!)
• 30% Homeworks
• 10% Scribing/participation

Three Topic Segments, Three Exams

The course instruction will be divided into three segments, with a particular area of focus, a different lecturer, and will end with an exam. The agenda will go as follows.

• Segment 1
  • Topic. Basic tools for learning: linear algebra, convex analysis, probability, deviation bounds, martingales.
  • Instructor. Prof. Jake Abernethy
  • Exam. In class on Tuesday 1/30/2024 2/6/2024
• Segment 2
  • Topic. Statistical learning theory: generalization bounds, uniform convergence, VC theory, Rademacher complexity.
  • Instructor. Tyler Labonte
  • Exam. In class on Tuesday 2/27/2024 3/5/2024
• Segment 3
  • Topic. Online learning and optimization: sequential learning framework, regret minimization, online convex optimization, multi-armed bandits.
  • Instructor. Guanghui Wang
  • Exam. In class on Tuesday 4/2/2024 4/9/2024

Note: this will leave around 5-6 lectures at the end of the course. We will use this as “extra-curriculur” time and we may have a set of guest lectures on special topics.

Homework

We’re going to try something different this semester: one homework problem per lecture!

During lectures, the presenting instructor will state one or more problems, with some of these clearly marked HOMEWORK. They will also be added to the lecture notes on the course wiki. The goal of these problems is to get students to engage with the material, and to make sure they understand the course material. Our homework policy is as follows:

• We encourage, but do not require, students to complete the problems within the week they are given out. Doing small bits of work to keep up with the course material is the best way to learn the material gradually.
• We require all of the homework problems for each segment of the course to be completed four days before the exam. We will release solutions at this time, and homework will not be accepted later than this date.
• While exams will be graded in detail, homework will be lightly graded according to this rubric:
  • 0 points for no submission
  • 1 point for any attempt at the problem
  • 2 points for a correct, or even mostly-correct, answer
• We strongly encourage students to use LaTeX to typeset solutions. Handwritten solutions are acceptable but discouraged.
• We will soon post details on Piazza for how to submit homework solutions.

Lecture notes

Every lecture will have two student scribes, and this pair of students will be asked to take detailed notes in class on what was covered. The quality of these notes will be graded!

Grade Rubric:

• 20% - punctuality
• 40% - correctness
• 40% - readability

Here is the course wiki.

Note: all students are allowed and encouraged to contribute to this wiki! Once the scribes have submitted their notes, other students are welcome to add any additional comments, results, material, etc. to the lecture notes. It would be great if the wiki provides a broad set of resources for students, beyond what was covered in lecture.

References:

The bulk of material from the course will follow material from the following texts:

• “Foundations of Machine Learning” by Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar
• The convex optimization approach to regret minimization survey by Elad Hazan.

Much of the material in online learning is specific to this course. For students that want more in-depth reading material on this topic, however, there are several surveys released in the last several years that explore several many areas we shall cover. These include:

• Understanding Machine Learning: From Theory to Algorithms by Shai Shalev-Shwartz and Shai Ben-David
• A Modern Introduction to Online Learning by Francesco Orabona
• Online Learning and Online Convex Optimization survey by Shai Shalev-Shwartz.
• Sasha Rakhlin’s Lecture Notes.

The Latex template for HW submissions is available here.

Previous offerings of the course:

• Fall 2018
• Fall 2019
• Fall 2023

Homeworks

Homework	Due Date	Solution
Homework 1	February 2, 2024, 11:59 pm	HW1 solution
Homework 2	March 1, 2024, 11:59 pm	HW2 solution
Homework 3	April 5, 2024, 11:59 pm	HW3 solution