# Optimistic No-regret Algorithms for Discrete Caching

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 72 references that are in the map.
- First posted on arXiv 15 Aug 2022.

## Builds on (most cited first, 30 of 36)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [Online Non-Convex Learning: Following the Perturbed Leader is Optimal](https://mlsanity.com/paper/1903.08110/) (2019)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [Online Linear Optimization via Smoothing](https://mlsanity.com/paper/1405.6076/) (2014)
- [Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness](https://mlsanity.com/paper/2202.07554/) (2022)
- [A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret](https://mlsanity.com/paper/1508.03769/) (2015)
- [Projection onto the capped simplex](https://mlsanity.com/paper/1503.01002/) (2015)
- [Optimal and Scalable Caching for 5G Using Reinforcement Learning of Space-time Popularities](https://mlsanity.com/paper/1708.06698/) (2017)
- [A Reinforcement-Learning Approach to Proactive Caching in Wireless Networks](https://mlsanity.com/paper/1712.07084/) (2017)
- [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)
- [No-Regret Caching via Online Mirror Descent](https://mlsanity.com/paper/2101.12588/) (2021)
- [Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Games](https://mlsanity.com/paper/2006.07541/) (2020)
- [The Role of Caching in Future Communication Systems and Networks](https://mlsanity.com/paper/1805.11721/) (2018)
- [Reinforcement Learning for Adaptive Caching with Dynamic Storage Pricing](https://mlsanity.com/paper/1812.08593/) (2018)
- [ktexttt-experts -- Online Policies and Fundamental Limits](https://mlsanity.com/paper/2110.07881/) (2021)
- [Spatial multi-LRU Caching for Wireless Networks with Coverage Overlaps](https://mlsanity.com/paper/1602.07623/) (2016)
- [Online Convex Optimization for Caching Networks](https://mlsanity.com/paper/2001.06351/) (2020)
- [Online Caching with Optimistic Learning](https://mlsanity.com/paper/2202.10590/) (2022)
- [Cache Optimization Models and Algorithms](https://mlsanity.com/paper/1912.12339/) (2019)
- [Placing Dynamic Content in Caches with Small Population](https://mlsanity.com/paper/1601.03926/) (2016)
- [Implicit Coordination of Caches in Small Cell Networks under Unknown Popularity Profiles](https://mlsanity.com/paper/1804.01895/) (2018)
- [Timely-Throughput Optimal Scheduling with Prediction](https://mlsanity.com/paper/1712.05677/) (2017)

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

- [No-regret Algorithms for Fair Resource Allocation](https://mlsanity.com/paper/2303.06396/) (2023)
- [On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning](https://mlsanity.com/paper/2505.22899/) (2025)
- [Fair Resource Allocation in Virtualized O-RAN Platforms](https://mlsanity.com/paper/2402.11285/) (2024)
- [Adaptive Online Non-stochastic Control](https://mlsanity.com/paper/2310.02261/) (2023)
- [Optimistic Online Non-stochastic Control via FTRL](https://mlsanity.com/paper/2404.03309/) (2024)
- [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)
- [Online Subset Selection using α-Core with no Augmented Regret](https://mlsanity.com/paper/2209.14222/) (2022)
- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)

## Abstract (arXiv)

We take a systematic look at the problem of storing whole files in a cache with limited capacity in the context of optimistic learning, where the caching policy has access to a prediction oracle (provided by, e.g., a Neural Network). The successive file requests are assumed to be generated by an adversary, and no assumption is made on the accuracy of the oracle. In this setting, we provide a universal lower bound for prediction-assisted online caching and proceed to design a suite of policies with a range of performance-complexity trade-offs. All proposed policies offer sublinear regret bounds commensurate with the accuracy of the oracle. Our results substantially improve upon all recently-proposed online caching policies, which, being unable to exploit the oracle predictions, offer only O(√T) regret. In this pursuit, we design, to the best of our knowledge, the first comprehensive optimistic Follow-the-Perturbed leader policy, which generalizes beyond the caching problem. We also study the problem of caching files with different sizes and the bipartite network caching problem. Finally, we evaluate the efficacy of the proposed policies through extensive numerical experiments using real-world traces.