Optimistic No-regret Algorithms for Discrete Caching

Journal Article (2023)
Author(s)

Naram Mhaisen (TU Delft - Networked Systems)

Abhishek Sinha (Tata Institute of Fundamental Research)

Georgios Paschos (Amazon.com Inc.)

George Iosifidis (TU Delft - Networked Systems)

Research Group
Networked Systems
Copyright
© 2023 N. Mhaisen, Abhishek Sinha, Georgios Paschos, G. Iosifidis
DOI related publication
https://doi.org/10.1145/3606376.3593561
More Info
expand_more
Publication Year
2023
Language
English
Copyright
© 2023 N. Mhaisen, Abhishek Sinha, Georgios Paschos, G. Iosifidis
Research Group
Networked Systems
Issue number
1
Volume number
51
Pages (from-to)
69-70
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

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.

Files

3606376.3593561.pdf
(pdf | 1.13 Mb)
- Embargo expired in 27-12-2023
License info not available