Online Weighted Paging with Unknown Weights

Summary

This paper considers a generalization of the classical online paging problem. In classical online paging, one needs to maintain a cache of k slots as requests for fetching pages arrive online. If the requested pages are in the cache, there is no charged cost; otherwise, w_p cost will be charged for page p. The goal is to maintain a cache of k slots such that the total fetching cost is minimized. This paper extends this classical setting to the case where the weight of all pages is not known prior to algorithms. Instead, the algorithm needs to sample a value from an unknown distribution, and such a value will be an estimated value of the actual weight. The goal is still to minimize the total fetching cost. The main contribution of this work is an online algorithm that achieves alg$\leq O(\log k)$ opt + $O(\sqrt{nT})$, where k is the size of the cache, n is the number of pages and T is the number requests. The main technique is fractional solution+rounding. To bridge these two phases, the authors design an interface, which aims to learn an estimation of weights for each page.

Strengths

1. The studied problem is well-motivated and it should be interested in the ML community. I expect that the studied problem will have a positive impact on practice. 2. I like the interface idea to bridge the fractional solution and rounding. The main purpose of the interface is to learn the weights. Although all these ideas are not novel, it is interesting to see that a simple combination works well. 3. The paper is well-structured. I appreciate that the authors give a very clear statement for the algorithmic framework in Section 3. This is very helpful for readers.

Weaknesses

There is no lower bound in the paper. The regret bound might be far from tight, but this is expected in the first paper.

Questions

Could you comment on how tight the regret bound O(\sqrt{nT}) is? This seems to be a large number.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

This is a theoretical paper, there is no potential negative societal impact.

Summary

This paper is the first to model and study to the online weighted paging problem with unknown weights. In this model, the weights $w_p$ of pages are initially unknown, and the eviction cost is drawn from an unknown distribution with an expectation equal to $w_p$. This study extends previous research on online weighted paging with unknown weights by integrating concepts from online learning. The authors present an algorithm that achieves the performance bound as follows: $$ E[ALG]\ \leq O(\log k) OPT + \tilde{O}(\sqrt{nT}). $$ Remark that $O(\log k) is the competitive ratio in the known-weight setting. The proposed solution comprises two main components: a fractional algorithm and a rounding framework. The fractional algorithm is designed to approximate the optimal cost, while the rounding framework ensures consistency with the fractional solution through a rebalancing routine. The methodology for the fractional algorithm and the rounding and rebalancing framework are from [Bansal et al. 2010] and [Bansal et al. 2012]. Additionally, the weight estimation utilizes a classical Upper Confidence Bound (UCB) method from the multi-armed bandit problem in online learning. It is a non-trivial combination of the two techniques.

Strengths

This paper presents their motivation for studying the new model clearly, using the example of multi-level cache structure as a compelling rationale. The proposed model is clean, providing a robust foundation that is likely to inspire future research.

Weaknesses

The presentation in section 5 is not clear and may only be reader-friendly to those familiar with it [Bansal et al. 2012]. We may need a high-level idea and some introductions, like anti-cache, before presenting the pseudocode.

Questions

In section 5, the author mentions that they need a more robust rebalancing procedure. What is the detailed difference between it and the previous approach? Can you give some more explanations? It seems that the algorithm runs really slow because of the continuous rebalancing step. Can you remark on the running time of the algorithm?

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

The author does not address the limitations of the proposed algorithm. The efficiency of the algorithm is not considered. Given that the algorithm maintains an exponential number of subsets $S \subset P$ and may adjust some $\mu(S)$ each time an $\epsilon$ fraction of $\mu(S)$ changes, the running time may be quite large.

Summary

The paper addresses the problem of online weighted paging with eviction costs drawn from unknown page-dependent distributions. As evictions occur, the authors demonstrate how to learn an effective eviction strategy online using previous cost samples, framing this as a multi-armed bandit problem. They first approach a fractional relaxation of the problem, then apply a rounding technique to derive a randomized algorithm for the original problem. The resulting algorithm incurs an expected cost of $O(\log k) \cdot \text{OPT} + O(\sqrt{nT})$, where $k$ is the cache size, $n$ is the number of pages, and $T$ is the number of time steps.

Strengths

* The paper is well-written and well-organized. * The setting is both well-motivated and theoretically interesting, as it combines techniques from competitive analysis and regret analysis. * The main result is strong and might inspire future work in the field of online algorithm design.

Weaknesses

I do not see any major weaknesses in this paper, but there are a few minor ones: * Although the setting is different, the paper is closely related to the framework of learning-augmented algorithms. I suggest that the authors mention this connection in the related work section. * A very similar setting has been studied in "On Preemption and Learning in Stochastic Scheduling" (ICML 2023) for the non-clairvoyant scheduling problem, which also couples the analyses of the competitive ratio and regret. Maybe this should be cited as a related work. * While the main contribution is theoretical, it would be nice to conduct a few experiments to demonstrate how the proposed algorithms compare to other benchmark algorithms where the weights are known

Questions

Since the algorithm only chooses which of the $k$ pages in the cache to evict, would it be possible to improve the regret term in Theorem 1.1 and have instead a term of the form $O(\sqrt{f(k,n) T})$, with $k \leq f(k,n) < n$? If not, can you prove that the bound $O(\sqrt{nT})$ is the best possible for any values of $n$ and $k$?

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

The assumptions of the theorems are clearly stated.

Summary

The paper studies a the online paging problem where the weights to retrieve a items are independent random variables with potentially different distributions. The paper introduces an algorithm whose expected performance differ from the optimal one by a multiplicative factor (logarithmic in the size of the cache) and an additive term (sublinear in the number of the requests).

Strengths

If correct, the paper makes a very interesting advance on an important theoretical topic. The authors position well the paper in the existing literature.

Weaknesses

I found this paper the most difficult to evaluate. I feel NeurIPS may not be the most suited venue for such work, both for its theoretical focus (it seems more a STOC-paper) and the 9-page limit which forced the authors to compress much their reasoning. Probably for this reason, as well as some disorganization in the presentation, I was not able to figure out how the algorithm really works as well as to follow some more technical arguments. I provide some specific comments below Doubts - about algorithm 1, what is really behind "continually increase" at line 4, should we assume that that y_p and m_p are updated according to differential equations? This seems to be supported also by later statements like at line 276 "upon any (infinitesimally small) change to a fractional variable" - I was not able to understand the reasoning about why the problem may not exhibit sublinear regret without a competitive ratio (point b at page 2) - in section 1.2, the paper argues that the solution cannot be built in the standard way by combining a solution to the fractional problem and a rounding scheme. I was not able to follow the reasoning in lines 86-94. Even more, because the proposed solution combines a solution to the fractional problem and a rounding scheme - in footnote 2, "note that k \le \sqrt{nT}", I did not get if this follows from the previous reasoning or it is an implicit assumption that T is large enough. - algorithm 2, what does it mean line 9 "add p' to the anti-cache in an \epsilon-measure of states without p'"? If find this kind of expressions too vague. - lines 254-255, there is probably an error, how can be UCB_p between 6^i and 6^{i+1} if, as observed in the same line UCB_p is between 0 and 1? Motivation - I find the motivation in terms of a cache inserted in the a hierarchy of caches quite weak. The content stored at caches of higher level would be determined by the caching decisions at lower levels. It would the not lead to the random weights considered in this paper. Confused presentation - the fact that costs may be considered to be paid upon eviction rather than upon fetching is mentioned in footnote 2 at page 4, but it is already implicitly used at page 2 when explaining why the problem cannot admit logarithmic competitive ratio without regret - the paper starts talking about moving fraction and servers at line 166 before referring to the parallel with the k-server problem - the (huge) caption of figure 1 refers to the "consistency property" and the "subset property". The first one is never really formally defined. The second one is only introduced two page later. - in the caption of figure 2, there is a reference to "class i" but this is only introduced at page 8. Also note that there are two classes i P_i and P_{\ge i} Minor - the problem is sometimes referred to as OWP-UW, others as UW-OWP - line 95: "the and rounding scheme" - footnote 1: "known in advanced" - in the figures the lables of the different subfigures (e.g. a, b, c, d in figure 1 are missing) Update after rebuttal - the authors have addressed some of my technical questions and I have increased the score.

Questions

See questions above.

Rating

4

Confidence

2

Soundness

2

Presentation

2

Contribution

3

Limitations

The computational complexity of the algorithm is not discussed. This is important, in particular if, as I think, the algorithm relies on solving some differential equations.

Summary

Author consider caching with stochastic weights. In particular, the cost incurred by the algorithm at eviction of a page p is drawn independently from a fixed distribution D_p which is different for every page and is not known to the algorithm in advance. Authors propose an algorithm with guarantees which combine both competitive ratio and regret. Authors claim that neither regret nor competitive ratio are possible on their own. Their algorithm is a modification of the classical algorithm by Bansal et al. for weighted paging, incorporating upper and lower confidence bounds on the average weight of the page. The more challenging part seems to be randomized rounding, where they have to deal with the changes of the upper confidence bounds and such element was not present in the original paper of Bansal et al.

Strengths

* Problem seems interesting * Result is non-trivial from technical point of view

Weaknesses

* I find the framing of their result in the context of hierarchical caching and CPU caches very unfortunate for several reasons: (1) hierarchical caching is already studied (see work of Bansal, Buchbinder, Naor SICOMP'12). Authors do not seem to be aware of this. (2) It is completely unclear why should there be an underlying distribution of the cost of loading each page in a hierarchical (or multi-level) cache: It is enough that the algorithm operating on different levels of the cache are mis-aligned in some way to make weights of the pages adversarial instead of stochastic. (3) I cannot imagine implementing anything resembling their approach in CPU caches. * Provided justification of the optimality of the presented results is very informal. It is just a few lines. In particular, authors argue about the necessity of the regret term using using lower bounds for bandits. However, their input is stochastic which allows much better regret bounds when the mean weights of the pages differ significantly. On the other hand, if the weights of the pages are similar, it is easy to achieve good competitive ratio. * Statements of their results are not completely clear: E.g., what is Q in Theorem 1.1? Theorem says it is an "input": Is it composed of the request sequence and the distribution of page weights, or does it contain also the realization of the page weights? What is OPT(Q) then? I do not see these things explained even in preliminaries.

Questions

* Please comment on the last two weaknesses mentioned above.

Rating

4

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

Authors do not discuss possible difficulties in implementing their algorithm in CPU caches although they use such use case as a main motivation.

Please comment on the rebuttal

Dear reviewer qj5j, MmEo and VdxB, Can you please read and comment on the rebuttal from the authors? Please also try to take other reviews and responses into consideration. Regards, Area Chair