- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
Online algorithms with prediction. Predictions describe exactly an optimal solution. Early work in learning augmented online algorithms studied simple combinations of two opposite behaviors, namely following completely the prediction or ignoring the prediction. In literature two approaches were studied:
(1) follow the prediction until either (two different approaches) the prediction appears to be wrong, or the current competitive ratio would exceed some threshold. And in that case switch to the best known algorithm without prediction.
(2) Distribute the resources or the probability space in two parts, and dedicate each to one of the oppositive behavior.
The paper studies the second approach, and claims novelty.
By definition a c-competitive online algorithm needs to be c-competitive on any prefix of the request sequence. The paper studies another measure, where an algorithm is anytime c-competitive iff it is c-competitive on any factor of the request sequence.
Results: for the metrical task system problem, maximum cardinality bipartite matching, paging and more generally the metrical task system problem the paper analyses their algorithm performance for consistency, robustness and any time competitive ratio. The performance is measured as a function of tau, a probability and tradeoff parameter of the algorithm, n or k, parameters of the instance size and beta a parameter describing how bad the prediction is.
Critical strengths
The paper claims a novel framework and applies to 3 important problems.
Critical weaknesses
I cannot make sense of the conclusion of the introduction: does there exist a model whose formal guarantees depend solely on the problem?
The paper claims novelty for the online algorithms with unreliable guidance model. This is a clear oversell, I have seen these models in the past. And calling the combination (referred as (2) above) a compiler is overselling.
An important reference is missing in the introduction. The studied problems fall typically in the primal dual framework, and therefore the paper should compare their contribution with The Primal-Dual method for Learning Augmented Algorithms by Bamas, Maggiori, Svensson.
The prediction model where the a solution is given is easy to analyze but is way to idealized in a machine learning context. I agree that analyzing an algorithm in this model is easier than in a more realistic model, where ML can predict some learnable aspects of the input sequence. I just don't like the studied model.
The notion of anytime competitiveness is interesting, but again the paper oversells it. This kind of measure has been studied in the past and references are missing:
Hazan and Seshadhri (2007) Adaptive Algorithms for Online Decision Problems
Daniely, Gonen, and Shalev-Shwartz (2015) Strongly Adaptive Online Learning
The community on online algorithms with prediction nowadays studies
- smoothness, i.e. performance as function of prediction error
- learnable predictions.
The paper does not address those, hence I find it not so interesting.
Questions for authors
The paper does not say if and how AI was used for this work.
In the description of the algorithm you should make clear if the random decision is done once for all from the beginning or for every request.
I don't understand while in line 227 the cost of the algorithm is written as a difference of costs.
Section 2. I am wondering if you can lighten the notation. I feel it obfuscates the key concepts.
I don't agree that beta is the smoothness. It is just the parameter which allows to generate the Pareto-points of the consistency-robustness tradeoff of the algorithm. Smoothness is the performance of the algorithm with the prediction error, and more precisely its slope.