Online Convex Optimization for Caching Networks

Georgios S. Paschos, Apostolos Destounis, George Iosifidis

Abstract

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 ($R_T/T \to 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 $R_T=O(\sqrt{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.

Introduction

In modern wireless edge caching, small-cell base stations (SBSs) store popular content to reduce latency and backhaul load. However, two major hurdles exist: non-stationarity and network complexity. File popularity changes rapidly and unpredictably, making traditional policies like Least-Recently-Used (LRU) or Least-Frequently-Used (LFU) suboptimal as they are often tuned for static request models. Furthermore, in dense wireless networks, a user might be within range of multiple caches, creating a coupling between caching (what to store) and routing (which cache should serve the request).

Figure 1: Wireless edge caching network architecture with macro-cell and small-cell base stations serving mobile users.

The goal is to develop a "universal" policy that performs as well as the best static configuration chosen in hindsight, regardless of whether the request sequence is stationary, adversarial, or follows complex temporal/spatial patterns.

Methodology: The BSCA Algorithm

The authors reformulate the caching network as an Online Convex Optimization (OCO) problem. The network is modeled as a bipartite graph where user locations are connected to a set of caches. Each request yields a "utility" (e.g., bandwidth savings or reduced delay) based on which cache serves it.

The Bipartite Supergradient Caching Algorithm (BSCA) is proposed to handle this setting. Since the utility function is concave but not always differentiable (piecewise linear), the algorithm utilizes supergradients. At each time step, the algorithm observes a request, calculates the optimal routing for the current cache state, and then updates the cache contents by moving in the direction of the supergradient.

Figure 2: The iterative process of the BSCA algorithm within a single time slot.

A major technical contribution is the Fast Cache Projection step. Ensuring the updated cache state fits within storage constraints (the "capped simplex") is typically a bottleneck. The authors developed a tailored algorithm that performs this projection in $O(N)$ time, where $N$ is the number of files, making it feasible for massive libraries. Unlike reactive policies that just swap files, BSCA treats caching variables as fractional, allowing for gradual, "inertial" updates that balance frequency and recency.

Key Insights and Results

A remarkable theoretical result is that the regret bound of BSCA is $O(\sqrt{JT})$, where $J$ is the number of caches and $T$ is time. Crucially, this bound is independent of the number of files ($N$), which is vital for real-world Content Delivery Networks (CDNs) with enormous catalogs. For the single-cache case, this regret matches the lowest possible theoretical bound.

BSCA acts as a hybrid between LRU and LFU, remembering frequency while reacting to recent requests. Its decisions are "smoother" due to a Euclidean regularizer in the projection step, preventing overreaction to noise. The algorithm was evaluated using synthetic Zipf models, Poisson Shot Noise models (simulating ephemeral content like trending videos), and real-world web traces:

  • No-Regret Guarantee: The algorithm provably achieves zero average utility loss compared to the best static hindsight policy as $T \to \infty$.
  • Performance Gains: In trace-driven simulations, BSCA outperformed LRU and LFU by up to 20% in hit rate for non-stationary models.
  • Network Efficiency: In complex bipartite networks with asymmetric utilities, BSCA outperformed "Lazy-LRU" and "Multi-LRU" by as much as 45.8%, demonstrating its superior ability to learn optimal file placement across multiple caches.

Conclusion and Future Work

BSCA provides a robust framework for dynamic caching in complex, non-stationary networks. While the current model assumes an uncapacitated bipartite graph, future work includes extending this OCO approach to non-bipartite mesh networks and integrating it with lower-level resource allocation, such as transmission power control and link scheduling. Additionally, while fractional caching can be implemented via MDS coding, practical engineering for legacy systems remains an area for further exploration.

Summary updated

Abstract

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 \emph{Bipartite Supergradient Caching Algorithm} (BSCA) which provably exhibits no regret ($R_T/T \to 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 $R_T=O(\sqrt{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.
BibTeX
@article{paschos2020online,
  author = {Georgios S. Paschos and Apostolos Destounis and George Iosifidis},
  title = {{Online Convex Optimization for Caching Networks}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2020},
  url = {https://openreview.net/forum?id=0WMHNuBZx2},
}
Figure