Learning-Augmented Algorithms with Explicit Predictors
Authors: Marek Elias
Haim Kaplan
Yishay Mansour
Shay Moran
Venue: NeurIPS 2024 poster (2024)
Keywords: online algorithms
learning-augmented algorithms
scheduling
caching
Primary area: learning_theory

Abstract: Recent advances in algorithmic design show how to utilize predictions obtained by machine learning models from past and present data. These approaches have demonstrated an enhancement in performance when the predictions are accurate, while also ensuring robustness by providing worst-case guarantees when predictions fail. In this paper we focus on online problems; prior research in this context was focused on a paradigm where the algorithms are oblivious of the predictors' design, treating them as a black box. In contrast, in this work,
we unpack the predictor and integrate the learning problem it gives rise for within the algorithmic challenge. In particular we allow the predictor  to learn as it receives larger parts of the input, with the ultimate goal of designing online learning algorithms specifically tailored for the algorithmic task at hand. Adopting this perspective, we focus on a number of fundamental problems, including caching and scheduling, which have been well-studied in the black-box setting. For each of the problems, we introduce new algorithms that take advantage of explicit and carefully designed learning rules. These pairings of online algorithms with corresponding learning rules yields improvements in the overall performance in comparison with previous work.

Learning-Augmented Algorithms with Explicit Predictors
Marek Eliáš Bocconi University, Milan
Haim Kaplan Tel Aviv University Google Research
Yishay Mansour Tel Aviv University Google Research
Shay Moran
Department of Mathematics, Technion Department Computer Science, Technion Department of Data and Decision Sciences, Technion Google Research.
Abstract
Recent advances in algorithmic design show how to utilize predictions obtained by machine learning models from past and present data. These approaches have demonstrated
enhancement in performance when the predictions accurate, while also ensuring robustness by providing worst-case guarantees when predictions fail. In this paper focus online problems; prior research in this context was focused on a paradigm where the algorithms are oblivious of the predictors' design, treating them as a black box. In contrast, in this work, we unpack the predictor and integrate the learning problem it gives rise for within the algorithmic challenge. In particular we allow the predictor learn as it receives larger parts of the input, with the ultimate goal of designing online learning algorithms specifically tailored for the algorithmic task hand. Adopting this perspective, we focus on number of fundamental problems, including caching and scheduling, which have been well-studied in the black-box setting. For each of the problems, we introduce new algorithms that take advantage of explicit and carefully designed learning rules. These pairings online algorithms with corresponding learning rules yields improvements in the overall performance in comparison with previous work.
Introduction
We study online algorithmic problems within the realm of leareing-augmented algorithms. A dearning-augmenter algorithm possesses the capability work conjunction with an oracle that supplies predictive information regarding the data it is expected to process. This innovative approach has been discussed landmark studies by Kraska et al. [2018) and Lykouris and Vassilvitskil [021]] J, situating it neatly within the "beyond worst-case analysis framework [Roughgarden, [2020] chap. 30].
In this framework, studies typically define predictions specifically tailored to the problem hand, which could presumably be learnt from historical data. Predictions might include, for instance, the anticipated next request time for a page caching problem or the expected duration of a job in scheduling task. These predictions are accessible either before or together with the online requests, allowing the algorithm utilize them for performance enhancement (measured by competitive ratio or regret). The objective is for the algorithm's performance to gracefully decrease as prediction accuracy declines, ensuring never underperforms the baseline achievable without predictions.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Despite the elegance of these results, several important aspects were neglected: the ad- ad-hoc nature of the predictions, the lack of standardized quality measures, and the frequently overlooked prediction generation methods and their relation to the algorithmic process. We believe that addressing these aspects is likely to yield substantial improvements.
Consider week-day and festive traffic patterns in a city - a simple example of a setting with two typical inputs requiring very different predictive and algorithmic strategies. Achieving good performance in such setting requires a learning component in the algorithm which discerns between the festive and week-day imput instances and suggests an appropriate routing strategy. Such learning components are already present (explicitly or implicitly) in works on combining algorithms in a black- box manner [Dinitz et al., [022] Emek et al., 2021 Anand et al.] [2022] Antoniadis et al., 2023). where switch between algorithms is made after incurring high cost.
Our approach goes one step further. It is based making the computation of the predictions an integral part of the algorithmic task at hand. We do this by making all the data (historical and current) directly available to the online algorithm (rather than summarizing it into ad-hoc predictions). This gives the algorithm two important abilities. The first ability is to learn the input instance based on its prefix (the shorter the better) and adapt the algorithmic strategy before incurring significant cost. E.g., in the example above, week-day and festive traffic patterns can be easily discerned already in early morning when the traffic is low and possibly suboptimal routing decisions have negligible impact on the overall cost. The second ability is to identify actions which are beneficial for many plausible input instances simultaneously but are not suggested by any of the black-box predictors. We use both abilities in design of our algorithms.
In more detail, we model the past data through the assumption that the algorithm is equipped with prior knowledge comprising set of descriptions of past input instances. Each description offers specific statisties or characteristics that represent essential information of the input instance. Borrowing terminology from learning theory, we call this set a hypothesis class and denote it by H. More specifically, H is set of hypotheses, where each hypothesis. h()), consists of information regarding a specific possible input instance I of the algorithmic task.
In the simplest setting each hypothesis could be the input instance itself (h(I) = I). Like the sequence of pages to arrive in a caching instance, or a set of jobs to arrive in a scheduling instance. In other situations, an hypothesis h could be a more compact summary of the instance I, such as the distribution of the arriving jobs (what fraction are of each "type"). ). In such case, many past input instances will correspond the same hypothesis and the size of H will be much smaller than the size of the dataset of past instances. However, in all cases that we consider, each hypothesis h(()) provides sufficient information about the instance in order determine an offline optimal solution OPT(T).
We distinguish between realizable and agnostic settings. In the realizable setting, we make the assumption that the actual input instance that the online algorithm has to serve. perfectly aligns with one of the hypotheses in H. That is, if I is the real input, then hI) E H. In the agnostic setting we remove this assumption and consider arbitrary inputs. Our goal is to deliver performance guarantees that improve if the actual input is "close" (defined in a suitable manner) to the hypothesis class H. Agnostic setting with [P[] = 1 captures the (usual) setting of ML-augmented algorithms with single black-box predictor. The realizable case is interesting mostly from a theoretical perspective as a very special case of the agnostic setting. Its simplicity makes it a logical starting point of a study If the current instance does not match any hypothesis perfectly (in the realizable setting) or is far from H (in the agnostic setting), we can still achieve good performance using robustification techniques, see e.g. [Wei] 2020 Antoniadis et al., 2023] Lattanzi et al. 2020 Lindermayr and Megow 2022).
Our methodology is to split the algorithm into two parts. One (called predictor) produces predictions based on the provided hypothesis class (70 and the part of the input seen so far. Its goal is to produce the best prediction for the instance hand which could be hypothesis from H or some other suitable instance designed based on H. The second part is the online algorithm itself. It uses the prediction of the first part to serve the input instance with low cost. In particular, it can compute the offline optimal solution for the prediction and serve the input instance according to this solution.
The predictor is the learning component of our algorithm. It solves learning task which is associated with the algorithmic problem at hand. For example, the learning task associated with caching is
Boosting technique, which had great impact on applied and practical machine learning, was developed while studying relationship between weak and strong PAC learning in the realizable setting.
2

---

caching
load balancing
non-clairvoyant scheduling
realizable
OPT+
Olog E) OPT
OPT+
agnostic
OPT+0(# + log E)
Olog E) ALG
OPT+p" + O(n log E) (1+c) OPT )0(1/e))²
previous works
OPT+0(p + k +++ TT
Thh log
(log () ALG"
Emek et al. 2021
Dinitz et al. 2022]
Dinitz et al. 2022)
Figure 1: Summary of our results. Notation: & = [H]; i and T: cache size and instance length respectively in caching; m: the number of machines in load balancing; n: the number of jobs in non-clairvoyant scheduling; μ²: distance of the input from the hypothesis class in caching and non-clairvoyant scheduling; ALG": cost of the best algorithmic strategy suggested by H.
variant of online learning with two kinds of costs: the smaller cost is due to a misprediction of an individual request and the larger one due to switching to a different predicted sequence. The costs are chosen to reflect the impact of the two events the overall performance of the algorithm.
We consider this new way to model setting of "online algorithm with predictions" one of our core contributions (in addition to the algorithms for the specific problems that we describe below). In a sense, our technique interpolates an interesting way between the learning challenge (from historical data) and the algorithmic challenge, while addressing both of them.
1.1 Performance bounds of our algorithms
We propose algorithms (within our framework) for three fundamental online algorithmic problems: caching, load balancing, and non-clairvoyant scheduling. For caching and non-clairvoyant scheduling. we achieve a (small) additive regret compared to the offiin optimal solution instead of a multiplicative competitive ratio. For load balancing, achieve competitive ratio with logarithmic dependence the size of the hypothesis class. Our results are summarized in Figure T. while the full description is deferred to Section 2
We focus our presentation on the basic framework with performance bounds dependent on the size of the hypothesis class H. We assume H to be restricted in the sense that not every instance / is close to some hypothesis in H. This ensures that there some structure the input instances which can be learnt. With an unrestricted H. every input would be possible and we would be in the classical online setting. However, our modular approach allows replacing the learning component in order to achieve additional desirable properties. This includes fast running time, better performance with clusterable datasets (see Dinitz et al. 20222). D. and better performance on instances composed several parts, each resembling a different hypothesis (see [Anand al. 2022 Antoniadis al. 2023
Recent works by Dinitz et al. [2022] and Fndek et al.] [202]] consider algorithms with access to a portfolio of predictors trying achieve performance comparable to the best one. Our results can be interpreted in their setting by considering the output of each predictor the portfolio as a hypothesis. We achieve comparable and sometimes better results (see Figure for comparison) using arguably simpler approach, separating the learning and algorithmic part and solving them separately.
Organization. Section describes describes our main contributions including the description of the problems studied and the approach which leads followed by a warm-up in Section containing an exposition of our approach on caching in realizable setting. The main technical part of our paper is in Appendix. Appendix considers the load balancing problem and Appendix the non-clairvoyant scheduling problem. We conclude our paper with treatment of caching agnostic setting in Appendix D
results. The survey of the related literature in Section
2
Main Results
Our study focuses on three fundamental online algorithmic problems: caching, load balancing, and non-clairvoyant scheduling. For each of these problems, we define learning tasks and devise explicit and efficient predictors for solving them. We demonstrate how these predictors can be integrated into algorithms designed to tackle the respective online problems. A key feature of our approach is the
3

---

modular separation of the learning and algorithmic components. By decoupling these aspects, we develop simpler algorithms that often yield improved bounds compared to previous works in the field.
2.1
Caching
In the caching problem, the input is a sequence of page requests. The online algorithm holds a cache of size k. and must ensure that the currently requested page is always available in the cache. If the requested page is absent from the cache, a page fault occurs, prompting the page to be loaded into the cache. If the cache is already full, another page must be evicted to make room. The ultimate objective is to minimize the number of page faults.
In the offiin scenario, where the input sequence is known ahead of time, an optimal algorithm adheres to the intuitive policy of removing a page that will not be requested again for the longest time. This algorithm, known as Furthest in the Future (FitF) [Belady 1966], achieves the minimum possible number of page faults.
The Learning Task: "Sequence Prediction with Switching Cost"
In this context we consider a variant of the classical learning task of sequence prediction that includes a switching cost. More precisely, the objective of the predictor is to predict the sequence of page requests denoted by r1, "2, rT. In each round t, the predictor presents a prediction for all remaining requests in the sequence Te, Te+l: ...., TT. At the conclusion of the round, the predictor sees and incurs a loss of 1 [T+ * r²] if the prediction was incorrect. After observing rts the predictor can choose to alter the subsequent predictions to T'+1:-.. .... TTy. Each time the predictor decides to modify the predictions, switching cost of incurred (remember that 2 represents the size of the cache). Thus, the total loss of the predictor is equal to the number of prediction errors plus k times the number of switches.
Hypotheses. Each hypothesis in our class H is a possible input sequence. In the realizable scenario, we operate under the assumption that the actual input matches one of the hypotheses within the class. In the agnostic case we relax this assumption and provide guarantees that scale with the Hamming distance between the input sequence and the hypothesis class.
In the realizable case we design a deterministic predictor whose total loss is at most & log (recall that e= (7(). It is based on majority vote or the halving algorithm [Littlestone] 1987]. An interesting and subtle point is that our predictor is improper, meaning it occasionally predicts the remaining sequence of page requests in a manner that does not align with any of the hypotheses in H. To incorporate such improper predictors, we need to use an optimal offline caching algorithm that is monotone in the following sense: applying the algorithm on input sequence ri,-... .....,PT PT produces caching policy which is simultaneously optimal for all prefixes Ti,.... Fr for < T. Fortunately, Belady's s FitF algorithm has this property, as outlined in Observation [
For the agnostic setting, we design a randomized predictor with a maximum total loss of O( k In f). where n² is the Hamming distance of the actual input sequence from the class H. This predictor utilizes a multiplicative-weige rate is specifically adapted to achieve the optimal balance between the cost of changing predictions (switching costs) and the inaccuracics in the predictions themselves (prediction errors).
rule [Littlestone and Warmuth, 1994), and its learning
Our final caching algorithm incorporates a predictor for this problem in such way that at each round t, it applies Belady's 's FitF algorithm to the predicted suffix of the sequence Tt. Tr. We then show that the cumulative loss of the predictor serves as an upper bound on the additional number of page faults that our algorithm experiences compared to the offline optimal algorithm. Overall we obtain the following guarantees for our caching strategy:
Theorem 1 (Caching). Let H be hypothesis class of size E and be an input instance with offline optimum value OPT There is a deterministic algorithm for the realizable setting (i.e., I I H) which has cost at most OPT( + k llog& f. There is randomized algorithm for the agnostic setting with expected cost at most OPT([) + (5+ 6/k)μ* + (2k + +1) In where μt the Hamming distance between I and the best hypothesis in H.
Our algorithms can be robustified, i.e., we can ensure that their cost is not larger than Ollog k) OPT(I) while loosing only constant factor in the dependency μ¹' and In l in our

---

additive regret bound, see Section D.1 for details. Note that the previous methods used to achieve robustness for eaching usually lose an additive term linear in OPT( see [Wei] 2020 Blum and Burch 2000, Antoniadis et al. 2023 In Section D.2 we describe how to extend our results to the setting where each hypothesis, instead of complete instance, is set of parameters of some prediction model producing next-arrival predictions. In Section[D. we show that the dependency on E, k, and μ² in Theorem [ cannot be improved by more than a constant factor. Our result is an improvement over the Ol" + k + ITk () regret bound of Emek et al. [2021] whenever (k log e).
2.2 Load Balancing
In online load balancing on unrelated machines, we have machines numbered from 1 to and a total of n jobs. The jobs arrive sequentially, and the objective to assign each job to one of the machines upon its arrival in order to minimize the makespan, which is the total time that the busiest machine is actively working. Each job is characterized by its type, which is an m-dimeenionnll vector The value p(i) indicates the time required for the i-th machine to complete the job. As the jobs arrive, the algorithm observes the job's type and makes a decision on which of the m machines to schedule it. These scheduling decisions are made in online manner, without knowledge of future jobs.
In the offline setting, the ordering of the jobs in the input sequence does not play any role. In fact, an instance of load balancing sufficiently deseribed by the number of jobs of each type which need to be scheduled and these numbers are available to the algorithm in advance. A 2-approximation algorithm by Lenstra, Shmoys, and Tardos [1990] based on linear programming achieves makespan that is at most twice the makespan of the optimal schedule.
The Learning Task: Forecasting Demand
The learning problem that arises in this context of makespan minimization a rather natural one and might be interesting in other contexts. The goal of the predictor is to forecast, for each possible job type p, the number of jobs of type that are expected to arrive. The predictor maintains a prediction that includes an upper bound, denoted as 'lp, on the number of jobs of each possible job type p. Similar to caching. the learning problem involves two distinct costs: prediction errors and switching costs. A prediction eπтоr occurs when the actual number of jobs of particular type exceeds the predicted upper bound mp. The cost of a prediction error is determined by the type of the job that witnessed it. A switching cost occurs when the predictor decides to modify its prediction (i.e., the predicted upper bounds ny 's). The cost of such a modification is the makespan associated with the new prediction
Hypotheses. In load balancing each hypothesis f in our class H. predicts the frequency of the jobs of each type p. That is, for each type it assigns number fp E [o, 1] which represents the fraction of jobs in the input whose type is p. We stress that the hypothesis does not predict the actual number of jobs of each type, nor does it even predict the total number of jobs in the input. In practice, the numbers Sp can be estimated by past statistics. With the knowledge of the correct hypothesis f, we integral assignment of jobs to machines at low cost. Previously studied
able to produce machine-weight predictions [[attanzi et al. 2020) allow producing a fractional assignment which requires costly rounding procedure [L and Xian 2021].
In the realizable scenario, we operate under the assumption that the actual input matches one of the hypotheses within the class. In the agnostic case we relax this assumption and provide guarantees that scale with the maximum (multiplicative) approximation error between the true frequencies and those predicted by the best hypothesis (see below).
In the realizable case, we design simple randomized predictor. ensuring that the total expected loss is at most (OPPT() log E) (recall that = (H), where OPT(() represents the makespan of the input instance 7 The key idea to guess the total number of jobs in the input sequence and accordingly to scale the frequencies in each hypothesis to predict the number of jobs np of each
Note that the offline optimal makespan does not depend on the order of the jobs, it only depends on the number of jobs of each type, and hence, it is a function of the predicted numbers n, for the types p.
We refer the makespan of the optimal schedule for an instance the makespan of the instance.
5

---

later time, Round-Robin algorithm is type. The randomized predictor maintains a random hypothesis consistent with the processed jobs. Whenever one of the predicted counts "p is violated, the predictor switches randomly chosen consistent hypothesis from H. resembling the classical randomized marking strategy in caching (Fiat jtt al. 199T].
We additionally present a deterministic predictor with loss of at most O(OPT()) log([?)) log T), where T is the number of job types with non-zero frequency in at least one of the hypotheses. The deterministic rule predicts the median among the counts "p provided by the hypotheses for each job type/ p. The analysis of this deterministic learning rule is more intricate than that of the randomized one. The crucial insight is that the produced "medians" prediction can be scheduled within makespan at most O(OPT(I) log r). Our predictors in the agnostic setting are based on those in the realizable case.
Our scheduling algorithm incorporates a predictor for this problem in such a way that at each round t, it behaves in accordance with the algorithm of Lenstra et al. (1990), applied to the predicted upper bounds n2,'s ss We demonstrate that the cumulative loss of the predictor serves as an upper bound on the makespan. We obtain the following result:
Theorem 2 (Load balancing). There are algorithms using deterministic and randomized predictor respectively which, given a hypothesis class H of size and an instance I with makespan (PT(T), satisfy the following. In the realizable setling (i.e., h([)) E H. where h(()) is the distribution corresponding to I). they produce a schedule whose makespan is at most O(log E loo T OPT(I)) and (log E (P)(1)) in expectation, respectively, where is the number of job types with non-zero frequency in at least one of the hypotheses. In the agnostic case they produce a schedule with makespan most aa log flog T (P)(()) and (a log É (OPT(!)) in expectation, respectively, where a and B describe the multiplicative error of the best hypothesis f E H.
In agnostic case, the multiplicative error of hypothesis f with respect to an instance with frequencies f is defined as follows. If there is job type p such that fp * 0 and fØ 0, we define := 1, where n denotes the number of jobs in the input instance. Otherwise,
max fp fp fo * 0}. Similarly, if there is job type such that fp 0 and f * O, we define 3 Otherwise, 3 == max mfx S5p S2 + 0}. We have a; 3 S n 1.
define
1.
Our algorithms can be robustified so that their competitive ratiq" is never larger than Olog m) (the best possible competitive ratio in the worst-case setting [Azar et al. 1992]. D. while loosing only a constant factor in the bounds mentioned in Theorem 2 see Section B.5 In Section B.7 we show
that our competitive ratio in the realizable case cannot be improved by more than a constant factor.
Previous works focused on predictions assigning weight to each machine which indicates its expected load Lattanzi et al. 2020), and acquiring a solution for the fractional variant of the problem. [Diiitz] et al. 2022 showed how to aggregate outputs of l algorithms into a single fractional solution, loosing a factor of Olog E) compared to the best of the algorithms. A fractional solution can be rounded log logm online, loosing a factor of O log log log m in the competitive ratio Lattanzi et al. 2020 Li and Xian 2021]. Instead, we use job-type frequencies which allow us to produce an integral solution directly without the costly rounding procedure. However, our approach can be used to aggregate outputs of any E algorithms, preserving integrality of their solutions, see Section B.6
2.3 Non-clairvoyant Scheduling
We consider a clairvoyytt scheduling problem in which a single machine is assigned the task of completing a set of n jobs, denoted as ja..a...... Jn. The jobs are released at time 0 and the scheduler's objective is determine the order in which they should be scheduled such that the sum of their completion times is minimized.
The optimal ordering is obtained by sorting the jobs in ascending order of their processing times. However, in the non-clairvoyant setting, the scheduler does not know these processing times. To address this challenge, the scheduler is allowed preempt job before is completed, meaning that it can interrupt the ongoing execution of a job and replace it with another job. The remaining portion of the preempted job then rescheduled for completion
'The maximum ratio between the cost of the algorithm and the offline optimal solution over all instances.

---

2-competitive and this is the best competitive ratio achievable in claicvavvy setting in the worst case [Motwani al. 1993].
The Learning Task: Comparing Job Durations
In the learning task explored within this context, the objective is for the predictor to learn the optimal ordering of jobs. We investigate two variants of this learning problem, one suited to the realizable setting and one suited to the agnostic setting.
In the realizable case, adopt a similar approach the previous sections. Here, each hypothesis within the class provides predictions for the processing times of all n jobs. We then design a predictor that learns the correct hypothesis in an online fashion. Our overall scheduling algorithm in the realizable case operates by always scheduling first the job with the shortest predicted processing time.
In the agnostic setting we follow different methodology which is more in line with statistical learning. We use here a weaker type of hypotheses: each hypothesis is permutation of the n jobs, indicating a prediction of the optimal ordering, without specifying the exact processing times.
In this learning task, the predictor is provided with a training set consisting of a small subset of the jobs that is sampled uniformly. For each job in the training set the predictor sees their lengths. Using this training set, the predictor generates a permutation IT of the 72 jobs.
Each permutation æ is associated with a loss I follows the order suggested by æ. In particular, the loss is defined in such way that the optimal permutation has the best (lowest) loss, and more generally permutations with faster completion times have smaller losses. The predictor we design for this task uses the training set to approximate the loss of every permutation in the class H. and outputs the one which minimizes the (approximated) loss.
which reflects the performance of a scheduler that
In order to avoid scaling issues, we formulate our guarantees for instances with maximum job length at most
Theorem 3 (Completion Time). Consider an input instance I, les OPT(T) denote the offline optimal value of its total completion time objective, and let H. be a hypothesis class of size f. We assume, without loss of generality, that the maximum job length in 1 is at most 1. Then, there is a deterministic algorithm which achieves total completion time at most OPT(T) + + +
in the realizable setting (i.e., I E H.). In the agnostic setting. there is randomized algorithm that with high probability achieves total completion time of at most (PT + (nn5/3 log f), where μ² is the difference between the total completion time of the best hypothesis in the class and OPT.
Note that the value of OPT(() is quadratic in n unless the size of a vast majority jobs in I is either O or vanishing as n grows.
We have also found unexpected separation: there is an algorithm for the realizable setting with regret at most n log l on input instances containing jobs of only two distinct lengths (Section C.I). On the other hand, there is no algorithm with regret off) on instances with at least three distinct lengths (Section C.3).
Previous work by Dinitz. et al. 2022 showed the following. For any >> O, there is an algorithm which achieves expected total completion time (1 + <) +0(1e" under certain assumptions about the input. Therefore, their bound always gives a regret linear in OPT and higher dependency μ("
Any algorithms can be robustified by running it speed (1-6) 6) simultaneously with the Round Robin algorithm at speed 8. This way, we get
algorithm in the worst case, because the schedule produced by Round Robin is 2-competitive with respect to the optimal schedule processed at speed 8. Dinitz et al. (022) used the same approach to robustify their algorithm, incurring the factor
FFrrmall, the loss of permutation is the expected value of the following random variable: sample pair of jobs uniformly at random; if the ordering of the jobs in places the longer job before the shorter one, output the difference between their respective lengths. Conversely, if the ordering in н does not violate the length ordering, output zero. Notice that the optimal permutation has 0 loss and moreover expected loss of any permutation и is proportional to the regret, that is, to the difference between the objective achieved by and the achieved by the optimal permutation, shown by Lindermayr and Megow 2022
'If a solution for instance / has total completion time objective OPT(2) R. then the same solution on a scaled instance I' obtained from / by multiplying all job lengths by a has objective (OOPT())) + R) OPT((') + aR.
7

---

I-8 on top of their bound quoted above. This procedure unfortunately worsens the performance of the original algorithm by constant factor, i... such robustification of our algorithm achieves additive regret only with respect to T-O OPT(I).
1
3 Related Work
The closest works to ours are by Dinitz et al. [202] and Emek et al. 22021 Dinitz et al. [002] design algorithms with access to multiple predictors. They study (offline) min-cost bipartite matching, non-clairvoyant scheduling, and online load balancing on unrelated machines 7 The main difference from our approach is conceptual: while we treat the task of identifying the best prediction as an independent modular learning problem. they treat it as an integral part of their algorithms. In the case of load balancing, they propose an (log -ccomeetiiive algorithm which combines solutions of & prediction-base algorithms into a fractional solution. A fractional solution can be rounded online, log log m
incurring an additional multiplicative factor of O log log log where m is the number of machines, see Lattanzi et al., 2020 Li and Xian 2021]. For non-clairvoyant scheduling for minimizing total completion time, they propose an algorithm which works under the assumption that no set of at most log log n jobs has large contribution to OPT. Their algorithm achieves a total completion time of (1+c) OPT+0(( ++(c=))pp ")²² for any > O, where μ denotes the difference between the cost of the best available prediction and the cost of the offline optimum.
Emek et al. [022 study caching with l predictors which predict either the whole instance, or the next arrival time of the currently requested page. Based on each prediction, they build an algorithm with performance depending on the number of mistakes in this prediction. Then, they combine the resulting e algorithms using the technique of Blum and Burch [2000) to build a single algorithm with a performance comparable to the best of them. Note that our approach is in a sense opposite to theirs: we use online learning techniques to build single predictor comparable to the best of the given & predictions and then we use this predictor in a simple algorithm. Their algorithm has a regret bound of O(μ² + k- + vTk log E), where T is the length of the sequence, k is the size of the cache, and μ² either the hamming distance of the actual input sequence from the closest predicted sequence or the number of mispredicted next arrival times in the output of the best predictor. This bound is larger than ours unless T is very small, e.g., olk log e).
There are numerous works on data-driven algorithm design, see the survey (Balcan 2021]. They consider (potentially infinite) hypothesis classes containing parametrizations of various algorithms and utilize learning techniques to identify the best hypothesis given its performance on past data. The main difference from our work that the hypothesis is chosen during the analysis of past data and before receiving the current input instance. In our case, learning happens as we receive larger and larger parts of the current input instance.
There are papers that consider our problems in a setting with a single black-box predictor which corresponds to our agnostic setting with hypothesis class of size 1. For caching. these are [Lykouris] and Vissklvitskiij 2 Rohatgi 2020) Weil (2000] (Antoniadis et al., 2023). For online load balancing on unrelated machines and its special case restricted assignment, there are works on algorithms using
predicted weights [Lattanzi et al. 2020 Li and Xian 2021]. The papers [Purohit et al. 2018 8 Wei and
Zhang 2020 Im al.] 2021 Lindermayr and Megow| 2022 address the problem of non-clairvoyant
scheduling.
Other related papers are by Bhaskara et al. (2020) who studied online linear optimization with several predictions, and [nnad ct al. 2022] Antoniadis et al. 2023) who designed algorithms competitive with respect dynamic combination of several predictors for online covering and the MTS problem, respectively. There are also works on selecting the single best prediction for a series of input instances online (Khodak al.) 2 and offline [Balcan et al., (022). The main difference from our work is that they learn the prediction before sol solving the input instance while we learn the prediction adaptively as we gain more information about the input instance.
TThey state their result for a special case called restricted assignment, because no ML-augmented algorithms for unrelated machines were known at that time. However, they mention in the paper that their approach works also for unrelated machines.
8

---

Other relevant works are on various problems in online learning which consider switching costs [Cesa- Bianchi al., 2013 Altschuler and Talwar 2018 and on online smoothed optimization [Goel
et al.]
2019 Zhang et al., 202 Chen et al. 2018
Since the seminal papers of Lykouris and Vassilvitskii 2021 and Kraska al. 20118) many works on ML-augmented algorithms appeared. There are by now so many of these works that is not possible to survey all of them here. Instead, we refer to the survey of Mitzenmacher and Vassilvitskii 2020
and to the website maintained by Lindermayr and Megow
2023
Caching in offline setting was studied by Belady [1966]. Sleator and Tarjan 1985 laying the
foundations of online algorithms and competitive analysis, showed that the best competitive ratio achievable by deterministic caching online algorithm is k. Fiat et al. [1991] proved that the competitive ratio of randomized caching algorithms is (log k). Non-clairvoyant scheduling with the total completion time objective was studied by Motwani et al. [1993] who showed that Round- Robin algorithm 2-competitive and that this is the best possible competitive ratio. |Azar et al. 1992] proposed an (log m) competitive algorithm for online load balancing on unrelated machines and showed that this is the best possible. In the offline setting, [enstra et al. [1990) proposed a 2-approximation algorithm and this remains the best known algorithm. There was recent progress on special cases [Svensson 2012 Jansen and Rohwedder 2017
4 Warm-up: Caching in the Realizable Setting
In this section, we describe the simplest use case of our approach and that is caching in the realizable setting. In caching, have universe of pages U, a cache of size k and its initial content xp (2) As it is usual, we assume that U contains k "blank" pages by...., b,, which are never requested
and xa (bl..... by). i.e., we start with an empty cache. We receive a sequence of requests Ti....,, PT E U (bl..... ] online. At each time step f, we need to ensure that Te is present in the cache, i.e., our cache E (k) contains If r. & zz-1 we say that there is a page fault and we choose x, (4) such that r. Zt. This choice needs be made without the knowledge of the future requests.
We measure the cost of solution to caching instance by counting the number of page loads (or, equivalently, page evictions) performed when transitioning from xt-1 to 22 at each time t = 1...., T. Denoting d( xie) (ar. \ x2-1/ the total cost of the solution .1,... FT is
cost(x)= = Σ 1=1
21).
Offline algorithm FitF. An intuitive offline optimal algorithm FitF was proposed by Belady 1966]: there page fault at time I, it evicts a page from xt-1 which requested furthest in the future (FitF). In case there are pages which will never be requested again, it breaks the ties arbitrarily. The following monotonicity property will be useful in our analysis.
Observation 4. Consider a request sequence Ti..... TT. For any < T, the cost incurred until time t by FitF algorithm for sequence Ti...., FT is the same as the cost incurred by FitF algorithm for sequence fi,...,'t
To see why this observation holds, it is enough notice that the solution produced by FitF on fi...., .T until time i is the same as the solution of FitF on .7 which breaks ties according to the arrival times in It+
Learning task. In the realizable setting, we are given a class H of hypotheses r' ...., E U such that the actual input sequence of requests is one of them (but we do not know which one). We split the task of designing an algorithm for this setting into two parts. First, we design an (improper) predictor that maintains predicted sequence of switches (changes to π) until it determines the correct hypothesis. Second, we design an algorithm which uses access to such predictor and its performance depends on the number of switches made by the predictor.
#1...., Tr. This predictor makes small number
Predictor. Our Predictor I below is based on majority rule, maintains a set A of all hypotheses (sequences) in the class H. which are consistent with the past requests. In time 1 the set A is

---

initialized to be the entire class, i.e. A = H. and it is updated whenever the current request ry differs from the predicted request Re (i.e., when there prediction error). The prediction used by our predictor is defined based on the set A as follows: We set := and, for T 1 1,.... T, we choose 3 to be the request agreeing with the largest number of hypotheses predicted sequence is modified exactly after time-steps & when # rg. and whenever this happens at least half the hypotheses in A are removed. Observe that we assume the realizable setting and hence at all times A contains the hypothesis which is consistent with the input sequence. In particular is never empty. This implies the following lemma:
A. This way, the
Lemma 5. In realizable setting, Predictor with a class H of hypotheses makes S log& switches and the final prediction consistent with the whole input.
Predictor 1: Majority predictor for caching in realizable setting
for t 1....,2 T do
if't prediction т. differs from the real request Ti then // make switch
A = {i {l....,{} {} r² = VT = l....t;: update Ti and arg maXpeu lit E A r p}l for each = =t+l.....
// consistent hypotheses
Algorithm. Our overall algorithm (See Algorithm 2 uses Predictor | and maintains the FitF solution ø1, #1..... FT (i) for the current prediction time t. Then it changes the cache to 2t. This solution needs to be recomputed whenever is modified.
Algorithm 2: caching, realizable setting
for 1 1...., do there a switch then receive from the predictor;
compute FitF solution 21,..., TT for T.;
move Zt-
Lemma 6. Consider input sequence and let OPT(r) denote the cost of the optimal offline solution for this sequence. Algorithu 2 with a predictor which makes a switches and its final prediction consistent with incurs cost most
OPT(r) ka.
Proof of Lemma can be found in Appendix A
Combining lemmas (and we get algorithm for
caching a realizable setting with the following guarantee.
Theorem 7. There is algorithm for caching in realizable setting which, given class H. of E hypotheses, achieves regret at most log
Conclusions
We introduce a new approach to modeling algorithms with predictions. Unlike the traditional black- box access to a predictor, we extend the algorithmic problem by studying the accompanying learning problem. This allows the algorithm designer to improve the algorithm by:
1. Learning while processing the input,
2. Classifying the input instance to select the most suitable strategy before incurring high costs,
3. Accelerating the classification of the input by taking actions that may not be directly aligned with any strategy suggested by past data.
To achieve this, we split the computational problem into learning component and an algorithmic component, addressing each separately. By applying our algorithms to existing settings with prediction portfolios [Dinitz et al. 2022 Emme et al. 202T], we demonstrate that our approach often results in simpler algorithms with improved performance compared to previous methods.
10

---

Acknowledgements
Haim Kaplan is supported by Israel Science Foundation (ISF) grants 1595/19 and 1156/23, and by the Blavatnik Research Foundation.
Yishay Mansour has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation, the Yandex Initiative for Machine Learning at Tel Aviv University and grant from the Tel Aviv University Center for AI and Data Science (TAD).
Shay Moran is Robert J. Shillman Fellow; he acknowledges support by ISF grant 1225/20, by BSF grant 2018385, by an Azrieli Faculty Fellowship, by Israel PBC-VATATS by the Technion Center for Machine Learning and Intelligent Systems (MIIS), and by the the European Union (ERC, GENERALIZATION, 101039692). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
References
[1] Altschuler and K. Talwar. Online learning over a finite action set with limited switching. In S. Bubeck, V. Perchet, and P. Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 1569-1573, PMLR, 06-09 Jul 2018. URL htLLhttss///prrceedinng
mlr ptw.s/ http:////ww/aaatssslleeeeeeeee 18a html
[2] K. Anand, R. Ge, A. Kumar, and D. Panigrahi. Online algorithms with multiple predictions. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 582-598. PMLR, 2022.
[3] A. Antoniadis, C. Coester, M. Eliáš, A. Polak, and B. Simon. Online metric algorithms with untrusted predictions. ACM Trans. Algorithms, 19(2). apr 2023. ISSN 1549-6325. doi: 10.1 15/3558888,6,, URL/httss: //doi. org/ 10. 1114//352255
[4] A. Antoniadis, C. Coester, M. Eliás, A. Polak, and B. Simon. Mixing predictions for online metric algorithms. Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 969-983. PMLR, 2023.
[5] Y. Azar, J. Naor, and R. Rom. The competitiveness of on-line assignments. J. Algorithms, 18: 221-237, 1992.
[6] M.-F. Balcan. Data-Driven Algorithm Design, page 626-645. Cambridge University Press, 2021. doi:
[7] M.-F. Balcan, T. Sandholm, and E. Vitercik. Generalization in portfolio-based algorithm selection. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14):12225 12232. 122222 May 2021. doi: 10.1660//aai..355i// v35i14.17451. bttpssts:///os waai. www//orgg..ii..ooo.oooooeegeeeee index. php/A
AAI/articla http///rtceleeveee//eeeee 17451
[8] L. A. Belady. A study of replacement algorithms for virtual-storage computr, 1BM Syst. J., 5 (2):781101, 1966. doi: 10.1147/sj.52.007
htRl/httpps:/doo.or///0... /1tp://////...1//......./ 0078
[9] A. Bhaskara, A. Cutkosky, Kumar, and M. Purohit. Online linear optimization with many hints. In Advances in Neural Information Processing Systems, volume 33, pages 9530-9539. Curran Associates, Inc., 2020.
[10] A. Blum and C. Burch. On-line learning and the metrical task system problem. Mach. Learn., 39(1):35-58, 2000. doi: 1023/A: 1007622001111111 0107766111264888 832648.
[11] A. Borodin and R. El-Yaniv. Online computation and competitive analysis. University Press, 1998. ISBN 978-0-521-56392-5.
Cambridge
[12] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, 2006. ISBN 978-0-521-84108.5 //doi. //doi.or//10 1017 10117/600979855554662211
doi: 10.1017/CC809700511544622 URI. https

---

[13] N. Cesa- BiannBi O. Dekel, and O. Shamir. Online learning with switching costs and other adaptive adversaries. Advances in Neural Information Processing Systems 26, January 2013.
[14] N. Chen, G. Goel, and A. Wierman. Smoothed online convex optimization in high dimensions via online balanced descent. In Proceedings of the 31st Conference On Learning Theory. volume 75 of Proceedings of Machine Learning Research, pages 1574-1594, PMLR, 06-09 Jul 2018.
[15] M. Dinitz, S. Im, T. Lavastida, B. Moseley, and S. Vassilvitskii. Algorithms with prediction portfolios. In Advances in Neural Information Processing Systems, volume 35, pages 20273- 20286. Curran Associates, Inc., 2022.
[16) Y. Emek, S. Kutten, and Y. Shi. Online Paging with a Vanishing Regret. In 12th Innovations in Theoretical Computer Science Conference (ITCS ), volume 185 of Leibniz International Proceedings in Informatics (L.PPlcs), pages 67:1 1-7:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zenttruuneee für Informatik. ISBN 978-3-959977-777-1 URL https://drops 00.442330IIIII ITCS. 2021.67
dagstuhl de/ http://eniiieee/cceeee////e/ee/e
[17] A. Fiat, R. M. Karp, M. Luby, L.. A. McGeoch, D. D. Sleator, and N. E. Young. Competitive paging algorithms. Journal of Algorithms,, 12(4):685-699 1991. ISSN 0196-6774. doi: http://.ooooo1110100001116666661
URL.https: bettps::/www.co.
http://ppppwww...ccccnnneeeeeeee www.nceddreett.................. com/
[18] Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application boosting. Journal of Computer and System Sciences, 55(1): 139, 1997. ISSN 0022-0000. doi: acceancc/arricee///////000000000 t.c.m/.ccinnttam.m wttom//cieenc//rticlee//aaaeeeep
URL htt.hhttts:/wwwccieeee
[19] G. Goel, Y. Lin, H. Sun, and A. Wierman. Beyond online balanced descent: An optimal algorithm for smoothed online optimization. In Neural Information Processing Systems, 2019.
[20] G. R. Grimmett and D. R. Stirzaker. The lost boarding pass and other practical problems. The Mathematical Gazette, 105(563):216-22) 2021. doi: 10. 10.1017/mag.2211.44
[21] S. Im, R. Kumar, M. Montazer Qaem, and M. Purohit. Online knapsack with frequency predictions. In Advances in Neural Information Processing Systems, volume 34, pages 2733 2743. Curran Associates, Inc., 2021. URL https: http:s/:////ccceeeeneeeee meeur neurips. ctcpipps.ccppppppp cc/paper__ iles/paper/
[22] K. Jansen and Rohwedder. On the Corg Problem, pages
of the Restricted Assiggneem
2017. doi: 10. 10.11337/19978161199777772.8 URL https:://///pubb... siam. rg/doi/abs/100 1137111111111 /ttp:///1..87111117777721111111 11/.
[23] M. Khodak, M.-F. F. Balcan, A. Talwalkar, and S. Vassilvitskii. Learning predictions for algorithms with predictions. In Advances in Neural Information Processing Systems, volume 35, pages 3542-3555, 2022.
[24] Kraska, A. Beutel, E, H. Chi, Dean, and N. Polyzotis. The case for learned index structures. In Proceedings of SIGMOD' '88, pages 489-504, 2018. doi: 10. 1445/3183773.19999
[25] S. Lattanzi, T. Lavastida, B. Moseley, and S. Vassilvitskii. Online scheduling via learned weights. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithmss SODA 2020, pages 1859-1877. SIAM, 2020. URL
[26] J. K. Lenstra, D. B. Shmoys, and É. Tardos. Approximation algorithms for scheduling unrelated parallel machines. Math. Program., 46:259-271, 1990. doi: 10. 10.1007/BF015857445 URL
https://dot: wwg/10../... 1007 BBF0158545
[27] and J. Xian. Online unrelated machine load balancing with predictions revisited. In
M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6523-6532. PMLR, 18-24 Jul 2021.
12

---

[28] A. Lindermayr and N. Megow. Permutation predictions for non-clairvoyant scheduling, In SPAA, pages 357-368. ACM, 2022.
[29] A. Lindermayr and N. Megow, Algorithms with predictionns. prtpddttioonnttttg///gggggootsst redi Redictions github. io 2023. http:::://llgorrtthsssswtthhhh
thu
b.io Online: accessed 2023-07-12.
[30] N. Littlestone. Learning quickly when irrelevant attributes abound: A new thnear-threshold algorithm. In 28th Annual Symposium Foundations of Computer Science (sfes 1987), pages 68-77, 1987. doi: 10.1 (O0//FSS..99...3
[31] N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Inf. Comput. 108(2): 212-261, 1994. doi: 10. 10.1006/inco. 1994./co..19411000 1009. URL https:://dii.org/1000/ 1000////.00000/nn 199
4. 1009
[32] T. Lykouris and S. Vassilvitskii. Competitive caching with machine learned advice. J. ACM, 68 (4):24:1-24:255 2021.
[33] M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions. Beyond the Worst-Cass Analysis of Algorithmms, pages 646-662. Cambridge University Press, 2020.
[34] R. Motwani, S. Phillips, and E. Torng. Non-clairvoyant scheduling. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '93, page 422-431, USA, 1993. Society for Industrial and Applied Mathematics. ISBN 0898713137.
[35] M. Purohit, Z. Svitkina, and R. Kumar. Improving online algorithms via ml predictions. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL http::t:pppcoccoettttttte wwwpiiinnnnnnnuuii. neurips hctppppprr..lleeppppoo////////// (ttppp/r/2218//11e///2330
pdf
[36] D. Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the Thirty-Firs Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '20, page 1834-1844 USA, 2020. Society for Industrial and Applied Mathematics.
[37] T. Roughgarden, editor. Beyond the Worst- Case Analysis of Algorithms. Cambridge University Press, 2020. ISBN 9781 108637435. doi: 10.1017797811108677553 /ttps:ss:://doi org/
10. 10.11017/78110066777
[38] D. D. Sleator and R. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2):202-208, 1985. doi: 10. 10.1144/2786.2799.
[39] O. Svensson. Santa claus schedules jobs on unrelated machines. SIAM J. Comput., 41(5): 1318-1341, 1341, 2012. doi: 10.1137/1 10851201. Jattps///////o orreii..rg/11/ 10. 1111111711111 1137/110851201
[40] R. Vershynin. Dighe-Dimesional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematies. Cambridge University Press, 2018 doi: 10.10177997811082315566
[41] A. Wei. Better and Simpler Learning- Augmented Online Caching. In J. Byrka and R. Meka, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), volume 176, pages 60: 1 -0: 17, Dagstuhl, Germany, 2020. Schloss Dagstuhl Leibniz-Zentrum für Informatik. URL ht https: httpps://rrpp......p//op http://rroos...ssuuut.. dagstuhl wtw.e/niiiiieeeaacouooo///o//a/0
APT.:CCK.PPPPRR//RAAA hwT.:///DDDOOOOO......0 2020.60
[42] A. Wei and F. Zhang. Optimal robustness-consistenn trade-offs for Baaming-augmente online algorithms. Advances in Neural Information Processing Systems, volume 33, pages 8042-8053, 2020.
[43] L. Zhang, W. Jiang, S. Lu, and T. Yang. Revisiting smoothed online learning. In Advances in Neural Information Processing Systems, volume 34, pages 13692- Curran Associates Inc.. 2021. URL wttph:ttp//// https/tt/////rroceiinggs itw.eeeedddiinnnnnnueseeeeeeeeee neurips...... wttppppp.cppppppppppppppppp laaperrrfilleeeeeeeeeeee www.iesssppppeee http:/pppppppe////ppp/ 2001:5f0990070449957772228888288
pdf
13

---

Appendix
A Caching in realizable setting: omitted proof
Proof of Lemma 6 At every switch, we pay most l for switching the cache from the FitF solution of the previous predicted sequence to the cache of the newly computed one. Thus suffices to show that in between these switches, our algorithm has the same number of page faults as OPT.
Denote i1....,fe to the times when switches happen; for convenience, we also define to 1, fo+1 T 1. We denote ,",................ ..... TT" the predictions such that r' was predicted before the ith switch and n¹ after. Let Ki be the cost of the FitF solution for n' paid during time steps f....., f 1, for i == o....,o, a. In this notation, the cost of OPT is Σi=o ki. since T² = r (recall that r is the input sequence), while, excluding the switching cost considered above, the cost of the algorithm is Ei= sq. because it pays k during time steps .......,...................... t++1
when following a FitF solution for n'. We use induction on i to show that R. = K? for each j = i, .,.... G. This implies Σi K3 Li=o nd. This essentially follows from Obsevation 4 and the fact that all sequences n². = i,..., agree on the prefix up to time 4++1 1. The formal details follow.
In the base case with i 0, Observation 4 implies that FitF solutions for each n² incur the same cost during time steps .,.... t1 - 1 and we have Ki) solution for each N with j 2 i during time steps 1,..., .i+1 - is 2m= Kif En N + ni by induction hypothesis. Using Observation 4 Σ Ky, + k² = ... Di-1 nim + n. and therefore
Kg. For > O, the cost of the FitF
<² = xe for each = i.. In total, the algorithm incurs cost
ALG(r) s Σ
ok
Σ
ok OPT(r) ok.
B Online Load Balancing on Unrelated Machines
We are given set M of m machines and sequence of jobs arriving online. At each time step, receive some job j described by a vector Pj. where (2) is its processing time on machine i E M. We say that the job has type Pj- We have assign job one of the machines immediately without knowledge of the jobs which are yet to arrive. Our objective is to build a schedule of minimum makespan, i.e., denoting J; the set jobs assigned to a machine i, we minimize the maximum load ΣjeJ, (i) over all E M. The best competitive ratio achievable in online setting is O(log m) [5]. In offline setting, there is a 2-approximation algorithm.
Proposition (Lenstra al. (26). There an offline 2-approximation algorithm for load balancing on unrelated machines.
Here we use the competitive ratio to evaluate the performance of our algorithms. We say that (randomized) algorithm ALG achieves competitive ratio (or that ALG is r-competitive), if Elcost(ALGii (ALG(I))] S r- cost(OPT(I)) + a holds for every instance I, where OPT(I) denotes the offline optimal solution for instance I and a is a constant independent of I.
Learning task. We are given class H of hypotheses Hi,... He, each specifying the frequency fp 2 0 for every job type such that Σ, fp = For simplicity, we assume that there is a constant d > 0 such that all frequencies in all hypotheses are integer multiples of 8. For a hypothesis H with frequencies fp and an integer h 2 1, we define a scaling H (h) as an instance containing h jobs of type p. for each p. This way, any type p with fp o 0 is represented by at least single job in (1). We denote co the largest makespan of H over all hypotheses H E H.
We say that instance I' is consistent with the input far, if the following holds for every job type pr the number of jobs of type p in instance I' is greater or equal to the number of jobs of type p which already arrived in the input sequence.
We note that the value e of the makespan of the real instance can be guessed (up to a factor of two) by doubling while loosing only a constant factor in the competitive ratio. Using doubling and
14

---

2 2-approximation offline algorithm (Proposition 8), we can also find scaling I; of each hypothesis H, such that the makespan of between e and 4c. Therefore. we start by assuming that we have the value of e and the scaled instances .,..... 7 in advance, and postpone the discussion of finding them to Section B..3 We begin with the realizable setting, where the task of the predictor is either to identify an instance I consistent with the whole input return ERR which signals an incorrect value of c. Agnostic case is considered Section B.4 and robustification of our algorithms in Section B.5
Section contains lower bounds.
B.1 Predictors
We propose deterministic and a randomized predictors for the realizable setting. Each of these predictors receives c- the guessed value of the makespan of the real instance and problem instances /1,...,I4 .1 whose makespan is between с and 4c created by scaling the hypotheses //,,..., Hy. For each p and i, we denote ni, the number of jobs of type p in instance I;. Both predictors switch to new prediction whenever they discover that, for some p, the number of jobs of type p which arrived so far already larger than their predicted number. At each switch, they update set C {1, {l.....6 of instances which are consistent with the input up to the current moment, i.e., the number of jobs of type p which appeared so far most ni, for all p and E A.
There is a simple proper predictor which makes l switches. This predictor starts by predicting according to an arbitrary instance. Whenever the current instance stops being consistent with the jobs arrived so far, it removes this instance from A, and switches to an arbitrary instance still in A. In what follows, provide more sophisticated predictors with lower number of switches.
Deterministic predictor. Our deterministic predictor is improper. At each switch, it predicts "median" instance I created from the instances in A as follows. For each type p. I contains nn jobs of type p. where nn is median of ni over all i E A. This way. whenever the number of jobs of type exceeds 2g. at least half of the instances are removed from A. Once A is empty, the algorithm returns ERR. In the realizable setting, this happens when the guess of c is not correct.
Predictor 3: load balancing on unrelated machines, deterministic
{}
2 choose ün as median of (ni, = 1, 1,....,e) f} for each job type p // switch to initial î 3 for time step when, for some the (ñ, + 1)st job of type arrives do
A set of instances consistent with the input so far if A = ( then return ERR for each job type p do
choose Ωp as median of (n², | A).
switch to new i
Lemma 9. Predictor maintains a prediction which is always consistent with the jobs arrived so far. Given instances of makespan between and 4c, it makes S llog switches before it either identifies an instance I consistent with the whole input, or returns ERR if there is no such instance. The makespan of each prediction at most 4c log T, where 5 is the number of distinct job types present in the instances I II,...,ly Tt.
Proof. First, note that whenever number of jobs of some type exceeds the prediction, Predictor switches to a new prediction consistent with this number.
Consider switch when the number of jobs of type p exceeds ñ.. Since 7p was chosen median of ni, over i E A, the size of A decreases by factor of at least 2 by this switch. Therefore, we have at most log l switches.
Now, we bound the makespan of by 4c logog where i is the prediction constructed from the current set of instances A. We do this by constructing schedule for i. We say that instance 1; covers type if ni 2 7p. By the construction of i, we have that for every at least half of the instances in A cover p. This implies that we can find an instance I, covering half of the job types. Indeed, consider matrix M whose columns correspond to instances i in A and its rows to 7' S different job types
15

---

present in instances of A. We define Mp.; if I; covers p and 0 otherwise. Since every row has least A|// ones, there are least 7' /2 ones M so there must be a column of M containing 7 ones.
So, pick I and add all its jobs to the schedule, using schedule of I, of makespan most 4c. Then we remove i from A, and remove all job types covered by from I. |A] decreases by 7 decreases by factor of 2, and we still have that every remaining, job type is covered by at least |A// instances: This follows since for any type remains the same while |A| decreases by 1. Therefore, after iterating this process at most log r times we cover all job types using makespan at most 4c log...
covered by It the number of instances covering
Randomized predictor. Our randomized predictor is proper. At each switch, it predicts an instance I, where i is chosen from uniformly random. We show that satisfies the same bound on the number of switches as Predictor 3 but the makespan of its predictions is much smaller.
Predictor load balancing on unrelated machines, randomized
A = (I,...,f choose E A uniformly at random
2 set np = p for each job type p
// switch to initial i
3 for time step when, for some p the (ñp + 1)st job of rype arrives do
A set of instances consistent with the input far
A =
then return ERR
choose A uniformly random
set 7ip n for each job type p
switch to a new i
Lemma 10. Predictor maintains prediction which is always consistent with the jobs arrived so far Given instances of makespan between e and 4c, it makes a S. log switches in expectation before it either identifies instance Ię- consistent with the whole input, or returns ERR there is such instance. Each prediction has makespan at most 4c.
Proof. First, note that whenever number of jobs of some type exceeds the prediction, Predictor switches to new prediction consistent with this number.
Now, we bound the expected number of switches done by Predictor in the style of the airplane seat problem. For every = I,..., ,,, É, define t, as the time step when an arriving job of type p exceeds ne. if no such time step exists. Note that for every instance which is inconsistent with the input, & finite. The instances are eliminated in the order of increasing f;- Since we choose uniformly at random the remaining instances, we have tý S for at least half of the inconsistent instances (in expectation). The formal proof then follows from the traditional analysis of the lost boarding pass problem, see e.g. [20]
B.2 Algorithm
Our algorithm uses a predictor whose predictions are always consistent with the jobs arrived so far. At each switch, it computes 2-approximation of the optimal solution for the predicted instance using algorithm from Proposition S and schedules jobs based on this solution until the next switch.
Algorithm 5: load balancing unrelated machines
for each incoming job do this the first job or there was switch then get a new prediction i from the predictor or return ERR compute Lenstra(i)
assign j to machine based on Lenstra(i)
Given a predictor which makes switches and produces predictions that are always consistent with the jobs arrived so far and have makespan most Algorithm Setrrtthhmussee uses makespan at
Lemma 11.
16

---

most 2nd and either schedules all jobs in the input sequence or reports ERR if none of the instances consistent with the input sequence.
Proof. At each switch, Algorithm 5 starts building a new schedule for the predicted instance with makespan most 2x. Therefore the total makespan is at most 26d.
B.3 Guessing the Optimal Makespan and Scaling
First, we discuss how find scaling of hypothesis H that has the required makespan. Let e be our estimate of OPT such that I OPT I 2c. We start with h = 1 and keep doubling h until Lenstra( H (h)) becomes at least 2c. (and most 4c). Since Lenstra is a 2-approximation, we know that when Lenstra( (h)) 2 2e then OPT(H (1)) 2 Since this is the smallest h for which Lenstra( H (h)) 2
we know that OP S 2c so OPT(H S 4e.
Algorithm i our scheduling algorithm. We start with the initial guess of co for the optimal solution, where cp an upper bound on the makespan of (1) for each H/ H. At each iteration we double our guess c. We scale the hypotheses to build instances with makespan between e and 4c. We run Algorithm with these instances until it returns error. We keep iterating until the whole input is processed.
Algorithm 6: guessing the optimal makespan by doubling for Co. ......... 2 co. 2oco, 23 co....... do for i =1 l....... do find scaling ht such that I, (h))) has makespan between and 4c
Run Algorithm 5 with J1, II...., Te
not ERR then finish: all the jobs are scheduled
If Algorithm 6 uses makespan at most 7/e in an iteration with guess c, then it uses makespan most O(-)c*, where et denotes the value of in the last iteration.
Lemma 12.
Proof. The total makespan used by the algorithm is at most
logie" /co) 2'co7 S 2c
Lemma 13. Let c* be the value of e in the last iteration of Algorithm 6 in the realizable setting. Then the makespan of the offline optimal solution is at least c* /2.
Proof. Let H₁ be the correct hypothesis describing the input instance 1. We know that 14,- (h /2) & I, otherwise Algorithm 6 would terminate the previous iteration. We have
0122 OP (h /2)) < OPT(I),
implying OPT()) 2 e2/2. The first inequality is by the choice of h. and the last one since Hy (WC (2) I.
Theorem 14. There are algorithms for the realizable setting with deterministic and randomized predictors which, given hypothesis class H of size E, achieve competitive ratio O(log e flog 7) and Ollog E) respectively, where is the total number of different job types in H.
Proof. Combining Lemmas
12 and 13 the makespan achieved by Algorithm is at most O(7 OPT).
9 10 and TI we have 7 = log e log in case of the deterministic Predictor and ? log & in case of the randomized Predictor
By Lemmas
17

---

B.4 Agnostic Setting
The algorithm above works also in the agnostic setting. Let fp and fü be the frequency job type p according to hypothesis H E H. and its true frequency, respectively. If there is a job type p such that Sp + and f O, we define ar == n + 1, where n denotes the number of jobs in the input instance. Otherwise, we define or == max P f * 0}. Similarly, if there a job type p such that fp = and f * O, we define 3и == n + 1. Otherwise, 3H = max fp fp + 0}. Note that both a and бy are at most + 1: the smallest fp > Os at least 1/n for the job types represented by a single job and the same holds for the scaling (1) of each hypothesis H H. Let H E H be a hypothesis achieving the smallest product 0z 1n We call a pair (a, 9), where ar = ay and / = 3y the error hypothesis class H.
We prove the following variant of Lemma for for agnostic setting, in the case with a. B S n.
Lemma 15. Let a* be the value of e in the last iteration of Algorithm iin the agnostic setting, given hypothesis class H with error a, 3 S n. Then, the makespan of the offline optimal solution is at least D(az)
Proof. The main idea here is that even all hypothesis are incorrect, Algorithm 66 terminates once the input instance 1 is subsumed by large enough scaling of some hypothesis. Consider the correct hypothesis H* for I consisting of real frequencies fp for each job type p (H1* may not be in H the agnostic setting) and the best hypothesis // E H. (such that a, 3 aH, (F)). We assume below that a and 3 are integers, otherwise we round them up to the closest integers.
We have the following: I H (h) for some integer scaling h. Since, fž S 8fp. we have H* S H (Bh). Therefore, in the last iteration of Algorithm 6 we have c* within a constant factor from the optimum makespan of H (3h) Similarly, since fp S a.p, we have that ((3h) C H (a,h) which implies that the optimum makespan of H (3h) is most a OP (Bh)) S a OPTP( Altogether, we have c* S 0(3 OPT([)).
Theorem 16. There are algorithms for the agnostic setting with deterministic and randomized predictors which, given a hypothesis class H of size l with error (a, 3), achieve competitive ratio Ol3 log foog r) and ((a3 log l), respectivel,, where T is the total number of different job types in H.
Proof. Consider an algorithm which schedules all jobs of type p such that fp according to all hypotheses in V. to the machine arg min Pt, i.e., the machine which can process the job fastest. Let Jo denote the set of such jobs. All other jobs in 7 Jo are scheduled using Algorithm The resulting makespan is most
Jol OPT +yc" < (Jo OPT +(((8)) OPT
where e* is the value of in the last iteration of Algorithm 6 processing jobs in T Jo- This is because, for every: j E Jo. we have OPT 2 minje[m] Pi. The inequality follows from lemmas 15 and I2
If [Jo] 0, then least one of a and / is at least + 1. Therefore, our makespan is always most a OPT. By lemmas [] and[T] we have y = log log T in case of the deterministic Predictor
and 7 = log in case of the randomized Predictor 4
B.5 Achieving Robustness
With large a. 3, the competitive ratio in Theorem 16 might be worse than O(log m) which is achievable without predictions, i.e., Algorithm 6 is not robust. This can be fixed easily: once Algorithm 5 returns ERR at iteration e, we run classical online algorithm by Azar et al. (5) as long as it uses makespan yc. That is, we stop as soon its makespan go above 7e (and we do not schedule the job that makes it go above ycc This increases the makespan of the solution by factor at most 2 and ensures that OPT 2 (c/O(logm) m).
The following lemma holds both in realizable and in the agnostic setting.
Lemma 17. The makespan of the solution produced by Algorithm 7 is at most a constant factor higher than of Algorithm 6 Moreover, its competitive ratio is always bounded by Ollog m).
18

---

Algorithm 7: robust variant of Algorithm 6
1 for c= Co...... cq, 2ºc,, 2 co..... do
for == ,,..,,& L do
find scaling h3 such that I; == (N() has makespan between and 4c
4 Run Algorithm 1 with I,...,
Run Online algorithm of Azar et al. [3] as long as it uses makespan of at most '
if all jobs are scheduled then finish
Proof. Algorithm O terminates once it finds e* and i, such that the actual instance 7 is a subset of H Hg ). With the same ct, Algorithm terminates as well. While Algorithm uses makespan of at most yc" in each iteration, Algorithm uses makespan of at most 2-yc* in each iteration.
Now we prove the (log m) bound on the competitive ratio. Consider I' C the set of jobs assigned to machines by the online algorithm of Azar et al. [5] in the next to last iteration (fine(5of Algorithm 7
We have OI)(()= 2 OPT(L") Z O[logm) because the online algorithm is O(log m) comppeiiiievee
72"/2_
and it required makespan ye" /2 the second last iteration. Since Algorithm uses makespan at
most ((yc*) by Lemma 12 the bound on its competitive ratio follows.
B.6 A note on combining arbitrary integral algorithms
Dinitz et al. [15] considered portfolio of & algorithms for load balancing on unrelated machines and proposed way to combine their outputs in single fractional solution of cost most O E) f)-times higher than the cost of the best algorithm in the portfolio. Such solution can be rounded online only by loosing an additional factor of (log log m/ log log log m))
Our approach described above can be used to produce directly an integral solution as far as all the algorithms in the portfolio are integral. The cost of this solution most Ollog c)-times higher than the cost of the best algorithm in the portfolio.
We guess the value of the makespan achieved by the best algorithm in the potfolio using the doubling trick, loosing a constant factor due to this guessing as in Section We create a randomized predictor similar to Predictor 4 as follows. Start with the set of active algorithms A == {1,..., {} and predict an algorithm chosen from A uniformly at random. Once its makespan exceeds c, we update A to include only those algorithms whose current makespan is at most c, choose one of them uniformly at random and iterate. We continue either until all jobs are scheduled or until A is empty which signals an incorrect guess of At each time step, schedule the current job based on decision of the algorithm currently chosen by the predictór, paying at most e while following a single algorithm. An argument in the proof of Lemma shows that our predictor switches Ollog E) algorithms in expectation at each iteration.
B.7
Lower Bound
Our lower bound holds for a special case of load balancing on unrelated machines called restricted assignment, where processing of each job is restricted to subset S, of machines, i.e., its processing time is on all machines belonging to Sj and +oo otherwise. Our construction requires m 2 { machines and is inspired by the construction of Azar et al. 55 (E is number of hypothesis in H as before). Since we can ensure that all jobs have infinite processing time on machines l + 1,...,
we can assume that & m and that e a power of two.
We construct instances of restricted assignment on machines, each with makespan c E N. In instance i {1,..., f). there are c jobs restricted to machines whose index agrees with in the j - most significant bits, for j 1...., log f. In particular, each instance starts with ol jobs any machine. The jobs arrive in iterations from j to log (from
which can be processed less restricted to more restricted). If numbers and i' have a common prefix of length j - 1, then instances and i' have the same jobs the first j iterations.
Optimal solution for instance can be described as follows: For each j 1,.... log l, schedule all el/2' jobs evenly on machines whose index agrees with i up bit j 1 but disagrees with i in bit
19

---

There are -
- 2/23 = 2/23 such machines. We leave all the machines which agree with i in the first j bits empty for the following iterations. Since, for each j. we schedule cl /2/ jobs evenly on f/2/ machines, their load is c.
Theorem 18. There is no (rundomized) algorithm which, with hypothesis class of size & S m, that achieves competitive ratio o(log E).
Proof. The adversary chooses the correct instance bit by bit, fixing the jth bit i, at the end of iteration j depending on the behavior of the algorithm. Bit ij is chosen according to the following procedure: Given the knowledge of the distribution over algorithm's is decisions, count the expected number of jobs from iterations ... assigned machines whose first j bits are f1,..... f1......jg11.0 If this number is higher than the expected number of jobs assigned to machines with prefix é1 8....... 4 1, then choose ig = O. Otherwise, choose i 1.
For each j = 1,...,logg log we denote M, the set of machines with prefix ;1,-.., ,,, with M,- = f1...., f). We show by induction on j that at least j//e/2 jobs are assigned to the machines belonging to M, in expectation. This way, Mogg& é contains single machine with expected load at least Leloge L.
The base case j = of the induction holds: We assign of jobs to l machines in Mo and i chosen so that machines in M1 get at least half of them, in expectation. For j > 1, the expected number of jobs from iterations up to j assigned to machines in M is at least 2 [j - 1)cl/222 22- by the induction hypothesis. There are /f/22 jobs restricted to machines in M, scheduled in iteration j. Therefore, the total expected number of jobs from iterations ......j assigned to machines in M3-1 is at least
1 (j 1)2
/ + 2 -
Since ij is chosen such that the machines in M, are assigned least half of the jobs assigned to machines in My-1 in expectation, the expected number of jobs assigned Mj is at least //2//2)
While the makespan for the instance is c, the machine in Moge e has expected load at least eooo f.
showing that the competitive ratio of the algorithm is at least 1 log l.
C Non-clairvoyant Scheduling
We have single machine and n jobs available from time O whose lengths P1..... the algorithm. We know the length Py of the job only once it is finished. If it is not yet finished and it was already processed for time J. we only know that Pj 2 Zj. Our objective is to minimize the sum of the completion times of the jobs. To avoid scaling issue in our regret bounds, we assume that the length of each job is at most 1. Note that if a solution for instance / has total completion time objective OPT(T) + R. then the same solution on a scaled instance obtained from by multiplying all job lengths by has objective (OOPT(I) + It) OPT(I') aR. There is 2-competitive Round Robin algorithm which runs all unfinished jobs simultaneously with the same rate [34) Consider an algorithm which schedules the jobs in order I,.... n, denoting Pr. their lengths. Then, its total completion time objective can be expressed as
.......PP....... Pn. are unknown to
Pj ;=1==
Σ j=1
pn j+
This objective is minimal if p1 .... Pa. which is the ordering chosen by the optimal algorithm Shortest Job First (SJF) for the clairvoyant setting where we know lengths of all the jobs in advance 34
Learning task. We are given class 7 of & hypotheses, each of them specifies length of all jobs, denoting pi the length of job j according to the hypothesis H,. predictor uses 7. produce prediction π, where πy is the predicted length of the job j. We call predictor monotone if, at each time step, it maintains a prediction which is consistent with our knowledge about lengths and n; < Pj holds for every job (i.e., it never overestimates a length of job). We propose monotone predictor only for the realizable setting. Non-clairvoyant scheduling in the agnostic setting is considered in Section C.2 with different kind of hypotheses.
20

---

Predictor. We propose monotone predictor which works as follows. At the beginning, we start with A : (1, .......... , At each time instant t, we remove from A each hypothesis such that there is some job which was already processed for time 2; > Pj. Whenever A changes, we switch to new prediction by updating the predicted lengths of unfinished jobs as follows. For every unfinished job, we predict the smallest length specified by any instance in A.
Predictor non-clairvoyant scheduling, realizable setting
for whenever some hypothesis is removed from do U := set of unfinished jobs
2
for j E U do jj == min | A} // switch: update pred. unfinished jobs
Lemma 19. In the realizable setting, Predictor is monotone and makes & switches.
Proof. Switch happens whenever z; πT for some unfinished job j. In that case, the hypothesis predicting 3, for job is removed from A; therefore there can be at most l switches.
In the realizable setting, there is hypothesis i* which is correct and is never removed from A. Therefore, at each time instant, we have π S 5 Py for any job j.
L
Algorithm. At each time instant, our algorithm receives the newest prediction from the predictor and always processes the job whose current predicted length is the smallest. When a switch happens, interrupts the processing of the current job, leaving unfinished.
Algorithm 9: non-clairvoyant scheduling
for each time instant do
U == set of unfinished jobs get the newest prediction ı from the predictor run job j arg minjeu(TT))
Lemma 20. With a monotone predictor which makes a switches, Algorithm Algorithm@produee produces schedule
with total completion time at most OPT(I) + / on an input instance with job lengths bounded by 1 and offline optimal completion time OPT(T).
Proof. We relabel the jobs so that S ... Pn. The optimal solution is to schedule them this exact order, always running the shortest unfinished job, achieving total completion time
OPT(I) = Ep: pr. -n-nnn -n- in-i+11
==1
At each switch of the predictor, our algorithm leaves the current job unfinished. On the other hand, whenever job is completed, it must have been the shortest unfinished job, because was the unfinished job with the shortest n, and we have P/ S n S Fy S Py for any unfinished job j' by the monotony of the predictor. Therefore, the total completion time of the algorithm is
ALG(I) S (m
where C, the time between the completion of jobs and spent processing jobs which were
left unfinished due to switch we denote the set of these jobs by Q; Algorithm Sporithmm@prccssseee processes job j only when πÿ S n for all unfinished jobs j'. Therefore, each job j Q can contribute to C; at most π < n. < ps. by the monotony of the predictor. Therefore we can bound the cost of the algorithm as follows:
ALG(!) = OPT())
Σ Co (n-i+1) 1=1
Σ p -
1=1 JEQ.
21

---

Note that o Ei= Qiil So, the sum in the right-hand side contains summands and each of them be bounded by (2)PT(T), since we have
(n i
22 E Pi k 1) S
2 Paln + 20PT()) Σ
1))² 2p:
The first inequality follows since S 1 and the third inequality since p: S Pk for each k z i. Therefore, we have
ALG OPT(1) s ov <ov2
Lemma 19 and Lemma 20 immly the following theorem.
Theorem 21. Consider an instance with maximun job length 1 and let OPT(1) be the offline optimal completion time of There is an algorithum for the realizable setting which, given hypothesis class H of size t, achieves objective value most OPT(() 4 2/2OP((()
C.1 Instances with Two Distinet Lengths
Consider the case in which the larger jobs have length and the smaller ones have length E [0, 1). We propose the following predictor which makes only log l switches and constructs prediction based on the majority rule.
Predictor 10: non-clairvoyant scheduling with two distinct lengths
for time instant do
if 0 some prediction shown to be wrong then
==
set of instances consistent with input so far
U set of unfinished jobs
for j U do Jij arg max Koj lie AHl // majority prediction
By its definition, Predictor 10 makes a switch every time its prediction is shown to be incorrect. The following lemma bounds its total number of switches. Lemma 22. Predictor makes makes most log & switches in total.
Proof. When a prediction nj is shown to incorrect, the predictor makes a switch and the size of A decreases by at least factor of 2, because the length of was predicted to be æ, by at least half of the hypotheses Therefore, there can be at most log switches.
Our algorithm works as follows. If there is an unfinished job j with A. it runs it to completion. Otherwise, it chooses an unfinished job predicted to have length 1 uniformly at random and runs it completion. The following lemma is useful for the analysis.
Algorithm 11: non-clairvoyant scheduling with two distinct lengths
for time step and whenever some job is finished do update the prediction π
:= set of unfinished jobs if [here j E U s.t. मं then run until it is completed
else choose j from uniformly at random and run to completion
Lemma 23. Consider two schedules without preemption such that the second one differs from the first one by moving a single job of size 1 earlier, jumping over d jobs. Then the total completion time of the second schedule is larger by at most d Li=1 Pi where -1.-.. Da are the processing times of the jobs which were delayed. This difference is at most (1 - X)d. If all these d jobs have length then the difference is exactly (1 X)d.
22

---

Proof. The completion time of the job we shifted earlier get smaller by Ei= Pt, and the completion time of the d jobs which were delayed increases by most 1. All other completion times do not change.
Lemma 24. Algorithm 17 for instances with job lengths in {1, with a predictor which makes a switch whenever its prediction is shown to be incorrect and makes switches in total produces schedule with expected total completion time at most OPT(I) + a(1 - A)n, where (PT(I) is the total completion time of the offline optimal solution.
Proof. The offline optimum schedules all jobs of length À before the jobs of length 1. If we finish a job and there was switch, the prediction of its length was correct. We write a' + o", where o' is the number of times we process a job with incorrect predicted length À (type- switch) and o" the number of times we process job with incorrect predicted length (type-2 switch).
Every type-1 switch causes a job length to be scheduled before at most ni jobs of length A. By Lemma 23 the schedule produced by the algorithm is more expensive than the solution where these o' jobs were executed last by at most d'(1 A)n. remains to analyze by how much this modified schedule, in which type-1 switches never happen, is more expensive than the optimal schedule.
We split the time horizon into intervals moments when a type-2 switch happens (recall that the switch happens right after we scheduled short job with predicted length 1). There are o" + intervals = 0, ..........'.. o". We denote by qi the number of jobs of predicted length À scheduled first in the ith interval (including the first job causing the type-2 switch) and by m, the number of jobs of predicted lnngh scheduled thereafter the ith interval. Let n, denote the total number of unfinished jobs when we finish scheduling the qi jobs of predicted length X. and let 8; be the number of unfinished jobs of length À at that time. We have qi
8:-1 8j.
With this notation and using Lemma 23 the regret of the algorithm is
x1
Σ
m48;
E=
This is because the optimal schedule processes jobs of length À first and our schedule can be constructed by moving (one by one) m; jobs of length forward, leaving s; jobs of length À behind for each 1,....o"..
Since we choose to process random job of predicted length we have Elm;; n2, st] 1
#++1 S
as we are drawing from n, jobs without replacement until the first of s; jobs of size A is drawn. Therefore E[m,; s,] S n/s; and Blm,s]] = Σý= IP(s; = j)E|m;s 8 = jl s n. So, the expected regret in case a type-1 switch never happens is
d"-1
(1 1- 1)
Σ
E[mss:] S (1 A)no".
Therefore, the cost of the algorithm is ALG S OPT -1--)nno.
Lemma 22 and Lemma 24 together imply the following theorem.
Theorem 25. Consider instance I with jobs of length either 1 or X for some fixed X (0, 1). There an algorithm which, given a hypothesis class H of size f, produces a schedule with expected total completion time most OPT(I) + o - X)n in the realizable setting (i.e., I H), where OPT(I) is the total completion time of the offline optimal solution.
C.2 Agnostic Setting
We propose an algorithm for the agnostic setting with a different type of hypotheses, each specifying an optimal ordering of the jobs rather than their lengths. Given a class of such hypotheses H. the predictor maintains an ordering and, at each switch, it can change the ordering of the unfinished jobs. Let = {1..... n) be the set of all jobs. We call mistake every inversion this ordering, i.e.
two jobs i, E J such that p. < Pj but π (j) < (1). For every pair of jobs (d. }}. we define
(p: p2) if) T())
(i.)))
(p, - p+)* otherwise.
23

---

If the order of j in is incorrect, then ju(T. ( is the weight of this mistake. Otherwise, it is equal to O. For a set of pairs of jobs P E (2) where (2) denotes the set of all pairs of jobs, we denote μT P) E(i.jer u(T, {i,j)). and p(=) pltT, (2) is the total weight of mistakes in и.
Proposition 26 (Lindermayr and Megow (28). Let OPT denote the cost of the offline optimal solution and ( the cost of the solution where the jobs are processed according the ordering g. Then cost(T) OPT = ((T)).
Predictor. It has a parameter m. First, it samples m pairs of jobs, P= ((i, (i- m.). The initial predicted permutation starts with these jobs, i.e., -- I'm and the rest of the jobs follow in arbitrary order. Once the lengths of the jobs in P are determined, the predictor calculates u(h, P) for each h E H. Then, it makes a switch to its final prediction by ordering the jobs not contained in P according to the hypothesis with the smallest u(h,P).
Predictor 12:
non-clairvoyant scheduling, agnostic case
At time O: sample m pairs of jobs P
When the last job in P is completed:
3 for h E H. do compute p(h, P)
4 Switch to a new prediction based on with minimum p(h, P)
Predictor makes only switch which happens at the moment when the last job from P is completed.
Lemma 27. Let π be the final prediction produced by Predictor ( during its only switch. With probability (1 5), we have u(T) S p(h'))+0(m// (log 2)2/3), where ht denotes the best hypothesis in H.
Proof. The total weight of the mistakes in the last prediction can be bounded by
p(xx) S ((h) + 2mn,
(I)
where i is the hypothesis chosen at line This follows because the 2m jobs belonging to which at the beginning of ir have length most and each of them delays the completion of most jobs. We need to show that, with high probability, we have to show that y(h) similar to p(h").
For each hypothesis h E H and pair {i,j} ((x)) chosen uniformly at random, we denote are chosen uniformly at random, we H. Now we use Hoeffding's concentration inequality [40
p(h)/ (()- Since the pairs have [h P)] = Pam for each Thm 2.2.6] to show that p(h, P) is close to its expectation with a high probability. Choosing m (20g)2/5)//)))
Ph Elu(h, (i.
where is parameter to be decided later, we have
PP P(u(h, P) pamm > em) < exx ( (- 2emm)² /2/m///mmmmmmm = 2 exxp( -exp(-2emmm 2m2 S 8/e,
for each h E H. So, by a union bound, with probability at least 1 - 6, we have (n(h, P) Pam S em for all hypothesis h E Ht and the chosen hypothesis h must have Ph S Ph + 2c. Multiplying by (?)
we get p(h) < p(h") ) + (?) with probability 1.
The total weight of mistakes in the final prediction π is bounded as follows:
n2 +
log(28/8)
u(T)= - (ahh) 2e
22 n.
2
We choose O log(t/8) 1/3
getting (T)) < p(hh)) + (n 5/3 (log 1/3) with desired probability.
Algorithm. At each step, it chooses the first unfinished job in the predicted ordering and runs it until it is completed.
Lemma 28. Given predictor which makes switches only at moments when some job is completed, never changes ordering of finished jobs, and the total weight of the mistakes in its final predictions
the regret of Algorithm 13 is p.
24

---

Algorithm 13:
non-clairvoyant scheduling, agnostic case
for each time instant do run the first unfinished job according to the current prediction
Proof. If switches happen only at job completions then Algorithm 13 never preempts any job before it is finished. Since, the predictor changes only the ordering of the unfinished jobs during, the algorithm processes jobs in the order suggested by the final prediction. By Proposition 26 the difference between the cost incurred by the algorithm and the offline optimum is equal to Jz.
Algorithm 13 when run with Predictor 12 first processes jobs in P. Once the last job in is completed, Predictor [2] switches to its final prediction by updating the ordering of unfinished jobs, fulfilling the conditions of Lemma 28 Together with Lemma (7] we get the following theorem.
Theorem 29. Consider an instance I with maximum job length 1. There an algorithm for the agnostic setting which, given hypothesis class H of size I with error μ. produces a schedule with total completion time at most OPT(I) + μ + On 5/3 (log 2)2/8) with probability at least (1 - 8).
C.3 Lower Bound
In this section, we prove a lower bound for instances with three distinct job lengths. The instances used in our construction will use only integer job lengths and the following technical lemma helps simplifying the exposition of the lower bound.
Lemma 30. Consider instance of non- cla-ccaarvoyaat scheduling with jobs of integer lengths. Any online algorithm A on this inslance can be converted to online algorithm A' with no larger cost which interrupts and starts processing of jobs only at integer time steps.
Proof. Let & f1.....ty ty be time instants such that the processed part of some job in the schedule produced by reaches an integer value. We use the following notation: The milestone i reached at time f is described by k N and ji E {1...., n meaning that k; units of job ji become completed at t.. Since jobs are guaranteed to have integral lengths, algorithm A discovers new information about job lengths only at times .1,...,44 Iy. Namely, at time knows that the length of job is max (k 4 S and ji = j} if j is finished, and at least max (k; + 4 < I and ja j] if is unfinished.
We describe algorithm A' which reaches the milestones 1...., N in the same order as A, reaching milestone i at time < t,. At time 0, it chooses job j1 and processes it for single time unit, reaching milestone 1 with ji and L1 = 1 at time S f1. Having milestones reached at time step i E ......... N 1, A' chooses job j++1 and processes it for single time unit. Since the previous milestone involving Ji+1 was already reached by A', Ji+1 is processed for k;+1 time units, reaching milestone i + 1. We have f++1 + 1, because reaching each milestone requires single unit of computational time and no algorithm can reach + 1 milestones before time i+! 1.
Since all jobs have integer lengths, they can be completed only when some milestone is reached. Since A' reaches all milestones no later than A, its total completion time is at most the one achieved by A.
Lemma 31. Consider two schedules such that the second one differs from the first one by moving at
least a single unit of some job j earlier, jumping over completion times of d jobs, while the completion time of j does not change. Then the total completion time of the second schedule is larger by at least
Consider two schedules such that the second one differs from the first one by moving a whole job j of size 3 earlier, jumping over d jobs of size at most 2. Then the total completion time of the second schedule is larger by at least d.
Proof. First case: the completion times of d delayed jobs increase by and all other completion times remain the same.
25

---

We assume that the algorithm starts and preempts jobs only in integral time steps. This assumption without loss of generality by Lemma 30 When deciding which job run at time E N, it can choose either a job from I.... l or a job from E² 1.... n. If it runs job from 1...., e for at least 1 time unit, it discovers the length of all jobs in the same block. If the true size of the job was 1 and Second case: the completion time of j decreases by at most 2d, while the completion times of the delayed jobs increase by 3. All other completion times do not change.
Theorem 32.
There is a hypothesis class of size E such that algorithm for non-clairvoyant scheduling in realizable setting can achieve a regret bound o(tn).
Proof. We construct e instances with > 21 jobs. The job lengths will be 2, However, can rescale the time to make an execution of a job of size 3 to last time unit. Such rescaling changes both the optimal and algorithm's total completion time as well as their difference by factor of 3.
The first e2 jobs are divided into blocks of l jobs each. The ith block includes jobs (i 1) 1, (i 1)e + 2...., il. The jobs in the ith block have length 1 in instance and 3 in all other instances. The jobs 12 +...... n have length 2 in all instances.
The correct instance is picked uniformly at random. By Yao's principle (see, e.g., [1I it is enough to prove a lower bound for any deterministic algorithm on this randomized instance to get lower bound for any randomized algorithm. The optimal solution of any of these instances is to schedule & jobs of size first, then n jobs of size 2, and finally 8² e jobs of size
the job is finished, it also discovers the true instance. We denote by A C {L......} the set of blocks
such that the algorithm still does not know the lengths of the jobs these blocks. We consider the following two cases:
Algorithm runs a job j E {E2 + +1, 1....,, n such a job has size 2 in all instances. If the correct instance not yet determined and there are still l unfinished jobs of length 1, this action worsens the algorithm's 's schedule by E, by Lemma 31
Algorithm runs a job; (I...., ]: the length j with probability 1/|A| jf belongs to a block i E A and otherwise. If is 1. the algorithm determines the correct instance and suffers no more regret. Otherwise, |.A] decreases by 1. If ALG processes this job completely, it suffers regret 2 Te by Lemma 31 where is the number of unfinished jobs of size 2. If it processes the job for least 1 time unit without finishing it, it also suffers regret 2 Pt.
One of the following complementary events occurs with probability at least 1/2: When the first job of size 1 is scheduled, either (1) r, < (n - /22 or (2) r; 2 (n - -2)2
If the event (1) occurs, at least (n f2/2 jobs of size 2 are scheduled before the first job of size 1, each of them causes regret at least f. With n 2 2f2, we have the regret at least ((f)).
In case event (2) occurs, we calculate how many jobs of size 3 are scheduled before the first job of size 1 in expectation. If each job j {l,..., { chosen by the algorithm belongs to e+1 different block, it will run E4T 2 t/2 jobs of size 3 before it runs the first job of size 1 in expectation. Otherwise, the expectation is even higher. Therefore, the algorithm suffers regret at least (E/2)r, 2 (1/2)(n /2//2 2 (2/2)(n/4) O(fn).
D Caching in Agnostic Setting
We describe extensions of our results from Section 4 to agnostic setting and setting with a more natural hypotheses. We also prove our lower bounds.
In agnostic setting, we are given set of hypotheses = (rr,..., r0) which does not necessarily contains the input sequence r. The number of mistakes of hypothesis r' is defined as the number of time steps E (I....,T] such that rf * rt. The best hypothesis the one with the smallest number of mistakes.
26

---

// Update distribution over Predictor: At each time step t, the predictor chooses hypothesis at random according to the probability distribution produced by the HEDGE algorithm [31 18
is different from the hypothesis chosen at time / 1, there is switch to new prediction which is consistent with the previous prediction until time f and, for r = .,..., T, predictor updates π = r
We construct a sequence of loss functions as input to HEDGE: At time t, the loss of hypothesis i is I if predicts an incorrect request and 0 otherwise. At each time step HEDGE gives probability distribution ç over the hypotheses. The predictor samples a hypothesis from this distribution in the following way. Let f be min-cost flow of the probability mass from distribution e to distribution E' (i.c., Σド=1 fij = - and Ei= fo = fj). where flow fúj has cost if o j and 0 otherwise Note that the cost of this flow Enzy fiz is equal to Total Variation Distance (TVD) between 5a-1 and et. If hypothesis was chosen time 1 as sample from gt-1, then the predictor switches to hypothesis with probability fyy/5 This way, the probability of choosing, at time is
Pii chosen at t (swisihhhn to chosen at - =
1=1
and the probability of switch occurring is Eigg fu = TVD( 59), See Predictor 14 for summary.
Predictor 14: caching, agnostic setting
= In T-
// Learning rate parameter
2 w : (l...., 1), 50 w/t:
predict a hypothesis sampled from 5 for trt-= = I...., T do
for i E {l...., C s.f.
+ rt do
L u; == wi exp(1)) // loss of instance i is 1: update wy using HEDGE
: w:/: wA for each i = l,....;;
hypotheses
compute min-cost flow f from e- to g so that Ei= fij -f: the previous prediction was hypothesis i, switch to j w.p. fy/Et
The following performance bound of the HEDGE algorithm can be found, e.g., in 12 Thm 2.4]. Proposition 33. Let μz be the loss of the best of the hypotheses. Then, the expected loss of the HEDGE algorithm with learning rate parameter is
/ I M/ + Inf
-eep(-1))
The probability distribution produced by HEDGE is relatively stable. We can bound TVD(E"=1 as function of 1) and the expected loss incurred by HEDGE at time l.
Proposition 34 (Blum and Burch [10] (Thm 3)). Let gr and g² be probability distributions of HEDGE learning rate parameter y at times and respectively. Then, we have
TVD(E--1.e") sn
Σ E
Lemma 35. Let jt" be the number of mistakes of the best hypothesis. The predictor for the agnostic setting makes μ mistakes and switches in expectation, where
5 (1+11/k)
In and o 11kk+1/k²)p.
'In our situation, min-cost flow fiz can expressed using an explicit formula: we define = Et e²-1 each i.j {l..... ...., f). using notation xt == max x0.
5+
and write fy = (-6+)+ 5 Σm-
27

---

Proof. The number of mistakes made by Predictor 14 is equal to the loss achieved by HEDGE algorithm. By Proposition we have
1 S 1744 + In
exp(
We choose :- In I-1/E which is S 1/k + 1/k2, whenever k 2 4. This is to make ko knj comparable to μ.. We substitute this upper bound in 2 and get
(In 1/k )m In (1+1/k)) + klnf.
1/k
At each time step t, Predictor 14 makess switch with probability Σity fij TVD(S" By Proposition 34 the expected number of switches made by our predictor is
Σ c = Tp S (1/k+ 11/k+1/1²)p
brigfrr
since Eirier, 4 is the expected number of mistakes at time t.
Algorithm. Our algorithm follows the FitF solution recomputed at each switch. If it happens that the current request r, not served by this solution (i.c., there is a mistake in the prediction), the algorithm loads ad-hoc and removes it instantly in order to return to the FitF solution.
Algorithm 15: caching, agnostic setting
for f ,....,T do
T.
if there is a switch then
recompute r1,...,,3y Fr the FitF solution for the current prediction;
move to Zz; rf & 24 then load rz. evicting an arbitrary page, and serve r:;
return back to 24;
If the predictor makes 0 mistakes, i.e., f then r, x, never happens and this algorithm is the same as the one for the realizable case (but note that the predictor is different). If > 0, then suffers additional cost of for every mistake.
Lemma 36. Consider an imput sequence r and let OPT(r) be the cost of the optimal offline solution for this sequence. the predictor makes μ mistakes and switches during this sequence, then the algorithm above has cost at most
OPT(r) + 4p ko.
Proof. For t = I,... T, let ग. denote the prediction made for Tt at time t. Here, Tt if the predictor was right or decided to make switch. Otherwise, the predictor chose suffer mistake,
the real input was T....., Tr. the cost of the algorithm would at most OPT(T)+ by Lemma Since and differ in μ time steps, the cost of the algorithm is at most OPT(T) + ko + 2y.
Now, note that we can use the optimal solution 21...., FT for produce solution for æ of cost at most OPT(() 2/: whenever & (this can happen only if T. o rz), we evict an arbitrary page load n,, serve the request and return back to It. This implies OPT(=) S OPT(r) 24..
Therefore, the cost of our algorithm is at most
OPT(r) + 4p ko.
Theorem 37. With a class H of hypothesis, Algorithm 15 has expected cost at most
05 + (2k + 1)
where 1² denotes the minimum number of mistakes over hypotheses in and OPT the cost of the offline optimum.
28

---

Proof. By Lemma 36 and Lemma 34
the cost of the algorithm is at most
OPT(r) + + ko
+ (htl:/)))+++t)tt/t// +10-1//////---000000004111111111
+ +(1/k+ 1/13//+///>///// kike
< <PT(()) (5+ 6/k)p* + (2k: In
D.1 Achieving Robustness
We can robustify our algorithms both for the realizable and agnostic setting in the following way. We partition the imput sequence into intervals such that the cost paid by OPT in interval is 2'k. Note that we start with an empty cache and OPT 2 k on any non trivial instance: if OPPT Σ k, less than k distinct pages were requested and any lazy algorithm is optimal. In each of these intervals, first run our algorithm until its cost reaches 2' log k. Then, we switch to an arbitrary worst-case algorithm with competitive ratio Oloog k) for the rest of the time window.
Lemma 38. Consider an algorithm ALG which, given predictor making P mistakes and a switches achieves regret ap + 3ko. We can construct an algorithm ALG' which Ollog k) competitive in the worst case and its regret always bounded by O(a) + OB3
Proof. We denote G the set of intervals where ALG paid cost ALG, S 2 log k. The cost of ALG' is then
ALG'S & Σ ALG, (Oo(log 2 + 2k), S
Σ ALG. +
Σ k)) 2'k,
IEG
iEG
SCG
where 2k denotes the cost of switching to the worst-case algorithm and back ALG. This already shows that ALG' is O(log cooopettie we have ALG' < OOlog k) OPT, because OPT pays 2 in window i.
To show that still preserves good regret bounds, note that ap;; + 3ko, 2 2 k log k in each interval i & G, where o, denotes the number of switches and μ4 the number of mistakes in interval i. Therefore, we have
ALG' S ALG +0(a)) A 0(8)ko.
D.2 Extension to Next-arrival-time Predictions
In order to compute a step of FitF, we either need know the whole request sequence or, at least, times of next arrivals of the pages in our current cache. Lykouris and Vassilvitskii [32] proposed acquiring prediction of the next arrival time (NAT) of each page when requested. Precise NAT
predictions allow us simulate FitF. Lykouris and Vassilvitskii [32] Rohatgi [36], Wei [1] proposed
algorithms able use them even they are not precise.
Our result can be extended to setting where each hypothesis is not an explicit caching instance given in advance but rather a set of prediction models which generate the relevant parts of the instance over time. Consider models generating next-arrival-timm predictions, as considered by Lykouris and Vassilvitskii 32). Given the part of the sequence seen so far, they produce next arrival time of the currently requested page. Using this information, we can compute the FitF solution to an instance which fully agrees with the predictions. Moreover, we can easily detect mistakes by comparing the currently requested page with the page which was predicted to arrive at the current moment. Therefore, Theorem 7 |ndd Theorem 37 hold also with H containing models producing next-arrival-ting predictions.
D.3 Lower Bounds
Lemma 39. In realizable setting, there is an input instance and a class H. of hypotheses such that any (randomized) algorithm has regret at least log l.
Proof. Let be power of two. We use universe of pages U (1,...,21 2 and define sequences 1...., k and b = k + 1..., 2k. By concatenating a and b in specific manner, we construct building blocks of the input sequence and the hypotheses: ag = 2k and 0 = a bb Here a denotes sequence iterated & times, and both blocks are chosen to have equal length.
......24.
29

---

For each i = 1,...,,, e, we use its binary representation bib2 bloge to construct hypothesis r² 0b b²
M from blocks dg and 01 Note that for any input sequence constructed from
blocks do and 01, wc can construct an offline solution such that:
at the beginning and at the end of each block, its cache content is {L,...,k} kj.
during block 00, it keeps pages 1....,k k 1 in cache, paying k for page faults during page faults in total
sequence and 1 for loading page k, i.e.,
during block ø1, pays 2k, because it replaces the whole cache with (1- + 1,..., 2 during the first occurrence of b and then with (1,...,A) j after the last occurrence of b.
For each L.... log4, issue abb the common prefix do and 01 and compute n, the expected number of pages from {I....,k) during a since it contains 2k distinct pages. If n4 < k/2, we issue 22++ completing block du- Otherwise, we issue 1 completing block 0T
k} in the cache. Note that any algorithm has to pay at least ls
In the first case, its expected cost will be at least k: + (k n2,) > ls + k/2, because the algorithm will have at least & - n, page faults during the sequence a2k+1 at the end of ag-
In the second case, the expected cost of the algorithm will be at least k + n, h 2 2k + k/2, where k page faults are during abb, page faults during bº, and another is page faults during for ba (contains 24 distinct pages). both cases, the difference from the cost of the offline solution is at least k/2.
This way, constructed an instance j E (1....,e) with binary representation by b2 ... bog & where b; = O if n, < k/2 and b; = otherwise. Moreover, in each iteration i 1,..., log l, the algorithm pays at least by k/2 more compared to the offline solution.
Lemma 40. There is deterministic algorithm which, given predicted request sequence with mistakes achieves regret smaller than p..
Proof. We construct a predicted instance ((I, k (), k), 1...., k))" which is given to the algorithm ALG. We construct real instance which constructed online based on ALG's decisions.
For any iteration 1, .,..., n, we build a corresponding part of the real instance which differs from the predicted one in at most one request and show that ALG has one more page fault compared to a described adversarial strategy ADV which starts and ends each iteration with cache content k).
First, any algorithm has page fault during kk 0) because + 1 distinct pages are requested, so both ALG and ADV pay 1. At the moment when 0 is requested, ALG must be missing some page from p [1,.... ... J. If 1, ADV evicts l instead and the real request sequence continues with (2.... - 1, instead of (2..... k), causing single mistake in the prediction. ALG has page fault during this part, while ADV has no page fault. If e {2. real request sequence continues as predicted without any mistake, causing a page fault to ALG, while
k}, ADV evicts and the
ADV has no page fault. the last part (0, 1...., k), both AL.G and A ADV have page fault. So, AL. had at least 3 page faults while ADV only 2, and there was at most one mistake.
Therefore, the total cost of ALG is at least 3n while ADV pays 2n. Since y n, the regret of ALG is at least
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
way of designing algorithms and that this way can be used to design simple algorithms with performace better and comparable the previous works. We discuss the novelty of our approach in the introduction and the bounds achieved by algorithms using our approach are discussed in Section 2
Justification: Main claim made in abstract is that propose
Guidelines: Section contains formal statements of our theoretical results which match with content of abstract and introduction.
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: This a theoretical work and we state our results including all assumptions required for their validity. Our results states the performance bounds of our algorithms in terms of regret and competitive ratio, as common in the areas of online algorithms and online learning. We do not discuss the running time of our algorithm, since this is not the subject of research in these areas.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use
31

---

their best judgment and recognize that individual actions in favor of transparency play an important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide formal statements of all results including all assumptions needed for their validity. We also provide formal proofs of all our results including references to utilized results from the literature.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA]
Justification: This paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
32

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This paper does not include any experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (lttps://nnps..cc/pp
olic/guides b www.eeeSummiiiiiiooooo.ooooooooo
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. http:/cccppccgguuuuuueeee httts///uiidessoeeeuuuumiiii wtwpdd//o/ooeetuiiisiiioooo
asionPolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: This paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
33

---

The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htttppps//eaurrpsscc//pubb.iieee
Answer: [Yes]
Justification: This is theoretical research which does not involve processing any data and does not involve any human participants.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consideration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This theoretical research proposing new research directions. We do not expect any direct societal impact.
34

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This work does not release any code nor data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This work does not use any existing code, dat, nor models. Previous theoretical results which are used in this paper are well cited and credited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
35

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswi thcode. com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not introduce nor release any assets in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
36

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "s7DDhqBnJp", "reviewer": "Reviewer_qEgX", "summary": "The paper studies three online algorithms in the learning augmented model: caching, load balancing, and non-clairvoyant scheduling. The goal seems to be to 'online learning' flavored learning-augmented algorithms. Rather than having a single predictor that synthesizes or predict something about the online input, the authors propose a framework where we have access to a large class of hypothesis such as the set of all past inputs. The goal is to be competitive with respect to the best hypothesis for the online input in hindsight. For example in the caching problem, the hypothesis are a large set of input sequences, and the goal is to get close to OPT in the case that the online sequence is actually one of these inputs in our set of hypothesis. In the cases where the online input is not part of the set of hypothesis, the authors obtain error guarantees depending on the hamming distance of the online input and the closest one in the hypothesis.\n\nFor the problems studied, the authors match or improve upon (in some parameter regimes) prior works which can be interpreted to be in their framework.", "questions": "- Can the authors clarify the n^(5/3) issue?", "limitations": "No societal consequences.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The motivation of the formulation is natural: having access say to the entire history of past inputs could allow one to directly learn the best predictor from data\n- The framework matches the best bounds for load balancing, and improves the caching result.", "weaknesses": "- The $n^(5/3)$ additive error for non-clairvoyant scheduling  seems to be a meaningless guarantee, since there are $n$ jobs which are assumed to have maximum job length $1$. So any scheduling guarantees that the jobs will finish in $n$ time. \n- The algorithms, for example for caching, must iterate over the entire set of hypothesis every time, which seems quite inefficient. \n- I'm also not sure if the formulation exactly captures the motivation of directly learning a good predictor from data. For example in caching, the performance seems to be 'bottle-necked' by a single past instance in the set of hypothesis, in the sense that we can only ever expect to do as good as the 'most similar' input in our set of past inputs. Rather, it would be more natural if one would learn from all of them simultaneously (so for ex 'learn' something from the first half of one past input and the second half of another). This is not the fault of their algorithms (which already achieve close to optimal performance), but rather the formulation itself. This is why I still think the standard prediction framework maybe more natural since a predictor can learn to synthesize information and implicitly combine different aspects of different past inputs seen, rather than relying on a single past input alone. \n- There are no experiments, even simple synthetic ones. It would be interesting to see even in synthetic case if the framework can actually be carried out.\n- There are no algorithms in the main body and it is hard to judge algorithmic improvements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback.\nHowever, their claim about our performance bound for non-clairvoyant scheduling being meaningless is incorrect. We study non-clairvoyant scheduling with the classical objective of\nminimizing the *sum* of completion times which has a different magnitude than the length of the schedule (or makespan).\nIn particular, if all jobs have size 1 and the length of the schedule is $n$,\nas the reviewer suggests, then the sum of completion times is about $n^2$. \nOur regret bound is of order $n^{5/3}$, i.e. it is sublinear.\n\n> The algorithms, for example for caching, must iterate over the entire set of hypothesis every time.\n>\n> It would be more natural if one would learn from all of them [hypotheses] simultaneously (so for ex 'learn' something from the first half of one past input and the second half of another).\n\nOur paper describes a basic framework, and we focused mainly on the approximation guarantees and not on other (important) resources such as running time. However, our framework does allow for optimization of other desired resources. For example, to avoid the need of iterating over all hypotheses in caching, we can replace HEDGE in our predictor by a suitable algorithm for the bandit setting like EXP4 (which considers a single hypothesis in each time-step). Similarly, if we want to capture inputs partitioned into several intervals,\neach resembling different hypothesis, we can use, for example, the classical SHARE algorithm\ninstead. Furthermore, our analysis readily implies how the regret guarantees of these algorithms (e.g. EXP4 or SHARE) translate to approximation guarantees of the implied learning-augmented online algorithm.\n\nWhile in some scenarios it might be the case that the black-box predictor satisfies the two properties pointed out by the reviewer, in other scenarios it might not. Our framework allows to optimize and analyze the predictor explicitly towards achieving these properties and other desired properties.\n\n> There are no experiments, even simple synthetic ones. It would be interesting to see even in synthetic case if the framework can actually be carried out.\n\nOur work is proposing a new theoretical framework for modeling of learning augmented algorithms. We have decided to focus on theoretical analysis. Experimenting with our framework is an interesting direction for future research.\n\n> There are no algorithms in the main body and it is hard to judge algorithmic improvements.\n\nWe have tried to informally convey the main ideas behind our algorithms in the main body. However we will try to further clarify these in subsequent versions (and welcome any suggestions toward this end).", "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": "", "extra_scores": {}}, {"review_id": "xW9gXjGxvY", "reviewer": "Reviewer_B3ME", "summary": "This paper considers a new formulation for learning-augmented algorithms/algorithms with predictions and applies it to the fundamental problems of online caching, online load balancing, and non-clairvoyant scheduling.  In the new formulation, the predictions/predictor is made more explicit and is a part of the solution process.  The predictions are given by a hypothesis class ${\\cal H}$ of size $\\ell$, which contains information about the \"plausible instances\" we are trying to solve.  One can think of ${\\cal H}$ as coming from past data and the goal is to use this information to get improved algorithms.  This is done in two settings: the realizable and agnostic settings.\n\nIn the realizable setting, the true instance is realized in ${\\cal H}$, so we can compare to the optimal cost in hindsight.  For this, the paper provides algorithms with the following bounds:\n\n - Caching: ${\\rm OPT}+ k \\log \\ell$\n - Load Balancing: $O(\\log \\ell \\cdot {\\rm OPT})$\n - Non-clairvoyant scheduling: ${\\rm OPT} + \\ell \\sqrt{ 2 \\rm OPT}$\n\nIn the agnostic setting, the true instance may not be realized in ${\\cal H}$, so instead we compare to the best hypothesis in ${\\cal H}$.  For this, the paper provides algorithms with the following bounds:\n\n - Caching: ${\\rm OPT} + O(\\mu^* + k \\log \\ell)$\n - Load Balancing: $O( \\mu^* \\cdot \\log \\ell \\cdot {\\rm OPT})$\n - Non-clairvoyant scheduling: ${\\rm OPT} + \\mu^* +  O(n^{5/3} \\log \\ell)$\n\nwhere in each, $\\mu^*$ is a problem-dependent notion of distance from ${\\cal H}$ to the true instance.\n\nSome lower bounds are given showing tightness or almost-tightness for these results.", "questions": "- To what extent can these techniques be generalized?  E.g., what can be said about $k$-server?\n\n - Only the case of finite ${\\cal H}$ is considered.  Can anything be said about infinite but \"low complexity\" ${\\cal H}$?", "limitations": "Limitations and assumptions have been made clear.  Potential negative societal impacts from this work are very unlikely.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "This paper gives a very different approach to learning-augmented algorithms that is interesting and has the potential to generate more ideas.  While the algorithms once given the predictions are simple (they are all essentially some notion of follow-the-prediction), this work shows that these simple algorithms can work well if fed carefully constructed predictions (given by the prediction algorithms designed in this paper).  Lower bounds are given showing that the results are somewhat tight.", "weaknesses": "- I think it would help the presentation to give examples of hypothesis classes to make the main conceptual idea more clear and provide a stronger connection to practice.\n\n- There is no experimental evaluation.  While some works in this area lack an experimental evaluation, there is a standard setup that has been used for the caching problem by Lykouris and Vassilvitskii [32] as well as Antoniadis et al. [4].  Providing such an evaluation could elucidate the construction of hypothesis classes and provide further evidence in favor of this paper's approach.\n\n- The writing has some awkward phrases and grammar throughout, e.g. the following (among others):\n\n   - line 62 \"... will be much smaller then ...\" -> \"... will be much smaller than ...\"\n   - lines 107-108 \"... using arguably simpler approach ...\" -> \"... using an arguably simpler approach ...\"\n   - lines 306-307 \"... under certain assumptions about input.\" -> \"... under certain assumptions about the input.\"\n   - lines 374-375 \"In offline setting, ...\" -> \"In the offline setting, ...\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive words and for their useful suggestions\nto improve our manuscript.\nWe respond the questions of the reviewer explicitly.\n\n> To what extent can these techniques be generalized? E.g., what can be said about -server?\n\nOur framework can be extended to $k$-server, even to any Metrical Task System (MTS).\nIn the lines of our results on caching, we can obtain the following bounds.\nIn the realizable case, where one of the hypothesis is the input sequence itself,\nwe can achieve regret $O(D\\ln \\ell)$, where $D$ is the diameter of the metric space.\nIn the agnostic case, we can obtain regret $O(D\\mu^* + D\\ln \\ell)$,\nwhere $\\mu^*$ is the number of mistakes in the best hypothesis, where a mistake\nis considered each time the predicted request (or cost function) is not\nexactly the same as the real one.\nOur paper is already quite dense and adding MTS and k-server requires several additional definitions. We tried to illustrate the framework without making it too hard to read.\n\n> Only the case of finite $H$ is considered. Can anything be said about infinite but \"low complexity\" $H$?\n\nThe case of infinite hypothesis classes with low complexity of some kind is very interesting. This is a great direction for future work.\n\n> There is no experimental evaluation.\n\nOur work is proposing a new theoretical framework for modeling of learning augmented algorithms. We have decided to focus on theoretical analysis. Experimenting with our framework is an interesting direction for future research.", "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": "", "extra_scores": {}}, {"review_id": "f7xWOdJIvr", "reviewer": "Reviewer_1P4N", "summary": "This paper proposes a new framework to use machine learned predictions to improve online algorithms. Recent work that has done this (in a slightly different framework) goes under the name learning-augmented algorithms (LA algorithms) or algorithms with predictions. The main difference in this work compared to the usual LA algorithms is that these authors propose integrating the learning problem into the algorithmic problem by allowing the algorithm to adaptively update its prediction based on the new information it receives. Additionally, instead of maintaining a single prediction, this framework maintains a hypothesis class of information about the instance. The paper exemplifies this framework on caching, online load balancing, and online non-clairvoyant scheduling. For all 3 problems they study a realizable and agnostic setting, where in the realizable setting, the hypothesis class contains h(I) for I the actual underlying offline instance, and in the agnostic setting, the information corresponding to the true offline instance is not necessarily in the class.", "questions": "- How do you see this framework allowing us to understand the complexity of problems (from a beyond-worst case analysis perspective) in a better way than the standard LA algorithms framework or other beyond worst-case analysis frameworks? In other words, how does the ability to (1) have a hypothesis class of information for the prediction and (2) update the prediction allow us to further surpass worst case lower bounds?\n- It’s unclear to me how large the hypothesis class should be. You get this trade off in the agnostic setting between having a large \\ell should lead to smaller \\mu^* indoor bounds, or a small \\ell might imply larger \\mu^*. Have you thought at all for the problems you study about how you can balance these? \n- A few times, you mention something like “each hypothesis h(I) provided sufficient information about the instance in order to determine an offline optimal solution OPT(I)”. This statement cannot be literally true, as you study a problem whose offline version is NP hard. I think you mean something like, h(I) provides sufficient information about the instance in order to find an offline solution \\alpha OPT(I) for alpha the apx factor, and then alpha comes into your completive ratio or regret bound.\n- Something seems weird in the appendix, section B.1 and C.1 have the exact text repeated. It seems B.1 is maybe a totally unnecessary section.", "limitations": "yes", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This framework could indeed be a better way to study algorithms with predictions. In combining the learning process with the algorithmic procedure we get the benefit of (1) demystifying how the prediction is obtained and (2) allowing ourselves the flexibility of updating the prediction as we receive new information about the input.\n- Using this more all-encompassing approach, the framework is able to improve upon some bounds from LA algorithms. \n- The authors did a good job in the related work differentiating their model from that on algorithms with a prediction pf portfolios, as well as data driven algorithms.", "weaknesses": "The algorithms proposed are augmenting simple procedures with this richer, more flexible hypothesis class, and the analyses involved are very straightforward. This isn’t inherently a bad thing. But there is a lot of work in the LA algorithms scene lately, and the work that stands out to me the most is the work that highlights some interesting technicality of the problem that wasn’t understood through classic worst-case analysis approaches. I’m afraid the problems that this model has been applied on did not result in technical components that stood out, and thus could lead to this paper blending into an already noisy scene. I will leave more specific related questions that may address this fear under “questions”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. Most (if not all) works on learning augmented algorithms solve some learning problem in an ad-hoc manner by assuming a black-box access to some predicitions. In our framework, we \"open the box\" and define the learning problem explicitly. This allows for a deeper and methodical integration of results from learning theory in learning-augmented algorithms, and as we demonstrate, gives rise to simple and clean algorithms with better performance bounds than previous works. We hope that our \"white-box\" perspective will inspire further work.\n\n> how does the ability to (1) have a hypothesis class of information for the prediction and (2) update the prediction allow us to further surpass worst case lower bounds?\n\nWe use hypothesis classes to model the learning problem (as is standard in learning theory). Thus, when the input is compatible with one of the hypothesis in the class, our algorithms can outperform algorithms in the standard learning augmented framework.  This can be illustrated by a simple example of a bi-modal input: there are only two possible scenarios, and there is no single set of pre-computed predictions which works well for both.  In our framework, we can learn the actual input sequence while processing it and then apply the approriate set of predicitons. As illustrated in the paper, this idea naturally extends to more than just two inputs and as well as to noisy scenarios.\n\nSimilar situations happen in other frameworks of beyond-worst case analysis. For example, the input may be stochastic in the first scenario\nwhile possessing some specific pattern in the second scenario.\n\nOne might argue that the argument above does not apply to problems like caching, where previous works did consider predictions that are generated over time. As noted by reviewer qEgX, in such a setting, the predictor may adapt its predictions based on the part of the input seen so far. Our framework captures this in a principled way which allows\ntheoretical analysis of such adaptability without committing to specific ad-hoc predictions.\n\n> It’s unclear to me how large the hypothesis class should be.\n\nIn principle, the hypothesis class reflects prior knowledge the algorithm design has on the learning problem. In practice the class can be determined e.g. using collected statistics of past inputs.\nOur framework is effective when one can indeed define a restricted hypothesis class which can capture the regularities in the inputs. (Otherwise we are back in the classical worst-case setting where any input is possible.)\n\nOur framework allows one to try and reduce the size of the hypothesis class by ``clustering'' the hypotheses. Indeed this is likely to increase the distance of the actual input to the class.  We specify the performance as a function of the size of the class and the maximum distance of an input to the class. Studying the relation between these parameters for specific applications is a nice direction for further research.\n\n> A few times, you mention something like “each hypothesis h(I) provided sufficient information about the instance in order to determine an offline optimal solution OPT(I)”. This statement cannot be literally true, as you study a problem whose offline version is NP hard. \n\nWe mean that $h(I)$ contains enough information to determine an offline optimal solution. We do not require that this could be done in polynomial time nor use it to compute an optimal solution: e.g. our algorithm for load balancing uses $h(I)$ to compute an approximate solution in polynomial time.\n\nThank you for pointing out that B.1 and C.1 are repeated. We will fix this.", "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": "", "extra_scores": {}}, {"review_id": "Pozfclz2WM", "reviewer": "Reviewer_oKpi", "summary": "The paper introduces a new framework for learning-augmented online algorithms. Learning-augmented algorithms (aka algorithms with predictions) are a very active subfield of beyond worst-case algorithm analysis. For online algorithms, which cope with uncertainty on their input, it gives an algorithm an addition information in form of a prediction. This prediction can be the (unknown) online instance or any other form of additional information. A learning-augmented algorithm is usually analyzed w.r.t. the quality of the given prediction.\nIn the most commonly used setup for online algorithm, the prediction is assumed to be generated upfront from some black-box predictor, or arrives online together with requests. There are also models where multiple predictions are initially available to an algorithm.\nThe authors of this paper introduce a new framework which integrates both the predictor and the learning-augmented algorithm. \nThe main motivation is that a predictor might update its prediction while the online instance is being revealed, and, thus, increase the prediction's quality over time. \nIn their model, they assume that there are given a set of hypotheses, which can be thought of different characteristics which the coming input could have. \nThe predictor can compute at any time a new prediction using these hypotheses and the input which has been revealed up to that time.\nThe authors distinguish between two settings: the easier \"realizable\" setting, which assumes that the hypothesis which corresponds to the actual input is contained in the hypotheses class, and the harder \"agnostic\" setting, which does not make this assumption.\nThe authors then apply this framework to three well-studied online problems in the learning-augmented area: caching, load balancing and non-clairvoyant scheduling. Some of their new bounds improve over previous work.", "questions": "- As far as I understand it one can model the traditional black-box setting via the agnostic setting by using a singleton hypothesis class and the 'traditional' prediction error as loss. Is this true? I am not sure if I missed this, but I think this could also be an interesting insight.\n\n\nFurther comments:\n- Line 1140: there is a comma before the second inequality.", "limitations": "As far as I see, all limitations have been properly addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper introduces an interesting generalization of the traditional learning-augmented framework. I think that this new view on learning-augmented algorithm can have an impact on this rapidly evolving field, since it untangles concepts which have already been used partially. I also appreciate the clear structure of the framework into predictor and algorithm.\n- The framework is conceptually well motivated and the authors show that it can be applied to at least three different and well-studied problems, which proves that it is practicable and can be used for relevant problems.\n- The authors present improved guarantees for previously well-studied online problems.", "weaknesses": "- A minor weakness can be the algorithmic novelty for the concrete applications. It seems that the algorithms follow in many cases the predictions given by the predictor. The predictors are tailored to the specific applications and are also rather simple.\n- Another minor weakness is the close relation to the established 'multiple prediction' setting. From my understanding, one can see the hypothesis class the set of given predictions, and the goal (in the agnostic setting) is to guarantee a bound w.r.t. the best one.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for highlighting the positive aspects of our work and pointing out a typo.\n\n> As far as I understand it one can model the traditional black-box setting via the agnostic setting by using a singleton hypothesis class and the 'traditional' prediction error as loss. Is this true?\n\nYes, the classical setting of learning-augmented algorithms is indeed subsumed by the case where the hypothesis class contains only a single hypothesis. We will make sure to clarify this in the final version of our manuscript.\n\n> A minor weakness can be the algorithmic novelty for the concrete applications.\n\nIn our framework, we achieve better bounds than the works on multiple black-box predictions using simpler algorithms (e.g. see our results for non-clairvoyant scheduling and caching).\nThis can be viewed as a strength rather than a weakness. Moreover, the idea of separating the learning and algorithmic parts is novel.\n\n> Another minor weakness is the close relation to the established 'multiple prediction' setting.\n\nOur setting is able to model the established 'multiple prediction' setting. However, our setting is more general and flexible. As can be seen from our results, it naturally leads to clean and simple algorithms which we find important.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of online learning in the learning augmented model, focusing on the problems of caching, load-balancing, and non-clairvoyant scheduling. The authors propose a model where the learner has access to an underlying hypothesis class that it can use to augment it's prediction. The authors provide algorithms (often following existing algorithmic frameworks such as exponential weights) that exploit these predictions and give improved results compared to existing works considering such augmentations.

The reviewers felt this work provided a new approach to LA algorithms. There were some common concerns about the structure of the paper - eg, the fact that no algorithms are included in the body of the work. I share this concern, and I think at least one full concrete example (say for caching) should be included in the main body.
Decision: Accept (poster)