Learning to Cache With No Regrets
arXiv:1904.09849
Abstract
This paper introduces a novel caching analysis that, contrary to prior work, makes no modeling assumptions for the file request sequence. We cast the caching problem in the framework of Online Linear Optimization (OLO), and introduce a class of minimum regret caching policies, which minimize the losses with respect to the best static configuration in hindsight when the request model is unknown. These policies are very important since they are robust to popularity deviations in the sense that they learn to adjust their caching decisions when the popularity model changes. We first prove a novel lower bound for the regret of any caching policy, improving existing OLO bounds for our setting. Then we show that the Online Gradient Ascent (OGA) policy guarantees a regret that matches the lower bound, hence it is universally optimal. Finally, we shift our attention to a network of caches arranged to form a bipartite graph, and show that the Bipartite Subgradient Algorithm (BSA) has no regret
IEEE INFOCOM 2019
References in corpus (8)
- Optimal Geographic Caching In Cellular Networks
- Optimal and Scalable Caching for 5G Using Reinforcement Learning of Space-time Popularities
- A versatile and accurate approximation for LRU cache performance
- Placing Dynamic Content in Caches with Small Population
- Online convex optimization and no-regret learning: Algorithms, guarantees and applications
- Projection onto the capped simplex
- Adapting Caching to Audience Retention Rate: Which Video Chunk to Store?
- Spatial multi-LRU: Distributed Caching for Wireless Networks with Coverage Overlaps