Online Caching with Optimistic Learning

Naram Mhaisen, George Iosifidis, Douglas J. Leith

TL;DR

This paper introduces a framework that treats content recommendations (like those from Netflix or YouTube) as "hints" for future data requests. By integrating these predictions into online learning algorithms, the authors achieve superior caching performance—sometimes even outperforming the best possible static strategy—while remaining robust enough to handle "garbage" predictions without failing.

What Problem Does This Paper Address?

Caching is a 50-year-old problem: deciding which files to store in limited, fast-access memory to minimize latency and bandwidth. Traditional policies like LRU (Least Recently Used) struggle when user preferences change rapidly (non-stationarity).

Modern research has turned to Online Convex Optimization (OCO) to create "no-regret" caching policies that adapt to any request pattern. However, these are purely reactive—they only look at past requests. The authors identify a missed opportunity: in modern systems, recommendation engines (rec-sys) actually influence what users watch next. This paper asks: Can we use these recommendations as "optimistic" predictions to look into the future of the caching queue?

The challenge is that recommendations are often noisy, biased, or ignored by users. A caching policy that blindly follows bad advice could perform worse than a simple reactive one.

Methods

The authors build upon the Follow-the-Regularized-Leader (FTRL) framework and introduce three novel algorithmic contributions:

  1. Optimistic FTRL (OBC): Designed for bipartite networks (where users can access multiple caches). It adds a "prediction" term to the standard FTRL update. If the prediction is perfect, the algorithm achieves "sub-zero" regret; if it's terrible, it still maintains the best-known theoretical performance bound ($O(\sqrt{T})$).
  2. Optimistic Elastic Caching (OEC): This addresses "elastic" caches, such as leased cloud storage where the cache size can change over time based on a budget. It uses a saddle-point analysis to balance caching gains against long-term leasing costs.
  3. Experts Caching (XC): A meta-learning approach. It runs two "experts" in parallel—one Optimistic (trusts recommendations) and one Pessimistic (robust/reactive). A meta-learner uses Online Gradient Ascent to decide how much to trust each expert based on their recent performance.

Datasets

The algorithms were evaluated using two main sources:

  • Synthetic Data: Requests generated using a stationary Zipf distribution (a standard model for file popularity) with varying skewness parameters ($\zeta$).
  • Real-World Traces: Trace-driven numerical tests using a publicly available dataset of YouTube request traces collected from a campus network.
  • Prediction Modes: To test robustness, the authors simulated different recommendation qualities, including "adversarial" modes where the system intentionally provides wrong predictions.

Key Insights and Ideas

  • Recommendations as Predictions: The "aha moment" is realizing that a recommendation system isn't just a feature for the user; it's a sensor for the cache. Because recommendations bias user behavior, they serve as a natural (if imperfect) forecast.
  • Negative Regret: In the world of online learning, "regret" measures how much worse you did than the best fixed strategy chosen with hindsight. This paper shows that with good predictions, you can achieve negative regret—meaning the online policy actually beats the best static strategy.
  • The Safety Net: The math ensures that "optimism" doesn't lead to "recklessness." The algorithms are designed so that even if the recommendation engine is completely wrong, the caching performance won't degrade beyond a constant factor of standard reactive policies.
  • Shadow Prices for Caching: In the elastic model, the dual variable $\lambda$ acts as a "shadow price," effectively telling the system how much a cache hit is worth relative to the current cost of leasing more storage.

Key Results

  • Superior Utility: In bipartite network simulations, the OBC policy maintained utility within 5.32% of the best hindsight solution.
  • Beating Benchmarks: Compared to the state-of-the-art Online Gradient Descent (OGD) policy, the proposed optimistic methods showed a 57.1% improvement in regret in certain scenarios.
  • Elastic Gains: In the elastic caching scenario, the OEC algorithm outperformed the benchmark by 42.5% because it could intelligently "violate" budget constraints temporarily to store high-value content that it predicted would be requested soon.
  • Robustness: The meta-learning (XC) approach successfully identified when a recommendation system was performing poorly and shifted its weight to the "pessimistic" expert to protect system performance.

Limitations and Future Work

  • Unit File Sizes: The current analysis assumes all files are the same size. While the authors note the math can be extended to variable sizes, the implementation and specific bounds might become more complex.
  • Rec-Sys Dependency: The performance boost is heavily dependent on the existence of a recommendation system. In environments without one (e.g., raw web traffic), the "optimistic" part of the algorithm has nothing to feed on.
  • Uncoded Caching: The authors suggest that applying these optimistic learning principles to uncoded caching (where files aren't split into mathematical "chunks") is a promising but currently unexplored direction.
  • Computational Overhead: While scalable, running multiple "experts" in the meta-learning framework (XC) increases the computational footprint per request compared to simple heuristics like LRU.

Summary updated

Abstract

The design of effective online caching policies is an increasingly important problem for content distribution networks, online social networks and edge computing services, among other areas. This paper proposes a new algorithmic toolbox for tackling this problem through the lens of optimistic online learning. We build upon the Follow-the-Regularized-Leader (FTRL) framework which is developed further here to include predictions for the file requests, and we design online caching algorithms for bipartite networks with fixed-size caches or elastic leased caches subject to time-average budget constraints. The predictions are provided by a content recommendation system that influences the users viewing activity, and hence can naturally reduce the caching network's uncertainty about future requests. We prove that the proposed optimistic learning caching policies can achieve sub-zero performance loss (regret) for perfect predictions, and maintain the best achievable regret bound O (√T) even for arbitrary-bad predictions. The performance of the proposed algorithms is evaluated with detailed trace-driven numerical tests.
BibTeX
@inproceedings{mhaisen2022online,
  author = {Naram Mhaisen and George Iosifidis and Douglas J. Leith},
  title = {{Online Caching with Optimistic Learning}},
  booktitle = {IFIP Networking},
  year = {2022},
  url = {https://openreview.net/forum?id=NulT8022SnE},
}

Loading related content...

Figure