Competitive caching with machine learned advice

By Thodoris Lykouris, Sergei Vassilvitskii. International Conference on Machine Learning, 2018

517 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/6c4e068c2e4b8f5cdc18bcf61cd7f66f6d22f8a7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Secretaries with Advice (2020, background): “Examples range from building better data structures [22, 28], to improved competitive and approximation ratios for several online tasks [23, 24, 26, 29, 30, 31], to cases where advice has been used to speed-up algorithms [1, 5] or to reduce their space complexity [19].”
Secretary and Online Matching Problems with Machine Learned Advice (2020, methodology): “We note that most of the following results are analyzed by means of consistency (competitiveratio in the case of perfect predictions) and robustness (worst-case competitive-ratio regardless of prediction quality), but the precise formal definitions of consistency and robustness slightly differ in ea”
Algorithms with predictions (2020, methodology): “A formal model of learning with predictions, including the notions of α -consistency and β -robustness, was presented by Lykouris and Vassilvitskii (2018).”
Improving Online Algorithms via ML Predictions (2024, background): “Recently, there has been some interest in using machine-learned predictions to improve the quality of online algorithms [21, 19].”