Modern Paradigms in Learning and Decision-Making

Class Overview

This is an advanced graduate level course covering recent advances in machine learning theory, with a particular focus on topics at the intersection of algorithms and society. The course will provide an overview of areas such as multicalibration, performative prediction, sequential decision-making, and verification of learning with the goal of enabling students to conduct their own research projects in these areas.

A thread unifying the various topics of the course is that machine learning algorithms actively shape the world around us. They inform medical treatments, bail decisions, determine our social networks, and access to social goods. Given their impact and ubiquity, we will explore formal answers to questions such as:

• How do we decide whether an algorithmic prediction is valid?
• What is an “individual” probability? What does it mean to forecast non-repeatable events?
• When can we trust (or efficiently check!) that predictors or generative models enable good decisions?

Course Staff

• Professor: Juan Carlos Perdomo — j.perdomo.silva[at]nyu.edu
• Course Assistant: Justin Li — jdl8238[at]nyu.edu

Meeting Times and Locations

• Lectures: Wednesdays from 6:30 to 9pm. Jacobs Hall, Room 201
• Instructor office hours: Wednesdays from 5–6pm. 370 Jay St, Brooklyn, Office 1102
• CA office hours: Mondays from 4–5pm. 60 5th Ave, 3rd Floor

Prerequisites

This is a theory course. Students are expected to have mathematical maturity at the level of a first year graduate student and feel comfortable with formal mathematical arguments in linear algebra, probability, and the analysis of algorithms.

Grading

Problem Sets, 20%. In Class Exam, 40%. Final Project, 40%.

Final Project

Students will complete a final project which can consist of a piece of original research or an simplifed exposition of a paper or series of papers. The project can be theoretical or empirical in nature.

Students will be expected to meet with the course staff during the semester to discuss their projects and receive feedback. They are free to work individually, or (better yet) in teams of 2. More details on the structure of the project will be available soon.

Course Resources

There is no required textbook. Course material will be drawn from lecture notes written by the instructor, and a collection of papers and surveys posted alongside each lecture in the schedule below. The following textbooks are excellent references for background material.

• Convex Optimization by Stephen Boyd and Lieven Vandenberghe
• High-Dimensional Probability by Roman Vershynin
• Introduction to Online Convex Optimization by Elad Hazan

Lecture Schedule

The schedule below is tentative and subject to change.