Lectures on Learning-Augmented Algorithms
Antonios Antoniadis, September-October 2019
Classical algorithms are usually designed with worst-case
performance guarantees in mind and do not adapt to
actual inputs. On the other hand approaches based on machine
learning are usually performing well in practice, specifically
because they are able to adapt to inputs. However their perfomance in
worst-case inputs can degrade significantly.
In learning-augmented algorithms we are interested to
design algorithms that may employ a
machine-learning predictor in order to become adaptive to
the input. Such a predictor will provide the algorithms with
predictions (of unknown quality) about the actual input, and for the
purpose of the algorithm designer this predictor can be seen as a
black box. The goal is to design an algorithm that incorporates
these predictions and provide performance guarantees based on their
quality. Ideally, the performance should improve
with the quality of the predictions, while even when the predictions are
bad the algorithm performance should not degrade by too
much (compared to the worst-case analysis).
Over three (or possibly four) lectures we will first introduce
the relevant concepts, and then investigate how this paradigm can be
used to develop improved algorithms for specific problems. The focus
will be mostly (but not exclusively) on online problems.
The lectures will take place in Room 024, Max Planck Institute
Building (E1.4), 15:30. Duration 75-90 minutes.
- The will be a fourth
lecture on October 9th. Notice that it will take place
in Room 023.
- The first three lectures will take place on
Wednesdays, September 18th, September 25th and October 2nd.
Schedule / Lecture Contents
- Lecture 1: Introduction. The concept of Learning Augmented
Algorithms. Quality measures: Competitive Ratio, Consistency and
Rubustness. First two examples: binary search and ski rental.
- Lecture 2:
- Lecture 3: Non-clairvoyant
- Lecture 4: Makespan scheduling
with restricted assignments.
References/Further Reading Material
- Near-Optimal Bounds for Online Caching with Machine Learned
Advice. D. Rohatgi, SODA 2020.
- Online Scheduling via Learned Weights. S. Lattanzi, T. Lavastida,
B. Moseley and S. Vassilvitskii. SODA 2020.
- Competitive Caching with Machine Learned Advice. T. Lykouris and
S. Vassilvitskii, ICML 2018.
Online Algorithms via ML Predictions. M. Purohit, Z. Svitkina
and R. Kumar, NIPS 2018
Algorithms for Rent-or-Buy with Expert Advice.
S. Gollapudi and D. Panigrahi, ICMLP 2019
- Scheduling with
Predictions and the Price of Misprediction. Michael
on Learning-Augmented Algogrithms.
- A new
dog learns old tricks: RL finds classic optimization
algorithms W. Kong, C. Liaw, A. Mehta and D. Sivakumar, ICLR 2019.