Online Weighted Paging with Unknown Weights

We would like to thank the reviewer for the thoughtful comments and encouraging review.

Regarding lower bounds, see the remark in the general rebuttal. In essence, we’ve presented lower bounds for the problem in “Our Results”, which we intend to further formalize in the camera-ready version.

Regarding the regret bound of $O(\sqrt{nT})$, consider the following implications of the lower bounds (a) and (b) that appear in this paragraph (starting at Line 61 in the paper):

1. Lower bound (b) implies that allowing a competitive ratio that is $o(\log k)$, the regret of any algorithm is $\Omega(T/k)$. In particular, for constant k, this implies $\Omega(T)$ regret. Without loss of generality $n\le T$, as pages that are never requested are never loaded into the cache; thus, the regret lower bound is $\Omega(\sqrt{nT})$ in this case.
2. The term $\Omega(\sqrt{T})$ is necessary for any choice of (sublinear) competitive ratio.

We thank the reviewer again for the supportive review and will happily address any further questions.

We thank the reviewer for the thoughtful comments and supportive review.

We take into account the comment regarding the presentation in Section 5. In the final version of the paper, we will edit this section to be more clear and emphasize high-level ideas.

Regarding your question about our rebalancing procedure, this procedure is different from that of Bansal, Buchbinder and Naor [2012] in the following ways:

1. Their procedure had to maintain the balanced property only upon changes to the distribution towards maintaining consistency (e.g., a certain probability mass gaining/losing a page). Our rebalancing procedure must also handle the case in which pages change class due to changes in their UCB (as page classes are not constant in our algorithm).
2. A technical observation: note that the rebalancing procedure fixes the imbalance at every level, in descending order. (The imbalance is the striped area in Figure 2.) However, fixing the imbalance at level $i$ can increase the imbalance at levels $\le i-1$. In BBN, after fixing an imbalance of $x$ at level $i$, the imbalance at levels $\le i-1$ can be seen to be at most $x$. However, in our case, the imbalance at levels $\le i-1$ can be at most $3x$; i.e., the imbalance grows exponentially. This tougher case of cascading imbalance occurs when fixing imbalance due to a page-changing UCB class.

Regarding the mentioned limitation, the rounding scheme does maintain a distribution supported by many cache states (while, of course, holding in actuality a single cache state). To the best of our knowledge, this is true of any known rounding scheme for weighted caching, in particular for that of Bansal, Buchbinder, and Naor [2012]. The focus of this paper was introducing unknown weights to weighted paging, rather than improving the computational tractability of the rounding scheme for known weights; however, we agree with your observation and believe this is a promising direction for future study.

We thank you again for the thoughtful review. We would be happy to discuss any further notes/questions you have. If we’ve properly addressed your concerns, we would be happy if you considered updating your assessment accordingly.

We thank the reviewer for the thoughtful feedback, please see below our comments for the concerns raised.

Regarding (1): “Hierarchical caching is already studied”. Assuming you refer to [1]: this paper studies generalized weighted paging, in which each page has both a weight and a size demand imposed on the cache. Their only reference to storage hierarchies refers to weights (not sizes); thus, we interpret the reviewer’s comment as claiming that our motivating example is captured by standard weighted paging with known weights. To illustrate why this is not the case, note that in standard weighted paging, different pages have different weights, but each specific page has the same weight over time. In our motivating example, this is not the case: the same page can alternate between the main memory (fetching cost 1) and the L2 cache (fetching cost epsilon << 1). This motivates learning a page’s expected fetching cost over time, which is the crux of our model.

Regarding (2): “...why should there be an underlying distribution of the cost of loading each page in a hierarchical cache”. Our goal in this work is to remove the commonly used known-eviction-costs assumption in online weighted paging. Our motivating example refers to the aforementioned cache hierarchy, in which the L2 cache holds pages with probability proportional to their demand by the individual cores; we believe this is a reasonable assumption to make. We agree that the requested computation could in theory “game” the L2 cache; but, we don’t think encapsulating this (arguably somewhat pathological) case would make our motivating example more compelling.

Regarding (3): (a) “I cannot imagine implementing…”. This paper, as previous works in this research field, is theoretical. Our algorithm is not claimed to be practically implementable, which also resembles previous works. The only inefficient component in our algorithm is the rounding scheme, as it performs infinitesimal iterations, similar to the original rounding scheme proposed by Bansal, Buchbinder and Naor (FOCS’ 07). “Justification of the optimality … is very informal”. Our upper bound combines both the element of learning the page weight, which yields a regret term and the element of planning a close-to-optimal eviction strategy, which yields a competitive ratio term. We claimed that each term separately is optimal, and the combination of both is necessary. As you mentioned, our bounds provide a trade-off between the regret caused by the unknown costs and a competitive ratio w.r.t the optimal algorithm that knows the true expected eviction costs.

(b) “What is $Q$ in Theorem 1.1?”. The overwhelming majority of work in randomized online algorithms deals with oblivious adversaries; this is also the case in this work. In particular, the input $Q$ consists of a sequence of $T$ requests for pages, where every page has an associated weight distribution; the oblivious adversary commits to this input. When the algorithm processes input $Q$, upon evicting a page, the algorithm obtains an independent sample from the weight distribution of that page.

We would be happy to elaborate on any issue during the discussion phase. If we’ve addressed your remarks to your satisfaction, we would be happy if you considered revising your merit score accordingly.

[1] "Randomized competitive algorithms for generalized caching", Bansal, Buchbinder & Naor, 2012.

We would like to thank the reviewer for their thorough assessment and comments. Here is our response to the points raised.

Suitability for NeurIPS: we note that theory papers considering online caching/paging have appeared in ML conferences when combined with an ML-related theme. See for example [1,2,3,4,5], which are theory papers that augment caching/paging with ML predictions, and have appeared in ICML. In our case, multi-armed bandits are clearly appropriate for NeurIPS (in fact, they constitute a primary area). Thus, we believe that NeurIPS is the appropriate venue for this paper.

Computational tractability: please see the general rebuttal. In short, the continuous presentation of the algorithm (also chosen for previous work) can easily be replaced with a computationally efficient discrete process.

Regret lower bound: the described construction implies that for every randomized algorithm $ALG$ there exists an input such that $OPT = O(T/(k \log k))$ and $E[ALG]=\Omega(T/k)$. Thus, $E[ALG]-OPT$ (i.e., the regret) is at least $\Omega(T/k)$; that is, the regret grows linearly in $T$. We intend to formalize this further in the camera-ready version; see general rebuttal.

Fractional+rounding framework: The point in Lines 86-94 was that in most algorithms involving fractional+rounding schemes, the integral problem immediately induces a fractional problem, such that the fractional solver is competitive w.r.t. this fractional problem, independently of any “downstream” rounding scheme. This is the case for Bansal, Buchbinder and Naor’s fractional solver for online paging with known weights. But, for unknown weights, no fractional solver can be competitive without learning about page weights – and this is done through sampling pages integrally, which cannot be done by a fractional solver. Thus, the interaction between the fractional solver and the rounding scheme is crucial even for the fractional solver itself to have any competitiveness guarantee. Indeed, one of the main contributions of this paper is devising an interface between the fractional solver and the rounding scheme that enables sampling page weights when needed. Thank you for this input regarding writing clarity, we’ll improve this paragraph in the camera-ready version.

Additional notes:

1. " note that $k \le \sqrt{nT}$": as noted in Line 146 in the preliminaries section, it holds that $k<n$ (otherwise the problem is trivial as all pages can be simultaneously held in the cache). Also, as $n$ is the number of requested pages and thus $n \le T$, it also holds that $k<T$. The observation follows.
2. "add $p'$ to the anti-cache in an \epsilon-measure of states without $p'$": In keeping with previous work on online weighted paging, our randomized algorithm is described as maintaining a distribution over cache states at any point in time; of course, in practice, only a single state is held by the algorithm and is updated as the distribution changes. For example, if the algorithm holds anti-cache state $S$ which has measure $x$ in the distribution, and the distribution is then updated such that $y<x$ measure of state $S$ receives page $p’$, then page $p’$ will be added to the anti-cache state with probability $y/x$ to maintain consistency. While this is consistent with previous work, we agree that this should be made more explicit; we will do so in the camera-ready version.
3. Lines 254-255: there is no mistake here. The classes of values between $0$ and $1$ correspond to non-positive values of $i$.

As for the other remarks regarding writing, thanks for bringing those to our attention; we will modify the paper accordingly for the final version. We hope the above has satisfied your concerns and questions, and that you positively consider increasing your assessment. We, of course, will happily address any further questions you may have.

[1] "Paging with Succinct Predictions", Antoniadis, Boyar, Eliáš, Favrholdt, Hoeksma, Larsen, Polak and Simon, ICML 2023

[2] "Parsimonious Learning-Augmented Caching", Im, Kumar, Petety and Purohit, ICML 2022

[3] "Robust Learning-Augmented Caching: An Experimental Study", Chłędowski, Polak, Szabucki and Żołna, ICML 2021

[4] "Online metric algorithms with untrusted predictions", Antoniadis, Coester, Elias, Polak and Simon, ICML 2020

[5] "Competitive Caching with Machine Learned Advice", Lykouris and Vassilvitskii, ICML 2018

We would like to thank the reviewer for the encouraging review, as well as the thoughtful comments. Please see below our response regarding the weaknesses and questions mentioned.

“… 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.”
Thanks for this remark, we’ll explore the connection between this problem and learning-augmented algorithms in the related work section.

“...it would be nice to conduct a few experiments…”
We’ll consider adding an experimental section towards demonstrating the applicability of the algorithm. We note that in bandit papers that focus on proving regret bounds, experimental sections are usually optional. (Unlike, e.g., learning-augmented online algorithms, where empirical evaluations are customary for ML conferences.)

“Since the algorithm only chooses which of the 𝑘 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 $𝑂(\sqrt{𝑓(𝑘,𝑛)𝑇})$, with $𝑘≤𝑓(𝑘,𝑛)<𝑛$? If not, can you prove that the bound $𝑂(\sqrt{𝑛𝑇})$ is the best possible for any values of 𝑛 and 𝑘?”
As mentioned in the lower bounds described in “our results”, in the regime that allows a competitive ratio of $\Theta(log k))$, there is a lower bound on regret of only $\Omega(\sqrt{T})$. It could be the case that the $\sqrt{n}$ term in our $O(\sqrt{nT})$ regret bound could be improved upon; as this is the first work on this problem, we did not focus on obtaining tight bounds. However, we remark that $\Theta(\sqrt{nT})$ is the optimal regret bound for standard MAB, and we would thus be surprised if a significant gap were obtained for OWP-UW.

We thank you again for your positive assessment and hope the above has satisfied your concerns. We would be happy to address any further questions you may have.