$\texttt{LeadCache}$: Regret-Optimal Caching in Networks
Authors: Debjit Paria
Abhishek Sinha
Venue: NeurIPS 2021 Poster (2021)
Keywords: Online learning
Network Caching
Regret Lower Bounds

Abstract: We consider an 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 may request 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 at each slot to maximize the total number of cache hits. The problem is non-trivial due to the non-convex and non-smooth nature of the objective function. In this paper, we propose $\texttt{LeadCache}$ - an efficient online caching policy based on the Follow-the-Perturbed-Leader paradigm. We show that $\texttt{LeadCache}$ is regret-optimal up to a factor of $\tilde{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. Furthermore, 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 an approximately tight regret lower bound using results from graph coloring. We conclude that the learning-based $\texttt{LeadCache}$ policy decisively outperforms the state-of-the-art caching policies both theoretically and empirically.

LeadCache: Regret-Optimal Caching in Networks
Debjit Paria'
Abhishek Sinha
Department of Computer Science Chennai Mathematical Institute Chennai 603103, India com
Department of Electrical Engineering
Indian Institute of Technology Madras
Chennai 600036, India
abhishek sinha@ee..eeeeeeeee .itm.. ac
Abstract
We consider an online prediction problem in the context of network caching. Assume that multiple users are connected to several caches via bipartite network. At any time slot, each user may request an arbitrary file chosen from a large catalog. A user's request
slot is met if the requested file is cached in least one of the caches connected to the user. Our objective is to predict, prefetch, and optimally distribute the files on the caches at each slot maximize the total number of cache hits. 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 efficient online caching policy based on the Follow-the- Follow-the-Perturrod--.co LeadCache is regret-optimal up to factor of Ō(n3/),, where is the number users. We design two efficient implementations of the LeadCache policy, one based Pipage rounding and the other based on Madow's sampling, each of which makes precisely one call to an LP-solver per iteration. Furthermore, with a Strong-Law assumption, show that the total number of file fetches under LeadCache remains almost surely finite over an infinite horizon. Finally, we derive approximately tight regret lower bound using results from graph coloring. We conclude that the learning- based LeadCache policy decisively outperforms the state-of-ther caching policies both theoretically and empirically.
paradigm. We show that
Introduction
We consider online structured learning problem, called Bipartite Caching, that lies at the of many large-scale internet services, including Content Distribution Networks (CDN) and Cloud Computing. Formally, set I of users is connected to set J of m caches via a bipartite network G(I J, E). Each cache is connected to at most d users, and each user is connected to at most A caches (see Figure (b)). There
catalog consisting of N unique files, and each of the caches can host at most C files at a time (in practice, C << N). The system evolves in discrete time slots. Each of the users may request any file from the catalog each time slot. The file requests could be dictated by an adversary. Given the storage capacity constraints, an online caching policy decides the files to be cached on different caches each slot before the requests for that slot arrive. The objective is to maximize the total number of hits by the unknown incoming requests by coordinating the caching decisions among multiple caches an online fashion. The Bipartite Caching problem is strict generalization of the online k-sets problem that predicts set of h items at each round so that the predicted set includes the item chosen by the adversary [Koolen al., 2010, Cohen and Hazan, 2015]. However, unlike the k-sets problem, which predicts single subset at time, in this problem, we are interested sequentially predicting multiple subsets, each corresponding to one of the caches. The interaction among the caches through the non-linear reward function makes this problem challenging.
Work done at the Indian Institute of Technology Madras part of the first author's Master's thesis.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

max-degree
6
Remote
Owke-
10
server
71 uSCTS
Cache
max-degree
User
Router
caches
(a)
(b)
Figure I: Reduction of the Network Caching problem (a) to the Bipartite Caching problem (b). In this schematic, we assumed that a cache, located within two hops, is reachable to a user.
The Bipartite Caching problem is simplified abstraction of the more general Network Caching problem central to the commercial CDNs, such as Akamai [Nygren et al., 2010], Amazon Web Services (AWS), and Microsoft Azure [Paschos et al., 2020]. In the Network Caching problem, V. and a set of caches J s V. A user
one is given an arbitrary graph (VV, E), a set of users can retrieve a file from cache only if the cache hosts the requested file. If the 1th user retrieves the requested file from the 5th cache, the user receives a reward of rij 2 0 for that slot. If the requested file is not hosted in any of the caches reachable to the user, the user receives zero rewards for that slot. The goal of network caching policy is to dynamically place files on the caches so that cumulative reward obtained by all users is maximized. The Network Caching problem reduces to the Bipartite Caching problem when the rewards restricted the set {0, 1}. It will be clear from the sequel that the algorithms presented in this paper can be extended to the general Network Caching problem well.
1.1 Prohlem Formulation
Denote the file requested by the 7th user by the one-hot encoded N N-ddimensional vector æf. In other words, æ the 1h user requests file f [N] at time slot t, or æi, = otherwise. Since user may request most one file per time slot, have: Σý- æi, S 1, Vi I, Vt. An online caching policy prefetches files the caches every time slot based past requests. Unlike classical caching policies, such as LRU, LFU, FIFO, Marker, that fetch a file immediately upon a cache-miss, we do enforce this constraint in the problem statement. The of files placed on the j cache at time other words, yi 1 the 5thh cache hosts file f [N] at time t, y 0 otherwise. Due to cache capacity constraints, the following inequality must be satisfied at each time slot I: Σ vi s C, VjeJ
represented by the N Y-dimensional incidence vector y! (0, 1)
The set of all admissible caching configurations, denoted by y' 10, 1m dictated by the cache capacity constraints. In principle. the caching policy is allowed to replace all elements of the caches every slot, incurring a potentially huge downloading cost over an interval. However, in Section we show that the total number of files fetched to the caches under the proposed LeadCache policy remains almost surely finite under very mild assumptions on the file request process.
The th user receives a cache hit at time slot if and only if any of the caches connected to the 8th user hosts the file requested by the reward. On the other hand, in the case of cache miss, the user receives zero rewards for that slot. Hence, for given aggregate request vector from all users æ, (æf, Z) and the aggregate cache configuration vector of all caches = (vl j J), the total reward q( (.) obtained by the users time may be expressed as follows:
slot t. In the case of cache hit, the user obtains unit
(a,, y:) Σ x min I ( Σ vi)}
(I)
jE0
where a- b denotes the inner-product of the vectors and b, Nx1 denotes the N-dimensional all-one column vector, the set (i) denotes the set all caches connected to the 7th user, and the "min" operator is applied component wise. The total reward QTT') accrued in time-horizon of length T

---

is obtained by summing the slot-wise rewards, i.e. 2(T)=EZx E g( V1). Following the standard practice in the online learning literature, we measure the performance of any online policy using the notion of (static) regret Rd (T), defined as the maximum difference in the cumulative rewards obtained by the optimal fixed
in hindsight and that of the online policy n, ie.,
(def.)
(L(eno) sup (wr
- E
R (T)
1=1
where y is the best static cache-configuration in hindsight for the file request sequence (mr ( i.e., y" arg may Σi= q( y). We assume that the file request sequence is generated by an oblivious adversary, i.e., the entire request sequence { { is fixed a priori. Note that the problem non-convex, as we seek binary cache allocations. With an eye towards efficient implementation. later we will also consider the problem of designing efficient policies that guarantee a-regret for a suitable value of a [Garber, 2021, Kakade et al., 2009, Fujita et al., 2013].
2 Background and Related Work
Online Linear Optimization (OLO) is canomical online learning problem that can be formulated as a repeated game played between learner (also known as the forecaster) and an adversary [Cesa- Bianchi and Lugosi, 2006]. In this model, at every time slot f, the policy selects an action yt from a feasible set J' = R.d After that, the adversary reveals a reward vector a; from set X' = IRd The adversary is assumed to be oblivious, Le., the sequence of reward vectors is fixed before the game begins. With the above choices, the policy receives a scalar reward {(x,, yr) (xr, yr) at slot t. A classic objective in this setting is to design a policy with small regret. Follow the Perturbed Leader (FTPL), is a well-known online policy for the OLO problem [Hannan, 1957]. At time slot 4, the FTPL policy adds a random noise vector Yt to the cumulative reward vector X, = Σ+= Br, and then selects the best action against this perturbed reward, i.e. y/ arg max X Yt y). See Abernethy et al. [2016] for unifying treatment of the FTPL policies through the lens of stochastic smoothing.
large number of papers on caching assume some stochastic model for the file request sequence, e.g., Independent Reference Model (IRM) and Shot Noise Model (SNM) [Traaerso et al., 2013]. Classic page replacement algorithms. such as MIN, LRU, LFU, and FIFO, are designed to minimize the competitive ratio with adversarial requests [Borodin and EI- Yaniv, 2005, Van Roy, 2007, Lee et al., 1999, Dan and Towsley, 1990]. These algorithms, being non- prefeetttn in nature, replace a page on demand upon cache-miss. However, since the competitive ratio metric is multiplicative in nature, there can be a large gap between the hit ratio of competitively optimal policy and the optimal offline policy. To design better algorithms, the caching problem has recently been investigated through the lens of regret minimization with prefetching policies that learn from the past request sequence [Vitter and Krishnan, 1996, Krishnan and Vitter, 1998]. Daniely and Mansour [2019] considered the problem of minimizing the regret plus the switching cost for a single cache. The authors proposed a variant of the celebrated exponential weight algorithm [Littlestone and Warmuth, 1994, Freund and Schapire, 1997] that ensures the minimum competitive ratio and a small but sub-optimal regret. The Bipartite Caching model was first proposed in a pioneering paper by Shanmugam et al. [2013]. where they considered a stochastic version of the problem with known file popularities. Paschos et al. [2019] proposed Online Gradient Ascent (OGA)- based Bipartite Caching policy that allows caching fraction of the Maximum Distance Separable (MDS)-coded files. Closely related to this paper is the recent work by Bhattacharjee et al. [2020], where the authors designed a regret-optimal single-cache policy and a Bipartite Caching policy for fountain-coded files. However, the fundamental problem of designing a regret-optimal uncoded caching policy for the Bipartite Caching problem was left as an open problem.
Why standard approaches fail: A straightforward way to formulate the Bipartite Caching problem is to pose it as an instance of the classic Prediction with Expert Advice problem [Cesa- Bianchi and Lugosi, 2006], where each of the possible (X)" cache configurations is treated as experts. However, this approach is computationally infeasible due to the massive number of resulting experts. Furthermore, the expected FTPL policy for convex losses in Hazan [2019] and its sampled version in Hazan and Minasyan [2020] are both computationally intensive, In view of the above challenges, now present our main technical contributions.
3

---

8: = ((8))
Z. pm #u:E))
FTPL
Nor-linear
Linear
Vartuaal Palicy
Physical Policy
Figure 2: Reduction pipeline illustrating the translation of the Bipartite Caching problem with non-linear reward function to an online learning problem with a linear reward function.
3 Main Results
1. FTPL for a non-linear non-convex problem: We propose LeadCache, network caching policy based on the Follow the Perturbed Leader paradigm. The non-linearity of the reward function and the non-convexity of the feasible set (due to the integrality of cache allocations) pose significant challenge in using the generic FTPL framework [Abernethy et al., 2016]. To circumvent this difficulty, we switch to virtual action domain 2 where the reward function is linear. We use an anytime version of the FTPL policy for designing a virtual policy for the linearized virtual learning problem. Finally, we translate the virtual policy back to the original action domain Y with the help of a mapping v + y obtained by solving a combinatorial optimization problem (see Figure 2 for the overall reduction pipeline).
New Rounding Techniques and a-regret: The mapping sb which translates the virtual actions to physical caching actions in the above scheme, turns out to be an NP-hard Integer Linear Program. As our second contribution, we design linear-time Pipage rounding technique for this problem [Ageev and Sviridenko, 2004]. Incidentally, our rounding process substantially improves upon previous rounding scheme proposed by Shanmugam
[2013] the context of caching with i.i.d. requests. Next, we propose linear-time randomized rounding scheme that yields an efficient online policy with a provable sub-linear a = 1 1/c regret. The proposed randomized rounding algorithm exploits a classical sampling technique used in statistical surveys.
Bounding the Switching Cost: As our third contribution, we show that if the file requests are generated by stochastic process satisfying mild Strong Law-type property, then the caching configuration under the LeadCache policy converges to the corresponding optimal configuration almost surely in finite time. As new file fetches to the caches from the remote server consume bandwidth, this result implies that the proposed policy offers the best of both worlds (1) a sub-linear regret for adversarial requests, and (2) finite downloads for "stochastically regular" requests.
4. New Regret Lower Bound: As final contribution, derive minimax regret lower bound that is tight up factor of Önn%)). Our lower bound sharpens result in Bhattacharjee al. [2020]. The proof of the lower bound critically utilizes graph coloring theory and the probabilistic Balls-into-Bine framework.
4 The LeadCache Policy
In this section, we propose LeadCache an efficient network caching policy that guarantees near- optimal regret. Since the reward function (1) is non-linear, we linearize the problem by switching to a virtual action domain 2, as detailed below.
The Virtual Caching Problem: First, we consider an associated Online Linear Optimization (OLO) problem, called Virtual Caching, as defined next. this problem, at each slot a virtual action 2, (z), i Z) taken in response to the file requests received so far. The 7th component of the virtual action, denoted by z (0, I. roughly indicates the availability of the files in the caches connected to the 4th user. The set of all admissible virtual actions, denoted by Z g {0, 1] Nxn is defined below in Eqn. (4). The reward r r(æ,, 2:) accrued by the virtual action z, for the file request vector at the th slot is given by their inner product, i.e.,
r(x 21) (x,, zx)
Σ x x/.
(3)

---

Virtual Actions: The set Z of all admissible virtual actions is defined as the set of all binary vectors é {0, 13 Nxm such that the following component wise inequalities hold for some admissible physical cache configuration vector y::
z' min [1NxI, (
v)),, isisn.
(4)
(1)
More explicitly, the set 2 can be characterized as the set of all binary vectors 2 E (0, 1) satisfying the following constraints for some feasible y E &V:
Σ sy Vie
(5)
Σ f-1
& C. VjEJ,
(6)
5/ {0,1},
(7)
Let v : + y be a mapping that maps any admissible virtual action & E Z to a corresponding physical caching action y satisfying the condition (4). Hence, the binary variable zi only the
file f is hosted in one of the caches connected to the hth user at time t in the physical configuration Y/ = (2().. The mapping 2h may be used to translate any virtual caching policy π virtual { {2 t= to physical caching policy x phy 15(1 ) (yr hea through the correspondence y: (=+), 1 The following lemma relates the regrets incurred by these two online policies:
Lemma 1. For any virtual caching policy π T'imual define a physical caching policy The (
as above. Then the regret of the policy xh is bounded above by that of the policy ninual i.e.
Rr S. RRT
VT
Please refer to Section 10.1 in the supplementary material for the proof of Lemma 1. Lemma 1 implies that any low-regret virtual caching policy may be used design a low-regret physical caching policy using the non-linear mapping 3-()). The key advantage of the virtual caching problem is that a standard OLO problem. Hence, our proposed LeadCache policy, we use an anytime version of the FTPL policy for solving virtual caching problem. The overall LeadCache policy is described below in Algorithm 1:
Algorithm The LeadCache Policy
1: X(0) + 0
2: Sample iid. ~ N(0, 1
3: to 1 to T do
4:
X(t) - X (t-1) +
5:
- (2d(lgg x + Cm
n
6:
(l)) (1) + Y
7:
21 max (1),,))
8: y: - (zz).
9: end for
In Algorithm 1, the flattened Nn x 1 dimensional vector X (t) denotes the cumulative count of the file requests (for each (user, file) tuple), and the vector (t) = (t), s n) denotes the perturbed cumulative file request counts obtained upon adding scaled i.i.d. Gaussian noise vector to (t). is also possible to sample a fresh Gaussian vector 7/2 in step 6 at every time slot, leading to a high probability regret bound [Devroye et al., 2015]. The following Theorem gives upper bound on the regret achieved by LeadCache:
Theorem 1. The expected regret of the LeadCache policy is upper bounded as:
EE (Heaadaach)) S kn 3/4 /144 /
where x Oppoly-og((//)) and the expectation is taken with respect to the random noise added by the policy.
Note that in contrast with the generic regret bound of Suggala and Netrapalli [2020] for non-convex problems, our regret-bound has only logarithmic dependence the ambient dimension N.
5

---

Proof outline:
Our analysis of the LeadCache policy uses the elegant stochastic smoothing frame-
work developed in Abernethy et [2016, 2014], Cohen and Hazan [2015], Lee [2018]. See Section 10.2 of the supplementary material for the proof of Theorem 1.
4.1 Fast approximate implementation
The computationally intensive procedures in Algorithm are (I) solving the optimization problem in step 7 to determine the virtual caching actions and (II) translating the virtual actions back to the physical caching actions in step (8). Since the perturbed vector ( is obtained by adding white Gaussian noise to the cumulative request vector X (1), some of its components could be negative. For maximizing the objective (7), it is clear that if some coefficient (1) is negative for some (i. f) tuple, is feasible and optimal to set the virtual action variable z to zero. Hence, steps (7) and (8) of Algorithm may combined as:
Σ (O)(t)) min (1, Σ $ [EI.JE[
ytt) + arg max yEy
(8)
((0
I(w)
where x² = max(0, x)) Incidentally, we find that problem (8) is mathematically identical to the uncoded Femtocaching problem with known file request probabilities studied by Shanmugam et al. [2013, Section III]. In the same paper, the authors proved the problem (8) to be NP-Hard. The authors also proposed a complex iterative rounding method for the LP relaxation of the problem. where, in each iteration, one needs to compute certain matchings. We now propose two simple linear-time rounding techniques that enjoy the same approximation guarantee.
LP Relaxation: We now introduce new set of variables z min(1, (i v/), Vi, Vi,, and relax the integrality constraints arrive at the following LP:
max (t)
(9)
1
Subject to,
5 Σ Uy [EEI jcar(1)
(10)
N Σ vt sC, YjeJ.
(11)
0 0 s1 $1, f
2 1 VieI,fe[[].
(12)
Denote the objective function for the problem (8) by T.yy and its optimal value (over 2) by OPT. Let y be an optimal solution to the relaxed I.P (9) and Z be the corresponding relaxed feasible
set. Since IP (9) is relaxation (8), it naturally holds that T((y") OPT. To round the resulting cache allocation vector y² to an integral one, we consider the following two rounding schemes (1)
Deterministic Pipage rounding and (2) Randomized sampling-basee rounding.
1. Pipage Rounding: The general framework of Pipage rounding was introduced by Ageev and Sviridenko [2004]. Our rounding technique, given in Algorithm 2, is markedly simpler compared to Algorithm 1 of Shanmugam et al. [2013]. While we round two fractional allocations of single cache time, the rounding procedure of Shanmugam al. [2013] jointly rounds several allocations in multiple caches at the same time by computing matchings in a bipartite graph.
Design:
The key to our deterministic rounding procedure is to consider the following surrogate objective function o( y) instead the original objective L(y) as given in Eqn. (8):
( (00 II (1 (1-)))).
(15)
jEO
Following a standard algebraic argument [Ageev and Sviridenko, 2004, Eqn. (16)), we have:
(a) L(v) 2 d(v)= 2 [ 1- 1 ((y), Vy [0.
(16)

---

Algorithm 2 Cashe-wise Deterministic Pipage rounding
I: y Solution of the LP (9).
2: while y is not integral do
3: Select a cache j with two fractional variables s/y and v//--
4: 6 - min( (v), 11 v/ c2 + min(1 - 1/1 v/yz).
5: Define two new feasible cache-allocation vectors a: B as follows:
a/1 - ,/1 - c1 a², + 5 + and
0 8/, - s +
aj + vÿ. otherwise,
(13)
+2, =2. - v/z - c2, and
BJ + v/. otherwise.
(14)
6: Set y + arg (a. (xx)
7: end while
8: return y.
where A = max (0)(())) Note that inequality (a) holds with equality for all binary vectors y {0, 1] 1pmA Our Pipage rounding procedure, given in Algorithm 2, begins with an optimal solution of the LP (9). Then it iteratively perturbs two fractional variables (if any) in a single cache in such a way that the value of the surrogate objective function dby) never decreases while at least one of the two fractional variables is rounded to an integer. Step (4) ensures that the feasibility is maintained at every step of the roundings. Upon termination (which occurs within O steps), the rounding procedure yields a feasible integral allocation vector y with an objective value L(g), which within a factor of 1 (1 11 of the optimum objective. The following theorem formalizes this claim.
Theorem 2. Algorithm 2 is an a 1 (1 1 -1- approximation algorithm for the problem 8
Note that the Pipage rounding procedure, although effective in practice, is not known to have formal regret bound.
See Section 11 of the supplementary material for the proof of Theorem 2.
An efficient policy for achieving sub-linear a-regret: Since the offline problem (8) NP- Hard, natural follow-up problem is to design a policy with sub-linear a-regret. Recall that a-regret is defined similarly as the usual static regret where the reward accrued by the offline oracle policy (i.e., the first term in Eqn. (2)) is discounted by factor of [Kalai and Vempala, 2005]. Note that directly using the Pipage-rounded solution from Algorithm 2 does not necessarily yield an online policy with sub-linear a-regret [Kakade et al., 2009, Garber, 2021, Hazan et al., 2018, Fujita et al., 2013]. In the following, we give an efficient dffline-to-onling reduction that makes only a single query to linear-time randomized rounding procedure per iteration. In our reduction, the following notion of an a point-wise approximation algorithm [Kalai and Vempala, 2005] plays a pivotal role. Definition 1 (ax point-wise approximation). For feasible set Z in the non-negative orthunt and non-negative input vector x, consider the Integer Linear Program maX x. Let Z 2 Z be a relaxation of the feasible set Z and let z arg maX z x be optimal solution of the relaxed ILP. If for some a > 0, a (randomized) rounding algorithm A returns a feasible solution & Z such that I2,3 azz,, Vi and for any input x, we call the algorithun A an point-wise approximation.
It immediately follows that for any point-wise approximation algorithm for the problem 9, if 2, E Ziel be the relaxed virtual action time t, we have ΣT [[2,]- D, 2 Σi= 2z- Dt, where the inequality follows from the point-wise approximation property. Thus, for any 2 E Z, the a-regret of the virtual policy may be upper bounded as
T Σ
T
T Σ
T
(6) S aB ABB(Rieaden RleaaCacche
T. S a
x
Σx,
21)
(17)
where RleadGacha is an upper bound to the regret of the LeadCache policy with the relaxed actions given by the solution of the LP (9). We bound the quantity E ((eleattCach)) in the following Proposition.
Proposition 1. For an appropriate learning rate sequence (nt) ) 121, the expected regret of the Lead- Cache policy with the relaxed action set End can be bounded as follows:
[0 [( (ileadCache) S KiN 3/4 3///////// dmnCT.
where K₁ is poly-logaiithmic in N and
7

---

See Section 13 of the supplementary materials for a proof sketch of the above result. In the following, we design an a point-wise approximate randomized rounding scheme.
Randomized Rounding via Madow's sampling: The key ingredient to our a point-wise approxi- mation oracle is Madow's ' systematic sampling scheme taken from the statistical sampling literature [Madow et al., 1949]. For a set of feasible inclusion probabilities p on a set of items [NV]. Madow's scheme outputs a subset S of size C such that the hh element is included in the subset S with probability Ps: $ i s N. For this sampling scheme to work, it is necessary and sufficient that the inclusion probability vector p satisfies the following feasibility constraint:
Σ p. C, and 0 S p s Vi [N].
(18)
The pseudocode for Madow's sampling is given in Section 12 in the supplement. Our proposed a point-wise approximate rounding scheme independently samples C' files in each cache in accordance with the inclusion probability given by the fractional allocation vector y obtained from the solution of the relaxed LP (9). From the constraints of the LP, it immediately follows that the inclusion vector y satisfies the feasibility constraint (18); hence the above process is sound. The overall rounding scheme is summarized in Algorithm 3. To show that the resulting rounding scheme satisfies the point-wise approximation property, note that for all i E I and f e [N]:
P(a = 1) = P( V 1 1) (2) 1- (1- (E8
(6) (21)21) 1-ee
vy 1 Enorc
(1) (2) 1- (1 (1- 5E
(E8*(1)
where the equality (a) follows from the fact that rounding in each caches are done independently of each other, the inequality (b) follows from the standard inequality exp(z) 2 1 + z, Vr e IR, the inequality (c) follows from the feasibility constraint (10) of the LP, and finally the inequality (d) follows from the concavity of the function - exp(-x) and the fact that 0 s 2) s 1. Since 2) is binary, it immediately follows that the randomized rounding scheme in Algorithm 3 is an point-wise approximation with a 1-
l/e. We formally state the result in the following Theorem.
Theorem 3. The LeadCache policy, in conjunction with the randomized rounding scheme with Madow's 's sampling (Algorithm 3), achieves an 1- -regrrt bounded by O11314 / /dCT))
Algorithm 3 Randomized Rounding with Madow's 's Sampling Scheme
Input:
Fractional cache allocation (3,,
Output: A rounded allocation (g, &) I: Let y be the output of the LP (9).
2: for each cache jE I do
3: Independently sample S, a set of C files with the probability vector y² using Madow's sampling scheme 4.
4: 8/, -
5: end for
6: 24 + jjeor(i) 8/. I.
7: Return 2))
5 Bounding the Number of Fetches
Fetching files from the remote server to the local caches consumes bandwidth and increases network congestion. Under non-pren con-prfeetchng policies, such as LRU. FIFO, and LFU, a file is fetched if and only if there cache miss. Hence, for these policies, is enough to bound the cache miss rates in order to control the download rate. However, since the LeadCache policy decouples the fetching process from the cache misses, in addition to a small regret, we need to ensure that the number of file fetches remains small as well. We now prove the surprising result that if the file request process satisfies a mild regularity property, the file fetches stop almost surely after a finite time. Note that our result is of a different flavor from the long line of work that minimizes the switching regret under adversarial inputs but yield a much weaker bound on the number of fetches [Mukhopadhyay and Sinha, 2021, Devroye et al.. 2015, Kalai and Vempala, 2005, Geulen al., 2010].
8

---

A. Stochastic Regularity Assumption: Let (t) be the cumulative request- arrival process. We assume that, there exists a set of non-negative numbers {D) such that for any 0:
20 Σ
P( (t) t
Σ [E
p/J 2 26) < co.
(19)
Using the first Borcl-Cantelli Lemma, the regularity assumption A implies that the process (x(() satisfies the strong-law: (0// - p'y. a.s. Vie f [N]. However, the converse may not be true. Nevertheless, the assumption A is quite mild and holds, e.g., when the file request sequence is generated by renewal process having an inter-arrival distribution with finite fourth moment (See Section 15 of the supplementary material for the proof). Define a fetch event F(t) to take place at time slot if the cache configuration at time slot different from that of at time slot t - 1, iee. F(t) == (v(()= y(t 1)). The following is our main result in this section:
(t))
Theorem 4. Under the stochastic regularity assumption A, the file fetches to the caches stop after finite time with probability 1 under the LeadCache policy.
Please refer to Section 14 of the supplementary material for the proof of Theorem 4. This Theorem implicitly assumes that the optimization problems in steps 7 and are solved exactly every time.
Minimax Lower Bound
In this section, we establish a minimax lower bound the regret for the Bipartite Caching problem. Recall that our reward function (1) is non-linear. As such, the standard lower bounds, such as Theorem 5.1 and 5.12 of Orabona [2019], Theorem 5 of Abernethy al. [2008] are insufficient for our purpose. The first regret lower bound for the Bipartite Caching problem was given by Bhattacharjee et al. [2020]. We now strengthen this bound by utilizing results from graph coloring.
Theorem 5 (Regret Lower Bound). For catalog of size N max 2mCC the regret of any
online caching policy n is lower bounded as: R. 2 max (V
MCCT 2
d
O 1
2
VT
Proof outline: We use the standard probabilistic method where the worst-case regret is lower bounded by the average regret over an ensemble of problems. To lower-bound the cumulative reward accrued by the optimal offline policy, we construct an offline static caching configuration, where each user sees different files on each of the connected caches (local exclusivity). This construction effectively linearizes the reward function that can be analyzed using the probabilistic Balls-into- framework and graph coloring theory. See Section 16 of the supplementary material for the proof. Approximation guarantee for LeadCache: Theorem I and Theorem 5, taken together, imply that the LeadCache policy achieves the optimal regret within factor of Ó(min (min((nd)) 1/4 (*/a))/4)). Hence, irrespective of d, the LeadCache policy is regret-optimal up to factor of ((13/8).
7 Experiments
In this section, we compare the performance of the LeadCache policy with standard caching policies.
Baseline policies: Under the LRU policy [Borodin and El- Yaniv, 2005], each cache considers the set of all requested files from its connected users independently of other caches. In the case of a cache-miss, the LRU policy fetches the requested file into the cache while evicting a file that was requested least recently. The LFU policy works similarly to the LRU policy with the exception that, in the case of cache-miss, the policy evicts file that was requested the least number of times among all files currently on the cache. Finally, for the purpose of benchmarking, we also experiment with Belady's 's offline MIN algorithm [Aho et al., 1971], which is optimal in the class of non-po non-pre-feed fetching reactive policies for each individual cache when the entire file request sequence known a priori. Note that Belady's algorithm is not optimal in the network caching setting as does not consider the adjacency relations between the caches and the users. The heuristic multi-cache policy by Bhattacharjee et al. [2020] uses an FTPL strategy for file prefetching while approximating the reward function (1) by linear function.

---

50
ady (offline)
10
LBU
Belady (offine)
LRU
LFU
Nomulized density
30
40
LeadCache-Mann -adoo
LeedCache-Pipsge
Bbattacharjes
[2020]
Nornslized deusity
LeadCacbe-
LeadCache Nadow
Bhattacharjja at al.
10
0.4
0.6
0.5
Average cache hit
Average download per cache
Figure Empirical distributions (a) Cache hit rates and (b) Fetch rates of different caching policies.
In our experiments, we use a publicly available anonymized production trace from large CDN provider available under BSD 2- 2-Clause License [Berger et al., 2018, Berger, 2018]. The trace data consists of three fields, namely, request number, file-id, and file size. In our experiments, construct random Bipartite caching network with 30 users and m 10 caches. Each cache is connected to d = 8 randomly chosen users. Thus, every user is connected to s 2.67 caches average. The storage capacity C of each cache is taken be 10% of the catalog size. We divide the trace consisting of the first ~ 375 K requests into 20 consecutive sub-intervals. File requests are assigned the users sequentially before running the experiments each of the sub-intervals. The code for the experiments is available online [Paria and Sinha, 2021].
Experimental Sctup:
Results and Discussion: Figure 3 shows the performance of different caching policies in terms of the average cache hit rate per file and the average number of file fetches per cache. From the plots, clear that the LeadCache policy, with any its Pipage and Madow rounding variants, outperforms the baseline policies in terms of the cache hit rate. Furthermore. we find that the deterministic Pipage rounding variant empirically outperforms the randomized Madow rounding variant (that has guaranteed sublinear a-regret) in terms of both hit rate and fetch rates. On the flip side, the heuristic policy of Bhattacharjee et [2020] incurs fewer number of file fetches compared to the LeadCache policy. From the plots, it is clear that the LeadCache policy excels by effectively coordinating the caching decisions among different caches and quickly adapting the dynamic file request pattern. Section 17 of the supplementary material gives additional plots for the popularity distribution and the temporal dynamics of the policies for a given file request sequence.
Conclusion and Future Work
In this paper, proposed an efficient network caching policy called LeadCache. We showed that the policy is competitive with the state-of-the-an art caching policies, both theoretically and empirically. We proved lower bound for the achievable regret and established that the number of file-fetches incurred by our policy is finite under reasonable assumptions. Note that LeadCache optimizes the cumulative cache hits without considering fairness among the users. In particular, LeadCache could potentially ignore small subset of users who request unpopular content. A future research direction could be incorporate fairness into the LeadCache policy so that each user incurs small regret [Destounis et al., 2017J. Finally, it will be interesting to design caching policies that enjoy strong guarantees for the regret and the competitive ratio simultaneously [Daniely and Mansour, 2019].
Acknowledgement
This work was partially supported by the grant IND-417880 from Qualcomm, USA, and a research grant from the Govt. India under the loE initiative. The computational work reported on this paper was performed on the AQUA Cluster at the High Performance Computing Environment of IIT Madras. The authors would also like to thank Krishnakumar from IIT Madras for his help with few illustrations appearing the paper.
10

---

References
Wouter M Koolen, Manfred Warmuth, Jyrki Kivinen, et al. Hedging structured concepts. In COLT,
pages 93 93-105. Citeseer, 2010.
Alon Cohen and Tamir Hazan. Following the perturbed leader for online structured learning. In International Conference on Machine Learning, pages 1034-1042, 2015.
Erik Nygren, Ramesh K. Sitaraman, and Jennifer Sun. The akamai network: A platform for high- performance internet applications. SIGOPS Oper. Syst. Rev, 44(3):2-19, August 2010. ISSN 0163- 5980. doi: 10.1 14//1444733..14277777
URL https:tp:///oii org/ 10. 01114/11842753 1842736.
Georgios Paschos, George losifidis, and Giuseppe Caire. Cache optimization models and algo- rithms. Foundations and Trends@ in Communications and Information Theory, 156--4) 2020. ISSN 1567-2190.
doi: 10. 10.116101100001144 URL http: /ttp:///xx.ddo wwt.x.dd..oo////11.. org/10. 1561/
0100000104.
Dan Garber. Efficient online linear optimization with approximation algorithms. Mathemalics of Operations Research, 46(1):204-220, 2021.
Sham M Kakade, Adam Tauman Kalai, and Katrina Ligett. Playing games with approximation algorithms. SIAM Journal on Computing, 19(3):1088-111 2009.
Takahiro Fujita, Kohei Hatano, and Eiji Takimoto. Combinatorial online prediction via metarounding. In International Conference on Algorithmic Learning Theory, pages 68-82. Springer, 2013.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
James Hannan. Approximation bayes risk in repeated play. Contributions the Theory of Games, 3:97-139, 1957.
Jacob Abernethy, Chansoo Lee, and Ambuj Tewari. Perturbation techniques in online learning and optimization. Perturbations, Optimization, and Statistics, page 233, 2016.
Stefano Traverso, Mohamed Ahmed, Michele Garetto, Paolo Giaccone, Emilio Leonardi, and Saverio Niccolini. Temporal locality in today's content caching: why matters and how model it. ACM SIGCOMM Computer Communication Review, 43(5):5-12, 2013.
Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. cambridge university press, 2005.
Benjamin Van Roy. A short proof of optimality for the min cache replacement algorithm. Information processing letters, 102(2-3):72--3. 2007.
Donghee Lee, Jongmoo Choi, Jong-Hun Kim, Sam H Noh, Sang Lyul Min, Yookun Cho, and Chong-Sang Kim. On the existence of spectrum of policies that subsumes the least recently used (Iru) and least frequently used (Ifu) policies. In SIGMETRICS, volume 99, pages 144, Citeseer, 1999.
Asit Dan and Don Towsley. An approximate analysis of the LRU and FIFO buffer replacement schemes, volume 18. ACM, 1990.
Jeffrey Scott Vitter and Padmanabhan Krishnan. Optimal prefetching via data compression. Journal of the ACM (JACM), 43(5):771-795 1996.
P Krishnan and Jeffrey Scott Vitter. Optimal prediction for prefetching in the worst case. SIAM Journal on Computing, (7(6)) 1998.
Amit Daniely and Yishay Mansour. Competitive ratio vs regret minimization: achieving the best of both worlds. In Algorithmic Learning Theory, pages 333-368, 2019.
Nick Littlestone and Manfred Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-266 1994.
11

---

Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-139, 1997.
Karthikeyan Shanmugam, Negin Golrezaei, Alexandros G Dimakis, Andreas F Molisch, and Giuseppe Caire. Femtocaching: Wireless content delivery through distributed caching helpers. IEEE Trunsactions on Information Theory, 59(12)8440284133 2013.
Georgios S Paschos, Apostolos Destounis, Luigi Vigneri, and George Iosifidis. Learning to cache with regrets. In JEEE INFOCOM 2019-IEEE Conference Computer Communications, pages 235-243. IEEE, 2019.
Rajarshi Bhattacharjee, Subhankar Banerjee, and Abhishek Sinha. Fundamental limits on the regret of online network-caching, Proc. ACM Meas. Anal. Comput. Syst., 4(2), June 2020. doi: 10.1145/3392143, URL https:://oi.oon 10. 33921433
Elad Hazan. Introduction to online convex optimization. arXiv preprint arXivv1909.05207, 2019..
Elad Hazan and Edgar Minasyan. Faster projection-free online learning. In Conference Learning Theory, pages 1877-1893. PMLR, 2020.
Alexander A Ageev and Maxim I Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization, 8(3): 307-328, 2004.
Luc Devroye, Gábor Lugosi, and Gergely Neu. Random-walk perturbations for online combinatorial optimization. IEEE Transactions Information Theoory 61(7):4099-411 4106, 2015.
Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In Algorithmii Learning Theory, pages 845-861, 2020.
Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari. Online linear optimization via smoothing. Conference on Learning Theory, pages 807-823 2014.
Chansoo Lee. Analysis of Perturbation Techniques in Online Learning. PhD thesis, 2018
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-307, 2005.
Elad Hazan, Wei Hu, Yuanzhi Li, and Zhiyuan Li. Online improper learning with approximation oracle. arXiv preprint arXiv: 8844077837 2018.
William G Madow et al. On the theory of systematic sampling, ii The Annals of Mathematical Statistics, 20(3):333-354, 1949.
Samrat Mukhopadhyay and Abhishek Sinha. Online caching with optimal switching regret. In 2021 IEEE International Symposium on Information Theory (ISIT), pages 1546-1551 2021. doi: 10.1 119///ITT5117.22211.959999
Sascha Geulen, Berthold Vöcking, and Melanie Winkler. Regret minimization for online buffering problems using the weighted majority algorithm. In COLT, pages 132-143, Citeseer, 2010.
Francesco Orabona. A modern introduction to online learning, arXiv preprint arXiv: 1rXiv:1912.13213 2019.
Jacob Abernethy, Peter L Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games. 2008.
Alfred V Aho, Peter Denning, and Jeffrey D Ullman. Principles of optimal page replacement. Journal of the ACM (JACM), 18(1):80-93, 1971.
Daniel S Berger, Nathan Beckmann, and Mor Harchol-Bales Practical bounds on optimal caching with variable object sizes. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2 2018.
Daniel S Berger. CDN Traces. https: httgtggttubbt//e// httpa///ww..aaeeee////////aaaaaa 2018
12

---

Debjit Paria and Abhishek Sinha. Source code for LeadCache: Pegret-Optimal Caching in Networks. ittps://githus com eet.aaaaaaaaat.ttaaaaaaaaaaaleea -NerIIS21,, 2021.
Apostolos Destounis, Mari Kobayashi, Georgios Paschos, and Asma Ghorbel. Alpha fair coded caching. In 2017 15th International Symposium Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), pages 1-8, IEEE, 2017.
Dimitri Bertsekas. Stochastic optimization problems with nondifferentiable cost functionals. Journal of Optimization Theory and Applications, 12(2):218-25 1973.
Martin J Wainwright, High-dimensional statistics: non-asymptotic viewpoint, volume 48, Cam- bridge University Press, 2019.
Pascal Massart. Concentration inequalities and model selection, volume 6. Springer, 2007.
Sheldon M Ross. Stochastic processes, volume 2. Wiley New York, 1996.
Reinhard Diestel. Graph theory 3rd ed. Graduate texts in mathematics, 173, 2005.
Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2004.
Godfrey Harold Hardy, John Edensor Littlwood, George Pólya, György Pólya, DE Littlewood, et al. Inequalities. Cambridge university press, 1952.
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tüs), 5(4):1-19, 2015.
13


Reviews:
[{"review_id": "ov3dUrxf0a0", "reviewer": "Reviewer_txkX", "summary": "This paper develops online algorithms for a bipartite caching problem. The problem is considered in an adversarial setting and the regret of the proposed algorithm is analyzed. Since the underlying problem is combinatorial, an intermediate step is needed to facilitate the algorithm design and regret analysis. This is done by designing another approximation algorithm with approximation analysis. Also, the regret lower bound of the problem is obtained, which improved the existing regret lower bound that we proposed recently in e Bhattacharjee et al. [2020]. Last, the performance is empirically evaluated using multiple datasets and against multiple traditional and recent regret-based algorithms. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this paper is well-written and well-organized. The technical presentation is clear and easy to follow. The results sound solid and the techniques that are used are different from the most related paper (Bhattacharjee et al. [2020]). It seems that the major technical contributions of the paper are the fast approximation algorithm and the improved regret lower bound. While the problem has been recently getting attention, it seems that the contribution of this paper is clear and substantial in the literature. \n\nThe only concern is how much the results are useful beyond the current problem. It seems that the approximation algorithm is highly utilizing the structure of the problem, in item 2 of Section 3, the authors claim that this is a new technique that could be useful beyond the current setting. But, in the rest of the paper, there are limited insights on why this is the case. \n\nMinor comments:\n\n-- It is better to briefly introduce the k-set problem in Line 27. \n\n-- The cache capacity is fixed and equal to $C$ for all caches. Is it easy to relax this assumption?\n\n-- The third contribution in Lines 148-153 should be states more clearly. The sublinearity in regret typically means that the decision converges to the best static action, leading to zero switching cost. However, the authors in this part claim that with some additional assumptions this happens. In addition, the regret result of the proposed algorithm is missing in Section 3. \n\n-- Line 28, it seems that the policy $\\pi$ is different from the $\\pi$ notation in the lower bound equation. \n\n-- It is true that the optimal offline for the networked caching problem is open, but, it is relatively straightforward to calculate this value when the problem size is small. This is missing in experiments and could help to show how much gap is still there between the proposed algorithm and the offline optimum. \n\n-- Last, it is always good to plot the regret of the algorithm since it shows another aspect of the algorithms on how it evolves over time as compared to the theoretical analysis.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "miQDOzqQeY", "reviewer": "Reviewer_A6cV", "summary": "This paper considers an online bipartite caching problem which has a wide application in practice and therefore has been extensively studied. The problem can be expressed via a bipartite graph in which we have a set of vertices on the left, one for each user, and a set of vertices on the right, one for each cache. There is an edge between user vertex and cache vertex if the user can fetch files from the cache. Each cache has a capacity which upper bounds the number of files that it can store. At each time slot, every user may request at most one file to visit. If such a file is stored in one of the neighbors of the user at the current time slot, the objective function will be rewarded by one, otherwise zero. The algorithm needs to decide which files should be stored in which cache at each time slot to maximize the total benefit. The optimization objective is regret which represents the performance of the online algorithm compared to an offline fixed strategy in the hindsight. Upper bounds and lower bounds are shown with respect to regret based on some coloring argument and a previously developed stochastic smoothing framework. The two bounds seem not matching although the authors claim a \"tightness\".\n\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies a caching decision learning problem to minimize regret. Each individual contribution listed in the main results look good but as a whole didn't solve the problem to an extent sufficient for NIPS.\n\nFor problems of this nature, one would expect that the upper bound and lower bound of the approximation ratio of the regret match each other. However, although the authors claim in abstract and conclusion that some bound is tight, it cannot be seen clearly in the flow of the paper that this is indeed the case. It would be better for the authors to clarify what that tightness means.\n\nUsing transformation from virtual to physical policy looks nice but technically not difficult. Pipage rounding is also kind of standard rounding technique, although using it improves the running of of an earlier work (but the core part inherits that from the earlier work).\n\nSome more detailed comments and typos:\n\n1. It is a bit weird to put the problem formulation in the introduction section which makes the reader almost forget about those definitions when Section 4 Lead Policy starts.\n\n2. Line 44, change \"one-hot\" to \"one-shot\".\n\n3. Line 97, change \"proceeds\" to \"proceed\".\n\n4. Line 137, change \"leads\" to \"leading\".\n\n5. Line 173, delete the first \"be\".\n\n6. Line 189, delete the last \",\".\n\n7. Line 194, this \"d\" is not defined in the main text but used here.\n\n8. Line 478, a subscript t should be added below the last z.\n\n9. Line 487, delete the redundant \"by\".\n\n10. Line 521, delete the redundant \"the\" and change the last \"are\" to \"is\".\n\n11. Line 582, change the first \"that\" to \"the\".\n\n12. Line 630, delete \"of\".\n\n13. Line 646, add \"are\" before \"not\".\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "18"}, "extra_text": {}}, {"review_id": "ZLqI5s7RMR9", "reviewer": "Reviewer_ocxm", "summary": "The paper studies the Bipartite Caching problem, from an online learning perspective. A bipartite graph describes how n users are connected to m caches, each of which supports C files. At each time t, N files are distributed across m caches (same file can be placed in multiple caches), and each user requests one file. Every cache-hit (a user that requests a file in one of its caches) counts as a +1 towards the total reward. The goal is to maximize the reward (or minimize the regret, which is the difference with respect to the reward of an optimal policy).\n\nThe file demands are assumed to be chosen by an \"oblivious\" adversary, which means that the file demands for the entire time horizon T are chosen by an adversary, but a priori (i.e., before seeing the cache allocations).\n\nThe paper proposes a cache allocation algorithm called LeadCache. The algorithm is based on the \"follow the perturbed leader\" policy. In essence, at time t, we aggregate all previous user-file requests until time t-1, add Gaussian noise to them, and then perform the file allocation to caches as if the resulting perturbed vector was the current file demand. The paper builds on previous works that study the problem of Online Linear Optimization and provide regret bounds for \"follow the perturbed leader\" algorithms. However, in order to apply these ideas in the bipartite caching context, several new ideas need to be introduced. In particular, the file allocation for time t is found by first solving a linear relaxation of the combinatorial optimization problem, and then using an interesting rounding algorithm, for which a performance guarantee can be proven.\n\nThe paper provides a careful bound on the regret achieved by LeadCache and shows that it is at most a O(n^(3/8)) factor away from a minimax lower bound. Furthermore, the paper analyzes the number of file fetches needed by LeadCache (i.e., how many times a cache needs to \"download\" a new file) and shows that, interestingly, the file fetches stop after a finite amount of time.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies the interesting problem of caching, which is important from the point of view of cloud computing and content distribution. This problem has received attention from many angles (coding, queueing theory, etc.) and the online learning setting with an adversarial sequence of file demands is an interesting one.\n\nWhile the paper builds on existing works on \"follow the perturbed leader\" policy, several new techniques need to be introduced to use this policy in the bipartite caching setting. In particular, the LP relaxation and the careful rounding to integers are pretty interesting. Furthermore, the regret analysis is fairly nontrivial and leads to a nice near-optimality guarantee. Finally, the result on the file fetching stopping after a while is interesting and the stochastic assumption used to establish it seems reasonable.\n\nOverall, the paper is well written and clear, and I enjoyed reading it. It provides proof sketches and discusses some of the key technical ideas, and presents complete proofs in the appendix. While I didn't go through the proofs in the appendix carefully, I skimmed through them for the main ideas, and found the appendix to also be well written and clear.\n\nThe paper also provides a simulation analysis that compares LeadCache with other cache allocation policies. It shows that LeadCache outperforms classical policies in terms of cache-hit rate and file-fetches per cache. While these results seem to suggest that LeadCache is much better than the state-of-the-art, I think these results may be a bit misleading as these two metrics may not paint the whole picture. I mention more on that below.\n\nMy main concerns with the paper and the significance of the results have to do with the general formulation of the problem. From the point of view of caching for content distribution, it's a bit strange to me that the reward is just a function of the number of cache hits. In practice, if a user has a file demand and it is not met at time t, I would think that the system would have to eventually meet that demand (and all demands would have to be met within some delay). Under the setting in the paper, some users that happen to be in a bad spot in the network (sharing a cache with many other users) or that are requesting unpopular files may never have their demands met, since it may be optimal to \"starve\" some users in order to get cache-hits from other users. Therefore, I think that the regret metric only paints a part of the picture here, and the paper should discuss this.\n\nRelated to the point above, the fact that file-fetches stop after a while is presented as a positive point, but it seems to be a consequence of the objective of minimizing the cache-hit regret. A caching policy that stops changing after a while (once it finds the optimal way to maximize cache-hits) doesn't necessarily feel very practical. I would like to see some of these points discussed in the paper.\n\nSome other comments:\n\n- The proof of Theorem 3 relies on using Borel-Cantelli to show that a certain event E cannot happen infinitely often. The event E, as I understand it, is the event that the policy chosen by LeadCache is suboptimal with respect to the asymptotic file demand probabilities p^i. This implies that after some finite time t, LeadCache must keep picking the optimal policy for (p^i) forever. I'm a bit confused by this. Isn't the problem of finding the optimal cache allocation for a set of demand probabilities (p^i) an NP-hard combinatorial optimization problem? I may be missing something here, but the authors may want to clarify this.\n\n- Algorithm 2, the pipage rounding, seems to assume that while y is not integral, there must be a cache with at least two non-integral variables. I believe this is a consequence of the fact that the sum of the y_{f,j}'s for some cache j must equal C for any optimal solution to the LP. Otherwise, I guess it could be that only one entry is non-integral? I may have missed this, but I didn't see it mentioned.\n\n- I think the fetches weren't defined very formally. While I believe I understand the concept, it may be good to define what a fetch means and when it happens.\n\nMinor issues/typos:\n- line 88: the x_t in the summation should be x_{\\tau}\n- line 122: should the (N choose k)^m be (N choose C)^m? \n- line 139: should \"problem P\" be \"problem $\\psi$\"?\n\n----\n\n**After rebuttal:**\nThe authors addressed my concerns well, and my positive impression of the paper is maintained.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This line of research mainly seeks to improve caching systems. The only negative societal impact could be that the proposed optimal policy seeks to maximize the global reward, potentially at the expense of individual users who happen to request unpopular content. I asked above that the authors discuss potential drawbacks of this problem formulation.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "2RuWVpZ9ZSV", "reviewer": "Reviewer_ZWvx", "summary": "This paper proposed an algorithm for the bipartite caching problem. The proposed algorithm has a follow-the-perturbed-leader (FTPL) flavour. The regret under the policy is proved to be optimal up to constant factors, assuming an adversarial request sequence. Further, it is proved if the request sequence is i.i.d. (or more generally satisfies a law of large numbers type property), then the cache stabilizes in finite time with probability 1. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results are quite strong. The novelty seems to lie in being able to relax the non-linear problem into a linear one, allowing FTPL regret bounded techniques to apply.\n\nOne aspect that I think deserves clarification in the manuscript is the following: The regret guarantee is proved assuming the optimal placement corresponding to Line 7 of Algorithm 1, which is NP-hard. While the authors do establish an approximation guarantee for a rounding technique, it is not clear how using an approximate solution of (7) would impact the regret of Algorithm 1. The authors may not have a clean answer to this, but this `gap' definitely deserves a discussion in the paper.\n\nHowever, in spite of the above, I think the paper makes a notable contribution.\n\n**Update: I thank the authors for the elaborate and comprehensive response. It would indeed be great to introduce the result on \\alpha-regret in the paper (if accepted).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"ethical_concerns": "Not applicable", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall, this is a quality submission. The paper addresses an important problem of interest to the community. They were given new algorithmic and analysis insights into bounding regret for this problem.  The reviewers felt the paper was written well and would be of interest.
Decision: Accept (Poster)