Competitive Caching with Machine Learned Advice
Open Access
- 14 July 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (4), 1-25
- https://doi.org/10.1145/3447579
Abstract
Traditional online algorithms encapsulate decision making under uncertainty, and give ways to hedge against all possible future events, while guaranteeing a nearly optimal solution, as compared to an offline optimum. On the other hand, machine learning algorithms are in the business of extrapolating patterns found in the data to predict the future, and usually come with strong guarantees on the expected generalization error. In this work, we develop a framework for augmenting online algorithms with a machine learned predictor to achieve competitive ratios that provably improve upon unconditional worst-case lower bounds when the predictor has low error. Our approach treats the predictor 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 predictions and prove that this combined approach achieves a competitive ratio that both (i) decreases as the predictor’s error decreases and (ii) is always capped by O(log k), which can be achieved without any assistance from the predictor. We complement our results with an empirical evaluation of our algorithm on real-world datasets and show that it performs well empirically even when using simple off-the-shelf predictions.Keywords
Funding Information
- NSF (CCF-1563714)
- Google Ph.D. Fellowship
This publication has 22 references indexed in Scilit:
- Online Allocation with Traffic SpikesPublished by Association for Computing Machinery (ACM) ,2015
- The dynamics of repeat consumptionPublished by Association for Computing Machinery (ACM) ,2014
- Online Optimization with Uncertain InformationACM Transactions on Algorithms, 2012
- Smoothed Analysis of the k-Means MethodJournal of the ACM, 2011
- Friendship and mobilityPublished by Association for Computing Machinery (ACM) ,2011
- Self-Improving AlgorithmsSIAM Journal on Computing, 2011
- Smoothed analysis of algorithmsJournal of the ACM, 2004
- Competitive k-server algorithmsJournal of Computer and System Sciences, 1994
- Competitive paging algorithmsJournal of Algorithms, 1991
- The working set model for program behaviorCommunications of the ACM, 1968