Reading Group on Learning Augmented Algorithms
This reading group will cover the emerging area of learning augmented
algorithms, which studies how to design algorithms to take advantage of an
untrusted predictor. The predictor may give information about the input
sequence or may give a partial information about the structure of an optimal
solution. The goal is to design algorithms that perform near-optimally when
the predictor is accurate, while gracefully degrading to worst-case
performance guarantees when the predictor is wrong. The origin and main
motivation comes from machine learning, where the predictor is typically
thought of as a black-box machine learning algorithm (e.g., a neural net).
The reading group aims to cover the range of applications for the learning
augmented approach and to stimulate new research directions in the area.
Organizers: Antonios Antoniadis (Twente), Daniel Dadush (CWI), Lars Rohwedder (Maastricht)
- Time: 3:30pm-5pm Tuesdays, bi-weekly (February 15th - June 7th, 2022)
- Location: Zoom
Meeting ID: 814 4415 3462
Passcode: 260407
- Recordings and Lectures Notes: Surfdrive (password protected)
Please email Daniel Dadush (dadush at cwi dot nl) if you want to be added to
the mailing list or if you would like to present a paper.
Format:
The first part of each session will last about 1 hour, with a 45-50min talk
followed by 5-10 minute Q&A. After a 5-min break, the second part will be
25-30 min consisting of either an additional technical presentation (covering
technical details skipped in the main presentation) OR an open discussion
session (longer technical questions, open problems, brainstorming).
Schedule (Spring 2022):
| Date | Topic | Literature | Speaker |
| February 15 | Competitive caching with machine learned advice | Lykouris, Vassilvitskii | Antonios Antoniadis |
| March 1 | Improving Online Algorithms via ML Predictions (Ski Rental / Scheduling) | Kumar, Purohit, Svitkina | Daniel Dadush |
| March 15 | The Primal-Dual method for Learning Augmented Algorithms | Bamas,Maggiori, Svensson | Danish Kashaev |
| March 29 | Learning Augmented Energy Minimization via Speed Scaling | Bamas, Maggiori, Rohwedder,Svensson | Lars Rohwedder |
April 12 | Faster Matchings via Learned Duals | Dinitz, Im, Lavastida, Moseley, Vassilvitskii | Sander Borst |
April 26 | Permutation Predictions for Non-Clairvoyant Scheduling
| Lindermayr, Megow | Nicole Megow |
| May 10 | Online Metric Algorithms with Untrusted Predictions
| Antoniadis, Coester, Elias, Polak, Simon | Christian Coester |
| May 23 (MONDAY!) | Secretary and Online Matching Problems with Machine Learned Advice
| Antoniadis, Gouleakis, Kleer, Kolev | Pieter Kleer |
| June 7 | Open Problem Session
| N/A | TBA |
Resources:
Additional suggestions for resources are welcome!
Please send your recommendations to Daniel Dadush (dadush AT cwi DOT nl).
|