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)))-copptitivy 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 11 μ 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 Pao 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, ccompeitveee 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-n)
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--uumenter 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 (a.s)))p)ppeeeeeeeeeeeee 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////oooteteeeeeeee wwntentttttttccccccccoccooooeett /dattt///////// ht//mm/ww//tta httpa//a/.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. Algorithms, 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 571-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 httthhtt/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///o http////oooe-ii-theee -eeer---------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-augmentted 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": "b-86kN1QfhR", "reviewer": "Reviewer_LdW3", "summary": "This paper is motivated by the challenge of dynamic power management in environments such as data centers. Computational devices like CPUs can transition to a sleep mode, for the purpose of preserving power. However, \"waking up\" entails consuming power, and so there is a tradeoff between entering a power-saving mode and avoiding future power spendings. The authors observe that this problem is reminiscent of the classical ski-rental problems and present a reduction from the former to the latter. This reduction enables borrowing deterministic and randomized algorithms for the ski-rental problem and applying them to this context. In addition, this enables using learning-augmented algorithms for ski-rental for dynamic power management (by predicting the duration of time in which the device is idle). Some experiments are presented.", "questions": "", "limitations": "", "rating": 5, "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": "Thank you for submitting to NeurIPS.\n\nI enjoyed reading the paper. The results are easy to parse and the proof techniques are clearly presented.\n\nThe main weakness of the paper, in my view, is that the relation to dynamic power management in environments such as data centers is quite vague. This relation is highlighted in the first few paragraphs of the Introduction but is never revisited afterwards. The specific characteristics of different power-saving mode, the patterns of idle time periods and the extent to which these can be predicted in data centers, etc., are never discussed. Since dynamic power management is supposedly the \"killer app\" for the presented algorithms, I think that these issues should be discussed.\n\nThis also relates to the presented experiments. The evaluation framework is very limited and is quite detached from the motivating example. For instance, the drawing requests uniformly at random and considering predictions that are random perturbations of the actual labels seems overly simple. I realize that this was done in [35], too, but there the key goal was illustrating the usefulness of predictions for online algorithm, as opposed to tackling a specific problem, as is done here.\n\nIn light of the above, this paper should, in my view, be evaluated as a theoretical paper about the ski-rental problem. As such, I'm not sure that the results are sufficiently significant.\n\nFollowing the authors' response:\n\nThank you for the detailed answer. I still have an issue with the positioning of this paper. I'm adjusting my score to 5.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not think that the paper potentially has negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "SJrmtQJEPPF", "reviewer": "Reviewer_cGaH", "summary": "This paper considers the problem of managing sleep states in dynamic power management in the framework of learning-augmented algorithms. This is a ski rental type problem but with multiple states, where idle periods of unknown lengths appear over time and the algorithm needs to decide which sleep state to transition to, where the deeper a sleep state it, the better it is for energy efficiency but the more expensive it is to bring it back to the awake state. The paper focuses on what it calls $(\\rho, \\mu)$-competitiveness, where alg $ \\le \\rho$ opt + $\\mu \\eta$ where $\\eta$ is the (scaled) $\\ell_1$ error in the predictions of the lengths of the idle periods. The goal is to optimize the tradeoff between $\\rho$ and $\\mu$. The optimal tradeoff is obtained by using a two-stage process: (a) show the the multi-state problem is equivalent to the 2-state problem, i.e., ski rental, provided the ski rental algorithm being used satisfies a technical monotonicity property, and (b) giving a monotone ski rental algorithm that optimizes the tradeoff between $\\rho$ and $\\mu$. This also gives a new result for the dynamic power management problem without predictions, by using the $e/(e-1)$ randomized ski rental algorithm and the above reduction. Finally, it is empirically validated through numerical experiments on synthetic datasets that the quality of the solution degrades smoothly with increasing prediction error.", "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": "This is a credible and interesting paper. Neither of the two steps -- the ski rental algorithm or the reduction from multi state DPM to 2-state DPM, i.e., ski rental -- is surprising, but each step requires some amount of careful technical work. For instance, in the second case, the idea is to set up the choice of transitioning from a state to its next state as a ski rental decision, and run these ski rental instances in parallel to obtain the overall DPM solution. Similarly, in the ski rental algorithm, the prediction has to be incorporated into the standard randomized algorithm for ski rental that chooses the buying threshold from a distribution with invariant competitive ratio. Overall, this paper adds interesting new ideas to the class of rent or buy problems that have been extensively studied in the learning-augmented setting.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does not discuss limitations explicitly. It would be beneficial to add this to the paper.\n\nI do not see any potential negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "None that I can think of.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "QvehUkTcTtq", "reviewer": "Reviewer_8AFS", "summary": "The paper considers a variant of the dynamic power management problem (DPM) with a learning augmented scenario. They prove an optimal competitive ratio with a matching lower bound. The key technique is a novel reduction method from DPM to the classical ski-rental problem. The authors also give some extensions of the main result and show experimental results using artificial data, which validates the theoretical results.\n\n", "questions": "", "limitations": "", "rating": 6, "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": "Comments:\nThe topic of the paper is about online algorithms and techniques shown are purely based on the literature. The proofs and techniques are solid and non-trivial but seem to follow rather standard techniques of the literature. The strength of the paper is showing the optimality of the prosed method. \n\nCommunication between the online algorithm and machine learning communities might be fruitful in the long run, but currently, the discipline in the paper is purely from the online algorithm literature and I am not sure how this paper stimulates the related areas of machine learning.\n\n\nThere is a related paper on an application of online learning for tracking experts to the “disk-spin down” problem: https://doi.org/10.1023/A:1019129116852  This problem could be an instance of DPM. \n\nThe writing is good in general, but it might be helpful for machine learning readers if the paper summarizes the proposed algorithm using, say, the algorithmic description.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "2fMNOk1GMAN", "reviewer": "Reviewer_JJ9s", "summary": "This paper provides an analysis of the learning-augmented dynamic power management (DPM) problem via a new randomized algorithm to the learning-augmented ski rental problem. These problems are examined through the lens of consistency and dependence on prediction error. The theoretical results are demonstrated by first detailing the new ski rental algorithm, and then reducing DPM to the ski rental problem. Finally, there are numerical results for comparison between several algorithms. ", "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": "Originality: This work analyzes the consistency vs. prediction error dependence tradeoff, which is modestly different from the previous analysis of consistency vs. robustness tradeoffs. In particular, [35] also gives competitive ratio as a function of error/OPT. It is not entirely clear why the robustness metric is skipped over in this work. So, the authors are encouraged to motivate this new analysis concretely. The proposed ski rental algorithm is fundamentally original, as it is specified by a CDF. This is also the first work that applies the learning-augmented setting to DPM. \n\nQuality: The submission is technically sound.\n\nClarity: The submission is overall well organized and written. My main concern is with the presentation of Theorem 5. It is unclear what extended result this provides beyond Theorem 3 by \"covering all \\rho simultaneously\", as it was introduced.\n\nSignificance: The experimental results demonstrate that the new algorithm achieves improved performance compared to previous ski rental algorithms in the DPM setting. However, the theoretical results are missing some comparisons against the robustness and consistency of Pareto-optimal randomized ski rental algorithms [35]. Also, the broader applicability of this new approach beyond ski-rental and its variants is not clear. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper was borderline. The reviewers appreciated the contributions of this paper to the online algorithms literature, but some reviewers were skeptical about the learning aspect (fit for neurips vs theory conferences) and the application to power management. After discussions, I believe that papers in the area of algorithms with ML predictions are a good fit for neurips (in addition, there have been multiple such papers recently accepted to neurips and icml) and am in favor of acceptance.
Decision: Accept (Poster)