# No-Regret Caching via Online Mirror Descent

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 63 references that are in the map.
- First posted on arXiv 29 Jan 2021.

## Builds on (most cited first, 16 of 16)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret](https://mlsanity.com/paper/1508.03769/) (2015)
- [Learning to Cache With No Regrets](https://mlsanity.com/paper/1904.09849/) (2019)
- [Projection onto the capped simplex](https://mlsanity.com/paper/1503.01002/) (2015)
- [LeadCache: Regret-Optimal Caching in Networks](https://mlsanity.com/paper/2009.08228/) (2020)
- [Temporal Locality in Today's Content Caching: Why it Matters and How to Model it](https://mlsanity.com/paper/1305.7114/) (2013)
- [Online Caching with Optimal Switching Regret](https://mlsanity.com/paper/2101.07043/) (2021)
- [Adaptive Caching Networks with Optimality Guarantees](https://mlsanity.com/paper/1604.03175/) (2016)
- [k-server via multiscale entropic regularization](https://mlsanity.com/paper/1711.01085/) (2017)
- [Cache Optimization Models and Algorithms](https://mlsanity.com/paper/1912.12339/) (2019)
- [Implicit Coordination of Caches in Small Cell Networks under Unknown Popularity Profiles](https://mlsanity.com/paper/1804.01895/) (2018)
- [A unified approach to the performance analysis of caching systems](https://mlsanity.com/paper/1307.6702/) (2013)
- [A Utility Optimization Approach to Network Cache Design](https://mlsanity.com/paper/1601.06838/) (2016)
- [Optimal Geographic Caching In Cellular Networks](https://mlsanity.com/paper/1409.7626/) (2014)
- [Joint Cache Resource Allocation and Request Routing for In-network Caching Services](https://mlsanity.com/paper/1710.11376/) (2017)

## Built on by (most cited first, 12 of 12)

- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (2022)
- [Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximation](https://mlsanity.com/paper/2202.13187/) (2022)
- [Online Caching with Optimistic Learning](https://mlsanity.com/paper/2202.10590/) (2022)
- [Online Caching with no Regret: Optimistic Learning via Recommendations](https://mlsanity.com/paper/2204.09345/) (2022)
- [Ascent Similarity Caching with Approximate Indexes](https://mlsanity.com/paper/2107.00957/) (2021)
- [On the Regret of Online Edge Service Hosting](https://mlsanity.com/paper/2303.06851/) (2023)
- [No-Regret Caching with Noisy Request Estimates](https://mlsanity.com/paper/2309.02055/) (2023)
- [An Online Gradient-Based Caching Policy with Logarithmic Complexity and Regret Guarantees](https://mlsanity.com/paper/2405.01263/) (2024)
- [Efficient and Optimal No-Regret Caching under Partial Observation](https://mlsanity.com/paper/2503.02758/) (2025)
- [Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalities](https://mlsanity.com/paper/2604.07662/) (2026)
- [On the Regret of Coded Caching with Adversarial Requests](https://mlsanity.com/paper/2409.12387/) (2024)
- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)

## Abstract (arXiv)

We study an online caching problem in which requests can be served by a local cache to avoid retrieval costs from a remote server. The cache can update its state after a batch of requests and store an arbitrarily small fraction of each file. We study no-regret algorithms based on Online Mirror Descent (OMD) strategies. We show that bounds for the regret crucially depend on the diversity of the request process, provided by the diversity ratio R/h, where R is the size of the batch, and h is the maximum multiplicity of a request in a given batch. We characterize the optimality of OMD caching policies w.r.t. regret under different diversity regimes. We also prove that, when the cache must store the entire file, rather than a fraction, OMD strategies can be coupled with a randomized rounding scheme that preserves regret guarantees, even when update costs cannot be neglected. We provide a formal characterization of the rounding problem through optimal transport theory, and moreover we propose a computationally efficient randomized rounding scheme.