Algorithms for Caching and MTS with reduced number of predictions
Authors: Karim Ahmed Abdel Sadek
Marek Elias
Venue: ICLR 2024 poster (2024)
Keywords: ML-Augmented Algorithms
Caching
Metrical Task Systems
Primary area: learning theory
TL;DR: We present 1-consistent, smooth, and robust algorithm for caching and consistent, smooth and robust algorithm for MTS with limited access to predictor

Abstract: ML-augmented algorithms utilize predictions to achieve performance beyond their worst-case bounds. Producing these predictions might be a costly operation – this motivated Im et al. [2022] to introduce the study of algorithms which use predictions parsimoniously. We design parsimonious algorithms for caching and MTS with action predictions, proposed by Antoniadis et al. [2023], focusing on the parameters of consistency (performance with perfect predictions) and smoothness (dependence of their performance on prediction error). Our algorithm for caching is 1-consistent, robust, and its smoothness deteriorates with decreasing number of available predictions. We propose an algorithm for general MTS whose consistency and smoothness both scale linearly with the decreasing number of predictions. Without restriction on the number of available predictions, both algorithms match the earlier guarantees achieved by Antoniadis et al. [2023].

Published as a conference paper at ICLR 2024
ALGORITHMS FOR CACHING AND MTS WITH REDUCED NUMBER OF PREDICTIONS* *
Karim Abdel Sadek University of Amsterdam
Marek Eliăš
Department Computing Sciences
ka Karim, abdel sadekestudent. uva.nl
Bocconi University
marek. .elk las unibooconi
ABSTRACT
ML-augmented algorithms utilize predictions achieve performance beyond their worst-case bounds. Producing these predictions might be costly operation this motivated [Im et al. (2022) introduce the study of algorithms which use predictions parsimoniously. We design parsimonious algorithms for caching and MTS with action predictions, proposed by (Antoniadis et al. (2023), focusing on the parameters of consistency (performance with perfect predictions) and smoothness (dependence of their performance on the prediction error). Our algorithm for caching is 1-consistent, robust, and its smoothness deteriorates with the decreasing number of available predictions. We propose an algorithm for general MTS whose consistency and smoothness both scale linearly with the decreasing number of predictions. Without the restriction on the number of available predictions, both algorithms match the earlier guarantees achieved by Antoniadis et al. (2023).
INTRODUCTION
Caching, introduced by Sleator and Tarjan (1985), is a fundamental problem in online computation important both in theory and practice. Here, we have a fast memory (cache) which can contain up to k different pages and we receive sequence of requests to pages in an online manner. Whenever page is requested, needs to be loaded in the cache. Therefore, the requested page is already the suffer page faulr: have evict one page
cache, it can be accessed at cost. Otherwise, from the cache and load the requested page its place. The page to evict is to be chosen without knowledge of the future requests and our target is to minimize the total number of page faults.
Caching is a special case Metrical Task Systems introduced by Borodin et al. 1992) as a general- ization of many fundamental online problems. In the beginning, are given metric space M of states which can be interpreted as actions or configurations of some system. We start at predefined state Zg M. At time steps = 1,2,- ..., we receive cost function & M R+ U {0, + and we need to make a decision: either to stay at Tt-1 and pay a cost (x(=;11, or to move to another, possibly cheaper state I; and pay f (z,) + d(I;-1, Tc), where the distance d(I;-1, represents the transition cost between states 2t-1 and Zt-
The online nature of both caching and MTS forces an algorithm make decisions without knowledge of the future which leads to very suboptimal results in the worst case (Borodin et al. 1992] Sleator and Tarjan 1985). recently emerging field of learning- augminne algorithms, introduced seminal papers by Kraska et al. (2188) and Lykouris and Vassilvitskii (202T), investigates approaches to improve the performance algorithms using predictions, possibly generated by some ML model. In general, no guarantee on the accuracy of these predictions is assumed. Therefore, the performance of learning- augmented algorithms is usually evaluated using the following three parameters:
Consistency. Performance with perfect predictions, preferably close optimum.
Robustness. Performance with very bad predictions, preferably no worse than what is achievable by known algorithms which do not utilize predictions.
Full version of this paper can be found Appendix and at htthttsss//ar..v.oott v. wttp:awwwww..rrgr///////////
The presentation of this paper was financially supported by the Amsterdam ELLIS Unit and Qualcomm. Work completed while Abdel Sadek in his final year of BSc Boceoni University

---

Published as a conference paper at ICLR 2024
Smoothness.. Algorithm's performance should deteriorate smoothly with increasing prediction error between the consistency and robustness bound.
These three parameters express desire to design algorithms that work very well when receiving reasonably accurate predictions most of the time and, in the rest of the cases, still satisfy state-of- the-art worst-case guarantees. See the survey by Mitzenmacher and Vassilvitskii (2020) for more information.
Producing predictions is often computationally intensive task, therefore it is interesting to understand the interplay between the number of available predictions and the achievable performance. In their inspiring work, [Im al. 2022) initiated the study of learning- nanningg algorithms which the predictions parsimoniously. In their work, they study caching with next-arrival-in -immetttmmmeetee predictions introduced by Lykouris and Vassilvitskii (2021). Their algorithm uses O(b logs+1 +1 k) OPT predictions. where OPT is the number of page faults incurred by the offline optimal solution and b E N is parameter. It achieves smoothness linear in the prediction error. satisfies tight consistency bounds: with perfect predictions, incurs at most ( k) OPT page faults and no algorithm can do better. In other words, achieves constant competitive ratio with unrestricted access to predictions (b = k) and, with b small constant, its competitive ratio deteriorates to O (log k) which is comparable to the best competitive ratio achievable without predictions. One of their open questions is whether a similar result could be proved for MTS.
In this paper, we study parsimonious algorithms for MTS working with action predictions which were introduced by AAtoniadii et al. (003). Here, each prediction describes the state of an optimal algorithm at the given time step and its error is defined as the distance from the actual state of the optimal algorithm. The total prediction error is the sum of errors of the individual predictions. In the case of caching, action predictions have a very concise representation, see Section 2. Unlike next-arrival-ting time predictions, action predictions can be used for any MTS. Using the method of Blum and Burch (2000), it is easy to achieve near-optimal robustness for any MTS losing only a factor (I+ E) in consistency and smoothness. Therefore, we study how the reduced number of predictions affects the consistency and smoothness parameters. We consider the following two regimes.
Bounded number of predictions: The algorithm can request prediction whenever prefers as far as the total number of requested predictions is bounded by b OPT, where b is parameter. This regime similar to Im et al. (2022).
Well-separated queries to the predictor: The queries to the predictor need to be separated by at least a time steps, for some parameter a. This captures the situation when producing each prediction takes more than one time step.
1 OUR RESULTS
We evaluate the algorithm's performance using competitive ratio which is, roughly speaking, the worst-case ratio between the cost incurred by the algorithm and the cost of the offline optimum, Section[]oor a formal definition. We say that an algorithm achieves consistency a and robustness 3 if its competitive ratio is most a when provided with perfect predictions and at most 3 with arbitrarily bad predictions. For given function g, we call an algorithm -smoohh if its competitive ratio is at most (()) whenever provided with predictions with the total error at most 17.
Our first contribution is an algorithm for caching which receives action predictions describing the states of the optimal offline algorithm Belady proposed by Belady (1966). High quality such predictor based on imitation learning was already designed by Liu et al. (2020). Its empirical evaluation within existing algorithms designed for action predictions was performed by Chledowski et al.) (202T).
Theorem 1.1. Let I be an increasing convex sunetifnntino such that f()) and f(i) S 2 for each i 2 O. There is an algorithm for cuching requiring OOfolg k)) OPT predictions which achieves consistency 1, robustness (log k), and smoothness D(f-'(n/OP) (P/OTT)) where n denotes the total prediction error with respect Belady and OPT is the number of page faults of Belady.
In fact, the number of required predictions is slightly smaller than what is stated in the theorem. Table T shows numbers of predictions and achieved smoothness for some natural choices of f. Already with O(Vk) OPT predictions, our bounds are comparable to Antoniadis et al. (023)) whose algorithm asks for prediction in every step, its consistency constant and its smoothness is logarithmic in
2

---

Published as a conference paper at ICLR 2024
Table 1: Smoothness vs. number of predictions.
f(i)
-
??
i
0
# of predictions
O(vk) OPT 0(1 log( OPT + 1))
Ollog k) OPT O (
Ollog k) OPT O O(OPT) 0 OPT
2 2PPT
smoothness
y. The algorithm also works with f(i) = O. In that case, asks for at most 2 OPT predictions and still remains 1-consistent. However, its smoothness is not very good. We use sliding marking phases and a careful distribution of queries of the predictor over the time horizon. This allows us to avoid dealing with so called "ancient" pages considered by |Rohatgi| (2020) and Antoniadis et al. (2023). resulting in an algorithm with better consistency and a simpler analysis.
We discuss tightness of bounds in Section in the full version of this paper (see Appendix). We show that with, for example, only 0.5OPT available predictions, no algorithm can be better than (log c)competii guarantee comparable the best classical online algorithms without predictions. We also show that the number of predictions used by our algorithm is close to optimal.
Theorem 1.2. Let f be an increasing function. Any f (mnoshhoth algorithm for caching with action predictions, i.e., an algorithm whose competitive ratio with predictions of error yj is (1)) for any " has to least [(In k)) OPT predictions.
For general MTS, we cannot bound the number of used predictions as a function of OPT. The reason is that any instance of MTS can be scaled to make OPT arbitrarily small, allowing us to use only very few predictions. We propose an algorithm which queries the predictor once in every a time steps, making at most T a/a queries in total, where T denotes the length of the input sequence.
Theorem 1.3. There is deterministic algorithm for any MTS which receives a prediction only once per each time steps and its cost is at most ((a) (OFF +2n), where OFF denotes the cost of an arbitrary offline algorithm and n the error of predictions with respect to this algorithm.
This is more general statement than Theorem 1.1 which requires OFF to be Belady. Considering any offline optimal algorithm OFF, Theorem implies smoothness (aa) (1 + 2n/ OPT) and consistency ((a). Our algorithm is based on work functions. For = 1, its smoothness is 1 2n/ OFF, see Section [4 which improves upon the smoothness bound of + 4n/ OFF by
Antoniadis et al. (2023). It is not robust on its own. However, it can be combined with any online
algorithm for the given MTS using the result of Blum and Burch (2000) achieving robustness comparable to that algorithm and losing only a factor of (1 + e) in smoothness and consistency.
No algorithm receiving a prediction only once in a time steps can be o(a)-consistent. This follows from the work of Emek et al. (2009) advice complexity, see Section 7 of the full version (in Appendix) for more details. The same can be shown for smoothness by modifying the lower bound construction of Antoniadis et al. (202)).
Theorem 1.4. There is no o(an/ OPT)-smooth -mooth algorithm for MTS with action predictions which receives predictions only once in time steps.
We can modify our algorithm for caching to ensure that the moments when the predictions are queried are separated by at least a time steps, not losing too much of its performance.
Theorem 1.5. There an algorithm for caching which receives prediction al most once S k time steps and using at most O( (log k)) OPT predictions in total which is O())-consistent, O(log k)- robust and O(f (an/ (PT)) smmooth.
In Section 5
we provide empirical results suggesting that our algorithm's 's performance can be comparable to the performance of algorithms imposing no limitations their use of predictions. Our algorithm may therefore be useful especially with heavy- weight predictors like (Liu et al.) 2020).
In Section 8 of the full version of this paper (see Appendix), provide an algorithm for an alternative prediction setup which we call FitF oracle: each prediction says which the pages in the current algorithms cache will be requested furthest in the future.
3

---

Published as a conference paper at ICLR 2024
1.2 RELATED WORK
The most related work is by Im al. (2022), who studied eaching with next arrival time predictions. smaller number of predictions affects the consistency of their algorithm: with b(log k/ log b) OPT predictions, they achieve consistency (log k/ log b) and they show that this is tight. They also show that their algorithm achieves linear smoothness. In contrast, our algorithm is 1-consistent when receiving least OPT predictions. This demonstrates that action predictions, although not containing more bits, seem to contain useful information about the input instance in more condensed form. See (Antoniadis et al. 2023) for comparison and connections between these prediction setups. Drygala et al. (2023) study ski rental and bahncard problems with predictions of fixed cost.
There are several other papers on eaching with predictions, including (1 (Lykouris and Vassilvitskii 202T] Rohatgi 2020; Wei 2020, [mme et al. 2009 Antoniadis al. [023 [0222 which design algorithms asking for a prediction at each time step. Consistency parameters achieved by these algorithms are constants greater than 1. Note that those using black-box methods to achieve robustness are (1 + e)- consistent (e.g. (Weil 2020)). We can explicitly compare our smoothness bounds to Antoniadis eet al. (2023) who use the same kind of predictions: their smoothness is O(1 log( with unlimttdd use of predictions while our algorithm achieves the same smoothness bound with OVV)) OPT predictions. We compare the smoothness of the other algorithms experimentally in Section 5 Antoniadis et al. (2022) study prediction setup where each prediction only a single bit, however their algorithms need to receive it in every time step. Gupta et al. (2022) study several problems including caching in a setting where each prediction is correct with a constant probability.
OPT PopLoPT: 1))
Antoniadis et al. (203)) proposed a 1-consistent and (1 + 4n/ action predictions which can be robustified by loosing factor (1 e) in consistency and smoothness. Getting smoothness bounds sublinear in n// OPT for specific MTS problems other than caching remains a challenging open problem even with unlimited number of predictions and this holds even for weighted caching. Specific results on weighted caching are by Jiang et (2022) who studied it in a setup requiring very verbose predictions and by Bansal et al. (2022) whose bounds depend on the number of weight classes. There is also consistency/robuttness trade-off by Lindermayr et al. (202)) for k-server.
algorithm for MTS with
Since the seminal papers by Kraska et al. (2118) and Lykouris and Vassilvitskii 2021 which initiated the study of papers ski rental (Purohit al. 2018), secretary problem (Dütting et al. (021), online TSP 2020). flow-time scheduling (Azar
algorithms, many computational problems were considered. There
(Bernardini et al. 2022). energy efficient scheduling (Bamas et al.
al.] [021 (022), ) and online page migration (Indyk et al.) | (0222). Further related works can be found
in References and are discussed in the full version of this paper (see Appendix).
2 PRELIMINARIES
Consider an algorithm ALG for MTS which produces solution To. F1.... 2T for an instance I consisting of cost functions ......, ST. We say that ALG is r-competitive with respect to an offline algorithm OFF there an absolute constant a E I such that E/cost Crcost(ALCC) (ALG(T)) < r cost(OFF + for any instance I. If ALG is r-competitive with respect to an optimal offline algorithm, we say that ALG is r-competitive and call the competitive ratio of ALG. In the classical setting (without predictions), the best achievable competitive ratios are @logg k) for caching (Fiat et al. 1991) and of order poly log n for MTS (Bartal ett al.) 2006 Bubeck et al. 2019), where is the number of points in the underlying metric space M. We refer to Borodii and El- Yaniv 1998) for a textbook treatment.
.......,7
We denote cost (ALGG()) Σ (Ex(2) +
2.1 ACTION PREDICTIONS FOR MTS
Antoniadis et al. (203) proposed a prediction setup which they call action predictions, where the predictions tell us what a good algorithm would do. More precisely, at each time t, the algorithm receives a prediction pt of a state where some offline algorithm OFF moves to at time t. The error of prediction is then = d(pt, 0t), where o, is the real state of OFF at time t. The total prediction
emror is defined as 7) Σ 1==10 1/.
4

---

Published as a conference paper at ICLR 2024
Considering the case of caching, the state corresponds to cache content, and the prediction error is the number of pages present in the cache of OFF and absent from the predicted cache content. A whole cache content may seem like a huge piece of information, but action predictions for caching can be implemented in a very succinct way. Antoniadis et al. (2023) explain how to represent them with only Ollo k) bits per time step when they received at each time step. Our algorithm asks, in each query, specific number of indices of pages which are present in its cache but absent from the predicted cache. When we talk about bound on the number of provided predictions, this bound applies both to the number of such queries as well as to the total number of indices reported by the predictor during the running time of the algorithm. There are predictors which can generate predictions of a similar kind by Jain and Lin (2016); Shi et al. (2019); Liu et al. (2020). See (Antoniadis et al. (0023) for a detailed treatment of this prediction setup and a comparison to other setups for caching.
2.2 CACHING: BELADY'S S ALGORITHM, MARKING, AND LAZY ALGORITHMS
The classical optimal offline algorithm for caching proposed by Belady 1966) is denoted Belady in this paper. At each page fault, it evicts a page which is going to be requested furthest in the future. In the case of a tie, i.c., if there are several pages in the cache which will not be requested anymore, it chooses one of them arbitrarily. Our caching algorithm assumes that the predictor is trying to simulate Belady. The following useful property allows us to detect errors in the predictions quickly. It was recently used by Eliás al. (2024).
Observation 2.1. Consider request sequence , PT. . For any / S T, the cost incurred by Belady for r1.............................. PT until time the same as the cost of Belady with input r'.
To see this, it is enough to note that the solution produced by Belady with input ri,-.. 'r agrees until time / with the solution produced by Belady r'....,?'s which breaks ties based the arrival times in Te+1...., PT.
We use properties of marking algorithms in this work. Such algorithms split the input sequence into phases, i.e., maximal subsequences where at most k distinct pages are requested. Usually, the first phase starts in the beginning and the next phase follows just after the end of the previous one. However, we will consider phases starting at arbitrary moments. Let O be the cache content of an algorithm in the beginning of the phase. Whenever a page is requested for the first time during the phase, we call this moment an arrival and we mark the page. At the end of the phase, the set M of marked pages will have size ke some of them belong to and are called old while those in MM O are called clean. Exactly |C| pages from O remain unmarked until the end of the phase.
Marking algorithms is a class of algorithms which never evict a marked page and all of them have cache content M at the end of the phase. Belady is not marking and our algorithm is not marking either, although it uses ideas from marking to achieve desired robustness and smoothness properties. At the end of each phase, can bound the difference between the cache content of some algorithm and marking.
Observation 2.2. Let be the cost incurred by some algorithm during marking phase. Then, 2 |M \ S), where S is the cache content of the algorithm at the end of the phase and M is the set of l pages requested during the phase.
This is because each page in p E M has to be present in algorithm's 's cache when requested during the phase. If p & S. then the algorithm must have evicted it during the phase incurring cost 1. Observation 2.3. If a page p is evicted by Belady at time f, then is not going to be requested in the marking phase containing t anymore.
If p is evicted by Belady at time f, then the currently requested page r; and 1 pages from the cache are i distinct pages that are requested before the moment when p is requested next time. The current phase then needs to end before that moment.
We say that algorithm is lazy if it evicts only one page at time and only at page fault. Belady is lazy while our algorithm, as described, may not be. However, any algorithm can be made lazy without increasing its cost. See (Borodin and Yanivy 1998) for more information about caching.
Observation 2.4. The difference in the cache content of two lazy algorithms can increase only both of them have page fault. In that case, it can increase by at most 1.
5

---

Published as a conference paper at ICLR 2024
3 BOUNDED NUMBER OF PREDICTIONS
In this section, we prove Theorem I.1 We propose an algorithm called F&R which consists of two parts: Follower and Robust. It starts with Follower which is 1-consistent, but lacks in smoothness and robustness. each page fault, Follower recomputes Belady for the part of the sequence seen so far and checks whether it also has a page fault. If yes, it copies the behavior of the predictor (Line B) Otherwise. it must have received an incorrect prediction before. Therefore, it switches to Robust (Line 5) which is more 1-consistent, but achieves desired smoothness and robustness. Robust runs for one marking phase and then returns back to Follower. At such moment, the predictor's 's and the algorithm's 's cache can be very different and Follower may need to lazily synchronize with the predictor (Line
Algorithm 1: Follower
P ;= initial cache content;
// Prediction for time
foreach pagefault do
rt E P and Belady has a pagefault then query new prediction P and evict any p E C\ else r, E P then evict arbitrary p & P:
else Switch to Robust (Algorithm 2;
Algorithm Robust, runs during single marking phase starting at the same moment, splitting it into windows as follows (assuming k is a power of 2): The first window W1 starts at the beginning of the phase and lasts k/2 arrivals, i.e., it ends just before the arrival number k/2 1. W, follows the W and its length is half of the remaining arrivals in the phase. The last window Wlog k+1 {k} lasts until the end of the phase. Robust comes with an increasing convex function such that f(0) = and f(i) < 2 1. Faster growing f does not further improve our smoothness bounds. Function determines that we should request fi) f(i - 1) predictions in window small, we ask for prediction at each time step. Robust starts with the cache content of a marking algorithm whose new phase would start at the same moment (Line [p. In the case of a page fault, evicts unmarked page chosen uniformly at random. At arrivals belonging to the sets S and F, it performs synchronization with the predictor and queries the predictor's ' state respectively. The synchronization is always performed with respect to the most recent prediction P which, in the case of lazy (or lazified) predictors, implicitly incorporates information from the previous predictions.
the window is too
Algorithm 2: Robust, / (one phase)
Load distinct most recently requested pages; S := [k- 2 + 1 | j = log .,, 0}:
W; : [A: 2logh- + 1, k 21og k- for I,,...,,ee, log ls and Vog k+1 = (k) 1), [. for each ;;
Choose F C (1.... k} such that |FnW, =i) min
S(i
5 foreach pagefault during the phase do
if it is arrival belonging to F then ask for new prediction P: if it is arrival belonging to S then synchronize with P; if requested page is still not in cache then evict random unmarked page;
Load all pages marked during the phase;
10 Switch to Follower (Algorithm)
Synchronization with P (Line works follows. All pages previously evicted by random evictions return to the cache and the same number of pages not present in P is evicted. We denote F,g ET U F the set of pages evicted the beginning of W,, where pages in F. are requested during W: while those in E are not. Note that algorithm's 's and predictor's cache may not become the same after the synchronization. Since the algorithm starts with pages in M and loads only clean pages, we have the following observation.
Observation 3.1. Let C,. [C,] = c; be the set of clean pages arriving before the start of W,. Then, F, C M U C2 and E. M U C k= Ct

---

Published as a conference paper at ICLR 2024
We assume that the predictor is lazy and does not load pages that not requested. Therefore, page from E will be loaded during We by the predictor and the same holds for Robust, implying the following.
Observation 3.2. For every = 1..... log k. we have E S Es-1 and therefore E, Ei+1 C E,
Synchronization with the marking cache performed by Robust is to ensure that the difference between the cache of the algorithm and Belady can be bounded by costs incurred by Belady locally using Observation 2.2 instead of diverging over time solely due to incorrect predictions.
Implementation suggestions. Algorithms are described as simplify the analysis. Synchronization in Robust (line should be done lazily as to make use of the most recent prediction. At arrivals of clean pages, one may evict page not present in predictor's 's cache instead of random unmarked page; one can also ask for a fresh prediction (at most 2 2OPT additional queries). The second synchronization with the marking cache in Robust (line can be omitted. With f(i) = O, one can query the predictor only at clean arrivals, using at most 2OPT predictions total. We recommend lazy implementation. Since Robust is not 1-consistent, one may also switch from Follower only once Follower's 's cost is at least constant (e.g. 2 or 3) times higher than the cost of Belady.
We denote H, the ith phase of Robust, and H a hypothetical marking phase which ends just before H4 starts. Note that H; might overlap with H; But H1, H2.... are disjoint and we denote G4 the time interval between the end of H, and the beginning of H441. c(Hq is the number of clean pages during phase H;. For a given time period X, we define (X),,, A (X).. and (X) the costs incurred by F&R, Belady, and the predictor respectively during X and n)X) the error of predictions received during X.
Here is the main lemma about the performance of Robust. Overview of its proof is deferred to Section 3.1
Lemma 3.3. Denote X; H UH, U H, During the phase He, Robust, receives at most flog kt) + predictions and we have
17 HH(H))
E[A)(H,) 0(1)
A (X,).
(1)
A (X.))
At the same time, we also have
EIA (H.)) - Ollog k) " (X.) and
(2)
A (H.) S O(k) + (H.))
(3)
The following lemma is useful to analyze the cost incurred during the Follower part of the algorithm. The proof of Theorem 1.I then combines it with with Lemma 3.3 and can be found in the full version of the paper. Lemma 3.4. Consider the gap Gis+1 between phases H, and H,-1 of Robusty. We have AA & A A + (H,,)
3.1 ANALYSIS OF Robust,
The full version of this section and the proof of Lemma 3.3 can be found in Appendix (Section 3.2). here we include a short overview. Charging a page fault on a page evicted due to predictor's advice to single incorrect action prediction can only give us smoothness linear in the prediction error. This is in contrast with next-arrival predictions where algorithms can be analyzed by estimating lengths of eviction chains caused by each incorrect prediction, as proposed by Lykouris and Vassilvitskil need to charge each such page fault to long interval of
(202T). To achieve sublinear smoothness, incorrect predictions. This is the most challenging part of our analysis because Belady also moves and the same prediction incorrect one time step may be correct at another time step. We estimate the error of predictions received during each window by introducing window rank which bounds the prediction error from below accounting for the movements of Belady.
4 WELL-SEPARATED QUERIES TO THE PREDICTOR
The full version of this section, which can be found in Appendix, contains a consistent and smooth algorithm for MTS proving Theorem 1.3 and extends analysis of F&R to the setting where the
7

---

Published as a conference paper at ICLR 2024
queries to the predictor need to be separated by at least time proving Theorem L.5 In MTS, the cost functions usually do not satisfy any Lipschitz property. Therefore, the difference between the cost of the state reported by the predictor and the state of the optimal algorithm does not need to be proportional to their distance. We show that a state satisfying this property which is close to the predicted state can be found using a classical technique for design of algorithms for MTS called work functions, see (Chrobak and Larmore 1996) for reference. Then, we use the approach of Emek et al. (2009) to interpolate between predictions received at times and ++ a. In the case of caching, the performance of F&R in this regime is the same as if it has received a incorrect predictions for each prediction error. Therefore, 77 in its smoothness bound needs to be multiplied by a.
EXPERIMENTS
We perform an empirical evaluation of our caching algorithm F&R on the same datasets and with the same predictors as the previous works (Lykouris and Vassilvitskii 2021; Antoniadis et al. 2023 Im
al. 2022).
We use the following datasets.
BrightKite dataset (Cho al. 2011) contains data from certain social network. We create a separate caching instance from the data of each user, interpreting check-in locations as pages. We use it with cache size 10 and choose instances corresponding to the first 100 users with the longest check-in sequences requiring at least 50 page faults in the optimal policy.
CitiBike dataset contains data about bike trips in bike sharing platform CitiBike We create a caching instance from each month in 2017, interpreting starting stations of the trips as pages, and trimming length of each instance to 25 000. We use with cache size k 100.
Some of the algorithms in our comparison use next-arrival predictions while F&R uses action predictions that can be generated from next-arrival predictions. Therefore, we use predictors which predict the next arrival of the requested page and convert it to action predictions. This process was used and described by Antoniadis et al. (2023) and we use their implementation of the predictors. Our algorithm then provided limited access to the resulting action predictions while the algorithm of Im et al. (2022) has limited access to the original next-arrival predictions.
Synthetic predictions: compute the exact next arrival time computed from the data and add noise to this number. This noise comes from a log-normal distribution with the mean parameter μ = O and the standard deviation parameter a. We use E [0, 50).
PLECO predictor proposed by Anderson et al. (0114): This model estimates the probability p of a page being requested in the next time step and we interpret this as a prediction that the next arrival of this page will be in 1/p time steps. The model parameters were fitted to BrightKite dataset and not adjusted before use on CitiBike.
POPU a simple predictor used by Antoniadis et al. (2023): if page appeared in p fraction of the previous requests, we predict its next arrival in 1/p time steps.
In our comparison, we include the following algorithms: offline algorithm Belady which we use to compute the optimal number of page faults OPT, standard online algorithms LRU and Marker (Fiat ct al. 1991). ML-augmented algorithms using next arrival predictions L&V (Lykouris and Vassilvit- skii 2021p. LMark and LnonMark (Rohatgi 2020). FtPM which, each step, evicts an unmarked page with the furthest predicted next arrival time, and algorithms for action predictions FtP and T&D (Antoniadis et al.) 2023). We use the implementation of all these algorithms published by Antoniadis et al. (2023). We implement algorithm AQ (Im et al. 2022) and our algorithm F&R.
Notes on implementation of F&R. We follow the recommendations in Section except that Follower switches to Robust whenever its cost is = 1 times higher compared to Belady in the same period. With higher a, the performance With k 10 (BrightKite dataset), we use F = [1, 6, 9] corresponding to f(i) i. Note that, with such small k. polynomial and exponential f would also give a very similar F. With & = 100 (CitiBike dataset), we exponential f(i) 2 - 1. With a-separated queries, Follower uses LRU heuristic when prediction is unavailable, and Robust ignores F, querying the predictor at each page fault separated from the previous query by least a time steps.
F&R approaches FIP on the considered datasets.
8

---

Published as a conference paper at ICLR 2024
Number of queries to the predictor
45000
1.30
400000
Competitive ratio
35000
1.20
LRU
1.15
Marker
30000
FIP
1.10
AQ
FPM
RIPM
25000
AQ_b2
1.05
T&D
T&D
1.00
F&
20000
40
20
50
Noise parameter a of the synthetic predictor
Noise parameter a of the synthetic predictor
Figure I: BrightKite dataset with Synthetic predictor, standard deviation at most 0.003 and 300 resp.
Predictor
Marker
FtP
AQ_b8
FtPM_al
FtPM_a5
F&R_al
F&R_a5
F&R_a20
POPU 1.861
1.739
1.782 1.875
1.776 1.877
1.833 1.867
1.800 1.878
1.802 1.879
1.803
PLECO
1.861
2.277
1.879
Figure 2: Competitive ratios CitiBike dataset with & 100, standard deviation at most 0.001
Results. Figures [ and contain averages of 10 independent experiments. Figure shows that the performance of F&R with high-quality predictions is superior to the previous Mi.-augmented algorithms except for FtP which follows the predictions blindly and is also 1-consistent. With high a, the performance of T&D becomes better. This is true also for F&R with F [1..10], suggesting that T&D might be more efficient using erroneous predictions. The second plot shows the total number of times algorithms query the predictor over all instances. Response to such query is single page missing from predictor's 's cache in the case of F&R and T&D and next arrival times of pages in the case of AQ_b. Note that FtPM equivalent the non-parsimonious version of AQ with k. F&R makes the smallest number of queries: with perfect predictions, it makes exactly OPT queries and this number decreases with higher as F&R spends more time in Robust.
Figure 2 shows that F&R performs well in the regime with a-separated queries. While the perfor- mance FiPM with POPU predictor worsens considerably towards Marker already with F&R keeps its improvement over Marker even with a 20. Predictions produced by PLECO seem much less precise as suggested by FtP with PLECO being worse than Marker and smaller number of such predictions either improves (AQ, FtPM) or does not affect performance (F &R) of considered algorithms. Further details of our experimental results are presented in Appendix (Section 5).
CONCLUSIONS
We present algorithms for MTS and caching with action predictions working in the setting where the number of queries or the frequency of querying the predictor are limited. We have shown that one can achieve theoretical well empirical performance comparable the setting with unlimited access to the predictor, possibly enabling usage of precise but heavy-weight prediction models in environments with scarce computational resources.
REPRODUCIBILITY STATEMENT
The appendix contains a full version of paper which includes proof of all the theorems and lemmas. We provide textual description the implementation of our algorithm in Section The code of our implementation can be found at athtttss://ithhu. http:hhwww..ccmmmceeeeeeeeeeeeee
-tt http/cchhnn///

---

Published as a conference paper at ICLR 2024
REFERENCES
[1] A. Anderson, R. Kumar, A. Tomkins, and S. Vassilvitskii. The dynamics of repeat consumption.
In Proceedings of conference World Wide Web 14, pages 430, 2014. doi: 10.1145/2566486. 25560188.
[2] A. Antoniadis, Gouleakis, Kleer, and P. Kolev. Secretary and online matching problems with machine learned advice. In NeurIPS, 2020.
[3 A. Antoniadis, C. Coester, M. Eliáš, A. Polak, and B. Simon. Learning- seaeminn-augmentee dynamic power management with multiple states via new ski rental bounds. In NewrlPS, 2021.
[4] A. Antoniadis, J. Boyar, M. Fliák, L. M. Favrholdr, R. Hoeksma, K. S. Larsen, A. Polak, and
B. Simon. Paging with succinct predictions, 2022.
[5] A. Antoniadis, P. J. Ganje, and G. Shahkarami. A novel prediction setup for online speed- scaling. In SWAT, volume 227 of L.Ples, pages 9:1-9:20. Schloss Dagstuhl Leibniz-Zentrrm für Informatik, 2022.
[6] A. Antoniadis, C. Coester, M. Eliáš, A. Polak, and B. Simon. Online metric algorithms with untrusted predictions, ACM Trans. Algorithmss, 19(2). apr 2023, ISSN 1549-6325. doi: 10.1145/358268, URL /ttt:/:://o...ogg11..... 11..11..11133310
[7] Y. Azar, S. Leonardi, and N. Touitou. Flow time scheduling with uncertain processing time. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, STOC 2021, page 1070-1080, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 4503480385 doi: 10.1445330063553555033. URL ltttps:/
1145/340632 34511132222445222 3451023
[8] Y. Azar, S. Leonardi, and N. Touitou. Distortion-oblivvoos algorithms for minimizing flow time. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithmss, SODA 2022, Virtual Conference / Alexandria, VA, USA, Jamuary 9 12, 2022, pages 252-274. SIAM, 2022. Utthttps: /ettps://doi... http://ooooooggg//// wttp://///.................o 0T111117717111199777977717779 1177166119777.1111
[9] É. Bamas, A. Maggiori, L. Rohwedder, and O. Svensson. Learning augmented energy mini- mization via speed scaling. In NeurlPS, 2020.
[10] N. Bansal, C. Coester, R. Kumar, M. Purohit, and E, Vee. Leamnng--uggmente weighted paging. In SODA, 2022.
[11] Y. Bartal, B. Bollobás, and M. Mendel. Ramsey-type theorems for metric spaces with applica- tions to online problems. Comput. Syst. Sci., 72(5):890-922 2006.
[12] I.. A. Belady. A study of replacement algorithms for virtual-storrage compute. IBM Syst. J. (2):78-10) 1966. doi: 10. 00.1147/sj.22.0078 URL httpp:://dbi..rg///// 1144/////1/111111......1
0078
[13] G. Bernardini, A. Lindermayr, A. Marchhetti-paaccamt N. Megow, L. Stougie, and M. Sweer- ing. A universal error measure for input predictions applied to online graph problems. CoRR, abs/2205. 28500, 2022. doi: 10.485500arX1v.2255.1r 12850. URL
18550/arXiv.. www.aiwwww........... 12850
[14] A. Blum and C. Burch. On-line learning and the metrical task system problem. Mach. Learn., 39(1)335-5, 2000. doi: 10. 100112//A:100621182202
[15] H. Böckenhauer, D. Komm, R. Královič, R. Královič, and T. Mömke. Online algorithms with advice: The tape model. Inf. Comput., 254:59-83, -3, 2017.
[16] A. Borodin and R. El- VanYa. Online computation and competitive analysis. Cambridge University Press, 1998. ISBN 978-0-521-56692-5.
[17] A. Borodin, N. Linial, and M. E. Saks. An optimal on-line algorithm for metrical task system. J. ACM, 39(4)7745-763, 1992. doi:
10

---

Published as a conference paper at ICLR 2024
[18] J. Boyar, L. M. Favrholdt, C. Kudahl, K. S. Larsen, and J. W. Mikkelsen. Online Algorithms with Advice: A Survey. ACM Computing Surveys, 50(2):1-34, 2017. Article No. 19.
[19] Boyar, L. M. Favrholdt, and K. S. Larsen. Online unit profit knapsack with untrusted predictions. In SWAT. volume 227 of LIPlcs, pages 20:1-20: Schloss Dagstuhl Leibniz- Zentrum für Informatik, 2022.
[20] S. Bubeck, M. B. Cohen, J. R. Lee, and Y. T. Lee. Metrical task systems on trees via mirror descent and unfair gluing. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 89-97, 2019. doi: 10. 10.1137/1.78116119754222 URL
https: //c::///ooo. www.oorg/....o..... 1131/11111 90816178111111 11w.611999552.66
[21] Chen, S. Silwal, A. Vakilian, and F. Zhang. Faster fundamental graph algorithms via learned predictions. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 3583- -6022. PMLR, 17-23 Jul 2022. httpttttt///pooeeeee
ml wttpmm.tt.....///////m chen22v www.hhhhnnnnmmmmll....
[22] J. Chledowski, A. Polak, B. Szabucki, and K. T. Zolna. Robust tearning-augmenter caching: An experimental study. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 1930. PMLR, 2021. htL Approceedings.. ml
htmm
[23] E. Cho, S. A. Myers, and social networks. In oftpreediinnosSSlllDDDD///..ppp 1082 2011. doi: 10. 145124220. 2020579. URL http:pppe//aagg..ccacfrrrdeeedda
Leskovee. Lekkoee. and user movement in location-
bri http://ooooorrogtttttcc
.ttll
[24] M. Chrobak and L. L. Larmore. Metrical task systems, the server problem and the work function algorithm. In Online Algorithms, The State of the Art, pages 74-96, 1996.
[25] CitiBike, Citi bike trip
[26] M. Dinitz, S. Im, T. Lavastida, B. Moseley, and S. Vassilvitskii. Faster matchings via learned duals. NeurIPS, pages 10393-10406, 2021.
[27] S. Dobrev, R. Královič, and Pardubská. Measuring the problem-relevant information in input. RAIRO Theor. Inf. Appl., 43(3):585-613, 2009.
[28] M. Drygala, S. G. Nagarajan, and O. Svensson. Online algorithms with costly predic- tions. In F. Ruiz, J. Dy, and J.-W. van de Meent, editors, Proceedings of The 26th In- ternational Conference on Artificial Intelligence and Stutistics, volume 206 of Proceed- ings of Machine Learning Research, pages 8078-8101. PMLR, 25-27 Apr 2023. URL html
https: http::://proceecinngg. wwwpesiiinnsm......mmmmmmemmm hww....peees//22/ddyyaa...e
[29] Dütting, S. Lattanzi, R. P. Leme, and S. Vassilvitskii. Secretaries with advice. In EC,, pages 409-429. ACM, 2021.
[30] Eberle, A. Lindermayr, N. Megow, L. Nölke, and Schlöter. Robustification of online graph exploration methods. In AAAI, pages 9732-9740. AAAI Press, 2022.
[31] M. Eliás, H. Kaplan, Y. Mansour, and S. Moran. Leannnn-augmmented algorithms with explicit predictors, 2024. URL htttttttp////att http://wwww....////////////.//..
[32] Y. Emek, P. Fraigniaud, A. Korman, and A. Rosén. Online computation with advice. In Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Proceedings, Part I. volume 5555 of Lecture Notes in Computer Science, pages 427-438 Springer, 2009. URL
https::/doi... .oroooooorrr/o/oooooo 10000000000000 322-2222222227
36
[33] J. C. Ergun, Z. Feng. S. Silwal, D. P. Woodruff, and S. Zhou. Learning augmented k-means clustering. In The Tenth International Conference on Learning Representations, ICLR 2022. OpenReview.net, 2022. URL htttts://openeev//// httt://oooromm..ooocc....eee

---

Published as a conference paper at ICLR 2024
[34] A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, and N. E. Young. Competitive paging algorithms. Journal of Algorithms, 12(4))685 699, 1991. ISSN 0196-6774. doi:
URL htw.Lttps:.. www www.ssseeinnereert.t.t..
90041V
[35] A. Gupta, D. Panigrahi, B. Subercaseaux, and K. Sun. Augmenting online algo- rithms with curepsilon-accuraal predictions. In S. Koyejo. S. Mohamed, A. Agar- wal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 2115-2127. Curran Associates, Inc., 2022. URL https:::/pppcceeeeeeeeece ngs neurips ec http//pper_ffle/peeeeeeeeeeeeeee wwwes//aper///////eeepp/aaappaat /20////222////e//////////// 0ea008312aa8122221111eeebb wwtp:riippppppppppp..pppppp
Paper Conference,
[36] J. Hromkovič, R. Královič, and R. Královič. Information complexity of online problems. In MFCS, volume 6281 of LNCS, pages 24-36. Springer, 2010.
[37] S. Im, R. Kumar, M. M. Qaem, and M. Purohit. Online knapsack with frequency predictions. In NeurlPS, pages 2733-2743, 2021.
[38] S. Im, R. Kumar, A. Petety, and M. Purohit. Parsimonious serming-augmenter caching. In ICML, 2022.
[39] P. Indyk, F. Mallmann-Thenn, S. Mitrovic, and R. Rubinfeld. Online page migration with ml advice. In G. Camps-Vale Valls, F. J. R. Ruiz, and Valera, editors, Proceedings of The 25th International Conference Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 1655-1670, PMLR, 28-30 Mar 2022. URL https #/proceedings mlr www.s
[40] A. Jain and C. Lin. Back to the future: Leveraging belady's 's algorithm for improved cache replacement. SIGARCH Comput, Archit. News, 44(3):78-89, June 2016. ISSN 0163-5964. doi: 10.1145/3007787.3001 146. /Bl//tttp////61..//1110.0
3001146
[41] Z. Jiang, D. Panigrahi, and K. Sun. Online algorithms for weighted paging with predictions. ACM Trans. Algorithmss, (8(4):39:133922) 2022. doi: 10.1145/3548774. URL https
org//.rg/1000 11t.///1...11388177771 1145/3548774
[42] Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis. The case for learned index structures. In Proceedings of SIGMOD' 18, pages 119-5004 2018. doi: 00.1145/318371333199900
[43] A. Lindermayr and N. Megow. Permutation predictions for non-clairvoyant scheduling. In SPAA, pages 357-368. ACM, 2022.
[44] A. Lindermayr and N. Megow. Algorithms
with predictions. 2022. [Online; accessed 8-September-
https:
7 7/algorithms weath--peeiice ctiisstion....o wtwpedeiciionniit........ //algorithms with wwwesswwttttpheeiitooeee wtionsisiioo..ii............. 2022].
io
URL https
[45] A. Lindermayr, N. Megow, and B. Simon. Double coverage with machine-learned advice. In M. Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 February 2022, Berkeley, CA, USA, volume 215 of LIPles, pages 99: 19:1199:11 18. Schloss Dagstuhl SewziiiiizZZetrrun für Informatik, 2022. doi: Lt23:/LIPcs..TSS..... URL httph::tt///cc... /tw:://ooi..e http:///ooo.oo///////// /00 4230 ht///IPIcSS ITCS 2022.92 .99
[46] E. Liu, M. Hashemi, K. Swersky, P. Ranganathan, and Ahn. An imitation learning approach for cache replacement. In Proceedings of the 37th International Conference on Machine Learning, volume 1 19 of Proceedings of Machine Learning Research, pages 0227-62477 PMLR, 13-18 Jul 2020. URL BRLhttts:: http::///occceeeeeeoo mlr www.ppesessiii... 1911/112/11fff. html
[47] T. Lykouris and S. Vassilvitskii. Competitive caching with machine learned advice. J. ACM, 68 (4):24:1-24:25, 2021.
[48] M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions. In Beyond the Worst-Case Analysis of Algorithms, pages 646-662. Cambridge University Press, 2020.
12

---

Published as a conference paper at ICLR 2024
[49] A. Polak and M. Zub. Learning-augmenter maximum flow. CoRR, 1bs/2207.12911, 2022.
[50] M. Purohit, Z. Svitkina, and R. Kumar. Improving online algorithms via ML predictions. In NeurIPS, 2018.
[51] D. Rohatgi. Near-optimal bounds for online caching with machine learned advice. In SODA, 2020.
[52] Sakaue and Oki. Diserre--oovexx-aaaliiishheed framework for warm-starting algorithms with predictions. CoRR, abs/2205.0992 2022. doi: 10:48500uXXi.225000000 00991..
[53] Z. Shi, X. Huang, A. Jain, and C. Lin. Applying deep learning to the cache replacement problem. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecturr, MICRO '52, page 413-425, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450369381. doi: 10.1145/352460.3338899.
URL
3358319
[54] D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2):202-208, 1985. doi: 10.1 10.1145/2786.2793.
[55] A. Wei. Better and simpler learning- augmented online caching. In APPROX/RANDOM, 2020.
[56] A. Zeynali, B. Sun, M. H. Hajiesmaili, and A. Wierman. Data-driven competitive algorithms
for online knapsack and set cover. In AAAI, pages 10833-10841. AAAI Press, 2021.
13

---

Published as a conference paper at ICLR 2024
FULL VERSION OF THE PAPER ALGORITHMS FOR CACHING AND MTS WITH REDUCED NUMBER OF PRE- DICTIONS
Karim Abdel Sadek
Marek Eliáš
University of Amsterdam"
Department of Computing Sciences Bocconi University
karim. abdel. sadek@student, uv
marek www.seuniboccooo.........ooooo..
ABSTRACT
ML-augmented algorithms utilize predictions to achieve performance beyond their worst-case bounds. Producing these predictions might be costly operation this motivated [Im et al. (2022) to introduce the study of algorithms which use predictions parsimoniously. We design parsimonious algorithms for caching and MTS with action predictions, proposed by Antoniadis et al. (2023), focusing the parameters of consistency (performance with perfect predictions) and smoothness (dependence of their performance the prediction error). Our algorithm for caching is 1-consistent, robust, and its smoothness deteriorates with the decreasing number of available predictions. We propose algorithm for general MTS whose consistency and smoothness both scale linearly with the decreasing number predictions. Without the restriction the number of available predictions, both algorithms match the earlier guarantees achieved by Antoniadis et al. (2023).
INTRODUCTION
Caching, introduced by Sleator and Tarjan (1955), a fundamental problem in online computation important both in theory and practice. Here, we have fast memory (cache) which can contain up to different pages and we receive a sequence of requests to pages in an online manner. Whenever a page is requested, it needs be loaded in the cache. Therefore, if the requested page is already in the cache, can be accessed at no cost. Otherwise, we suffer a page fault: we have to evict one page from the cache and load the requested page in its place. The page eviet is be chosen without knowledge of the future requests and our target is to minimize the total number page faults.
Caching is special ization of many fundamental online problems. In the beginning, we are given a metric space M of states which can be interpreted as actions configurations of system. We start state To E M. At time steps t = 2, we receive cost function E M + R U {0, + and we need make decision: either stay at xt-1 and pay a cost (x(=:1)) or move to another, possibly cheaper state and pay (xx)) + d(x:-1, Ix), where the distance d(I xx) represents the transition cost between states 2t-1 and Ft.
of Metrical Task Systems introduced Borodin al. (1992) as a general-
predefined
The online nature of both caching and MTS forces an algorithm to make decisions without knowledge of the future which leads to very suboptimal results in the worst case (Borodin et al. 1992, Sleator and Tarjan 1985). A recently emerging field of Marning-auggentee algorithms, introduced in seminal papers by Kraska et al. (2018) and Lykouris and Vassilvitskil (202I), investigates approaches to improve the performance of algorithms using predictions, possibly generated by some ML model. In general, no guarantee on the accuracy of these predictions assumed. Therefore, the performance of leaminn--uggennt algorithms is usually evaluated using the following three parameters:
Consistency. Performance with perfect predictions, preferably close to optimum.
"The presentation of this paper was financially supported by the Amsterdam ELLIS Unit and Qualcomm. Work completed while Abdel Sadek in his final year of BSc Boceoni University

---

Published as a conference paper at ICLR 2024
Robustness. Performance with very bad predictions, preferably worse than what is achievable by known algorithms which do not utilize predictions.
Smoothness. Algorithm's 's performance should deteriorate smoothly with increasing prediction error between the consistency and robustness bound.
These three parameters express desire to design algorithms that work very well when receiving reasonably accurate predictions most of the time and, in the rest of the cases, still satisfy state-of- the-art worst-case guarantees. See the survey by Mitzenmacher and Vassilvitskii (2020) for more information.
Producing predictions is often computationally intensive task, therefore it is interesting understand the interplay between the number of available predictions and the achievable performance. In their inspiring work. [Im al. (2022) initiated the study of learning- -aggeneed algorithms which use the predictions parsimoniously. In their work, they study caching with next-arrival-iie predictions introduced by Lykouris and Vassilvitskii (202T). Their algorithm uses Obboggo+1 k) OPT predictions, where OPT is the number of page faults incurred by the offline optimal solution and b E N is parameter. It achieves smoothness linear in the prediction error. satisfies tight consistency bounds: with perfect predictions, it incurs at most (1ogg++1 k) OPT page faults and no algorithm can do better. In other words, achieves constant competitive ratio with unrestricted access to predictions (b k) and, with b small constant, its competitive ratio deteriorates (log k) which is comparable to the best competitive ratio achievable without predictions. One of their open questions is whether a similar result could be proved for MTS.
In this paper, we study parsimonious algorithms for MTS working with action predictions which were introduced by Antoniadis et al. (2023). Here, each prediction describes the state of an optimal algorithm at the given time step and its error is defined as the distance from the actual state of the optimal algorithm. The total prediction error is the sum of errors of the individual predictions. In the case of caching, action predictions have a very concise representation, see Section 2. Unlike next-arrival-tim timm predictions, action predictions can be used for any MTS. Using the method of Blum and Burch (2000), it is easy to achieve near-optimal robustness for any MTS losing only a factor (1+ in consistency and smoothness. Therefore, we study how the reduced number of predictions affects the consistency and smoothness parameters. We consider the following two regimes.
Bounded number of predictions: The algorithm can request prediction whenever prefers as far as the total number of requested predictions is bounded by b OPT, where b is parameter. This regime similar to Im et al. (2022).
Well Well-separated queries to the predictor: The queries to the predictor need to be separated by at least a time steps, for some parameter a. This captures the situation when producing each prediction takes more than one time step.
1.1 OUR RESULTS
We evaluate the algorithm's performance using competitive ratio which is, roughly speaking, the worst-case ratio between the cost incurred by the algorithm and the cost of the offline optimum, see Daction[]for a formal definition. We say that an algorithm achieves consistency a and robustness 3 if its competitive ratio is at most a when provided with perfect predictions and at most 3 with arbitrarily bad predictions. For given function g. we call an algorithm (()) -smothh if its competitive ratio is at most (v)) whenever provided with predictions with the total error at most y).
Our first contribution is an algorithm for caching which receives action predictions describing the states of the optimal offline algorithm Belady proposed by Belady (1966). High quality such predictor based on imitation learning was already designed by Liu et al. (2020). Its empirical evaluation within existing al algorithms designed for action predictions was performed by Chledowski et al. (202T).
Theorem 1.1. Let be an increasing convex function such that f() and f(i) < 2 for each i 2 O. There is an algorithm for caching requiring (l k)) OPT predictions which achieves consistency robustness (log k), and smoothness O(f Onf-((//O prediction error with respect to Belady and OPT is the number of page faults of Belady.
where r denotes the total
In fact, the number of required predictions is slightly smaller than what is stated in the theorem. Table shows numbers of predictions and achieved smoothness for some natural choices of f. Already with
2

---

Published as a conference paper at ICLR 2024
Table 1: Smoothness vs. number of predictions.
((i)
# of predictions
smoothness
O(VR)PPT
" 0(1 + log( OPT + 1))
82
Ollog 2 k) OPT
0 2 2OPT)
i
Oloog k) OPT
0 1
0
2 OPP
O ((PT)
O(Vk) OPT predictions, our bounds are comparable to Antoniadis et al. (2023) whose algorithm asks for prediction in every step, its consistency is constant and its smoothness is logarithmic in The algorithm also works with f() = 0. In that case, asks for at most 2 2PT predictions and still remains 1-consistent. However, its smoothness is not very good. We use sliding marking phases and a careful distribution of queries of the predictor over the time horizon. This allows us to avoid dealing with so called "ancient" pages considered by |Rohatgi (2020) and Antoniadis et al. (2023). resulting in an algorithm with better consistency and simpler analysis.
We discuss tightness of our bounds in Section 7 We show that with, for example, only P. available predictions, no algorithm can be better than Oloog k)-competitive guarantee comparable to the best classical online algorithms without predictions. We also show that the number of predictions used by our algorithm is close optimal.
Theorem 1.2. Let f be an increasing function. Any (n)-mmooth algorithm for caching with action predictions, i.e., an algorithu whose competitive ratio with predictions of error 1j is fn) for any ? has to use at least f(ln k) OPT predictions.
For general MTS, cannot bound the number of used predictions as function of OPT. The reason is that any instance of MTS can be scaled to make OPT arbitrarily small, allowing us to use only very few predictions. We propose an algorithm which queries the predictor once in every time steps, making at most T'aa aa queries in total, where T denotes the length of the input sequence.
Theorem 1.3. There is deterministic algorithum for any MTS which receives a prediction only once per each time steps and its cost at most O(a) (OFF +2n), where OFF denotes the cost of an arbitrary offtine algorithm and 1) the error of predictions with respect to this algorithm.
This is more general statement than Theorem which requires OFF to be Belady. Considering any offline optimal algorithm OFF, Theorem implies a smoothness ( (1 + 2n/ OPT) and consistency (a). Our algorithm is based work functions. For
its smoothness is 1 OF/OFF, see Section 4 which improves upon the smoothness bound of + 4n/ OFF by Antoniadis et al. (202)) It not robust on its own. However, it can be combined with any online algorithm for the given MTS using the result of Blum and Burch (2000) achieving robustness comparable that algorithm and losing only factor of (1 + c) in smoothness and consistency.
No algorithm receiving a prediction only once in a time steps can be ofa)-consistent. This follows from the work Emek al. (2009) on advice complexity, can be shown for smoothness by modifying the lower bound construction of Antoniadis et al. (2023).
Section for more details. The same
Theorem 1.4. There is no olan/ OPT) smooth algorithm for MTS with action predictions which receives predictions only once a time steps.
We can modify our algorithm for eaching to ensure that the moments when the predictions are queried are separated by at least a time steps, not losing too much of its performance.
Theorem 1.5. There is an algorithm for caching which receives prediction at most once in S. k time steps and using at most Off (log k)) OPT predictions in total which is O())coonsistent, Ö(log k)- robust and ((f-((an) (OTT)))SSiiii smooohh.
we provide empirical results suggesting that algorithm's 's performance can be comparable to the performance of algorithms imposing no limitations on their use of predictions. Our algorithm may therefore be useful especially with heavy-weight predictors like (Liu al. 2020
In Section 5
3

---

Published as a conference paper at ICLR 2024
we provide algorithm for alternative prediction setup which call FitF oracle: each prediction says which of the pages in the current algorithms cache will be requested furthest in the future.
In Section 8
1.2 RELATED WORK
The most related work is by Im al. (2022). who studied caching with next arrival time predictions. smaller number of predictions affects the consistency of their algorithm: with b(log k/ log b) OPT predictions, they achieve consistency (log k/ log and they show that this is tight. They also show that their algorithm achieves linear smoothness. In contrast, our algorithm is 1-consistent when receiving least OPT predictions. This demonstrates that action predictions, although not containing more bits, seem to contain useful information about the input instance in more condensed form. See (Antoniadis et al. 2023) for comparison and connections between these prediction setups. Drygala et al. (2023) study ski rental and bahncard problems with predictions of fixed cost.
There are several other papers on eaching with predictions, including (Lykouris and Vassilvitskii 2002]] Rohatgi 2020; Wei, 20200 [mmek et al. 2009 Antoniidis al.) 2023 [0222 which design algorithms asking for a prediction at each time step. Consistency parameters achieved by these algorithms are constants greater than 1. Note that those using black-box methods to achieve robustness are (1 + e)- consistent (e.g. (Wei 2020 We can explicitly compare our smoothness bounds to Antoniadis et al. (2023) who use the same kind of predictions: their smoothness is O(1 log(opT + 1)) with unlimttd use of predictions while our algorithm achieves the same smoothness bound with OVVE) OPT predictions. We compare the smoothness of the other algorithms experimentally in Section 5 Antoniadis et al. (2022) study prediction setup where each prediction is only a single bit, however their algorithms need to receive it in every time step. Gupta el al. (2022) study several problems including caching in a setting where each prediction is correct with a constant probability.
Antoniadis et al. (023) proposed a 1-consistent and (1 + 4n/ -mTo)smmothh algorithm for MTS with action predictions which can be robustified by loosing factor (1 + E) in consistency and smoothness. Getting smoothness bounds sublinear in n// OPT for specific MTS problems other than caching remains a challenging open problem even with unlimited number of predictions and this holds even for weighted caching. Specific results on weighted caching are by Diang et al. (2022) who studied it in a setup requiring very verbose predictions and by Bansal et al. (2022) whose bounds depend on the number of weight classes. There is also a consistency/robustres trade-off by Lindermayr et al. (2022) for k-server.
Since the seminal papers by Kraska et al. (2018) and Lykouris and Vassilvitski 2021 which initiated the study of Baaring--uggment
algorithms, many computational problems were considered.
There are papers on ski rental (Purohit et al. 2018
Antoniadis et al. 2021 secretary and matching 2020),
problems Dütting et al. 2021 [021||Antoiadii et al.
(Im et al. 2021 Zeynali
et al. 2021 Boyar et al. 2022), graph exploration (Eberle et al. (202)), online TSP (Bernardini et al.
2022). energy efficient scheduling (Bamas et al.
2020). flow-time scheduling (Azar et al. 202 1
2022), restricted assignment (Lattanzi et al. [2020), non-clairvoyant scheduling Purohit al. (2018):
Lindermayr and Megow| (2022), and online page migration (Indyk et al./ (2022). In offline setting,
there is work of Dinitz al. (Dinitz al. (022) on matching, Chen et al. (Chen et al. (002)) on graph algorithms, Polak and Zub (Polak and Zub (022) on flows, Sakaue and Oki (Sakaue and Oki 2022) on discrete optimization problems, and Ergun al. (Ergun et al. (022) on clustering. We also refer to (Lindermayr and Megow 2022) to an updated list of results in the area.
There are numerous works on advice complexity of online problems, where algorithms are given certain number of bits of information about the future which are guaranteed to be correct. This is different from our setting, where we receive predictions of unknown quality. We refer to the survey by Boyar et al. (217)). work of Dobrev et al. (2009) caching, Emek et al. (2009) on MTS, and further papers by Hromkovič et al. (2010): Böckenhauer et al. (2017).
There are already works on predictors for caching, Jain and Lin (016)) proposed binary classifier called Hawkey which predicts which pages will be kept in cache by Belady, providing us with action predictions. Their result later improved by (Shi by(Shi et al. (2019) who designed model called Glider for the same classification problem. There is a very precise model by Liu et al. (2020) whose main output can be interpreted as an action prediction although it has second prediction head which
4

---

Published as a conference paper at ICLR 2024
produces next arrival predictions. This model is large and relatively slow and served motivation for this work. [Chledowski et al. (2021) evaluated the performance of existing ML-augmented algorithms with this predictor.
PRELIMINARIES
Consider an algorithm ALG for MTS which produces a solution To, ......,......................... 2T for an instance consisting of cost functions f,...,,7. fr. We say that ALG is r-competitive with respect to offline algorithm OFF if there is an absolute constant a E IR such that H [oosst(( ALG(()) S cost(OFF(()) + a for any instance I. If ALG is r-competitive with respect an optimal offline algorithm, we say that ALG is r-competitive and call the competitive ratio of ALG. In the classical setting (without predictions), the best achievable competitive ratios are O (log k) for caching (Fiat al. 1991) and of order poly log n for MTS (Bartal et al., 2006 Bubeck et al. 2019), where n is the number of points in the underlying metric space M. We refer to [Borodin and Yaniv 1998) for a textbook treatment.
We denote cost (A)G()))) Σ
11= (fxx)) + (,,
[[cost(ALG(())
2.1 ACTION PREDICTIONS FOR MTS
Antoniadis et al. 2023) proposed a prediction setup which they call action predictions, where the predictions tell what good algorithm would do. More precisely, each time t, the algorithm receives a prediction P: of a state where some offiie algorithm OFF moves to at time t. The error of prediction Pt is then 7) d(pt. oz), where o, is the real state of OFF at time t. The total prediction error defined as 1) = Σー 1/p-
Considering the case of caching, the state corresponds to cache content, and the prediction error is the number of pages present in the cache of OFF and absent from the predicted cache content. whole cache content may seem like a huge piece of information, but action predictions for caching can be implemented in a very succinct way. Antoniadis et al. (2023) explain how to represent them with only (log k) bits per time step when they received at each time step. Our algorithm asks, in each query, specific number of indices pages which are present in its cache but absent from the predicted cache. When we talk about bound on the number of provided predictions, this bound applies both to the number of such queries as well as to the total number of indices reported by the predictor during the running time of the algorithm. There generate predictions of a similar kind by Jain and Lin (2016); (Shi et al. (2019); Liu et al. (2000). See (Antoniadis al. (203) for detailed treatment of this prediction setup and a comparison other setups for caching.
predictors which can
2.2 CACHING: BELADY'S S ALGORITHM, MARKING, AND LAZY ALGORITHMS
The classical optimal offline algorithm for caching proposed by Belady 1966) is denoted Belady in this paper. each page fault, evicts a page which going to be requested furthest the future. In the case of tie, i.e., if there are several pages in the cache which will not be requested anymore, chooses one of them arbitrarily. Our caching algorithm assumes that the predictor is trying to simulate Belady. The following useful property allows to detect errors in the predictions quickly, was recently used by Eliás et al. 2024)..
Observation 2.1. Consider request sequence Ti,.... TT. For any S T, the cost incurred by Belady for ri. . .T until time t is the same as the cost of Belady with input rrpputri..... .'...
To see this, it is enough to note that the solution produced by Belady with input ri,..., 'T agrees until time / with the solution produced by Belady on ri....,P', which breaks ties based on the arrival times in Tt+1...., TT..
We use properties marking algorithms in this work. Such algorithms split the input sequence into phases, i.e., maximal subsequences where at most k distinct pages are requested. Usually, the first phase starts in the beginning and the next phase follows just after the end of the previous one. However, will consider phases starting at arbitrary moments. Let O be the cache content of an algorithm in the beginning of the phase. Whenever a page is requested for the first time during the phase, call this moment arrival and we mark the page. At the end of the phase, the set
5

---

Published as a conference paper at ICLR 2024
M of marked pages will have size k: some of them belong to O and are called old while those in C' = MM O are called clean. Exactly |C] pages from O remain unmarked until the end of the phase.
Marking algorithms is class of algorithms which never evict marked page and all of them have cache content M at the end the phase. Belady is not marking and our algorithm not marking either, although it uses ideas from marking achieve desired robustness and smoothness properties. At the end of each phase, we can bound the difference between the cache content of some algorithm and marking.
Observation 2.2. Let è be the cost incurred by some algorithm during marking phase. Then, 2 JM \ S), where is the cache content of the algorithm at the end of the phase and M is the set of l pages requested during the phase.
This is because each page in p E M has to be present in algorithm's cache when requested during the phase. p $ S, then the algorithm must have evicted it during the phase incurring cost 1.
Observation 2.3. If a page p is evicted by Belady at time t, then p is not going to be requested in the marking phase containing t anymore.
If p is evicted by Belady at time t, then the currently requested page rt and 1 pages from the cache are i distinct pages that are requested before the moment when p is requested next time. The current phase then needs to end before that moment.
We say that algorithm is lazy if it evicts only one page at time and only at page fault. Belady is lazy while our algorithm, as described, may not be. However, any algorithm can be made lazy without increasing cost. See (Borodin and El- Yaniv 1998) for more information about caching.
Observation 2.4. The difference in the cache content of two lazy algorithms can increase only if both of them have a page fault. that case, can increase by at most
2.3
MTS AND ADVICE COMPLEXITY
Advice complexity studies the performance of algorithms depending on the number of bits of precise information about the instance available in advance. In the case of MTS, Emek et al. al.] (2009) study the situation when algorithm receives a log n bits of information about the state of some optimal offline algorithm, being able to identify its true state once in a time steps. They formulate the following proposition for OFF being optimal algorithm, but the proof does not use its optimality and it can be any algorithm located at at time in.
Proposition 2.5 (mek et al. (2009)). There is an algorithm which, with knowledge of state q, of algorithu OFF at time ia for I,...,TT T//. a, is ( (())-competitive w.r.t. OFF.
In our context, we can say that the algorithm from the preceding proposition is O(a)-consistent if @1 ... (a are states of an optimal solution. However, it is not smooth because it may not be possible to relate the cost of OFF to the prediction error with respect OPT.
BOUNDED NUMBER OF PREDICTIONS
In this section, we prove Theorem I.I We propose algorithm called F&R which consists of two parts: Follower and Robust. It starts with Follower which is I-consistent, but lacks in smoothness and robustness. At each page fault, Follower recomputes Belady for the part of the sequence seen so far and checks whether it also has page fault. If yes, it copies the behavior of the predictor (Line B) Otherwise. must have received an incorrect prediction before. Therefore, it switches Robust (Line 5) which is no more 1-consistent, but achieves desired smoothness and robustness. Robust runs for one marking phase and then returns back to Follower. At such moment, the predictor's 's and the algorithm's 's cache can be very different and Follower may need to lazily synchronize with the predictor (Line 4).
Algorithm Robust runs during single marking phase starting at the same moment, splitting it into windows as follows (assuming l is a power of 2): The first window W1 starts at the beginning of the phase and lasts k/2 arrivals, i.e., it ends just before the arrival number h/2 + 1. W, follows the W. and its length is half of the remaining arrivals in the phase. The last window Wing = {k} lasts until the end of the phase. Robust. comes with an increasing convex function such that f(0) 0

---

Published as a conference paper at ICLR 2024
Algorithm 1: Follower
P := initial cache content;
// Prediction for time
foreach pagefault do if rt & P and Belady has a pagefault then query new prediction P and evict any p E C. P; else rf P then evict arbitrary p & P.
else Switch to Robust (Algorithm)
and f(i) < 2 -1- Faster growing f does not further improve our smoothness bounds, Function determines that we should request f(i) - f(i - predictions in window i. the window too small, we ask for prediction at each time step. Robust starts with the cache content of a marking algorithm whose new phase would start at the same moment (Line [T. In the case of page fault, evicts unmarked page chosen uniformly at random. At arrivals belonging to the sets S and F, performs synchronization with the predictor and queries the predictor's ' state respectively. The synchronization is always performed with respect to the most recent prediction P which, in the case of lazy (or lazified) predictors, implicitly incorporates information from the previous predictions.
Algorithm 2: Robust, y (one phase)
Load distinct most recently requested pages;
2 := [k- 2 + 1 = log k, ,., 0}:
3 We = [k 2 k- i+1 + 1, 2 i for io .,....,.oop.. log ks and Wlog k+1 = {k]:
Choose F (1,..., k} such that |FNW. min ʃ(i 1), W;]] for each
foreach pagefault during the phase do
if it is arrival belonging F then ask for new prediction P: if' it is arrival belonging to S then synchronize with P: if' requested page still not in cache then evict random unmarked page:
Load all pages marked during the phase; Switch to Follower (Algorithm)
10
Synchronization with P (Line 7 works as follows. All pages previously evicted by random evictions return to the cache and the same number of pages not present in P is evicted. We denote E, = ET E the set of pages evicted at the begimning of W,, where pages in E, are requested during W: while those in E, are not. Note that algorithm's 's and predictor's 's cache may not become the same after the synchronization. Since the algorithm starts with pages in M and loads only clean pages, have the following observation.
Observation 3.1. Let C., |C,| = & be the set of clean pages arriving before the start of W,. Then, E, C M C, and EE [ UM k- Ct-
We assume that the predictor is lazy and does not load pages that are not requested. Therefore, no page from E will be loaded during W; by the predictor and the same holds for Robust, implying the following.
Observation 3.2. For every i = 1,...,
, log k, we have E C Ei_ and therefore E, E+p C E,
Synchronization with the marking cache performed by Robust is to ensure that the difference between the cache of the algorithm and Belady can be bounded by costs incurred by Belady locally using Observation 2.2 instead of diverging over time solely due to incorrect predictions.
Implementation suggestions. Algorithms are described as to simplify the analysis. Synchronization in Robust (line(7 should be done lazily as to make use of the most recent prediction. At arrivals of clean pages, one may evict page not present in predictor's cache instead of a random unmarked page; one can also ask for fresh prediction (at most 0PT additional queries). The second synchronization with the marking cache in Robust (line 9 can be omitted. With f(i) = O, one can query the predictor only clean arrivals, using at most 2 2OPT predictions in total. We recommend a lazy implementation. Since Robust is not 1 1-consistent, one may also switch from Follower only once Follower's cost is at least constant (e.g. 2 or 3) times higher than the cost of Belady.
7

---

Published as a conference paper at ICLR 2024
We denote H, the ith phase of Robusty and H hypothetical marking phase which ends just before H4 starts. Note that H; might overlap with H But H1, Hz... are disjoint and denote G1a+1 the time interval between the end of H; and the beginning of H4+1- c(H is the number of clean pages during phase H₁. For a given time period X, we define (X),), B (X), and (X) the costs incurred by F&R,, Belady, and the predictor respectively during X and (xX) the error of predictions received during X.
Here is the main lemma about the performance of Robust. Its proof is deferred to Section 3.2
Lemma 3.3. Denote X; Hi-1UP H U H, During the phase He Robust, receives at most f(log k) predictions and we have
(H4))
EHA)(H,) S O0()
(x..)) (X,,)
At the same time, we also have
EAA (H.) < Ollog A) (X:) and
(2)
A (H;) S ((k) + (H.).
3.1 ANALYSIS OF FOLLOWER
Lemma 3.4. Consider the gap Gist1 between phases H, and H,-1 of Robusty. We have (A s A + (H,,)
Proof. There are A (Gr,441) page faults served at line 3 because Belady also has those page faults. To bound the cost incurred on line 4 we denote P. B, M the cache contents of the predictor, Belady, and Robust respectively at the end of the phase H. The synchronization with P costs at most ((P) \ .M) n B if we omit costs incurred by Belady which were already accounted for above. However,
n (B), M) n C B M and [B \ M < A (H;) by Observation 2.2
The cost of Follower until the start of H1 is the same as the cost of Belady. the cost of F&R, in expectation, is at most Therefore, by lemmas 3.4 and 3.3 equation I
Proof of Theorem 1.7
n(H,) AB(X.)
OPT + Σ (O()))(())))
where the sums are over all phases of Robust and X, = H U H. U H₁. Since phases H, are disjoint and the same holds for H, this expression is at most OPT Of OPT)) by concavity of f-1, implying the smoothness bound for F&R.
If we use bound equation 2 instead of equation | we get Olog k) OPT the robustness bound. Since there must be at least eтror during the execution of Follower to trigger each execution of Robust, equation 3 implies that the cost of F&R is at most OPT (k) With 1j 0, this implies 1-consistency of F&R. Follower queries the predictor only a page fault by OPT and the prediction consists of single page evicted by the predictor. Robust may ask for up to flog k) + 1 predictions in each phase, each of them consisting of indices most cf (.) pages from F&R cache not present in the predictor's 's cache. This gives both ( k)) OPT queries to the predictor as well as Of (log k)) OPT predicted indices in total.
Note that Robust, rarely use full (log k)) predictions, because the last windows are not long enough. More precise calculation of numbers of predictions can be found in Appendix A
3.2 ANALYSIS OF Robust,
First, we relate the number of clean pages in a robust phase to the costs incurred by Belady. Observation 3.5. Consider phase H denoting C(H) the set of clean pages arriving during H. We
have
((H) = (C(H) < B + B (H))
8

---

Published as a conference paper at ICLR 2024
Proof. There are k + c(H) pages requested during H U H. Therefore, any algorithm, and Belady in particular, has to pay cost A A"(H" UH) 2 c(H).
Lemma 3.6. Consider phuse Hi. Cost incurred by Robust synchronization with marking in Line is at most A A
U U
Proof. Let M denote the & distinct most recently requested pages these are marked pages during H We consider two cases.
If HH H = 0, then whole H, was served by Follower. Each p E . must have been in the cache of both Follower and P when requested and Follower would evict it afterwards only if P did the same. Therefore, Robust needs to load at most A (H,) A (H,) pages.
If H and H overlap, let M' denote the set of pages marked during H;-1- At the end of H,-1, Robust loads M' and Follower loads only pages from M until the end of H," Therefore, Robust
starting H, needs to evict only pages from M') M. Now, note that there are M U M| distinct pages
requested during H U Hj and therefore |M' \ M| = |M / U M| k - A B (H UH, O
We consider costs incurred by Robust during window W; for 1, ,.... log k 1. Note that E = F = Fr = 0, since W1 starts at the beginning of the phase and there are no clean pages arriving strictly before W1.
Lemma 3.7. Expected cost incurred by Robust, during W1 is most 202. For i 2, 2,... .... log we have
EIA [[A)(W
E - --1 - - | + G+1 -c),
denoting Clog k+2 c(H).
First, consider the costs during W₁. There are C2 - = 62 clean pages arriving during Wi and Robust has a page fault due to each of them, evicting a random unmarked page. In the worst case, all these clean pages arrive at the beginning of W1. Therefore, at arrival c2 + 1, there are cz pages evicted which were chosen among unmarked pages uniformly at random. Let U, denote the set of unmarked pages at arrival a. We have U1 = M (the initial cache content of Robust) and none of those pages get marked during first 02 arrivals. During every arrival C2 + 1,... k/2 S[2] a single unmarked page is marked and we have UU, = (a c2). As in the classical analysis of 1998) and references therein), the probability of the requested Marker (see (Borodin and EJ- Yaniv unmarked page being evicted is c2/
Proof.
Cal. We have
S(2|-1
AA(W)) = 02 +
Σ a c211
S
C2
+ 2 k/2
02
202-
UU
For 2 2, there are & pages evicted before the start of Wf: those in E were evicted due to synchronization with the predictor and the rest were evicted in randomized evictions those loaded back to the cache at the beginning of Wi, causing cost c; - -ET_1 = | + c Q-1- After this synchronization, all unmarked pages in the cache except those belonging to E,-
During W. pages from E, and G++1 - C, new clean pages are requested causing page faults which resolved by evicting random unmarked page from the cache. In the worst case, these page faults all happen in the beginning of the window, leaving more time for page faults on randomly-evicted pages. Let denote the first arrival after these page faults and Ua the of unmarked pages that moment. At arrival a, there are C++1 pages missing from the cache: pages from E,+ which are not going to be requested during W, and E + C++1 C c++ E unmarked pages were chosen uniformly at random from Ua \ E, = Un \ Et. This is because only pages which were marked since the beginning of W. until à are those from E.- and they were not present in the cache before they got marked. We compute the expected number of page faults on the randomly evicted pages. Since they are unmarked when evicted, such page faults can happen only on arrivals.
At arrival a, the set of unmarked pages U. has size k (a c++1). For any E W, such that a 2 we have Ua O Fr- 0 and pages in U, n Et are evicted with probability 1. So, G+4 E2t evicted

---

Published as a conference paper at ICLR 2024
pages picked uniformly random from Un \ E of size at least (a c++1) E. Therefore, our expected cost is at most
51++1|-1
Gi+1 - |
G+11 - |
Ci+1 - |
Σ
Ci+1 1
a c++1 E
h
2
k:/2'
neW;
which is equal to FT-1l + Gs - C--1-
Note that h a- k Sli + 1] 1 = k- k/22'.
For i = 1, ..... log k, we define
rank(W.) := [84+1 O BB+1 - (W;).
where B; denotes the cache content of Belady at the beginning of W We do not define rank(W,) for i = 1 + log k. Later, we relate rank to the prediction error. We have the following lemma. Lemma 3.8. During a phase H. the expected cost of Robusty is most
log 1++
3
rank(W;-1) + 3c(H) + +6 (H).
Proof. First, we observe that
E S rank(W:-1)++
A W + A (W.)
(4)
holds for i = 2,..... log k + 1. This is because E n B, S E, n rank(W, A (W:
and E B3J < A (W;) due to pages from E being requested during W; and Belady having
load them. Combining equation 4 with Lemma 3.7 and summing over all windows, we get the
statement of the lemma.
Now, we relate the rank of a window to the prediction error.
Lemma 3.9, Denote gy the error of predictions arriving during W.. We have
nW;) 2 FF n W;| rank(W.)..
Proof. Prediction error at time is 1)t = B, P.l. the end of W., it least |E O B Due to laziness of the predictor, |B \ P, can increase only if both predictor and Belady have a page fault: in that case it may increase by 1, see Observation 2.4 Therefore. at any time during W,, we have m B, P. > [E41 n F++1l - A 8 (WW) (a, Since we query the predictor at arrivals belonging to F, the total error of received predictions is at least IF n W; rank(W,).
We will analyze intervals of windows starting when some particular incorrect prediction was intro- duced and ending once it was corrected. The following lemma charging the increase of rank to the arriving clean pages and costs incurred by Belady will be used to bound the number of such intervals. Lemma 3.10. For i I....,
., log k. we have
rank(W.) - rank(W.-1)) S A (W,,1) + G.+1 - Ci.
denoting Wo empty window before W1 with rank(Wo) 0.
Proof. It is enough to show that
E+1 n B, & E.E,B + (WW,) + c+1 -..
Since the right-hand side is always non-negative, we only need to consider the when the left-hand side is positive. We show how to charge pages in E, n B+41 either to pages in E, n B; or to A B (W,) and C++1 Cz.
Since E = G < Ci+1 |E4z// we can construct an injective map 3: E, - E,41, such that 3(p) = p for each p E E, E,+1. There are |E411| E, C++1 c, pages p such that / (p) is not defined. We show that, for each p E E n B,+1 for which is defined, ,3 g-1 (p) is either a page in E, O B; page loaded by Belady during W. There are two cases.
10

---

Published as a conference paper at ICLR 2024
p E, n E implying (p) p. Then either p B, and therefore E, n B,, E Bi+1 \ B, implying that Belady has loaded during W,.
p $ E, n 1 implying q = (p) E, E By Observation 3.2 q i must have been requested during W,. If g B, then, E E, Otherwise, Belady must have loaded q during W.
To sum up: B is an injective map and (p) does not exist for at most 4+1 pages p E O Bi+1- other p Es+1 n B,+1 are mapped by 3-1 unique page either belonging to E, n B, or loaded by Belady during W,-
Proof of Lemina
3.3 Robusty receives prediction only at an arrival belonging to F. Since F Fn loog (f(i) (f()) f(i 1)) + log k+1| S fllo k)) + arrivals, because and f(0) = O, there are at most f (log k) queries to the predictor.
contains
Σ 1=1
k+1
[Woog k++1
To prove equations ) we always start with bounds proved lemmas 3.5 3.8 3.6 In the rest of the proof, we write H instead of H; and X instead of H; to simplify the notation.
To get equation equation note that (W;) S c(H) for each window Therefore, by lemmas and 3.6 we can bound E(AA(H)) by
3.5
3.8
B (x) + 3c) log + 3e(1)) + 6Λ B (H) I O(log k: A))
To get equation equation note that A (
(H) & h (H) < k, and rank rank(W,)) > 0 only if m 2 [Ee41 0 B,+1| 1. Therefore, get A (H) S ((k) + m (k))
Now we prove equation equation We define Q.. = iil (Wn < m and rank(Ws+1) 2 m)
and Q
Σm 1mml. We can bound Q using Lemma 3.10
We have
log
log k
Q
Qml =
Σ max ra,)(W.) rank(W:-1)) <
(24 (W,) + -4). (5)
m=
1=1
which is equal to 2 + (H).
We bound D & ran as function of Q and r)(H
log
rank(W,) s 2Q (
(6)
Q
This relation is proved in Proposition 3.11 with a = and, together with equation desired bound
gives us the
E (()) an (H)
an(H)
Q
Proposition 3.11.
log rank(W,) s 2QQ f-((
Q
Proof. We rearrange the sum of ranks in the following way. We define Lm. = fil rank(W,) 2 m}. and mi such that T.m UseQ... (i, + di,m] for each m. We write
log k
k
k
rank(W.))
Lm
ai,m
(8)
m=
m=
FEQ
11

---

Published as a conference paper at ICLR 2024
rank(W.)) |FO,. (Lemma 3.9
On the other hand, we write 77 2m=1 the total prediction error 77()) as follows:
which allows us to decompose
dia
n(H)
Σ E melmmmm
FNWI
E
Σ
Σ
FF
m= 11liimm j=1
Let i* denote the first window such that |W,.| < f(() f(i" - 1). i + Oi. < i", then
Ei= IF n We+sl = f(i + mm. - f() 2 f(as.m) ) by convexity of f. If this is not the case, we claim that Djer F PnW++112 2 I [(aim / /2). This is clearly true if i [ai,m//2] < i" Otherwise, we Eaim j== /2] |F n Wetil 2 20 because + di,m S k and therefore + /21 2m/.m/ By our assumptions about f. we have faat.m/ S 20
have
Σ f5.m F Witsl= 2
1=
[W++
So, have the following lower bound on v7H):
k
m(H)
2
Σ Σ
f(ai.m/2).
m= i
By convexity of this lower bound is smallest if all at" are the same, ie., equal to the total rank
divided by Q Σm m 1Qml and then f faiim/ = my ((2/QQ for each and m. Combining equation and equation we get
log k
rank(W.))
Σ 5
Clam SQ.
(HH) Q
2
m=1 m=1iEQm
WELL-SSPPARATED QUERIES TO THE PREDICTOR
4.1 MTS
We consider the setting when we are able to receive prediction once every time steps, for some parameter a E Without loss of generality, we assume that T multiple of a. In time steps ia, where = 1, 1,..., T, a, we receive a prediction p; E M. State p; itself might be very bad, e.g. lin (Pt) might be infinite. We use work functions to see whether there a more suitable point nearby pi.
Work functions. Consider an MTS on metric space M with starting state E M and sequence of cost functions ,,,...,rr Er. For each time step = l...., T and state x E M, we define a workffucctinn
Wc (x) min (d(ye, x) + Σ dvvi + ((x))),
1=1
where the minimum is taken over all ....... Dt such that yo zo. In other words, it is the cheapest way to serve all the cost functions up to time and end in state z. Work function is a major tool for design of algorithms for MTS and satisfies the following property.
Observation 4.1. For any x, E M and any time t. we have wy wx(x) & wr(y) + d(y, x).
This holds because one way to serve the cost functions eI,..., & is to follow the best solution which ends state y and then move to æ. If w. (p;) = w. (v) + d(y, Pt). we can see that p; is not a very good state, since the best solution ending in Pa goes via y. We say that p. is supported by y.
Algorithm of Emek et al. 22099). Algorithm 3 was proposed by Emek et al. (2009) in the context of advice complexity. It receives the state of offline optimum algorithm every time steps.
4.2 ALGORITHM FTSP
Given q-11 and 4 for = 1)a 1,...,ia, ia, we define
wf;(x) = min (dleinn.))) +
Σ
d(Fz-1, + +85(15)
(=(t1)a++1
12

---

Published as a conference paper at ICLR 2024
Algorithm 3: One cycle of algorithm by Emek et al. (2009)
== reported state of OFF at time ia;
j 0, 0:
for 1 = in ,,..., (i 1)a do
2/ := arg
25) {d(z, Z1-1) +(()));
while + d(e,, x4t) + (x/) > 2 do
j 2 j:
F = arg min xc 2/) (d(z R4-1) (x));
2t = 2 c = d( 24) (xx);
where the minimum is taken over 1(j-1)a:...... Via M such that 2(i-1)a = qi-1. In fact, the work function at the end of an MTS instance with initial state di-1 and request sequence & for t = (i- 1)a + l,..., ia. Instead ps, we choose point
{ wf,((z) wfi(x) = wf((p:) - d(r, -a(,,)))((,.pp))) dlc.
arg min REM
ie., the "cheapest" state supporting p. in wf.. After computing we run one cycle of Algorithm This algorithm which call "Follow the Scarce Predictions" (FtSP), is summarized in Algorithm
Algorithm 4: FtSP
for i ,,. T/a do
receive prediction p::
use to compute q;: run one cycle of Algorithm 3 starting at g::
Let Q denote the best (offline) algorithm which located at gi at time step each i 1,..., TTa., We have
T/a
cost Q)) = Σ (g:(
We can relate the cost of Q to the prediction error using the following lemma. Together with Proposition 2.5 gives bound
cost(ALG) S ((F) +2n),
implying Theorem 1.3
Lemma 4.2. Let OFF be an arbitrary offline algorithm and o, denote its state at time io for i= 1-.,.../// IfQ Q was computed from predictions Pt.-...PT /or we have
cost(Q) < OFF +2m
where 11 ΣTi d(ps, ox) is the prediction error with respect to OFF.
Proof. Denote A; algorithm which follows the steps of Q until time ia and then follows the steps of OFF. We have
cost(A,) & cost (A, + wf,
wf, + d(gs, 0z)
because both A; and A are at fi-1 at time (i - 1) 1)a, and A;-1 then travels to o; paying wfz(ox) while A; travels ds ia paying wfr(g:) and its costs after ia will be by at most d(g;, 0:) larger than the costs of A,
By Observation 4.1 and the choice of qi, we have
(fx(os) 2 wf.(pt) d(os, pi) wl((g:) d(g..p d(or,p)).
13

---

Published as a conference paper at ICLR 2024
Combining the two preceding inequalities, we get
cost(A.) I cost(Ai-i) + wf((q:) (f)
+ ddoo, pt) - d(ps, 9.) + oi)
(o,s(AA,1)) + 2d(o,, Pt);
where the last step follows from the triangle inequality.
Since OFF Ao and Q Ar we have
Tía
Q OFF +2 Σ d(o..p)) = OFF +2n.
4.3 CACHING
Follower cannot maintain 1-consistency in this setting, For the sake of theoretical bound, we can do the following: We serve the whole input sequence by subsequent phases of Robust, which -oosssssttt with F chosen in such a way that the arrivals in F are separated by at least a. We prove the following replacement Proposition 3.11
Proposition 4.3.
log
1-1 (n(Ht)
rank(W.) 22 52)
Proof. We rearrange the sum of ranks in the following way. We define Lm = fil rank(W,) 2 m] Qm {il rank(W,) m and rank(W;+1)) :+1) m], and ai,ms such that L,n. = UsERm ( ai.m for each We write
ran)(W;))
Σ
Lm
a.m-
(10)
m=
(an)(W.) |FN,: (Lemma 3.9 which allows us to decompose
On the other hand, we can write 1 the total prediction error T7(H) ) as follows:
m==
as.m
n(H)
Σ
Σ
FnWl
Σ
Σ
F
FoWeyl
fELm
j=1
Let it denote the first window such that W.-1 f(i) -(i--1))
- 1). If i + aim < i", then
Ejer |F A Witj f(i + ai,m) f(i)= (ai,m) by convexity of f. If this is not the case, claim that Ejer Fn a (((aimm/2)
aiam
if + [amm/2]] < :²: we have
aa /2]
IFWW44
Σ
IF flaim//2
Otherwise: we have
64.m
Ri.m
FnW
FOW
14
Wi+sl 2 22..m/2 2 a- faa.m(
a
j=[oem/21
1=
[a..m/2
By assumptions about saying that f(ai,m/ 20.
14

---

Published as a conference paper at ICLR 2024
So, we have the following lower bound on (7H):
an(H) H)) 2
Σ
flas.m/2)
(11)
m== kE
By convexity of f. this lower bound is smallest if all at" are the same, i.., equal to (H) divided by Q -_m Qml and then faassm// - an(H)) for each and m. Combining equation 10 and equation 11
we get
log k
ran
Σ
Σ
ds.m
SQ. 8-
2
2
m=
im
Using the proposition above in Equation equation the proof of Lemma 3.3 gives us the following smoothness bound:
Lemma 4.4. Denote X; = H HJ U H,, During the phase H, Robust, receiving at most
prediction in time steps incurs the cost
aml H.)
(HA) O(1)f
A (X,).
A (X.)
Theorem 1.5 follows from summation of the bound above over all phases of Robust and concavity of f as in proof of Theorem 1.1
EXPERIMENTS
We perform an empirical evaluation of our caching algorithm F&R on the same datasets and with the same predictors the previous works (Lykouris and Vassilvitskii 2021 Antoniadis et al. 2023 Im
ct al. 2022). We use the following datasets.
BrightKite dataset (Cho al. 2011) contains data from certain social network. We create a separate caching instance from the data of each user, interpreting check-in locations as pages. We use it with cache size 10 and choose instances corresponding to the first 100 users with the longest check-in sequences requiring at least 50 page faults in the optimal policy.
CitiBike dataset contains data about bike trips in a bike sharing platform CitiBike We create caching instance from each month in 2017, interpreting starting stations of the trips as pages, and trimming length of each instance to 25 000. We use it with cache size k 100.
Some of the algorithms in comparison next-arrival predictions while F&R action predictions that can be generated from next-arrival predictions. Therefore, we use predictors which predict the next arrival of the requested page and convert it to action predictions. This process was used and described by Antoniadis et al. (2023) and we use their implementation of the predictors. Our algorithm then provided limited access to the resulting action predictions while the algorithm of Im et al. (2022) has limited access to the original next-arrival predictions.
Synthetic predictions: compute the exact next arrival time computed from the data and add noise to this number. This noise comes from a log-normal distribution with the mean parameter μ = and the standard deviation parameter a. We use [0, 50).
PLECO predictor proposed by Anderson et al. (2014): This model estimates the probability p of page being requested in the next time step and interpret this as a prediction that the next arrival of this page will be in 1/p time steps. The model parameters were fitted to BrightKite dataset and not adjusted before use on CitiBike.
POPU - a simple predictor used by Antoniadis et al. (2023): if page appeared in p fraction of the previous requests, we predict its next arrival in 1/p time steps.
15

---

Published as a conference paper at ICLR 2024
1.3
Competitive ratio
LRU
1.2
Marker
FiP
AQ_b2
1.1
FIPM
T&D
F&R
1.0
0
10
20
30
40
50
Noise parameter a of the synthetic predictor
Figure 1: BrightKite dataset with Synthetic predictor: competitive ratio
In our comparison, we include the following algorithms: offline algorithm Belady which we use to compute the optimal number of page faults OPT, standard online algorithms LRU and Marker (Fiat et al. 1991). ML-augmented algorithms using next arrival predictions L&V (Lykouris and Vassilvit
skii 2021p, LMark and LnonMark (Rohatgi 2020). FtPM which, each step, evicts an unmarked page with the furthest predicted next arrival time, and algorithms for action predictions FtP and T&D (Antoniadis al. 2023). We use the implementation of all these algorithms published by Antoniadis
et al. (2023). We implement algorithm AQ (Im et al. 2022) and our algorithm F&R.
Notes on implementation of F&R. We follow the recommendations Section except that Follower switches to Robust whenever its cost is = 1 times higher compared to Belady in the same period. With higher a, the performance
F&R approaches FtP on the considered datasets. With k 10 (BrightKite dataset), we use F [1, 6, 9) corresponding to f(i) i. Note that, with such small k. polynomial and exponential f would also give a very similar F. With A = 100 (CitiBike dataset),
exponential f(i) 2 - 1. With a-separated queries, Follower uses LRU heuristic when prediction is unavailable, and Robust ignores F, querying the predictor at each page fault separated from the previous query by least time steps.
Results. Figures [ and 3 contain averages of 10 independent experiments. Figure shows that the performance of F F&R with high-quality predictions is superior to the previous ML-augmented algorithms except for FtP which follows the predictions blindly and is also 1-consistent. With high the performance of T&D becomes better. This is true also for F&R with F = [1..10], suggesting that T&D might be more efficient in using erroneous predictions. Figure Souure@]shone shows the total number of times algorithms query the predictor over all instances. Response such query a single page missing from predictor's ' cache in the case of F&R and T&D and next arrival times of 6 pages in the case of AQ_ b. Note that FtPM equivalent to the non- non-parsimen con-parmmmoiouss version of AQ with F F&R makes the smallest number of queries: with perfect predictions, it makes exactly OPT queries and this number decreases with higher as F&R spends more time Robust.
Figure 3 shows that F&R performs well in regime with a-separated queries. While the performance of FiPM with POPU predictor worsens considerably towards Marker already with a = 5, the performance of F&R. worsens only very slowly. On CitiBike dataset, it keeps its improvement over Marker even with a = 20 (note that we use & = 100 with this dataset). Predictions produced by PLECO seem much less precise suggested by FtP with PLECO being worse than Marker and smaller number of such predictions either improves (AQ, FtPM) or does not affect performance (F&R) of considered algorithms.
Figures 4 and 5 complements the comparison of F&R to existing ML-augmented algorithms for With smaller a, again demonstrates the better
paging by including those omitted in Figure [
16

---

Published as a conference paper at ICLR 2024
45000
Number of queries predictor
40000
35000
30000
FtP
FtPM
AQ_b2
25000
T&D
F&R
10
20
50
Noise parameter a of the synthetic predictor
Figure 2: BrightKite dataset with Synthetic predictor: number of used predictors
Dataset
Predictor
Marker
F&R al
F&R a2
F&R a3
F&R a5
F&R a8
F&R 22R
CitiBike
POPU
1.862
1.800
1.802
1.802
1.802
1.803
1.803
CitiBike
PLECO
1.862
1.878
1.878
1.878
1.879
1.879
1.879
BrightKite
POPU
1.333
1.320
1.328
1.332
1.336
1.337
1.341
BrightKite
PLECO
1.333
1.371
1.374
1.376
1.377
1.378
1.378
Dataset
Predictor
T&D
FiP
FiPM_al
FiPM_a5
AQ_b8
L&V
LMark
LnonMark
CitiBike
POPU
1.776
1.739
1.776
1.833
1.782
1.776
1.780
1.771
CitiBike
PLECO
1.847
2.277
1.877
1.866
1.875
1.877
1.876
1.863
BrightKite
POPU
1.276
1.707
1.262
1.306
1.263
1.262
1.264
1.266
BrightKite
PLECO
1.292
2.081
1.341
1.337
1.342
1.340
1.337
1.333
Figure 3: Competitive ratios with predictors POPU and PLECO
17

---

Published as a conference paper at ICLR 2024
1.3
Competitive ratio
1.2
LRU
Marker
FtP
1.1
L&V
LnonMark
F&R
1.0
10
20
30
40
50
Noise parameter of the synthetic predictor
Figure 4: BrightKite dataset with Synthetic predictor: competitive ratio
45000
Number of queries to the predictor
40000
35000
30000
FtP
L&V
25000
LnonMark
F&R
0
10
20
30
40
50
Noise parameter of the synthetic predictor
Figure 5: BrightKite dataset with Synthetic predictor: number of used predictions
18

---

Published as a conference paper at ICLR 2024
1.30
1.25
Competitive ratio
LRU
1.20
Marker
FiP
1.15
T&D
1.10
F&R_al a
F&R a2
1.05
F&R_a _a
F&R a5
1.00
0
10
20
30
40
50
Noise parameter of the synthetic predictor
Figure 6: BrightKite dataset with Synthetic predictor: competitive ratio
consistency of F&R. With higher a. F&R achieves performance comparable to both L&V and LnonMark, while using a smaller number of predictions. We have decided not include L.Mark because its performance as well number of predictions used were almost the same as of LnonMark. Note that, in the case of both algorithms, the number used predictions is equal to the number of clean arrivals and therefore it does not change with the prediction error.
Figures 6 and ssows shows performance F&R regime with a-separated queries for different values of a. It shows significant loss of consistency already with = 2 compared to a 1. However, with higher noise parameter a, the difference performance does not seem large. In this regime, the focus is the gap between predictor queries rather than the total number of queries: F&R queries a predictor at each page fault separated from previous query by at least a time steps. However, we decided include also the plot of the total number of queries (Figure 7 because shows that with > 20, F&R with = 1 uses a smaller number of predictions than with while maintaining better performance. This suggests that the freedom choose the right moment for query might be more important for the performance than the total number of used predictions.
and even a = 3,
Figure X shows experiments with a probabilistic predictor on the BrightKite dataset. this setting, we consider predictor that evicts the page requested furthest in the future with a given probability 1- p. On the other hand, evicts a random page with probability p. The horizontal axis corresponds to the probability p. We can observe that better consistency of our algorithm compared to T&D is visible for p up to 0.4.
Each plot and table contains averages of 10 independent experiments. We have seen standard deviations at most 0.004 the case figures 6. 0.0015 for Figure CitiBike dataset and 0.0025 BrightKite dataset, and 300 for figures 7 counting numbers of used predictions.
CONCLUSIONS
We present algorithms for MTS and caching with action predictions working in the setting where the number of queries or the frequency of querying the predictor are limited. We have shown that one achieve theoretical well empirical performance comparable to the setting with unlimited access to the predictor, possibly enabling usage of precise but heavy-weight prediction models in environments with scarce computational resources.
19

---

Published as a conference paper at ICLR 2024
45000
Number queries to the predictor
40000
35000
30000
FIP
T&D
25000
F&R_aT
F&R_a2
20000
F&R_a3
F&R_aS
15000
10
20
30
40
50
Noise parameter of the synthetic predictor
Figure 7: BrightKite dataset with Synthetic predictor: number of used predictions
1.4
1.3
Competitvee ratio
1.2
LRU
1.1
Marker
FIP
T&D
1.0
F&R
0.0
0.2
0.4
0.6
0.8
1.0
Probability Erao
Figure 8: BrightKite dataset with probabilistic predictor: competitive ratio
20

---

Published as a conference paper at ICLR 2024
7 LOWER BOUNDS
7.1 CACHING
Proof of the following proposition can be found in (Borodin and El- Yaniv 1998 Theorem 4.4).
Proposition 7.1 ((Fiat et al. 1991]). For any randomized algorithm ALG for caching there is pages
input instance on universe of k ++1 pages such that the expected cost of ALG more than In l times the cost of the offline optimal solution.
For given algorithm, it constructs an instance consisting of marking phases, each with a single clean page such that the optimal algorithm pays 1 and the online algorithm pays at least In k.
Imagine an algorithm receiving at most 0.5 OPT predictions during this instance. Then, there must be least 0.5 OPT phases during which the algorithm receives no prediction. cost is at least in each such phase, giving total cost 0.5 OPT In k.
Theorem 1.2 is implied by the following more general statement with 1 and d =
Theorem 7.2. Let e and d 2 be constants. Any (cff-((pf (n) -smooohh algorithm for caching with action predictions has to use at least f(c
d) OPT predictions.
Proof. Consider a fixed algorithm accepting action predictions. Choose T long enough, an arbitrary prediction for each time step f 1..... T, and give them to the algorithm at time O. Having the predictions already, this algorithm becomes a standard randomized algorithm which does not use any further predictions. We Proposition 7.1 to generate instance such that [[ALG]] > OPT In k where ALG denotes the cost of the algorithm with predictions generated in advance. It clear that these predictions, generated before the adversary has chosen the input instance, are useless, not helping the algorithm to surpass the worst-case bounds. However, since the universe of pages has size only k 1, each of the predictions can differ from optimal algorithm by at most one page.
we want to have
B|ALG] OPT
S of
OPT ) + d, then we need
E[ALG]
d) > {
lnk
-d)
OPT
COPT
Since every prediction has error at most 1, we need to receive at least 2 f(c-1I1 In d) OPT predictions.
L
7.2 MTS
Antoniadis al. 2003) showed the following lower bound smoothness of algorithms for general MTS with action predictions.
Proposition 7.3 (Antoniadis al. (202)). For nj 2 O and E N, every deterministic (or random- ized) online algorithm for MTS on the repoint uniform metric with access action prediction oracle with error at least 1) with respect to some optimal offline algorithm has competitive ratio Ω (min {a,,, + oPT)). }), where a,, (n) (or a,, (log n)) is the optimal competitive ratio of deterministic (or randomized) algorithms without prediction.
We use this proposition prove the following theorem from which Theorem 1.4 directly follows.
Theorem 7.4. For rj 0 and E N, every deterministic (or randomized) online algorithm for MTS on the n-point uniform metric with access to an action prediction oracle at most once in a time sleps with error at least y with respect some optimal offline algorithm has competitive ratio Ω (min { (0 1 + an }), where a,, = ((n) (or a, = O(og n)) is the optimal competitive ratio of deterministic (or randomized) algorithms without prediction.
Proof. We extend the (n - 1)-pt uniform metric from the proposition above by single point Poo whose cost will be +00 at each time step, ensuring the optimal algorithm will never located there. Consider fixed algorithm and predictor producing at most prediction in time steps with the total prediction error n). By issuing prediction Poo in all missing time steps, we complete predictions for each time step with error at least 1/ an.
21

---

Published as a conference paper at ICLR 2024
By proposition above, the algorithm with completed predictions has competitive ratio least
2 min {an-1,
of )FT)
s2 min {an, , 1 )PT))
since On and an-1 differ by at most constant factor.
8 FITF ORACLE
In this section we work with predictor which tells us which page in our current cache will be requested furthest in the future, we call FitF page. Note that this is not the same as the predictions considered in Section 3 where we receive page not present in Belady's cache. Belady evicts FitF page from its current cache content which may be different from the FitF page from current cache content of our algorithm. Prediction error is the total number of times the predictor reports an incorrect FitF page.
We split our algorithm into Follower and Robust part. The Follower (Algorithm 5 checks each page fault whether Belady starting at the same time with the same cache content also has page fault. If yes, it evicts page reported by the predictor. Otherwise, it switches to the Robust part (Algorithm 6)
Algorithm 5: Follower with FitF oracle
P starting cache content;
2 foreach pugefault do
Compute Belady for the sequence from the beginning of this execution starting with P: Belady has page fault as well then
p page in the current cache chosen by the predictor; evict p:
else
Run one phase of Algorithm starting with the current cache content;
Lemma 8.1. Consider one execution of Algorithm denoting a the request subsequence and yp the the same cost
number of incorrect predictions received during this execution. Algorithmmppon Belady serving a and starting with cache content P. There is a lie-breaking rule for Belady such that the cache contents of both algorithms after processing a differ in at most &p pages.
Proof. Whenever the algorithm has page fault and Belady not, the execution of Algorithm terminates. Therefore, both algorithms have the same cost during the execution.
Denote A and B the cache contents of our algorithm and Belady respectively. We choose the following tic- breaking rule for Belady: whenever the algorithm evicts p E A n B which is no more requested in a, Belady evicts predicted page E i and Belady evicts a different page g E A n B. This can happen only if the next request of p comes earlier than q by the tie- tie-breaking rule above. Since p, q A, the oracle made a prediction error.
well. The size of A B increases only when the algorithm evicts
Robust part (Algorithm 6) uses a parameter which controls the number of predictions used during its execution. It runs for duration of single marking phase split into log & windows, as in Section 3 making sure that the number predictions received each window at most the number clean pages received far. Evictions of random unmarked pages prediction. At the end, it loads all marked pages. This is to ensure that the difference between the optimal and algorithm's 's cache content can be bounded by the cost of the optimal algorithm during the phase (using Observation 2.2h instead of accumulating over repeated executions of Follower and Robust.
used at page faults with available
Lemma 8.2. Consider execution of Algorithm 6 during which it receives &p incorrect predictions. The expected cost incurred by Algorithm is at most 2A B + 3:p(1 + b-1 log k). where B denotes the cost incurred by Belady starting the time with the cache content.
22

---

Published as a conference paper at ICLR 2024
Algorithm 6: Robust with FitF oracle
P == starting cache content;
== [ = k: 2 + for j = log k log k + 1 W; St + 1] for i
// Split the phase into
windows
foreach pagefault time during the phase do :unmberr of clean pages which arrived so far; number of received predictions in the phase is less than bog then if number of received predictions in this window is less than then
p = page in the current cache chosen by the predictor; evict p:
else
11
evict a random unmarked page;
12
Once phase has ended, load all marked pages to the cache and run Algorithm 5
Proof. There are three kind of page faults:
1. evicted page is chosen by the predictor
2. requested page was chosen before by the predictor, evicted page was chosen at random
3. both evicted and requested pages were chosen at random
In the worst case, we can assume that once we run out of budget for predictions, all incorrectly evicted pages are requested page faults of type 2 and returned to the cache. Now, let g denote the number of pages evicted due to correct predictions they are not going to be requested in this phase anymore (Observation (.3)). All other evicted pages are chosen uniformly at random among unmarked pages which were not evicted due to correct predictions. So, until another batch of page faults of type 1, we have only page faults on arrivals and the probability of a page fault on arrival a is at most
Ca g
1:
(a c.)
where is the number of clean pages until arrival and A: (a cx) is the number of unmarked pages, at most of them were evicted due to correct predictions.
We count the number of page faults in window for i 1, ..... log k + 1. We denote m, the number of page faults of type and resulting into eviction of gi correctly predicted pages. Then, by our assumption, we have m, 9: page faults of type 2. The expected number of page faults of type depends on when do types and happen. In the worst case, they all happen in the beginning of W; well all arrivals of clean pages. We consider three cases.
Case A. Prediction budget was not depleted, there were only evictions type 1.
AA(W)) = m; 9s + Dt-
Case B. There were m, = C++1 predictions during W2 and we have ;i = Ci+1 9:- After page faults of type 2, there are at most C++1 Sr randomly chosen unmarked pages evicted. Therefore, the expected number of page faults of type 3 is at most
Σ =EW;
C 9a
Σ aEW;
Ci+1 9i
(a
C4+1) -
k - (a - Ci+1) - 9b.
C+11 9i
C.+1 9b
C.+1 9t.
k
2
k/2
neW.
Therefore, counting evictions types 1, 2, and 3, we have
A (W,) & (4p; 9i) + si (G+1 9t) S gi + 3:p-
23

---

Published as a conference paper at ICLR 2024
Case C. There were bc1+1 predictions since the beginning of the phase. We have my I C++-1 and C++1 94 S i (bc,+1 9b) S top where sp is the total number of incorrect predictions received since the beginning of the phase. We have
A (WW))) ci+i + (ci+1 - g6) + (c141 - gi) S gs + 3(0+1 - 9i).
which is at most 9i + b.pbb.
Now, the sum of costs over all the windows is at most
E9 Σ 3pp + Σ
2c 3p +
34 log
b
where c c= Ei S A., because consider Belady starting with the same cache content the algorithm which does not contain the clean pages.
Theorem 8.3. Let b E (I,.... log k} be a parameter. During a request sequence with optimum cost OPT, our algorithm receives at most (b) OPT predictions and its expected cost is always bounded by (log k) OPT. If only ip predictions are incorrect, its expected cost at most
2
+ OPT
(4+ 14-36-1- 36 log k)) OPT.
Moreover, if = 0, its cost is equal to OPT.
Proof. We split the time horizon into intervals corresponding exccutions of Follower and Robust. For each interval i, we denote şú the number of received incorrect predictions, A the cost incurred by Belady started with the same content as our algorithm and A the cost incurred by the optimal solution during interval i. We denote F' the set of intervals during which Follower was executed and R the set of intervals during which Robust was executed. We also define 0 E R an empty interval in the beginning of the request sequence with A A 0.
In order to prove bounds on robustness and number of used predictions, we provide relations between A and A independent of yp. For each F, we have 1 E R. Interval 1 is marking phase and Robust has all marked pages in the cache at the end (Lemma 8.2). By Observation 2.2 the starting cache content of Follower in interval differs from optimal cache in most A pages. Therefore, we have
A < - + A
ViEF.
(12)
For each i R. we have i -- 1 E F and i 2 E R. By Observation 2.4 the difference between the cache of Follower and optimum increases during interval 1 by at most A Since the starting cache of Follower interval - 1 differs from optimal in A pages, the starting cache of Robust in interval i differs from optimum by at most A + - Therefore, we have
A S A Ao A
ViE
(13)
Using equations equation 12 and equation 13
we can bound the number of used predictions as
Σ
A
Σ
6A S 3bOPT.
iEF
SR
Since A,, for F, and 4p, S 6A
for i R, we have the following robustness bound:
ALG <
Σ A
Σ
(A
+ p: 36-1 log k:)
F
<
Σ A B
Σ
B
(1 36 log k)
F
ER
< OPT
Ollg
where the last inequality follows from equation
12
equation
13 and b log k.
24

---

Published as a conference paper at ICLR 2024
Now, analyze smoothness. We can bound A, A by the difference between optimal and
algorithm's 's cache in the beginning of the interval i. This at most - for each E R (Lemma
and at most A for each i E F by equation 12 Lemmas 3.1 and 8.2 imply
ALG S
Σ APP
Σ
(24
+ 36-3-11 log k))
iEN
Σ iEF
(A) A 10
Σ (4, - PP-1 + + 3b log
iR
2PPT + 4 + 36- log k).
I-consistency of our algorithm can seen from the fact that each execution of Robust is triggered by an incorrect prediction. Therefore, with perfect predictions, only Follower is used and behaves the same as Belady.
REFERENCES
[1] A. Anderson, R. Kumar, A. Tomkins, and S. Vassilvitskii. The dynamics of repeat consumption. Proceedings of conference World Wide Web '4, pages 419-430, 2014. doi: 10. 145/2566486. 2568018.
[2] A. Antoniadis, Gouleakis, Kleer, and P. Kolev. Secretary and online matching problems with machine learned advice. In NeurlPS, 2020.
[3] A. Antoniadis, C. Coester, M. Eliáš, A. Polak, and B. Simon. Leaming-augmmntted dynamic power management with multiple states via new ski rental bounds. In NeurlPS, 2021.
[4] A. Antoniadis, J. Boyar, M. Eliáš, L. M. Favrholdt, R. Hoeksma, K. S. Larsen, A. Polak, and
B. Simon. Paging with succinct predictions, 2022.
[5] A. Antoniadis, P. J. Ganje, and G. Shahkarami. A novel prediction setup for online speed- scaling. In SWAT, volume 227 L/Plcs, pages 9:1-9:20. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2022.
[6] A. Antoniadis, C. Coester, M. Eliáš, A. Polak, and B. Simon. Online metric algorithms with untrusted predictions. ACM Trans. Algorithms,, 19(2), apr 2023. ISSN 1549-6325. doi: 10.1145/358268, URL http://:///aa........o0...0.....
[7] Y. Azar, S. Leonardi, and N. Touitou. Flow time scheduling with uncertain processing time. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1070-1080, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450380539,
doi: 10.1145/3403325.4551222 URL /ttps://doi.ors:
1145/3406325 0001//4446325333552222 3451023
[8] Y. Azar, Leonardi, and N. Touitou. Distortion-obliviors algorithms for minimizing flow time. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, Jamuary 9 12, 2022, pages 252-274, SIAM, 2022. URL http:s:///oi... doi. org/ 11..111.1111111 9781611977073..
[9] É. Bamas, A. Maggiori, L.. Rohwedder, and O. Svensson. Learning augmented energy mini- mization via speed scaling. In NeurIPS, 2020.
[10] N. Bansal, C. Coester, Kumar, M. Purohit, and Vee. Leaming-augmented weighted paging. In SODA, 2022.
[11] Y. Bartal, B. Bollobás, and M. Mendel. Ramsey-type theorems for metric spaces with applica- tions to online problems. J. Comput. Syst. Sci., 7295):890-9 2006.
[12] L. A. Belady. A study of replacement algorithms for virtual computer. IBM Syst. J. (2)7781001 1966. doi: 10. 10.1 10.11./...55000077... /
0078
25

---

Published as a conference paper at ICLR 2024
[13] G. Bernardini, A. Lindermayr, A. Marchetti- Spaccamela, N. Megow, L. Stougie, and M. Sweer- ing. A universal error measure for imput predictions applied to online graph problems. CoRR. abs/2205.12850, 2022. doi: 1144850062Xx1.2220.1128888 URL
48550/arXiv 2205. 12850
[14] A. Blum and C. Burch. On-line learning and the metrical task system problem. Mach. Learn., 39(1):35-58, 2000. doi: 10. 10.102//A110076628886668
[15] H. Böckenhauer, D. Komm, R. Královič, R. Královič, and T. Mömke. Online algorithms with advice: The tape model. Inf. Comput., 254:59-83, 2017.
[16] A. Borodin and R. EI- Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. ISBN 978-0-521-56392-55.
[17] A. Borodin, N. Linial, and M. E. Saks. An optimal on-line algorithm for metrical task system. J. ACM, 39(4):745-763, 1992. doi: 10.1 10.1145/146585 11445//46585.46668 146588.
[18] J. Boyar, L. M. Favrholdt, C. Kudahl, K. S. Larsen, and J. W. Mikkelsen. Online Algorithms with Advice: A Survey. ACM Computing Surveys, 50(2):1-34, 2017. Article No. 19.
[19] J. Boyar, L. M. Favrholdt, and K. S. Larsen. Online unit profit knapsack with untrusted predictions. In SWAT, volume 227 of L.Ples, pages 20:1-20:17. Schloss Dagstuhl Leibniz- Zentrum für Informatik, 2022.
[20] S. Bubeck, M. B. Cohen, J. R. Lee, and Y. T. Lee. Metrical task systems trees via mirror descent and unfair gluing. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 89-97, 2019. doi: 10.1137/1.978161119954444 https: // /oi wtw.ooo.oggiinoo www.oogg//...... 113 011.1//1911111999998
URL
[21] J. Chen, S. Silwal, A. Vakilian, and F. Zhang. Faster fundamental graph algorithms via learned predictions. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 3583-3602. PMLR, 17-23 Jul 2022. URLpttps:: hw..ttpps:/prroceiiingg https:///ccceeeeengg.. mlr wrw.prresssss wwt.:2/ccccccecccccaceeaea
[22] J. Chledowski, A. Polak, B. Szabucki, and K. T. Zolna. Robust learning- augmented caching: An experimental study. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 1920-1930. PMLR, 2021. URL ( //proceedings.o mlr www.ppes//vvii
html
[23] E. Cho. S. A. Myers, and J. Leskovec. Friendship and mobility: user movement in location-based social networks. In Pfooeedigggoo SGKXXD 102-0000000000000000000000000000 2011. doi: 145124//0020408, 2020579. htt.a///ww/gaaa....aaaaaa//a///a
[24] CitiBike. Citi bike trip histories.
[25] M. Dinitz, S. Im, T. Lavastida, B. Moseley, and S. Vassilvitskii. Faster matchings via learned duals. NewrlPS, pages 10393-10406, 2021.
[26] S. Dobrev, R. Královič, and D. Pardubská. Measuring the problem-relevant information in input. RAIRO Theor. Inf. Appl., 43(3):585-613, 2009.
[27] M. Drygala, S. G. Nagarajan, and O. Svensson. Online algorithms with costly predic- tions. In F. Ruiz, J. Dy, and J.-W. van de Meent, editors, Proceedings of The 26th In- ternational Conference on Artificial Intelligence and Statistics, volume 206 of Proceed- ings of Machine Learning Research, pages 8078-8101, PMLR, 25-27 Apr 2023, URL html
https::/prroceddnngg mll. http:///ccaaaaain......p.p/pr//a
[28] P. Dütiing, S. Lattanzi, R. P. Leme, and S. Vassilvitskii. Secretaries with advice. In EC, pages 409 429. ACM, 2021.
[29] Eberle, A. Lindermayr, N. Megow, L. Nölke, and J. Schlöter. Robustification of online graph exploration methods. In AAAI, pages 9732-9740. AAAI Press, 2022.
26

---

Published as a conference paper at ICLR 2024
[30] M. Eliáš, H. Kaplan, Y. Mansour, and S. Moran. caaaaiinn-uggmenten algorithms with explicit predictors, 2024. URLptttss://// /arvvv. www.wwwwww..aaaaaaaa.. orgg/bs///40..... 07413
[31] Y. Emek, P. Fraigniaud, A. Korman, and A. Rosén. Online computation with advice. In Automata, Languages and Progrumming, 36th International Colloquium, ICALP 2009, Pruceedings, Part 1. volume 5555 of Lecture Notes in Computer Science, pages 427-438. Springer, 2009. URL
https://des www.do...gggoooooooooo 10110..11079770 37 02927-3222222 106162666666660001110333-11_6661
[32] J. C. Ergun, Z. Feng, S. Silwal, D. P. Woodruff, and S. Zhou. Learning-augmenter k-means clustering. In The Tenth International Conference on Learning Representations, ICLR 2022. OpenReview.net, 2022. URL httttp:://ppenzeviettt
[33] A. Fiat, R. M. Karp, Luby, L. A. McGeoch, D. D. Sleator, and Young. Competitive paging algorithms. Journal of Algorithms, 12(4):685-699) 1991. ISSN 0196-6774. doi: htps://doi.org/10.1000 0111:/00000000006607799999000010 com/
URL //wp::///wwww http::///ww..ccceeeeeeee.. www.::/..iineeeiie......
[34] A. Gupta, D. Panigrahi, B. Subercaseaux, and K. Sun. Augmenting online algo- rithms with warressioonaaccurate predictions. In S. Koyejo, S. Mohamed, A. Agar- wal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems. volume 35, pages 2115-2127. Curran Associates, Inc., 2022. URL hww./tteer/ppcceeennn...eer....o wwtprriipppccpppprrrrppppp sactsper_flleee wwwps//pppe/////222222 (aa053312aa52211111ee555500000e0
[35] J. Hromkovič, R. Královič, and R. Královič, Information complexity of online problems. In MFCS, volume 6281 of LNCS, pages 24-36. Springer, 2010.
[36] S. Im, R. Kumar, M. M. Qaem, and M. Purohit. Online knapsack with frequency predictions. In NeurlPS, pages 2733-2743, 2021.
[37] S. Im, R. Kumar, Petety, and M. Purohit. Parsimonious learning -ugginn-d caching. In ICML, 2022.
[38] Indyk, Mallmann-Trenn Mitrovic, and R. Rubinfeld. Online page migration with ml advice. In G. Camps-Vall F. J. R. Ruiz, and I. Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 1655 1670. PMLR, 28 30 Mar 2022. URL |
//proceedings.o mlr w wtw........//lll./nn............
[39] A. Jain and C. Lin. Back to the future: Leveraging belady's ' algorithm for improved cache replacement. SIGARCH Comput. Archit. News, 44(3):78 89, June 2016. ISSN 0163-5964. doi: 00.1145/007787730000 146. hRRLtttts:
1111111111114 1145/ 11111111117711111 3007787 3001146
[40] Z. Jiang, D. Panigrahi, and K. Sun. Online algorithms for weighted paging with predictions. ACM Trans. Algorithms, 18(4):39:133:22 2022. doi: 10.1145/3548774. URL https:
7 /oii. . org/10. 1145/3548774
[41] T. Kraska, A. Beutel, E. H. Chi, Dean, and N. Polyzotis. The case for learned index structures.
In Proceedings of SIGMOD'JA 18, pages 489-504, 2018. doi: 10.11453183713.319960
[42] S. Lattanzi, T. Lavastida, B. Moseley, and S. Vassilvitskii. Online scheduling via learned weights. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 1859-1877. SIAM, 2020. httppp///oo...rrr/........7.....
114
[43] A. Lindermayr and N. Megow. Permutation predictions for non-clairvoyant scheduling. In SPAA, pages 357-368. ACM, 2022.
[44] A. Lindermayr and N. Megow. Algorithms
with predictions. 2022.
https https:
io
URL
[Online; accessed 8-September-
2022].
27

---

Published as a conference paper at ICLR 2024
[45] A. Lindermayr, N. Megow, and B. Simon. Double coverage with machine-learned advice. In M. Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022. Jamuary 31 February 2022, Berkeley, CA. USA, volume 215 of LIPles, pages 99:1-99:18. Schloss Dagstuhl Lentniz-Zenntru für Informatik, 2022. doi: 11.42300..Pccc..ICS..222222 ITCS 2022.99
URL htt.hh:pp:///oi.... htt.://oorrr111..2//11PPP.....
[46] E. Liu, M. Hashemi, K. Swersky, Ranganathan, and J. Ahn. An imitation learning approach for cache replacement. In Proceedings of the 37th International Conference on Machine Learning. volume 199 of Proceedings of Machine Learning Research, pages 6237-6247 6247. PMIR, 13-18 Jul 2020. URL http:::t https::/prrocedd
ml htt.:/g....es//////...........
iu20f ht.m]
[47] T. Lykouris and S. Vassilvitskii. Competitive caching with machine learned advice. J. ACM, 68 (4):24:1-24:25, 2021.
[48] M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions. In Beyond the Worst-Case Analysis of Algorithms, pages 646-662. Cambridge University Press, 2020.
[49] A. Polak and M. Zub. Seamiin--uugmette maximum flow. CoRR, abs/2207.12911. 2022.
[50] M. Purohit, Svitkina, and Kumar. Improving online algorithms via MI. predictions. In NeurIPS, 2018.
[51] D. Rohatgi. Near-optimal bounds for online caching with machine learned advice. In SODA, 2020.
[52] S. Sakaue and T. Oki. Disrree-conver--alllii-----ee framework for warm-starting algorithms with predictions. CoRR, abs/22055009961 2022. doi: 10.48550krXi...255..996
[53] Z. Shi, X. Huang, A. Jain, and C. Lin. Applying deep learning to the cache replacement problem. In Proceedings of the 52nd Annual IEEE/ACM International Symposium Microarchitecture, MICRO '52, page 413-425, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450369381. doi: 10.1145/3352460.333311
URL https://doi.org:
1145/3352 3358319
[54] D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2):202-208, 1985. doi: 10.1 10.1145/278..27993
[55] A. Wei. Better and simpler luarning-augmentedd online caching. APPROXRANDOM, 2020.
[56] A. Zeynali, Sun, M. Hajiesmaili, and A. Wierman. Data-driven competitive algorithms
for online knapsack and set cover. In AAAI, pages 10833-10841, AAAI Press, 2021.
28

---

Published as a conference paper at ICLR 2024
A COMPUTATIONS FOR TABLE 1
In this section, we present the computations for the numbers of predictions we obtained in Table For f(i) = i and f() i², we have floog k) equal to log and log* à: respectively.
For f()) 2' 1. we identify the first window longer than f(i) f(i - 1). Note that the length of window i k/2' = 2log k and this is equal to the sum of lengths of the windows j > i. The total number of predictions used will be therefore f(i) + 2 k-i For
log vk + 1, we have f()--f(i-1] (i-1) = 2 = 2 log k-1 > 21og k-i Therefore, we use 2 1 + 21og k-i 2 3v h: predictions in each robust phase. Since offline optimum has to pay least 1 per robust phase, we use at most O(Vk) OPT predictions total.
f()) (19--((
For (1) O, we ask for prediction at each arrival of a clean page. The number of queries used will therefore be at most the number of clean arrivals, which is most 2 OPT.
29


Reviews:
[{"review_id": "fgdZnA2Ltn", "reviewer": "Reviewer_dLjd", "summary": "This paper considers the problem of Metrical Task Systems (MTS) under the prediction setting. In the classical MTS problem, the algorithm starts from an initial state (or a point in a metrical space), and the adversary releases a cost function at each time step. After seeing the cost function, the algorithm needs to make a decision at each time: either stay in the same state or move to another state, which is possibly cheap, but some extra moving costs will be charged. In the prediction setting, the algorithm accesses a prediction on future information. In this paper, the prediction is considered the next stage of an optimal algorithm. Unlike other prediction papers, this work investigates how the number of predictions affects the algorithm.\n\nThe main contribution of this work is a learning-augmented framework achieves a good trade-off between the smoothness ratio and the number of predictions. For the Caching problem, this framework achieves a nearly optimal tradeoff. The authors also show that such a framework works for the general MTS problem. Besides this, this work also extends the framework for the setting where the prediction can also be obtained by at least a time step. Finally, the authors verify their algorithm in some datasets.", "questions": "I don't have any specific questions.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strengths:\n\n1. The paper is well-written and well-structured. I appreciate that the authors provide sufficient intuitions on appropriate places, which significantly improves the readability of the paper.\n2. I particularly like the model where the prediction cannot be obtained by at least some fixed time step. This idea seems new and can capture many applications in practice.\n3. The technical contribution is solid. Although the high-level picture of the proposed algorithm follows a typical framework in a learning-augmented area, the algorithm contains sufficient new ideas and analysis.", "weaknesses": "Weaknesses:\n\nI don't see any major weaknesses in the paper. My main concern is that due to its technical nature, one would really be required to check all proofs for correctness. I am unfortunately not able to do that due to the time limit for reviewing. I only checked a few lemmas and I believe they are correct. If all proofs are correct, then I think this is a good paper.", "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": "", "extra_scores": {}}, {"review_id": "BxZT3EQCRs", "reviewer": "Reviewer_NjU5", "summary": "The paper studies the online caching problem and the metrical task system problem which admits online caching as a special case. In the online caching problem, we are given a cache of fixed capacity $k$ and a sequence of online arriving elements, and want to design an online algorithm that decides which elements to keep in the cache and which ones to evict when the cache becomes full. The goal is to minimize the number of cache misses, which occur when an arriving element is not present in the cache. In the metrical task system problem, we are given a metric space $M$ of states and an initial state $x_0\\in M$. At each time step $t$, we receive a cost function $\\ell_t: M \\rightarrow R^+ \\cup \\set{0, \\infty }$ and need to decide which state to move to. When moving to a state $x_t\\in M$, we have to pay $\\ell_t(x_t) + d(x_{t-1},x_t)$. The goal is to minimize the total payment. To see that online caching is its special case, we can view the elements kept in the cache as the state in a metric space. \n\nThe two problems are considered in the learning-augmented setting, where we can access imperfect predictions about the future.  More precisely, the authors assume that at any time $t$, if they query a predictor, the predictor returns a prediction $\\hat{s}_t$ of the state that the optimal solution (or a good approximation solution) moves to. Since the prediction is imperfect, they define the prediction error $\\eta$ to be the moving distance between the predicted state and the real optimal state. The authors show that for online caching,  there exists an algorithm that achieves $1$-consistency, $O(\\log k)$-robustness, and $O(f^{-1}(\\eta /OPT))$-smoothness within a query complexity at most $f(\\log k)OPT$, where function $f( \\cdot )$ is an increasing convex function with $f(0)=0$ and $f(i)\\leq 2^i-1$ $\\forall i\\geq 0$. For metrical task system, the authors show that there exists an algorithm that achieves a cost at most $O(a) \\cdot (OPT+2\\eta)$ by making a query each $a$ time step. The smoothness lower bounds are further provided in the paper to show the optimality of their results. Finally, the proposed algorithms are evaluated empirically.", "questions": "(1) The key algorithmic idea for algorithm 1 is built on observation 2.1 that Belady is somehow stable. If the predictor simulates other unstable algorithms, is there any non-trivial smoothness bound?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This is a technically solid paper. Online caching and MTS are very classical and important problems in online optimization, and can capture many real-world applications. The paper advances in the direction of augmenting online algorithms by restricted learning. The two problems are good targets since the existence of a robust framework for them alleviates the concern about robustness. The authors show non-trivial trade-offs between the query complexity and the smoothness, which may influence future work in the field of learning-augmented algorithms.", "weaknesses": "One weakness is that the action prediction setting still looks a little bit weird. To me, particularly in online caching, predicting the next arrival time of the current element makes more sense and is more learnable. It seems hard to learn the optimal actions from historical data in practice. But I understand that this is a setting proposed in the previous work, and the local information predictions (e.g. next arrival time) may not help in the restricted-learning setting.", "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": "", "extra_scores": {}}, {"review_id": "S0kwcY6mBd", "reviewer": "Reviewer_bwNg", "summary": "This paper studies online algorithms for caching (and more generally MTS) with predictions. The considered prediction is “action prediction”, which tells what (the ideally optimal) algorithm does. The goal here is not only to achieve a good prediction error vs competitive ratio tradeoff, but also to use fewer predictions, through queries to the action prediction.\n\nThe results look very general and strong. The main results are about caching with size k. It shows for a large class of functions f, the algorithm uses f(log k) * OPT predictions, achieves consistency 1, robustness O(log k) and smoothness O(f^{-1}(\\eta / OPT)), where \\eta is the number of wrongly predicted actions. Furthermore, these bounds are also justified by nearly matching lower bounds.\n\nTechnically, the caching algorithm first tries to follow the prediction, and if the prediction “looks bad”, it switches to a modified Marking algorithm to preserve the robustness. But to preserve consistency, this modified Marking is run for only O(k) distinct requests and will switch back to follow the prediction again. This algorithm is intuitive, but the analysis is very involved, especially to deal with the randomness of the Marking algorithm and to control the number of predictions used.\n\nFor the MTS problem, it does not make much sense to aim for a query complexity bound like f(\\cdot) OPT, and the paper turns to put a constraint that the algorithm can only make a query every $a$ steps, where $a$ is some parameter. This also makes the techniques very different from the caching algorithm.", "questions": "- In Section 1.1, it is not clear enough what \\eta means without reading later parts of the paper, particularly what it means by “total error” (mentioned in the first paragraph of Section 1.1). Some intuitive explanations would be helpful. Furthermore, it may look like the meaning of \\eta is different between Theorem 1.1 and Theorem 1.3, and this should be clarified, too. (By the way, this is not clearly discussed even in Section 2.1.)\n\n- Theorem 1.2: \\eta is not quantified; I guess we should say “for every \\eta > 0”?\n\n- In Section 2.2, it is assumed that the predictor is trying to simulate Belady. Is this without loss of generality?\n\n- In Algorithm 2, is $S$ a set or a sequence? I don’t find S = [ xxx ] a standard notation. Also, S[I] does not look standard, either.\n\n- In Algorithm 2, line 4, is this to define $F$?\n\n- In Algorithm 2, line 4, how is p chosen?\n\n- In Algorithm 2, I find additional whitespace before “;” in lines 6 - 8.\n\n- Section 3, it’s better to give some “comment” in the algorithm (or somewhere in the main text) to describe what F and S stand for.\n\n- Page 6, there’s a paragraph about “implementation suggestions”. This paragraph is not directly related to the proof of the main theorem, so it is slightly out of context. Maybe move it to the end of the section, or somewhere in the experiments section?\n\n- Page 7, 2nd paragraph. What is G_{i, I+1} exactly? In particular, what does “gap” mean? I’m not even sure if this is a number or a subset when I first read it.\n\n- Page 7, 2nd paragraph. What do you mean by “period” X? Maybe you simply say X is a sequence of requests.\n\n- I tried to read the proof of Lemma 3.3, but I didn’t find a clear place for “Robust_f uses at most f(log k) predictions”. Where is it? Also, does this bound depend on the randomness?\n\n\n- Section 5, for the synthetic predictions, why do we consider the log-normal distribution?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- I’m impressed by the results and techniques.\n\n- The paper is very clearly written, and the comparison to previous works is adequate.\n\n- This paper has a very comprehensive discussion of how to potentially implement the predictor and the ways to tune the algorithm for better practical performance — I find this very helpful.", "weaknesses": "- The MTS part does not seem to connect well enough to the rest of the paper which mainly focuses on caching; especially I cannot see the tight relation in terms of algorithms/techniques.\n\n- The experiments only show a marginal advantage over baselines on real datasets.", "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": "", "extra_scores": {}}, {"review_id": "IkgIEtN4z6", "reviewer": "Reviewer_utqC", "summary": "This paper considers online caching and metrical task systems (MTS) in the popular algorithms with predictions framework.  Following recent related work due to Im et al. 2022, they consider reducing the number of predictions utilized by the algorithm.  This paper differs from that one in two respects:\n - This paper considers action predictions as introduced by Antoniadis et al. which are different from the usual notion of \"next-arrival-time\" predictions as used by Lykouris and Vassilvitskii 2021, Rohatgi 2020, and Im et al. 2022.\n- In addition to considering bounded number of predictions as in Im et al. 2022, they also propose studying well-separated queries to the predictions.  In this setting there is a lower bound on the number of time steps between queries to the predictions.  This is motivated by settings where we may not be able to immediately query the prediction.\n\nThe main theoretical results are as follows:\n- An algorithm for caching with robustness $O(\\log k)$, smoothness $O(f^{-1}(\\eta / OPT))$ and using at most $O(log k)OPT$ queries to predictions.  $f$ is an increasing function with some restrictions.  Examples of the relationship for different $f$'s are described.\n- A lower bound of $f(\\ln k) OPT$ queries to the predictor for any algorithm that is $f(\\eta)$ smooth.\n- For MTS, the authors study well-separated queries that arrive once every $a$ steps and give an algorithm with cost $O(a)(OPT + 2\\eta)$ and give a nearly tight lower bound.\n\nTo complement these, several experiments using datasets that have been utilized in prior work are carried out, comparing the proposed algorithm to the algorithms proposed in several prior works.", "questions": "### Major Questions and Comments\n\n- The motivation for well-separated queries is settings in which the waiting for the query to be produced may take a number of time steps to produce.  Have you considered a setting where the prediction queries are explicitly delayed?  For example, based on the state of the algorithm at time $t$, we make a query to the predictor, but the result does not arrive until time $t+a$.  So predicted information is directly more costly in the sense that it may no longer be \"fresh\" or as useful when we receive it.\n- For MTS, you are unable to give a bound on the number of predictions that scales with $OPT$ since the adversary can scale the instance to make $OPT$ arbitrarily small.  Can the absolute number of predictions be bounded?  For example is it possible to use $o(T)$ queries to the predictions for this setting, or is this impossible similar to the lower bound in Theorem 1.4?\n\n\n### Minor Comments\n - First page, third paragraph - \"Online nature of ...\" -> \"The online nature of ...\"\n - Second page, second new paragraph - \"Using method of Blum and Burch ...\" -> \"Using the method of Blum and Burch...\"\n - Several places - In case of caching ...\" -> \"In the case of caching\"\n - Please make general improvements to the grammar.\n - Page 6, first paragraph - \"$f(i) \\leq 2^j - 1$\" - should this be $f(i) \\leq 2^i - 1$?  I don't see $j$ defined nearby...\n - For the synthetic noise a log-normal distribution is used.  I believe you meant the parameters for this distribution are $\\mu = 0$ and $\\sigma \\in [0,50]$.  The mean of a log-normal distribution cannot be 0...\n - In the captions for Figures 1 and 2, please clarify if the standard deviation reported is for the competitive ratio averaged over many trials (and not the noise for the synthetic predictions), and how many trials were used for this average if so.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Developing algorithms which make use of predictions economically is an interesting question that has arisen recently\n- The result for caching gives a nice way of quantifying the trade-off between number of predictions and smoothness through the function $f$, although it is a little more difficult to interpret than say the result in Im et al. 2022.\n- The experimental results are promising", "weaknesses": "- The writing and grammar needs improvement at certain points (see below for more specific comments).", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)