Learning-Augmented Algorithms with Explicit Predictors

Authors: marek  eliáš
haim  kaplan
yishay  mansour
shay  moran
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 15:21:37

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.

Main paper: 
 introduction: 
 We study online algorithmic problems within the realm of learning-augmented algorithms. A learning-augmented algorithm possesses the capability to work in conjunction with an oracle that supplies predictive information regarding the data it is expected to process. This innovative approach has been discussed in landmark studies by Kraska et al. [2018] and Lykouris and Vassilvitskii [2021] , 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 at hand, which could presumably be learnt from historical data. Predictions might include, for instance, the anticipated next request time for a page in a caching problem or the expected duration of a job in a scheduling task. These predictions are accessible either before or together with the online requests, allowing the algorithm to 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 it never underperforms the baseline achievable without predictions.Despite the elegance of these results, several important aspects were neglected: the 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 a good performance in such setting requires a learning component in the algorithm which discerns between the festive and week-day input 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., 2022 , Emek et al., 2021 , Anand et al., 2022 , Antoniadis et al., 2023] , where a switch between algorithms is made after incurring a high cost.Our approach goes one step further. It is based on 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 a set of descriptions of past input instances. Each description offers specific statistics 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 a set of hypotheses, where each hypothesis, h(I), 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(I) 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 to 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(I) provides sufficient information about the instance in order to determine an offline optimal solution OPT(I).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 h(I) ∈ 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 |H| = 1 captures the (usual) setting of ML-augmented algorithms with a 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. 1 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 (H) and the part of the input seen so far. Its goal is to produce the best prediction for the instance at hand which could be a 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 a learning task which is associated with the algorithmic problem at hand. For example, the learning task associated with caching is a 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 on the overall performance of the algorithm.We consider this new way to model a setting of "online algorithm with predictions" as one of our core contributions (in addition to the algorithms for the specific problems that we describe below). In a sense, our technique interpolates in an interesting way between the learning challenge (from historical data) and the algorithmic challenge, while addressing both of them.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 offline optimal solution instead of a multiplicative competitive ratio. For load balancing, we achieve a competitive ratio with logarithmic dependence on the size ℓ of the hypothesis class. Our results are summarized in Figure 1 , 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 I is close to some hypothesis in H. This ensures that there is some structure in 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. [2022] ), and better performance on instances composed of several parts, each resembling a different hypothesis (see [Anand et al., 2022 , Antoniadis et al., 2023] ).Recent works by Dinitz et al. [2022] and Emek et al. [2021] consider algorithms with access to a portfolio of predictors trying to achieve performance comparable to the best one. Our results can be interpreted in their setting by considering the output of each predictor in the portfolio as a hypothesis. We achieve comparable and sometimes better results (see Figure 1 for comparison) using an arguably simpler approach, separating the learning and algorithmic part and solving them separately.Organization. Section 2 describes our main contributions including the description of the problems studied and the approach which leads to our results. The survey of the related literature in Section 3 is followed by a warm-up in Section 4 containing an exposition of our approach on caching in realizable setting. The main technical part of our paper is in Appendix. Appendix B considers the load balancing problem and Appendix C the non-clairvoyant scheduling problem. We conclude our paper with treatment of caching in agnostic setting in Appendix D. 
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 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.In the caching problem, the input is a sequence of page requests. The online algorithm holds a cache of size k, and it 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 offline 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 r 1 , r 2 , ..., r T . In each round t, the predictor presents a prediction for all remaining requests in the sequence π t , π t+1 , ..., π T . At the conclusion of the round, the predictor sees r t and incurs a loss of 1[π t ̸ = r t ] if the prediction was incorrect. After observing r t , the predictor can choose to alter the subsequent predictions to π ′ t+1 , ..., π ′ T . Each time the predictor decides to modify the predictions, a switching cost of k is incurred (remember that k ≥ 1 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 k log ℓ (recall that ℓ = |H|). 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 an input sequence r 1 , . . . , r T produces a caching policy which is simultaneously optimal for all prefixes r 1 , . . . , r t for t ≤ T . Fortunately, Belady's FitF algorithm has this property, as outlined in Observation 4.For the agnostic setting, we design a randomized predictor with a maximum total loss of O(µ ⋆ + k ln ℓ), where µ ⋆ is the Hamming distance of the actual input sequence from the class H. This predictor utilizes a multiplicative-weight rule [Littlestone and Warmuth, 1994] , and its learning rate is specifically adapted to achieve the optimal balance between the cost of changing predictions (switching costs) and the inaccuracies in the predictions themselves (prediction errors).Our final caching algorithm incorporates a predictor for this problem in such a way that at each round t, it applies Belady's FitF algorithm to the predicted suffix of the sequence π t , ..., π T . 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 a hypothesis class of size ℓ and I be an input instance with offline optimum value OPT(I). There is a deterministic algorithm for the realizable setting (i.e., I ∈ H) which has cost at most OPT(I) + k log ℓ. There is a randomized algorithm for the agnostic setting with expected cost at most OPT(I) + (5 + 6/k)µ ⋆ + (2k + 1) ln ℓ, where µ ⋆ is 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 O(log k) OPT(I) while loosing only a constant factor in the dependency on µ ⋆ and ln ℓ in our additive regret bound, see Section D.1 for details. Note that the previous methods used to achieve robustness for caching usually lose an additive term linear in OPT(I), 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 a complete instance, is a set of parameters of some prediction model producing next-arrival predictions. In Section D.3, we show that the dependency on ℓ, k, and µ ⋆ in Theorem 1 cannot be improved by more than a constant factor. Our result is an improvement over the O(µ⋆ + k + √ T k log ℓ) regret bound of Emek et al. [2021] whenever T = ω(k log ℓ).In online load balancing on unrelated machines, we have m machines numbered from 1 to m and a total of n jobs. The jobs arrive sequentially, and the objective is 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-dimensional vector p. 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 an 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 is sufficiently described 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 a makespan that is at most twice the makespan of the optimal schedule.The learning problem that arises in this context of makespan minimization is 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 p that are expected to arrive. The predictor maintains a prediction that includes an upper bound, denoted as n p , 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 error occurs when the actual number of jobs of a particular type exceeds the predicted upper bound n p . 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 n p 's). The cost of such a modification is the makespan associated with the new prediction. 2Hypotheses. 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 p it assigns a number f p ∈ [0, 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 f p can be estimated by past statistics. With the knowledge of the correct hypothesis f , we are able to produce an integral assignment of jobs to machines at a low cost. Previously studied machine-weight predictions [Lattanzi et al., 2020 ] allow producing a fractional assignment which requires a costly rounding procedure [Li 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 a simple randomized predictor, ensuring that the total expected loss is at most O(OPT(I) • log ℓ) (recall that ℓ = |H|), where OPT(I) represents the makespan of the input instance I. 3 The key idea is 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 n p of each type. The randomized predictor maintains a random hypothesis consistent with the processed jobs. Whenever one of the predicted counts n p is violated, the predictor switches to a randomly chosen consistent hypothesis from H, resembling the classical randomized marking strategy in caching [Fiat et al., 1991] .We additionally present a deterministic predictor with loss of at most O(OPT(I) • log(|H|) • log τ ), where τ 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 n 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 τ ). 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 n p 's. 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 a deterministic and randomized predictor respectively which, given a hypothesis class H of size ℓ and an instance I with makespan OPT(I), satisfy the following. In the realizable setting (i.e., h(I) ∈ H, where h(I) is the distribution corresponding to I), they produce a schedule whose makespan is at most O(log ℓ log τ OPT(I)) and O(log ℓ OPT(I)) 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 at most O(αβ log ℓ log τ OPT(I)) and O(αβ log ℓ OPT(I)) in expectation, respectively, where α and β describe the multiplicative error of the best hypothesis f ⋆ ∈ 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 a job type p such that f p ̸ = 0 and f ⋆ p = 0, we define α := n + 1, where n denotes the number of jobs in the input instance. Otherwise, we defineα := max{f p /f ⋆ p | f ⋆ p ̸ = 0}.Similarly, if there is a job type p such that f p = 0 and f ⋆ p ̸ = 0, we define β := n + 1. Otherwise, β := max{f ⋆ p /f p | f p ̸ = 0}. We have α, β ≤ n + 1. Our algorithms can be robustified so that their competitive ratio 4 is never larger than O(log m) (the best possible competitive ratio in the worst-case setting [Azar et al., 1992] ), 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. Dinitz et al. [2022] showed how to aggregate outputs of ℓ algorithms into a single fractional solution, loosing a factor of O(log ℓ) compared to the best of the algorithms. A fractional solution can be rounded online, loosing a factor of Θ log log m 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 ℓ algorithms, preserving integrality of their solutions, see Section B.6.We consider a non-clairvoyant scheduling problem in which a single machine is assigned the task of completing a set of n jobs, denoted as j 1 , j 2 , . . . , j n . The jobs are released at time 0 and the scheduler's objective is to 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 to preempt a job before it 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 is then rescheduled for completion at a later time. Round-Robin algorithm is 2-competitive and this is the best competitive ratio achievable in non-clairvoyant setting in the worst case [Motwani et al., 1993] .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, we adopt a similar approach to 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 a different methodology which is more in line with statistical learning. We use here a weaker type of hypotheses: each hypothesis is a 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 π of the n jobs.Each permutation π is associated with a loss 5 which reflects the performance of a scheduler that follows the order suggested by π. In particular, the loss is defined in such a 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.In order to avoid scaling issues, we formulate our guarantees for instances with maximum job length at most 1. 6Theorem 3 (Completion Time). Consider an input instance I, let OPT(I) denote the offline optimal value of its total completion time objective, and let H be a hypothesis class of size ℓ. We assume, without loss of generality, that the maximum job length in I is at most 1. Then, there is a deterministic algorithm which achieves total completion time at most OPT(I) + ℓ 2 OPT(I) in the realizable setting (i.e., I ∈ H). In the agnostic setting, there is a randomized algorithm that with high probability achieves total completion time of at most OPT(I)+µ * +O(n 5/3 log 1/3 ℓ), where µ * is the difference between the total completion time of the best hypothesis in the class and OPT.Note that the value of OPT(I) is quadratic in n unless the size of a vast majority of jobs in I is either 0 or vanishing as n grows.We have also found an unexpected separation: there is an algorithm for the realizable setting with regret at most n log ℓ on input instances containing jobs of only two distinct lengths (Section C.1). On the other hand, there is no algorithm with regret o(ℓn) on instances with at least three distinct lengths (Section C.3). Dinitz et al. [2022] showed the following. For any ϵ > 0, there is an algorithm which achieves expected total completion time (1 + ϵ) OPT +O(1/ϵ 5 )µ * under certain assumptions about the input. Therefore, their bound always gives a regret linear in OPT and a higher dependency on µ * . Any algorithms can be robustified by running it at speed (1 -δ) simultaneously with the Round Robin algorithm at speed δ. This way, we get O(δ -1 )-competitive algorithm in the worst case, because the schedule produced by Round Robin is 2-competitive with respect to the optimal schedule processed at speed δ. Dinitz et al. [2022] used the same approach to robustify their algorithm, incurring the factor 1 1-δ on top of their bound quoted above. This procedure unfortunately worsens the performance of the original algorithm by a constant factor, i.e., such robustification of our algorithm achieves additive regret only with respect to 1 1-δ OPT(I).Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: This is 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 no 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 a 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 on 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community.Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
related work: 
 The closest works to ours are by Dinitz et al. [2022] and Emek et al. [2021] . Dinitz et al. [2022] 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 O(log ℓ)-competitive algorithm which combines solutions of ℓ prediction-based algorithms into a fractional solution. A fractional solution can be rounded online, incurring an additional multiplicative factor of Θ( log log m log log log m ) 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 a large contribution to OPT. Their algorithm achieves a total completion time of (1 + ϵ) OPT +O(ϵ -5 )µ * for any ϵ > 0, where µ * denotes the difference between the cost of the best available prediction and the cost of the offline optimum.[2021] study caching with ℓ 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 ℓ 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 a 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 + √ T k log ℓ),where T is the length of the sequence, k is the size of the cache, and µ * is 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., o(k log ℓ).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 is 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 a hypothesis class of size 1. For caching, these are [Lykouris and Vassilvitskii, 2021 , Rohatgi, 2020 , Wei, 2020 , 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 Other related papers are by Bhaskara et al. [2020] who studied online linear optimization with several predictions, and [Anand et al., 2022 , Antoniadis et al., 2023] who designed algorithms competitive with respect to a 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 et al., 2022] and offline [Balcan et al., 2021] . The main difference from our work is that they learn the prediction before solving the input instance while we learn the prediction adaptively as we gain more information about the input instance. Since the seminal papers of Lykouris and Vassilvitskii [2021] and Kraska et al. [2018] , 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 a 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 is 2-competitive and that this is the best possible competitive ratio. Azar et al. [1992] proposed an O(log m)-competitive algorithm for online load balancing on unrelated machines and showed that this is the best possible. In the offline setting, Lenstra et al. [1990] proposed a 2-approximation algorithm and this remains the best known algorithm. There was a recent progress on special cases [Svensson, 2012, Jansen and Rohwedder, 2017 ].Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: We provide formal statements of all our 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 crossreferenced. • All assumptions should be clearly stated or 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 to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
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, we have a universe of pages U , a cache of size k and its initial content x 0 ∈ U k . As it is usual, we assume that U contains k "blank" pages b 1 , . . . , b k which are never requested and x 0 = {b 1 , . . . , b k }, i.e., we start with an empty cache. We receive a sequence of requests r 1 , . . . , r T ∈ U \ {b 1 , . . . , b k } online. At each time step t, we need to ensure that r t is present in the cache, i.e., our cache x t ∈ U k contains r t . If r t / ∈ x t-1 we say that there is a page fault and we choose x t ∈ U k such that r t ∈ x t . This choice needs to be made without the knowledge of the future requests.We measure the cost of a solution to a caching instance by counting the number of page loads (or, equivalently, page evictions) performed when transitioning from x t-1 to x t at each time t = 1, . . . , T . Denoting d(x t-1 , x t ) = |x t \ x t-1 |, the total cost of the solution x = x 1 , . . . , x T iscost(x) = T t=1 d(x t-1 , x t ).Offline algorithm FitF. An intuitive offline optimal algorithm FitF was proposed by Belady [1966] : if there is a page fault at time t, it evicts a page from x t-1 which is 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 r 1 , . . . , r T . For any t ≤ T , the cost incurred until time t by FitF algorithm for sequence r 1 , . . . , r T is the same as the cost incurred by FitF algorithm for sequence r 1 , . . . , r t .To see why this observation holds, it is enough to notice that the solution produced by FitF on r 1 , . . . , r T until time t is the same as the solution of FitF on r 1 , . . . , r t which breaks ties according to the arrival times in r t+1 , . . . , r T .Learning task. In the realizable setting, we are given a class H of ℓ hypotheses r 1 , . . . , r ℓ ∈ U T such that the actual input sequence of requests r 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 a predicted sequence π = π 1 , . . . , π T . This predictor makes a small number of switches (changes to π) until it determines the correct hypothesis. Second, we design an algorithm which uses an access to such predictor and its performance depends on the number of switches made by the predictor.Predictor. Our Predictor 1 below is based on a majority rule. It maintains a set A of all hypotheses (sequences) in the class H which are consistent with the past requests. In time t = 1 the set A is initialized to be the entire class, i.e. A = H, and it is updated whenever the current request r t differs from the predicted request π t (i.e., when there is a prediction error). The prediction π used by our predictor is defined based on the set A as follows: We set π t := r t and, for τ = t + 1, . . . , T , we choose π τ to be the request agreeing with the largest number of hypotheses in A. This way, the predicted sequence π is modified exactly after time-steps t when π t ̸ = r t , and whenever this happens at least half of 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 A is never empty. This implies the following lemma: Lemma 5. In realizable setting, Predictor 1 with a class H of ℓ hypotheses makes σ ≤ log ℓ switches and the final prediction is consistent with the whole input.Predictor 1: Majority predictor for caching in realizable setting for t = 1, . . . , T do if t = 1 or prediction π t differs from the real request r t then // make a switchA := {i ∈ {1, . . . , ℓ} | r i τ = r τ ∀τ = 1, . . . t} ; // consistent hypotheses update π t = r t and π τ = arg max p∈U |{i ∈ A | r i τ = p}| for each τ = t + 1, . . . , T ;Algorithm. Our overall algorithm (See Algorithm 2) uses Predictor 1 and maintains the FitF solution x 1 , . . . , x T ∈ U k for the current prediction π at time t. Then it changes the cache to x t . This solution needs to be recomputed whenever π is modified.Algorithm 2: caching, realizable setting for t = 1, . . . , T do if there is a switch then receive π from the predictor; compute FitF solution x 1 , . . . , x T for π; move to x t . Lemma 6. Consider an input sequence r and let OPT(r) denote the cost of the optimal offline solution for this sequence. Algorithm 2 with a predictor which makes σ switches and its final prediction is consistent with r incurs cost at most OPT(r) + kσ.Proof of Lemma 6 can be found in Appendix A. Combining lemmas 5 and 6, we get an algorithm for caching in a realizable setting with the following guarantee. Theorem 7. There is an algorithm for caching in realizable setting which, given a class H of ℓ hypotheses, achieves regret at most k log ℓ.Question: 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 or not)? 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 a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is 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 one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • 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. • The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or 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 out 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 are 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
conclusions: 
 We introduce a new approach to modeling algorithms with predictions. Unlike the traditional blackbox 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 a learning component and an algorithmic component, addressing each separately. By applying our algorithms to existing settings with prediction portfolios [Dinitz et al., 2022 , Emek et al., 2021] , we demonstrate that our approach often results in simpler algorithms with improved performance compared to previous methods. 
safeguards: 
 Question: 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)? 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 a best faith effort. 12. Licenses for existing assets Question: 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? 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 use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
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 to 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 NeurIPS 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. 
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 crowdsourcing nor research with human subjects.• 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. 
 
 Appendix: A Caching in realizable setting: omitted proof Proof of Lemma 6. At every switch, we pay at most k for switching the cache from the FitF solution of the previous predicted sequence to the cache of the newly computed one. Thus it suffices to show that in between these switches, our algorithm has the same number of page faults as OPT.Denote t 1 , . . . , t σ the times when switches happen; for convenience, we also define t 0 = 1, t σ+1 = T + 1. We denote π 0 , . . . , π σ the predictions such that π i-1 was predicted before the ith switch and π i after. Let κ j i be the cost of the FitF solution for π j paid during time steps t i , . . . , t i+1 -1, for i = 0, . . . , σ. In this notation, the cost of OPT is σ i=0 κ σ i , since π σ = r (recall that r is the input sequence), while, excluding the switching cost considered above, the cost of the algorithm is σ i=0 κ i i , because it pays κ i i during time steps t i , . . . , t i+1 -1 when following a FitF solution for π i . We use induction on i to show that κ j i = κ σ i for each j = i, . . . , σ. This impliesσ i=0 κ σ i = σ i=0 κ i i .This essentially follows from Obsevation 4 and the fact that all sequences π j , j = i, . . . , σ agree on the prefix up to time t i+1 -1. The formal details follow.In the base case with i = 0, Observation 4 implies that FitF solutions for each π i incur the same cost during time steps 1, . . . , t 1 -1 and we haveκ 1 0 = • • • = κ σ 0 .For i > 0, the cost of the FitF solution for each π j with j ≥ i during time steps 1, . . . , t i+1 -1 is i m=0 κ j m = i-1 m=0 κ σ m + κ j i by induction hypothesis. Using Observation 4, i-1 m=0 κ σ m + κ i i = • • • = i-1m=0 κ σ m + κ σ i and therefore κ j i = κ σ i for each j = i, . . . , σ. In total, the algorithm incurs costALG(r) ≤ σ i=0 κ i i + σk = σ i=0 κ σ i + σk = OPT(r) + σk.We are given a set M of m machines and a sequence of jobs arriving online. At each time step, we receive some job j described by a vector p j , where p j (i) is its processing time on machine i ∈ M . We say that the job j has type p j . We have to assign job j to 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 i the set of jobs assigned to a machine i, we minimize the maximum load j∈Ji p j (i) over all i ∈ M . The best competitive ratio achievable in online setting is Θ(log m) [5] . In offline setting, there is a 2-approximation algorithm. Proposition 8 (Lenstra et al. [26] ). There is 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 a (randomized) algorithm ALG achieves competitive ratio r (or that ALG is r-competitive), if E[cost(ALG(I))] ≤ r • cost(OPT(I)) + α holds for every instance I, where OPT(I) denotes the offline optimal solution for instance I and α is a constant independent of I.Learning task. We are given a class H of ℓ hypotheses H 1 , . . . , H ℓ , each specifying the frequency f p ≥ 0 for every job type such that p f p = 1. For simplicity, we assume that there is a constant δ > 0 such that all frequencies in all hypotheses are integer multiples of δ. For a hypothesis H with frequencies f p and an integer h ≥ 1, we define a scaling H(h) as an instance containing hf p /δ jobs of type p, for each p. This way, any type p with f p ̸ = 0 is represented by at least a single job in H(1). We denote c 0 the largest makespan of H(1) over all hypotheses H ∈ H.We say that an instance I ′ is consistent with the input so far, if the following holds for every job type p: 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 c 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 a 2-approximation offline algorithm (Proposition 8), we can also find a scaling I i of each hypothesis H i such that the makespan of I i is between c and 4c. Therefore, we start by assuming that we have the value of c and the scaled instances I 1 , . . . , I ℓ 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 i consistent with the whole input or return ERR which signals an incorrect value of c. Agnostic case is considered in Section B.4 and robustification of our algorithms in Section B.5. Section B.7 contains lower bounds.We propose a 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 I 1 , . . . , I ℓ whose makespan is between c and 4c created by scaling the hypotheses H 1 , . . . , H ℓ . For each p and i, we denote n i p the number of jobs of type p in instance I i . Both predictors switch to a new prediction whenever they discover that, for some p, the number of jobs of type p which arrived so far is already larger than their predicted number. At each switch, they update a set A ⊆ {1, . . . , ℓ} 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 is at most n i p for all p and i ∈ A. There is a simple proper predictor which makes ℓ 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, we provide a more sophisticated predictors with lower number of switches.Deterministic predictor. Our deterministic predictor is improper. At each switch, it predicts a "median" instance Ĩ created from the instances in A as follows. For each type p, Ĩ contains ñp jobs of type p, where ñp is a median of n i p over all i ∈ A. This way, whenever the number of jobs of type p exceeds ñp , 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. // switch to a new Ĩ Lemma 9. Predictor 3 maintains a prediction which is always consistent with the jobs arrived so far. Given ℓ instances of makespan between c and 4c, it makes σ ≤ log ℓ switches before it either identifies an instance I i ⋆ consistent with the whole input, or returns ERR if there is no such instance. The makespan of each prediction is at most 4c log τ , where τ is the number of distinct job types present in the instances I 1 , . . . , I ℓ .Proof. First, note that whenever a number of jobs of some type exceeds the prediction, Predictor 3 switches to a new prediction consistent with this number.Consider a switch when the number of jobs of type p exceeds ñp . Since ñp was chosen as a median of n i p over i ∈ A, the size of A decreases by factor of at least 2 by this switch. Therefore, we have at most log ℓ switches. Now, we bound the makespan of Ĩ by 4c log τ , where Ĩ is the prediction constructed from the current set of instances A. We do this by constructing a schedule for Ĩ. We say that an instance I i covers type p, if n i p ≥ ñp . By the construction of Ĩ, we have that for every p, at least half of the instances in A cover p. This implies that we can find an instance I i covering half of the job types. Indeed, consider a matrix M whose columns correspond to instances i in A and its rows to τ ′ ≤ τ different job types p present in instances of A. We define M p,i as 1 if I i covers p and 0 otherwise. Since every row has at least |A|/2 ones, there are at least τ ′ |A|/2 ones in M so there must be a column i of M containing τ ′ /2 ones. So, we pick I i and add all its jobs to the schedule, using a schedule of I i of makespan at most 4c. Then we remove i from A, and remove all job types covered by I i from Ĩ. |A| decreases by 1, τ ′ decreases by factor of 2, and we still have that every remaining job type is covered by at least |A|/2 instances: This follows since for any type p not covered by I i , the number of instances covering it remains the same while |A| decreases by 1. Therefore, after iterating this process at most log τ times we cover all job types using makespan at most 4c log τ .Randomized predictor. Our randomized predictor is proper. At each switch, it predicts an instance I i , where i is chosen from A uniformly at random. We show that it satisfies the same bound on the number of switches as Predictor 3, but the makespan of its predictions is much smaller. . Predictor 4 maintains a prediction which is always consistent with the jobs arrived so far. Given ℓ instances of makespan between c and 4c, it makes σ ≤ log ℓ switches in expectation before it either identifies an instance I i ⋆ consistent with the whole input, or returns ERR if there is no such instance. Each prediction has makespan at most 4c.Proof. First, note that whenever a number of jobs of some type exceeds the prediction, Predictor 4 switches to a new prediction consistent with this number. Now, we bound the expected number of switches done by Predictor 4 in the style of the airplane seat problem. For every i = 1, . . . , ℓ, define t i as the time step when an arriving job of type p exceeds n i p , or ∞ if no such time step exists. Note that for every instance i which is inconsistent with the input, t i is finite. The instances are eliminated in the order of increasing t i . Since we choose i uniformly at random over the remaining instances, we have t j ≤ t i 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] .Our algorithm uses a predictor whose predictions are always consistent with the jobs arrived so far. At each switch, it computes a 2-approximation of the optimal solution for the predicted instance using the algorithm from Proposition 8 and schedules jobs based on this solution until the next switch.Algorithm 5: load balancing on unrelated machines for each incoming job j do if this is the first job or there was a switch then get a new prediction Ĩ from the predictor or return ERR compute Lenstra( Ĩ) assign j to a machine based on Lenstra( Ĩ) Lemma 11. Given a predictor which makes σ switches and produces predictions that are always consistent with the jobs arrived so far and have makespan at most κ, Algorithm 5 uses makespan at most 2κσ and either schedules all jobs in the input sequence or reports ERR if none of the instances is consistent with the input sequence.Proof. At each switch, Algorithm 5 starts building a new schedule for the predicted instance with makespan at most 2κ. Therefore the total makespan is at most 2κσ.First, we discuss how to find a scaling of a hypothesis H that has the required makespan. Let c be our estimate of OPT such that c ≤ OPT ≤ 2c. We start with h = 1 and keep doubling h until Lenstra(H(h)) becomes at least 2c. (and at most 4c). Since Lenstra is a 2-approximation, we know that when Lenstra(H(h)) ≥ 2c then OPT(H(h)) ≥ c. Since this is the smallest h for which Lenstra(H(h)) ≥ 2c we know that OPT(H(h/2)) ≤ 2c so OPT(H(h)) ≤ 4c.Algorithm 6 is our scheduling algorithm. We start with the initial guess of c 0 for the optimal solution, where c 0 is an upper bound on the makespan of H(1) for each H ∈ H. At each iteration we double our guess c. We scale the hypotheses to build instances with makespan between c and 4c. We run Algorithm 5 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 c = c 0 , . . . , 2 1 c 0 , 2 2 c 0 , 2 3 c 0 , . . . do for i = 1, . . . , ℓ do find scaling h i c such that I i := H i (h i c ) has makespan between c and 4cRun Algorithm 5 with I 1 , . . . , I ℓ if not ERR then finish: all the jobs are scheduled Lemma 12. If Algorithm 6 uses makespan at most γc in an iteration with guess c, then it uses makespan at most O(γ)c ⋆ , where c ⋆ denotes the value of c in the last iteration.Proof. The total makespan used by the algorithm is at mostlog(c ⋆ /c0) i=0 2 i c 0 γ ≤ 2c ⋆ γ.Lemma 13. Let c ⋆ be the value of c 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 i ⋆ be the correct hypothesis describing the input instance I. We know that H i ⋆ (h i ⋆ c ⋆ /2 ) ⊊ I, otherwise Algorithm 6 would terminate in the previous iteration. We havec ⋆ /2 ≤ OPT(H i ⋆ (h i ⋆ c ⋆ /2 )) ≤ OPT(I),implying OPT(I) ≥ c ⋆ /2. The first inequality is by the choice of h i ⋆ c ⋆ /2 and the last one sinceH i ⋆ (h i ⋆ c ⋆ /2 ) ⊊ I.Theorem 14. There are algorithms for the realizable setting with deterministic and randomized predictors which, given a hypothesis class H of size ℓ, achieve competitive ratio O(log ℓ log τ ) and O(log ℓ) respectively, where τ is the total number of different job types in H.Proof. Combining Lemmas 12 and 13, the makespan achieved by Algorithm 6 is at most O(γ OPT). By Lemmas 9, 10, and 11, we have γ = log ℓ log τ in case of the deterministic Predictor 3 and γ = log ℓ in case of the randomized Predictor 4.The algorithm above works also in the agnostic setting. Let f p and f ⋆ p be the frequency of job type p according to a hypothesis H ∈ H and its true frequency, respectively. If there is a job type p such that f p ̸ = 0 and f ⋆ p = 0, we define α H := n + 1, where n denotes the number of jobs in the input instance. Otherwise, we define α H := max{f p /f ⋆ p | f ⋆ p ̸ = 0}. Similarly, if there is a job type p such that f p = 0 and f ⋆ p ̸ = 0, we define β H := n + 1. Otherwise, β H := max{f ⋆ p /f p | f p ̸ = 0}. Note that both α H and β H are at most n + 1: the smallest f ⋆ p > 0 is at least 1/n for the job types represented by a single job and the same holds for the scaling H(1) of each hypothesis H ∈ H. Let H ∈ H be a hypothesis achieving the smallest product α H β H . We call a pair (α, β), where α = α H and β = β H the error of hypothesis class H.We prove the following variant of Lemma 13 for agnostic setting, in the case with α, β ≤ n. Lemma 15. Let c ⋆ be the value of c in the last iteration of Algorithm 6 in the agnostic setting, given a hypothesis class H with error α, β ≤ n. Then, the makespan of the offline optimal solution is at least c ⋆ O(αβ) .Proof. The main idea here is that even if all hypothesis are incorrect, Algorithm 6 terminates once the input instance I is subsumed by a large enough scaling of some hypothesis. Consider the correct hypothesis H ⋆ for I consisting of real frequencies f ⋆ p for each job type p (H ⋆ may not be in H in the agnostic setting) and the best hypothesis H ∈ H (such that α, β = α H , β H ). We assume below that α and β 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 ⋆ p ≤ βf p , we have H ⋆ (h) ⊆ H(βh). Therefore, in the last iteration of Algorithm 6, we have c ⋆ within a constant factor from the optimum makespan of H(βh) Similarly, since f p ≤ αf ⋆ p , we have that H(βh) ⊆ H ⋆ (αβh) which implies that the optimum makespan of H(βh) is at most α OPT(H ⋆ (βh)) ≤ αβ OPT(I).Theorem 16. There are algorithms for the agnostic setting with deterministic and randomized predictors which, given a hypothesis class H of size ℓ with error (α, β), achieve competitive ratio O(αβ log ℓ log τ ) and O(αβ log ℓ),respectively, where τ is the total number of different job types in H.Proof. Consider an algorithm which schedules all jobs of type p such that f p = 0 according to all hypotheses in H to the machine arg min i∈[m] p i , i.e., the machine which can process the job fastest. Let J 0 denote the set of such jobs. All other jobs in I \ J 0 are scheduled using Algorithm 6. The resulting makespan is at most|J 0 | OPT +γc * ≤ |J 0 | OPT +O(αβγ) OPTwhere c * is the value of c in the last iteration of Algorithm 6 processing jobs in I \ J 0 . This is because, for every j ∈ J 0 , we have OPT ≥ min i∈[m] p i . The inequality follows from lemmas 15 and 12.If |J 0 | > 0, then at least one of α and β is at least n + 1. Therefore, our makespan is always at most αβγ OPT. By lemmas 9, 10, and 11, we have γ = log ℓ log τ in case of the deterministic Predictor 3 and γ = log ℓ in case of the randomized Predictor 4.With large α, β, 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 c, we run a classical online algorithm by Azar et al. [5] as long as it uses makespan γc. That is, we stop it as soon as its makespan go above γc (and we do not schedule the job that makes it go above γc. This increases the makespan of the solution by factor at most 2 and ensures that OPT ≥ γc/O(log 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 O(log m).for c = c 0 , . . . , 2 1 c 0 , 2 2 c 0 , 2 3 c 0 , . . . do for i = 1, . . . , ℓ do find scaling h i c such that I i := H i (h i c ) has makespan between c and 4cRun Algorithm 5 with I 1 , . . . , I ℓ Run Online algorithm of Azar et al. [5] as long as it uses makespan of at most γc if all jobs are scheduled then finish Proof. Algorithm 6 terminates once it finds c ⋆ and i, such that the actual instance I is a subset ofH i (h i c ⋆ ).With the same c ⋆ , Algorithm 7 terminates as well. While Algorithm 6 uses a makespan of at most γc ⋆ in each iteration, Algorithm 7 uses makespan of at most 2γc ⋆ in each iteration. Now we prove the O(log m) bound on the competitive ratio. Consider I ′ ⊆ I the set of jobs assigned to machines by the online algorithm of Azar et al. [5] in the next to last iteration (line 5 of Algorithm 7). We haveOPT(I) ≥ OPT(I ′ ) ≥ γc ⋆ /2O(log m) because the online algorithm is O(log m)-competitive and it required makespan γc ⋆ /2 in the second to last iteration. Since Algorithm 7 uses makespan at most O(γc ⋆ ) by Lemma 12, the bound on its competitive ratio follows.Dinitz et al. [15] considered a portfolio of ℓ algorithms for load balancing on unrelated machines and proposed a way to combine their outputs in a single fractional solution of cost at most O(log ℓ)-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 is at most O(log ℓ)-times higher than the cost of the best algorithm in the portfolio.We guess the value c 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 B.3. 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 c. At each time step, we schedule the current job based on a decision of the algorithm currently chosen by the predictor, paying at most c while following a single algorithm. An argument as in the proof of Lemma 10 shows that our predictor switches O(log ℓ) algorithms in expectation at each iteration.Our lower bound holds for a special case of load balancing on unrelated machines called restricted assignment, where processing of each job j is restricted to a subset S j of machines, i.e., its processing time is 1 on all machines belonging to S j and +∞ otherwise. Our construction requires m ≥ ℓ machines and is inspired by the construction of Azar et al. [5] (ℓ is number of hypothesis in H as before). Since we can ensure that all jobs have infinite processing time on machines ℓ + 1, . . . , m, we can assume that ℓ = m and that ℓ is a power of two.We construct ℓ instances of restricted assignment on ℓ machines, each with makespan c ∈ N. In instance i ∈ {1, . . . , ℓ}, there are cℓ/2 j jobs restricted to machines whose index agrees with i in the j -1 most significant bits, for j = 1, . . . , log ℓ. In particular, each instance starts with cℓ jobs which can be processed on any machine. The jobs arrive in iterations from j = 1 to log ℓ (from less restricted to more restricted). If numbers i and i ′ have a common prefix of length j -1, then instances i and i ′ have the same jobs in the first j iterations.Optimal solution for instance i can be described as follows: For each j = 1, . . . , log ℓ, schedule all cℓ/2 j jobs evenly on machines whose index agrees with i up to bit j -1 but disagrees with i in bit j:There are ℓ/2 j-1 -ℓ/2 j = ℓ/2 j 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 cℓ/2 j jobs evenly on ℓ/2 j machines, their load is c. Theorem 18. There is no (randomized) algorithm which, with a hypothesis class of size ℓ ≤ m, that achieves competitive ratio o(log ℓ).Proof. The adversary chooses the correct instance i bit by bit, fixing the jth bit i j at the end of iteration j depending on the behavior of the algorithm. Bit i j is chosen according to the following procedure: Given the knowledge of the distribution over algorithm's decisions, count the expected number of jobs from iterations 1, . . . , j assigned to machines whose first j bits are i 1 , . . . , i j-1 , 0. If this number is higher than the expected number of jobs assigned to machines with prefix i 1 , . . . , i j-1 , 1, then choose i j = 0. Otherwise, choose i j = 1.For each j = 1, . . . , log ℓ, we denote M j the set of machines with prefix i 1 , . . . , i j , with M 0 = {1, . . . , ℓ}. We show by induction on j that at least 1 2 jcℓ/2 j jobs are assigned to the machines belonging to M j in expectation. This way, M log ℓ contains a single machine with expected load at least 1 2 c log ℓ. The base case j = 1 of the induction holds: We assign cℓ jobs to ℓ machines in M 0 and i 1 is chosen so that machines in M 1 get at least half of them, in expectation. For j > 1, the expected number of jobs from iterations up to j -1 assigned to machines in M j-1 is at least 1 2 (j -1)cℓ/2 j-1 by the induction hypothesis. There are cℓ/2 j jobs restricted to machines in M j-1 scheduled in iteration j. Therefore, the total expected number of jobs from iterations 1, . . . , j assigned to machines in M j-1 is at least1 2 (j -1)c ℓ 2 j-1 + c ℓ 2 j = jc ℓ 2 j .Since i j is chosen such that the machines in M j are assigned at least half of the jobs assigned to machines in M j-1 in expectation, the expected number of jobs assigned to M j is at least c 2 jℓ/2 j . While the makespan for the instance i is c, the machine in M log ℓ has expected load at least 1 2 c log ℓ, showing that the competitive ratio of the algorithm is at least 1 2 log ℓ.We have a single machine and n jobs available from time 0 whose lengths p 1 , . . . , p n are unknown to the algorithm. We know the length p j of the job j only once it is finished. If it is not yet finished and it was already processed for time x j , we only know that p j ≥ x j . 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 I has total completion time objective OPT(I) + R, then the same solution on a scaled instance I ′ obtained from I by multiplying all job lengths by α has objective α(OPT(I) + R) = OPT(I ′ ) + αR. There is a 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 1, . . . , n, denoting p 1 , . . . , p n their lengths. Then, its total completion time objective can be expressed asn j=1 j i=1 p j = n j=1 p j (n -j + 1).This objective is minimal if p 1 ≤ • • • ≤ p n 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 a class H of ℓ hypotheses, each of them specifies length of all jobs, denoting p i j the length of job j according to the hypothesis H i . A predictor uses H to produce prediction π, where π j is the predicted length of the job j. We call a predictor monotone if, at each time step, it maintains a prediction which is consistent with our knowledge about job lengths and π j ≤ p j holds for every job j (i.e., it never overestimates a length of a job). We propose a monotone predictor only for the realizable setting. Non-clairvoyant scheduling in the agnostic setting is considered in Section C.2 with a different kind of hypotheses.Proof. The completion time of the job we shifted earlier get smaller by d i=1 p i , and the completion time of the d jobs which were delayed increases by at most 1. All other completion times do not change.Lemma 24. Algorithm 11 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 a schedule with expected total completion time at most OPT(I) + σ(1 -λ)n, where OPT(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 no switch, the prediction of its length was correct. We write σ = σ ′ + σ ′′ , where σ ′ is the number of times we process a job with incorrect predicted length λ (type-1 switch) and σ ′′ is the number of times we process a job with incorrect predicted length 1 (type-2 switch).Every type-1 switch causes a job of length 1 to be scheduled before at most n jobs of length λ. By Lemma 23, the schedule produced by the algorithm is more expensive than the solution where these σ ′ jobs were executed last by at most σ ′ (1 -λ)n. It 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 a short job with predicted length 1). There are σ ′′ + 1 intervals i = 0, 1, . . . , σ ′′ . We denote by q i 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 i the number of jobs of predicted length 1 scheduled thereafter in the ith interval. Let n i denote the total number of unfinished jobs when we finish scheduling the q i jobs of predicted length λ, and let s i be the number of unfinished jobs of length λ at that time. We haveq i = s i-1 -s i .With this notation and using Lemma 23, the regret of the algorithm is(1 -λ) σ ′′ -1 i=0 m i s iThis is because the optimal schedule processes jobs of length λ first and our schedule can be constructed by moving (one by one) m i jobs of length 1 forward, leaving s i jobs of length λ behind for each i = 1, . . . , σ ′′ .Since we choose to process a random job of predicted length 1 we have E[m i | n i , s i ] = ni+1 si+1 ≤ n si , as we are drawing from n i jobs without replacement until the first of s i jobs of size λ is drawn. ThereforeE[m i | s i ] ≤ n/s i and E[m i s i ] = n j=1 P(s i = j)E[m i s i | s i = j] ≤ n.So, the expected regret in case a type-1 switch never happens is(1 -λ) σ ′′ -1 i=0 E[m i s i ] ≤ (1 -λ)nσ ′′ .Therefore, the cost of the algorithm is ALG ≤ OPT +(1 -λ)nσ.Lemma 22 and Lemma 24 together imply the following theorem. Theorem 25. Consider an instance I with jobs of length either 1 or λ for some fixed λ ∈ (0, 1). There is an algorithm which, given a hypothesis class H of size ℓ, produces a schedule with expected total completion time at most OPT(I) + σ(1 -λ)n in the realizable setting (i.e., I ∈ H), where OPT(I) is the total completion time of the offline optimal solution.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 J = {1, . . . , n} be the set of all jobs. We call a mistake every inversion in this ordering, i.e., two jobs i, j ∈ J such that p i < p j but π(j) < π(i). For every pair of jobs {i, j}, we defineµ(π, {i, j}) = (p i -p j ) + if π(i) < π(j) (p j -p i ) + otherwise.If the order of i j in π is incorrect, then µ(π, {i, j}) is the weight of this mistake. Otherwise, it is equal to 0. For a set of pairs of jobs P ⊆ J 2 , where J 2 denotes the set of all pairs of jobs, we denote µ(π, P ) = {i,j}∈P µ(π, {i, j}), and µ(π) = µ(π, J2 ) is the total weight of mistakes in π. Proposition 26 (Lindermayr and Megow [28] ). Let OPT denote the cost of the offline optimal solution and cost(π) the cost of the solution where the jobs are processed according to the ordering π. Then cost(π) -OPT = µ(π).Predictor. It has a parameter m. First, it samples m pairs of jobs, P = {{j i , j ′ i } | i = 1, . . . , m}. The initial predicted permutation starts with these jobs, i.e., j 1 , j ′ 1 , . . . , j m , j ′ m and the rest of the jobs follow in an arbitrary order. Once the lengths of the jobs in P are determined, the predictor calculates µ(h, P ) for each h ∈ 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 µ(h, P ).Predictor 12: non-clairvoyant scheduling, agnostic case At time 0: sample m pairs of jobs P When the last job in P is completed:for h ∈ H do compute µ(h, P )Switch to a new prediction based on ĥ with minimum µ( ĥ, P )Predictor 12 makes only one switch which happens at the moment when the last job from P is completed. Lemma 27. Let π be the final prediction produced by Predictor 12 during its only switch. With probability (1-δ), we have µ(π) ≤ µ(h * )+O(n 5/3 (log ℓ δ ) 1/3 ), where h * denotes the best hypothesis in H.Proof. The total weight of the mistakes in the last prediction can be bounded by µ(π) ≤ µ( ĥ) + 2mn,where ĥ is the hypothesis chosen at line 4. This follows because the 2m jobs belonging to P which are at the beginning of π have length at most 1 and each of them delays the completion of at most n jobs. We need to show that, with high probability, we have to show that µ( ĥ) similar to µ(h * ).For each hypothesis h ∈ H and a pair {i, j} ∈ [n] 2 chosen uniformly at random, we denoteρ h = E[µ(h, {i, j})] = µ(h)/ n 2 .Since the pairs in P are chosen uniformly at random, we have E[µ(h, P )] = ρ h m for each h ∈ H. Now we use Hoeffding's concentration inequality [40, Thm 2.2.6] to show that µ(h, P ) is close to its expectation with a high probability. Choosing m = log(2ℓ/δ)/2ϵ 2 , where ϵ is a parameter to be decided later, we haveP |µ(h, P ) -ρ h m| > ϵm ≤ 2 exp -2(ϵm) 2 /m = 2 exp(-2ϵ 2 m) ≤ δ/ℓ,for each h ∈ H. So, by a union bound, with probability at least 1-δ, we have |µ(h, P )-ρ h m| ≤ ϵm for all hypothesis h ∈ H and the chosen hypothesis ĥ must have ρ ĥ ≤ ρ h ⋆ + 2ϵ. Multiplying by n 2 we get µ( ĥ) ≤ µ(h * ) + 2ϵ n 2 with probability 1 -δ. The total weight of mistakes in the final prediction π is bounded as follows:µ(π) ≤ µ(h * ) + 2ϵ n 2 + log(2ℓ/δ) ϵ 2 n.We choose ϵ = O log(ℓ/δ) n 1/3 , getting µ(π) ≤ µ(h * ) + O 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 a 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 is µ, the regret of Algorithm 13 is µ.Proof. By Lemma 36 and Lemma 34, the cost of the algorithm is at mostOPT(r) + 4µ + kσ ≤ OPT(r) + 4(1 + 1/k)µ ⋆ + k ln ℓ + k(1/k + 1/k 2 )(1 + 1/k)µ ⋆ + k(1/k + 1/k 2 )k ln ℓ ≤ OPT(r) + (5 + 6/k)µ ⋆ + (2k + 1) ln ℓ.We can robustify our algorithms both for the realizable and agnostic setting in the following way. We partition the input sequence into intervals such that the cost paid by OPT in interval i is 2 i k. Note that we start with an empty cache and OPT ≥ k on any non-trivial instance: if OPT ≤ k, less than k distinct pages were requested and any lazy algorithm is optimal. In each of these intervals, we first run our algorithm until its cost reaches 2 i k log k. Then, we switch to an arbitrary worst-case algorithm with competitive ratio O(log k) for the rest of the time window. Lemma 38. Consider an algorithm ALG which, given a predictor making µ mistakes and σ switches achieves regret αµ + βkσ. We can construct an algorithm ALG ′ which is O(log k)-competitive in the worst case and its regret is always bounded by O(α)µ + O(β)kσ.Proof. We denote G the set of intervals i where ALG paid cost ALG i ≤ 2 i k log k. The cost of ALG ′ is thenALG ′ ≤ i∈G ALG i + i / ∈G (O(log k) 2 i k + 2k), ≤ i∈G ALG i + i / ∈G O(log k) 2 i k,where 2k denotes the cost of switching to the worst-case algorithm and back to ALG. This already shows that ALG ′ is O(log k)-competitive: we have ALG ′ ≤ O(log k) OPT, because OPT pays 2 i k in window i.To show that it still preserves good regret bounds, note that αµ i + βkσ i ≥ 2 i k log k in each interval i / ∈ G, where σ i denotes the number of switches and µ i the number of mistakes in interval i. Therefore, we have ALG ′ ≤ ALG +O(α)µ + O(β)kσ.In order to compute a step of FitF, we either need to 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 a prediction of the next arrival time (NAT) of each page when requested. Precise NAT predictions allow us to simulate FitF. Lykouris and Vassilvitskii [32] , Rohatgi [36] , Wei [41] proposed algorithms able to use them even if 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-time predictions, as considered by Lykouris and Vassilvitskii [32] . Given the part of the sequence seen so far, they produce a 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 and Theorem 37 hold also with H containing ℓ models producing next-arrival-time predictions.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 k 2 log ℓ.Proof. Let ℓ be power of two. We use universe of pages U = {1, . . . , 2k} and define sequences a = 1, . . . , k and b = k + 1, . . . , 2k. By concatenating a and b in a specific manner, we construct building blocks of the input sequence and the hypotheses: σ 0 = a k ba 2k+1 and σ 1 = a k bb k ba k . Here a k denotes a sequence a iterated k times, and both blocks are chosen to have equal length.For each i = 1, . . . , ℓ, we use its binary representation b i1 b i 2 • • • b i log ℓ to construct a hypothesis r i = σ b i 1 σ b i 2 • • • σ b i log ℓfrom blocks σ 0 and σ 1 . Note that for any input sequence constructed from blocks σ 0 and σ 1 , we can construct an offline solution such that:• at the beginning and at the end of each block, its cache content is {1, . . . , k}.• during block σ 0 , it keeps pages 1, . . . , k -1 in cache, paying k for page faults during sequence b and 1 for loading page k, i.e., k + 1 page faults in total• during block σ 1 , it pays 2k, because it replaces the whole cache with {k + 1, . . . , 2k} during the first occurrence of b and then with {1, . . . , k} after the last occurrence of b.For each i = 1, . . . , log ℓ, we issue a k b -the common prefix of σ 0 and σ 1 -and compute n i the expected number of pages from {1, . . . , k} in the cache. Note that any algorithm has to pay at least k during a k b since it contains 2k distinct pages. If n i < k/2, we issue a 2k+1 , completing block σ 0 . Otherwise, we issue b k ba k , completing block σ 1 .In the first case, its expected cost will be at least k + (k -n i ) > k + k/2, because the algorithm will have at least k -n i page faults during the sequence a 2k+1 at the end of σ 0 .In the second case, the expected cost of the algorithm will be at least k Lemma 40. There is no deterministic algorithm which, given a predicted request sequence with µ mistakes achieves regret smaller than µ.+ n i + k ≥ 2k + k/2,Proof. We construct a predicted instance π = ((1, . . . , k, 0)(2, . . . , k)(0, 1, . . . , k)) n which is given to the algorithm ALG. We construct a real instance which is constructed online based on ALG's decisions.For any iteration i = 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 {1, . . . , k}.First, any algorithm has a page fault during (1, . . . , k, 0) because k + 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, . . . , k}. If p = 1, ADV evicts k instead and the real request sequence continues with (2, . . . , k -1, 1) instead of (2, . . . , k), causing a single mistake in the prediction. ALG has a page fault during this part, while ADV has no page fault. If p ∈ {2, . . . , k}, ADV evicts 1 and the real request sequence continues as predicted without any mistake, causing a page fault to ALG, while ADV has no page fault. In the last part (0, 1, . . . , k), both ALG and ADV have a page fault. So, ALG 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 µ ≤ n, the regret of ALG is at least µ.1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: Main claim made in abstract is that we propose a new way of designing Learning-augmented algorithms and that this way can be used to design simple algorithms with performace better and comparable to 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. Guidelines: Section 2 contains formal statements of our theoretical results which match with the 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 in 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 it is clear that these goals are not attained by the paper.38th Conference on Neural Information Processing Systems (NeurIPS 2024).Boosting technique, which had a great impact on applied and practical machine learning, was developed while studying relationship between weak and strong PAC learning in the realizable setting.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 np for the types p.We refer to the makespan of the optimal schedule for an instance as the makespan of the instance.The maximum ratio between the cost of the algorithm and the offline optimal solution over all instances.Formally, the loss of a permutation π is the expected value of the following random variable: sample a 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 one achieved by the optimal permutation, as shown byLindermayr and Megow [2022].If a solution for instance I has total completion time objective OPT(I) + R, then the same solution on a scaled instance I ′ obtained from I by multiplying all job lengths by α has objective α(OPT(I) + R) = OPT(I ′ ) + αR.They 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. 


Decision: 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.

Reviews: review: paper_summary: paper_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.

For the problems studied, the authors match or improve upon (in some parameter regimes) prior works which can be interpreted to be in their framework.
strength_weakness: strength_weakness: - 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. 
- The algorithms, for example for caching, must iterate over the entire set of hypothesis every time, which seems quite inefficient. 
- 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. 
- 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.
- There are no algorithms in the main body and it is hard to judge algorithmic improvements.
questions: questions: - Can the authors clarify the n^(5/3) issue?
limitations: limitations: No societal consequences.
paper_summary: paper_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.

In 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:

 - Caching: ${\rm OPT}+ k \log \ell$
 - Load Balancing: $O(\log \ell \cdot {\rm OPT})$
 - Non-clairvoyant scheduling: ${\rm OPT} + \ell \sqrt{ 2 \rm OPT}$

In 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:

 - Caching: ${\rm OPT} + O(\mu^* + k \log \ell)$
 - Load Balancing: $O( \mu^* \cdot \log \ell \cdot {\rm OPT})$
 - Non-clairvoyant scheduling: ${\rm OPT} + \mu^* +  O(n^{5/3} \log \ell)$

where in each, $\mu^*$ is a problem-dependent notion of distance from ${\cal H}$ to the true instance.

Some lower bounds are given showing tightness or almost-tightness for these results.
strength_weakness: strength_weakness: - 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.

- 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.

- The writing has some awkward phrases and grammar throughout, e.g. the following (among others):

   - line 62 "... will be much smaller then ..." -> "... will be much smaller than ..."
   - lines 107-108 "... using arguably simpler approach ..." -> "... using an arguably simpler approach ..."
   - lines 306-307 "... under certain assumptions about input." -> "... under certain assumptions about the input."
   - lines 374-375 "In offline setting, ..." -> "In the offline setting, ..."
questions: questions: - To what extent can these techniques be generalized?  E.g., what can be said about $k$-server?

 - Only the case of finite ${\cal H}$ is considered.  Can anything be said about infinite but "low complexity" ${\cal H}$?
limitations: limitations: Limitations and assumptions have been made clear.  Potential negative societal impacts from this work are very unlikely.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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”.
questions: 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?
- 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? 
- 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.
- 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: limitations: yes
paper_summary: paper_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.
In 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.
The authors of this paper introduce a new framework which integrates both the predictor and the learning-augmented algorithm. 
The 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. 
In 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. 
The predictor can compute at any time a new prediction using these hypotheses and the input which has been revealed up to that time.
The 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.
The 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.
strength_weakness: strength_weakness: - 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.
- 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.
questions: 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.


Further comments:
- Line 1140: there is a comma before the second inequality.
limitations: limitations: As far as I see, all limitations have been properly addressed.

Comments: title: Response to Rebuttal
comment: I thank the authors for their response.

The ability to combine the learning problem with the algorithmic one is obviously desirable. I think where my initial criticism came from is that I'm not totally sure the paper's proposed way of doing this is "the right way". On further thought, this is an unrealistic expectation to have. It may take several tries for researchers on LA algorithms to build consensus on the right model to open up the black box of the learning problem. I'm not sure this is the right model, but it's a good start, and it shows promise given the results they obtain.  From this lens, I think the paper is making an important contribution, and I will be raising my score. I support acceptance.
I thank the authors for their rebuttal, and for answering my question about the connection to the traditional setting.

My opinion about the paper and my score remain unchanged.
Thank you for your response, my evaluation is unchanged.