Caching with Time-Varying Popularity Profiles: A Learning-Theoretic Perspective

Content caching at the small-cell base stations (sBSs) in a heterogeneous wireless network is considered. A cost function is proposed that captures the backhaul link load, called the 'offloading loss,' which measures the fraction of the requested files that are not available in the sBS caches. As opposed to the previous approaches that consider time-invariant and perfectly known popularity profiles, caching with non-stationary and statistically dependent popularity profiles (assumed unknown, and hence, estimated) is studied from a learning-theoretic perspective. A probably approximately correct result is derived, which presents a high probability bound on the offloading loss difference, i.e., the error between the estimated and the optimal offloading loss. The difference is a function of the Rademacher complexity, the eta -mixing coefficient, the number of time slots, and a measure of discrepancy between the estimated and true popularity profiles. A cache update algorithm is proposed, and simulation results are presented to show its superiority over periodic updates. The performance analyses for Bernoulli and Poisson request models are also presented.