A Regression Approach to Learning-Augmented Online Algorithms
Year: 2021

Abstract:
The emerging field of learning-augmented online algorithms uses ML techniques to predict future input parameters and thereby improve the performance of online algorithms. Since these parameters are, in general, real-valued functions, a natural approach is to use regression techniques to make these predictions. We introduce this approach in this paper, and explore it in the context of a general online search framework that captures classic problems like (generalized) ski rental, bin packing, minimum makespan scheduling, etc. We show nearly tight bounds on the sample complexity of this regression problem, and extend our results to the agnostic setting. From a technical standpoint, we show that the key is to incorporate online optimization benchmarks in the design of the loss function for the regression problem, thereby diverging from the use of off-the-shelf regression tools with standard bounds on statistical error.

heading: 1 Introduction
text: A recent trend in online algorithms has seen the use of future predictions generated by ML techniques to bypass pessimistic worst-case lower bounds. A growing body of work has started to emerge in this area in the last few years addressing a broad variety of problems in online algorithms such as rent or buy, caching, metrical task systems, matching, scheduling, experts learning, stopping problems, and others (see related work for references). The vast majority of this literature is focused on using ML predictions in online algorithms, but does not address the question of how these predictions are generated. This raises the question: what can we learn from data that will improve the performance of online algorithms? Abstractly, this question comes in two inter-dependent parts: the first part is a learning problem where we seek to learn a function that maps the feature domain to predicted parameters, and the second part is to re-design the online algorithm to use these predictions. In this paper, we focus on the first part of this design pipeline, namely we develop a regression approach to generating ML predictions for online algorithms.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Before delving into this question further, we note that there has been some recent research that focuses on the learnability of predicted parameters in online algorithms. Recently, Lavastida et al. [33], building on the work of Lattanzi et al. [32], took a data-driven algorithms approach to design online algorithms for scheduling and matching problems via learned weights. In this line of work, the goal is to observe sample inputs in order to learn a set of weights that facilitate better algorithms for instances from a fixed distribution. In contrast, Anand et al. [4] relied on a classification learning approach for the Ski Rental problem, where they aimed to learn a function that maps the feature set to a binary label characterizing the optimal solution. But, in general, the value of the optimal solution is a real-valued function, which motivates a regression approach to learning-augmented online algorithms that we develop in this paper.
To formalize the notion of an unknown optimal solution that we seek to learn via regression, we use the online search (ONLINESEARCH) framework. In this framework, there is as an input sequence Σ = σ1, σ2, . . . available offline, and the actual online input is a prefix of this sequence ΣT = σ1, σ2, . . . , σT , where the length of the prefix T is revealed online. Namely, in each online step t > 0, there are two possibilities: either the sequence ends, i.e., T = t, or the sequence continues, i.e., T > t. The algorithm must maintain, at all times t, a solution that is feasible for the current sequence, i.e., for the prefix Σt = σ1, . . . , σt. The goal is to obtain a solution that is of minimum cost among all the feasible solutions for the actual input sequence ΣT .
We will discuss applicability of the ONLINESEARCH framework in more detail in Section 1.2, but for a quick illustration now, consider the ski rental problem in this framework. In this problem, if the sequence continues on day t, then the algorithm must rent skis if it has not already bought them. In generalizations of the ski rental problem to multiple rental options, the requirement is that one of the rental options availed by the algorithm must cover day t. We will show in Section 1.2 that we can similarly model several other classic online problems in the ONLINESEARCH framework.
We use the standard notion of competitive ratio, defined as the worst case ratio between the algorithm’s cost and the optimal cost, to quantify the performance of an online algorithm. For online algorithms with predictions, we follow the terminology in [41] that is now standard: we say that the consistency and robustness of an algorithm are its competitive ratios for correct predictions and for arbitrarily incorrect predictions respectively. Typically, we fix consistency at 1 + for a hyper-parameter and aim to minimize robustness as a function of .
We make some mild assumptions on the problem. First, we assume that solutions are composable, i.e., that adding feasible solutions for subsequences ensures feasibility over the entire sequence; second, that cost is monotone, i.e., the optimal cost for a subsequence is at most that for the entire sequence; and third, that the offline problem is (approximately or exactly) solvable. These assumptions hold for essentially all online problems we care for.

heading: 1.1 Our Contributions
text: As a warm up, we first give an algorithm called DOUBLE for the ONLINESEARCH problem without predictions in Section 2. The DOUBLE algorithm has a competitive ratio of 4. We build on the DOUBLE algorithm in Section 3, where we give an algorithm called PREDICT-AND-DOUBLE for the ONLINESEARCH problem with predictions. We show that the PREDICT-AND-DOUBLE algorithm has a consistency of 1 + and robustness of O(1/ ), for any hyper-parameter > 0. We also show that this tradeoff between consistency and robustness is asymptotically tight.
Our main contributions are in Section 4. In this section, we model the question of obtaining a learningaugmented algorithm for the ONLINESEARCH problem in a regression framework. Specifically, we assume that the input comprises a feature vector x that is mapped by an unknown real-valued function f to an input for the ONLINESEARCH problem z. In the training phase, we are given a set of labeled samples of the form (x, z) from some (unknown to the algorithm) data distribution D. The goal of the learning algorithm is to produce a mapping from the feature space to algorithmic strategies for the ONLINESEARCH problem, such that when it gets an unlabeled (test) sample x from the same distribution D, the algorithmic strategy corresponding to x obtains a competitive solution for the actual input z in the test sample (that is unknown to the algorithm).
The learning algorithm employs a regression approach in the following manner. It assumes that the function f is from a hypothesis class F , and obtains an empirical minimizer in F for a carefully crafted loss function on the training samples. The design of this loss function is crucial since a bound
on this loss function is then shown to translate to a bound on the competitive ratio of the algorithmic strategy. (Indeed, we will show later that because of this reason, standard loss functions used in regression are inadequate for our purpose.) Finally, we use statistical learning theory for real-valued functions to bound the sample complexity of the learner that we designed.
Using the above framework, we show a sample complexity bound of O ( H·d ) for obtaining a competitive ratio of 1 + , where H and d respectively represent the log-range of the optimal cost and a measure of the expressiveness of the function class F called its pseudo-dimension.1 We also extend this result to the so-called agnostic setting, where the function class F is no longer guaranteed to contain an exact function f that maps x to z, rather the competitive ratio is now in terms of the best function in this class that approximates f . We also prove nearly matching lower bounds for our sample complexity bounds in the two models.
Our framework can also be extended to the setting where the offline optimal solution is hard to compute, but there exists an algorithm with competitive ratio c given the cost of optimal solution. In that case our algorithms gives a competitive ratio c(1 + ), which can still be better than the competitive ratio without predictions (see examples in next subsection).

heading: 1.2 Applicability of the ONLINESEARCH framework
text: The ONLINESEARCH framework is applicable whenever an online algorithm benefits from knowing the optimal value of the solution. Many online problems benefit from this knowledge, which is sometimes called advice in the online algorithms literature. For concreteness, we give three examples of classic problems – ski rental with multiple options, online scheduling, and online bin packing – to illustrate the applicability of our framework. Our algorithm PREDICT-AND-DOUBLE (explained in more detail in section 3) successively predicts the optimal value of the solution and appends the corresponding solution to its output.
Ski Rental with Multiple Options. Generalizations of the ski rental problem with multiple options have been widely studied (e.g., [1, 34, 37, 19]), recently with ML predictions [44]. Suppose there are V options (say coupons) at our disposal, where coupon i costs us Ci and is valid for di number of days. Given such a setup, we need to come up with a schedule: {(tk, ik), k = 1, 2 . . .} that instructs us to buy coupon ik at time tk. (The classic ski rental problem corresponds to having only two coupons C1 = 1, d1 = 1 and C2 = B, d2 → ∞.) Our ONLINESEARCH framework is applicable here: a solution that allows us to buy coupons valid time t is also a valid solution for all times s ≤ t. Further, PREDICT-AND-DOUBLE can be implemented efficiently as we can compute OPT(t), for any time t using a dynamic program.
Online Scheduling. Next, we consider the classic online scheduling problem where the goal is to assign jobs arriving online to a set of identical machines so as to minimize the maximum load on any machine (called the makespan). For this algorithm, the classic list scheduling algorithm [26] has a competitive ratio of 2. A series of works [23, 14, 29, 2] improved the competitive ratio to 1.924, and currently the best known result has competitive ratio of (approx) 1.92 [20]; in fact, there are nearly matching lower bounds [25]. However, if the optimal make-span (OPT) is known, then these lower bounds can be overcome, and a significantly better competitive ratio of 1.5 can be obtained in this setting [17] (see also [10, 31, 21, 22]). The ONLINESEARCH framework is applicable here with a slight modification: whenever PREDICT-AND-DOUBLE tries to buy a solution corresponding to a predicted value of OPT, we execute the 1.5-approximation algorithm based on this value. The problem still satisfies the property that a solution for t jobs is valid for any prefix. We get a competitive ratio of 1.5 +O( ) that significantly outperforms the competitive ratio of 1.92 without predictions.
Online Bin Packing. As a third example, we consider the online bin packing problem. In this problem, items arrive online and must be packed into fixed-sized bins, the goal being to minimize the number of bins. (We can assume w.l.o.g., by scaling, that the bins are of unit size.) Here, it is known that the critical parameter that one needs to know/predict is not OPT but the number of items of moderate size, namely those sized between 1/2 and 2/3. If this is known, then there is a simple 1.5-competitive algorithm [5], which is not achievable without this additional knowledge. Again, our ONLINESEARCH framework can be used to take advantage of this result. In this case, the application is not as direct, because predicting OPT does not yield the better algorithm. Nevertheless,
1Intuitively, the notion of pseudo-dimension extends that of the well-known VC dimension from binary to real-valued functions.
an inspection of the algorithm in [5] reveals the following strategy: The items are partitioned into three groups. The items of size≥ 2/3 are assigned individual bins, items of size between 1/3 and 1/2 are assigned separate bins where at least two of them are assigned to each bin, and the remaining items are assigned a set of common bins. Clearly, the first two categories can be handled online without any additional information; this means that we can define a surrogate OPT (call it OPT′) that only captures the optimal number of bins for the common category. Note that the of prediction of OPT’ serves as a substitute for knowing the numbers of items of moderate size. Now, if OPT′ is known, then we can recover the competitive ratio of 3/2 by using a simple greedy strategy. This now allows us to use the ONLINESEARCH framework where we predict OPT′. As earlier, the ONLINESEARCH framework can be applied with slight modification: whenever PREDICT-AND-DOUBLE tries to buy a solution corresponding to a predicted value of OPT′, we execute the 1.5-competitive algorithm based on this value. The problem still satisfies the property that a solution for t items is valid for any prefix.

heading: 1.3 Motivation for a cognizant loss function
text: In this work, we explore the idea of a carefully crafted loss function that can help in making better predictions for the online decision task. To illustrate this, consider the problem of balancing the load between machines/clusters in a data center where remote users are submitting jobs. The goal is to minimize the maximum load on any machine, also called the makespan of the assignment. The optimal makespan, which we would like to predict, depends on the workload submitted by individual users who are currently active in the system. Therefore, we would like to use the user features to predict their behavior in terms of the workload submitted to the server. A typical feature vector would then be a binary vector encoding of the set of users currently active in the system, and based on this information, a learning model trained on historical behavior of the users can predict (say) a histogram of loads that these users are expected to submit, and therefore, the value of the optimal makespan. The feature space can be richer, e.g., including contextual information like the time of the day, day of the week, etc. that are useful to more accurately predict user behavior. Irrespective of the precise learning model, the main idea in this paper is that the learner should try to optimize for competitive loss instead of standard loss functions. This is because the goal of the learner is not to accurately predict the workload of each user, but to eventually obtain the best possible makespan. For instance, a user who submits few jobs that are inconsequential to the eventual makespan need not be accurately predicted. Our technique automatically makes this adjustment in the loss function, thereby obtaining better performance on the competitive ratio.

heading: 1.4 Related Work
text: There has been considerable recent work in incorporating ML predictions in online algorithms. Some of the problems include: auction pricing [36], ski rental [41, 24, 4, 13, 44, 6], caching [35, 42, 28, 45], scheduling [41, 32, 39], frequency estimation [27], Bloom filters [38], online linear optimization [16], speed scaling [11], set cover [12], bipartite and secretary problems [9], etc. While most of these papers focus on designing online algorithms for ML predictions but not on the generation of these predictions, there has also been some work on the design of predictors using a binary classification approach [4]), and on the formal learnability of the predicted parameters [32, 33]. In contrast, we use a regression approach to the problem in this paper.
The PAC learning framework was first introduced by [43] in the context of learning binary classification functions, and related the sample complexity to the VC dimension of the hypothesis class. This was later extended to real-valued functions by [40], who introduced the concept of pseudo-dimension, and [30] (see also [15]), who introduced the fat shattering dimension, as generalizations of VC dimension to real-valued functions. For a comprehensive discussion of the extension of VC theory to learning real-valued functions, the reader is referred to the excellent text by [8]. A different approach was proposed by [3] (see also [7]) who analysed a model of learning in which the error of a hypothesis is taken to be the expected squared loss, and gave uniform convergence results for this setting. In this paper, we use pseudo-dimension and corresponding sampling complexity bounds in quantifying the complexity of the regression learning problem of predicting input length.
2 ONLINESEARCH without Predictions
As a warm up, we first describe a simple algorithm called DOUBLE (Algorithm 1) for the ONLINESEARCH problem without predictions. This algorithm places milestones on the input sequence corresponding to inputs at which the cost of the optimal solution doubles. When the input sequence crosses such a milestone, the algorithm buys the corresponding optimal solution and adds it to the existing online solution. This simple algorithm will form a building block for the algorithms that we will develop later in the paper; hence, we describe it and prove its properties below.
First, we introduce some notation. Definition 1. We use OPT(t) to denote an optimal (offline) solution for the input prefix of length t; we overload notation to denote the cost of this solution by OPT(t) as well. Definition 2. Given an input length τ and any α > 0, we use MIN-LENGTH(α, τ) to denote the smallest length t such that OPT(t) ≥ α · OPT(τ). The monotonicity property of OPT ensures that MIN-LENGTH(α, τ) > τ if α > 1, and MIN-LENGTH(α, τ) ≤ τ otherwise.
Algorithm 1 DOUBLE Input: The input sequence I. Output: The online solution SOL.
Set i := 0, τ0 := 1, SOL := ∅. for t = 1, 2, . . . , T
if t = τi Set τi+1 = MIN-LENGTH(2, τi). Add OPT(τi+1 − 1) to SOL. Increment i.
Theorem 1. The DOUBLE algorithm is 4-competitive for the ONLINESEARCH problem.
3 ONLINESEARCH with Predictions
In the previous section, we described a simple online algorithm for the ONLINESEARCH problem. Now, we build on this algorithm to take advantage of ML predictions. For now, we do not concern ourselves with how these predictions are generated; we will address this question in the next section.
Suppose we have a prediction T̂ for the input length T of an ONLINESEARCH problem instance. Naïvely, we might trust this prediction completely and buy the solution OPT(T̂ ). While this algorithm is perfect if the prediction is accurate, it can fail in two ways if the prediction is inaccurate: (a) if T T̂ and therefore OPT(T ) OPT(T̂ ), then the algorithm has a large competitive ratio, and (b) if T > T̂ , then OPT(T̂ ) may not even be feasible for T . A natural idea is to then progressively add OPT(t) solutions for small values of t (similar to DOUBLE) until a certain threshold is reached, before buying the predicted optimal solution OPT(T̂ ). Next, if T > T̂ , the algorithm can resume buying solution OPT(t) for t > T̂ , again using DOUBLE, until the actual input T is reached.
One problem with this strategy, however, is that the algorithm does not degrade gracefully around the prediction, a property that we will need later in the paper. In particular, if T is only slighter larger than T̂ , then the algorithm adds a solution that has cost 2 · OPT(T̂ ), thereby realizing the worst case scenario in Theorem 1 that was achieved without any prediction. Our work-around for this issue is to buy OPT(t) for a t slightly larger than T̂ , instead of OPT(T̂ ) itself, which secures us against the possibility of the actual input being slightly longer than the prediction. We call this algorithm PREDICT-AND-DOUBLE (Algorithm 2). Here, we use a hyper-parameter that offers a tradeoff between the consistency and robustness of the algorithm. We also use the following definition: Definition 3. Given an input length τ and any α > 0, we use MAX-LENGTH(α, τ) to denote the largest length t such that OPT(t) ≤ α · OPT(τ).
As described in the introduction, the desiderata for an online algorithm with predictions are its consistency and robustness; we establish the tradeoff between these parameters for the PREDICTAND-DOUBLE algorithm below.
Algorithm 2 PREDICT-AND-DOUBLE Input: The input sequence I and prediction T̂ . Output: The online solution SOL.
Set SOL := ∅, t1 := MIN-LENGTH( /5, T̂ ), and t2 := MAX-LENGTH(1 + /5, T̂ ). Phase 1: Execute DOUBLE while t < t1. Phase 2: At t = t1, add OPT(t2) to SOL. Phase 3: If t > t2, resume DOUBLE as follows: Set i := 0, τ0 := t2 + 1. for t = t2 + 1, t2 + 2, . . . , T
if t = τi Set τi+1 = MIN-LENGTH(2, τi). Add OPT(τi+1 − 1) to SOL. Increment i.
Theorem 2. The PREDICT-AND-DOUBLE algorithm has a consistency of 1 + and robustness of 5 ( 1 + 1 ) .
We also show that this tradeoff between (1 + )-consistency and O(1/ )-robustness bounds is essentially tight. Theorem 3. Any algorithm for the ONLINESEARCH problem with predictions that has a consistency bound of 1 + must have a robustness bound of Ω ( 1 ) .
Having shown the consistency and robustness of the PREDICT-AND-DOUBLE algorithm, we now analyze how its competitive ratio varies with error in the prediction T̂ . In particular, the next lemma shows that the competitive ratio gracefully degrades with prediction error for small error, and is capped at 4 for large error.
Lemma 4. Given a prediction T̂ for the input length, the competitive ratio of PREDICT-AND-DOUBLE is given by:
CR ≤  4 , T ≤ t1 (1 + ) · OPT(T̂ )
OPT(T ) , t1 ≤ T ≤ t2 4 , T > t2
where t1 represents the minimum value of t that satisfies OPT(t) ≥ 5 · OPT(T̂ ) and t2 represents the maximum value of t that satisfies OPT(t) ≤ (1 + 5 ) · OPT(T̂ ).
4 LEARN TO SEARCH: A Regression Approach
In the previous section, we designed an algorithm for the ONLINESEARCH problem that utilizes ML predictions. Now, we delve deeper into how we can generate these predictions. More generally, we develop a regression-based approach to learn to solve an ONLINESEARCH problem. For this purpose, we first introduce some standard terminology for our learning framework, which we call the LEARNTOSEARCH problem.

heading: 4.1 Preliminaries
text: An instance (x, z) of the LEARNTOSEARCH problem is given by a feature x ∈ X, and the (unknown) cost of the optimal offline solution z ∈ [1,M ]. The two quantities x and z are assumed to be drawn from a joint distribution on X× [1,M ]. A prediction strategy works with a hypothesis class F that is a subset of functions X 7→ [1,M ] and tries to obtain the best function f ∈ F that predicts the target variable z accurately. For notational convenience, we set our target y = ln z, i.e., we try to predict the log-cost of the optimal solution. Note that predicting the log-cost of OPT(T ) is equivalent to predicting the input length T .2 Furthermore, let D denote the input distribution on X× Y, where Y = [0, H] and H = lnM ; i.e., we assume that (x, y) ∼ D.
2When multiple input lengths might have the same optimal cost, we can just pick the longest one.
We define a LEARNTOSEARCH algorithmA as a strategy that receives a set ofm samples S ∼ Dm for training, and later, when given the feature set x of a test instance (x, y) ∼ D (where y is not revealed to the algorithm), it defines an online algorithm for the ONLINESEARCH problem with input y. Recall that an online algorithm constitutes a sequence of solutions that the algorithm buys at different times of the input sequence (see Algorithm 3 for a generic description of an LEARNTOSEARCH algorithm).
Algorithm 3 A general LEARNTOSEARCH algorithm Training: Given a Sample Set S, the training phase outputs a mapping M from every feature vector x ∈ X to an increasing sequence of positive integers Testing: Given unknown sample x ∈ X, define thresholds M(x) = (τ0, τ1 . . .) Set i := 0, SOL := OPT(τ0 − 1). while (Input has not ended)
if (SOL is infeasible) SOL := OPT(τi+1 − 1). Increment i.
We will use the notation CRA(x, y) to denote the competitive ratio obtained by an algorithm A on the instance (x, y). For a given set of thresholds (τ0, τ1 . . .), define iT = minτi>T i. Then, A pays a total cost of ∑iT i=0 OPT(τi), and thus the competitive ratio is
CRA(x, y) =
∑iT i=0 OPT(τi)
ey .
We define the “efficiency” of a LEARNTOSEARCH algorithm by comparing its performance with the best achievable competitive ratio. The optimal competitive ratio for a given distribution may be strictly greater than 1. For example, consider the distribution where x is fixed (say x0) and z is uniformly distributed over the set {2, 4}. One can verify that the best strategy for the above distribution is to buy the solution costing 2, and then if the input has not ended, then buy the solution costing 4. The competitive ratio for this strategy (in expectation) is 1.25.
Definition 4. A LEARNTOSEARCH algorithm A is said to be -efficient if
E(x,y)∼DCRA(x, y) ≤ ρ∗ + ,
where ρ∗ = E(x,y)∼DCRA∗(x, y) and A∗ is an optimal solution that has full knowledge of D and no computational limitations.
The “expressiveness” of a function family is captured by the following standard definition:
Definition 5. A set S = {x1, x2, . . . xm} is said to be “shattered” by a class F of real-valued functions S 7→ [0, H] if there exists “witnesses” R = {r1, r2 . . . rm} ∈ [0, H]m such that the following condition holds: For all subsets T ⊆ S, there exists an f ∈ F such that f(xi) > ri if and only if xi ∈ T . The “pseudo-dimension” of F (denoted as Pdim(F)) is the cardinality of the largest subset S ⊆ X that is shattered by F .
4.2 The Sample Complexity of LEARNTOSEARCH
Our overall strategy is to learn a suitable predictor function f ∈ F and use f(x) as a prediction in the PREDICT-AND-DOUBLE algorithm. Note that prediction errors on the two sides (over- and under-estimation) affect the competitive ratio of PREDICT-AND-DOUBLE (given by Lemma 4) in different ways. If we underestimate OPT(T ) by a factor less than 1 + 5 , the competitive ratio remains 1 +O( ), but a larger underestimate causes the competitive ratio to climb up to 4. On the other hand, if we overestimate OPT(T ), then the competitive ratio grows steadily by the ratio of over-estimation, until it reaches 5 · ( 1 + 1 ) . This asymmetric dependence is illustrated in Figure 1.
At a high level, our goal is to use regression to obtain the best function f ∈ F . But, the asymmetric behavior of the competitive ratio suggests that we should not use a standard loss function in the regression analysis. Let be the accuracy parameter for the PREDICT-AND-DOUBLE algorithm, and let ŷ = ln OPT(T̂ ) and y = ln OPT(T ) be the predicted and actual log-cost of the optimal solution respectively. Then we define the following loss function that follows the asymmetric behaviour of the competitive ratio for PREDICT-AND-DOUBLE:
Definition 6. The -parameterized competitive error is defined as:
` (y, ŷ) =  5 − 1 when y ≤ ŷ − ln 5 ey−ŷ − 1 when ŷ − ln 5 < y ≤ ŷ 1 · (y − ŷ) when ŷ < y ≤ ŷ + ln ( 1 + 5 ) 1 when y > ŷ + ln ( 1 + 5 ) .
We give more justification for using this loss function in the supplementary material, and show that standard loss functions do not suffice for our purposes. Using this loss function, we can measure the error of a function for an input distribution or for a fixed input set: Definition 7. Given a distribution D on the set X× Y and function f : X 7→ Y, we define
ERD, (f) = E(x,y)∼D[` (y, f(x))]. Alternatively, for a set of samples, S ∼ Dm, we define,
ERS, (f) = 1 m · m∑ i=1 ` (yi, f(xi)).
Our high-level goal is to use samples to optimize for the loss function called -parameterized competitive error that we defined above over the function class F , and then use an algorithm that translates the empirical error bound to a competitive ratio bound. This requires, in the training phase, that we optimize the empirical loss on the training samples. We define such a minimizer below: Definition 8. For a given set of samples S ∼ D and a function family F , we denote an optimization scheme O : S 7→ F as −Sample Error Minimizing (SEM) if it returns a function f̂ ∈ F satisfying:
ERS, (f̂) ≤ inf f∈F [ERS, (f)] + .
For the rest of this paper, we will assume that we are given an − SEM routine for arbitrary > 0. We are now ready to present our LEARNTOSEARCH algorithm (Algorithm 4), which basically uses the predictor with minimum expected loss to make predictions for PREDICT-AND-DOUBLE.
Algorithm 4 A LEARNTOSEARCH algorithm with accuracy parameter Training:
Input: Sample Set S, Function Family F Output: f̂ output by an -SEM algorithm O, i.e., ERS, (f̂) ≤ inf f̃∈F ERS, (f̃) + .
Testing: Given new sample x, set ŷ = f̂(x). Predicted prefix length: T̂ = maxOPT(t)≤eŷ t. Call PREDICT-AND-DOUBLE with T̂ and .
We relate the competitive ratio of Algorithm 4 to the error of function f̂ obtained during training: Lemma 5. Algorithm 4 has a competitive ratio upper bounded by ( 1 + + 3 · ERD, (f̂) ) .
Standard and Agnostic Models. We consider two different settings. First, we assume that the function class F contains the function f∗ that maps the feature set x to y – we call this the standard model. We relax this assumption in the more general agnostic model, where the function class F is arbitrary. In terms of the error function, in the standard model, we have inff∈F ERD, (f) = inff∈F ERS, (f) = 0, while no such guarantee holds in the agnostic model.

heading: 4.3 Analysis in the Standard Model
text: Next, we analyze the competitive ratio of Algorithm 4 in the standard model, i.e., when inff∈F ERD, (f) = inff∈F ERS, (f) = 0.
Theorem 6. In the standard model, Algorithm 4 obtains a competitive ratio of 1 + O( ) with probability at least 1− δ, when using O
( H·d log 1 log
1 δ ) samples, where d = Pdim(F).
When the cost of the optimal solution OPT(τ) is hard to compute, we can replace the offline optimal with an online algorithm that achieves competitive ratio c given the value of τ to get the following:
Corollary 7. In the standard model, if there exists a c-competitive algorithm for OPT(τ) given the value of prefix-length τ , Algorithm 4 obtains a competitive ratio of c(1 +O( )) with probability at least 1− δ, when using O ( H·d log 1 log 1 δ ) samples, where d = Pdim(F).
We also show that the result in Theorem 6 is tight up to a factor of H log 1/ :
Theorem 8. Let F be a family of real valued functions such that there exists a function f∗ : X 7→ Y that f∗(x) = y and let d = Pdim(F). There exists an instance of the LEARNTOSEARCH problem that enforces any algorithm to query Ω ( d log 1δ ) samples in order to have an expected competitive
ratio of 1 + with probability ≥ 1− δ.

heading: 4.4 Extension to the Agnostic Model
text: In the agnostic model, we no longer assume a function f ∈ F that predicts the log-cost y perfectly. It is possible that the true predictor is outside F , or in more difficult scenarios for any feature x, the behaviour of the log-cost y may be entirely arbitrary.
We first show that the loss function -parameterized competitive error defined earlier is still a reasonable proxy for the competitive ratio. Specifically, we show that any algorithm that hopes to achieve a competitive ratio of 1+O( ) must use a prediction f̂ ∈ F whose error ERD, (f) is bounded by O( ). We formally state this below:
Lemma 9. Let A be an algorithm for LEARNTOSEARCH that has access to a predictor f̂ : X 7→ [0, H] for the log-cost y. Then, there exists a distribution D and a function f̂A with the property ERD, (f̂A) = such that E(x,y)∼D [CRA(x, y)] ≥ 1 + 2 .
Unlike in the standard model, we no longer have that for any > 0, minf∈F ERD, (f) = 0. Therefore, we need to first quantify the performance of an ideal algorithm that uses predictors from F . Definition 9. Let χ( ) = minf∈F ERD, (f). Then, ∆F is the solution to the equation: = χ( ).
∆F measures the best competitive ratio that we can hope to get when we use a predictor from F . Note that appears in two places in this definition, since the loss function in Definition 6 depends on . We first show that this is a reasonable definition in that the solution to the equation is unique:
Lemma 10. For a given function family F and distribution D, the value of ∆F is unique.
We also give an algorithm that can approximate ∆F (Algorithm 5). Lemma 11. If |S| ≥ C · ( H·d log 1 log 1 δ ) for suitable constants C > 0, δ ≤ 12 , and ≤ ∆F , then with probability at least 1− δ, we have ε/6 ≤ ∆F ≤ 5ε/3, where ε is as returned by Algorithm 5.
We are now ready to define our LEARNTOSEARCH algorithm for the agnostic model. This algorithm is simply Algorithm 4 where the accuracy parameter is set to the value of ε returned by Algorithm 5.
Algorithm 5 Procedure to estimate ∆F Input: Sample Set S, and function family F Let be an accuracy parameter given by the size of the sample set S. Choose ε := Compute: f̂ such that ERS,ε(f̂) ≤ minf∈F ERS,ε(f) + ε3 . while ε ≤ ERS,ε(f̂) ε← 2ε. Recompute f̂ s.t. ERS,ε(f̂) ≤ minf∈F ERS,ε(f) + ε3 . Return ε.
Theorem 12. In the agnostic model for a function family F , Algorithm 4 with accuracy parameter ε from Algorithm 5 obtains a competitive ratio of 1 + O (∆F ) with probability at least 1− δ, when
using O ( H·d log ( 1 ∆F ) ·log 1δ
∆F
) samples, where d = Pdim(F).
We also lower bound the sample complexity of a LEARNTOSEARCH algorithm: Theorem 13. Any LEARNTOSEARCH algorithm that is -efficient with probability at least 1 − δ must query Ω ( log 1δ 2 ) samples.

heading: 4.5 Robustness of Algorithm 4
text: So far, we have established the competitive ratio of Algorithm 4 in the PAC model. Now, we show the robustness of this algorithm, i.e., bound its competitive ratio for any input. Even for adversarial inputs, we show that this algorithm has a competitive ratio of O(1/ ), which matches the robustness guarantees in Theorem 2 for the PREDICT-AND-DOUBLE algorithm. Theorem 14. Algorithm 4 is 5(1 + 1 ) = O ( 1 ) -robust.

heading: 5 Conclusion, Limitations, and Future Work
text: In this paper, we studied the role of regression in making predictions for learning-augmented online algorithms. In particular, we used the ONLINESEARCH framework that includes a variety of online problems such as ski rental and its generalizations, online scheduling, online bin packing, etc. and showed that by using a carefully crafted loss function, we can obtain predictions that yield nearoptimal algorithms for this problem. One assumption that holds for the above problems, but not for other problems such as online matching, is the composability of solutions, i.e., that the union of two feasible solutions is also a feasible solution. Extending our work to such “packing” problems is an interesting direction for future research. Another interesting direction would be to give a general recipe for converting competitive ratios to loss functions, minimizing which over a collection of training samples generates better ML predictions for online problems.

heading: 6 Acknowledgements
text: This research was partially funded by the Indo-US Virtual Networked Joint Center project No. IUSSTF/JC-017/2017. Keerti Anand and Debmalya Panigrahi were supported in part by NSF Awards CCF-1955703, CCF-1750140 (CAREER), and ARO Award W911NF2110230. Rong Ge was also supported in part by NSF Awards DMS-2031849, CCF-1704656, CCF-1845171 (CAREER), CCF-1934964 (TRIPODS), a Sloan Research Fellowship, and a Google Faculty Research Award.

Review summaries:
The paper considers an "online search problem", which includes ski rental and variants as special cases and is also applicable to a classical scheduling problem and online bin packing, and proposes an approach for solving these problems in a learning-augmented setting. The online search problem is very generic: An input sequence is known *offline*, but the actual online input is a prefix of this sequence of unknown length. The goal is to minimize some cost. Some assumptions need to be satisfied, e.g. if A and B are solutions to two subsequences then the combined solution of A and B is feasible for the concatenation of the two subsequences (and the cost of the combined solution is at most the sum of the individual costs). Essentially, this is an abstract version of a generalization of ski rental. Although scheduling and bin packing don't have the property of the online input being a prefix of a known offline input, they can be reduced to the online search problem at the loss of a 1.5 factor in the competitive ratio (the classical competitive ratios for the scheduling and bin packing problems are roughly 1.9 and 1.6 respectively, so a bit higher than those 1.5).  The paper first gives a 4-competitive algorithm for the online search problem (using a standard doubling technique) and a prediction-augmented algorithm with consistency 1+eps and robustness 5+5/eps for any eps (which is pareto-optimal up to a constant factor in the robustness). Here, the prediction is the optimal cost for the online input (or equivalently, the length of the online input). The competitive ratio as a function of the prediction error has an unusual asymmetric shape, which motivates the paper's main contribution:  The main contribution is a regression approach to generate this prediction: It is assumed that for any instance, some feature vector x can be observed at the start, and if z is the optimal value of the instance, then the pair (x,z) comes from some (unknown) probability distribution. Since z is needed as the prediction for the learning-augmented algorithm, the goal of the regression approach is to learn a function f that maps x to z. However, the loss function used for learning is not simply an l1 error or similar, but rather a carefully crafted loss function that serves as a proxy of the competitive ratio as a function the true optimal value z and the predicted value f(x). Such a non-standard loss function is needed because of the asymmetric nature of the competitive ratio as a function of the prediction error. Upper and lower bounds on the sample complexity are given so that the resulting algorithm has competitive ratio close to 1+eps with high probability, where epsilon (roughly speaking) is the loss of the best function f from the considered function class.

This paper studies learning augmented algorithms from the perspective of regression.  In particular, this paper studies both how to construct predictions (via regression) and how to use them online for the online search framework.  The online search framework captures problems such as ski rental, online scheduling on identical machines, and online bin packing.  The first main result of this paper consists of tight bounds (up to constants) for robustness and consistency for the online search problem with predictions of the input length.  Next, the paper studies how to predict the value of the optimal solution using regression under the assumption that each instance of the problem has a feature vector x associated with it.  To do this, a novel loss function is proposed that takes into account the competitive ratio of the algorithm utilizing the predicted values.  Nearly tight sample complexity bounds are given for the regression problem. 

Learning-augmented algorithms have been recently proposed as a way to utilize machine-learned predictions in online algorithm design. This paper considers the related problem of how to learn from past data so that online algorithms can obtain improved performance. Specifically, the paper introduces a general online search problem and design online algorithms for it, both without using predictions and using them. The online search framework is fairly general and encompasses well-studied problems such as generalized ski-rental, load balancing and bin packing. Given a single real-valued predicted parameter, the authors design an algorithm that is $(1+\epsilon)$-consistent and $O(1/\epsilon)$ robust.   Secondly (and more interestingly), the paper designs a learning algorithm to efficiently learn such a parameter given sample access to a data distribution. The authors show that utilizing the structure of the online algorithm, one can define an asymmetric loss function such that the empirical minimizer of this loss function serves as a good prediction for the online algorithm. 

This paper focuses on using regression-based ML-predictions in online search problems. In particular, they construct a new loss function that incorporates the asymmetric behavior of the competitive ratio to generate these ML predictions. They show that their proposed algorithm has nearly tight sample complexity bounds under the standard model (when a perfect predition is available in $\mathcal{F}$), and can also achieve good sample complexity guarantees in the agnostic setting.