Guarantees in Machine Learning


Course basics

Logistics

  • Time and Place: Wednesdays 8-10am, online over zoom (previously: CAB G 51)
  • Starting March 18, lectures will also be recorded and posted online
  • Instructor: Fanny Yang
  • Teaching assistants:
    • Alexandru Tifrea (tifreaa at inf.ethz.ch), Amir Joudaki (ajoudaki at inf.ethz.ch)
    • Office hours: Monday, 4-5 pm, online over zoom upon request via email (previously: CAB G 69.3)
  • Sign up on waitlist until March 1st, fill out form
  • De-register until March 13th
  • Piazza (Announcements, Discussion of homeworks and classes)
  • gradescope enroll with entry code 975DPG (homeworks)
  • eduApp online (in-class check-ins and feedback)

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

How to get there

  1. understand and apply known and new generalization concepts for ML guarantees
  2. critically read papers by assessing strengths and weaknesses using clear evidence, conjecture and prove new research questions that are impactful
  3. communicate own ideas, results and knowledge efficiently in a paper and presentation
  4. Learn to collaborate

Evaluation

  • 10% HW, 50% oral midterm, 40% project
  • Homework:
    • some graded homework problems
    • rest is self-graded (mandatory hand-in)
  • Project report and presentation: see project website
  • Presence is mandatory in the last four weeks of classes during presentations

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. Ensure that the following appear on the first page of the write-up:

    • your name,
    • your Student ID, and
    • the names and IDs of any students with whom you discussed the assignment.

  • Submit your write-up, one page per question, as a single PDF file by 11:59 PM of the specified due date to gradescope. Follow the instructions and mark the pages that belong to the corresponding questions. See more details on the homework sheet.

  • Some questions will be graded by the TAs. All questions will be self-graded by you.

  • Discussions on piazza

Academic integrity for homeworks

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.

  • For homeworks 1-2, you may discuss only at a high level with up to three classmates; please list their IDs on the first page of your homework. Everyone must still submit an individual writeup, 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

  • Subject to frequent changes, check back often!
  • Assignments are released and due on the Friday of the week, if not specified otherwise
  • The slides are not shown as is during lecture, but they contain a superset of the content of each lecture
Date Topic Material Assignments
19.2 Logistics, Uniform convergence, Rademacher complexity MW 2, 4 HW 1
26.2 Uniform law proof, VC dimension and Rademacher contraction MW 4 HW 1 due
4.3. Margin bounds, metric entropy and chaining MW 5 HW 1 sol
11.3. Chaining, Localized complexities and critical inequality MW 5, 13 HW 2, HW 1 selfgrade due
18.3. Non-parametric regression, from feature maps to RKHS [Lec Pt. 1 Lec Pt. 2], [Live notes] MW 12, 13 Project proposal
25.3. From kernels to RKHS, Error bounds for RKHS [Lecture video] [Live notes] MW 12, 13 HW 2 due, HW 2 sol
1.4. Mercer and Bochner’s theorem, random features, 2-layer NN [Lecture video] [Live notes] MW 12, SC 4 HW 2 selfgrade due
8.4. Gaussian process vs. penalized regression, Random design[Lecture video][Live notes] MW 13, 14 HW 3
15.4. Holidays, enjoy!
22.4. Minimax lower bounds[Lecture videos][Live notes] MW 15 HW 3 sol, HW 3 due
29.4. Midterm
6.5. Implicit regularization: Theory and practice[Lecture videos] Mid-Project drafts due
13.5. Presentations 1, see full schedule
20.5. Presentations 2, see full schedule
27.5. Presentations 3, see full schedule
14.6. 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