Paging with Succinct Predictions

Antonios Antoniadis*, Joan Boyar*, Marek Eliáš*, Lene M. Favrholdt*, Ruben Hoeksma*, Kim S. Larsen*, Adam Polak*, Bertrand Simon*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

2 Downloads (Pure)

Abstract

Paging is a prototypical problem in the area of online algorithms. It has also played a central role in the development of learning-augmented algorithms. Previous work on learning-augmented paging has investigated predictions on (i) when the current page will be requested again (reoccurrence predictions), (ii) the current state of the cache in an optimal algorithm (state predictions), (iii) all requests until the current page gets requested again, and (iv) the relative order in which pages are requested. We study learning-augmented paging from the new perspective of requiring the least possible amount of predicted information. More specifically, the predictions obtained alongside each page request are limited to one bit only. We develop algorithms satisfy all three desirable properties of learning-augmented algorithms - that is, they are consistent, robust and smooth - despite being limited to a one-bit prediction per request. We also present lower bounds establishing that our algorithms are essentially best possible.

Original languageEnglish
Title of host publicationProceedings of the 40th International Conference on Machine Learning
Number of pages17
Volume202
PublisherML Research Press
Publication date2023
Pages952-968
DOIs
Publication statusPublished - 2023
Event40th International Conference on Machine Learning, ICML 2023 - Honolulu, United States
Duration: 23. Jul 202329. Jul 2023

Conference

Conference40th International Conference on Machine Learning, ICML 2023
Country/TerritoryUnited States
CityHonolulu
Period23/07/202329/07/2023
SeriesProceedings of Machine Learning Research
ISSN2640-3498

Cite this