Beyond worst-case: the rise of learning-augmented online algorithms

Online algorithms are traditionally analysed in adversarial worst-case settings, leading to guarantees that often fail to capture practical performance. The emerging framework of learning-augmented algorithms integrates machine-learned predictions into online decision making while preserving rigorous guarantees. These algorithms are designed to be consistent (near-optimal when predictions are accurate), robust (competitive even under adversarial errors) and smooth if their performance degrades gracefully as prediction quality deteriorates. This talk surveys recent advances in the area, emphasising problems where predictions provably overcome long-standing competitive-ratio barriers. I will mostly focus on: (i) secretary and online matching problems enhanced by machine-learned advice from [1] and [2], as well as (ii) online facility location with predicted optimal centres from [3]. Throughout the talk, I will highlight the unifying design principles and the interplay between consistency, robustness, and smoothness and conclude with open directions at the intersection of learning and online optimisation.

References

[1]: Antoniadis A, Gouleakis T, Kleer P, Kolev P. Secretary and online matching problems with machine learned advice. Discrete Optimization. 2023 May; 48(part 2):100778.

[2]:Choo D, Gouleakis T, Ling CK, Bhattacharyya A. Online bipartite matching with imperfect advice. In Proceedings of the 41st International Conference on Machine Learning 2024 

[3]: Fotakis D, Gergatsouli E, Gouleakis T, Patris N, Tolias T. Improved Bounds for Online Facility Location with Predictions. In Proceedings of the AAAI Conference on Artificial Intelligence 2025 

Themis Gouleakis is an Assistant Professor in the College of Computing and Data Science at Nanyang Technological University. Previously, he has worked as a postdoctoral researcher at the University of Southern California, as a postdoctoral fellow at the Algorithms & complexity department of Max-Planck-Institute for informatics and as a senior research fellow at National University of Singapore. He completed his PhD at MIT affiliated with the Theory of Computation group in CSAIL and advised by Ronitt Rubinfeld. He is the recipient of the Outstanding Paper Award at the 33rd Annual Conference on Neural Information Processing Systems (NeurIPS 2019).

For more information about the ESD Seminar, please email esd_invite@sutd.edu.sg