2022/04/20 by Naram Mhaisen, Mhaisen, Naram, George Iosifidis +3
Computer Science · #Caching and Content Delivery #FOS: Computer and information sciences #Machine Learning (cs.LG) #Networking and Internet Architecture (cs.NI) #Optimization and Search Problems #Recommender Systems and Techniques
paper · pdf · doi:10.48550/arxiv.2204.09345
openalex publication_date 2022/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The design of effective online caching policies is an increasingly important problem for content distribution networks, online social networks and edge computing services, among other areas. This paper proposes a new algorithmic toolbox for tackling this problem through the lens of optimistic online learning. We build upon the Follow-the-Regularized-Leader (FTRL) framework, which is developed further here to include predictions for the file requests, and we design online caching algorithms for bipartite networks with pre-reserved or dynamic storage subject to time-average budget constraints. The predictions are provided by a content recommendation system that influences the users viewing activity and hence can naturally reduce the caching network's uncertainty about future requests. We also extend the framework to learn and utilize the best request predictor in cases where many are available. We prove that the proposed optimistic learning caching policies can achieve sub-zero performance loss (regret) for perfect predictions, and maintain the sub-linear regret bound O(√ T), which is the best achievable bound for policies that do not use predictions, even for arbitrary-bad predictions. The performance of the proposed algorithms is evaluated with detailed trace-driven numerical tests.