Paging with Succinct Predictions

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

doi:10.5555/3618408.3618447

Paging with Succinct Predictions

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

^*Kontaktforfatter

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer 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.

Originalsprog	Engelsk
Titel	Proceedings of the 40th International Conference on Machine Learning
Antal sider	17
Vol/bind	202
Forlag	ML Research Press
Publikationsdato	2023
Sider	952-968
DOI	https://doi.org/10.5555/3618408.3618447
Status	Udgivet - 2023
Begivenhed	40th International Conference on Machine Learning, ICML 2023 - Honolulu, USA Varighed: 23. jul. 2023 → 29. jul. 2023

Konference

Konference	40th International Conference on Machine Learning, ICML 2023
Land/Område	USA
By	Honolulu
Periode	23/07/2023 → 29/07/2023

Navn	Proceedings of Machine Learning Research
ISSN	2640-3498

Bibliografisk note

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.

Dokumenter og links

10.5555/3618408.3618447

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

Citationsformater

@inproceedings{2751be3bbed84c4880d3fb71e5e89c70,

title = "Paging with Succinct Predictions",

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.",

author = "Antonios Antoniadis and Joan Boyar and Marek Eli{\'a}{\v s} and Favrholdt, {Lene M.} and Ruben Hoeksma and Larsen, {Kim S.} and Adam Polak and Bertrand Simon",

note = "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.; 40th International Conference on Machine Learning, ICML 2023 ; Conference date: 23-07-2023 Through 29-07-2023",

year = "2023",

doi = "10.5555/3618408.3618447",

language = "English",

volume = "202",

series = "Proceedings of Machine Learning Research",

pages = "952--968",

booktitle = "Proceedings of the 40th International Conference on Machine Learning",

publisher = "ML Research Press",

}

Antoniadis, A, Boyar, J, Eliáš, M, Favrholdt, LM, Hoeksma, R, Larsen, KS, Polak, A & Simon, B 2023, Paging with Succinct Predictions. i Proceedings of the 40th International Conference on Machine Learning. bind 202, ML Research Press, Proceedings of Machine Learning Research, s. 952-968, 40th International Conference on Machine Learning, ICML 2023, Honolulu, USA, 23/07/2023. https://doi.org/10.5555/3618408.3618447

Paging with Succinct Predictions. / Antoniadis, Antonios; Boyar, Joan; Eliáš, Marek et al.
Proceedings of the 40th International Conference on Machine Learning. Bind 202 ML Research Press, 2023. s. 952-968 (Proceedings of Machine Learning Research).

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

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 -

Paging with Succinct Predictions

Abstract

Konference

Bibliografisk note

Dokumenter og links

SDU link

Fingeraftryk

Citationsformater