# LeadCache: Regret-Optimal Caching in Networks

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Sep 2020.

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

- [No-Regret Caching via Online Mirror Descent](https://mlsanity.com/paper/2101.12588/) (2021)
- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (2022)
- [No-regret Algorithms for Fair Resource Allocation](https://mlsanity.com/paper/2303.06396/) (2023)
- [Online Caching with no Regret: Optimistic Learning via Recommendations](https://mlsanity.com/paper/2204.09345/) (2022)
- [Universal Caching](https://mlsanity.com/paper/2205.04860/) (2022)
- [Personalized Federated Learning for Cellular VR: Online Learning and Dynamic Caching](https://mlsanity.com/paper/2501.11745/) (2025)
- [On the Regret of Online Edge Service Hosting](https://mlsanity.com/paper/2303.06851/) (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)
- [Online Subset Selection using α-Core with no Augmented Regret](https://mlsanity.com/paper/2209.14222/) (2022)
- [Tight Bounds for γ-Regret via the Decision-Estimation Coefficient](https://mlsanity.com/paper/2303.03327/) (2023)
- [α-Fair Contextual Bandits](https://mlsanity.com/paper/2310.14164/) (2023)
- [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 consider an online prediction problem in the context of network caching. Assume that multiple users are connected to several caches via a bipartite network. At any time slot, each user may request an arbitrary file chosen from a large catalog. A user's request at a slot is met if the requested file is cached in at least one of the caches connected to the user. Our objective is to predict, prefetch, and optimally distribute the files on the caches at each slot to maximize the total number of cache hits. The problem is non-trivial due to the non-convex and non-smooth nature of the objective function. In this paper, we propose textttLeadCache - an efficient online caching policy based on the Follow-the-Perturbed-Leader paradigm. We show that textttLeadCache is regret-optimal up to a factor of tildeO(n3/8), where n is the number of users. We design two efficient implementations of the textttLeadCache policy, one based on Pipage rounding and the other based on Madow's sampling, each of which makes precisely one call to an LP-solver per iteration. Furthermore, with a Strong-Law-type assumption, we show that the total number of file fetches under textttLeadCache remains almost surely finite over an infinite horizon. Finally, we derive an approximately tight regret lower bound using results from graph coloring. We conclude that the learning-based textttLeadCache policy decisively outperforms the state-of-the-art caching policies both theoretically and empirically.