Better and Simpler Learning-Augmented Online Caching

Alexander Wei

Introduction

Online caching, or the paging problem, is a fundamental challenge in computer science. Given a cache of size $k$ and a sequence of page requests, an algorithm must decide which page to evict when a miss occurs to minimize the total number of misses. Traditionally, this problem has been analyzed through the lens of competitive analysis, comparing an online algorithm's performance against an offline optimal adversary ($OPT$). While classical algorithms like Least Recently Used (LRU) provide robust worst-case guarantees, they often fail to exploit patterns present in real-world data.

Recently, the field of "learning-augmented algorithms" has emerged to bridge this gap. These algorithms leverage potentially noisy predictions (e.g., the next arrival time of a page) to improve performance. The goal is to achieve consistency (near-optimal performance with accurate predictions) and robustness (performance no worse than classical algorithms when predictions are poor). Previous work in this area often involved complex, integrated modifications to randomized marking algorithms. This paper proposes a significantly simpler and more effective "black-box" approach.

The BlindOracle and Black-Box Combination

The core of the proposed method lies in its simplicity. Rather than redesigning the caching logic from scratch, the author introduces two distinct components:

  1. BlindOracle: This is a naive algorithm that treats every machine-learned prediction as absolute truth. It follows the "Furthest-In-Future" (FIF) policy based strictly on the provided predictions, evicting the page predicted to be requested furthest in the future.
  2. Black-Box Combiners: These are meta-algorithms designed to combine the outputs of multiple online algorithms. By running BlindOracle alongside a robust classical algorithm (like LRU), the combiner ensures the final performance is competitive with the better of the two in any given scenario.

Theoretical Analysis and the $1/k$ Factor

The paper’s primary technical contribution is a rigorous analysis of BlindOracle using a potential function. This mathematical framework tracks the "distance" between the state of the algorithm's cache and the optimal cache. The author proves that the number of cache misses incurred by BlindOracle is gracefully bounded by the total prediction error $\eta$.

A significant finding is that the impact of the prediction error on the competitive ratio scales with $1/k$, where $k$ is the cache size. Specifically, the error term is $\frac{1}{k} \frac{\eta}{OPT}$. This indicates that as the cache size increases, the algorithm becomes naturally more tolerant of prediction inaccuracies. This $1/k$ dependence is a marked improvement over previous state-of-the-art results (e.g., Rohatgi, 2020), which featured a less efficient $\frac{\log k}{k}$ scaling.

Key Results and Optimality

The paper establishes new upper bounds for the competitive ratio in both randomized and deterministic settings:

  • Randomized Algorithms: The approach achieves a ratio of $O(1 + \min(\frac{1}{k} \frac{\eta}{OPT}, \log k))$. This improves upon the previous best known bounds.
  • Deterministic Algorithms: The approach achieves a ratio of $O(1 + \min(\frac{1}{k} \frac{\eta}{OPT}, k))$.

Furthermore, the author provides a matching lower bound for deterministic algorithms. This proof shows that no deterministic algorithm can achieve a better dependence on the error $\eta$ than $1/k$. By matching the upper and lower bounds, the paper effectively "closes" the problem for the deterministic case, proving that the combination of BlindOracle and LRU is optimal.

Conclusion

This work demonstrates that simplicity can outperform complexity in learning-augmented algorithm design. By treating the predictive component as a black box, the author achieves better theoretical guarantees and a more modular architecture. While the deterministic case is now fully characterized, future research may focus on closing the small logarithmic gap remaining in the randomized lower bounds and exploring alternative prediction models beyond "next arrival times."

Summary updated

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
@inproceedings{wei2020better,
  author = {Alexander Wei},
  title = {{Better and Simpler Learning-Augmented Online Caching}},
  booktitle = {APPROX-RANDOM},
  year = {2020},
  url = {https://openreview.net/forum?id=wvRBlwJhPZ_},
}
Figure