| Paper ID | D4-S1-T3.3 |
| Paper Title |
Online Caching with Optimal Switching Regret |
| Authors |
Samrat Mukhopadhyay, Abhishek Sinha, Indian Institute of Technology, Madras, India; , |
| Session |
D4-S1-T3: Online & Meta-Learning |
| Chaired Session: |
Thursday, 15 July, 22:00 - 22:20 |
| Engagement Session: |
Thursday, 15 July, 22:20 - 22:40 |
| Abstract |
We consider the classical uncoded caching problem from an online learning point-of-view. A cache of limited storage capacity can hold C files at a time from a large catalog. A user requests an arbitrary file from the catalog at each time slot. Before the file request from the user arrives, a caching policy populates the cache with any C files of its choice. In the case of a cache-hit, the policy receives a unit reward and zero rewards otherwise. In addition to that, there is a cost associated with fetching files to the cache, which we refer to as the switching cost. The objective is to design a caching policy that incurs minimal regret while considering both the rewards due to cache-hits and the switching cost due to the file fetches. The main contribution of this paper is the switching regret analysis of a FOLLOW THE PERTURBED LEADER-based anytime caching policy, which is shown to have an order optimal switching regret. In this pursuit, we improve the best-known switching regret bound for this problem by a factor of Θ(√C). We conclude the paper by comparing the performance of different popular caching policies using a publicly available trace from a commercial CDN server.
|
