Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds
Authors: Antonios Antoniadis
Christian Coester
Marek Elias
Adam Polak
Bertrand Simon
Venue: NeurIPS 2021 Poster (2021)
Keywords: Learning-augmented algorithms
online algorithms
energy-efficient algorithms
power management
ski rental

Abstract: We study the online problem of minimizing power consumption in systems with multiple power-saving states. During idle periods of unknown lengths, an algorithm has to choose between power-saving states of different energy consumption and wake-up costs. We develop a learning-augmented online algorithm that makes decisions based on (potentially inaccurate) predicted lengths of the idle periods. The algorithm's performance is near-optimal when predictions are accurate and degrades gracefully with increasing prediction error, with a worst-case guarantee almost identical to the optimal classical online algorithm for the problem. A key ingredient in our approach is a new algorithm for the online ski-rental problem in the learning augmented setting with tight dependence on the prediction error. We support our theoretical findings with experiments.

Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds
Antonios Antoniadis University of Twente Enschede, The Netherlands antoni adis@utwente. nl
Christian Coester
Tel Aviv University Tel Aviv, Israel
christian. cew.eiaan.oesttermmaal..oom
Marek Eliáš
Adam Polak EPFL
Bertrand Simon
Università Bocconi
IN2P3 Computing Center, CNRS
Milan, Italy
Lausanne, Switzerland adam. odam.polak@epfl.c
Villeurbanne, France bertrand. seerradd.simoneee simondcnrs.
marek. www.ssuuiibccoooi.....
Abstract
We study the online problem of minimizing power consumption in systems with multiple power-saving states. During idle periods of unknown lengths, an algorithm has choose between power-saving states of different energy consumption and wake-up costs. We develop decisions based on (potentially inaccurate) predicted lengths of the idle periods. The algorithm's 's performance is near-optimal when predictions are accurate and degrades gracefully with increasing prediction error, with a worst-case guarantee almost identical to the optimal classical online algorithm for the problem. A key ingredient in our approach is a new algorithm for the online ski rental problem the learning augmented setting with tight dependence on the prediction error. We support our theoretical findings with experiments.
online algorithm that makes
Introduction
Energy represents up to 70% of total operating costs of modern data centers [4 and one of the major -feeite-of-service parameters in battery-operated devices. In order to ameliorate this, contemporary CPUs are equipped with sleep states to which the processor can transition during periods of inactivity. In particular, the ACPI-standard (25 specifies that each processor should possess, along with the active state CO that is used for processing tasks, at least one sleep state C1. Modern processors generally possess more sleep states C2....: for example, current Intel CPUs implement at least 4 such C-states [19]. Apart from CPUs, such sleep states appear in many systems ranging from hard drives or mobile devices the start-stop feature found in many cars, and furthermore often employed when rightsizing data centers 2
Intuitively, in "deeper" sleep state, the set of switched-off components will be superset of the corresponding set in a more shallow sleep state. This implies that the rumning cost for residing in that deeper state will be lower, but the wake-up cost to return to the active state CO will be higher compared to a more shallow sleep state. In other words, there a tradeoff between the running and the wake-up cost. During each idle period, dynamic power management (DPM) strategy has decide in which state the system resides at each point in time, without a-priori knowledge about the duration of the idle period. Optimally managing these sleep states is challenging problem due to its online nature. On the one hand, transitioning the system to a too deep state could be highly suboptimal if the idle period ends shortly after. On the other hand, spending too much idle time in shallow state would accumulate high running costs. The impact of DPM strategies in practice
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

has been studied for instance in data centers, where each machine may be put to sleep mode if no request expected. See the study of Lim al. (34 on multi-tier data centers.
The special case of 2-state DPM systems, i.e., when there is only a single sleep state (besides the active state), is essentially equivalent to the ski rental problem,
of the most classical problems and of central importance in the area of online optimization [39 26). This problem is defined as follows: A person goes skiing for an unknown number of days. On every day of skiing, the person must decide whether to continue renting skis for one more day or to buy skis. Once skis are bought there will be no more cost on the following days, but the cost of buying much higher than the cost of renting for a day. It is easy to see that this captures a single idle period of DPM with a single sleep state whose running cost is O: The rental cost corresponds state and the cost of buying skis corresponds to the wake-up cost; transitioning to the sleep state corresponds to buying skis. Given this equivalence, the known 2-competitive deterministic algorithm and e/(e 1) = 1.58-competitive randomized algorithm for ski rental carry over to 2-state DPM, and these competitive ratios are tight. In fact, it was shown by Irani al. [28 and Lotker al. (36 that the same competitive ratios carry over even to multi-state DPM. Ski rental, also known as rent-or-buy problem, is fundamental problem appearing in many domains not restricted to computer hardware questions. For the AI community, this problem for example implicitly appears in expert learning with switching costs: paying the price to switch to a better expert allows to save expenses in the future.
the running cost of the active
Beyond these results for the classical online setting, (28) also gave a deterministic e/(e 1)- competitive algorithm for the case in which the length of the idle periods is repeatedly drawn from a fixed, and known, probability distribution. When the probability distribution is fixed but unknown they developed an algorithm that learns the distribution over time and showed that it performs well in practice. Although it is perhaps not always reasonable to assume a fixed underlying probability distribution for the length of idle periods, real-life systems do often follow periodical patterns so that these lengths can indeed be frequently predicted with adequate accuracy, see Chung et al. [88] for a specific example. Nevertheless, is not hard to see that blindly following such predictions can lead to arbitrarily bad performance when predictions are faulty. The field of learning-augnenn augmented algorithms (38 is concerned with algorithms that incorporate predictions in robust way.
In this work, we introduce multi-state DPM to the learnng--augmente, augmented setting. Extending ideas of (28 and (36. we give a reduction from multi-state DPM to ski rental that is applicable to setting. Although ski rental has been investigated through the learning-
the learning-augmentt augmented algorithms lens before 40 44], earlier work has focused on the optimal trade-off between consistency (i.e., the performance when predictions are accurate) and robustness (i.e., the worst-case performance). To apply our reduction from DPM to ski rental, we require more refined guarantees for saamingg-uggmnteed ski rental. To this end we develop a new Baaninggauugment ski rental that obtains the optimal trade-off between consistency and dependence on the prediction error. Our resulting algorithm for DPM achieves competitive ratio arbitrarily close to in case of perfect predictions and its performance degrades gracefully to a competitive ratio arbitrarily close to the optimal robustness of e/ e/(e- 1) x 1.58 as the prediction error increases.
algorithm for
Potential negative societal impact. This is work of theoretical nature and we are not aware of potential negative societal impact. That said, we cannot rule out future misuse of the contained theoretical knowledge.
1.1 Formal definitions
Problem definition. In the problem of dynamic power management (DPM), we are given k + 1 power states denoted by 0, I..... k, with power consumptions ar >.. ag 0 and wake-up costs Bo <... < Br.. For state 0, we have Bo = 0 and we call this the active state. The input is a series of idle periods of lengths (,.... er received online, i.e., the algorithm does not know the length of the current period before it ends. During each period, the algorithm can transition to states with lower and lower power consumption, paying energy cost xa, for residing in state for time x. If j is the state at the end of the idle period, then it has to pay the wake-up cost Bj to transition back to the active state O. The goal is to minimize the total cost.
In the learning-aute -agmeented setting, the algorithm receives at the beginning of the ith idle period a prediction T, 0 for the value of as additional input. We define 7) oolT; Egl to be the error of the ith prediction, and n7 Σ n7 to be the total prediction error.
2

---

(Continuous-ting) time)) ski rental is the special case of DPM with k = 1, 0 and single idle period of some length C. In this case, we call a ap the rental cost, B B1 the buying cost, and & the length of the ski season. In learning-augmented ski rental, we write the single prediction :=
(p, j)) compettiiiiee Classical online algorithms are typically analyzed in terms of competitive ratio. A (randomized) algorithm A for an online minimization problem is said to be p-competitive (or alternatively, obtain a competitive ratio p) if for any input instance.
() S p OPT +c.
where (Os and OPT denote the (expected) cost of A and the optimal cost of the instance and c is constant independent of the online part of the input (i.e., the lengths 4 in case of DPM). For the ski rental problem one requires = 0, since the trivial algorithm that buys at time 0 has constant cost B.
In the learning- augmented setting, for p 1 and μ O, we say that A is (p, competttive if
cost(A) S p OPT + +
(2)
for any instance, where is the prediction error. This corresponds to a competitive ratio of p + OPT (with c 0). While this could be unbounded as T/ co, our DPM algorithm achieves favorable competitive ratio even in this case (see Theorem where we take the minimum over range of pairs (p. (). including μ 0).
"
For (p. c)-competitive algorithm, is also called the consistency (i.e., competitive ratio in case of perfect predictions) while μ describes the dependence on the prediction error.
1.2 Our results
Our first result is a (p. μ)) commptttiive algorithm for ski rental that achieves the optimal μ correspond- ing the given p. For p E [1, 1- let
- p e-1
T)e |
u(p) == max
p(1 ((1-TTee
1n2
where 7 E [0, 1] is the solution to e = 1
Let = 1.16 be the value of p for which both terms the maximum yield the same value. The first term dominates for > f and the second term if p < p. Note that μ(1)
and μ (--)) O. See F for illustration.
Theorem 1. For any p [1, -. there is (p. -(p))ccompeiitiiee randomized algorithm for aagnninee ski rental, i.e., given prediction with error n, its expected cost at most P 1PT+u((p) .7.
Note that p < 1 is impossible for any algorithm (due to the case 1 0) and > since p ب already achieves the best possible value of µ 0.
ب is uninteresting
We also prove a lower bound showing that u(p) defined (3) is the best possible. Theorem 2. For any p E [1, = and any (randomized) algorithm A, there is ski rental instance with some prediction error such that the expected cost of A is at least OPT +p(p)n
However, for most values of the prediction it is possible achieve better μ μ(p), and p(p)
only captures the worst case over all possible predictions т. The proof of Theorem iis sketched in Section The complete proofs of Theorems I and 2 are provided in the full version [ in the supplementary material.
In Section 3 we give reduction from DPM to ski rental in the learning augmented setting, provided that the ski rental algorithm satisfies a natural monotonicity property (defined formally in Section B):
Lemma 3. If there is a monotone (p. μ) competitive ski rental algorithm, then there is a (p.H)- competitive algorithm for DPM.
Since our ski rental algorithm is monotone, this directly yields a (p. (((p)))-oopptitivy algorithm for DPM. From the special case (p. (z². 0), this theorem directly implies the following result for classical DPM (without predictions), which was first proved by Lotker al. (6 for the equivalent multi-slope ski rental problem:
3

---

1.7
1.6
Competiive reto
1.5
1.4
13
1.2
Online algorithm
Blindly follow predictions algorithm
11
1.0
1.1
8
1.2
1.3
1.4
1.5
1.6
1.0
0.0
0.4
0.6
1.0
// OPT
Figure Illustration of p(p) and of the resulting competitive ratio in function of n/PT.
Corollary 4 (33 There competttiee randomized online algorithm for DPM (without
predictions).
Using techniques from online learning, in way similar to [5), we show in Section how to achieve "almost" (p.p(())-comppettttten
simultancously for all p:
Theorem 5. For any > O, there is aangeeeeed algorithm A for dynamic power manage- ment whose expected cost can be bounded as
cost(A) & (1 é) min {p OPT +u(p) 7/ p [1. ( log )
The above theorem gives competitive ratio arbitrarily close min(p μ(p) J which is equal to if = 0 and never greater than < In particular, we achieve a performance that degrades gracefully from near-optimal consistency to near-optimal robustness as the error increases See Figure I (right) for an illustration.
In Section 5 we illustrate the performance these algorithms by simulations on synthetic datasets, where the dependence the prediction error be observed as expected from theoretical results.
1.3 Related work
Algorithms. Learning augmented algorithms have been very active area of research since the seminal paper of Lykouris and Vassilvitskii (37. We direct the interested reader
35 for recent results on secretary problems, paging, k-server as well as scheduling problems. In the following we survey some results in the area more closely related to our work.
survey 38 by Mitzenmacher and Vassilvitskii, well as 7 20 37 42
The ski rental problem has already been studied within the context of learning augmented algo- rithms. Here, the main objective
optimize the tradeoff between consistency and robustness (performance on perfect predictions and worst-case performance). The first results are due to Purohit al. [40] who propose a deterministic and a randomized algorithm. A hyperparameter allows to choose a prescribed consistency p and leads to corresponding robustness. They also present linear dependency on the error: their randomized algorithm is -oompetiiiii for p 2 with larger p allowing for better robustness. Note that such guarantee of (p.p)-competitiieene valuable in our model where we do not focus on robustness as blindly following the predictions leads to a (1, >-comettitive algorithm. Wei and Zhang [4 show that the consistency robusttesss tradeoff achieved by the randomized algorithm of 40 is Pareto-optimal. Angelopoulos et al. [4] propose deterministic algorithm achieving a Pareto-optimal consistency / robustness tradeoff, but with no additional guarantee when the error is small. Interestingly, these algorithms not focusing on (p. p) --competitiveness are naturally monotone, easily extend to DPM by Lemma contrarily to the tight algorithm we present in this paper. Nevertheless, experimental data (Section 5 seem to indicate that our algorithm optimizing (p, -ompeeiitiveness for ski rental leads to better algorithms for DPM. A variant with multiple predictions was also studied in [1].
is not
As we will see in Section 4 DPM can be cast as a problem from the class of Metrical Task Systems (MTS). Antoniadis et al. gave (1, 4) competitive within their prediction setup.
augminnted algorithm for MTS that can be interpreted as
At first glance, our consistency and robustness might seem to contradict the lower bound of Wei and Zhang for ski rental. However, [44 crucially uses 0 in the definition of competitiveness for ski rental.
A

---

A different problem related to energy conservation is the classical online speed scaling problem, which was recently studied in the -aggnnnee setting by Bamas et al.
DPM. The equivalence between 2-state DPM and ski rental is mentioned in 39 Therefore the well-known 2-competitive deterministic and an (e -iee-ii 1) co-ompeeiieive randomized algorithm [0] for the classical ski rental problem carry over to 2-state DPM, and these bounds are known to be tight.
Irani al. [28] present an extension of the 2-competitive algorithm for two-state DPM to multi-state DPM that also achieves a competitive ratio of 2. Furthermore they give an e/(e - c)-ooppetitive algorithm for the case that the lengths of the idle periods come from fixed probability distribution.
Lotker et al. [36 consider what they call multi-slope ski rental which is equivalent to the DPM problem. Among other results, they show how to reduce (k + 1)-slope ski rental instance to k classical ski rental instances. The reduction from DPM to ski rental presented in this paper is similar, but more general in order to also be applicable in the presence of predictions with the introduced (p. (e.j)-oompetiiiveesss. They furthermore show how to compute the best possible randomized strategy for any instance of the problem.
There have been several previous approaches that try to predict the length of an idle interval (see, e.g.. [8] 28, and the survey of Benini et al. [3]. However, the proposed approaches to use these predictions are not robust against a potentially high prediction error.
Augustine et al. [00 investigate problem generalizing DPM where transition cost is paid for going to deeper sleep state rather than waking up and these transition costs may be non-additive (i.e., can be cheaper to skip states). Albers 2 studies the offline version of the problem with multiple, parallel devices and shows that it can be solved in polynomial time.
Irani et al. [29] introduced a 2-state problem where jobs that need to be processed have a release-time deadline and required processing time. This gives further flexibility the system to schedule the jobs and create periods of inactivity so as to maximize the energy-savings by transitioning to the sleep state. For the offline version, there is an exact polynomial-time algorithm due Baptiste et al. [12]. Recently, a 3-approximation algorithm for the multiprocessor-cant was developed (6).
Another related problem consists of deciding which components of data-center should be powered on or off in order to process the current load on the set of active components (see, e.g.. [3]. A similar problem, where jobs have individual processing times for each machine, was studied in B1 33) Helmbold et al. (23] considered the problem of spinning down the disk of a mobile computer when idle times are expected, which is another instance of DPM.
Several surveys cover DPM, see for example 13 27
2 New algorithm for ski rental
For p E [1, با we present a (p, compptitiie algorithm for (learning augmented) ski rental, proving Theorem [ The next lemma shows that it suffices to give such an algorithm for a =
Lemma 6. An algorithm A' that is (p. p) -competitive for instances of the ski rental problem with == implies a (p. ->coopetteivee algorithm A for arbitrary ar B O.
Proof idea. Simulate A' with prediction Sr. if buys time r', then A buys at time r &.'.
A key difference between proving p-competitiveness in the classical online setting and (p, 44- competitiveness in the searning-augment predictions, a greedy algorithm that buys with the highest affordable probability is optimal. This relies on the fact that the right-hand side of ( is a monotone and concave function of the skiing season length. In contrast, the right-hand side of (2) is neither monotone (if r > 1) nor concave (regardless of r), which complicates the description and especially the analysis of our algorithm.
setting is the following. In the online setting without
2.1 Description of the algorithm
We next deseribe our randomized algorithm for instances with a = =B= 1, which can then be used to solve arbitrary ski rental instances using Lemma 6 Our algorithm is fully specified by the cumulative
5

---

1.0
Probability that the algorithm buys before that time
T=1.7
1-
r=1.4
Tw0.65
Case 1, 0.5856
r=0.5
Case 2, [0.5856, !]
Case 3,
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
Time
Figure 2: Our (p. μ1) competitive ski rental algorithm for p 1.1596 and μ u(ه = 0.3852.
The figure presents the cumulative distribution functions of the time buying for several prediction values Here
i.e., at time buying and renting has equal costs.
distribution function (CDF) F, the time when the algorithm buys skis. The algorithm then draws ape [0, IJ uniformly random and buys at the earliest time [0, oo) such that Ft p. The CDF Fr will depend on the given prediction T 2 0 as well as the fixed and μ., which can be chosen μ μ(p), see Equation
Definition of the CDF (see Figure any 0, we denote by P, the probability density of buying time that the probability that the algorithm buys by time x can be expressed as
denote by Po the probability of buying at time 0 and, for
(x)x) Po+ S[" p,dr.
For convenience, we also specify the probability P.. = (Po+ f p,dt) of never buying.
To define Po and Pr. we distinguish three cases depending on the value of the prediction Note that we always have & μ s
Case 1: # - -+
We choose
Po = T(p- 1))
P. = ppe-1 for E (b, 1]
Pw min 1 Po).
1-7
otherwise
where E [T, 1] is chosen such that Po P Lo pet dt 1, in order to have the sum of probabilities equal to 1. Note that Po 2 - μ. we have and = 0 for all > O.
Case 2: -- 1-p++1 1s μ and r S 1. We choose
(ut+p-2 l)e² pel-1
for / S for (b, 1] otherwise
Po = PT,
P.
P. min Po).
where [] is chosen maximal such that Pp Poo 10 (uT+p-p 4 1)e'dl di s 1, and [T. 1] chosen that Po P.s 1"" (μT + p- 1) di pe di in order have the sum of probabilities equal to 1. case = - recovering the classical online algorithm of Karlin et al. 330
e c we have μ == 0 and (μr p- μ I)e' = (p 1)e' = =pe-!
Case 3: r >> 1. If uT 2 1, we buy at time 0. Otherwise, we choose
(uT + p 1 e)
if T
Po = μT,
Pr =
Pas = Pa=p-u-(pT) -----11 1)e",
0
if > T

---

where T is the number closest to r I that satisfies
e"
p
(equivalently Poo 2 0)
(4)
p 1 4-11 e p 24
(equivalently P.. $ jt).
(5)
MT + +p- - 1-1
Thus, either 7 = -- if this choice satisfies both bounds, or 7 is at an endpoint of the feasible interval prescribed by and
2.2 Sketch of the analysis
Our algorithm is (p. ()) cooppetiivee if and only if for all x 2 O have
cost(x) == Po+ { (1 (1+1) p;dtt + J.a. x P,dt + x s min[x, p -
x/.
(6)
where (xst(x) denotes the expected cost of the algorithm in the at some time and / < x, we pay + otherwise we pay x. On the right hand side, min(x, 1} is the optimal cost and T
when ( = If we intend to buy
is the prediction error, assuming a = =
We first sketch the analysis for Case 2. and then discuss the differences in Case 1. These cases are relatively simple. Case is far more involved and we will only sketch the ideas.
Case 2: For the algorithm be well defined, we need to choose f such that a suitable E [T, 1]
exists. For μ = p(p), this is ensured by the inequality μ(p) I-p"- which implies existence of such b for any value of r. If In 2, then μ μ(p) is in fact the smallest possible, allowing only b r. For other values of r, suitable b exists also for smaller values of ju. We now show that 66 is satisfied.
In from the definition of μ(p),
Note that (6 is tight for to show that the derivative of the left-hand side with respect to x is at most the derivative of the right-hand side (where derivatives exist). For (0, \ {a, 1), we have
with both sides equal to μr. To obtain (6 for all x it suffices
d cost(()) = (1+x)px+ + S( Pidt xpx Poo Px S(
Pidt + Pos.
dx
For e (0, a) this yields
d
ccot((x) = Px +1 - (px Po) = 11 (uT + 4 1)e p-
dx
which is equal to the derivative of the right-hand because Px is O, and the derivative of the right-hand side 6 is p μ or p + μ. For E (b, 1),
hand side of 66 For E (a, b), d cost(x) is even smaller
d cos((x)= Pxx* J.a dx
pi Poo Px (p) px) P p P S p
which is equal to the derivative of the right-hand side of (6. Finally, for x we have dx cost(x) P $ μ and the derivative of the right-hand side also μr.
The reason we cannot define P, in the same way as in Case 2 is that Py would be negative for (i.e., the algorithm would try to sell skis that bought time O, which not allowed). We therefore choose Po such that (6) is tight for x = r if we do not buy in the interval (0, r]. The remainder of the proof of (6) is similar Case 2. For μ μ(p), the existence of b e [r. follows from the inequality μ 2 p(1 TT in the definition of u(p). Note that such is the smallest possible for
Case 1:
The first step in the analysis of Case is to derive an inequality involving p. μ. T and T that is equivalent to the algorithm being (p. co-motttteeee Denoting by (p) the minimal μ satisfying this inequality, it suffices to show that (p) S μ(p) for all > 1. The difficulty that no closed-form expression for μr
Case 3:
(p) exists. However, have a local maximum only T = T 1, and therefore sup.> # (p) is achieved either for - or when T r 1. This allows that μ = (() satisfies the remaining inequality (with tightness occurring for S O and T = 7' 1).
still able to show that 7 H, (p) can
eliminate from the aforementioned inequality, and we can show
A complete proof of Theorem I is in the full version of the paper in the supplementary material.
7

---

3 Reduction from DPM to ski rental
We now give reduction from DPM to ski rental in the -uggeette setting (Lemma B) provided that the ski rental algorithm satisfies the following monotonicity property: We say that ski rental algorithm for rental cost a = I and buying cost B I monotone if its CDF F, for the buying time when given prediction satisfies
(+(1) S (t)(1)
for all f 2 0 and T <
Intuitively, this property is very natural: The longer the predicted duration of skiing, the greater should be our probability of buying. Indeed, our algorithm satisfies this property:
Lemma 7. For p(p). the (u.p))-ompeting ski rental algorithm from Section 2 is monotone, i.e, its CDF Fr when given prediction satisfies (1) (1) for all 2 0 and r <
For many T one could actually achieve a better (p) < μ()). However, somewhat surprisingly the optimal such algorithm would not be monotone. The monotonicity of our algorithm therefore crucially relies on our specific description (in particular the choice of a and b), which only aims for (u(p))-cometittveenee with μ(()) sup, (p()).
Combining Theorem I Lemma 3 and Lemmal we get:
Corollary 8. For every E [1, [1 there is a (p. -oooppiicooeeeiiiive algorithm for DPM.
To prove Lemma 3 it suffices to describe a (p, μ1) -c-omeettieive algorithm for the special case of DPM with single idle period: Running such an algorithm for each individual period yields (p. competiiive algorithm for DPM with any number of idle periods, since we can simply sum inequality ( over all periods obtain the corresponding inequality for the entire instance.
Consider now single idle period of length E for DPM. We first recall some observations of Irani et al. that the optimal offline algorithm would transition to some state j only once at the beginning of the period and remain there throughout the period, paying cost aj{+ + By. Thus, state j preferred over state j - I and only if a- ßj-1 > B1-B,_1
28 about the optimal offline algorithm: It is easy
a,l + Bj. or equivalently l > 1j == ay-1-a;' We may assume without loss of generality that 1x: Indeed, suppose fj+1 S Ij. then state j redundant because whenever j is preferred over j - 1, then j + 1 is preferred over j. Defining to == O and [2+1 == 400, we get partition +00) = U/ i Jj. where 1 = [1).))+1) We can then express the cost of the offline optimum as OPT c Byr, with j such that E ly-.
In the online setting, we of course do not know C. The idea of our algorithm (similar 33) is to simulate k ski rental algorithms Ai.... An in parallel, where the task of A, is to decide whether it is time to transition from the state j - rental with rental cost - 2 and buying cost Bj- ßj-1- Let Fr be the CDF of the buying time of a monotone ski rental algorithm (for a = B = 1) when given prediction т. Recalling our reduction from arbitrary and ß to the case β = 1 in Lemma 6 the CDF of R, is given by
j. For this, we choose A, to be an algorithm for ski
F()) Fr/t, (1/1g)
An outline of our algorithm is given in Algorithm ]
Algorithm 1: DPM with a single idle period
j=/...,... do
L Let Fl be as defined by 88) induced by monotone (p. μ) competiiive ski rental algorithm;
Choose p [0, 1] uniformly random;
At any time choose state m: F$() 2 p):
The proof that Algorithm| I is (p. co-mottttti relies on the fact that (1) is non-increasing in j:
()) = Fr/ty-1 (1/tz-1) 2 Fr/t, (t/tz-1) 2 Frit, (t/t,)=
where we used 1-- 1j in both inequalities, the first inequality uses monotonicity of the ski rental
algorithm and the second inequality uses that any CDF is non-decreasing. Thus, algorithm A, signals transitioning from state 1 j earlier than Ay-1 signals transitioning from state 2 to j 1.
8

---

Conversion to a prudent algorithm. It was shown in Lotker et al. [3 Theorem 4.2] that any DPM algorithm can be converted (online) into a so-called prudent one that assigns non-zero probability to at most two adjacent power states. The resulting algorithm pays the same expected wake-up cost but can only have smaller running cost than the original non-prudent algorithm. Hence, any implementation should apply this conversion, which we describe in the supplementary material.
4 Finding the best trade-off online
Our goal to design an algorithm whose performance almost matches that of Corollary ously for all p. proving Theorem 5
& simultane- It will be useful to view DPM Metrical Task System.
Metrical Task Systems (MTS). Metrical Task Systems (MTS), introduced by Borodin et al. 15 is a broad class of online problems containing many other problems as special cases. In MTS, we are given a metric space M of states. We start at a predefined initial state xo. At each time 1 1, 1.2, ......... we are presented with a cost function c₁ : M - R.. Then, we have to choose our new state and pay dist(x;-1.xx) (x²), where 11.t(x;,1.xxz) Xy) the distance between X,-1 1 and X, M. The objective is to minimize the overall cost incurred over time.
To formulate DPM as a Metrical Task System, choose states 0, 1,...,k k corresponding to the power states, with distances dis
[B: - -Byl. so that the cost of switching from the state 0 to and back is ßy. We choose as the initial state. We discretize time in the DPM instance using time steps of some small length 8 > 0. At each time step belonging some idle period, we issue cost function such that c(j) = day for each j = O.....k. k. At the end of each idle period, we issuc a cost function where c(0) 0 and c(j) +oo for = l.....k, which forces any algorithm move back to the active state.
We use the result of Blum and Burch 14 to combine multiple instances of our algorithm with different parameters p.
Theorem 9 (Blum and Burch (14). There is an algorithm which, given N online algorithms Aj.... .N for an MTS with diameter D and El < 1/2, achieves expected cost at most min(cost(A O(D/e) In..
(1+ (
Using this result, the straightforward proof of Theorem 5 is given in the supplementary material. r of size O(1/e2) so that the combination of our (p, ccompettveee algorithms for all p E P using the algorithm Blum and Burch 14] achieves expected cost most
Here, we just note that choose suitable set P c [1,
OPT +u(p))) + to Bx In 1 E2
(1 + E1) +22)
min pe(L,e(e--)
In the supplementary material, we also argue how using results on shifting/dynamicc regret [6 22 (24) can be used to achieve cost comparable not only to the algorithm with the best fixed p. but also the best strategy of switching between multiple values of p bounded number of times. This can be useful in scenarios where well-predictable parts of the input are interleaved with unpredictable or adversarial sequences.
5 Experiments
We ran an experimental evaluation of our algorithms compared to existing learning-augmentedd ski rental algorithms for the ski rental and DPM problems. Due to space limitations, only small part of the experimental results is presented here and others are deferred to the supplementary material, which also contains the source code and data D. Our results suggest that the performance of
algorithms indeed degrades smoothly when the error increases, providing solutions which are better, for medium errors, than naive algorithms trusting the predictions and online (predictionless) algorithms. In the experiments, our algorithm's 's performance degrades more smoothly compared to previous sermingg-ugmented algorithms when the prediction error increases. This is expected, since consistency- robussteess trade-offs of previous algorithms optimize the two extreme scenarios of perfect predictions and adversarially bad predictions, whereas the notion of (p. μ) -ompetiitivenss also captures the case of useful but imperfect predictions.

---

3,00
24
2.75
1am FTP
2.2
Our algorihhm
2.50
algorithm
Competitive ratio
Lem 3 Thm 9.4 PSK
AD]XR
Competitive
2:5
1om + Thmn 9 ADJKR
Lem + Thm 9 PSK
Lezs 3 Than FTP
2,00
Thes FTP
1.8
1.75
1.6
1.50
14-
125-
12-
1.00
cpptholl
tte Boulig
cxptioo
1th Bestig
0
Good predictions
Bad predictions
Noise parameter a of the synthotic predictor
(a) Synthetic dataset with durations from U|0, 8). Pre- dictions generated by adding Gaussian noise with standard deviation the exact durations.
(b) Real-world dataset
4 based smartphone I/O
traces. Predictions come from multiplicative weights
update algorithm [24 23
run on past idle periods.
Figure 3: Experimental performance of different algorithms for DPM with four power states.
Setup. We consider four power states, whose respective power consumptions (1, 0.100,
0. 12, 0.33, 1}, values corresponding to the active, idle, stand-by and sleep states of an IBM mobile hard-drive (28]. We convert algorithms initially designed for ski rental using Lemma 3 and convert the resulting algorithms to their prudent variants as discussed in Section 3 In addition to the classical e/(e - c)-ompetiiivve online ski rental algorithm, we consider the following algorithms: FTP, which blindly follows the prediction (i.e.. it either buys at time 0 or never); PSK, the randomized algorithm from |40] and ADJKR, the deterministic algorithm from 4. We use Theorem to let the algorithms automatically adjust their consistency parameters over time (p in the notation of our paper). For FTP, when we use Theorem P we combine it only with the classical randomized online algorithm. More details about the setup and additional scenarios are provided in supplementary material.
and wake-up costs are (0,0.12
Synthetic scenario. For the synthetic dataset, generate both the input data and predictions similarly to Purohit et al. [40]. Figure 3al shows the performance of the algorithms on dataset composed of 100 idle periods, whose durations are drawn independently and uniformly from [0, 8J. We feed the saaming-augmenter algorithms with synthetic predictions generated as follows: each prediction is equal to the exact request plus a random noise drawn from normal distribution of mean and standard deviation or (rounding any negative predictions to 0). We can observe that for low eπror the algorithms perform equally well. The figure shows that the algorithms PSK and ADJKR (combined with Lemma 3 and Theorem 9) essentially perform as well as the better of the two algorithms FTP and the classical online algorithm without predictions. In contrast, since our algorithm not only optimizes consistency and robustness, but also ( cooppetttiiseeessss our algorithm achieves significant improvement over previous algorithms in the regime of medium-sized errors and even when predictions are only very weakly correlated with the truth.
Real-world scenario. We created a dataset based on I/O traces from Nexus 5 smartphone [45] Predictions are generated based on past idle periods in way proposed by Helmbold et al. [23] in the context of spinning down disks of mobile computers. The predictor adapts the Share learning algorithm of Herbster and Warmuth [24], which is based on the multiplicative weights update method. Since is interesting to evaluate seemiing-uggmntee algorithms both the presence of good and bad predictions, we consider two variants of that predictor. The good variant uses hyperparameters proposed in (33]: the bad variant has the rate parameter of weight updates negated. Figure 3b presents the results of the experiment on two selected traces. In particular, on each dataset, either our algorithm performs better than all the others, or the nonrobust FTP is the best one and all robust Hamming-augment algorithms almost equally good.
10

---

Acknowledgments and Disclosure of Funding
Christian Coester is supported by the Israel Academy of Sciences and Humanities & Coun- cil for Higher Education Excellence Fellowship Program for International Postdoctoral Re- searchers. Research was carried out while he was at CWI in Amsterdam and supported by NWO VICI grant 639.023.812. Marek Eliáš was supported by NWO GROOT project number SEENWWGROOT.2019
(OPTIMAL) and research was carried out while he was at CWI in Amsterdam. Adam Polak supported by SNSF project Lattice Algorithms and Integer Programming (185030).
References
[1] S. Albers. Energy-efflcient algorithms. Commun. ACM, 53(5):86 96, 2010.
[2] S. Albers. On energy conservation in data centers. ACM Trans. Parallel Comput., 6(3):13:1-13::26 2019.
[3] S. Albers and Qucdenfeld. Optimal algorithms for right-sizing data centers. C. Scheideler and J. Fineman, editors, Proceedings of SPAA '88, pages 363-372. ACM, 2018.
[4] S. Angelopoulos, C. Dürr, S. Jin, S. Kamali, and M. Renault. Online Computation with Untrusted Advice. In Proceedings of ITCS'20, 20, volume 151, pages 52:1 52:15, 2020.
[5] Antoniadis, Coester, Eliás. A. Polak, B. Simon. Online metric algorithms with untrusted predictions, Proceedings of ICMI. 20, pages 345-355. PMIRR 2020.
[6] A. Antoniadis, N. Garg, G. Kumar, and N. Kumar. Parallel machine scheduling to minimize energy consumption. In Proceedings of SODA '20, pages 2758-2769, SIAM, 2020.
[7] A. Antoniadis, T. Gouleakis, P. Kleer, and P. Kolev. Secretary and online matching problems with machine learned advice. Proceedings of NeurlPS'20, 2020.
[8] A. Antoniadis, C. Coester, M. Fliáš, A. Polak, and B. Simon. Leaming-augmented dynamic power management with multiple states via new ski rental bounds. CoRR, abs/21 10. 13116, 2021. URI. http
wtwpivv.rrg/bbbb/eeeeeeeo 13116
A. Antoniadis, C. Coester, M. Elidš, A. Polak, and B. Simon. http://:tttubb..cmmmmmmmll.... 2021.
[10] Augustine, Irani, and C. Swamy, Optimal power-down strategies. SIAM Comput., 37(5):1499-11 2008.
[11] É. Bamas, A. Maggiori, L. Rohwedder, and O. Svensson. Learning augmented energy minimization via speed scaling. In Proceedings NeurlPS 2020.
[12] Baptiste, M. Chrobak, and C. Dür. Polynomial-ting algorithms minimum energy scheduling. ACM Trans. Algorithms, 8(3):26:1 26:29, 2012.
[13] L.. Benini, A. Bogliolo, and G. D. Micheli, A survey of design techniques for system-level dynamic power management. IEFF Trons. Very Large Scale Integr. Syst. 8(3):299-316, 2000.
[14] A. Blum and C. Burch. On-line learning and the metrical task system problem. Machine Learning, 39(1): 35-58, 2000.
[15] A. Borodin, N. Linial, and M. E, Saks. An optimal on-line algorithm for metrical task system. J. ACM, 39 (4):745-766 1992.
[16] N. Cesa Cesa-Bianchi, P. Gaillard, G. Lugosi, and G. Stoltz. A new look at shifting regret. CoRR, abs/1 202.3333, 2012. URL http:://axxii......//. org/ aba/ 0/////222233222
[17] N. Chen, G. Goel, and A. Wierman. Smoothed online convex optimization in high dimensions via online balanced descent. In Proceedings of COLT' 18, volume 75, pages 1574-1594, PMLR, 2018.
[18] E. Chung. L. Benini. A. Bogliolo, Lu, and G. D. Micheli. Dynamic power management for nonstationary service requests. IEEE Trans. Computers, 51(11):1345 1361, 2002.

---

[19] J. R. J. Dirk Blevins, Michael Loewe. White Paper, Inter Corporation: Designing Systems with- out Suspend Supply. https://www inteiitell.... com wwt.c////oootttee wwntentttttttccccccccoccooooeett /dattt///////// ht//mm/ww//tta httpa//aa.aaaaa////////a//////// publlic/uua/en/doocmeetttta white-
pdf 2008. [Online; accessed 14-May-
2021].
[20] P. Dütting. S. Lattanzi, R. Leme, and Vassilvitskii. Secretaries with advice. CoRR, abs/2011.06726, 2020.
[21] S. Gollapudi and D. Panigrahi. Online algorithms for rent-or-buy with expert advice. In Proceedings of ICML' 19, pages 2319-2327, 2019.
[22] E. Hall and Willett. Dynamical models and tracking regret in online convex programming. In Proceedings of ICML'13, '1, volume 28:1, pages 579-587. PMLR, 2013.
[23] D. P. Helmbold, D. D. Long, and B. Sherrod. A dynamic disk spin-down down technique for mobile computing In Proceedings of the 2nd ammual international conference on Mobile computing and networking, pages 130-142, 1996.
[24] M. Herbster and M. K. Warmuth. Tracking the best expert. In Proceedings of ICML'95, '95, pages 286-294. Morgan Kaufmann, 1995.
[25] Hewlett-Packarg Corporation, Intel Corporation, Microsoft Corporation, Phoenix Technologies Ltd.. and Toshiba Corporation. Advanced Configuration and Power Interface Specification (ACPI). https //uefi.org wwt.ooggg////....... acpa/ 2013. [Online; accessed 14-May-2021).
[26] S. Irani and A. R. Karlin. Online computation, In D. Hochbaum, editor, Approximation Algorithms for Hard Problems, page 521 -64. PWS Publishing Co., USA, 1996. ISBN 0534949681.
[27] S. Irani and K. Pruhs Algorithmic problems in power management. SIGACT News, 36(2):63-76,2000
[28] S. Trani, S. Shukla, and R. Gupta. Online strategies for dynamic power management in systems with multiple power-saving states. ACM Trans. Embed. Comput. Syst., 203)325-346, 2003.
[29] S. Irani, S. K. Shukla, and R. Gupta. Algorithms for power savings. ACM Trans. Algorithmss 3(4):41, 2007.
[30] A. R. Karlin, M. S. Manasse, L. A. McGeoch, and S. S. Owicki. Competitive randomized algorithms for nonuniform problems. Algorüthmica, 11(6):542-33 541-571, 1994.
[31] S. Khuller, Li, and B. Saha. Energy efficient scheduling via partial shutdown. In SODA, pages 1360-1372. SIAM, 2010.
[32] S. Lattanzi, Lavastida, B. Moselcy, and S. Vassilvitskii. Online scheduling via learned weights. In Proceedings of SODA '20, pages 1859-1877, 2020.
[33] Li and Khuller. Generalized machine activation problems. Proceedings of SODA'1L 11, pages 94. SIAM, 2011.
[34] S.-H. Lim, Sharma, C. Tak, and C. R. Das. dynamic energy management scheme for multi-tier data centers. In (IEEE ISPASS) IEEE International Symposium on Performance Analysis of Systems and Software, pages 257-266. IEEE, 2011.
[35] A. Lindermayr, N. Megow, and B. Simon. Double coverage with machine-learned advice. CoRR. abs/2103.01640, 2021. URL httthstt/t//attt www.vvoorg/aaaa Brrg/abs/2ie aba/ .01640
[36] Z. Lotker, B. Patt-Shamir, and D. Rawitz. Rent, lease, or buy: Randomized algorithms for multislope ski rental. SIAM J. Discret. Math, 26(2):718-27 736, 2012.
[37] T. Lykouris and S. Vassilvitskii Competitive caching with machine learned advice. In Proceedings of ICML'18, 18, pages 3302-3311,200
[38] M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions. In T. Roughgarden, editor, Beyond the Worst- Analysis of Algorithms, pages 646-662. Cambridge University Press, 2020.
[39] S. Phillips and J. Westbrook. On-line algorithms: Competitive analysis and beyond. In M. J. Atallah, editor, Algorithms and Theory of Computation Handbook, chapter 10. CRC Press, 1999.
[40] M. Purohit, Z. Svitkina, and R. Kumar. Improving online algorithms via ML predictions. In Proceedings of NeurlPS 18, pages 9684 9693,9993,,4 2018
12

---

[41] M. Rareshide.
Power in the data
center and its cost across the U.S.
httpa: tta-.ortt--rros------umlaalaaass 2017. [Online, acessed 23-May-20211
www/coo///////o http////oooe-ii-theee -eee----------tt-------------- and-
[42] D. Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of SODA '20, pages 1834-1845, 2020.
[43] A. Wei. Better and simpler leaming-augmmntted online caching. In Proceedings APPROX/RANDOM volume 176 LIPles, pages 60:1 60:17, 2020.
[44] A. Wei and F. Zhang. Optimal tobustness-consistenn trade-off's for learning- -uggmented online algorithms. In Proceedings of NeurlPS'20, 2020.
[45] D. Zhou, W. Pan, W. Wang, and T. Xie. 1/O characteristics of smartphone applications and their implications eMMC design. 2015 IEEE International Symposium on Workload Characterization, pages 21. IEEE Computer Society, 2015. doi: 10.1109/55...2015.88.
13


Reviews:
[{"review_id": "uc3mww-0Cna", "reviewer": "Reviewer_53BA", "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.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThis 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.  \n\nBecause 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.  \n\n[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.]", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\n", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "uL-fwxcifA", "reviewer": "Reviewer_SQBd", "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThis 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. \n\nThere 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.\n\nA minor correction:\n\nPage 5, line 182, should be A’.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Nil.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "pCEzngmbrET", "reviewer": "Reviewer_da7H", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and easy to follow.\n\nThe motivation for this work was power management, so experiments that show how this algorithm performs in that real scenario would make the paper stronger.\n\nWhat 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.\n\nThe 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?\n\nThe paper ends abruptly in the Experiments section.  Some concluding remarks on the results from the experiments are missing.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Y-eRjY_KU4", "reviewer": "Reviewer_Bp21", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)