We take a systematic look at the problem of storing whole files in a cache with limited capacity in the context of optimistic learning, where the caching policy has access to a prediction oracle. The successive file requests are assumed to be generated by an adversary, and no assumption is made on the accuracy of the oracle. We provide a universal lower bound for prediction-Assisted online caching and proceed to design a suite of policies with a range of performance-complexity trade-offs. All proposed policies offer sublinear regret bounds commensurate with the accuracy of the oracle. In this pursuit, we design, to the best of our knowledge, the first optimistic Follow-The-Perturbed leader policy, which generalizes beyond the caching problem. We also study the problem of caching files with different sizes and the bipartite network caching problem.

The advent of elastic Content Delivery Networks (CDNs) enable Content Providers (CPs) to lease cache capacity on demand and at different cloud and edge locations in order to enhance the quality of their services. This article addresses key challenges in this context, namely how to invest an available budget in cache space in order to match spatio-temporal fluctuations of demand, wireless environment and storage prices. Specifically, we jointly consider dynamic cache rental, content placement, and request-cache association in wireless scenarios in order to provide just-in-time CDN services. The goal is to maximize the an aggregate utility metric for the CP that captures both service benefits due to caching and fairness in servicing different end users. We leverage the Lyapunov drift-minus-benefit technique and Jensen's inequality to transform our infinite horizon problem into hour-by-hour subproblems which can be solved without knowledge of future file popularity and transmission rates. For the case of non-overlapping small cells, we provide an optimal subproblem solution. However, in the general overlapping case, the subproblem becomes a mixed integer non-linear program (MINLP). In this case, we employ a randomized cache lease method to derive a scalable solution. We show that the proposed algorithm guarantees the theoretical performance bound by exploiting the submodularity property of the objective function and pick-and-compare property of the randomized cache lease method. Finally, via real dataset driven simulations, we find that the proposed algorithm achieves 154% utility compared to similar static cache storage-based algorithms in a representative urban topology.