2021/01/29 by Tareq Si Salem, Salem, T. Si, Giovanni Neglia +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Caching and Content Delivery #FOS: Computer and information sciences #Machine Learning (cs.LG) #Networking and Internet Architecture (cs.NI) #Optimization and Search Problems #Performance (cs.PF)
paper · pdf · doi:10.48550/arxiv.2101.12588
openalex publication_date 2021/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.