TTIC 31290 - Machine Learning for Algorithm Design (Autumn 2025)

Lectures: Tue/Thu 9:30-10:50 in TTIC 530

Instructors: Avrim Blum (Office hours: TBD) and Dravyansh Sharma (Office hours: TBD)

Course description: This course will cover the theoretical foundations for using machine learning in algorithm design. Algorithm design has classically been studied either on worst-case inputs (worst-case analysis), or random inputs (average-case analysis). However, for many problems, typical instances are neither worst-case nor uniform random, and one would instead like to use past data to design an algorithm that will perform well on new instances from a given domain. The use of machine learning for algorithm design has a long history in AI and there have been substantial recent developments in Theory. This course will cover fundamental theoretical topics in this area including statistical and online models for data-driven algorithm design, analytical tools for proving generalization bounds and regret bounds, analysis of learning-augmented algorithms (algorithms with predictions), and non-worst-case models such as smoothed analysis, perturbation stability, and semi-random input models.

Prerequisites: Intro to Machine Learning (or equivalent) and Algorithms (or equivalent). This is a proof-oriented course.

Evaluation: Grades will be based on 4 homeworks (60%), a course project (15%), class participation (10%), and a final (15%). Each student will be asked to help with grading one of the assignments as part of the class participation component.

Textbook: There is no single textbook for this course, although we will refer to several chapters of the book Beyond the Worst-Case Analysis of Algorithms (edited by Tim Roughgarden). Please see the "Recommended texts/readings" section below for some useful references.

Homeworks

• TBD

Lecture Notes and Tentative Plan

1. 09/30: Classic approaches to hard problems I: Approximation Algorithms

2. 10/02: Classic approaches to hard problems II: Fixed Parameter Tractability and Average Case Analysis

3. 10/07: Beyond Worst-Case Analysis I: Semi-Random Models and Smoothed Analysis

4. 10/09: Beyond Worst-Case Analysis II: Perturbation-Resilience and Approximation-Stability

5. 10/14: Typical Case Analysis: Introduction to Data-driven Algorithm Design

6. 10/16: Some fundamental concepts from Learning Theory

7. 10/21: The Fundamental Theorem of Statistical Learning

8. 10/23: General tools for piecewise-structured duals

9. 10/28: Applications to classical algorithms: Dynamic Programming, Graph Algorithms

10. 10/30: Applications to Hyperparameter Tuning in Machine Learning

11. 11/04: Applications to Automated Mechanism Design

12. 11/06: Applications to Operations Research: Mixed-Integer Programming

13. 11/11: Online Learning under Smoothed Adversaries

14. 11/13: Lower bounds and impossibility results

15. 11/18: Algorithms with Predictions

16. 11/20: TBD

17. 11/25, 11/27: Thanksgiving Break

18. 12/02, 12/04: TBD

Recommended texts/readings:

• Beyond the Worst-Case Analysis of Algorithms (edited by Tim Roughgarden).

• More to come…