To join this virtual meeting via Zoom, click here.
This Zoom meeting requires a passcode. Email the organizers (Cameron Musco or Rik Sengupta) if you need the Zoom password, or see emails on the seminars list.
Title: Fundamental Limits on the Regret of Online Network-Caching
Abstract: Optimal caching of files in a content distribution network is a problem of fundamental and growing commercial interest. Although many different caching algorithms are in use today, the fundamental performance limits of network caching algorithms from an online learning point-of-view remain poorly understood to date. Recently, an online gradient-based \emph{coded} caching policy was shown to enjoy sub-linear regret. However, due to the lack of known regret lower bounds, the question of the optimality of the proposed policy was left open. In this talk, we settle this question by deriving tight non-asymptotic regret lower bounds for online caching. We first derive regret lower bounds for the setting when a single user is connected to a single cache and then tackle the more general case of a set of users and a set of caches interconnected through a bipartite network. In addition to that, we propose a new Follow-the-Perturbed-Leader-based \emph{uncoded} caching policy with near-optimal regret. Technically, the lower-bounds are obtained by relating the online caching problem to the classic probabilistic paradigm of balls-into-bins. Our proofs make extensive use of a new result on the expected load in the most populated half of the bins, which might also be of independent interest. Finally, we experimentally demonstrate the performance of the online caching policies and conclude the talk with design recommendations and a list of open problems. This talk is based on joint work* with Subhankar Banerjee and Abhishek Sinha.
*Fundamental Limits on the Regret of Online Network-Caching (ACM Sigmetrics 2020)