Learning Predictions for Algorithms with Predictions
Authors: Mikhail Khodak
Nina Balcan
Ameet Talwalkar
Sergei Vassilvitskii
Venue: NeurIPS 2022 Accept (2022)
Keywords: algorithms with predictions
learning-augmented algorithms
online learning
combinatorial optimization
meta-learning

Abstract: A burgeoning paradigm in algorithm design is the field of algorithms with predictions, in which algorithms can take advantage of a possibly-imperfect prediction of some aspect of the problem. While much work has focused on using predictions to improve competitive ratios, running times, or other performance measures, less effort has been devoted to the question of how to obtain the predictions themselves, especially in the critical online setting. We introduce a general design approach for algorithms that learn predictors: (1) identify a functional dependence of the performance measure on the prediction quality and (2) apply techniques from online learning to learn predictors, tune robustness-consistency trade-offs, and bound the sample complexity. We demonstrate the effectiveness of our approach by applying it to bipartite matching, ski-rental, page migration, and job scheduling. In several settings we improve upon multiple existing results while utilizing a much simpler analysis, while in the others we provide the first learning-theoretic guarantees.

Learning Predictions for Algorithms with Predictions
Mikhail Khodak Carnegie Mellon University kchodakccmu. edu
Maria-Florina Balcan
Carnegie Mellon University ninamf @cs. cmu. edu
Ameet Talwalkar Carnegie Mellon University edu
Sergei Vassilvitskii
Google Research New York sergeivdgoogle.coom com
Abstract
A burgeoning paradigm in algorithm design is the field of algorithms with predic- tions, in which algorithms can take advantage of a possibly-imperfeer prediction of some aspect of the problem. While much work has focused on using predictions to improve competitive ratios, running times, or other performance measures, less effort has been devoted to the question of how to obtain the predictions themselves, especially in the critical online setting. We introduce a general design approach for algorithms that learn predictors: (I) identify functional dependence of the per- formance measure on the prediction quality and (2) apply techniques from online trade-offs, and bound the
learning to learn predictors, tune bobustness-consisteeee sample complexity. We demonstrate the effectiveness of our approach by applying it to bipartite matching. ski-rental, page migration, and job scheduling. In several settings we improve upon multiple existing results while utilizing a much simpler analysis, while in the others provide the first learning- thheoretic guarantees.
Introduction
Algorithms with predictions, subfield of reeyond-worst-oe analysis of algorithms [36], aims to de- sign methods that make use of machine-learned predictions in order to reduce runtime, error, some other performance cost. Mathematically, for some prediction x, algorithms in this field are designed such that their cost (x) on an instance / is upper-bounded by some measure (x(x) of the quality of the prediction on that instance. The canonical example here is that the cost of binary search on sorted array of size can be improved from (log n)) to S (x) 2 log 77: (x). where ()xx) is the distance between the true location of a query t in the array and the location predicted by the predictor x [36]. In recent years, algorithms whose cost depends on the quality of possibly imperfect predictions have been developed for numerous important problems, including caching [41, 24, 34], scheduling [30, 43], ski-rental [29, 1, 15], bipartite matching [16], page migration [22], and many more [10. 17, 36).
While there has been significant effort to develop algorithms that use earned predictions, until very recently [13, 33] there has been less focus on actually learning predict. For example, of the works listed only two on ski-rental [1, 15] and one other [16] show sample complexity guarantees, and none consider the important online learning setting, which problem instances may not come from fixed distribution. This is in contrast to the related area of data-driven algorithm design [19, 3], which has established techniques such as dispersion [6] and others [8. 11] for deriving learning- theoretic guaran- tees, leading to end-to-end results encompassing both learning and computation. It is also despite the fact that, as we see in this work, learning even simple predictors is in many cases non- non-trivial problem.
We bridge this gap and provide framework for obtaining leaming-theorreie theoretic guarantees for algorithms with predictions. In addition improving sample complexity bounds, we show how to learn the parameters of interest in an setting with low overall regret. We accomplish this using a two-
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Settings we apply our framework to, new learning algorithms derive, and their regret.
Prooiem
Algorichm with prediction
Feedback
Upper bound (losses)
Leaming algo.
Regret
Min, weight hipuriite matching (3)*.1
Hungarian mathod initizliizd by doal R
Opt. dual (e)
O [[| x (e)lls)
Proj. online gradient
(n+T)
Online
Lary offline oprimal For prodictions "P[))
Requett
1420 Ap
Exponeniited gradient x
(nIT)
migration
Online schedulligg (5)*
Conrected optimal for predicted logit& & E R
Opt. weights
w E A
o O1l log w|l
KT-OCO
Euclideun
( (mm log(mT)
Non-slairayyant job scheduling (6)
Preferencia round robin with trade parameser X
Prodiction
min
1+2n/n (
Expomential
< ((TTlgTT)
quality
forecastor
Ski-rental integer days [M] (6)
Buy price S in, A maae-
Number of ski-days
Expanemiined
(NyTlog(NVT)
off weest-case appros.
1-11+1/01-BA
gradient
Ski-renial with
Buy after days, À trade-
Number
min (. (0m2)la2
Exponeniial
((TT)o
fiddispessed
off with weest-ease appros.
ski-days
forecester
4N2y1-B)
For these problems
provide guarantess statistiaal (ii.)) setting learning linesr prodicters take instince festuros their inputs. We also obtain results for is extensions to minimuum-weigh weight b-masching and other graph algorittiss with predictions in Appendices B and D.
We also provide new guarantees for the problem loaming job permutations in the non chirroyant setting in Appendix. E.
step approach inspired by recent work on theoretical meta-learning [25], which has been used to derive numerous multi -tak learning results by optimizing regret-upper-boure bounds that encode the task- similarity [31, 32, 9, 26]. As evidenced by our results in Table 1, we believe the following two-step framework below holds similar potential for obtaining guarantees for algorithms with predictions:
1. For a given algorithm, derive convenient-tor to-ottimmzze upper bound (x) on the cost (x) that depends on both the prediction x and information specific to instance / returned once the algorithm terminates, e-g. the optimum in combinatorial optimization. We find that in many cases such bounds already exist, and the quality of the prediction can be measured by a distance from some ground truth obtained from the output, a quantity that is usually convex and thus learnable. Apply online learning to obtain both regret guarantees against adversarial sequences and sample complexity bounds for i.i.d. instances. We provide pseudo-code for generic setup in Algorithm 1.
Table I summarizes instantiations of our framework on multiple problems. Our approach is designed to be simple-to-xxecute, leaving much of the difficulty to what the field is already good at: designing curriiin-ualltyydeeeeeeee
upper bounds on their costs. Once the latter is accomplished, our framework leverages groblem-speciiee structure to design a customized learning algorithm for each problem, leading to strong regret and sample complexity guarantees. In particular, in multiple settings we improve upon existing results in either sample complexity or generality, and in all cases we are the first to show regret guarantees in the online setting. This demonstrates the usefulness of and need for such a theoretical framework for studying these problems.
algorithms and proving
We summarize the diverse set of contributions enabled by our theoretical framework below:
1. Bipartite matching: Our starting example builds upon the work on minimum-weight bipartite matching using the Hungarian algorithm by Dinitz et al. [16]. We show how our framework leads directly to both the first regret guarantees in the online setting and new sample complexity bounds that improve over the previous approach by a factor linear in the number of nodes. In the Appendix we show similar strong improvements for b-matching and other graph algorithms.
2. Page migration: We next study a more challenging application, online page migration, and show how we can adapt the algorithmic guarantee of Indyk et al. [22] into a learnable upper bound for which we can again provide both adversarial and statistical guarantees.
3. Learning linear maps with instance-featur inputs: Rather than assume the existence of a strong tixed prediction, it is often more natural to assume each instance comes with features that can be input into a predictor such as a linear map. Our approach yields the first guarantees for learning linear predictors for algorithms with predictions, which obtain for the two problem settings above and also for online job scheduling using makespan minimization [30].
4. Tuning mownsteess-cossstteen incorporate parameterized trade-offss between trusting the prediction or falling back on worst-case approximation. This suggests the usefulness of tuning the trade-off parameter, which we instantiate on a simple job scheduling problem with a fixed predictor. Then we turn to the more challenging problem of simultaneously tuning the trade-off and learning predictions, which we achieve on two variants of the ski-rental problem. For the discrete case we give the only learning beaming-theooretic theoretic guaran- tee, while for the continuous case our bound uses dispersion assumption [6] that, in the i.i.d. set- ting, is a strictly weaker assumption than the log-coneave requirement of Diakonikolas et al. [15].
trade-off's: Many bounds for online algorithms with predictions
2

---

2
Related work
Algorithms with predictions is a type of beyond-worss worrstccse analysis of algorithms [42]; along with areas like smooth analysis [45] and data-driven algorithm design [3], it takes advantage of the fact that real-world instances are not worst-case. Inspired by success in applications such as learned indices [27]. there has been great deal of theoretical study focusing on algorithms whose guarantees depend on the quality of a given predictor (c.f. the Mitzenmacher and Vassilvitskii [36] survey). The actual learning of this predictor has been studied less [1, 15, 16] and rarely in the online setting; we aim to change this with our study. Some papers improve online learning itself using predictions [39, 23, 14], but they also assume known predictors or only learn over small set of policies, and their goal is minimizing regret not computation. In-general, we focus on showing how algorithms with predictions can make use of online learning rather than on new methods for the latter. Several works [4, 40, 2] use learning while advising an algorithm, in-effect taking a learning-inspiree approach to better make use of a prediction within an algorithm, whereas we focus on learning the prediction outside of the target algorithm. Our paper presents the first general framework for efficiently learning useful predictors.
Data-driven algorithm design is related area that has seen more learning-theoretic effort [19, 6, 3]. At high-level, it often studies tuning parameters such as the gradient descent step-size [19] or settings of branch and bound [5], whereas the predictors in algorithms with predictions guess the sequence in an online algorithm [22] or the actual outcome of the computation [16]. The distinction can be viewed as terminological, since prediction can be viewed as a parameter, but it can mean that in our settings we have full information about the loss function since it is typically some discrepancy between the full sequence or computational outcome and the prediction. In contrast, in data-driven algorithm design getting the cost of each parameter often requires additional computation, leading to (bandit settings [7]. A more salient difference is that data-driven algorithm design guarantees compete with the parameter that minimizes average cost but do not always quantify the improvement attainable via learning: in algorithms with predictions we do generally quantify this improvement with an upper bound on the cost that depends on the prediction quality, but we usually only compete with the parameter that is optimal for prediction quality, which is not always cost-optimal. We do adapt data-driven algorithm design tools like dispersion [6] for algorithms with predictions.
Our two-step approach to providing guarantees for algorithms with predictions is inspired by the Average Regret-Upper-Bound Analysis (ARUBA) framework [25] for studying meta-learning [18]. Instead of instances they have tasks with different data-points, and the upper bounds are on learning- theoretic quantities such as regret rather than computational costs such as runtime. Mathematically. ARUBA takes advantage of similar structure in the sepet-uppp--buddee that we find in algorithms with predictions, namely that the upper bounds encode some measure of the quality of the prediction (in their case an initialization for gradient descent) via a comparison to the ground-truth (in their case the optimal parameter). However, whereas in ARUBA the need to know this optimal parameter after seeing a task is a weakness that does not hold in practice, in algorithms with predictions the corresponding quantity the feedback listed in Table i-is generally known after seeing the instance.
3 Framework overview and application to bipartite matching
In this section we outline the theoretical framework for designing algorithms and proving guarantees for learned predictors. As an illustrative example we will use the Hungarian algorithm for bipartite matching, for which Dinitz et al. [16] demonstrated an instance-dependent upper bound the running time using a learned dual vector. Along the way, we will show an improvement to their sample complexity bound together with the first online results for this setting.
Bipartite matching: For bipartite graph on n nodes and m edges, min-weight perfect matching (MWPM) asks for the perfect matching with the least weight according to edge-costs Zm A common approach here is the Hungarian algorithm, a convex optimization- based approach for which Dinitz et al. [16] showed a runtime bound of Ô (m / T min f||x - x" (c) vnt). where x e 2n initializes the duals in a primal-dual algorithm and x* (c) E 2d is dual of the optimal solution; note that the latter is obtained for free after running the Hungarian method.
The first step of our approach is to find a suitable function (x) of the prediction x that (a) upper bounds the target algorithm's 's cost (x), (b) can be constructed completely once the algorithm terminates, and (c) can be efficiently optimized. These qualities allow learning the predictor in the second step. The requirements are similar to those of ARUBA for showing results for meta-lcarning [25], although there the quantity being upper-bounded was regret, not algorithmic cost.
Step 1- Upper bound:
3

---

Algorithm I: Generic application of an online learn- ing algorithm over X learn a predictor for method Algorithm WithPrediction that takes ad- vice from X' and returns upper bounds Ug on its cost. The goal of Online.lggorihmm is low regret over the sequence Ug, so that on- on-average C₁ is upper bounded by the smallest possible average of U,, to some error decreasing in T. For specifie instanti- ations of algorithms and feedback see Table 1.
30
50000,,,, x0-200
linar bound
ni1000, vD-100
incer bound
Lound on an sosoecttttiee
bound
yo-20
initialize X1 E X for OnlineAlgorithnn for instance (. == 1,.... T do
mix espected number of mistabes in any Interva of belggth
obtain instance I,
Figure Bounds (c.f. Lemma 4.1) for three different n. and 7D on the expected largest number of mistakes in any 4D- interval as a function of the maximum expected number (p) in any interval.
run A Algorithm WithPPeeiction x+)
suffer cost (x,x, S (x,)
get feedback to construct upper bound U2
Xx+1 f- OnlineAlgorithm (())))m((())))))))
Many guarantees for algorithms with predictions are already amenable to being optimized, although we will see that they can require some massaging in order to be useful. In many cases the guarnntee is a distance metric between the prediction x and some instance-dependent perfect prediction x", which is convex and thus straightforward to learn. This is roughly true of our bipartite matching example, although taking the minimum of a constant and the distance |x - x" (c)lla between the predicted and actual duals makes the problem convcx.vex. However, we can further upper bound their result by O /tn//l/ x* (c)ll1) note that Dinitz et al. [16] also optimize this quantity, not the tighter upper bound with the minimum. While this might seem to be enough for step one, Dinitz et al. [16] also require the prediction to be integral, which is difficult combine with standard online procedures. In order to get around this issue, we show that rounding any nonnegative real vector to the closest integer vector incurs only a constant multiplicative loss in terms of the ε didisttnce.
Claim 3.1. Given any vectors x E nn and E IR", let y E " be the vector whose elements are those of y rounded to the nearest integer. Then ||x 5l1 I 2||x yll1.
Proof. Let S c. [n]] be the set of indices i E [n]] for which X 2 V(j]
Ty 1. For
i E [n]) we have [X|] -yal 2 1/2 2
[+ Yigl so it follows by the triangle inequality that
|xx -- 511
Σ b - -JAA Σ |x| 741
+ Ylal
xx
-ygl
iES
iES
[X||]
Y(g)
+ 2
S
2||x
yll
iES
#E[n](S
Combining this projection with the convex relaxation above and the result of Dinitz et al. [16] shows that for any predictor R" we have (up to affine transformation) convex upper bound Ux(x) ||x - x" (ct)]l on the runtime of the Hungarian method, as desired. We now move to step two.
Step 2- Online learning: Once one has an upper bound U, on the cost, the second component of our approach is to apply standard online learning algorithms and results to these upper bounds to obtain guarantees for learning predictions. In online learning, on each of a sequence of rounds = 1,..., T we predict x, E and suffer (x+) for some adversarially chosen loss function U, : X + that we then observe; the goal is to use this information to minimize regret Σt= (x(x: minge Ux(x). with the usual requirement being that it is sublinear in T and thus decreasing on average over time. For bipartite matching, we can just apply regular projected online (sub)gradient descent (OGD) to losses (x) = ||x x" (c.))l i.e the update rule X +- arg min a (X), x) + 1 ||x|| for appropriate step-size a > 0; as shown in Theorem 3.1, this yields sublinear regret via a textbook result. The simplicity here the point: by relegating as much of the difficulty as we can to obtaining an easy- to-optimize upper bound in step one, we make the actual learning-theoreti component easy. However, as we show the following sections, it is not always easy to obtain suitable upper bound, nor it always obvious what online learning algorithm apply, e.g. if the upper bounds non-convex.

---

Our use of online learning is motivated by three factors: (1) doing well on non-i..d. instances is impor- tant in practical applications, e.g. in job scheduling where resource demand changes over time; (2) its extensive suite of algorithms lets us use different methods to tailor the approach to specific settings and obtain better bounds, as we exemplify via our use of exponentiated gradient over the simplex geometry in Section 4 and KT-OCC over unbounded Euclidean space in Section 5; (3) the existence of classic moline-to-bated procedures for converting regret into sample complexity guarantees [12], i.c. bounds on the number of samples needed to obtain an e-suboptimal predictor w.p. 2 1 6. While online-to- batch conversion can be suboptimal [20], as we show in Theorems 3.1, B.2, and D.I its application
to various graph algorithms with predictions problems improves upon existing sample complexity results. For completeness, we formalize muline-to-butee conversion as Lemma A.1 in the Appendix.
We now show how to apply the second online learning step to bipartite matching by improving upon the result of Dinitz et al. [16] in Theorem 3.1; the improvement the entirely new regret bound against adversarial cost vectors and a O(n) lower sample complexity. Note how the proof needs only their existing algorithmic contribution, Claim 3.1, and some standard tools in online convex optimization.
Theorem 3.1. Suppose we have a fixed bipartite graph with n 2 3 vertices and m 2 1 edges.
For any cost vector с E 220 and any dual vector x E IR" there exists an algorithm MWPM that runs in time
Ô (m min {U(x), vnt) S Ô (m (x))
for Uxx) = ||x- x' (c)llI, where x" (c) the optimal dual vector associated with c.
2. There exists a poly-time algorithm s.t. for any ö, > O and distribution D over integer m-vectors with -x- -norm= < C it takes O
(( (Ca)² log :) samples from D and returns & s.I. w.p. 2 1 8:
BeNDll x" (c)ll2
min |0
BeeDlIx - -0*(xxx"())i xx(c)]l1 +E
3. Let Ci...., CT 20 be an adversarial sequence of m-vecoors with lorm S C. Then OGD with appropriate step-size has regret
T
Σ
X (c,)ll |xx x (ct)ll S Cni2T
max |X SC
Proof. The first result follows by combining Dinitz et al. [16, Theorem 13] with Claim 3.1. For the third result, let be the sequence generated by running OGD [46] with step size C/V2TT on the losses (x(x) = |x - x" (c:))lı over domain [-C, CJ" Since these losses are Vn--iisshhizz and the duals are Cv /n-boundded in Euclidean norm the regret guarantee follows from Shalev-Shwartz [44, Corol- lary 2.7]. For the second result, we apply standard online-to-batee conversion to the third result, i.e. we draw T' = Ω ((2((z)) (~=)² log } samples C₁ run OGD above on the resulting losses Ur, and set x
1 E x; to be the average of the resulting predictions x,. The result follows by Lemma A.1.
This concludes an overview of our two-step approach for obtaining learning guarantees for algorithms with predictions. To summarize, we propose to (1) obtain simple-to-optimzze upper bounds (x) on the cost of the target algorithm on instance as a function of prediction x and (2) optimize (x(x) using online learning. While conceptually simple, even in this illustrative example it already improves upon past work; in the sequel we demonstrate further results that this approach makes possible. Note that, like Dinitz et al. [16], we are also able to generalize Theorem 3.1 to b-matchings, which we do in Appendix B; another advantage of our approach is that it lets us prove online and statistical learning in the case where the demand vector b varies across instances rather than staying fixed as in Dinitz et al. [16]. Finally, in Appendix D we also improve upon the more recent learning-the theoretic tehming-teoorticc results of Chen et al. [13] for related graph algorithms with predictions problems.
4 Predicting requests for page migration
Equipped with our two-step approach for deriving guarantees for learning predictors, we investigate several more important problems in combinatorial optinization, starting with the page migration problem. Our results demonstrate that even for learning such simple predictors there are interesting technical challenges in deriving learnable upper bound. Nevertheless, once this accomplished the second step of our approach is again straightforward.
5

---

Page migration: Consider server that sees a sequence of requests sII),......pp from metric space (K, d) and at each timestep decides whether to change its state d[j] E K at cost Dd(a qja) for some D > 1; it then suffers a further cost d(a(j) $1.).. The online page migration (OPM) problem is then to minimize the cost to the server. Recently, Indyk et al. [22] studied setting where are given a sequence of predicted points 1[1], ... Six] E K to aid the page migration algorithm. They show that if there exists 7, q E (0,1) s.t. 7D E [n|] and for any E [nx] we have Σj=i E وي S gy then there exists an algorithm with competitive ratio (1 + 7) + (4)) w.r.t. to the offline optimal. This algorithm depends on but not q, so we study the setting where 7 is fixed.
Deriving an upper bound: As in the previous section, the predictions are discrete, so use our approach we must convert it into a continuous problem. As we have fixed 7, the competitive ratio is an affine function of the following upper bound on g:
14 H4gD-1 D-1
max Q(8, 8) 7D ie(m-aD+1]
Σ
1 [
We assume that the set of points KC finite with indexing k - I,..,, [C] and use this introduce our continuous relaxation, a natural randomized approach converting the problem of learning a prediction into n experts problems on |K] experts. For each j E [n]] we define a probability vector P(y] E 4 governing the categorical r.v. $b)) i.e. Pr[š
k] = Pl A k E K. Under these distributions the expected competitive ratio will be (1 + 71 + (p Q(s, s))) for the product distribution of the vectors Pj- Note that forcing each P, to be a one-hot vector recovers the original approach with no loss, optimizing Q(s, s) over p E Ax] would find predictor that fits the original result.
However, ((,, s) not convex in p. The simplest relaxation is replace the maximum by summation, but this leads worst-case bound of O (Tb) thus also the expected competitive
WW instead bound Egpp ((,, 8) and by function of the following maximum over expectations:
i4yD-1
i49D-1
(p( max iE(n->D+1]
Espp
Σ
max iE(n-gDD+]
Σ 1- (s),, j=i
where J. = = V E KC, i.. St)] encodes the location in XC of the jth request. As a maximum over n - 7D - 1 convex functions this objective is also convex. Note also that if U, (p) is zero- i.e. the probability vectors one-hot and perfect-then ((s,pQ((s))))) 2 q will also be zero. In fact, q is upper-bounded by a monotonically increasing function of U. (p) that is zero at the origin, but as this
function is concave and non-Lipschitz (c.f. Figure 1) we incur an additive O [log(n>D++1) loss to 70 obtain an online-learnable upper bound. This is formalized in the following result (proof in A.1). Lemma 4.1. There exist constants a < e,b < 2/e and a monotonically increasing function f [0, oo) + 10, oc) s.t. f(0) = and
E Q(5,s) [(U.(p)) yD
aU.(p) + blog(n 7D + 1)
<
7D
We now have an convex bound on the competitive ratio for the OPM algorithm of Indyk et al. [22]. For both this and bipartite matching we resorted to a relaxation of a discrete problem. However, whereas before we only incurred a multiplicative loss (c.f. Claim 3.1), here we have an additive loss that makes the bound meaningful only for DD >> log n. However, the method we propose optimizes (p), which bounds with no additive error via the function ff in Lemma 4.1, in-practice may expect it to help minimize g in all regimes. Note that the Linshhissssssssss near zero that prevents using f for formal regret guarantees comes from the poor tail behavior of Poisson-like random variables with small means, which we do not expect can be significantly improved.
Learning guarantees: Having established an upper bound, in Theorem 4.2 we again show how learning- theorrtic result follows from standard online learning. This time, instead of OGD we run exponentiated (sub)gradient (EG) [44], a classic method for learning from experts, on each of simplices to learn the probabilities Pbj V j [ns]. The multiplicative update x++1 & x, <e@eep((<o - (x.)) of EG is notable for yielding regret logarithmic in the size [KC of the simplices, which is important for large metric spaces. Note that as the relaxation is randomized, our algorithms
output dense probability vector; to obtain prediction for OPM we sample štp] P V E [n]].

---

Theorem 4.2. Let (K, d) be finite metric space.
1. For any request sequence and any set of probability vectors i there exists an algorithm for OPM with expected competitive ratio
log(n - - ) yD (1+ (1+0 Up(P) (1o
YD
There exits a poly-time algorithm s.t. for any o, > and distribution over request sequences
E KC it takes O ((22) (n² log |1c| + log
samples from D and returns P s.t. w.p. 2 1-
E EUDDU U.((U S min EUNDU,(P) + PE
3. Let $1,...,8T be adversarial sequence of request sequences. Then updating the distribution Prtj] over pK] at each timestep j E [mn] using EG with appropriate step-size has regret
T
max (p). - -U, Up) S >>Dn//T DEA JAS 1=1
Proof. The first result follows by combining Indyk al. [22, Theorem 1] with Lemma 4.1. For the third let p. be generated by running exponentiated gradient algorithms with step-size
log [K] 2y
losses Us. (P) over 4k-- Since these are DD-Lpschhtzz and the maximum entropy is log KK], the regret follows by [44, Theorem 2.15]. For the second result, apply standard online-to-bated conversion to the
((T)
2 (n² log |C] + log }
third, i.e. draw T Ω
samples s,, run EG on Us, (p) as above, and set p ΣT Pa to be the average of the resulting actions. The result follows by Lemma A.1.
As before, this result first shows how the quantity of interest- here the competitive ratio-ip is upper- bounded by affine function of some quality measure (p), for which we then provide regret and statistical guarantees using online learning. The difficulty deriving a suitable bound exemplifies the technical challenges that arise in learning predictors, and may also be encountered in other sequence prediction problems such as TCP [10]. Nevertheless, our approach does yield an online procedure that incurs only ( log additive error over Indyk et al. [22] in the case of a perfect predictor and, unlike their work, we provide an algorithm for learning the predictor itself. In Appendix C.2 we also show an auto-regressive extension which does not require learning distribution for each timestep [n]]
Learning linear predictors with instance-feature inputs
So far we have considered only fixed predictors, either optima-in hindsight in the online setting a population risk minimizers for i.i.d. data. Actual instances can vary significantly and so a fixed pre- dictor may not be very good, e.g. in the example of querying sorted array it means always returning the same index. In the online setting one can consider methods that adapt to dynamic comparators [46, upper bounds; however, these still need measures such as
23, 37], which are also applicable the comparator path-length to be small, which may be more reasonable in some cases but not all.
We instead study the setting where all instances come with instance-specific features, natural and practical assumption [27, 30] that encompasses numerical representations of the instance itself e.g. bits representing a query or graph- or other information such as weather or day of the week. These are passed to functions-ca, linear predictors, neural nets, or trees-whose parameters can be learned from data. We study linear predictors, which are often amenable to similar analyses as above since the composition of a convex and affine function is convex. For example, it is straightforward to extend the matching results to learning linear predictors of duals. OPM is more challenging because the outputs must lie in the simplex, which can be solved by learning rectangular stochastic matrices. Both sets of results shown in Appendix C. Notably, for page migration our guarantees cover the regressive setting where the server probabilities are determined by a fixed linear transform of past states.
Our main example will be online job scheduling via minimizing the fractional makespan [30], where we must assign each a sequence of variable-sized jobs one of m machines. Lattanzi et al. [30] pro- vide an algorithm that uses predictions w 1" of "oood" machine weights E 17 assign jobs
7

---

based on how well w corresponds to machine demand; the method has performance guarantee of Wid, (log min max; wiy m)). They also discuss learning linear and other predictors, but without guar- antees. We study linear prediction of the logarithm the machine weights, which makes the problem convex, and assume features lie the f-dimensional simplex. For simplicity we only consider learn- ing the linear transform from features to predictors and not the intercept, as the former subsumes the latter. For the online result, we use KT-OCO [38, Algorithm 1]. parameter-free subgradient method with update X;+1 + 1+ (g.. E Le=t ga for ga (U,(x,); it allows us to not assume any bound on the machine weights and thus to compete with the optimal linear predictor all of RR /
Theorem 5.1. Consider online restricted assignment with 2 machines [30, Section 2.1].
1. For predicted logits R there is an algorithm whose fractional makespan has competitive ratio
O(min [| logwll log m)) S OU)(x)
for U(x)= = log wlooo. where w E Rg0 are good machine weights [30, Section 31.
2. There exists poly-time algorithm s.t. for any ô,e
and distribution 'D over machine (weight, feature) pairs (w,f) Ry0 Ds s.t. log w|ooo S B the algorithm takes
O ((#) (ms
1 +lgg (m))) samples from and returns A E Bmxx s.t. w.p. 2 1
E(w,r)~DlAAF log w/ <
min (( Af log w/ +
|
Iulam SB
Let (W1, fi),.... (rr. fr) E Rgo D be an adversarial sequence of (weights, feature) pairs. Then for any A mxx KT-OCO has regret
Σ |Ach - wl ||Af; log wello (IAlFy/T 247 [|]3)
If we restrict to matrices with entries bounded by B then OGD with appropriate step-size has regret
max JA MIax SB IIA - log we - ||Af, log welloo B/2mmf
Proof. The first result follows by substituting max; exp(X(a)
wij] for in in Lattanzi et al. [30, Theorem 3.1] and upper bounding the maximum by the foc -norm. For the third, since U, is I-Lipschitz w.r.t. the Eu- clidean norm apply the guarantee for KT-OCO [38, Algorithm 1] using
1 and the subgradients of A log wt walloo as rewards [38, Corollary 5]. The result for B-bounded A follows by applying
OGD with step-size B
V
mf 2T
over ||A] max S B [44, Corollary 2.7]. Finally, the second result follows
by applying online-to-bated conversion to the latter result, i.e. draw T = Ω ((=)² (mf + log !
samples (We, ft), OGD the resulting losses A log w. above, and set Å + ト A, to the average of the resulting actions A, The result follows by Lemma A.I.
This guarantee is the first we are aware of for learning non-static predictors in the algorithms with predictions literature. demonstrates both how to extend fixed predictor results to learning linear predictors-nott that the former is recovered by having f, 1, V ('aand how to handle unbounded predictor domains. The ability to provide such guarantees another advantage of our approach.
Tuning robustaess-consiitenng trade-offs for scheduling and ski-rental
We turn to tuning ceassttess--oosisteen trade-offss, introduced in Lykouris and Vassilvitskii [34]. This trade-off captures the tension between following the predictions when they are good (consistency) and doing not much worse than the worst-case guarantee either case (robustness). In many cases, this trade-off can be made explicit, by parameter À E [0, 1]. The setting of À is crucial, yet previous work left the decision to the end-user. Here we show that it is often eminently learnable an online setting. We then demonstrate how to accomplish much harder task task-tuning À at the same time as learning to predict-on on two related but technically very different variants of the ski-rental problem. This meta-application highlights the applicability of our approach to non-convex upper bounds.

---

Robustness-consisten trade-offs: Most problems studied in online algorithms with predictions usually have existing worst-case guarantees on the competitive ratio, i.e. a constant y 2 on how much worse (multiplicatively) a learning-free algorithm does relative to the offline optimal cost OPT, on instance While the goal of algorithms with predictions is to use data to do better than this worst-case bound, an imperfect prediction may lead to much worse performance. As result, most guarantees strive to upper bound the cost of an algorithm with prediction x on an instance t as follows:
C₂ >) & min (f(A)u(xx) ((
Here Ue is some measure of the quality of x on instance À [0. 1] is parameter, f is a mono- tonically increasing function that ideally satisfies f(0) = 1, and gr is a monotonically decreasing function that ideally satisfies (1( = O.P,, very common structure is f(A) 1/(1 A) and (:(A) = T.T,, For example, consider job scheduling with predictions, a setting where we are given jobs and their predicted runtimes with total absolute error r) and must minimize the sum of their completion times when running on single server with pre-emption. Here Kumar et al. [29, Theorem 3.3] showed that preferential round-robin algorithm has competitive ratio at most 1+2n/2
min { 1-> 1-x . Thus if know the prediction is perfect we can set À 0 and obtain the optimal cost (consistency); on the other hand, if we know the prediction is poor we can set À = 1 and get the (tight) worst-case guarantee of two (robustness).
Of course in- in-practice we often do not know how good a prediction is on a specific instance t; we thus would like learn set X, i.e. to learn how trustworthy our prediction is. As first step, we can consider doing so when we are given a prediction for each instance and thus only need to optimize over A. For example, the just-discussed problem of job scheduling has competitive ratio upper-bounded by U+(A) min 142%//m XX I-X
2 for ni, and the number of jobs and the prediction quality, respectively,
on instance L. Assuming a bound B on the average error makes U, Lipschitz, so we can apply the exponentially weighted average forecaster [28, Algorithm 1], also known the exponential forecaster. This algorithm, whose action at each time t + 1 is to sample from the distribution with density P-+1()) x pi exp(-a etx U.).), has the following regret guarantee (proof in A.2):
Corollary 6.1. For the competitive ratio upper bounds Ue of the job scheduling problem with average prediction error n/ at most B the exponential forecaster with appropriate step-size has expected regret
T
T V
max AE
E
U.(A)) s 9B 1
logT
1=1
Thus standard learning method produces sequence A, that performs as well as the best À asymp- totically. We next consider the more difficult problem of simultaneously tuning À learning to predict.
Ski-rental: We instantiate this challenge on ski-rental, in which each task / is a ski season with an unknown number of days n, E Zz2; to ski each day, we must either buy skis at price b, or rent each day for the price of one. The optimal offline behavior is to buy iff b, ne, and the best algorithm has worst-case competitive ratio e/(e - 1). Kumar et al. [29] and Bamas et al. [10, Theorem 2] further derive algorithm with the following robustness-consiitenee trade-off between blindly following prediction x and incurring cost (I) = belesd, + n4 nelug, or going with the worst-case guarantee:
Uz(2, A) min Au (z), be, no)
_e(2)) = (1 (1+ 1/b,)
1- e-ee(->)
Assuming a bound of N 2 2 on the number of days and B > O on the buy price implies that U, is bounded and Lipschitz w.r.t. X. We thus run exponentiated gradient a categorical distribution over the product set [N] x {6/2.... ..,,.....,....... ,1 6/2} for some s.t. 1/8 E Zzz-
the functions U, to learn This yields the following bound on the expected regret (proof in A.3).
Corollary 6.2. For the competitive ratio upper bounds U. of the discrete ski-rental problem the randomized exponentiated gradient algorithm with an appropriate step-size has expected regret
T
max (0.1
E
7 Ud( - U2 < GN GN.TTog
Thus via an appropriate discretization the sequence of predictions (xre A,) does as well as the joint optimum on this problem. However, can also look case where we not able to just discretize

---

to get low regret. In particular, we consider the continuous ski-rental problem, where each day n, is a real number, and study how to pick thresholds r after which to buy skis, which has cost (x(ar) = meln,se Sa + (be + x:) m, Note that J = 0 and x = N recovers the previous setting where our decision was to buy or not at the beginning. For this setting. Diakonikolas et al. [15] adapt an
algorithm of Mahdian et al. [35] to bound the cost as follows:
Ca X) S U,(2, = min { (r(x)) [1-X' (E-
emin emin(n,, br)
While the bound is simpler function of X, it is discontinuous in x because 14 is piecewise- Lipschitz. Since one cannot even attain sublinear regret on adversarially chosen threshold functions, must make an assumption the data. In particular, we will assume the days dispersed:
Definition 6.3. set of (possibly random) points #1,-..., ar E are 3-dispersed if V 2 T-8 the expected number in any s-ball is O(ET), i.. E ma x = [ nTH] = Ō(=T).
Dispersion encodes the stipulation that the days, and thus the discontinuities of (x A). are not too concentrated. In the i.i.d. setting, a simple condition that leads to dispersion with = 1/2 is the assumption that the points are drawn from k- k-bounded distribution [6, Lemma 1]. Notably this is a strictly weaker assumption than the log-concave requirement of Diakonikolas et al. [15] that they used to show statistical learning results for ski-rental. Having stipulated that the ski-days are 3-dispersed, we can show that it implies dispersion of the loss functions [6] and thus obtain the following guarantee for the exponential forecaster applied to U1 A) (proof in A.4):
Corollary 6.4. For cost upper bounds U, of the continuous ski-rental problem the exponential forecaster with an appropriate step-size has expected regret
T
3 U. Ao) U.(x, A) S S 50)==OV (VTlog(NT) + (N +N+ B) 8)
max (OE
Thus in two mathematically quite different settings of ski-rental we can directly apply online learning to existing bounds to not only learn online the best action for ski-rental, but to at the same time learn how trustworthy the best action is via tuning the robustness-consistemn trade-off.
7 Conclusion and future work
The field of algorithms with predictions has been successful in circumventing worst case lower bounds and showing how simple predictions can improve algorithm performance. However, except for a few problem-specific approaches, the question of how to predict has largely been missing from the discussion. In this work we presented the first general framework for efficiently learning useful predictions and applied it to a diverse set of previously studied problems, giving the first low regret learning algorithms, reducing sample complexity bounds, and showing how to learn the best trade-off. One current limitation is the lack of more general-case guarantees and learning the predictor, which we only show for
consistency-robuslii
for simultaneously tuning robustness-consistene ski-rental. There are also several other avenues for future work. The first is to build on our results and provide learning guarantees for other problems where the algorithmic question of how to use predictions is already addressed. Another is to try to improve known bounds by solving the problems holistically: developing easy-to-learn parameters in concert with developing algorithms that can use them. Finally, there is the direction of identifying hard problems: what are the instances where no reasonable prediction can help improve an algorithm's performance?
Acknowledgmentts
We thank Yilin Yan, Alexander Smola, Shinsaku Sakaue, and Taihei Oki for helpful discussion. This material is based on work supported in part by the National Science Foundation under grants CCF-1535967, CCF-1910322 IIS-1618714, IIS-1705121, IIS-1838017, 199119,,,,, I1S-2046613, and SESS-191444 the Defense Advanced Research Projects Agency under cooperative agreements
HR001 10200003 and FA875017C0141; a Simons Investigator Award; an AWS Machine Learning Research Award; an Amazon Research Award; a Bloomberg Research Grant; Microsoft Research Faculty Fellowship; an Amazon Web Services Award; a Facebook Faculty Research Award; funding from Booz Allen Hamilton Inc.; a Block Center Grant; and a Facebook PhD Fellowship. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of any of these funding agencies.
10

---

References
[1] Keerti Anand, Rong Ge, and Debmalya Panigrahi. Customizing ML predictions for online algorithms. In Proceedings of the 37th International Conference on Machine Learning, 2020.
[2] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. A regression approach to learning-augee augmented online algorithms. In Advances Neural Information Processing Systems, 2021.
[3] Maria-Florina Balcan. Data-driven algorithm design. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, Cambridge, UK, 2021.
[4] Maria-Florina Balcan and Avrim Blum. Approximation algorithms and online mechanisms for item pricing. Theory of Computing, 3:179-195, 2007.
[5] Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In Proceedings of the 35th International Conference on Machine Learning, 2018.
[6] Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 603-614, 2018.
[7]
Balcan, Travis Dick, and Wesley Pegden. Semi-bandie optimization in the dispersed setting. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2020.
[8] Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient learn high-performing algorithms? Generalization guarantees for data-driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computingg. 2021.
[9] Maria-Florina Balcan, Mikhail Khodak. Dravyansh Sharma, and Ameet Talwalkar. Learning-to learn non-convex piecewise-Lipschie functions. In Advances in Neural Information Processing Systems, 2021.
[10] Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. In Advances in Neural Information Processing Systems, 2020.
[11] Peter Bartlett, Piotr Indyk, and Tal Wagner. Generalization bounds for data-driven numerical linear algebra. In Proceedings of the 35th Annual Conference on Learning Theory, 2022.
[12] Nicolò Cesa- Desa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. JEEE Transactions on Information Theory, 50(9):2050-205 2004.
[13] Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. In Proceedings of the 40th International Conference on Machine Learning, 2022.
[14] Ofer Dekel, Arthur Flajolet, Nika Haghtalab, and Patrick Jaillet. Online learning with a hint. In Advances in Neural Information Processing Systems, 2017.
[15] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. Learning online algorithms with distributional advice. In Proceedings of the 38th International Conference on Machine Learning, 2021.
[16] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. In Advances in Neural Information Processing Systems, 2021.
[17] Elbert Du, Franklyn Wang, and Michael Mitzenmacher. Putting the "learning" into learning- augmented algorithms for frequency estimation. Proceedings of the 38th International Conference Machine Learning. 2021.

---

[18] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In Proceedings of the 34th International Conference on Machine Learning, 2017.
[19] Rishi Gupta and Timothy Roughgarden. A PAC approach to application-specife algorithm selection. SIAM Journal on Computing, 46(3):992-1017, 2017.
[20] Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: Optimal algorithms for stochastic strongly-convex optimization. Journal of Machine Learning Research, 15:2489-2512, 2014.
[21] David P. Helmbold and Manfred K. Warmuth. Learning permutations with exponential weights. Journal of Machine Learning Research, 70177517766 2009.
[22] Piotr Indyk, Frederik Mallmann-Treon, Slobodan Mitrović, and Ronitt Rubinfeld. Online page migration with ML advice. In Proceedings of the 25th International Conference on Artificial Intelligence and Statisties, 2022.
[23] Ali Jadbabaie, Alexander Rakhlin, and Shahin Shahrampour. Online optimization: Competing with dynamic comparators. In Proceedings of the 18th International Conference Artificial Intelligence and Statistics, 2015.
[24] Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted paging with predictions. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020.
[25] Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Adaptive gradient-based based meta- learning methods. In Advances in Neural Information Processing Systems, 2019.
[26] Mikhail Khodak, Renbo Tu, Tian Li, Liam Li, Maria-Florina Balcan, Virginia Smith, and Ameet Talwalkar. Federated hyperparameter tuning: Challenges, baselines, and connections to weight-sharing. In Advances in Neural Information Processing Systems, 2021.
[27] Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, 2018.
[28] Walid Krichene, Maximilian Balandat, Claire Tomlin, and Alexandre Bayen. The hedge algorithm continuum. In Proceedings of the 32nd International Conference Machine Learning, 2015.
[29] Ravi Kumar, Manish Purohit, and Zoya Svitkina. Improving online algorithms via ML predic- tions. In Advances Neural Information Processing Systems, 2018
[30] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. In Proceedings of the 2020 ACM-SIAM Symposium Discrete Algorithms, 2020.
[31] Jeffrey Li, Mikhail Khodak, Sebastian Caldas, and Ameet Talwalkar. Differentially private meta-lcarning. In Proceedings of the 8th International Conference on Learning Representations, 2020.
[32] Sen Lin, Mehmet Dedcoglu, and Junshan Zhang. Accelerating distributed online meta-learning via multi-agent collaboration under limited communication. In Proceedings of the Twenty- second International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing. 2021.
[33] Alexander Lindermayr and Nicole Megow. Permutation predictions for non-clairvoyant schedul- ing. In Proceedings the 34th ACM Symposium on Parallelism in Algorithms and Architectures, 2022.
[34] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM, 68(4), 2021.
12

---

[35] Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Online optimization with uncertain information, ACM Transactions on Algorithms, 8:1-29, 2012.
[36] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Tim Rough- garden, editor, Beyond the Worst-Case Analysis of Algorithmss Cambridge University Press, Cambridge, UK, 2021.
[37] Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro. Online opti- mization in dynamic environments: Improved regret rates for strongly convex problems. In Proceedings of the 55th IEEE Conference on Decision and Control, 2016.
[38] Francesco Orabona and David Pal. Coin betting and parameter-free online learning, In Advances in Neural Information Processing Systems, 2016.
[39] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Annual Conference on Learning Theory, 2013.
[40] Alexander Rakhlin and Karthik Sridharan. Efficient online multiclass prediction graphs via surrogate losses. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017.
[41] Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020.
[42] Timothy Roughgarden. Beyond Worst-Case Analysis of Algorithms. Cambridge University Press, 2020.
[43] Ziv Scully, Isaac Grosof, and Michael Mitzenmacher. Uniform bounds for scheduling with job size estimates. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022.
[44] Shai Shalev-Shwarzz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2011.
[45] Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 513333885-463, 2004.
[46] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent.
In Proceedings of the 20th International Conference on Machine Learning, 2003.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumptions stated in Sections 3, 4, 6, and the Appendix.
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs given in Sections and the Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "adB7Q_c9Faf", "reviewer": "Reviewer_wD8D", "summary": "This paper proposes a general meta-framework for improving algorithms with predictions (e.g. an initial guess). The authors propose a 2 step procedure to iteratively learn better predictions: 1. upper bound the problem's cost (or tradeoff parameter) using the prediction (e.g. distance between prediction and global optimum), then 2. update the prediction using this cost estimate via standard online learning, with the goal of minimizing expected regret and sample complexity. This framework is used to derive improved guarantees across a wide range of algorithms such as matching and scheduling.\n", "questions": "- How tight are the regret/sample complexity bounds in practice on real problem instances?", "limitations": "This paper describes limitations as opportunities for future work, but does not address any potential negative social impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Originality\n- This paper presents several novel analyses under a unified framework, and cites previous work where appropriate\n\n## Quality/Significance\n- The proposed framework is interesting, well-motivated, and has potential for many follow up works\n- In the beginning of Section 4, the authors claim an upper bound on parameter $q$. However the assumption in [17] implies a lower bound on $q$. I'm unsure how much this possible bug affects the rest of the analysis.\n- This paper has clear, elegant theoretical contributions. However, it would be stronger if it also contained experiments that verify the regret guarantees, sample complexity bounds, and general efficacy of the new algorithms\n\n## Clarity\n- Well organized and a pleasure to read\n- Clear statements of results and intuitions behind them\n- Typo: on Line 89 \", nut they also\" should be \", but they also\"\n\n[17] Piotr Indyk, Frederik Mallmann-Trenn, Slobodan Mitrovic, and Ronitt Rubinfeld. Online page migration with ML advice. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, 2022.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TUIehjG7hVY", "reviewer": "Reviewer_zeSS", "summary": "The paper studies learning-augmented algorithms, mostly focused on the online setting. A recent line of works establishes that one can improve upon classic, worst-case guarantees if the algorithm is furnished with good predictions. However, the question of when and how such good predictions can be learned from data (efficiently) is still open. \n\nThis work presents a fairly general approach to answering this question. Prior work shows that the performance of a learning-based algorithm can be bounded by some error measure of the prediction (compared with the best prediction). This paper shows that if there's an efficiently-optimizable upper bound of the error measure, then techniques from online learning (in particular, online convex optimization) can be applied to learn good predictions. \n\nIt is shown that this general learning-theoretic framework can be applied to matching, paging migration, scheduling and ski-rental. ", "questions": "On the technical side, can the dimension-dependence (on n) of theorem 3.1 be improved? I think using OGD on the L-infty ball constraint may be loose. Note that one sqrt n factor comes from Line 181, where the L-infty constraint is converted to L2, allowing one to apply the OGD guarantee. The author(s) may want to look into the relevant literature on online mirror descent; e.g., “On the Universality of Online Mirror Descent” (https://arxiv.org/abs/1107.4080)\n", "limitations": "In general, I feel that this approach has more potential, to be applied to more problems. Here are two concrete suggestions:\n\n* “Permutation Predictions for Non-Clairvoyant Scheduling” (SPAA 22) studies a new prediction model for non-clairvoyant scheduling, which provides a relative order of jobs. It seems that the continuous relaxation technique of section 4 can be used to learn this permutation. I believe this could be more broadly interesting, to other online problems, such as paging and   graph problems (where vertices/edges arrive online in some order, and it would help if you can learn this order).  \n\n* “Faster Fundamental Graph Algorithms via Learned Predictions” (ICML 22) considers speeding up other (offline) graph problems, not just matching. The techniques from section 3 can probably be used in those settings. \n\nFinally, I'd like to see whether the regret bounds from section 3 can be improved. ", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n----\nThe paper is solid on a technical level and the theoretical claims are sound.\n\nOverall I find the paper very well written. \n\nTo the best of my knowledge, the results are novel. Given the recent spate of work on algorithms with predictions, I believe it has potential to make further impact\n\nWeaknesses\n---\nI am not convinced that the paper exhausts all its potential. Particularly, there should be some more problems where this general framework can be applied. I suggest a few in a later section. I encourage the author(s) to consider them in the final version or in a followup work.\n\n\nIn comparison with some of the prior work, the paper  does not provide experimental evaluations. \n\nMinor and missing references\n---\nRelated work: “Faster Fundamental Graph Algorithms via Learned Predictions” (ICML 22) also studies bipartite matching, extending Dinitz et al.\n\nTheorem 3.1. I suggest the author(s) switch the order of the third and second result, since the second result is obtained from the third (using online-to-batch conversion), so it’s natural to present the third first.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PQWWxjkEpue", "reviewer": "Reviewer_58f3", "summary": "The paper studies the learnability of predictions in the field of algorithms with predictions. The authors propose a general framework to learn predictions, and show that the framework can be applied to bipartite matching and page migration. In each setting, the proposed learning method obtains statistical guarantees. Furthermore, they show that the learning framework can help to tune the robustness-consistency tradeoffs in some problems, e.g. scheduling and ski rental.", "questions": "- The ``OnlineAlgorithm\" in Algorithm 1 is unclear to me. Does this refer to the online gradient descent algorithm?\n\n- Figure 1 is too far from where it is referenced.\n\n- The submission should not have the appendices.", "limitations": "I didn't see any potential negative societal impact.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The learnability of predictions is a piece in the learning-augmented model which receives little attention but is very necessary. The paper makes contributions in this part. It not only improves the sample complexity given in the previous work when the instance (of bipartite matching) is sampled from a fixed distribution, but also presents theoretical bounds of the sample complexity and the average regret when instances are from an adversarial sequence. To the best of my knowledge, this is the first regret bound in the learning-augmented framework.\n\nWeakness:\n- The paper has theoretical contributions but is not that technically deep. It builds on several existing theorems to give the statistical guarantees, which makes the results technically simple.\n\n- There is no experiment. In (Dinitz et al, NeurIPS 2021), experiments were provided to investigate the empirical performance. Since the paper introduces a new learning setting, it is expected that there are experiments to show that the new learning framework can perform better than the previous learning algorithm (empirical risk minimization) on some data sets.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9M_MLs0SdcP", "reviewer": "Reviewer_br4H", "summary": "This paper gives a framework for learning parameters in learning-augmented algorithms. First, an upper bound is computed on the objective of interest such that this upper bound function can be optimized. If the upper bound is reasonably tight, this is also a reasonable optimization for the actual cost. Then, the parameters optimizing the upper bound of the cost function are used as learned parameters in the learning-augmented algorithm. \n\nTwo forms of this optimization are considered in this paper: sample complexity bounds for inputs drawn from a distribution and regret bounds from online learning for adversarial inputs. In terms of applications, this idea is applied to obtain new sample complexity and online learning bounds for several problems: speeding up matching algorithms using a warm start by learned duals, online page migration, obtaining the optimal consistency-robustness tradeoff in problems like ski rental and scheduling, etc.", "questions": "I do not have specific questions. This is a nice paper overall and should be accepted.", "limitations": "There is some discussion about limitations and future work at the end of the paper. It reads somewhat generic though, mostly focusing on some broad future directions for the entire field of learning-augmented algorithms rather than being specific to this paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. I like the general area of learning-augmented algorithms and data driven algorithms, and this paper makes an important contribution to this area. There is relatively little work on the learnability of predicted parameters. Instead, the focus has been on developing (robust) algorithms to exploit (noisy) predictions generated by a black box learner. This is reasonable for certain situations, e.g., if one is using a deep neural network for the purpose of generating parameters. But, in situations where we do have well-understood theoretical abstractions such as PAC and online learning, it makes sense to think of a white box approach as proposed in this paper.\n\n2. The framework proposed is quite general and intuitive and can be applied broadly to multiple learning paradigms. In particular, the use of online learning in making predictions about algorithmic parameters is novel (to the best of my knowledge). \n\nWeaknesses:\n\n1. One might complain that there is no killer application here. In particular, the improvements in sample complexity bounds are relatively modest. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept