Guarantees in Machine Learning


Course basics

Logistics

  • Time: Tuesdays 10-12 CAB G59, Fridays 14-16 CHN G 42
  • Lectures will not be recorded! This is an in-person only class
  • Instructor: Fanny Yang
  • Teaching assistants:
    • Tobias Wegel (tobias.wegel at inf.ethz.ch), Julia Kostin (julia.kostin at inf.ethz.ch)
    • Office hours: upon request via email
  • Sign up on waitlist until September 26th
  • De-register until October 8th - if you don’t appear to the oral exam and do not present a project, it will count as a no-show

We will use the following online platforms

  • All material(homeworks, slides, links) will be uploaded to this website
  • Please ask all of your questions in moodle, and if you’re even actively answering other people’s questions, eternal gratitude from your peers is ensured ;). If you’re still on the waitlist, you can enroll using the password Dudley@ETH2025

Learning objectives

This course is designed to prepare master students for successful research in ML, and prepare PhD students to find new research ideas related to ML theory. Content wise, the technical part will focus on generalization bounds using uniform convergence, and non-parametric regression.

By the end of the course

  • both easily read and write theorems that provide generalization guarantees for machine learning algorithms
  • find high-impact questions and theorems to prove and work on that you are highly passionate about

Learning objectives

  1. acquire enough mathematical background to understand a good fraction of theory papers published in the typical ML venues. For this purpose, students will learn common mathematical techniques from statistics and optimization in the first part of the course and apply this knowledge in the project work

  2. critically examine recently published work in terms of relevance and determine impactful (novel) research problems. This will be an integral part of the project work and involves experimental as well as theoretical questions

  3. find and outline an approach (some subproblem) to prove a conjectured theorem. This will be practiced in lectures / exercise and homeworks and potentially in the final project.

  4. effectively communicate and present the problem motivation, new insights and results to a technical audience. This will be primarily learned via the final presentation and report as well as during peer-grading of peer talks.

Evaluation

  • 60% oral midterm, 40% project, 0% HW (but passing required to take midterm)
  • Homework:
    • you pass a homework (there are two) if we see that you properly attempted all questions (except the bonus ones that are a service to you). A genuine attempt means showing your reasoning, intermediate steps, or explanation
    • if you fail one homework out of two and do not de-register by the above deadline, you will not be able to take the oral exam and obtain a no-show
  • Project report and presentation: see project website for grading information
  • Presence is mandatory in the last four weeks of classes during presentations. You’re also asked to give feedback to peers and if your presentation grade itself is in between two grades, the helpfulness of your feedback to others will be taken into account.

Additional homework information

  • Homeworks are designed to
    • do some technical (“just algebra”) work that needs to be practiced individually
    • learn how to read more material on the matter effectively (homework content will be part of the midterm exam!)
  • No late homework
  • Each homework write-up must be neatly typeset as a PDF document using TeX, LaTeX, or similar systems (for more details see below). This is for you to practice getting efficient at it. Make sure you indicate on the first page, which students you discussed the assignment with, but do not add your own name to the sheet.
  • Submit your write-up as a single PDF file by 11:59 PM of the specified due date via email to tobias.wegel at inf.ethz.ch
  • All questions will be reviewed by the TAs.
  • Questions and discussions on moodle

Academic integrity for homework

As graduates students we expect you to take this class because you want to learn the material and how to do research. All assessments are designed to maximize the learning effect. Cheating will harm yourself and hence it is of your own interest to adhere to the following policy.

  • All homework is submitted individually, and must be in your own words.

  • You may discuss only at a high level with up to two classmates; please list their IDs on the first page of your homework. Everyone must still submit an individual write-up, and yours must be in your own words; indeed, your discussions with classmates should be too high level for it to be possible that they are not in your own words.

  • We prefer you do not dig around for homework solutions; if you do rely upon external resources, cite them, and still write your solutions in your own words.

  • When integrity violations are found, they will be submitted to the department’s evaluation board.

Schedule & course content

  • Links to files are intentionally not active until you get the announcement
  • Subject to frequent changes, check back often!
  • The slides are not shown as is during lecture, but they contain a superset of the content of each lecture
Date Topic Location Material Assignments
16.9 Lecture: Introduction and concentration bounds (Recording) CAB G59 MW 2
19.9 Lecture: Uniform tail bound and McDiarmid CHN G42 MW 2,3,4
23.9. no class
26.9. Lecture: Azuma-Hoeffding and the uniform law CHN G42 MW 4 HW 1
30.9. Lecture: Uniform law and Rademacher complexity CAB G59 MW 2,4
3.10. Lecture: VC bound and margin bounds Exercise sheet CHN G42 SS 7, 26
7.10. Lecture: Metric entropy CAB G59 MW 5 HW 1 and de-registration due by 8.10. 23:59, HW 1 sol
10.10. Lecture: Chaining CHN G42 SS 26
14.10. No class Project sign-up 14:00
17.10. No class
21.10. Lecture: Non-parametric regression and kernels CAB G59 SC 4, MW 12, 13
24.10. Lecture: Kernel ridge regression CHN G42 MW 13 Project proposals due
28.10. Lecture: Random design CAB G59 MW 14 HW 2
31.10. Lecture: Minimax lower bounds CHN G42 MW 15
4.11. Lecture: Minimax lower bounds CAB G59 MW 15
7.11. Interactive session: Multi-objective learning CHN G42 Exercise sheet Solution
11.11. [Lecture: Double Descent] CAB G59 HW 2 due 23:59, HW 2 sol
14.11. No class
17./18.11. ORALS
21.11. Guest lecture CHN G42
25.11. Guest lecture CAB G59
28.11. Guest lecture by Amartya Sanyal CHN G42 Presentation draft due
2.12. No class
5.12. No class
9.12. [Presentations 1], see full schedule CAB G59
12.12. [Presentations 2], see full schedule CHN G42
16.12. [Presentations 3], see full schedule CAB G59
19.12. [Presentations 4], see full schedule CHN G42 [Peer-grading due]
12.1. No class Project reports due

References

Course content

Links to books are online resources free from the ETH Zurich network:

Learning Theory

Some more background reading for your general wisdom, knowledge and entertainment

Typesetting

  • For LaTeX, see 1, 2 or 3, 4
  • For Pandoc Markdown by John McFarlane, refer to my git repo with sample instructions on how to use Pandoc for simple math notes and webpages