Algorithms with Prediction Portfolios
Authors: Michael Dinitz
Sungjin Im
Thomas Lavastida
Benjamin Moseley
Sergei Vassilvitskii
Venue: NeurIPS 2022 Accept (2022)
Keywords: algorithms with predictions
multiple predictions
learnability
minimum cost matching
load balancing
completion time scheduling

Abstract: The research area of algorithms with predictions has seen recent success showing how to incorporate machine learning into algorithm design to improve performance when the predictions are correct, while retaining worst-case guarantees when they are not.  Most previous work has assumed that the algorithm has access to a single predictor. However, in practice, there are many machine learning methods available, often with incomparable generalization guarantees, making it hard to pick a best method a priori. In this work we consider scenarios where multiple predictors are available to the algorithm and the question is how to best utilize them. 

Ideally, we would like the algorithm's performance to depend on the quality of the {\em best} predictor.  However, utilizing more predictions comes with a cost, since we now have to identify which prediction is best.  We study the use of multiple predictors for a number of fundamental problems, including matching, load balancing, and non-clairvoyant scheduling, which have been well-studied in the single predictor setting. For each of these problems we introduce new algorithms that take advantage of multiple predictors, and prove bounds on the resulting performance. 

Algorithms with Prediction Portfolios
Michael Dínitz Johns Hopkins University mdinitz@cs. wtw.teee.........eeeo.eeee edu edu
Sungjin Im UC Merced s im3@ucmercedd edu
Thomas Lavastida" University of Texas at Dallas
thomas cetrrastidd@utdaallee edu
Benjamin Moseley
Sergei Vassilvitskii
Carnegie Mellon University moseleybone moseleybbandrew. cmu. edu
Google Research sergeivdgoogle... com
Abstract
The research area of algorithms with predictions has seen recent success showing how to incorporate machine learning into algorithm design to improve performance when the predictions are correct, while retaining worst-case guarantees when they are not. Most previous work has assumed that the algorithm has access to single predictor. However, in practice, there are many machine learning methods available, often with incomparable generalization guarantees, making it hard to pick the best method a priori. In this work we consider scenarios where multiple predictors are available to the algorithm and the question is how to best utilize them.
Ideally, we would like the algorithm's 's performance to depend on the quality of the best predictor. However, utilizing more predictions comes with a cost, since we now have to identify which prediction is the best. We study the use of multiple predictors for number of fundamental problems, including matching, load balancing, and non-clairvoyant scheduling, which have been well-studied the single predictor setting. For each of these problems we introduce new algorithms that take advantage of multiple predictors, and prove bounds on the resulting performance.
Introduction
An exciting recent line of research attempts to go beyond traditional worst-case analysis of algorithms by equipping algorithms with machine-learned predictions. The hope is that these predictions allow the algorithm to circumvent worst case lower bounds when the predictions are good, and approximately match them otherwise. The precise definitions and guarantees vary with different settings, but there have been significant successes applying this framework for many different algorithmic problems, ranging from general online problems classical graph algorithms (see Section 1.2 for a more detailed discussion of related work, and (33) for survey). In all of these settings turns out be possible define "prediction" where the "quality" of the algorithm (competitive ratio, running time, etc.) depends the "error" of the prediction. Moreover, in at least some of these settings, has been further shown that this prediction is actually learnable with a small number of samples, usually via standard ERM methods (18).
Previous work has shown the power of accurate predictions, and there are numerous examples showing improved performance both theory and practice. However, developing accurate predictors remains art, and single predictor may not capture all of the subtleties of the instance space. Recently, researchers have turned to working with portfolios of predictors: instead of training single model, train multiple models, with the hope that one of them will give good guarantees.
Work was done while the author was at Cameegie Mellon University.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

It is easy to see why the best predictor in portfolio may be significantly better than a one-size fits all predictor. First, many of the modern machine learning methods come with a slew of hyperparameters that require tuning. Learning rate, mini-batch size, optimizer choice, all of these have significant impact on the quality of the final solution. Instead of commiting to a single setting, one can instead try to cover the parameter space, with the hope that some of the predictors will generalize better than others. Second, problem instances themselves may come from complex distributions, consisting of many latent groups or clusters. A single predictor is forced to perform well on average, whereas multiple predictors can be made to "specialize" to each cluster.
In order to take advantage of the increased accuracy provided by the portfolio approach, we must adapt algorithms with predictions to take advantage of multiple predictions. To capture the gains in performance, the algorithm must perform as if equipped with the best predictor, auto- uuto-tuning to use the best one available in the portfolio. However, it easy to see that there should be cost as the size of the portfolio grows. In the extreme, one can add every possible prediction to the portfolio, providing no additional information, yet now requiring high performance from the algorithm. Therefore, we must aim to minimize the dependence on the number of predictions in the portfolio.
We remark that the high level set up may be reminiscent of expert- or bandit-leariing literature. However, there is a critical distinction. In expert and bandit learning, we are given a sequence of problem instances, and the goal to compete (minimize regret) with respect to the best prediction averaged over the whole sequence. On the other hand, in our setup, we aim to compete with the best predictor on a per-instance basis.
Previous work multiple predictions. Bhaskara et al. studied an online linear optimization problem where the learner seeks to minimize the regret, provided access to multiple hints [[6]. Inspired by the work, Anand et al. recently studied algorithms with multiple learned predictions in (7]. proving strong bounds for important online covering problems including online set cover, weighted caching, and online facility location. It was significant extension of the work [22] which studied the rent-or-buy problem with access to two predictions. However, their techniques and results limited to online covering problems. Moreover, they do not discuss the learning aspects all: they simply assume that they are given h predictions, and their goal is to have competitive ratios that are based on the minimum error of any of the k predictions. (They actually compete against stronger dynamic benchmark, but for our purposes this distinction is not important.)
On the other hand Balcan et al. 14 look at this problem through a data driven algorithm lens and study the sample complexity and generalization error of working with k (as opposed to 1) parameter settings. The main difference from our work is that they also aim learn selector, which selects one of the A parameters prior to beginning to solve the problem instance. In contrast, in this work we make the selection during the course of the algorithm, and sometimes switch back and forth while honing in on the best predictor.
1.1 Our Results and Contributions
In this paper we study three fundamental problems, min-cost perfect matching, online load balancing, and non-clairvoyant scheduling for total completion time, in this new setting. Each of these has seen significant success in the single-prediction model but is not covered by previous multiple-reddiction frameworks. Our results are primarily theoretical, however we have included a preliminary empirical validation of our algorithm for min-cost perfect matching in the supplementary material.
For each of these we develop algorithms whose performance depends on the error of the best prediction, and explore the effect of the number of predictions, k. Surprisingly, in the case of matching and scheduling we show that using a limited number of predictions is essentially free, and has no asymptotic impact on the algorithm's 's performance. For load balancing, on the other hand, we show that the cost of multiple predictions grows logarithmically with k; again implying a tangible benefit of using multiple predictions. We now describe these in more detail.
Min-Cost Perfect Matching. We begin by showcasing our approach with the classical min-cost
perfect matching problem in Section 3 This problem was recently studied by [7 18 to show that is possible to use learned predictions to improve running times of classical optimization problems. In particular, [18 showed is possible to speed up the classical Hungarian algorithm by predicting
dual values, and morcover that it is possible to efficiently (PAC-)learn the best duals. We show that

---

simple modifications of their ideas lead to similar results for multiple predictions. Interestingly, we show that as long as k I O( n) the extra "cost" (running time) of using k predictions is negligible compared to the cost of using a single prediction, so we can use up to vn predictions "for free" while still getting running time depending on the best of these predictions. Moreover, since in this setting running time is paramount, we go beyond sample complexity to show that it is also computationally efficient to learn the best k predictions.
Online Load Balancing with Restricted Assignments. We continue in Section with the funda- mental load balancing problem. In this problem there are m machines, and jobs which appear in online fashion. Each job has a size, and a subset of machines that it can be assigned to. The goal is to minimize the maximum machine load (i.e., the makespan). This problem has been studied extensively in the traditional scheduling and online algorithms literature, and recently it has also been the subject of significant study given single prediction [66-28] In particular, Lattanzi, Lavastida, Moseley, and Vassilvitskii [26] showed that there exist per machine "weights" and an allocation function so that the competitive ratio of the algorithm depends logarithmically on the maximum error of the predictions. We show that one can use k predictions and incur an additional (log k) factor in the competitive ratio, while being competitive with the error of the best prediction. Additionally, we show that learning the best & predicted weights (in a PAC sense) can be done efficiently.
Non Clairvoyant Scheduling Finally, in Section 5 we move to the most technically complex part of this paper. We study the problem of scheduling n jobs on a single machine, where all jobs released at time 0, but where we do not learn the length of job until it actually completes (the non-clairvoyans model). Our objective is to minimize the sum of completion times. This problem
has been studied extensively, both with and without predictions (24, 30 35 371. Most recently, Lindermayr and Megow (30] suggested that we use an ordering as the prediction (as opposed to the more obvious prediction of job sizes), and use the difference between the cost induced by the predicted ordering and the cost induced by the instance-optimal ordering as the notion of "error". In this case, simply following the predicted ordering yields an algorithm with error equal to the prediction error.
We extend this to the multiple prediction setting, which turns out to be surprisingly challenging. The algorithm of [30] is quite simple: follow the ordering given by the prediction (and run 2-competitive algorithm in parallel to obtain worst-case backstop). But obviously cannot do this when are given multiple orderings! So we must design an algorithm which considers all & predictions to build schedule that has error comparable to the error of the best one. Slightly more formally, we prove that we can bound the sum of completion times by (1 + e)PT plus poly(1/e) times the error of the best prediction, under the mild assumption that no set of at most log log n. jobs has large contribution to OPT.
To do this, we first use sampling techniques similar to those of [24] to estimate the size of the approximately en 'th smallest job without incurring much cost. We then use even more sampling and partial processing to determine for each prediction whether its en prefix has many jobs that should appear later (a bad sequence) or has very few jobs that should not be in the prefix (a good sequence). If all sequences are bad then every prediction has large error, and charge the cost to the prediction error. Otherwise, we choose one of the good orderings and follow for its en prefix (being careful to handle outliers). We then recurse on the remaining jobs.
use round robin schedule
1.2 Related Work
As discussed, the most directly related papers are Anand et al. 77 and Balcan, Sandholm, and Vitercik [14]; these give the two approaches (multiple predictions and portfolio-based algorithm selection) that are most similar to our setting. The single prediction version of min-cost bipartite matching was studied in [17] [8], the single prediction version of our load balancing problem was considered by 22 (and a different though related load balancing problem was considered by [4),, and the single prediction version of our scheduling problem was considered by [30] with the same
prediction that we use (an ordering) and earlier with different predictions by [4 37 39
Online
scheduling with estimates of the true processing times was considered in [1]
More generally, there has been an enormous amount of recent progress on algorithms with predictions.
This is particularly true for online algorithms, where the basic setup formalized by [31] in the
3

---

31 38 secretary problems [0], ski rental 37 39, and set cover [15]. There has also been recent work on going algorithmic game theory 2 21 32, and streaming algorithms i 19 23 The learnability of predictions for online algorithms with predictions was considered by 66. They give novel loss function tailored to their specific online algorithm and prediction, and study the sample complexity of learning a mapping from problem features to prediction. While they only concerned with the sample complexity of the learning problem, we also consider the computational complexity, giving polynomial time (approoio algorithms for the learning problems associated with min-cost matching and online load balancing.
context of caching. For example, the problems considered include caching 25
beyond traditional online algorithms, including work on running times 17 18
The above is only small sample of the work on algorithms with predictions. We refer the interested reader a recent survey (33. as well as recently set up website which maintains a list of papers in the area 29
2 Learnability
When designing new methods in the algorithms with predictions setting, the predictions under consideration must satisfy two constraints. First, they should be useful to the algorithm, so that using the predictions allows the algorithm to achieve better running time, competitive ratio, some other performance measure. Second, they must be learnable: it must be feasible to find good predictions given a of problem instances.
To rigorously prove learnability, we follow previous work 13 on the sample complexity of finding the best predictions that generalize.
18 34) and focus on proving a bound
Our main result shows that for given problem, the pseudo-dimension of finding i predictions is Ö(k) factor larger than that for finding a single best predictor. We state the formal Theorem below, but defer the proof to the supplementary material.
Theorem 2.1. Let F be a class of functions : X - R with pseudo- d and let F (F(x) = minse(H] fx()) ff fI......., ghc E F}. Then the pseudo dimenindimension of Fk is at most Ödk)).
Note that this directly implies that the sample complexity when looking for k predictions is factor of k larger than that of a single predictor by the following well-known theorem.
Theorem 2.2. g 34
36) Let D be distribution over domain X and F be a class of functions pseudo-dimension dimension dy. Consider independent samples ø1, 22..... Ey from D.
f: X [0, H with pseudo
There is universal constant co, such for any >> O and 5 E (0. 2 co (#) (dy+In(1/8)) then we have
f(x;) EEND(((E)) Sc
for all f E F with probability at least 1 1-6 8.
3 Minimum Cost Bipartite Matching with Predicted Duals
In this section we study the minimum cost bipartite matching problem with multiple predictions. The case of a single prediction has been considered recently [1], where they used dual values as prediction and showed that the classical Hungarian algorithm could sped up by using appropriately learned dual values. Our goal in this section is to extend these results to multiple predictions, i.e., multiple duals. In particular, in Section 3.2 we show that we can use k duals and get running time comparable to the time we would have spent if we used the single best of them in the algorithm of [18), with no asymptotic loss if is at most O (n). Then in Section 3.3 we show that & predictions can be learned with not too many more samples (or running time) than learning a single prediction.
20(.) suppresses logarithmic factors

---

3.1 Problem Definition and Predicted Dual Variables
In the minimum cost bipartite matching problem we are given a bipartite graph G (V, E) with |V| vertices and m =EE| edges, with edge costs c E z". The objective is to output perfect matching M S E which minimizes the cost c(M) := Eeer Ce. This problem is exactly captured by the following primal and dual linear programming formulations.
Dinitz al. 18 studied initializing the Hungarian algorithm with a prediction I of the optimal dual solution y" They propose an algorithm which operates in two steps. First, the predicted dual solution D may not be feasible, so they give an O(n + m) time algorithm which recovers feasibility (which we refer to as Make--Fessbble dual solution is used in a primal-dual algorithm such as the Hungarian algorithm (which we refer to as Primal-Dusl and they show that the running time depends on the & error the predicted solution. In addition to this they show that learning a good initial dual solution is computationally efficient with low sample complexity. More formally, they proved the following theorems.
min
Σ Co
(MWPM-P)
Fr.
VIEV
Second, the now-feasible
NEN())
Ie
VEE E
max
Σ Vi
(MWPM-D)
EV + yj S Ce
Ve = ij E
Theorem 3.1 (Dimitz et al. (18). Let (G,c) c) be an instance of minimum cost bipartite matching and ÿ be prediction of an optimal dual solution y² There exists an algorithm which returns an optimal solution and runs in time O(mvT llv" - 9111).
Theorem 3.2 (Dinitz et al. [8]. Let D be an unknown distribution over instances (G,c) on vertices and let y (G, c) be an optimal dual solution for the given instance. Given S independent samples from D, there is polynomial time algorithm that outputs solution ÿ such that
E(G.ey~D Illy* (G, - 0111] S min B(G.,)~D Illy* (G,c) =111] +
with probability 1 where S poly(n, (n, c }).
3.2
Using k Predicted Dual Solutions Efficiently
Given k predicted dual solutions "².."..... we would like to efficiently determine which solution has the minimum error for the given problem instance. Note that the predicted solutions may still be infeasible and that we do not know the target optimal dual solution y". We propose the following simple algorithm which takes as input k predicted solutions and whose running time depends only on the l error of the best predicted solution. First, we make each predicted solution feasible, just as before. Next, select the (now-leasible) dual solution with highest dual objective value and proceed running the primal-dual algorithm with only that solution. See Algorithm I forr pseudo-code.
We have the following result concerning Algo- rithm [ To interpret this result, note that the cost for increasing the number of predictions is ((k(n+m)), which will be dominated by the myn term we pay for running the Hungarian algorithm unless k is extremely large (certainly larger than /n) or there is prediction with error (which is highly unlikely). Hence we can reap the benefit of a large number of predictions "for free".
Algorithm Minimum cost matching with k predicted dual solutions
1: procedure k- s=PREDICTEDPIIMAL-DUAUU for l [k]] do
80, ,',0"'".0. , ......)))) 8r)
y² MaMMaeeFeasbbbllGG.... 4: end for
E' ++++r arg ma (k) Eiev of M PrrimallDDallCC (G,c,y²) c.y²))
6:
Return M
8: end procedure
Theorem 3.3. Let (G,c) be minimum cost bipartite matching instance and let ğ .g?...., predicted dual solutions. Algorithmm] returns an optimal solution and runs in time Okk(n m) + mynn minse Ily - (1))
....... g² be
We defer the proof to the supplementary material. But correctness is essentially direct from 18 and the running time requires just a simple modification of the analysis of [18).
5

---

3.3 Learning & Predicted Dual Solutions
Next extend Theorem 3.2 to the setting where output & predictions. Let D be distribution over problem instances (G, c) on n vertices. We show that we can find the best set of l predictions. More formally, prove the following theorem.
Theorem 3.4. Let DD be an unknown distribution over instances (G, c) on n. vertices and let y (G, c) be an optimal dual solution for the given instance. Given S independent samples from D, there is polynomial time algorithm that outputs k solutions g v.. ......." 5 such that
((GD))
min 110 (G, S <01)) [EE(A]
min BiG,))D [E
min (G, 1/111 te
with probability 8 where poly(n, (n. k. ct
The proof of this theorem can he found in the supplementary material, but it is straightforward. The sample complexity due combining Theorem 2.1 with Theorem 3.2 (or more precisely, with the pseudo-dimensing
bound which implies Theorem 3.2). The ((T)aaprroximation factor and polynomial running time from the observation that the ERM problem this setting just an instance of the k-median clustering problem.
4 Online Load Balancing with Predicted Machine Weights
We now apply our framework online load balaneing with restricted assignments. In particular, we consider proportional weights, which have been considered in prior work [26 Informally, we show in Section 4.2 that if B the cost of the best of the i predictions, then even without knowing a priori which prediction is best, we get cost of O(3 log k). Then in Section 4.3 we show that it does not take many samples to actually learn the best k predictions.
4.1 Problem Definition and Proportional Weights
In online load balancing with restricted assignments there is sequence of n jobs which must be assigned to machines in an online fashion. Upon seeing job j. the online algorithm observes its size Pj > and neighborhood NG) S [m]] of feasible machines. The algorithm must then choose some feasible machine E N(j) to irrevocably assign the job to before seeing any more jobs in the sequence. We also consider fractional assignments, i.c. vectors belonging to the set X {I E IT Vj [n], E, Izj = I, and Tij 0 > & N()).
Prior work studied the application of proportional weights 3 28 Intuitively, a prediction in this setting is a weighting of machines, which then implies an online assignment, which is shown to be netr-op Slightly more formally, suppose that we are given weights w; for each machine i, Then each job j is fractionally assigned to machine i to fractional amount of wy
EveNyy wy Notice
that given weights, this also gives an online assignment. is known that there exist weights for any instance where the fractional solution has near optimal makespan, even though there are only m "degree of freedom" in the weights compared to mn in an assignment. That is, for all machines i, is most (1 + factor larger than the optimal makespan for any constant Eje(n Pj EVeNs) Whr
0
3 126].
Let w be set of near optimal weights for a given instance. Lattanzi al. 26 showed the following theorem:
Theorem 4.1. Given predicted weights ú. there an online fractional algorithm which has makespan to be the error in the prediction. Ollog(n(ú,, w² OOPT), where 1)(10, w²) = max;e[m] max th wi
Moreover, this fractional assignment can be converted online to an integral assignment while losing only an Olog lo) factor in the makespan 26 28). Thus, we focus on constructing fractional assignments that are competitive with the best prediction in hindsight.

---

4.2 Combining Fractional Solutions Online
Given I different predicted weight vectors w., uh ,....... u. we want to give an algorithm which is competitive against the minimum enror among the predicted weights, i.e. we want the competitiveness to depend upon 7/min == minge[k] 17("", w=).
The challenge is that do not know up front which e E [k] will yield the smallest error, but instead learn this in hindsight. For each & E [k]. let be the resulting fractional assignment from applying the fractional online algorithm due to [26] with weights wf. This fractional assignment is revealed one job at time.
We give an algorithm which is (log commpttiiee against any collection of l fractional assignments which are revealed online. Moreover, our result applies to the unrelated machines setting, in which The algorithm is based on the doubling trick and is similar to results in [IO] which apply to metrical task systems. Let mi max; 2, Piyziy be the best fractional makespan in hindsight. As in previous work, our algorithm is assumed to know |3, an assumption that can be removed [26]. At a high level, our algorithm maintains set A C [k] of solutions which are good with respect the current value of 3, averaging among these. See Algorithm 2 for a detailed description. We have the following theorem.
each job has a collection of machine-dependent sizes
Theorem 4.2. Let x x.? ,...,"" x² be fractional assignments which are revealed online. A/goorith run with = minge(k] max; Ej Pizafg. then it yields a solution of cost Olog k) and never reaches the fail state (line in Algorithm
Let Be = max, E, Peyaff and OPT be the optimal makespan. Theorem 4.1 shows that Be S Olog Me OPT. The following corollary is then immediate:
Corollary 4.3. Let w w² ..... w be the predicted weights with errors n7 n/2 ..... ./¹ Then Algo- rithm returns a fractioonal assignment with makespan at most OPT O(log k)- minseja] log(n").
Algorithm 2 Algorithm for combining fractional solutions online for load balancing.
procedure COMBNN-LOADBLLANCIIGG))
2: A + [k]
>> Initially all solutions are good
3: for each job j do
4: Receive the assignments
x I
5: A(j. 3) < {e E Vi e [m]. oly > = Pijals S BB}
6:
if 0 or A(j 8) then
7:
Return "Fail" end if
8:
9:
Vi E [m), Fij <- [AC.9]| ExEAcII
10:
B - (E E max;e[[] Ey Pigaayy > B8
D Bad solutions w.r.t. B
11:
A A\B B
end for
13:
end procedure
We defer the proof of Theorem 4.2 to the Supplementary material.
4.3 Learning & Predicted Weight Vectors
We now turn the question of showing how to leam h different predicted weight vectors r. i?..... u Recall that there is an unknown distribution D over sets of n jobs from which receive independent samples J2.... Js. Our goal is to show that we can efficiently learn (in terms of sample complexity) l predicted weight vectors to minimize the expected minimum error. "/) be Let w" (J) be the correct weight vector for instance and let n7w, w²) max max( wy w/ the error between pair of weight vectors. We have the following result.
Theorem 4.4. Let D be an unknown distribution over restricted assignment instances on n jobs and let w" (J) be set of good weights for instance J. Given S independent samples from D,
7

---

there is a polynomial time algorithm that output k weight vectors wi . wh such that E [minee[s] log(n(w', w (J)) + e
ES-D [mi] log(n( w" (J))] Σ O(1) ming' _22
with probability 8, where S = poly(mo (m, k. +
The proof of Theorem 4.4] is deferred the Supplementary material, but we note that to get polynomial time algorithm we carry out an interesting reduction to k-median clustering. Namely, we show that the function d(w, w') := log(r((w w()) satisfies the triangle inequality and thus forms a metric space.
Scheduling with Predicted Permutations
In this problem there are n jobs, indexed by 1,2.... n. to be scheduled on a single machine. We assume that they are all available at time 0. Job j has size Pj and needs to get processed for P; time units to complete. If all job sizes are known a priori, Shortest Job First (or equivalently Shortest Remaining Time First), which processes jobs in non-decreasing order of their size, is known to be optimal for minimizing total completion time. We assume that the true value of pj is unknown and revealed only when the job completes, i.c. the non-clairvoyant setting. In the non-clairvoyant setting, it is known that Round-Robin (which processes all alive jobs equally) is 2-competitive and that this is the best competitive ratio one hope for (35].
We study this basic scheduling problem assuming certain predictions are available for use. Fol- lowing the recent work by Lindermayr and Megow [30, we will assume that we are given k orderings/sequences as prediction, {oe Each dg a permutation of J := [n]. Intuitively, suggests an ordering in which jobs should be processed. This prediction is inspired by the afore- mentioned Shortest Job First (SJF) as an optimal schedule can be described as an ordering of jobs, specifically increasing order of job sizes.
For each oe. its error is measured as n)J, σe) == co OPT(J), where COST(J, σz) denotes the objective of the schedule where jobs are processed in the order of a and OPT(J) denotes the optimal objective value. We may drop from notation when it is clear from the context.
As observed in 30), the error can be expressed as 17(J,, oz) = Eiejes 1/ lp: Pýl. where T is an indicator variable for 'inversion' that has value if and only if ae predicts the pairwise ordering of and j incorrectly. That is, if p; Pj. then the optimal schedule would process é before j; here 1i 1 iff i > j.
As discussed in 330 this error measure satisfies two desired properties, monotonicity and Lipschitz- ness, which were formalized in 24
Our main result is the following.
Theorem 5.1. Consider a constant e > O. Suppose that for any S C with |S|= O O (log logn log k + log(1/e))), we have OPT(S) S ce (PT(J) for some small absolute constant c. Then, there exists a randomized algorithm that yields schedule whose expected total completion time is at most (1 + e)OPT + (1 + <) [,,,, ()) for all & E [k))
As a corollary. by rumning our algorithm with 1 - e processing speed and simultancously running Round- Rohnd-Robin with the remaining of the speed, the cost increases by factor of at most T-c while the resulting hybrid algorithm is 2/ 2/e-competitive
5.1 Algorithm
To make our presentation more transparent we will first round job sizes. Formally, we choose uniformly at random from [0, 1). Then, round up each job j's size to the closest number of the form (1 + c)oft for some integer L. Then, we scale down all job sizes by (1 + e) factor. We will present our algorithm and analysis assuming that every job has size equal to power of (1 + e). In the
Formally, we run our algorithm ignoring RR's 's processing and also run RR ignoring our algorithm; this can be done by a simple simulation. Thus, we construct two schedules concurrently and each job completes at the time when it does in either schedule. This type of algorithms first used in B7].
3 'This hybrid algorithm is essentially the preferential time sharing 24 50 37
8

---

supplementary we show how to remove this assumption without increasing our algorithm's objective by more than 1 + factor in expectation.
We first present the following algorithm that achieves Theorem 5.1 with |S| = x (log n + log k)). The improved bound claimed in the theorem needs minor tweaks of the algorithm and analysis and they are deferred to the supplementary material.
Our algorithm runs in rounds. Let J, be the jobs that complete in round 2 1. For any subset S of rounds, Js := U,. For example, Jgr == J1 U... Jy. Let n, := |Jzel = n - |J denote the number of alive jobs at the beginning of round r.
Fix the beginning of round r. The algorithm processes the job in the following way for this round. If n, S (log n + log k)), we run Round-Robin to complete all the remaining, jobs, Jzr. This is the last round and is denoted as round L. + 1. Otherwise, we do the following Steps 1-4:
Step 1. Estimating c-percentile. Roughly speaking, the goal is to estimate the e-percentile of job sizes among the remaining jobs. For a job j E JJzr. define its rank among J2r as the number of jobs no smaller than j in Jzr breaking ties in an arbitrary yet fixed way. Ideally, we would like to estimate the size of job of rank en,, but do so only approximately.
The algorithm will find q. that is the size of a job whose rank lies in [e(1 e) e(1 + e)n,]. To handle the case that there are many jobs of the same size qr. we estimate yr the number of jobs no bigger than q-; let y, denote without spending much time by sampling some jobs and partially processing them in Round-Robin manner (the proof of the following lemma can be found in the supplementary material.)
estimate of Vr- We will show how we can do these estimations
Lemma 5.2. W.h.p. the algorithm can construct estimates qr and Dr in time at most O 73 logn) such that there is a job of size q. whose rank lies in [e(1 - e)nn,, c(1 e)m,) and 1 yrl S en
Step 2. Determining Good and Bad Sequences. Let of denote oy with all jobs completed in the previous rounds removed and with the relative ordering of the remaining jobs fixed. Let of_, denote the first őr jobs in the ordering. We say a job is big if P3 > qr: middle if pj ~r: small otherwise. Using sampling and partial processing we will approximately distinguish good and had sequences. Informally of is good if of, has few big jobs and bad if it does many big jobs. The proof of the following lemma can be found in the supplementary material.
Lemma 5.3. For all 8 E [k], we label sequence of either good bad in time at most Og 2 (log n + log k)) that satisfies the following with high probability: If it is good, o²,e has at most n. big jobs; otherwise or,, has at least nn big jobs.
Step Job Processing. If all sequences are bad, then we process all jobs, each up q. units in an arbitrary order. Otherwise, we process the first Zr jobs in an arbitrary good sequence, in an arbitrary order, each up to q. units.
Step 4. Updating Sequences. The jobs completed in this round drop from the sequences but the remaining jobs' relative ordering remains fixed in each juqu)ssq For simplicity, we assume that partially processed jobs were never processed- this is without loss of generality as this assumption only increases our schedule's objective.
5.2 Analysis of the Algorithm's Performance
We defer the analysis of the above algorithm (the proof of Theorem 5.1) to the supplementary material, as it is quite technical and complex. At a very high level, though, we use the f'cc that the error in each prediction can be decomposed into pair-wise inversions, and moreover we can partition the inversions into the rounds of the algorithm in which they appear. Then we look at each round, and split into two cases. First, if all sequences are bad then every prediction has large error, so we can simply use Round Robin (which is 2 2-competitive against OPT) and the cost can be charged to the error of any prediction. Second, if there is a good sequence, then in any good sequence the number of big jobs is small (so we do not spend much time processing them), and we therefore complete almost all of the non-big jobs. Here, we crucially use the fact that we can process the first fraction of jobs in a sequence in an arbitrary order remaining competitive against the sequence. Finally, show that all

---

of the additional assumptions and costs (e.g., rounding processing times and the cost due to sampling) only change our performance by + e factor. Getting all of these details right requires much care.
5.3 Learning k Predicted Permutations
Now show that learning the best k permutations has polynomial sample complexity.
Theorem 5.4. Let 'D be an unknown distribution of instances on jobs. Given S indepen- dent samples from 'D there is an algorithm that outputs k permutaations 51, .2..... 5g such that EI [minee(s] [[J] mill.,,02...... BB [minge[s] nnJ, az)] + with probability 6, where S poly(n, k. 8)
Proof. The algorithm is basic ERM, and the polynomial sample complexity follows from Theorem 2.1 and Theorem 20 in Lindermayr and Megow (30).
Conclusion
Despite the explosive recent work in algorithms with predictions, almost all of this work has assumed only single prediction. In this paper we study algorithms with multiple machine-learned predictions, rather than just one. We study three different problems that have been well-studied in the single prediction setting but not with multiple predictions: faster algorithms for min-cost bipartite matching using learned duals, online load balancing with learned machine weights, and non-clairvoyant scheduling with order predictions. For all of the problems we design algorithms that can utilize multiple predictions, and show sample complexity bounds for learning the best set of k predictions. Demonstrating the effectiveness of our algorithms (and the broader use of multiple predictions) empirically is an interesting direction for further work.
Surprisingly, we have shown that in some cases, using multiple predictions is essentially "free." For instance, the case of min-cost perfect matching examining amount of time as one round of the Hungarian algorithm, but the number of rounds is determined by the quality of the best prediction. In contrast, for load balancing, using k predictions always incurs an Olog k)) cost, so using a constant number of predictions may be best. More generally, studying this trade-off between the cost and the benefit of multiple predictions for other problems remains an interesting and challenging open problem.
O(vn) predictions takes the same
Acknowledgments and Disclosure of Funding
Michael Dinitz was supported in part by NSF grant 1C9-1909111 Sungjin Im was supported in part by NSF grants CCF-1617653, 184499 and CCF-2121745. Thomas Lavastida and Benjamin Moseley were supported in part by NSF grants CCF- CMMI-1938909. Benjamin Moseley was additionally supported in part by a Google Research Award, an Infor Research Award, and Carnegie Bosch Junior Faculty Chair.
(CCF-184116, CCF-2121744 and
References
[1] Anders Aamand, Piotr Indyk, and Ali Vakilian. (learned) frequency estimation algorithms under zipfian distribution. arXiv preprint arXiv:1908.051 05988 2019.
[2] Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. Learning- augmented mechanism design: Leveraging predictions for facility location, 2022. URL https
orw.a/s/.rg///////////ooo/b. 2204. 01120
[3] Shipra Agrawal, Morteza Zadimoghaddam, and Vahab Mirrokni. Proportional allocation: Simple, distributed, and diverse matching with high entropy. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüüssun, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of mlr
Machine Learning Research, pages 99-108. PMLR, 2018. http: press/v80 Press//80/agrawal1ee wgrawwll8b..... html
10

---

[4] Sara Ahmadian, Hossein Esfandiari, Vahab Mirrokni, and Binghui Peng. Robust Load Balancing with Machine Learned Advice, pages 20- 34. 2022. doi: 00.11377/.978161111777333 URL httpss//epubs. siam. org doi wwwp//////bbsoooooo/oo 1137/1 11t.1/..........97111117777...1. 9781611977073..2
[5] Keerti Anand, Rong Ge, and Debmalya Panigrahi. Customizing ML predictions for online algorithms. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Viriual Event, volume 119 of Proceedings of Machine Learning Research, pages 303-313. PMLR, 2020. URI. html
mlr www.mmml.........e.mm.m.m /
[6] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. regression ap- proach to learning-augmented online algorithms. In Marc' Aurelio Ranzato, Alina Beygelz- imer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Ad- vances in Neural Information Processing Systems 34; Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 30504-30517, 2021. URL https::::: http:///eocceeeeeeeeeeee
ceourips.cc/ppper/202222
Abstract. html
[7] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions. In Proceedings of the 39th International Conference on Machine Learning, ICML 2022, 2022.
[8] Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations. cambridge university press, 2009.
[9] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev, Secretary and online matching problems with machine learned advice. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Sarri-FFlorina Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Informa- tion Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 2020, virtual, 2020. URL / www.innggse.uuuueeeeee neur ips cc/paper/20200 httaa////.7.78000000016111111133 www.:ttt-bbbttttttt.om
[10] Yossi Azar, Andrei Z. Broder, and Mark S. Manasse, On-line choice of on- oine algorithms. In Vi- jaya Ramachandran, editor, Proceedings of the Fourth Annual ACM/SIGACT
Symposium on Discrete Algorithms,, 25-27 January 1993, Austin, Texas, USA, pages 432 440. ACM/SIAM, 1993. URLpttp:: //dl. acm. org/ citation. sfm?id=31355 01135559.1884777 313847
[11] Yossi Azar, Stefano Leonardi, and Noam Touitou. Flow time scheduling with uncertain processing time. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1070-1080, ACM, 2021. doi: 10. 10.11455340062553551000 URL https //doi.org// 10. 04445//3433252./ 3451023
[12] Yossi Azar, Stefano Leonardi, and Noam Touitou. Distortion-oblivious algorithms for mini- mizing flow time. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9- 12, 2022, pages 252-274. STAM, 2022. doi:
URL https://////o11 org 10. 1137/1 7781111977117111.1
[13] Maria-Florina Balcan, Dan F. DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data sufficient to learn high-performing algorithms? CoRR, hbss/998.028944 2019, URL http::ttt://tttt org/ abs/ abs/1908 1908. 02894
[14] Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Generalization in portfolio-based algorithm selection. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 12225- 12232. AAAI Press, 2021. htttt:tt////ogg aaai org/ heg/index.cr php/ /tt.A///aaaacceeee////r
[15] Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell,

---

Balcan, and Hsuan-Tiees Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020. NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL httpp::/ neur ips. wtt.cccppper//22200000/ 4833611148377500007776666666-643
[16] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit, Online linear optimiza- tion with many hints. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Newral Information Processing Systems, volume 33, pages 9530-9539. Curran Associates, Inc., 2020. URL /tt/spps////prreeeainnss http://erer.p....peee//////
file/6c220 /ttp///2888222004440303000002220 Paper pdf
[17] Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. CoRR, abs/2204.120555 12055, 2022. doi: 10.48550/arXiv.2204
12055. URL https:////doi org/10. 48550/ arxiv 2204. 12055
[18] Michael Dinitz, Sungjin Im. Thomas Lavastida, Benjamin Moseley, and Sergei Vassil- vitskii. Faster matchings via learned duals. In Marc' Aurelio Ranzato, Alina Beygelz- imer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Ad- vances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 10393-10406, 2021. URL httptttts////rcceeeeee www.--bb.ttttttmmm
neurips. cat.cccppappe wwwpcppppe/////eecce 2021/hah/////
[19] Elbert Du, Franklyn Wang, and Michael Mitzenmacher. Putting the "learning" into learning- augmented algorithms for frequency estimation. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Pro- ceedings of Machine Learning Research, pages 2860-2869, PMLR, 18-24 Jul 2021. URL https://proceeddi:
mlr wwwps/ pttoss/vv33//00 htt.1399//22.d..... html
[20] Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. CoRR, abs/201 1ttp/2001.06666, .06726, 2020. URL http:/ttts///xxi..t/ta org/ abs/ 06726.
[21] Vasilis Gkatzelis, Kostas Kollias, Alkmini Sgouritsa, and Xizhi Tan. Improved price of anarchy via predictions, 2022.
http:///axvvvv.. www.aiwww....aaaaaaee
www./rgg////.... abtg//bs//222 04252
[22] Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, Califormia, USA, volume 97 of Proceedings of Machine Learning Research, pages 2319 2327. PMLR, 2019, /tLL/tttp:///oo//
mlr. www..press/vee v97 haai//golllppuuui 19a. html
[23] Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning- frequency estimation algorithms. In 7th International Conference on Learning Representations, 2019.
[24] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Non-clairvoyant scheduling with predictions. In Kunal Agrawal and Yossi Azar, editors, SPAA '21: 33rd
ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021, pages 285-294, ACM, 2021. doi: 10.1145/3409964434617777 URL https
/
3461799
[25] Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted paging with predictions. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th Interna- tional Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference). volume 168 of LiPles, pages 69: 19:1-69:11 Schloss Dagstubl- Leibniz Zeniiiz für Informatik, 2020. doi: 1044300LIPPs.1CAAPP2200000
URL
https://do:: org/ 10. 4230/LIPICs ICALP 2020. 69
[26] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Shuchi Chawla, editor, Proceedings of the 2020 ACM- SIAM Symposium Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1859-1877. SIAM, 2020. doi: 113771..781111197999999 114. URL.
attps://doo 10. 100 114
12

---

[27] Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Learnable and instance- robust predictions for online matching. flows and load balancing. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lishon, Portugal (Virtual Conference), volume 204 of I.IPlss, pages 59:1-59:17. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2021. doi: 10.4230/LIPics. 20....2..59. URL http::ttt////tt org/10 4230/ ESA 2021.59
[28] Shi Li and Jiayi Xian. Online unrelated machine load balancing with predictions revisited. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 6523-6532, PMLR, 2021. URL http:/tttpocceeeiinneee
mlr. wtwppesssvv///1222200 http////9/1///..... html
[29]
Alexander Lindermayr and Nicole Megow. Algorithms with predictions.
https://
www.etiiinnniiiiiii....... github. io/| 2022.
[30] Alexander Lindermayr and Nicole Megow. Non-clairvoyant scheduling with predictions revis-
ited. CoRR, abx/2202.00199, 2022. J.R.//tttss//arrvv.orr//aass wtw.///g/a../.....a.../// 10199
[31] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned ad- vice. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmssäässan Stockholm, Sweden, July 10- 15, 2018, pages 3302-3311, 2018.
[32] Andrés Muñoz Medina and Sergei Vassilvitskii. Revenue optimization with approximate bid predictions. In Proceedings of the 31st International Conference Neural Information Processing Systems, NIPS' 17, page 1856-1864, Red Hook. NY, USA, 2017. Curran Associates
Inc. ISBN 9781510860968
[33] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithmss with Predictions, page 646-666 662. Cambridge University Press, 2021. doi: 10.1017/9781 101/97335.1
[34] Jamie H Morgenstern and Tim Roughgarden. On the pseudo-dimension of nearly C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 136-144. Curran Associates, Inc., 2015. URL http: http://papers. nips. cappcccc/pprr/ 5766- on- tee-tthe-eeeeee pase-pseudo-- dimension of nearly-rrl-l--eaaa optimal- pdf
optimal auctions.
[35] Rajeev Motwani, Steven Phillips, and Bric Torng Nonclairvoyant scheduling. Theoretical Computer Science, 130(1):17-47119 1994.
[36] David Pollard. Convergence of stochastic processes. Springer Science & Business Media, 2012.
[37] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Advances in Neural Information Processing Systems, pages 9661-9670, 2018.
[38] Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Symposium on Discrete Algorithms (SODA), 2020.
[39] Alexander Wei and Fred Zhang. Optimal robustness coaaattees--cosssseneey trade-offs for learning- augmented online algorithms. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL pct.pppp::// neurips.c.mmm cc/ htt.:oooeee22o----bbtrttt.....a
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]
13

---

(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]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either the supplemental material or as a URL)? [Yes] See the supplementary material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to 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 (c.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to 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": "fhdGeMq5W5V", "reviewer": "Reviewer_vvHm", "summary": "The paper attempts to examine solving certain online problems using a set of $k$ predictions and examine the statistical complexity of obtaining a good algorithm that uses such $k$ predictions. These problems include min-cost perfect matching, online load balancing and non-clairvoyant scheduling for total completion time. The task is to perform as well as the best prediction.\n", "questions": "Related Work: The related work is quite comprehensive. One of the related works that I found that the authors could contrast their work vis-a-vis learnability is :\n\nAnand, Keerti, et al. \"A regression approach to learning-augmented online algorithms.\" Advances in Neural Information Processing Systems 34 (2021): 30504-30517.\n\nThis is because in this work Anand et al did not consider the computational complexity of the optimization procedure that obtains the sample error minimizer. In comparison, the authors in this paper give a technique that is a polynomial time approximation algorithm for obtaining the predictions from the sample set that are O(1) within the best predictions obtainable from ERM. \n\nLine 290: In this proof of Thm 3.4, won’t the algorithm need to look at all |S| choose k candidate solutions (and that would be exponential in $k$). The claim is that “we can find an O(1)-approximate solution which is of polynomial size in polynomial time”. What exactly in the time complexity and what is the procedure? Please clarify.\n", "limitations": "None.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The paper’s work seems to be original. Using $k$ predictions to supplement online algorithms has been explored by multiple works in the past. In this paper, it has been extended to 3 other problems. The algorithmic techniques for Section 3 and Section 4 are fairly standard and known. Exploring the learnability of using such $k$ predictions seems to be a new undertaking. The algorithm for Section 5 also seems to be new work.\n\nClarity: The non-technical part of the paper is clearly written and easy to understand. Due to paucity of time, I could not verify the technical aspects of the paper but the theorem statements “make sense” to me. I found that the authors motivated the use of multiple predictions well.\n\n\nQuality: The quality of results and writing is good. I did not check the math for the proofs in Section 5 but the algorithm seems intuitive. The paper is quite theoretical so having experiments/simulations is not warranted but would have been nice to see the proposed algorithm in Section 5 in action (even against synthetic datasets)\n\nSignificance: There is a plethora of work currently in Learning augmented algorithms. I find this work to be incremental in the field of using multiple predictions for Online Algorithms. The significance of the work is relevant since algorithms with predictions as a general field has gained so much traction in the community.\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": "W_K2i42aJO3", "reviewer": "Reviewer_Zbpu", "summary": "The paper considers using multiple machine-learned predictions to improve classic algorithm design. In particular, the work is focused on three problem: min-cost bipartite matching, online makespan minimization, and non-clairvoyant scheduling. For the first problem, the goal is to improve run-time, whereas for the last two the goal is to improve competitive ratio. \n\nIn each setting, the paper gives an efficient algorithms that makes use of multiple predictions. When (at least one of) the predictions are good, the resulting learning-augmented algorithm can achieve better performance than classic, worst-case counterparts. Moreover, the paper works out the learnability conditions, showing that good predictions can be efficiently PAC learned from data.", "questions": "For matching, I am wondering if experimentally one can find multiple predictions can help (for real world or synthetic data). Let's say $k=5$ or $10$.  In principle it may not; that is, the best single prediction (in expectation over the distribution) is generally very good for every single instance in the distribution. My intuition is that if the distribution is somewhat \"concentrated\" such that the instances generally look alike, then multiple predictions may not help. On the other hand, if the distribution has a \"multiple clusters\" structure, then having multiple predictions can provide much better coverage and therefore improve performance a lot. Is it possible to formalize this intuitions and give some theory, for matching or graph problems in general?\n\nThe recent work by Chen, Silwal, Vakilian, and Zhang [Faster fundamental graph algorithms via learned predictions, ICML 22] shows that using (single) prediction can help to improve the run-time of graph algorithms, beyond the matching problem of Dinitz et al. I think the multiple prediction can be interesting more broadly in speeding up offline graph algorithms. This is another future direction the author(s) can explore. \n\nFor online makespan minimization, can the fractional solution be rounded in an online fashion? A majority of the paper by Lattanzi et al is spent on rounding (their Section 4 and 5).  I think their techniques can be applied here. ", "limitations": "As I mentioned, the paper does not give a general framework of addressing multiple predictions in learning-based algorithms. In fact, reading its title, I expect they would. \n\nSome experiments on matching could be very interesting.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n-----\nThe paper is generally well-written, though with a few minor typos that may be confusing at times. I have listed them in a later section.\n\nThe results are novel in light of the recent literature on learning-based algorithms. In particular, this can be seen as a good follow-up on the question of algorithms with multiple predictions, recently initiated by Anand, Ge, Kumar, and Panigrahi [\"Online algorithms with multiple\npredictions\" (ICML 22)]. As the author(s) point out,  Anand et al focus only on a set of online covering problems. The results of this paper do not lie within this framework. I believe this paper is a good addition to this line of work. \n\nThe theoretic claims are correct. \n\nWeaknesses\n----\nIn my view, some of the results in this work are a bit weak on a technical level. In particular, Section 3 on matching extends Dinitz et al in a fairly trivial fashion. The main algorithm (Algorithm 1) essentially says: take the largest dual prediction and run Dinitz et al single-predictor algorithm. This should be thought as a simple observation.  On the other hand, the algorithmic result of Section 4 on scheduling relies on several key insights of Lattanzi et al (\"Online Scheduling via Learned Weights\", SODA 20).  The learnability generally follows from a pseudodimension + PAC learning argument, again from Dinitz et al. \n\nCompared with Anand et al, this paper does not provide a general framework. Rather, it addresses 3 separate problems of different nature. That is, matching is offline and the goal is to improve run-time, but the scheduling problems are online and the goal is to deal with the uncertainty.  \n \nCompared with Dinitz et al, the paper does not provide experiments.\n\nCompared with Lattanzi et al, the paper does not address rounding fractional solutions. \n\nMinor errors and missing references\n-----\nLine 11: “which prediction is [the] best”\n\nLine 104: another paper that studies non-clairvoyant scheduling in single-predictor setting is “Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms” by Wei & Zhang (NeurIPS 20)\n\nLine 249 reads a bit awkward, which is not making a definition. Maybe remove the “we say that”.\n\nLHS of Line 10 of Algorithm 2 should be $S(j, \\beta)$? I suggest the author(s) avoid overloading the notation of $A$ here.\n\nLHS of Line 10 of Algorithm 2 should be $B$ instead of $A$.\n\nLine 314: Optimal schedule, and Line 318: optimal objective value\n\nLine 423 of the supplement: I suggest the author(s) to give a standard reference for constant-approximation of k-median; e.g., “A Constant-Factor Approximation Algorithm for the k-Median Problem” (https://www.sciencedirect.com/science/article/pii/S0022000002918829)\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": "Bcuplni9mjo", "reviewer": "Reviewer_zg9d", "summary": "Considering the fact that the worst-case performance of algorithms could be improved by equipping them with good machine-learned predictions, together with the increased use of \"multiple\" machine-learned models for solving a specific task, with each of them being specialized on a part of the problem, the paper tries to adapt algorithms for the case where multiple machine-learned predictors are used instead of a single one. They try to design algorithms for this case and bound the overhead caused compared to the single predictor case (since now the best predictor should be identified among the $k$ predictors) and the error that the algorithm incurs compared to the case where it is given the best predictor only. They investigate this problem for 3 fundamental problems being bipartite matching, load balancing and clairvoyant scheduling. \n\nThey start by proving that the complexity of looking for $k$ predictions is a factor of $k$ larger than that of a single predictor. \n\nThey further move to the three specific problems. First, they consider the min-cost bipartite matching problem with multiple predictions available. They show the running time of the state of the art algorithm for solving this problem for the case of single prediction is comparable to that of considering $k$ predictions when $k\\leq O(\\sqrt{n})$ which suggests that learning with $k$ predictions is coming for free in this case.\n\nThey further consider the problem of online load balancing (where a weight vector is to be learned to distribute a task between several machines with the goal of minimizing the maximum machine load) and show that there is a polynomial time algorithm that can output $k$ weight vectors which can minimize the expected minimum error with some bounded error which comes with a logaritmic cost with respect to $k$.\n\nFinally they consider the problem of scheduling $n$ jobs on a machine when the time that each process takes for completion is not known prior to the completion of the process (clairvoyant scheduling). The goal is to minimize the sum of the completion times. They show that learning the best $k$ permutations is doable in polynomial time with bounded error compared to the best predictor.", "questions": "- How is the quality of the predictors affecting the performance of the final algorithm which takes into account all predictors? For each of the algorithms proposed, which of the following is more fabvorable? to have one very accurate and several very inaccurate predictors, or to have good performance in all predictors? Are the results also dependant on the performance of the worst predictor?\n\n- Why are there no experiments conducted? It would be nice to see whether the running times in practice also match the ones stated in the paper or see the quality of the found solution compared to the algorithm using only the best predictor. Also having multiple machines with different performances and then analyzing the performance of the algorithm would be very interesting. Another set of interesting experiment is to vary $k$. I believe one can think of many more interesting experimental setups that could support the theory.\n\n- Was there a reason for taking this 3 problems? How do you think one can generalize the result for other problems?", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper considers a very well motivated problem. \n- The paper is very carefully written.\n- I believe there will be many applications and room for future work. Generalizing the results of the paper for any $k$ predictors solving any task and then bounding the error with respect to the error of each of the predictors would be very interesting.\n\nWeaknesses:\n- The supplementary does not match the main. Supplementary is an extended version of the paper and does not include only the proofs of the Theorems or Propositions stated in the main. Some of the mismatches: Theorem 2.1 in the main is Theorem 2.3 in the supplementary, Thorem 5.4 in the main is Theorem 5.7 in the supplementary etc.\n- Section 2 is not self-contained. Without referring to the supplementary, it is almost impossible to understand what this section is trying to say or what the results are. Since most of the coming results in other sections are based on Theorem 2.1, I think it is important that enough details about this Theorem is provided in the main.\n- The writing could be improved. Sometimes it is very hard to understand what you try to convey by the wording you use. I could not understand the sentence written lines 23-25. I also could not really understand what you try to do in the paper by only reading the abstract. More clear explanations would be great.\n-Typo in line 25\n- Although all the results are proven and there is no need for experiments to show that the theory works in practice, I believe experiments are missing from the paper and one could design many interesting experimental setups to show that the theory is working in practice.", "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": "3f44Y_VXTT", "reviewer": "Reviewer_3fpq", "summary": "Over the last 10 years, a significant line of work has focused on how to augment optimization algorithms with predictions so that (a) improved performance is achieved when the predictions are accurate and (b) worst-case performance is recovered when the predictions are not accurate. In this work, the authors build on the more recent idea to augment optimization algorithms with $k$ predictions. For three canonical tasks, the authors quantify the computational cost (which they show is mostly quite small) to obtain equivalent performance to augmenting the optimization algorithm with the (unknown) best of the $k$ predictors.", "questions": "I've detailed this in the body of my review.", "limitations": "I see no negative societal impacts of this theoretical work.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is clearly written (although the supplementary material is hard to follow at first, due to interleaving theorem statements, proofs, and intuition like a textbook), and the problem well-motivated. The results are novel and the proofs all seem correct, although the technical contributions of the learning theory arguments are minimal. (For example, I believe Theorem 2.1 can be extracted from (the proofs of) more general results on compositions of VC classes. See Theorem 6.1 of https://arxiv.org/pdf/1105.4618.pdf, attributed to a 1997 textbook.) \n\nThe main limitation of the work is the incremental nature of the contribution and the utility of the results for demonstrating actual improved performance. For all three problems considered, the authors thoroughly cite how past work has considered the single predictor impact. The main contribution is improving (using the notation of Section 3, but the contribution is the same for all three problems)\n$$\n   \\min_{\\hat y} E_{(G,c)\\sim\\mathcal{D}} \\ \\lvert\\lvert y^*(G,c) - \\hat y \\rvert\\rvert_1\n$$\nto\n$$\n   \\min_{\\hat y^1,\\dots,\\hat y^k} E_{(G,c)\\sim\\mathcal{D}} \\min_{\\ell\\in[k]} \\  \\lvert \\lvert y^*(G,c) - \\hat y^\\ell \\rvert\\rvert_1.\n$$\nObviously the second term is no larger than the first term. However, since there is a (sometimes small, but not zero) addition to computational complexity in order to achieve the second term, I think the main quantity of interest is *how much* smaller the second term gets. This should depend on the problem parameters, $k$, and some properties of $\\mathcal{D}$ (e.g., how symmetric it is?). This will provide an answer to the question: is the improvement in performance worth the computational cost of considering $k$ predictors over a single predictor?\n\nI do not mean to penalize the authors for their useful characterization of the existing literature, and hence I rate the paper as borderline. If the authors can quantify exactly how much better using $k$ predictors can be in terms of the relevant parameters for the three problems of interest, this would be sufficient to improve my rating to an accept. \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": {}}]

Author rebuttal:

Decision: Accept