Title
Optimistic No-regret Algorithms for Discrete Caching
Author
Mhaisen, N. (TU Delft Networked Systems)
Sinha, Abhishek (Tata Institute of Fundamental Research)
Paschos, Georgios (Amazon.com Inc.)
Iosifidis, G. (TU Delft Networked Systems)
Date
2023
Abstract
We take a systematic look at the problem of storing whole files in a cache with limited capacity in the context of optimistic learning, where the caching policy has access to a prediction oracle. The successive file requests are assumed to be generated by an adversary, and no assumption is made on the accuracy of the oracle. We provide a universal lower bound for prediction-Assisted online caching and proceed to design a suite of policies with a range of performance-complexity trade-offs. All proposed policies offer sublinear regret bounds commensurate with the accuracy of the oracle. In this pursuit, we design, to the best of our knowledge, the first optimistic Follow-The-Perturbed leader policy, which generalizes beyond the caching problem. We also study the problem of caching files with different sizes and the bipartite network caching problem.
Subject
caching
online algorithms
optimistic learning
regret bounds
To reference this document use:
http://resolver.tudelft.nl/uuid:5dceb596-50a6-43fb-ad3d-3f28f874be46
DOI
https://doi.org/10.1145/3606376.3593561
Embargo date
2023-12-27
ISSN
0163-5999
Source
ACM SIGMETRICS Performance Evaluation Review, 51 (1), 69-70
Bibliographical note
Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.
Part of collection
Institutional Repository
Document type
journal article
Rights
© 2023 N. Mhaisen, Abhishek Sinha, Georgios Paschos, G. Iosifidis