Workshop on Learning-augmented Algorithms: Theory and Applications – June 19, 2023 – SIGMETRICS 2023

This workshop will cover recent results, as well as new emerging directions in the rapidly-advancing field of learning-augmented algorithms, also known as algorithms with predictions or algorithms with ML advice. This nascent area, at the intersection of TCS and ML, studies the interplay between ML and the design/analysis of algorithms with strict, provable performance guarantees. Its aim is to provide insight into fundamental questions related to modeling, performance evaluation, and analysis techniques, such as:

• How can imperfect predictions be used robustly, i.e., how do we retain the worst-case guarantees of classic algorithms, while still obtaining near-optimal performance when the predictions are accurate?

• How can algorithms adapt their behavior to the properties of the input distribution so as to achieve improved performance on specific classes of practical workloads while still ensuring worst-case adversarial guarantees?

• If predictions come at a cost, how can an algorithm determine the right time to most effectively make use of them?

• What tools from decision theory, e.g., Pareto efficiency, should we use in order to better evaluate the performance of the algorithm?

• How to train (possibly multiple) predictors to best suit the needs of online algorithms and improve the average performance while ensuring worst-case robustness?

This area has blossomed in recent years, both in terms of foundational theoretical results but also in terms of exciting applications across a broad range of settings, such as streaming algorithms, online scheduling, clustering, filtering, online matching, caching, system control, cloud computing, and many others. Some recent workshops/seminars on this topic include the Workshop on Algorithms with Predictions at EPFL in 2022, the Workshop on Algorithms with Predictions, at STOC 2022 and STOC 2020, and Machine Learning for Algorithms at FODSI, 2021.

Organizers:

• Spyros Angelopoulos, CNRS and Sorbonne University, spyros.angelopoulos@lip6.fr

• Mohammad Hajiesmaili, UMass Amherst, hajiesmaili@cs.umass.edu

• Shahin Kamali, York University, kamalis@yorku.ca

• Shaolei Ren, UC Riverside, sren@ece.ucr.edu

• Adam Wierman, Caltech, adamw@caltech.edu