Competitive Caching with Machine Learned Advice

Thodoris Lykouris, Sergei Vassilvtiskii
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:3296-3305, 2018.

Abstract

We develop a framework for augmenting online algorithms with a machine learned oracle to achieve competitive ratios that provably improve upon unconditional worst case lower bounds when the oracle has low error. Our approach treats the oracle as a complete black box, and is not dependent on its inner workings, or the exact distribution of its errors. We apply this framework to the traditional caching problem {—} creating an eviction strategy for a cache of size k. We demonstrate that naively following the oracle’s recommendations may lead to very poor performance, even when the average error is quite low. Instead we show how to modify the Marker algorithm to take into account the oracle’s predictions, and prove that this combined approach achieves a competitive ratio that both (i) decreases as the oracle’s error decreases, and (ii) is always capped by O(log k), which can be achieved without any oracle input. We complement our results with an empirical evaluation of our algorithm on real world datasets, and show that it performs well empirically even using simple off the shelf predictions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-lykouris18a, title = {Competitive Caching with Machine Learned Advice}, author = {Lykouris, Thodoris and Vassilvtiskii, Sergei}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {3296--3305}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/lykouris18a/lykouris18a.pdf}, url = {https://proceedings.mlr.press/v80/lykouris18a.html}, abstract = {We develop a framework for augmenting online algorithms with a machine learned oracle to achieve competitive ratios that provably improve upon unconditional worst case lower bounds when the oracle has low error. Our approach treats the oracle as a complete black box, and is not dependent on its inner workings, or the exact distribution of its errors. We apply this framework to the traditional caching problem {—} creating an eviction strategy for a cache of size k. We demonstrate that naively following the oracle’s recommendations may lead to very poor performance, even when the average error is quite low. Instead we show how to modify the Marker algorithm to take into account the oracle’s predictions, and prove that this combined approach achieves a competitive ratio that both (i) decreases as the oracle’s error decreases, and (ii) is always capped by O(log k), which can be achieved without any oracle input. We complement our results with an empirical evaluation of our algorithm on real world datasets, and show that it performs well empirically even using simple off the shelf predictions.} }
Endnote
%0 Conference Paper %T Competitive Caching with Machine Learned Advice %A Thodoris Lykouris %A Sergei Vassilvtiskii %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-lykouris18a %I PMLR %P 3296--3305 %U https://proceedings.mlr.press/v80/lykouris18a.html %V 80 %X We develop a framework for augmenting online algorithms with a machine learned oracle to achieve competitive ratios that provably improve upon unconditional worst case lower bounds when the oracle has low error. Our approach treats the oracle as a complete black box, and is not dependent on its inner workings, or the exact distribution of its errors. We apply this framework to the traditional caching problem {—} creating an eviction strategy for a cache of size k. We demonstrate that naively following the oracle’s recommendations may lead to very poor performance, even when the average error is quite low. Instead we show how to modify the Marker algorithm to take into account the oracle’s predictions, and prove that this combined approach achieves a competitive ratio that both (i) decreases as the oracle’s error decreases, and (ii) is always capped by O(log k), which can be achieved without any oracle input. We complement our results with an empirical evaluation of our algorithm on real world datasets, and show that it performs well empirically even using simple off the shelf predictions.
APA
Lykouris, T. & Vassilvtiskii, S.. (2018). Competitive Caching with Machine Learned Advice. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:3296-3305 Available from https://proceedings.mlr.press/v80/lykouris18a.html.

Related Material