We consider the onlineBipartite Caching problem where n users are connected to m caches in the form of a bipartite network. Each of the m caches has a file storage capacity of C. There is a library consisting of N >C distinct files. Each user can request any one of the files from the library at each time slot. We allow the file request sequences to be chosen in an adversarial fashion . A user's request at a time slot is satisfied if the requested file is already hosted on at least one of the caches connected to the user at that time slot. Our objective is to design an efficient online caching policy with minimal regret. In this paper, we proposeLeadCache,\texttt{  an online caching policy based on the \textsf{Follow the Perturbed Leader (FTPL) paradigm. We show that \textsf{LeadCache is regret optimal up to a multiplicative factor of \tilde{O}(n^{ 0.375 }) . As a byproduct of our analysis, we design a new linear-time deterministic Pipage rounding procedure for the LP relaxation of a well-known NP-hard combinatorial optimization problem in this area. Our new rounding algorithmsubstantially improves upon the currently best-known complexity for this problem. Moreover , we show the surprising result that under mild Strong-Law-type assumptions on the file request sequence, the rate of file fetches to the caches approaches to zero under the\textsf{LeadCache policy. Finally\texttt{  , we derive a tight universal regret lower bound for the\textsf{Bipartite Caching problem, which critically makes use of results from graph coloring theory and certifies the announced approximation ratio .
We consider a set-valued online prediction problem in the context of network caching. Assume that users are connected to a number of caches via a bipartite network. At any time slot, each user requests some file chosen from a large catalog . A user's request is met if the requested file is cached in at least one of the caches connected to the user . The objective is to predict and optimally store the files on the caches to maximize the total number of cache hits. We propose\texttt{LeadCache - an online caching policy based on the \textsf{ Follow-the-Perturbed-Leader paradigm. We show that \textsf{ the policy is regret-optimal up to a factor of \tilde{O}(n^{ 3/8 }) , where n is the number of users. We implement the policy by designing a new linear-time Pipage rounding algorithm. With an additional Strong-Law-type assumption , we show that the total number of file fetches \textsf{ under\texttt{LeadCache remains almost surely finite. Additionally , we derive a tight regret lower bound \textsf{ using results from graph coloring . Our conclusion is that the proposed learning-based caching policy decisively outperforms the classical policies both theoretically and empirically .
D
the online
D
Bipartite Caching
R
problem where n
a set-valued online prediction problem in the context of network caching. Assume that
R
m caches in the form of
a number of caches via
R
Each of the m caches has a file storage capacity of C. There is a library consisting of N >C distinct files. Each user can request any one of the files from the library at each time slot. We allow the file request sequences to be chosen in an adversarial fashion
At any time slot, each user requests some file chosen from a large catalog
R
at a time slot is satisfied
is met
R
already hosted on
cached in
R
at that time slot. Our
. The
D
design an efficient online caching policy with minimal regret. In this paper, we propose
R
LeadCache,
predict and optimally store the files on the caches to maximize the total number of cache hits. We propose
A
LeadCache
A
-
D
Follow the Perturbed Leader
R
(FTPL)
Follow-the-Perturbed-Leader
D
LeadCache
R
is regret optimal
the policy is regret-optimal
D
multiplicative
R
0.375
3/8
R
. As a byproduct of our analysis, we design a
, where n is the number of users. We implement the policy by designing a
R
deterministic Pipage rounding procedure for the LP relaxation of a well-known NP-hard combinatorial optimization problem in this area. Our new rounding algorithmsubstantially improves upon the currently best-known complexity for this problem. Moreover
Pipage rounding algorithm. With an additional Strong-Law-type assumption
R
the surprising result that under mild Strong-Law-type assumptions on the file request sequence, the rate
that the total number
D
to the caches approaches to zero under the
D
LeadCache
R
policy. Finally
under
A
LeadCache
A
remains almost surely finite. Additionally
D
universal
D
for the
D
Bipartite Caching
R
problem, which critically makes use of
using
R
theory and certifies the announced approximation ratio
. Our conclusion is that the proposed learning-based caching policy decisively outperforms the classical policies both theoretically and empirically