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.

- 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: Paging/Caching.
- Lecture 3: Non-clairvoyant scheduling.
- Lecture 4: Makespan scheduling with restricted assignments.

- 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.
- Improving Online Algorithms via ML Predictions. M. Purohit, Z. Svitkina and R. Kumar, NIPS 2018
- Online Algorithms for Rent-or-Buy with Expert Advice. S. Gollapudi and D. Panigrahi, ICMLP 2019
- Scheduling with Predictions and the Price of Misprediction. Michael Mitzenmacher, arXiv.
- Materials from MIT-Course 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.