Abstract: In this reading group, we first introduce a popular model of algorithms with predictions, as formulated by Lykouris and Vassilvitskii [1]. After briefly covering the results of this paper, we then discuss two other papers: one on ski rental with predictions [2], and one describing an LP-duality-based method for analyzing various algorithms-with-predictions settings [3]. Finally, we conclude with an open problems session in which participants collaborate in small groups to identify and clearly define specific new directions.

References:
[1] Lykouris, Thodoris, and Sergei Vassilvitskii. "Competitive caching with machine learned advice." Journal of the ACM (JACM) 68.4 (2021): 1-25.
[2] Gollapudi, Sreenivas, and Debmalya Panigrahi. "Online algorithms for rent-or-buy with expert advice." International Conference on Machine Learning. PMLR, 2019.
[3] Bamas, Étienne, Andreas Maggiori, and Ola Svensson. "The primal-dual method for learning augmented algorithms." Advances in Neural Information Processing Systems 33 (2020): 20083-20094.