Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the control of passing between power-on and several stand-by or idle states for devices like CPUs that may have non-deterministic job arrivals.  The authors model this problem as a ski rental problem, where a prediction on the length of the state is available.  They assume some predicted value with varying noise to emulate predictions coming from a learning algorithm.  They propose an algorithm for this multi-state ski rental problem with 'learned' predictions and numerically compare to other known algorithms.
main_review: The paper is well written and easy to follow.

The motivation for this work was power management, so experiments that show how this algorithm performs in that real scenario would make the paper stronger.

What is the scale of noise used in the experiments, and how should we interpret them?  The noise value in the results goes up to roughly 5, but it's unclear what this means.  Further, at this high end other algorithms like ADJKR trend towards performing better than the proposed algorithms.  Some explanation and discussion here is necessary.

The authors mention 'learning augmented' algorithms.  It's not clear what learning is happening - are the predictions being refined or learned online ?  This doesn't seem to be the case.  It seems the predictions are just some noisy value around the true period lengths?

The paper ends abruptly in the Experiments section.  Some concluding remarks on the results from the experiments are missing.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors provide a new online algorithm for the Dynamic Power Management problem and Ski Rental problem in the learning-augmented setting where the learner has access to predictions.  With inaccurate predictions the algorithm performs as well as classical algorithms, but the algorithm has improved competitive ratio with accurate predictions.  A lower bound is also provided and the algorithm is near optimal.
main_review: The paper deals with the important setting of dynamic power managment, which is a practically useful problem.  To do this, they produce a new ski-rental algorithm in the learning augmented setting.  The addition of predictions seems useful to make the settings more realistic.

The paper is well written and appears to be correct. The work is novel and seems technically challenging, especially the main ski-rental algorithm.  Reduction of DPM to SR seems common, but the use of the monotonicity of the CDFs for this particular ski-rental algorithm was interesting. Using online learning to provide bounds simultaneously for all $\rho$ is important to have a general algorithm, but does not seem to be a main contribution of this work. The lower bound for the learning-augmented setting also strengthens the result.  The experiments don't seem completely necessary for this work but are good to have for completeness. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the online version of the dynamic power management problem with multi-states (DPM). In this problem, the machine has multiple power-save states, different power-save states have different active cost and wake-up cost. Initially, the machine stays in the busy state. The input contains a set of idle periods during which the machine can stay in some power-save state. The length of each idle period is not known by the algorithm. When an idle period is released, the algorithm can make the machine stay in some power-save state for some length smaller than the length of the idle period and pay the corresponding active cost. At the end of each idle period, the algorithm needs to set the machine to be in the busy state and pay the corresponding wake-up cost. The objective is to minimize the total energy consumption of this off and on process. A new online algorithm for the ski rental problem is proposed which can achieve tight approximation ratios together with possessing a monotone property which is crucial in being used to solve the DPM problem studied in this paper. As a by product, for multi-states DPM, a randomized online algorithm with a good approximation algorithm can be derived based on the results in this paper. 
main_review: The main result of the paper is a learning-augmented algorithm for multi-state DMP that achieves a good consistency and robustness at the same time (Corollary 8). The robustness directly implies a e/e-1 randomized online algorithm for general DMP. To achieve the above result, the authors give a new algorithm for the ski-rental problem which is equivalent to 2-state DMP. And then, the authors run k ski-rental algorithms in parallel in each idle period. The correctness of the above reduction between 2-state DMP and multi-state DMP relies on the fact that the algorithm for 2-state DMP has a monotonic property. The main technique in the algorithm for the ski-rental problem is a probability density function defined by the authors. By carefully choosing the value of the density function according to the predicted value, the authors show that the algorithm is optimal. Finally, the authors show another similar algorithm that almost achieves the same performance but suitable for a wider range of predictions. The main technique of this part is the reduction between DMP and  Metrical Task System.

This work is the initial study of the multi-state DMP in the learning augmented setting. The proposed algorithm achieves the optimal ratio e/e-1 when the prediction is untrusted and therefore the algorithm is robust. The competitive ratio of the proposed algorithm can be arbitrarily close to 1 when the prediction is reliable and thus the algorithm is consistent. Although there are some results that build on the previous results, the overall technique is sound and non-trivial. On the other hand, the decision about which results are theorems or corollaries seem not quite suitable in some places. For example, some theorems should be stated as a lemma, like Theorem 3, while some lemma or corollary should be stated as a theorem, like Corollary 8. 

There is also a lack of high level illustration of the importance of certain results, or the comparison with earlier results. For example, for the two earlier papers about ski rental in the learning framework, do their algorithms satisfy the monotone property. If no, then the contribution of this paper is much more since they give a new algorithm not only satisfying some property which earlier algorithms do not satisfy but also has better bounds than previous algorithms.

A minor correction:

Page 5, line 182, should be A’.


limitations_and_societal_impact: Nil.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper looks at learning-augmented versions of the ski rental problem, and derives theoretical bounds (upper bounds via an algorithm and lower bounds) on the competitive ratio that can be achieved with noisy hints.  It then additionally extends these results to other variations of the problem (dynamic power management, metrical task systems);  in particular, this gives a practical motivation for this particular study.  
main_review: I am generally a fan of learning-augmented algorithms, and believe it is a good direction for the theoretical computer science community to go to make their work more relevant. I acknowledge that sadly it is not clear the theory community is entirely on board yet. It is perhaps less clear how the work in learning-augmented algorithms generally has an immediate effect on the AI community, although as with any application of AI, I think the application area may, in many circumstances, be of interest to the AI community.

This paper covers one of the "most natural" online algorithm problems (ski rental problem), which is well known and well studied in the online literature.  I am not clear if the ski rental problem and its variations are of wider interest to the AI community, but it is a fundamental problem, and the authors do a suitable job of providing a practical motivation (dynamic power management) that increases the "weight" of the problem being studied.  The theoretical work is well developed and would be worthy of publication in a theoretical conference, although it is perhaps unclear what level of conference it would reach.  The results are complete and in particular the characterization of the tight lower and upper bound is compelling.  The paper is well presented.  

Because learning-augmented algorithms is such a recent area it is a bit difficult to determine what is the right "level" for acceptance.  I am reading a number of papers on this theme;  this is clearly one of the better ones.  I do think it provides a useful and fairly compelling example of the genre, so while I would still deem it borderline I would be inclined to accept, although I am open to the viewpoints of the other reviewers.  

[Final Note;  I have considered the author response.  I believe the authors attempted to address the concerns presented in a reasonable manner.  While I am not changing the final score -- I still think it is above the acceptance threshold but only marginally so -- I remain inclined to accept the paper, which seems consistent with other reviews.]
limitations_and_societal_impact: Because this is primarily a theoretical paper and I do not think we need worry about potential negative social impacts;  I do appreciate the potential positive impact of the primarily theoretical work in that the authors do describe a potential real-worldd application that is reasonably realistic. I believe the authors have addressed from the theoretical perspective the limitations of their work.
review_title: null

Meta-review: The reviewers generally agree that dynamic power management is an interesting problem that motivates further study of the ski-rental problem in the learning-augmented algorithms framework. Reviewers da7H and Bp21 both say that the paper is well-written and organized. Reviewers Bp21, SQBd, and 53BA found the theory well developed and insightful (especially the reduction from DPM to SR and using the fact that it preserves monotonicity). On the other hand, reviewer SQBd asked for more high level illustrations of the important results and comparisons with prior work, which would be good to add to the paper. Reviewer da7H asked for real world experiments, and the authors provided these during the rebuttal period. If possible, it would be good to add these to the final version of the paper. Overall the paper has good support from the reviewers, so I recommend accept.
Decision: Accept (Poster)