Robust Learning-Augmented Caching: An Experimental Study

Jakub Chłędowski, Adam Polak, Bartosz Szabucki, Konrad Tomasz Żołna
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:1920-1930, 2021.

Abstract

Effective caching is crucial for performance of modern-day computing systems. A key optimization problem arising in caching – which item to evict to make room for a new item – cannot be optimally solved without knowing the future. There are many classical approximation algorithms for this problem, but more recently researchers started to successfully apply machine learning to decide what to evict by discovering implicit input patterns and predicting the future. While machine learning typically does not provide any worst-case guarantees, the new field of learning-augmented algorithms proposes solutions which leverage classical online caching algorithms to make the machine-learned predictors robust. We are the first to comprehensively evaluate these learning-augmented algorithms on real-world caching datasets and state-of-the-art machine-learned predictors. We show that a straightforward method – blindly following either a predictor or a classical robust algorithm, and switching whenever one becomes worse than the other – has only a low overhead over a well-performing predictor, while competing with classical methods when the coupled predictor fails, thus providing a cheap worst-case insurance.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-chledowski21a, title = {Robust Learning-Augmented Caching: An Experimental Study}, author = {Ch{\l}{\k{e}}dowski, Jakub and Polak, Adam and Szabucki, Bartosz and {\.Z}o{\l}na, Konrad Tomasz}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {1920--1930}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/chledowski21a/chledowski21a.pdf}, url = {https://proceedings.mlr.press/v139/chledowski21a.html}, abstract = {Effective caching is crucial for performance of modern-day computing systems. A key optimization problem arising in caching – which item to evict to make room for a new item – cannot be optimally solved without knowing the future. There are many classical approximation algorithms for this problem, but more recently researchers started to successfully apply machine learning to decide what to evict by discovering implicit input patterns and predicting the future. While machine learning typically does not provide any worst-case guarantees, the new field of learning-augmented algorithms proposes solutions which leverage classical online caching algorithms to make the machine-learned predictors robust. We are the first to comprehensively evaluate these learning-augmented algorithms on real-world caching datasets and state-of-the-art machine-learned predictors. We show that a straightforward method – blindly following either a predictor or a classical robust algorithm, and switching whenever one becomes worse than the other – has only a low overhead over a well-performing predictor, while competing with classical methods when the coupled predictor fails, thus providing a cheap worst-case insurance.} }
Endnote
%0 Conference Paper %T Robust Learning-Augmented Caching: An Experimental Study %A Jakub Chłędowski %A Adam Polak %A Bartosz Szabucki %A Konrad Tomasz Żołna %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-chledowski21a %I PMLR %P 1920--1930 %U https://proceedings.mlr.press/v139/chledowski21a.html %V 139 %X Effective caching is crucial for performance of modern-day computing systems. A key optimization problem arising in caching – which item to evict to make room for a new item – cannot be optimally solved without knowing the future. There are many classical approximation algorithms for this problem, but more recently researchers started to successfully apply machine learning to decide what to evict by discovering implicit input patterns and predicting the future. While machine learning typically does not provide any worst-case guarantees, the new field of learning-augmented algorithms proposes solutions which leverage classical online caching algorithms to make the machine-learned predictors robust. We are the first to comprehensively evaluate these learning-augmented algorithms on real-world caching datasets and state-of-the-art machine-learned predictors. We show that a straightforward method – blindly following either a predictor or a classical robust algorithm, and switching whenever one becomes worse than the other – has only a low overhead over a well-performing predictor, while competing with classical methods when the coupled predictor fails, thus providing a cheap worst-case insurance.
APA
Chłędowski, J., Polak, A., Szabucki, B. & Żołna, K.T.. (2021). Robust Learning-Augmented Caching: An Experimental Study. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:1920-1930 Available from https://proceedings.mlr.press/v139/chledowski21a.html.

Related Material