No-Regret Caching via Online Mirror Descent

Tareq Si Salem (1, 2) , Giovanni Neglia (2) , Stratis Ioannidis (3)

1 UniCA - Université Côte d'Azur
2 NEO - Network Engineering and Operations
3 Northeastern University [Boston]

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.

Domaines: Informatique [cs]

Tareq Si Salem, Giovanni Neglia, Stratis Ioannidis. No-Regret Caching via Online Mirror Descent. ICC 2021 - IEEE International Conference on Communications, Jul 2021, Montreal (virtual), Canada. ⟨10.1109/ICC42927.2021.9500487⟩. ⟨hal-03376156⟩