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.


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


Additional suggestions for resources are welcome!
Please send your recommendations to Daniel Dadush (dadush AT cwi DOT nl).