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.

We learn optimal user association policies for traffic from different locations to Access Points(APs), in the presence of unknown dynamic traffic demand. We aim at minimizing a broad family of α-fair cost functions that express various objectives in load assignment in the wireless downlink, such as total load or total delay minimization. Finding an optimal user association policy in dynamic environments is challenging because traffic demand fluctuations over time are non-stationary and difficult to characterize statistically, which obstructs the computation of cost-efficient associations. Assuming arbitrary traffic patterns over time, we formulate the problem of online learning of optimal user association policies using the Online Convex Optimization (OCO) framework. We introduce a periodic benchmark for OCO problems that generalizes state-of-the-art benchmarks. We exploit inherent properties of the online user association problem and propose PerOnE, a simple online learning scheme that dynamically adapts the association policy to arbitrary traffic demand variations. We compare PerOnE against our periodic benchmark and prove that it enjoys the no-regret property, with additional sublinear dependence of the network size. To the best of our knowledge, this is the first work that introduces a periodic benchmark for OCO problems and a no-regret algorithm for the online user association problem. Our theoretical findings are validated through results on a real-trace dataset.