Paging with Succinct Predictions

Antonios Antoniadis, Joan Boyar, Marek Elias, Lene Monrad Favrholdt, Ruben Hoeksma, Kim S. Larsen, Adam Polak, Bertrand Simon
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:952-968, 2023.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-antoniadis23a, title = {Paging with Succinct Predictions}, author = {Antoniadis, Antonios and Boyar, Joan and Elias, Marek and Favrholdt, Lene Monrad and Hoeksma, Ruben and Larsen, Kim S. and Polak, Adam and Simon, Bertrand}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {952--968}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/antoniadis23a/antoniadis23a.pdf}, url = {https://proceedings.mlr.press/v202/antoniadis23a.html}, 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.} }
Endnote
%0 Conference Paper %T Paging with Succinct Predictions %A Antonios Antoniadis %A Joan Boyar %A Marek Elias %A Lene Monrad Favrholdt %A Ruben Hoeksma %A Kim S. Larsen %A Adam Polak %A Bertrand Simon %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-antoniadis23a %I PMLR %P 952--968 %U https://proceedings.mlr.press/v202/antoniadis23a.html %V 202 %X 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.
APA
Antoniadis, A., Boyar, J., Elias, M., Favrholdt, L.M., Hoeksma, R., Larsen, K.S., Polak, A. & Simon, B.. (2023). Paging with Succinct Predictions. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:952-968 Available from https://proceedings.mlr.press/v202/antoniadis23a.html.

Related Material