Summary and Contributions: The paper considers the ski-rental and non-clairvoyant job scheduling problems an online model which mixes predictions with the adversarial setting. The goal is to optimize the trade-off between performance under good predictions (consistency) and performance under bad predictions (robustness). Both problems were given upper bounds in foundational prior work on the model. The present work provides new lower bounds which are tight for the ski-rental problem. They also present a tight algorithm for the special case of non-clairvoyant job scheduling with only two jobs. UPDATE: I have read the rebuttal and other reviews. My score remains the same.
Strengths: The foundational papers on this model [34,42] have gotten a lot of attention and this complements that important work well. The paper is well-written with good presentation.
Weaknesses: No major weaknesses.
Correctness: The claims appear to be correct.
Clarity: Yes.
Relation to Prior Work: Along with citing [18, 15, 35, 37, 39], the authors may want to address the following more closely related paper which mixes the model of [15] with an adversarial setting. Online allocation with traffic spikes: Mixing adversarial and stochastic models Hossein Esfandiari, Nitish Korula, Vahab Mirrokni
Reproducibility: Yes
Additional Feedback: The robustness of the random algorithm in [42] is stated as a function of the budget, but the robustness stated in Theorem 1.2 here is not. Is there significance to the problem with only two jobs aside from being a natural special case to explore theoretically? I am not aware of anything, but it seems like it could be a subroutine for something. If so, explaining this would strengthen the result. Regarding footnote 1: Expected competitive ratio also commonly takes expectation over the randomness in the online model even for deterministic algorithms.
Summary and Contributions: The paper considers the problem of designing online algorithms that utilize machine learning predictions for the ski rental and non-clairvoyant scheduling problem. In the learning augmented setup, the consistency of an algorithm is defined to be its competitive ratio given perfect predictions whereas the robustness of an algorithm is defined to be its competitive ratio when the predictions are arbitrarily erroneous. Unlike most recent work in this area, the paper focuses on providing lower bounds on the tradeoffs between robustness and consistency in this framework. In particular, they show that for the ski rental problem the learning augmented algorithms of [42] actually yield the optimum tradeoff between robustness and consistency (for both deterministic and randomized algorithms). The proofs of these lower bounds are non-trivial but not surprising. The paper also shows a lower bound for the non-clairvoyant scheduling problem to minimize weighted completion time although it does not match the algorithms of [42]. For the special case of only 2 jobs, the paper develops a new algorithm that yields a much better tradeoff than [42] and also gives a matching lower bound.
Strengths: This is among the first papers to show lower bounds on the trade-offs between robustness and consistency in learning-augmented algorithms. The techniques employed are non-trivial and lead to some interesting insights - for e.g. that the learning augmented algorithm for non-clairvoyant scheduling is probably not optimal.
Weaknesses: The algorithmic contributions of the paper are a bit weak. In my opinion, the paper will be significantly strengthened if the analysis of the final algorithm could be improved to the case with more than 2 jobs.
Correctness: Yes
Clarity: Yes
Relation to Prior Work: Yes
Reproducibility: Yes
Additional Feedback: Other comments: - In Theorems 1.1 and 1.2, mention “deterministic algorithm” and “randomized algorithm” respectively. Currently although the theorem is titled appropriately, the statement does not specify deterministic / randomized algorithms at all. - In the section of non-clairvoyant scheduling (page 3), the term “makespan” is misused. In typical scheduling literature, makespan is always used to denote the earliest time by which all jobs are scheduled. The quantity measured here is simply called “total completion time”.
Summary and Contributions: The authors study performance of classic online algorithms for ski-rental and scheduling with ML advice. The paper proposes algorithms that have guarantees better than the worst-case when the predictions are good and not much worse than it when the advice is bad.
Strengths: Learning augmented algorithms is an important paradigm for designing more practical algorithms for many online problems such as caching, scheduling, routing, etc. The paper proposes simple algorithms with lower bounds for both ski-rental and non-clairvoyant scheduling. The algorithm for scheduling problem is tight.
Weaknesses: The analysis for the ski-rental problem is rather straightforward. Thm 1.1 is immediate. A simple proof is the following: Suppose the prediction is B. Then, to get consistency of 1 + \lambda, you cannot buy after \lambda B. But, if you buy at or before \lambda B, then robustness is 1 + 1/\lambda. Thm 1.2, while offering a more technical proof, does not offer significantly new insights.cIt'll help to add some empirical evaluation of the algorithms. -- Update -- The author's have responded to my questions satisfactorily.
Correctness: I did not carefully read all the theorems and proofs. The claims in the paper look correct.
Clarity: The paper is well written and all the details could be easily followed.
Relation to Prior Work: A comparison with the algorithm proposed in Gollapudi and Panigrahi, ICML 2019, for the single expert case will help differentiate the proposed solutions better.
Reproducibility: Yes
Additional Feedback: