Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: - Strengths:
    - 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.
    - The technical results appear correct (although I did not verify all the details in the supplement); and the analyses are clean.
- Weaknesses:
    - 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.
    - 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.
    - The paper would be stronger with a more thorough discussion (or perhaps empirical support) of the modeling assumptions and why they were chosen.
- Minor:
    - Line 84: The acronym “FIF” (assuming it means “furthest in the future”) should be defined before its first use, perhaps in Line 80.
    - Line 323: “revealted” → “revealed”
    - References: Reference [25] is a duplicate of [24]; likewise for [28] and [27].
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?
- 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strength:
- 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.

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

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

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

- Line 76: ``the minimize the number of page swaps ".

- Line 84: ``FIF"  should be given the full name the first time it is used.
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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

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

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

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

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

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

- 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.
questions: 1) Is there a more comprehensive lower bound for caching? (e.g. for larger epsilon)
2) 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?
3) 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). 
4) 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
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: 
The 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. 

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

For the set-cover problem, they introduce algorithms with achieve a O(1/ eps) ratio which is again shown to be tight. 

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. 

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

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

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


questions: I’ve included most of my questions above, my main concern is around this Delta parameter. 
Very minor comment: add the FIF abbreviation on L80 where you first refer to the furthest in the future concept. 

limitations: Limitations are appropriately discussed.
review_title: null

Meta-review: metareview: This paper is part of a recent line of work that augments algorithms with ML predictions. It introduces an interesting new model where the quality of a prediction is measured by its accuracy, instead of its error, and gives strong competitive ratios for the online problems of caching and covering augmented with such predictions. This new model could influence future work in this area.
confidence: Less certain
Decision: Accept