Workshop on Learningaugmented Algorithms: Theory and Applications – June 19, 2023 – SIGMETRICS 2023
This workshop will cover recent results, as well as new emerging directions in the rapidlyadvancing field of learningaugmented 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 worstcase guarantees of classic algorithms, while still obtaining nearoptimal 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 worstcase 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 worstcase 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