# Online Convex Optimization for Caching Networks

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

## Key facts

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

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

- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (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)
- [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)
- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)
- [Meta-Learning-Based Handover Management in NextG O-RAN](https://mlsanity.com/paper/2512.22022/) (2025)

## Abstract (arXiv)

We study the problem of wireless edge caching when file popularity is unknown and possibly non-stationary. A bank of J caches receives file requests and a utility is accrued for each request depending on the serving cache. The network decides dynamically which files to store at each cache and how to route them, in order to maximize total utility. The request sequence is assumed to be drawn from an arbitrary distribution, thus capturing time-variance, temporal, or spatial locality of requests. For this challenging setting, we propose the Bipartite Supergradient Caching Algorithm (BSCA) which provably exhibits no regret (RT/T → 0). That is, as the time horizon T increases, BSCA achieves the same performance with the cache configuration that we would have chosen knowing all future requests. The learning rate of the algorithm is characterized by its regret expression, found to be RT=O(√JT), which is independent of the content catalog size. For the single-cache case, we prove that this is the lowest attainable bound. BSCA requires at each step J projections on intersections of boxes and simplices, for which we propose a tailored algorithm. Our model is the first that draws a connection between the network caching problem and Online Convex Optimization, and we demonstrate its generality by discussing various practical extensions and presenting a trace-driven comparison with state-of-the-art competitors.