Review for NeurIPS paper: Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online 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.