Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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. 
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.

One 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.

However, in spite of the above, I think the paper makes a notable contribution.

**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).
limitations_and_societal_impact: Not applicable
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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".


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.

For 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.

Using 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).

Some more detailed comments and typos:

1. 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.

2. Line 44, change "one-hot" to "one-shot".

3. Line 97, change "proceeds" to "proceed".

4. Line 137, change "leads" to "leading".

5. Line 173, delete the first "be".

6. Line 189, delete the last ",".

7. Line 194, this "d" is not defined in the main text but used here.

8. Line 478, a subscript t should be added below the last z.

9. Line 487, delete the redundant "by".

10. Line 521, delete the redundant "the" and change the last "are" to "is".

11. Line 582, change the first "that" to "the".

12. Line 630, delete "of".

13. Line 646, add "are" before "not".


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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).

The 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).

The 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.

The 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.


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.

While 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.

Overall, 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.

The 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.

My 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.

Related 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.

Some other comments:

- 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.

- 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.

- 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.

Minor issues/typos:
- line 88: the x_t in the summation should be x_{\tau}
- line 122: should the (N choose k)^m be (N choose C)^m? 
- line 139: should "problem P" be "problem $\psi$"?

----

**After rebuttal:**
The authors addressed my concerns well, and my positive impression of the paper is maintained.



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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 

The 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. 

Minor comments:

-- It is better to briefly introduce the k-set problem in Line 27. 

-- The cache capacity is fixed and equal to $C$ for all caches. Is it easy to relax this assumption?

-- 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. 

-- Line 28, it seems that the policy $\pi$ is different from the $\pi$ notation in the lower bound equation. 

-- 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. 

-- 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.  
limitations_and_societal_impact: yes
review_title: null

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)