DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.60

Better and Simpler Learning-Augmented Online Caching

Authors: Alexander Wei

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

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.

Cite as

Alexander Wei. Better and Simpler Learning-Augmented Online Caching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wei:LIPIcs.APPROX/RANDOM.2020.60,
  author =	{Wei, Alexander},
  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 =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.60},
  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}
}

Search Results

Documents authored by Wei, Alexander

Better and Simpler Learning-Augmented Online Caching

Abstract

Cite as

Thanks for your feedback!

Could not send message