PaperlayerView exact revision on arXiv

Source-linked AI summary

No-Regret Mixing of LRU and LFU with Optimal Switching Cost

Younes Ben Mazziane, Xinying Zou

arXiv:2609.07566v2cs.LGcs.NI

TL;DR

Whether learning-inspired caching policies can guarantee sublinear regret against the better of LRU and LFU on every request sequence remains unclear. The paper proves linear regret for LeCaR and proposes H-MC, which preserves Hedge’s selection probabilities while minimizing switching cost. H-MC achieves sublinear regret, while LeCaR’s linear-regret result holds even with unbounded history.

  • Problem

    It remains unclear whether learning-inspired mixtures of LRU and LFU guarantee performance comparable to the better policy on every request sequence.

    Source: §1 · pp. 1–2

  • Method

    H-MC applies Hedge to virtual LRU and LFU caches, then couples consecutive selections to preserve their probabilities while minimizing switching.

    Source: Contributions · p. 2

  • Results

    LeCaR has linear regret against an oblivious adversary even with unbounded history, while H-MC achieves sublinear regret and has worst-case switching cost O(T).

    Source: Contributions · p. 2, §5 · p. 5

  • Takeaways & Limitations

    The paper concludes that a suitable experts formulation can combine sublinear regret with switching-cost minimization for caching.

    Source: §5 · p. 5

    H-MC minimizes switching cost, but a change in selected expert may still incur a large upload cost in one step; the paper uses switching cost as a proxy for practical upload cost.

    Source: §4 · p. 5, §5 · p. 5

Abstract

from arXiv · show

Caching systems often rely on simple eviction policies such as Least Recently Used (LRU) and Least Frequently Used (LFU), which perform well in complementary request regimes. Recent policies such as LeCar and Cacheus combine LRU and LFU using ideas from the experts problem in online learning. Specifically, upon a miss, they randomize between the two eviction rules using probabilities derived from scores updated by tracking the history of past evictions. While these policies exhibit strong empirical performance, it remains unclear whether they are guaranteed, on every request sequence, to perform asymptotically as well as the better of LRU and LFU, i.e., whether they achieve sublinear regret with respect to this benchmark. We first show that LeCar suffers linear regret against an oblivious adversary, even with unbounded history. We then propose H-MC, a Hedge-based mixture of virtual LRU and LFU caches that preserves Hedge's selection probabilities, and hence its regret guarantees, while minimizing the switching cost among all joint selection rules with these marginals.

1. INTRODUCTION

LRU and LFU suit complementary request regimes, but existing learning-inspired mixtures are not known to guarantee performance comparable to the better policy on every sequence. The paper proves LeCaR can have linear regret and introduces H-MC to retain Hedge’s regret guarantees while minimizing switching cost.

1. INTRODUCTION

  • LRU and LFU perform well in complementary regimes, yet adaptive mixtures are not known to match the better policy on arbitrary sequences.LFU is asymptotically optimal under stationary requests, while LRU can be more effective in non-stationary environments with temporal locality.Source: §1 · p. 1
  • Sublinear regret against the optimal static cache can still fail to capture performance on recency-friendly workloads.For the described phased trace, LRU incurs 2n misses while the optimal static cache incurs 2(n −1)r misses.Source: §1 · p. 1
  • H-MC combines virtual LRU and LFU caches while preserving Hedge’s selection probabilities and minimizing switching among couplings with those marginals.It uses maximal coupling between consecutive expert selections; the paper reports a worst-case switching cost of O(T).Source: Contributions · p. 2
  • LeCaR has linear regret against an oblivious adversary, even with unbounded history.A periodic trace makes LRU and LFU incur equal misses while recommending different stored files, leading LeCaR to switch repeatedly.Source: Contributions · p. 2

2. PROBLEM FORMULATION

The paper measures regret against the better of LRU and LFU over request sequences of length T. It also describes LeCaR’s eviction-based randomization and the cache state it maintains.

2. PROBLEM FORMULATION

  • Regret is the worst-case gap between an algorithm’s miss count and the smaller miss count of LRU or LFU.The goal is sublinear regret, which the paper states guarantees adaptation to frequency- and recency-driven workloads.Source: §2 · p. 2
  • Upon a miss, LeCaR randomizes between LRU and LFU eviction rules using probabilities derived from scores updated through past eviction history.When an evicted item is requested again, the rule responsible for its eviction is penalized.Source: §2 · p. 2
  • LeCaR maintains cache contents, a recency ordering, LFU counts, expert weights, and histories of items evicted on each expert’s recommendation.The request stream has length T, and the cache can store at most C of the N files.Source: §2 · p. 2

3. LECAR HAS LINEAR REGRET

LeCaR can incur linear regret even when LRU and LFU have comparable performance and histories are unbounded. A periodic request construction and a selection-probability drift argument establish the result for cache capacity two, then extend it to larger capacities.

3. LECAR HAS LINEAR REGRET

  • A periodic trace keeps LRU and LFU at comparable performance while maintaining different cache contents, and LeCaR’s switching makes it worse than both.The construction uses six-request phases with fresh items; the two policies each incur three misses per phase.Source: §3 · p. 3
  • LeCaR has linear regret for cache capacity C = 2 and any history length k ≥1, and the result extends to every C ≥2.The proof establishes constant excess misses per phase, yielding R^LeCaR_T = Ω(T).Source: §3 · pp. 3–4
  • A negative-drift argument for the Markov chain of the experts’ selection-probability ratio shows that the ratio does not escape to either extreme.Even with unbounded histories, the end-of-phase histories contain only items that will never be requested again, so they incur no future penalties.Source: §3 · pp. 3–4

4. CACHING WITH EXPERTS

The section formulates caching as an experts problem in which virtual LRU and LFU caches recommend complete cache states. H-MC couples consecutive expert choices to preserve Hedge’s probabilities while minimizing switching cost.

4. CACHING WITH EXPERTS

  • Each expert recommends the cache state maintained by its virtual LRU or LFU cache, making the regret of the resulting online decision problem coincide with the paper’s benchmark.Hedge’s probabilities are based on the experts’ miss counts.Source: §4 · p. 4
  • A switch between virtual caches may require uploading as many as C files, motivating switching cost as a proxy for update cost.The section also describes a flexible randomized-cache implementation that retains Hedge’s expected regret guarantee while avoiding a whole-cache upload in one shot.Source: §4 · pp. 4–5
  • Independent resampling can cause linear switching cost, while maximal coupling preserves consecutive selection marginals and minimizes switching probability.For two Bernoulli selections, the minimum mismatch probability is the absolute difference between their success probabilities.Source: §4 · pp. 4–5
  • H-MC inherits Hedge’s sublinear regret while minimizing switching cost among couplings with the same marginal probabilities.The section also reports a worst-case switching-cost bound of O(√T).Source: §4 · p. 5

5. CONCLUSION

The conclusion contrasts LeCaR-style mixing with H-MC: the former can have linear regret, while the latter achieves sublinear regret and minimizes switching cost. It identifies extensions to general experts and more practical upload-cost guarantees as future work.

5. CONCLUSION

  • LeCaR-style mixing can incur linear regret relative to the better of LRU and LFU.H-MC instead achieves sublinear regret while minimizing switching cost through maximal coupling of consecutive selections.Source: §5 · p. 5
  • The authors identify extending maximal coupling to efficient lazy no-regret algorithms for general experts as future work.The paper’s construction exploits the presence of two experts.Source: §5 · p. 5
  • The authors also propose pursuing caching policies with sublinear regret under a more practical upload-cost metric rather than switching cost as a proxy.Source: §5 · p. 5

APPENDIX

The appendix excerpt gives fragments of a LeCaR-style update algorithm, including its inputs, expert set, and cache-history operations. The supplied algorithm passages do not show a complete update sequence.

APPENDIX

  • The algorithm takes a request sequence, cache size, initial cache state and recency list, learning rate, discount factor, and history size as inputs.Source: A. LECAR · p. 6
  • It initializes the expert set to LRU and LFU, with per-expert weights and histories and initial LFU counters for cached items.Source: A. LECAR · p. 6
  • On a hit, the excerpt updates recency and increments the requested item’s LFU counter; on a miss, it updates cache state and histories of evicted items.The history excerpts specify timestamped insertion and discarding the oldest entry when the history exceeds size k.Source: A. LECAR · p. 6

B. PROOFS

The proof constructs a maximal coupling for two Bernoulli variables by first assigning probability to their agreement. Its minimum mismatch probability is the absolute difference between their success probabilities.

B. PROOFS

  • The construction sets r(i) to the smaller of the two distributions’ probabilities at outcome i, and α to the sum of those shared probabilities.Source: B. PROOFS · p. 6
  • With probability α, the coupled variables take the same value V; otherwise, they are drawn from residual distributions with disjoint supports.Source: B. PROOFS · p. 6
  • For Bernoulli variables with success probabilities x and y, the minimum mismatch probability is |x − y|, achieved by maximal coupling.Source: B. PROOFS · p. 6

C. HEDGE

Hedge selects experts using probabilities based on their cumulative losses. Its regret bound is minimax optimal up to constant factors.

C. HEDGE

  • Each expert incurs a loss in the standard experts problem.Source: C. HEDGE · p. 6
  • Hedge selects an expert at each time step with a probability based on cumulative loss.Source: C. HEDGE · p. 6
  • For any loss sequence, Hedge's regret is minimax optimal up to constant factors [4, Thm. 2.2 and Sec. 3.7].Source: C. HEDGE · p. 6

D. SIMULATIONS: UPLOAD COST AND MISS RATIO

The simulations compare miss ratios across synthetic traces and quantify how maximal coupling affects upload cost. Upload cost measures the files replaced into the cache between consecutive steps.

D. SIMULATIONS: UPLOAD COST AND MISS RATIO

D.1 Traces

The simulations use synthetic traces covering stationary frequency-oriented demand, changing recency-oriented demand, scans and churn, and adversarial requests with and without random perturbations.

D.1 Traces

  • The Zipf trace draws 100,000 requests independently from 1,000 items with exponent α = 1.1; the Markov-modulated trace alternates frequency- and recency-oriented regimes.The Markov regimes persist for an average of 500 requests, over 100,000 total requests.Source: §D.1 · p. 7
  • The scan/churn trace cycles through scans of 3C unseen items and churn phases of 2C new items, each requested four times.For C = 100, 100 cycles yield 110,000 requests.Source: §D.1 · p. 7
  • The adversarial trace uses C − 2 persistent objects and two evolving cache positions; its perturbed version replaces 2% of requests with draws from a 4C-object pool.Both versions use 2,000 phases and 60,015 requests.Source: §D.1 · p. 7

D.2 Experiment Setup and Results

Across five traces, maximal coupling reduces H-MC's upload cost relative to Hedge while their miss ratios remain nearly identical. Miss-ratio comparisons with LeCaR vary by workload.

D.2 Experiment Setup and Results

  • H-MC and Hedge are evaluated over 30 random seeds, with learning rate η = 8 log 2/T.LeCaR uses η = 0.45, history size C, and discount factor d = 0.0051/C, matching its original paper's configuration [17, Section 3].Source: §D.2 · p. 8
  • H-MC has a lower average miss ratio than LeCaR on Zipf and both adversarial traces, while LeCaR leads on Markov-modulated and scan/churn workloads.Source: §D.2 · p. 8
  • 23.6%–80.0% upload-cost savings accompany a largest observed H-MC–Hedge average miss-ratio difference of 0.052%.Across five traces, H-MC preserves Hedge's marginal expert-selection probabilities while changing the coupling between consecutive selections.Source: §D.2 · p. 8
Loading 2609.07566v2…