Improving Online Algorithms via ML Predictions
In this work we study the problem of using machine-learned predictions to improve the performance of online algorithms. We consider two classical problems, ski rental and non-clairvoyant job scheduling, and obtain new online algorithms that use predictions to make their decisions. These algorithms are oblivious to the performance of the predictor, improve with better predictions, but do not degrade much if the predictions are poor.
Update after rebuttal & discussion: I am satisfied with the authors' response, and while I agree with another reviewer that a more general setup/investigation would be nice, I believe the present work focussing on special cases/problems is of sufficient novelty and marks a good first step toward more general frameworks on the future research agenda. Thus, I uphold my vote and strongly recommend accepting this submission.  -------- The present paper introduces deterministic and randomized algorithms for online ski rental and non-clairvoyant single-machine scheduling problems that incorporate (machine-learned) predictions in order to improve competitiveness in case of good predictions while maintaining robustness, i.e., avoiding performance degradation, in case of bad predictions. Both problems are intuitively amenable to make use of predictions of rental or job processing times, respectively, and the proposed algorithms show how such intuition can be exploited on-the-fly for robust and competitive online solution algorithms. Thus, the work is well-motivated and contributes practically interesting methods to well-studied and relevant problems. The paper is also generally well-written and mostly easy to follow. Therefore, I recommend accepting this submission.  Although the considered online-optimization problems may be easily described, they are in fact somewhat challenging. A clear strength of the present work is fusing known approximation approaches for either problem with the assumed availability of data predictions into new online algorithms that are  *provably* robust in the sense that they do not deteriorate much (w.r.t. the best-known competitive ratios – i.e., ratio between computed solution and the theoretical „offline, clairvoyant“  optimum – achievable by algorithms not exploiting predictions) in case the predictions are rather bad, but are *provably* able to improve competitiveness if the incorporated predictions are good. Some numerical experiments further support the theoretical results and demonstrate practicality of the proposed schemes. I particularly like the theoretical disconnection of the introduced data-driven algorithms and the actual origin of the predictions that are exploited.  A weakness of the paper is that some parts are a bit vague or unclear, and that it contains various typos or formatting issues. I shall provide details in the following list; typos I found will be listed afterwards.  1. In the section about related work, I was wondering whether there is no related literature from the robust scheduling literature. I am not overly familiar with the area, so I cannot give concrete references, but I am aware that robust scheduling is a very large field, so I would be surprised if there were no robust online scheduling problems/algorithms that are connected to the work at hand in one way or another. Could you please shed some light on this aspect (and provide some reference(s) if appropriate)?  2. From the description in the „main results“ section of the Introduction, the precise connection between competitive ratio and robustness or consistency did not become entirely clear to me. Please provide some additional clarification on what is to be compared here – in particular, I also stumbled over why (as stated in several corresponding theorems) one ends up with competitive ratios „at most min{ robustness-ratio, consistency-ratio }“. At first glance, I had thought that if an algorithm does well for good predictions but the robustness bound is bad, that the latter should dominate. As this is apparently not the case, I ask for a brief explanation/clarification, preferably already in the introduction, as to why the minimum of the two values yields a bound on the competitive ratio.  3. In Algorithm 3, please clarify what „chosen“ means exactly. (Is it „drawn uniformly at random from the k (or l, resp.) values q_i (r_i, resp.)“ ? Or „chosen as index yielding maximal q_i/r_i-value“? Or something else?) Also, on a higher level, what makes q_i and r_i probability distributions?  4. On p.5, line 151 (multi-line inequality chain): I could not immediately verify the 3rd equation (in the middle line of the chain) – if it is based on a known formula, I do not recall it (maybe provide a reference?), otherwise please elaborate.  5. Please provide a reference for the statement that „... no algorithm can yield any non-trivial guarantees if preemptions are not allowed“ (lines 187-188, p. 6, 1st paragraph of Section 3).  6. At the very end of Section 3, you omit a proof for lack of space. If possible, please do include the proof in the revision (at least as supplementary material, but maybe it fits into the main paper after all).   7. Beginning of Section 2.2: should it not be „... must incur a competitive ratio of at most $b$.“ (not „at least“) ? The worst case would be x=1, then the ratio would be b/1=b, but in all other cases (x>1), the ratio is either b/x or eventually b/b=1 (as soon as x>b).   8. In Section 2.4, perhaps add „as in Theorems 2.2 and 2.3, respectively.“ to the sentence „Both Algorithms 2 and 3 extend naturally to this setting to yield the same robustness and consistency guarantees.“ ?   Finally, here's a (sorry, quite pedantic) list of typos or formatting improvement suggestions for the authors' consideration: -- line 1: „machine-learned“ (hyphen is missing here, but used subsequently) -- l. 13: I think it should be „aimed at tackling“, not „aimed to tackle“  -- l. 18: missing comma between „Here“ and „the effort...“ -- The dollar sign (used in the context of the ski rental problem) somehow looks awkward; actually, could you not simply refrain from using a specific currency?  -- Regarding preemptions, I think „resume“ is more common than „restart“ (ll. 54, 186) -- l. 76: I think it should be „used naively“, not „naively used“ -- Proof of Lemma 2.1, last bullet point: to be precise, it should be „ … x < b+x-y ... “ -- l. 119: comma is missing after „i.e.“ -- Proof of Theorem 2.2: There is a „d“ that should probably be a „b“ (ll. 134 and 136) -- Throughout the paper, you use four different ways to typeset fractions: in-line, \frac, \tfrac, and that other one with a slanted „frac-line“. I would appreciate a bit more consistency in that regard. In particular, please avoid using \frac when setting fractions in-line, as in Theorem 2.2, where it messes up the line spacing.  -- l. 144 (1st sentence of Sect. 2.3): comma missing after „In this section“ -- p. 5: the second inequality chain violates the textwidth-boundary – can probably easily be fixed be linebreaking before the last equality- rather than the first inequality-sign.  Also, „similar to“ should be „similarly to“ (ll. 157 and 159). -- l. 216, comma missing after „i.e.“ -- Lemma 3.2: Statement should start with a „The“ (and avoid \frac in-line, cf. earlier comment) Given the end of the proof, the statement could also be made with the less-coarse bound, or writing „less than“ instead of „at most“. -- l. 234: insert „the“ between „...define d(i,j) as“ and „amount of job“ (perhaps use „portion“ instead of „amount“, too) -- l. 238: missing comma between „predicted“ and „the longer job“ -- l. 243: suggest replacing „essentially“ by „asymptotically“ -- l. 249: comma missing after „Finally“ -- Theorem 3.3: Statement should start with a „The“. -- l. 257: comma missing after „e.g.“ -- l. 276: hyphenate „well-modeled“ -- l. 279: comma missing before „where“ -- Ref. [11]: use math-mode for e/(e-1), and TCP should be upper-case -- Ref. [14]: „P.N.“, not „PN“, for Puttaswamy's initials -- Ref.s [15, 16, 17]: Journal/Source ? Page numbers?  -- Generally, the reference list is somewhat inconsistent regarding capitalization (in paper and journal titles) and abbreviations (compare, e.g., [11] Proceedings title with [21] Proceedings title).