Augmenting Online Algorithms with $\varepsilon$-Accurate Predictions
Authors: Anupam Gupta
Debmalya Panigrahi
Bernardo Subercaseaux
Kevin Sun
Venue: NeurIPS 2022 Accept (2022)

Abstract: The growing body of work in learning-augmented online algorithms studies how online algorithms can be improved when given access to ML predictions about the future. Motivated by ML models that give a confidence parameter for their predictions, we study online algorithms with predictions that are $\epsilon$-accurate: namely, each prediction is correct with probability (at least) $\epsilon$, but can be arbitrarily inaccurate with the remaining probability. We show that even with predictions that are accurate with a small probability and arbitrarily inaccurate otherwise, we can dramatically outperform worst-case bounds for a range of classical online problems including caching, online set cover, and online facility location. Our main results are an $O(\log(1/\varepsilon))$-competitive algorithm for caching, and a simple $O(1/\varepsilon)$-competitive algorithm for a large family of covering problems, including set cover and facility location, with $\epsilon$-accurate predictions.

Augmenting Online Algorithms with E-Accurate Predictions
Anupam Gupta Carnegie Mellon University anupamgocs. cmu edu
Debmalya Panigrahi Duke University debmalya@cs duke. edu
Bernardo Subercaseaux Carnegie Mellon University bsubercašcs. cmu, edu
Kevin Sun
Duke University
kaun@cs duke. edu
Abstract
A growing body of work online algorithms can be improved when given access to ML predictions about the future. Motivated by ML models that give a confidence parameter for their predic- tions, study online algorithms with predictions that are e-accurate: namely, each prediction is correct with probability (at least) e, but can be arbitrarily inaccurate with the remaining probability. We show that even with predictions that accurate with a small probability and arbitrarily inaccurate otherwise, we can dramatically outperform worst-case bounds for range of classical online problems including caching, online set cover, and online facility location. Our main results are an compeeiiite algorithm for caching, and simple ((1/e) -(oppetiiottiiiie algorithm for a large family of covering problems, including set cover, network design, and facility location, with e-accurate predictions.
online algorithms studies how
1 Introduction
The study of online algorithms with ML predictions has gained significant traction in the ML and algorithms research communities in recent years. The basic premise is that by having access to predictions about the future, one can design online algorithms that significantly outperform worst-case bounds. In practice, ML models producing such predictions often come with confidence estimate which can be roughly interpreted as a probability E of the prediction being accurate- we call these e-accurate predictions. Thus, it is natural to ask: is a function of the confudence parameter e of MI. predicictt I = and all predictions are correct, would like the algorithm approach optimal offline performance (consisfency). If the predictions have no guarantees and we would like to ensure that the algorithm is not much worse would
we design online algorithms whose performance
then
than an online algorithm without predictions (robustness). Between these two extremes, like the performance of the algorithm to gracefully degrade with the value of e. In this paper, we present online algorithms augmented with E-accurate predictions for fundamental problems such as caching. online set cover, online facility location, and online network design.
E-accurate predictions. We consider ML predictions that (independently) correct with probability at least e. Note that e represents only a minimum guarantee on the probability of a prediction being accurate; individual predictions are allowed to have higher confidence values. Moreover, do not restrict what an incorrect prediction constitutes since this will depend on specific problem settings. But morally, a correct prediction reveals information about the future while incorrect prediction does not. The design of online algorithms augmented with e-accurate predictions has two main challenges: (i) that information (correct predictions) is provided to the algorithm at slow rate, about
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

once every 1/2 steps, and (ii) the algorithm needs to disambiguate information (correct predictions) from noise (incorrect predictions). We emphasize that we are interested in the "high noise" regime, i.e., small values of E, where for every correct prediction, there are many incorrect ones. We will show that even in this regime, we can obtain online algorithms that are substantially better than the worst case. We also do not assume that the value of e is known to the online algorithm; rather, our algorithms automatically adapt to the (unknown) value of & in the underlying prediction model. In some cases, however, it will be easier to describe the algorithm and analysis if we assume that is known. If that is the case, we will first present the simpler algorithm that knows e and then generalize it to the that does not know E.
Prediction error vs e-accurate predictions. The trend in the online algorithms with predictions literature has been to use prediction error rather than prediction confidence to parameterize the performance of online algorithms. Note the difference in the two measures of prediction quality: an ML. model with high confidence (i.e., that produces E-accurate predictions for & close to 1) can occasionally make highly inaceurate predictions and therefore have very high prediction error; conversely, ML model that has a small but consistent bias can have 0 but still have small prediction error. So, the results obtained this paper are complementary (and incomparable) to the existing literature on online algorithms parameterized by prediction error. To the best of our knowledge, neither caching nor covering problems have been studied in the setting of e-accurate predictions.
Prior to our work, variants of e-accurate predictions that also model confidence estimates of pre- dictions have been studied in few different problem settings such as frequency estimation in data streams [13], k--maan [11], secretary problems [10], and page migration [14]. In some cases such as for ski rental [23] and set cover [6], the confidence parameter À does not represent measure of correctness of the prediction, rather it is simply a hyperparameter that can be used to trade off the consistency and robustness bounds of the algorithm. In contrast to these, the goal in this paper is to understand the role of e-accurate predictions in two central problem domains in online algorithms caching and online covering problems.
Competitive ratio. As in previous literature in this area, we also use the classical performance metric of competitive ratio for online algorithms. The competitive ratio of an online algorithm is the worst-case ratio between the (expected) value of the objective in the algorithm's solution to that of the (offline) optimum across all input instances. In the e-accurate predictions model, this expectation taken over both the randomness of the algorithm (if any) and the randomness of the predictions. Our competitive ratios are expressed as a function of and gracefully degrade as goes from I to O. But, even if e = O, we do not lose robustness; using standard techniques (e.g.. [4]), we can combine the best online algorithm without predictions and our algorithm with s-accurate prediction to match (up to constants) the better of the two solutions.
1.1 Our contributions
First, we consider the problem of caching with e-accurate predictions. In this problem, there is an underlying (slow) main memory of pages; at any given point of time, some l & of these can be stored in a (fast) cache. The online input comprises a sequence of page requests Pl: P2...... Pr- with page p. [n] being requested at time f. If page p, is not in the cache at this time, the algorithm must perform a page swap: it must evict some page from the cache, and load page pt. The goal of the algorithm the minimize the number of page swaps over the entire sequence of requests.
Lykouris and Vassilvitskii [18] initiated the study of caching with ML predictions and gave determin- istic and randomized algorithms whose competitive ratio gracefully degrades with prediction error. (See [7, 15, 24, 27] for subsequent work on this problem.) The general idea in these algorithms is to evict the page whose next request is predicted to be furthest in the future, but robustify this strategy by appropriately combining it with a worst-case randomized marking algorithm if the predictions turn out to be inaccurate.
In our paper, we consider the caching problem with e-accurate predictions. At each time, the algorithm is given prediction for the FIF page in the cache that is correct with probability at least E; with the remaining probability, the prediction just random page in the cache and hence, does not reveal any information about the future. A natural algorithm is to simply follow the prediction,

---

namely evict the predicted FIF page if the currently requested page is outside the cache. We call this the ONE-STRIKE algorithm and show that it achieves a competitive ratio of O(1/E).
Our main result is to obtain an exponential improvement over this baseline. To achieve the better bound, we give more nuanced algorithm that we call the TWO-STRIKES algorithm, and show that it achieves a competitive ratio of (loog(1/E)) lower bound of ()log(//E)) on the competitive ratio of any algorithm for caching with e-accurate predictions when 1/k log k. (Note that as long as > 0, s-accurate predictions are more accurate than predictions generated uniformly at random.)
We show this bound is tight by giving matching
Next, we consider the problem of solving online covering problems given E-accurate predictions. Online covering is a general framework for many optimization problems such as set cover and network design. In this problem, the online algorithm has to maintain a solution on a fixed set of variables, and is only allowed monotonically increase the variables over time. In each online step, the algorithm is presented with a new covering constraint on these variables, and must then augment its existing solution to satisfy the new constraint. The goal is minimize a linear cost function defined on the variables.
The systematic study of online covering with predictions was initiated by Bamas, Maggiori, and Svensson [6], who used primal dual techniques to leverage a predicted optimal solution given to the online algorithm (see also [1] for subsequent work on online covering with predictions). We consider a model where in each online step, the algorithm gets a covering constraint and a predicted optimal be
way of satisfying the constraint. (Given an offline predicted solution, these online predictions generated on the fly.) However, these are only E-accurate predictions. Namely, in each online step, the predicted solution to the covering constraint is part of an optimal solution with probability at least e, and otherwise it is an arbitrary way of satisfying the constraint with the remaining probability. Note that in the latter case, the prediction does not reveal any information about the future. We give simple algorithm for online covering with e-accurate predictions that obtains a competitive ratio of O(1/e), and also matching lower bound of ((1/e). Our covering framework and algorithm are very flexible: they can even model and solve problems like facility location that are not covering problems in strict sense.
Related work. There has been much recent work on incorporating ML predictions in online algo- rithms, such in ad-allocation [19], auction pricing [20], page migration [14), flow allocation [17], scheduling [16, 22, 23], frequency estimation [13], speed scaling [5]. Bloom filters [21], bipartite and secretary problems [3], and online linear optimization [9]. In particular, the caching problem was studied by [7, 15, 18, 24, 27], where the prediction model is that at each time i, the algorithm is given a prediction of when currently requested page pt next requested, and the prediction error n) is defined as the & error between the predicted and actual request times. Antoniadis et al. [2] consider the more general problem of metrical task systems; their predictor gives state Pt of the optimal solution, and the еттог 7) is the sum of distances between the predictions and actual states. The online set cover problem with predictions was studied by [5], where the (offline) prediction provides an entire feasible solution at the outset. Their algorithm uses the online primal-dual framework, and uses a hyperparameter À [0, 1] to obtain a trade off between the consistency and robustness bounds.
1.2 Preliminaries
For every positive integer n, let [n] := (1.2...., Let us formalize the prediction model: at each time I, the algorithm is given some prediction or suggestion 8t, whose nature depends on the problem statement. At each time I, the algorithm is given one of two possible suggestions: a "good" suggestion ye, "bad" suggestion 2t- While the precise definitions of y and z, depend on the specific problems, we require that the former reveals some information about the optimal solution, and make no such requirement about the latter. There is fixed value (0, 1] that is unknown to the algorithm. Now at each time step t, the é-accurate prediction St is determined as follows, independently of the past:
Vt
with probability at least otherwise.
24
'oore precisely, we can get O(min(1/e log k) by combining ONE- STRIKE with Randomized Marking us- ing standard techniques (see e.g., [2, 18). As this applies to all our algorithms, we omit writing O(min(: log k)) for simplicity.
3

---

We aim to bound the competitive ratio of the algorithm in terms of the noise parameter E. Note that the randomness that determines whether s, = yt or s, 2, is hidden from both the adversary, who generates the input sequence, and the algorithm.
2 Caching
In the caching problem there is underlying (slow) main memory of n pages; at any given point of time, some < n of these can be stored in the (fast) cache. The online input comprises a sequence of page requests PI; .2,,......1 Pr, with page Pt E [n] being requested at time I. If page ps is already in the algorithm's 's cache at this time, the algorithm does not need to do anything, else it must perform a page swap: it must evict some page in the cache, and load the page Pt. The goal of the algorithm is the minimize the number of page swaps over the entire sequence of requests.
Given the request sequence up-front, strategy that minimizes the number of page swaps is Bélády's 's rule [8]: at each time f. if the requested page Pt is not in the cache, evict the page that is requested the furthest in the future (FIF) among the pages in the cache. An online algorithm does not know the future requests, so this is not implementable; instead policies such as LRU [26] and Randomized Marking [12] are used to circumvent this lack of foresight by using past requests to predict the future.
In contrast to the recent work which assumes prediction for the next-arrival time of the page requested at time t [7, 18, 25, 27]. we consider model where at every time f, the algorithm is provided with a prediction on the page in its cache that will be requested furthest in the future. The prediction is a noisy prediction: with probability E it is the FIF page, else it is a random page from the algorithm's cache. Using the notation from Section 1.2, y/+ is the FIF page in the algorithm's 's cache, and 2, is page chosen uniformly at random from the the algorithm's 's cache. This assumption of uniformity only made for simplicity. We can in fact show (see Appendix A.2) that it suffices to assume that the probability that page p is incorrectly predicted as the FIF page is at most 1/ke where e a constant.
Note the two extremes: if = 1 then we can follow Bélády's rule and be optimal; if = 0 then the predictions are just random pages in the cache (which can be generated without any knowledge about the future), and we get back the classic worst-case online setting.
Starting with the first request, partition the input sequence into phases, where phase is defined as a maximal contiguous subsequence of requests containing &o distinct pages. (The last phase might contain fewer than & distinct pages because of the termination of the input sequence.) We note that our algorithms do not actually require suggestions to be precisely the FIF page; they work unchanged as long as the correct predictions provide page that is not requested in the current phase. (The FIF page is just one such page.)
All our algorithms use the idea of cache reset at the beginning of cach phase (except the first): replace the contents of the cache with the pages requested in the previous phase. Since each page brought back in due to cache reset must have been evicted after it was last requested in the just-ended phase, we get the following lemma.
Lemma 2.1 (Cache Reset Overhead). If an algorithm that performs cache resets at the beginning of each phase, the number of page swaps in any cache reset at most the number of page swaps performed in the previous phase.
These cache resets allow us to localize the description and analysis of our algorithms to a single phase, because the state of the cache at the beginning of the phase only depends on the input sequence, and is now independent of the algorithm. Furthermore, we partition the (at most) k pages requested in each phase into two sets: clean pages are the ones that were not requested the previous phase, and the rest are called stale. (All the k requested pages in the first phase are considered clean.) Let A; denote the number of clean pages in the tth phase.
2.1 ONESTRIKE: A Deterministic O(Vs)-Competitiv Algorithm
Our first algorithm ONESTRIKE using e-accurate predictions is simple and deterministic, and obtains a competitive ratio of (11e). the first phase, it fetches each requested page into the cache. After this point in time, the cache always remains full (with à pages). Each subsequent phase starts with

---

Remark. The ONESTRIKE algorithm and its analysis both apply assuming weaker prediction model, in which the 2 predictions (i.c., the non-good ones) are chosen adversarially, rather than uniformly at random among the pages in the algorithm's 's cache. Note that in this model, an adversary cache reset. Let C2 denote the algorithm's 's cache contents at the end of timestep t. During the phase, the algorithm the following:
(a) If the requested page Pt is already in C2-1, do nothing (i.e., it sets Ct +- C2-1). (b) Else if Pt & C--1, evict the predicted page St, i.c., set C + (C,-1 \ st) U {pr}.
Theorem 2.2. The ONESTRIKE ONESTRIKEAllgorilmm is Oooopeicoeeeiiivv.
still does not know when good predictions are given, but can adapt to the algorithm's 's behavior when specifying the 2 predictions.
2.2 TWOSTRIKES: A Randomized O(log 1/2) Cooppetitie Algorithm
We now use randomization to improve the competitive ratio to (logg(//e). Before describing the formal algorithm, time it must make a page swap. This places too much faith on the predictions, and incurs a large loss. Our first change is that the algorithm is more cautious with the predictions, and now views two predictions for the same page (and not just a single prediction) as a strong- erough signal to evict the page. We show that the probability that page that remains the FIF page long enough is predicted twice far outweighs the probability that any non-FIF page is (erroneously) predicted twice during the course of the entire phase. As we now need two predictions before evicting page, we need fallback option if the requested page is not in the cache and no page has been predicted twice. We run randomized marking algorithm (call it MARKER) for this purpose, and carefully combine these two algorithms to obtain the final algorithm.
first give some intuition. The ONESTRIKE algorithm uses the prediction every
However, this does not suffice: consider situation where the length of the request sequence for which a page remains the FIF page in the cache is very short. (An extreme example is when pages requested round-robin, in which case every page is the FIF page right after it is requested and remains so for only a single request.) In this case, none of the FIF pages maintain their FIF status long enough be predicted twice, and the algorithm devolves to essentially being MARKER with competitive ratio of Olog k). To handle this situation, we stop the algorithm once we are confident that we have seen at least A FIF pages in the predictions, where A is the number of clean pages requested in the phase. At this point, we switch to a different algorithm, which is again MARKER but run only on pages predicted earlier in the phase.
2.2.1 The TWOSTRIKES Algorithm
We now formally describe the TWOSTRIKES algorithm. (In this section we assume that we know the accuracy parameter e: we remove this assumption later in the supplementary material.) As in ONESTRIKE, the first phase in TWOSTRIKES brings the first k requested pages into the cache and does no evictions. Every subsequent phase begins with a cache reset to ensure that the pages in the cache are precisely those requested in the previous phase. We now describe the behavior of the TWOSTRIKES algorithm for single phase.
Epochs and Segments. Since the algorithm does not know A (the number of clean requests in this phase), it maintains guess A, which starts and is periodically updated. These updates break the phase into epochs: the first epoch starts at the beginning of the phase; each time we observe that the number of clean requests in the phase exceeds our guess A, we double the value of A. thereby ending the current epoch and starting a new one.
When an epoch starts, TWOSTRIKES first performs a cache reset, and then checks if S (2/2)1/5; so, it simply runs randomized marking in the rest of the current epoch. Else if (2/k)1/5 1/5 the epoch now is partitioned into an explore segment followed by an exploit segment. In the explore segment, the algorithm makes A good evictions of pages that have been predicted twice (for some A < Σ), and also learns a small candidate set of pages that contains at least A A pages which make for good evictions. the following exploit segment, the algorithm then runs randomized marking these candidate pages to actually make A A good evictions.
5

---

Before we give details about these two segments, let give two procedures: MARKER and STRIKER. The MARKER procedure maintains a binary flag called MARK for every page; we say that page p is marked if MA)K(p) I, else it is unmarked. We mark and unmark pages by changing the flag to 1 or respectively. All pages are unmarked at the beginning of the epoch. The MARKER algorithm essentially runs the R RANDOM MARKING algorithm, but since we may run it starting with only few unmarked pages, we allow for the possibility running out of unmarked pages-in which case we declare failure. The details of MARKER appear in Algorithm 1.
Algorithm 1: MARKER
11
let C' be the set of pages in the cache page Pt. is requested at the current time t do
1.3
case Pt E C do do nothing
1.4
case Pt E C and |C| < k do C C. (pt)
1.5
case Pt & C and |C| = k and C has at least unmarked page do
1.6
let dr. be a uniformly random unmarked page in C, and set C <- (C) u {pr}
otherwise do declare FAIL
mark page Pt.
The second procedure is STRIKER: it maintains counter called STRIKE for every page, which takes on values in {0, 1, 1,2). we say that page p is striked if STRIKF(P) E (1,2), otherwise STRIKF(p) = 0 and page p wnstriked. If STRIKF()) 2, we say page p is strike-evicted. At the beginning of the epoch, all pages are unstriked. The STRIKER procedure operates in two modes: active and passive. The procedure is in the active mode when the cache contains k pages (i.c., is full), and is in the passive mode (and does nothing) otherwise. Like MARKER, STRIKER is not a stand-alone caching algorithm; instead, it is active when the cache is full acknowledge the prediction, and possibly performs preemptive eviction. The details appear in Algorithm 2.
Algorithm 2: STRIKER
2.1 let C' be the set of pages in the cache
if |C| < k then do nothing (we in the passive mode)
2.3 else if page E C is the predicted page at the current time then
STRIKE(S:)++
2.5
if STRIKE(s:)) = then evict 8t, so C + C. {se} (so that 8t is strike-evicted)
Switching to ONESTRIKE. In both the explore and exploit segments, it is possible for the algorithm to switch to the ONESTRIKE algorithm. When this happens, all marks and strikes are forgotten, and the algorithm simply evicts the predicted page whenever an eviction is required. The only state that remains is the count on the number of clean pages in the phase so far: whenever exceeds A, regardless of the state of the algorithm,
double the value of A and start new epoch.
The Explore Segment. We now describe our algorithm for the explore segment. uses a global counter called AAD-STRIKES, initialized 0 at the beginning of each epoch, that counts the number of bad evictions made by the STRIKER procedure. Recall that an eviction at time is good the evicted page is not requested in the current phase after time and it is bad otherwise. Before serving each request, the algorithm first increments BAD-STRIKES as necessary, and then calls STRIKER and MARKER in that order. The formal description is in Algorithm 3. The explore segment ends if either (a) STRIKER makes at least 2 evictions in the segment, or (b) STRIKER has been in active mode for N = A/2² requests.
Lemma 2.3. In the explore segment, the MARKER procedure never declares FAIL.
Proof. Pages are marked only when they are requested in the current epoch. So, if pt & C and C' has marked pages, then & + distinct pages have been requested the current epoch, and therefore also in the current phase. This contradicts the definition of a phase.
The Exploit Segment. The exploit segment ignores all predictions. Instead it relies on the fact (proved in Lemma 10) that the set of striked pages at the end of the explore segment contains A

---

Algorithm 3: Explore Segment
3.1 foreach time do
let Pr. be the requested page and the predicted page at time &
3,3
if Pr. is strike-evicted STRIKE(P:) = 2) then increment BAD-STRIKES
if BBAD-STRIKES A then run ONESTRIKE for rest of epoch else set STRIKE(p))
3,5
call STRIKER
call MARKER
terminate explore segment STRIKER evicts pages 2 2Â times, or STRIKER active
3,7
mode for N := 2/2" requests
pages that would be good evictions (with good probability). The exploit segment now runs MARKER on these striked pages, Formally, see Algorithm 4.
Algorithm 4: Exploit Segment
mark all pages in the cache with strikes; striked pages are left unmarked foreach time do
4.2
let Pt be page requested at time
4.4
if Pt. is strike-evicted (i.e., STRIKE(p:) 2) then increment BAD-STRIKES
if BAD-STRIKES A then ONESTRIKE for rest of epoch else set STRIKE(P)) 0
4.6 call MARKER
MARKER returns FAIL then run ONESTRIKE for the rest of the epoch
Since the exploit segment handles the possibility that MARKER may fail (and reverts to ONESTRIKE in that case), the algorithm is well-defined; it only remains to bound the expected number of evictions per epoch, and hence per phase. This is what we do next.
2.2.2 Competitive Ratio of the TWOSTRIKES Algorithm
Theorem 2.4. The algorithm performs O log \/c) evictions expectation an epoch.
Proof. There are four types of evictions that happen during an epoch:
(i) evictions performed by STRIKER in the explore segment, evictions performed by MARKER in the explore segment, iiii evictions performed by MARKER in the exploit segment, and
(iv) evictions due to the ONESTRIKE algorithm,
We show that the expected number of each of type of eviction is at most O log 1/2). The type (i) evictions are the casiest: there are at most 2A of these, by the termination condition of the explore segment.
Next we bound the number of evictions type (iii): consider running MARKER with some cache Co. where some &- pages are pre-merked. Consider the unmarked pages of Co, and order them as Pt. ........P1 Pr. in reverse chronological order of their first request this segment. The pages that not requested at all are placed at the beginning of this sequence, but can be arbitrarily ordered relative to each other. Let D be number of requests for pages outside set Co received by the algorithm. The following property holds by induction, since only D pages are evicted, and each unmarked page is equally likely to be evicted at any time:
Lemma 2.5. At any time t, suppose pages Ps,+1 P. Pr have already been requested and pages P1, .2.....Po Pt, have not been requested yet. Then, for any S in the probability that page ps is not in the cache of the MARKER procedure at time t is at most min(D/sr,
Note that the property of this lemma is unconditional, in the sense that it does not depend on the set of pages among P1, Pi.-2..... Pr that were evicted before time 1. The following corollary follows by applying this lemma at the time of the first request for page p.:
7

---

Corollary 2.6. The probability that the cache of the MARKER procedure does not contain page ps at the time of its first request is at most min(D/; 1).
The next lemma is proved using the above corollary:
Lemma 2.7. The expected number of evictions of type (iii) in an epoch is O(Â log(1/E)).
Proof. The explore segment terminates after it sees at most N = A/2² requests for which STRIKER active mode. Let denote the set of striked pages; clearly, |S] S N. Moreover, the number of distinct clean page requests is at most A, else the epoch ends. By Corollary 2.6, the expected number of evictions at most
1S| Σ min
A i
N
A i
S
A +
H&) = O( log(1/e)).
L
Bounding evictions of type (ii) a bit more involved, because we start off with unmarked pages (so the naive application of Corollary 2.6 would give us O log k)); we need use the interplay between MARKER and STRIKER to get our bound.
Lemma 2.8. The expected number of evictions of type (ii) in an epoch is o(Î log(1/E)).
Finally, to bound the number of type (iv) evictions. observe that we run ONESTRIKE if the counter BAD-STRIKES reaches A, or MARKER returns FAIL in the exploit segment. We claim that both of these events happen with probability at most e. Now since ONESTRIKE makes O (A//E) evictions in expectation the expected number of such evictions is at most e O(A/e) = O()).
Lemma 2.9. Pr|BAD--TTREE STRIKES 2 A E.
Lemma 2.10. The probability that MARKER declares FAIL in the exploit segment is at most (
We now summarize the bounds on the four types of evictions. In the explore segment, STRIKER performs at most 2 evictions by design of the algorithm, and MARKER performs O ())))
evictions by Lemma 2.8. In the exploit segment, MARKER performs O A log(1/e)) evictions by Lemma 2.7. Finally, Lemmas 2.9 and 2010 show that ONESTRIKE is called with probability O(e), and its cost is O(A/E), so its expected contribution is O(A) evictions. Combining everything together, the total expected number of evictions in any epoch is at most O log.//) 1/s), which proves Theorem 2.4.
Since we double our guess for Â each time, the total expected cost of a phase is O(A log 1/=). thereby proving the claimed competitive ratio for the known-e case. The algorithm (and analysis) when we do know the value of E in advance are conceptually similar the one above, but there are more details to consider. In particular, we maintain guess for e, and each time we square this guess. The real problem is that unlike the value of A, we do not get clear signal that we have overestimated the value of e. Our algorithm therefore needs to infer failure from our algorithm not performing as claimed; we defer this to the supplementary materials.
Comparison with [27]. We show that under our prediction model, the algorithm given by Wei [27] performs poorly. That algorithm combines RANDOM MARKING and BlindOracle (which in our terminology is called ONESTRIKE). Since the BlindOracle algorithm just evicts the page suggested by the oracle, we take n k + 1 pages and construct sequence of phases. In phase i we request all pages except page round-robin, and do this & times. The optimal strategy is to eviet page i at the start of this phase. But the algorithm follows the oracle blindly, so it will evict random pages due to bad suggestions 1/c times in expectation before getting good suggestion and evicting page i. This happens in each phase, giving an expected cost (2(1/) times the optimum. Since this is combined with RANDOM MARKING which has an 2(log k) lower bound, by setting e = 1/ log and interleaving phases of the above lower bound sequence with phases of the lower bound for RANDOM MARKING, we get sequence that causes Wei's algorithm to pay 2(log k) times the optimal cost, whereas our algorithm pays (loog(1/e) Oloog log k) times the optimal cost.
8

---

3 Set Cover and Generalized Covering Problems
We now show that for a large class of online covering problems, which includes set cover (and its multiset multicover variants), facility location, and network design problems such as Steiner tree and Steiner forest, we can obtain an ((o/e)-competitve algorithm with E-accurate predictions. We first present for the case of online set cover, and then extend the ideas to more general settings.
3.1 The Set Cover Problem
In the SET COVER problem we are given a collection of m subsets S : (Si,.... Sm) of a universe U containing [U] elements. Each set has a cost c(S) > 0, and we want to pick subcollection of least cost covering the universe. In the online version of the problem, we do not know the set system in advance: an element E U is revealted at each time i, along with the names of the sets containing ex. If none of these sets have already been chosen by the algorithm, one must be chosen at this time. Sets once chosen cannot be dropped (so the solutions are monotonically increasing), and the goal is to minimize the total cost of the chosen sets.
Our model of e-accurate suggestions is the following: at each time, we are given an element et, along with a suggested set sf S, with the guarantee that Pr[s' OPT H I 2 E. where H the history of all requests, predictions, and actions taken in previous steps, and OPT is the optimal offline solution.
SET-HEDGE: If is already covered, do nothing. Else let g be the minimum-cost set that covers ex. Choose sf with probability c(g') //(s)) and choose g otherwise.
Since g' is the cheapest set covering et, we have clg')//(s') and hence valid probability. Theorem 3.1. Given E-accurate predictions. the SET-HEDOS algorithm is 2/E-competitivv.
This result is tight up to constant factors: we show in the supplementary material that no algorithm for set cover can have competitive ratio better than (11/e) in general. Moreover, algorithm in parallel with any other online set cover algorithm, say one that is asc-competitive, to get algorithm that is (mii(11/e compeetive.
this
3.2 Extension to Generalized Covering Problems
The simplicity of the algorithm allows us to extend to very general set of objective functions and constraints, which call generalized submodular-cost coverage (GSCC). Consider the following:
1. The algorithm controls a point I E R2 The initial point is x = 0, the all-zeros vector. We require that is monotone over time; i.e., '=11 <'.
2. (Covering.) At each time t, set K, C R is revealed, and we want that x N We restrict ourselves to sets that are closed under taking component-we maximums i... v, y E K, = (x V v) E K,, where (x V y); = max(s;, Us).
3. (Monotonicity and Submodularity.) The objective function
Rd + Rzo is monotone: if & c(*Vy)- c(x).
x I y then c(x) S c(y). Moreover, is submodular:
The e-accurate suggestion model now says: at each time the suggestion s' E Kr, and moreover Pr[s < xx" H' > E, where x* is the optimal offline solution. The HOVER-HEDGE algorithm now extends the SET-HEDGE algorithm as follows:
Let g" be the minimum-cost increment-i.e., of t arg min(c(x 1 E K.). Then set x f- r-1 v s² with probability d(="-lvg - -(=')) otherwise.
and xf +- x v
vi c(o
In general, finding this miminum-com cost increment may be computationally hard; we focus the information-theoreti considerations for now, and defer the computational issues for later.
Theorem 3.2. Given e-accurate suggestions, the COVER-HEDGE algorithm 2/--coppeee for any generalized covering problem.

---

3.3 Applications
Beyond set cover, the general covering formulation above captures several interesting problems:
Network Design: In the Survivable Network Design problem (which generalizes Steiner Tree and Steiner Forest) are given set V of points together with the distances diy between them i, V. The goal is to connect & pairs of points [(5e, 42) E V x V E [R]] at minimum cost, where each pair (se,42 comes with connectivity requirement of ra disjoint paths between them. This problem can be written as
min Σ dig
Σ iES.jE8
mij 2 TE AS, E E [K] S,t & S; x E TR
NEEV
This formulation satisfy the Covering, Monotonicity, and Submodularity properties. Moreover, the least-cost augmentation g" can be obtained polynomial time by minimum cost flow algorithm.
This not a covering program, yet it can be modeled using our framework. Given point set V on points and distances di between points i, E V. and opening costs 2 0 for each i E V. the goal is to designate some subset F of points as facilities, so that the total cost of EiEP + Σjev minker de is minimized. We can write this using Balinski's MILP formulation:
Facility Location:
min
Σ fin Edj Σ may = =1j=e may S M Vi,j V.y 20. NEV
R
jEV
can be verified that this formulation also satisfies the Covering, Monotonicity, and Submodularity properties, despite the non-covering constraints of the form Zig y/- (Indeed, in the supplementary material, we show that the coordinate-wise maximum covering property allows us to go beyond standard covering programs.) Moreover, the least-cost augmentation g' can be obtained in polynomial time using a simple greedy algorithm.
Covering Hixed-Integer Linear Programs (MILPs): given non-negative A E Rmxx b E R and c, u E RR, and a subset / C [n.]. we want to solve
min(cTa Ax 2 6,0 < x S u, E Z E 1, RVI $ 1}.
Each constraint is half-space, and can be verified that this formulation satisfies the Covering. Monotonicity, and Submodularity properties. However, since this problem is hardard in general, the least-cost augmentation g² can be computed efficiently only in some cases such as the network design problems described above.
4 Conclusions
In this paper, we presented online algorithms augmented with e-accurate predictions for several classic problems such as caching, set cover, facility location, Steiner tree, and generalizations. Can we show a poly log(1/ competitiveness, or even f(z) competitiveness for the k-server problem, which is extension of our results for caching? Another direction would be to combine the e-accuracy prediction model studied in this paper with some measure 1j of total prediction error namely, design online algorithms augmented by probabilistically approximately correct (or PAC) predictions. Finally, a third direction of future work would thorough experimental analysis of our framework and algorithms, to empirically compare the performance of our work with that of other tearning-augmentee algorithms.
Acknowledgments
AG and BS were supported in part by NSF awards CCF-1955785, CCF-2006953, and CCF-2224718, DP and KS were supported in part by NSF grants CCF-1750140 (CAREER) and CCF-1955700 and ARO grant W91 W991NF21102:0 10230.
References
[1] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions, In International Conference on Machine Learning. PMLR, 2022.
10

---

[2] Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In International Conference on Machine Learning. pages 345-355. PMLR, 2020.
[3] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev, Secretary and online matching problems with machine learned advice. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balean, and Hsuan-Tien Lin, editors, NeurIPS 2020, 2020.
[4] Yossi Azar, Andrei Z. Broder, and Mark Manasse. On-line choice of on-line algorithms. In Vi- jaya Ramachandran, editor, Proceedings of the Fourth Anmual ACM/SIGACT SIAM Symposium on Discrete Algorithms, 25-27 January 1993, Austin, Texas, USA, pages 432 440. ACM/SIAM, 1993.
[5] Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented energy minimization via speed scaling. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, NeurIPS 2020, 2020.
[6] Étienne Bamas, Andreas Maggiori, and Ola Svensson. augmented algorithms. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florins Balcan, and Iisuan-Tien Lin, editors, NeurlPS 2020, 2020.
The primal-dual method for learning
[7] Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee. Learning- augmented weighted paging. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 67-89. SIAM, 2022.
[8] Laszlo A. Belady. A study of replacement algorithms for virtual-storage computer. IBM Syst. J., 5(2):78-101, 1966.
[9] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit, Online learning with imperfect hints. In International Conference on Machine Learning, pages 822-831. PMLR, 2020.
[10] Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. In Péter Biró, Shuchi Chawla, and Federico Echenique, editors, EC '21: The 22nd ACM Conference Economics and Computation, Budapest, Hungary, July 18-23, 2021, pages ACM, 2021.
[11] Jon Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou. augmented k-means clustering. CoRR, abs/21 10. 14094, 2021.
Learning-
[12] Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, and Neal E. Young. Competitive paging algorithms. J. Algorithms, 12(4):685-695 699, 1991.
[13] Chen-Ye Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-bast based frequency estimation algorithms. In International Conference Learning Representations, 2019.
[14] Piotr Indyk, Frederik Mallmann-Tress Slobodan Mitrović, and Ronitt Rubinfeld. Online page migration with ml advice. arXiv preprint arXiv:2006. 05028, 2020.
[15] Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted paging with predictions. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Bagstuhl-Lcibnii-Zeenree für Informatik, 2020.
[16] Silvio Lattanzi, Thomas Lavastida. Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1859-1877. SIAM, 2020.
[17] Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Learnable and instance- robust predictions for online matching, flows and load balancing, 2020.
[18] Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In International Conference Machine Learning, pages 3296-3305, PMLR, 2018.
11

---

[19] Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Allocating online advertisement space with unreliable estimates. Jeffrey K. MacKie-Mason David Parkes, and Paul Resnick, editors, Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), San Diego, California, USA, June I 11-15, 2007, pages 288 298. ACM, 2007.
[20] Andrés Muñoz Medina and Sergei Vassilvitskii. Revenue optimization with approximate bid predictions. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pages 1856-1864, 2017.
[21] Michael Mitzenmacher. A model for learned bloom filters, and optimizing by sandwiching. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pages 462-471, 2018.
[22] Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In 1/th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2020.
[23] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via MI predic- tions. In Advances Neural Information Processing Systems, pages 9661-9670, 2018.
[24] Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1834-1845, SIAM, 2020.
[25] Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Shuchi Chawla, editor, Proceedings of the 2020 ACM- SIAM Symposiun on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1834-1845. SIAM, 2020.
[26] Daniel D Sleator and Robert E Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, 1985.
[27] Alexander Wei. Better and simpler (earnin--uugmette online caching. In Approximation, Ran- domization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Schloss Dagstuhl-Leiinniz-Zenin für Informatik, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 4, where we list the
problems we consider and directions for future work.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Most proofs are the supplementary material.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
12

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "nctlXsK9fpU", "reviewer": "Reviewer_iZrF", "summary": "This paper introduces a new model of learning-augmented online algorithms and studies caching and generalized covering problems in this model. In this standard learning-augmented model, the algorithm is supplied with some predictions about the future, and we seek to bound the competitive ratio of the algorithm in terms of some measure of the \"prediction error\", so that when the error is low the algorithm is near-optimal, and when the error is high the algorithm's performance gracefully decays. In the new model, the algorithm is again supplied with some predictions about the future, but we seek to bound the competitive ratio of the algorithm in terms of the probability that the prediction is correct. The goal is that even when the probability of correctness is a small constant, the algorithm still outperforms un-augmented algorithms.\n\nFor caching, the predictions are of the page in the cache which will take the longest time to be requested again (as in prior work on learning-augmented caching). The assumption is that with probability epsilon the prediction is exactly correct, and otherwise the prediction is a uniformly random page from the cache. This paper provides a simple algorithm OneStrike which achieves performance O(min(1/eps, log k)) and a more complex algorithm TwoStrike which achieves performance O(min(log(1/eps), log k)). They also show that if eps = 1/(k log k) then TwoStrike is optimal, i.e. it's impossible to beat Omega(log k).\n\nFor online set cover, the predictions are as follows. Each time an element is given, the algorithm needs to pick a set which contains that element (each element has a cost), and the prediction is supposed to supply one of the sets in the optimal solution which contains that element. The assumption is that with probability epsilon the prediction is in fact in the optimal solution. This paper provides a simple algorithm Set-Hedge which achieves competitive ratio O(1/eps), and shows that this is optimal. Finally, this algorithm is generalized to a class of \"submodular-cost coverage problems\".", "questions": "1) Is there a more comprehensive lower bound for caching? (e.g. for larger epsilon)\n2) What happens if the \"bad\" predictions are allowed to be arbitrary? Is it possible that log(1/eps) is still attainable, or is there a stronger lower bound in this model?\n3) In the set cover model, it's rather restrictive that the \"good\" prediction is required to be in the optimal solution. Does the proof generalize if we instead assume that the prediction is in a near-optimal solution? (e.g. a solution with cost within a constant factor of optimal). \n4) More fundamentally, what if there are multiple optimal solutions and the \"good\" predictions at different steps are contained in possibly-different optimal solutions? It seems to me that the potential function proof might require it to be the same OPT at each step. Is there a reason to expect in practice that the prediction would be \"consistent\", i.e. drawn from a single optimal solution?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In brief, this paper is original (introducing an interesting and practical twist to the traditional model of learning-augmented online algorithms) and clearly written. I checked correctness of the simpler caching algorithm (OneStrike), the online set covering algorithm (Set-Hedge), and the lower bounds. Set-Hedge is particularly elegant, whereas the algorithm/analysis of Two-Strike is rather complicated and ad-hoc (although this is a common issue in this literature). There are some weaknesses to the caching model/results which I expand on below. On the whole I think the conceptual contribution of this paper is interesting; on the other hand, there are significant ways in which the model/results are not entirely practically justified / could be strengthened (although these could reasonably be left to future work).\n\nStrengths:\n- The main strength of this paper is the new model. While it does not generalize prior work (it's incomparable), it introduces a new idea: it allows for some predictions to be arbitrarily erroneous, which may easily arise in practice when predictions are produced via machine learning.\n\nWeaknesses:\n- The weakness of this model (for both caching and set-cover) is that it requires the \"good\" predictions to be exactly correct. For caching, it seems often unreasonable to ask that the machine-learned model predicts which exact page will be requested farthest in the future with constant probability, since there may be a long tail of e.g. O(sqrt k) very rare pages in the cache which cannot be plausibly disambiguated. In such a setting we would expect that epsilon is roughly O(1/sqrt k), in which case (in this model) we do not improve upon the un-augmented O(log k) competitive ratio. In contrast, in the prediction error model, it's fine if all predictions have some noise. To put some numbers, if a phase has length O(k), then these hypothetical sqrt k rare pages would contribute at most roughly eta := k^{1.5} to the l1 error per phase; if OPT has O(k) cache misses in this phase, then the relative error eta/OPT is sqrt k, in which case we might expect (e.g. via [Wei20]) a competitive ratio of O(1). While this is a very rough back-of-the-envelope calculation, it suggests that either the augmented caching model introduced in this paper doesn't quite capture the strengths of machine-learned predictions, or the algorithm is not actually optimal.\n\n- If I'm not missing some simple reduction, the caching lower bound of Omega(log 1/eps) claimed in this paper (Theorem B.6) is a little oversold. In particular, it is only proven for eps = 1/(k log k): that is, when the probability of getting the correct prediction is *lower-order* than the probability of getting any fixed page in the cache from a random prediction. This leaves open the possibility that for larger epsilon, the O(log 1/epsilon) algorithm can be improved (e.g. perhaps if epsilon = 1/sqrt(k) there is actually an algorithm with o(log k) competitive ratio). Indeed, this sort of phenomenon does happen in the prediction error model (parametrizing the competitive ratio by the relative error (l1 error)/OPT) [Wei20].\n\n- Theorem 2.4 (analyzing the main caching algorithm TwoStrike) relies on a much stronger assumption than claimed in the abstract (\"with predictions that are accurate with a small probability and arbitrarily inaccurate otherwise\"). Specifically, with epsilon probability the prediction is assumed to be correct, and with the remaining probability the prediction is assumed to be a *uniformly random page from the cache*. This seems to me entirely unreasonable in a model which is motivated by machine-learned predictions. Errors made by machine-learning models tend to have severe correlations and biases, and are far from uniform.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hRUPxMxQwA", "reviewer": "Reviewer_QMX1", "summary": "This paper proposes and studies a model of learning-augmented online algorithms where future predictions are “$\\varepsilon$-accurate”, but do not necessarily have low “error”. (An $\\varepsilon$-accurate prediction is an accurate prediction that has been corrupted with probability $1-\\varepsilon$.) The authors show $\\varepsilon$-accuracy is sufficient to obtain beyond-worst-case performance in two instantiations of this model for online paging and online covering, respectively. This work fits into a growing literature on algorithm design, motivated by the increased availability of data and the structure inherent in many real-world problems, in which the input is augmented with “predictions” about the task at hand.", "questions": "- For the section on set cover, the predictions appear to be reliant on the choice of a distinguished solution $\\mathsf{OPT}$ if there are multiple optimal solutions. Is there a way to define the model without reference to a specific $\\mathsf{OPT}$ so that the results still hold?\n- For the section on covering-type problems, it is great to see that the result applies in such generality. For such settings, are there empirical datasets where such a predictor—of which constraint to make binding—makes sense?", "limitations": "The authors discuss the limitations of their theoretical results in Section 4.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths:\n    - I appreciate the thought put towards considering a new model of prediction, as I find that consideration of models of prediction—while being a central driver of the results in this literature—has not received as much attention it deserves.\n    - The technical results appear correct (although I did not verify all the details in the supplement); and the analyses are clean.\n- Weaknesses:\n    - While I like the idea of considering $\\varepsilon$-accurate predictions (as it can encompass, e.g., heavy-tailed noise), I would have found the main result in the section on online paging more compelling if the analysis did not rely on uniformly random corruptions.\n    - The $O(1/\\varepsilon)$ bounds feel somewhat limited, as they should be somewhat expected when on a $\\varepsilon$-fraction of the rounds the augmented hint tells the algorithm exactly the right action to take.\n    - The paper would be stronger with a more thorough discussion (or perhaps empirical support) of the modeling assumptions and why they were chosen.\n- Minor:\n    - Line 84: The acronym “FIF” (assuming it means “furthest in the future”) should be defined before its first use, perhaps in Line 80.\n    - Line 323: “revealted” → “revealed”\n    - References: Reference [25] is a duplicate of [24]; likewise for [28] and [27].", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G0ej7uX1bqk", "reviewer": "Reviewer_jWJY", "summary": "This paper considers the recently popular learning-augmented model in online algorithmic design. The authors use the minimum probability guarantee that a prediction is 100\\% accurate to measure the quality of the prediction: say a prediction is ``$\\epsilon$-accurate\" if it is perfect with probability at least $1-\\epsilon$. The paper presents several online algorithms which incorporate $\\epsilon$-accurate predictions. For caching, a competitive ratio of $O(\\log (1/\\epsilon))$ is obtained, while for covering problems, a $O(1/\\epsilon)$-competitive algorithm is given. The competitive lower bounds of caching and covering with $\\epsilon$-accurate predictions are also discussed in the paper to show the optimality of the proposed algorithms.", "questions": "- In the proof of Lemma 2.9 (line 591-593), why the expected contribution of $p$ to BAD-STRIKES is at most $\\sum_{i\\geq 1} i {N \\choose i} \\frac{1}{k^{2i}}$? It is not clear to me where the term $\\frac{1}{k^{2i}}$ comes from. Intuitively, this term should have a dependence on the accuracy parameter $\\epsilon$.", "limitations": "I didn't see any potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- A novelty of this paper is using the accuracy guarantee instead of the traditional prediction error to measure the prediction quality. Although the accurate parameter $\\epsilon$ can still be viewed as a particular prediction error, I still think this measure is interesting and could influence future work, where it is not clear that how to define a prediction error.\n\n- The paper is technical. It proposes learning-augmented algorithms for classical online problems: caching and covering problems. Both algorithms are proved to have nearly optimal dependence of the accurate parameter $\\epsilon$.\n\nWeakness:\n- There is no discussion about the learnability of such $\\epsilon$-accurate predictions. Can we really learn them from historical data? Intuitively, it seems hard to get a 100\\% accurate prediction with high probability. \n\n- Experiments may be needed. Caching and covering problems are well studied in the learning-augmented model. The paper builds on a new prediction quality measure to give algorithms. So it might be better to conduct experiments to compare against previous learning-augmented algorithms. \n\n- Line 76: ``the minimize the number of page swaps \".\n\n- Line 84: ``FIF\"  should be given the full name the first time it is used.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7W_4ZFxqtnR", "reviewer": "Reviewer_nuaT", "summary": "\nThe paper considers the problem of designing ML augmented online algorithms for caching and set cover problems. They initiate the study of these algorithms with eps-accurate predictions, that is algorithms which provide relevant information with probability eps, and otherwise provide arbitrary predictions.  More precisely, they focus on the “high noise” regime where eps is very small and predictions are for me for the most part uninformative. \n\nBeginning with the online caching problem, the start by introduce an algorithm OneStrike which is O(1 / eps) competitive and later show how the algorithm can be refined into the TwoStrikes algorithm which is O(log(1/ eps) *  Delta) competitive where Delta is a problem parameter capturing the number of “clean” page requests. They then prove that no algorithm can do better than a Omega( log( 1/ eps)) ratio. \n\nFor the set-cover problem, they introduce algorithms with achieve a O(1/ eps) ratio which is again shown to be tight. \n", "questions": "I’ve included most of my questions above, my main concern is around this Delta parameter. \nVery minor comment: add the FIF abbreviation on L80 where you first refer to the furthest in the future concept. \n", "limitations": "Limitations are appropriately discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The learning model considered in this paper is well-motivated and, to the best of my knowledge, novel. The ideas are for the most part very well presented. The idea of eps-accurate predictions is clearly introduced and clear. It would be valuable however to include more formal definitions in the main body of the paper. For example, the definition of a competitive ratio is defined in L62-64 in words, however, it would help with understanding if the authors provide a precise, formal definition of this quantity in the context of the caching and set cover problems they consider. \n\nApart from the competitive ratio, there are a number of other quantities which could benefit from having more formal definitions. For example, for caching: phases, and the number of clean pages should have more precise definitions. \n\nFrom examining the upper and lower bounds, it looks like their results are unimprovable up to this factor of \\Delta which captures the number of clean pages requested in a phase. It wasn’t clear to me how to think about this parameter and its relationship to the size of the cache k. Adding further discussion on this point would be helpful.\n\nFrom a significance perspective, the paper appears to make a valuable contribution to the growing literature on learning augmented algorithms. The results are nearly tight for the problems they consider and provide a useful way of leveraging the eps-accurate prediction model which they introduce.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept