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 LeadCache - an online caching policy based on the Follow-the-Perturbed-Leader paradigm. We show that the policy is regret-optimal up to a factor of 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\texttt{  Strong-Law-type assumption, we show that the total number of file fetches under \texttt{LeadCache} remains almost surely finite . Additionally , we derive a tight regret lower bound using results from graph coloring. Our conclusion is that the proposed learning-based caching \texttt{ policy decisively outperforms the classical policies both theoretically and empirically.
We consider a set-valued online prediction problem in the context of network caching. Assume that multiple users are connected to several caches via a bipartite network. At any time slot, each user requests an arbitrary file chosen from a large catalog. A user's request at a slot is met if the requested file is cached in at least one of the caches connected to the user. Our objective is to predict , prefetch, and optimally distribute the files on the caches to maximize the total number of cache hits in an online setting. The problem is non-trivial due to the non-convex and non-smooth nature of the objective function. In this paper, we propose LeadCache - an online caching policy based on the Follow-the-Perturbed-Leader paradigm. We show that the policy is regret-optimal up to a factor of O(n^{3/8}), where n is the number of users. We design two efficient implementations of the\texttt{LeadCache policy, one based on Pipage rounding and the other based on Madow's sampling, each of which makes precisely one call to an LP-solver per iteration. With a Strong-Law-type assumption, we show that the total number of file fetches under \texttt{LeadCache} remains almost surely finite over an infinite horizon. Finally , we derive a tight regret lower bound using results from graph coloring. We conclude that the learning-based \texttt{LeadCache policy decisively outperforms the known caching policies both theoretically and empirically.
A
multiple
R
a number of
several
R
some
an arbitrary
A
at a slot
R
The
Our
R
and optimally store
, prefetch, and optimally distribute
R
. We
in an online setting. The problem is non-trivial due to the non-convex and non-smooth nature of the objective function. In this paper, we
R
implement the policy by designing a new linear-time Pipage rounding algorithm. With an additional
design two efficient implementations of the
A
LeadCache
A
policy, one based on Pipage rounding and the other based on Madow's sampling, each of which makes precisely one call to an LP-solver per iteration. With a
R
. Additionally
over an infinite horizon. Finally
R
Our conclusion is that the proposed
We conclude that the
D
caching
A
LeadCache
R
classical
known caching