# Near-Optimal Bounds for Online Caching with Machine Learned Advice

arXiv: https://arxiv.org/abs/1910.12172 · HTML: https://mlsanity.com/paper/1910.12172/

## Key facts

- Cited by 73 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2019.

## Built on by (most cited first, 30 of 73)

- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Learning to Warm-Start Fixed-Point Optimization Algorithms](https://mlsanity.com/paper/2309.07835/) (2023)
- [Learning Predictions for Algorithms with Predictions](https://mlsanity.com/paper/2202.09312/) (2022)
- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Customizing ML Predictions for Online Algorithms](https://mlsanity.com/paper/2205.08715/) (2022)
- [Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds](https://mlsanity.com/paper/2110.13116/) (2021)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Parsimonious Learning-Augmented Caching](https://mlsanity.com/paper/2202.04262/) (2022)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [A Novel Prediction Setup for Online Speed-Scaling](https://mlsanity.com/paper/2112.03082/) (2021)
- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis](https://mlsanity.com/paper/2302.06832/) (2023)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Can Q-Learning be Improved with Advice?](https://mlsanity.com/paper/2110.13052/) (2021)
- [Mixing predictions for online metric algorithms](https://mlsanity.com/paper/2304.01781/) (2023)
- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [Robust Learning-Augmented Caching: An Experimental Study](https://mlsanity.com/paper/2106.14693/) (2021)
- [Logarithmic Regret from Sublinear Hints](https://mlsanity.com/paper/2111.05257/) (2021)
- [A Regression Approach to Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2205.08717/) (2022)
- [Algorithms for Caching and MTS with reduced number of predictions](https://mlsanity.com/paper/2404.06280/) (2024)
- [Online Bin Packing with Predictions](https://mlsanity.com/paper/2102.03311/) (2021)
- [(Optimal) Online Bipartite Matching with Degree Information](https://mlsanity.com/paper/2110.11439/) (2021)
- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [Double Coverage with Machine-Learned Advice](https://mlsanity.com/paper/2103.01640/) (2021)
- [Robustification of Online Graph Exploration Methods](https://mlsanity.com/paper/2112.05422/) (2021)
- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (2022)
- [Paging with Succinct Predictions](https://mlsanity.com/paper/2210.02775/) (2022)
- [Improved Learning-augmented Algorithms for k-means and k-medians Clustering](https://mlsanity.com/paper/2210.17028/) (2022)
- [Active causal structure learning with advice](https://mlsanity.com/paper/2305.19588/) (2023)
- [Single-Leg Revenue Management with Advice](https://mlsanity.com/paper/2202.10939/) (2022)

## Abstract (arXiv)

In the model of online caching with machine learned advice, introduced by Lykouris and Vassilvitskii, the goal is to solve the caching problem with an online algorithm that has access to next-arrival predictions: when each input element arrives, the algorithm is given a prediction of the next time when the element will reappear. The traditional model for online caching suffers from an Omega(log k) competitive ratio lower bound (on a cache of size k). In contrast, the augmented model admits algorithms which beat this lower bound when the predictions have low error, and asymptotically match the lower bound when the predictions have high error, even if the algorithms are oblivious to the prediction error. In particular, Lykouris and Vassilvitskii showed that there is a prediction-augmented caching algorithm with a competitive ratio of O(1+min(√η/OPT, log k)) when the overall ℓ1 prediction error is bounded by η, and OPT is the cost of the optimal offline algorithm. The dependence on k in the competitive ratio is optimal, but the dependence on η/OPT may be far from optimal. In this work, we make progress towards closing this gap. Our contributions are twofold. First, we provide an improved algorithm with a competitive ratio of O(1 + min((η/OPT)/k, 1) log k). Second, we provide a lower bound of Omega(log min((η/OPT)/(k log k), k)).