TY - GEN
T1 - Paging with Succinct Predictions
AU - Antoniadis, Antonios
AU - Boyar, Joan
AU - Eliáš, Marek
AU - Favrholdt, Lene M.
AU - Hoeksma, Ruben
AU - Larsen, Kim S.
AU - Polak, Adam
AU - Simon, Bertrand
N1 - Funding Information:
Boyar, Favrholdt, and Larsen were supported in part by the Independent Research Fund Denmark, Natural Sciences, grant DFF-0135-00018B and in part by the Innovation Fund Denmark, grant 9142-00001B, Digital Research Centre Denmark, project P40: Online Algorithms with Predictions. Po-lak was supported in part by Swiss National Science Foundation projects Lattice Algorithms and Integer Programming (185030) and Complexity of integer Programming (CRFS-2 207365). Part of the research was carried out during the Workshop on Algorithms with Predictions in the Bernoulli Center for Fundamental Studies at EPFL.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
U2 - 10.5555/3618408.3618447
DO - 10.5555/3618408.3618447
M3 - Article in proceedings
AN - SCOPUS:85174170202
VL - 202
T3 - Proceedings of Machine Learning Research
SP - 952
EP - 968
BT - Proceedings of the 40th International Conference on Machine Learning
PB - ML Research Press
T2 - 40th International Conference on Machine Learning, ICML 2023
Y2 - 23 July 2023 through 29 July 2023
ER -