No-Regret Caching via Online Mirror Descent

Caches are deployed at many different levels in computer systems: from CPU hardware caches to operating system memory caches, from application caches at clients to CDN caches deployed as physical servers in the network or as cloud services like Amazon's ElastiCache [1]. They aim to provide faster service to the user and/or to reduce the computation/communication load on other system elements, like hard disks, file servers, etc. The ubiquity of caches has motivated extensive research on the performance of existing caching policies, as well as on the design of new policies with provable guarantees. To that end, most prior work has assumed that caches serve requests generated according to a stochastic process, ranging from the simple, memory-less independent reference model [2] to more complex models trying to capture temporal locality effects and time-varying popularities (e.g., the shot-noise model [3]). An alternative modeling approach is to consider an adversarial setting.