Summary and Contributions: Comments after rebuttal: thanks to the authors for addressing some of the issues raised in my review. It is a pity though that the authors did not implement the e/(e-1)-competitive randomized algorithm, it is a really simple algorithm. Overall, my score remains unchanged. ---- The paper considers online algorithms that make use of predictions. Such algorithms provide worst-case guarantees, while utilizing predictions to improve their performance if those predictions are close to correct. Two specific problems considered are ski rental and TCP acknowledgment. Both are classic problems well-studied in the online algorithm literature. The paper presents algorithms for the aforementioned problems, as well as their experimental evaluation (on synthetic data).
Strengths: - The algorithms that incorporate multiplicative weights approach. This seems like an interesting research direction. - For some range of parameters, the proposed algorithms improve (in theory and experimentally) over prior bounds
Weaknesses: - It is not clear how natural the synthetic data sets are, and how they were selected. For example, ski rental is evaluated on instances selected uniformly at random from the intervals {1....4b} or {1...2.5b}. What is the reason for choosing these ranges ? Why are they different ? Note that if the instances were instead selected uniformly at random from {1...b}, then the classic 2-competitive algorithm would actually achieve optimal cost, so the proposed algorithms would be not better (and probably worse) than what is known. So the size of the range matters. - It would also be helpful to experimentally compare the proposed algorithms to the classic approaches (2-competitive deterministic and e/(e-1)-competitive randomized).
Correctness: Yes, although see comments about experiments above.
Clarity: Yes.
Relation to Prior Work: Yes.
Reproducibility: Yes
Additional Feedback:
Summary and Contributions: The paper considers ski rental and related online problems, in the context of predictions, primarily based on using the Hedge algorithm.
Strengths: This provides a nice framework, extending some of the ideas of consistency and robustness in previous work, providing potentially useful frameworks for further work.
Weaknesses: Most everything seems to boil down to "Use a standard hedge algorithm along with the prediction as a prior", which isn't especially compelling. The experiments seem poorly designed.
Correctness: The proofs and such are correct. The authors need a more robust set of experiments.
Clarity: The paper is a bit notation heavy at times. I consider labeling the 3 decisions for ski rental 0|0, 1|0, 1|1, for example, annoying and unhelpful.
Relation to Prior Work: Relation to prior work is discussed.
Reproducibility: Yes
Additional Feedback: There were many thinks liked about the paper, including the idea of having an ML-advisor algorithm be e-close and alpha-accurate. I also liked the interpretation of a Hedge algorithm with an advisor give on page 5. In some ways the Hedge formalization, though, seems to minimize the use of predictors to just giving a prior. As someone interested in this area I find that a not especially hopeful or compelling message, but perhaps for some problems that's the right methodology. The experiments don't seem that useful. In particular, for Figure 1, choosing lambda = 1 just gives the "standard" 2-competitive type algorithm for the ski rental problem, so the results are unsurprising. (Ideally, one should vary lambda with sigma, as ostensibly one has some idea of the noise.) Indeed, using normally distributed noise for the predictor is somewhat disappointing and does not, I think, show the strength or weaknesses of predictors adequately. I realize you are short on space, but better experiments (with other failure modes in the predictors) seems important to test. Some discussion of Figure 2 seems warranted. The results look interesting -- what should we be taking away from the Figure? Post feedback: Overall I thought the authors responded well to the review concerns. While I am not changing my score, I remain favorably disposed to acceptance.
Summary and Contributions: The authors studied the online rent-or-buy problem and how predictions made by machine learning can be incorporated. The authors proposed a new algorithm where performance guarantees come in terms of the accuracy of the prediction, where accuracy can be problem-specific. The algorithmic framework is applied to both the ski-rental problem and the dynamic TCP acknowledgment problem and is shown to be closed to optimal with accurate predictions via simulation.
Strengths: The overall idea of using ML prediction to improve performance for online algorithm when prediction error is small while still keeping the worst case guarantee is appealing. However, this seems to come from [13].
Weaknesses: 1. There is not much distinction in terms of novelty in methodology and theoretical results compared to [13]. The authors introduced the accuracy measure for prediction uncertainty but did not fully justify why this is a good measure. 2. The theoretical results are a little weak, the accuracy term does not improve the competitive ratio in Theorem 2.2, rather, it only appears in the constant term. 3. The robustness and consistency guarantee of Algorithm 1 come from two different set of parameter setting, this seems a little strange. Is it possible to have both robustness and consistency guarantee with a common set of parameters? 4. It would be good to show the actual performance of Algorithm 5 compared to existing online algorithm
Correctness: The claims and methods seem to be correct.
Clarity: Overall the presentation is clear.
Relation to Prior Work: The distinction between this work and [13] is not very clear.
Reproducibility: Yes
Additional Feedback: