No- Regret Caching with Noisy Request Estimates

Younes Ben Mazziane, Francescomaria Faticanti, Giovanni Neglia, Sara Alouf

TL;DR

This paper introduces Noisy-Follow-the-Perturbed-Leader (NFPL), a caching algorithm designed for real-world systems where tracking every single file request is impossible due to high traffic or memory limits. The authors prove that even when working with noisy, sampled data, NFPL achieves "sublinear regret"—meaning its performance eventually catches up to the best possible static caching strategy.

What Problem Does This Paper Address?

In the world of online learning for caching, "regret" is the gold standard for performance. It measures the difference between the number of cache misses an algorithm incurs and the misses incurred by the best possible static cache configuration chosen with 20/20 hindsight. A "no-regret" algorithm is one where this gap grows slower than time ($o(T)$), meaning the algorithm's average performance converges to the optimum.

However, most existing no-regret algorithms (like Online Gradient Descent or the classic Follow-the-Perturbed-Leader) assume the system has perfect knowledge of every request. In high-throughput environments or memory-constrained edge devices, this is a fantasy. Engineers often use sampling or approximate counters (like Bloom filters or sketches) to keep up, which introduces noise. This paper asks: Can we still guarantee no-regret performance when our request data is "noisy"?

Methods

The authors build upon the Follow-the-Perturbed-Leader (FPL) algorithm. In standard FPL, the cache looks at the total history of requests, adds a bit of random noise (perturbation) to the counts, and then picks the top $C$ files to store. The noise prevents the algorithm from being "tricked" by adversarial request patterns.

The authors extend this to NFPL (Noisy-FPL). Instead of using the true request vector $r_t$, the algorithm uses an estimate $\hat{r}_t$. They propose two practical implementations:

  1. NFPL-Fix: Samples a fixed number of requests ($b$) from each batch.
  2. NFPL-Var: Samples each request with a fixed probability ($f$).

The core of the paper is a mathematical proof showing that as long as the estimator is unbiased (meaning it's correct on average), NFPL maintains sublinear regret.

Datasets

The researchers evaluated their algorithms using three distinct types of request traces:

  • Zipf Trace: A synthetic trace where file popularity follows a power-law distribution. This is the standard "stationary" model for web traffic.
  • Akamai Trace: A real-world dataset from the Akamai CDN, capturing several days of file requests. This includes temporal correlations and popularity shifts.
  • Round-robin Trace: An adversarial trace where files are requested in a repeating sequence ($1, 2, 3... N$). This is a "nightmare scenario" for traditional heuristics like LRU (Least Recently Used), which would miss every single request.

Key Insights and Ideas

  • Noise can be a Blessing: In the adversarial round-robin scenario, NFPL actually outperformed the standard FPL. Why? Because the sampling noise acted as an additional layer of randomization, preventing the cache from over-fitting to the immediate past and allowing it to "stumble" upon a better set of files to hold.
  • Catalog Independence: One of the most significant theoretical contributions is a new regret bound for FPL that is independent of the catalog size ($N$). Previous bounds suggested that as the number of possible files grew, the regret would explode. This paper proves that for caching, the size of the library doesn't actually hurt the theoretical performance guarantee.
  • Robustness to Sampling: The experiments showed that the specific method of sampling (fixed vs. variable) matters very little. What matters is the sampling rate. While lower sampling rates slow down how fast the algorithm learns, the "no-regret" property remains intact.

Key Results

  • Theoretical Guarantee: The authors proved that NFPL's regret is bounded by $O(\sqrt{T})$. Specifically, for NFPL-Fix, the regret is $\leq 2\sqrt{2} \cdot B\sqrt{C \cdot T}$, where $B$ is the batch size and $C$ is the cache capacity.
  • Convergence: In Zipf and Akamai traces, NFPL successfully converged toward the optimal static allocation (OPT). While it was slower than FPL with perfect knowledge, it significantly outperformed standard heuristics like LRU in many cases.
  • Adversarial Resilience: In the round-robin test, while LRU and LFU (Least Frequently Used) failed miserably (near 100% miss rate), NFPL maintained a miss ratio close to the theoretical optimum.

Limitations and Future Work

The current study focuses primarily on sampling as the source of noise. While sampling is common, many systems use approximate counting data structures like Count-Min Sketches to track requests. The authors acknowledge that extending the NFPL analysis to these specific data structures is a vital next step.

Additionally, the algorithm requires tuning a "learning rate" ($\eta$) based on the expected noise. In a highly dynamic environment where noise levels change (e.g., fluctuating traffic loads), an adaptive version of NFPL that tunes itself on the fly would be a significant practical improvement.

Summary updated

Abstract

Online learning algorithms have been successfully used to design caching policies with regret guarantees. Existing algorithms assume that the cache knows the exact request sequence, but this may not be feasible in high load and/or memory-constrained scenarios, where the cache may have access only to sampled requests or to approximate requests' counters. In this paper, we propose the Noisy-Follow-the-Perturbed-Leader (NFPL) algorithm, a variant of the classic Follow-the-Perturbed-Leader (FPL) when request estimates are noisy, and we show that the proposed solution has sublinear regret under specific conditions on the requests estimator. The experimental evaluation compares the proposed solution against classic caching policies and validates the proposed approach under both synthetic and real request traces.
BibTeX
@inproceedings{mazziane2023no,
  author = {Younes Ben Mazziane and Francescomaria Faticanti and Giovanni Neglia and Sara Alouf},
  title = {{No- Regret Caching with Noisy Request Estimates}},
  booktitle = {VCC},
  year = {2023},
  url = {https://openreview.net/forum?id=uaDNM3jrgD},
}

Loading related content...

Figure