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.

News:

• 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: Paging/Caching.
• Lecture 3: Non-clairvoyant scheduling.
• 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.
• 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.