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.


Schedule / Lecture Contents

References/Further Reading Material