Machine Learning for Algorithm Design

Overview

Machine learning presents both opportunities and challenges to the design of algorithms. Machine learning can be used to automate the selection of algorithms as well as to improve the performance of traditional algorithms. However, due to the rise of machine learning, algorithms are increasingly optimizing noisy models learned from data and handling extremely large datasets.

This topics course covers recent developments on the role of machine learning in the design of algorithms, with a strong emphasis on both modeling and algorithmic techniques. The course is organized in the following four parts:

  1. Optimization from samples
  2. Learning-augmented algorithms
  3. Parallel, distributed, and streaming algorithms
  4. Data-driven algorithm design

Prerequisites. This is a mathematically rigorous course. There are no formal pre-requisites, but mathematical maturity is recommended.

Goals. The goal of this course is to expose students to advanced topics at the intersection of algorithm design and machine learning. To this end, the course will mainly cover recent papers and encourage research in this area.

Assessment

The main component of this course will be a research project (60%). Assignments also include a presentation of a research paper (20%) and two problem sets (20%).

Research project. The project can be theoretically-focused, data-oriented, or a combination of both on any topic broadly related to one (or more) of the four parts of the course. Ideas for how to choose a project will be discussed in class. Students will work on their project in groups of two. The main milestones are:
• One page project proposal, due on 10/19.
• 5 min presentation of current project status in class on 11/4
• 30 min meeting with the instructor for each group in November
• Final write-up (6 to 10 pages), due on 12/13
• Final presentation during last class on 12/14

Paper presentations. A number of classes will be devoted to paper presentations. During each of these classes, one or two students will present a research paper for around 1 hour. The remaining 15 minutes of that class will consist of a class discussion of the paper presented. For each paper presentation, all students are expected to read before class at least the abstract and introduction of the paper being presented. Students will do a practice presentation with the instructor 1 or 2 days before the class where they are presenting. Students will be able to choose which paper they present based on a first-come first-serve basis. A sign-up sheet will circulate during the second
week of classes.