No-Regret Caching via Online Mirror Descent
This work addresses efficient caching strategies for systems with retrieval costs, offering incremental improvements in regret analysis and practical rounding methods.
The paper tackles the online caching problem by analyzing no-regret algorithms based on Online Mirror Descent (OMD), showing that regret bounds depend on request diversity and characterizing optimality across regimes, with a randomized rounding scheme preserving guarantees for whole-file storage.
We study an online caching problem in which requests can be served by a local cache to avoid retrieval costs from a remote server. The cache can update its state after a batch of requests and store an arbitrarily small fraction of each file. We study no-regret algorithms based on Online Mirror Descent (OMD) strategies. We show that bounds for the regret crucially depend on the diversity of the request process, provided by the diversity ratio R/h, where R is the size of the batch, and h is the maximum multiplicity of a request in a given batch. We characterize the optimality of OMD caching policies w.r.t. regret under different diversity regimes. We also prove that, when the cache must store the entire file, rather than a fraction, OMD strategies can be coupled with a randomized rounding scheme that preserves regret guarantees, even when update costs cannot be neglected. We provide a formal characterization of the rounding problem through optimal transport theory, and moreover we propose a computationally efficient randomized rounding scheme.