No-Regret Caching via Online Mirror Descent
Tareq Si Salem, Giovanni Neglia, Stratis Ioannidis
Abstract
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 content. We study no-regret algorithms based on Online Mirror Descent (OMD) strategies. We show that the choice of OMD strategy depends on the request diversity present in a batch and that OMD caching policies may outperform traditional eviction-based policies.
Topics & Concepts
Computer scienceRegretCacheServerComputer networkScheme (mathematics)Online algorithmOnline modelCache algorithmsDescent (aeronautics)Distributed computingCPU cacheAlgorithmStatisticsMathematical analysisEngineeringMachine learningMathematicsAerospace engineeringCaching and Content DeliveryOptimization and Search ProblemsAdvanced Bandit Algorithms Research