@online{Antoniadis2210.02775,
TITLE = {Paging with Succinct Predictions},
AUTHOR = {Antoniadis, Antonios and Boyar, Joan and Eli{\'a}{\v s}, Marek and Favrholdt, Lene M. and Hoeksma, Ruben and Larsen, Kim S. and Polak, Adam and Simon, Bertrand},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2210.02775},
EPRINT = {2210.02775},
EPRINTTYPE = {arXiv},
YEAR = {2022},
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
-- a recent line of research that aims to ameliorate the shortcomings of
classical worst-case analysis by giving algorithms access to predictions. Such
predictions can typically be generated using a machine learning approach, but
they are inherently imperfect. 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 consider two natural such setups: (i) discard predictions, in which the
predicted bit denotes whether or not it is ``safe'' to evict this page, and
(ii) phase predictions, where the bit denotes whether the current page will be
requested in the next phase (for an appropriate partitioning of the input into
phases). We develop algorithms for each of the two setups that 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.
},
}