mlsanityData to 7 Oct 2026

Parsimonious Learning-Augmented Caching

arXiv 2202.04262 ↗First posted 9 Feb 2022cs.DS cs.LGcited by 19

Not on the map. Why?

Abstract (arXiv)

Learning-augmented algorithms -- in which, traditional algorithms are augmented with machine-learned predictions -- have emerged as a framework to go beyond worst-case analysis. The overarching goal is to design algorithms that perform near-optimally when the predictions are accurate yet retain certain worst-case guarantees irrespective of the accuracy of the predictions. This framework has been successfully applied to online problems such as caching where the predictions can be used to alleviate uncertainties. In this paper we introduce and study the setting in which the learning-augmented algorithm can utilize the predictions parsimoniously. We consider the caching problem -- which has been extensively studied in the learning-augmented setting -- and show that one can achieve quantitatively similar results but only using a sublinear number of predictions.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). Builds on 13 of its 36 references that are in the map. First posted on arXiv 9 Feb 2022.

Builds on

13 of 36 references.

References · 13

  1. 2018Competitive caching with machine learned advicecited by 194
  2. 2017The Case for Learned Index Structurescited by 188
  3. 2020Algorithms with Predictionscited by 152
  4. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 78
  5. 2020Online metric algorithms with untrusted predictionscited by 74
  6. 2019Near-Optimal Bounds for Online Caching with Machine Learned Advicecited by 73
  7. 2020Better and Simpler Learning-Augmented Online Cachingcited by 38
  8. 2020Online Algorithms for Weighted Paging with Predictionscited by 29
  9. 2021Flow Time Scheduling with Uncertain Processing Timecited by 29
  10. 2020Learning-Augmented Weighted Pagingcited by 17
  11. 2021Logarithmic Regret from Sublinear Hintscited by 11
  12. 2017k-server via multiscale entropic regularizationcited by 6
1 more
  1. 2017Fusible HSTs and the randomized k-server conjecturecited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 6; 2024: 5; 2025: 2; 2026: 4.

19 papers.

Sort:

  1. 2023Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysiscited by 16
  2. 2023Mixing predictions for online metric algorithmscited by 12
  3. 2024Algorithms for Caching and MTS with reduced number of predictionscited by 12
  4. 2022Paging with Succinct Predictionscited by 10
  5. 2023Improved Frequency Estimation Algorithms with and without Predictionscited by 10
  6. 2023Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictionscited by 8
  7. 2024Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithmscited by 8
  8. 2024Non-clairvoyant Scheduling with Partial Predictionscited by 7
  9. 2024Learning-Augmented Priority Queuescited by 7
  10. 2022Online Learning and Bandits with Queried Hintscited by 6
  11. 2025Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistencycited by 3
  12. 2023On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rentalcited by 2
7 more
  1. 2025Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictorscited by 2
  2. 2023Out-of-Distribution-Aware Electric Vehicle Chargingcited by 1
  3. 2026Learning-augmented smooth integer programs with PAC-learnable oraclescited by 1
  4. 2026Parsimonious Learning-Augmented Online Metric Matchingcited by 1
  5. 2024Safe Exploitative Play with Untrusted Type Beliefscited by 0
  6. 2026Learning-Augmented Approximation for Unrelated-Machines Makespan Schedulingcited by 0
  7. 2026Compressing Value Predictions for Learning-Augmented Metrical Task Systemscited by 0