# An Online Gradient-Based Caching Policy with Logarithmic Complexity and Regret Guarantees

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 47 references that are in the map.
- First posted on arXiv 2 May 2024.

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

- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [The Computational Power of Optimization in Online Learning](https://mlsanity.com/paper/1504.02089/) (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)
- [No-Regret Caching via Online Mirror Descent](https://mlsanity.com/paper/2101.12588/) (2021)
- [Online Caching with Optimal Switching Regret](https://mlsanity.com/paper/2101.07043/) (2021)
- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (2022)
- [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)
- [Adaptive Oracle-Efficient Online Learning](https://mlsanity.com/paper/2210.09385/) (2022)
- [Regret-Optimal Online Caching for Adversarial and Stochastic Arrivals](https://mlsanity.com/paper/2211.16051/) (2022)
- [An O(1) algorithm for implementing the LFU cache eviction scheme](https://mlsanity.com/paper/2110.11602/) (2021)
- [A Utility Optimization Approach to Network Cache Design](https://mlsanity.com/paper/1601.06838/) (2016)
- [Optimistic Online Caching for Batched Requests](https://mlsanity.com/paper/2310.01309/) (2023)
- [Elastic Provisioning of Cloud Caches: a Cost-aware TTL Approach](https://mlsanity.com/paper/1802.04696/) (2018)
- [Exact Analysis of TTL Cache Networks: The Case of Caching Policies driven by Stopping Times](https://mlsanity.com/paper/1402.5987/) (2014)

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

- [Efficient and Optimal No-Regret Caching under Partial Observation](https://mlsanity.com/paper/2503.02758/) (2025)

## Abstract (arXiv)

Commonly used caching policies, such as LRU (Least Recently Used) or LFU (Least Frequently Used), exhibit optimal performance only under specific traffic patterns. Even advanced machine learning-based methods, which detect patterns in historical request data, struggle when future requests deviate from past trends. Recently, a new class of policies has emerged that are robust to varying traffic patterns. These algorithms address an online optimization problem, enabling continuous adaptation to the context. They offer theoretical guarantees on the regret metric, which measures the performance gap between the online policy and the optimal static cache allocation in hindsight. However, the high computational complexity of these solutions hinders their practical adoption. In this study, we introduce a new variant of the gradient-based online caching policy that achieves groundbreaking logarithmic computational complexity relative to catalog size, while also providing regret guarantees. This advancement allows us to test the policy on large-scale, real-world traces featuring millions of requests and items - a significant achievement, as such scales have been beyond the reach of existing policies with regret guarantees. To the best of our knowledge, our experimental results demonstrate for the first time that the regret guarantees of gradient-based caching policies offer substantial benefits in practical scenarios.