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 homework assignments (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 test/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 I
16. 11/20: Algorithms with Predictions II
17. 12/02: Learning Predictions for Algorithms with Predictions I
18. 12/04: Learning Predictions for Algorithms with Predictions II

Recommended Readings

• Beyond the Worst-Case Analysis of Algorithms (edited by Tim Roughgarden).
  • Chapter 5: Perturbation Resilience by Konstantin Makarychev and Yury Makarychev
  • Chapter 29: Data Driven Algorithm Design by Maria-Florina Balcan
• More to come...