License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.60
URN: urn:nbn:de:0030-drops-126633
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12663/
Go to the corresponding LIPIcs Volume Portal

Wei, Alexander

Better and Simpler Learning-Augmented Online Caching

pdf-format:
LIPIcs-APPROX60.pdf (0.5 MB)

Abstract

Lykouris and Vassilvitskii (ICML 2018) introduce a model of online caching with machine-learned advice that marries the predictive power of machine learning with the robustness guarantees of competitive analysis. In this model, each page request is augmented with a prediction for when that page will next be requested. The goal is to design algorithms that (1) perform well when the predictions are accurate and (2) are robust in the sense of worst-case competitive analysis.
We continue the study of algorithms for online caching with machine-learned advice, following the work of Lykouris and Vassilvitskii as well as Rohatgi (SODA 2020). Our main contribution is a substantially simpler algorithm that outperforms all existing approaches. This algorithm is a black-box combination of an algorithm that just naïvely follows the predictions with an optimal competitive algorithm for online caching. We further show that combining the naïve algorithm with LRU in a black-box manner is optimal among deterministic algorithms for this problem.

BibTeX - Entry

@InProceedings{wei:LIPIcs:2020:12663,
  author =	{Alexander Wei},
  title =	{{Better and Simpler Learning-Augmented Online Caching}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{60:1--60:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Jaros{\l}aw Byrka and Raghu Meka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12663},
  URN =		{urn:nbn:de:0030-drops-126633},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.60},
  annote =	{Keywords: Online caching, learning-augmented algorithms, beyond worst-case analysis}
}

Keywords: Online caching, learning-augmented algorithms, beyond worst-case analysis
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Issue Date: 2020
Date of publication: 11.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI