A Regression Approach to Learning-Augmented Online Algorithms
Authors: Keerti Anand
Rong Ge
Amit Kumar
Debmalya Panigrahi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Learning Aided Algorithm Design
learning augmented online algorithms
learning theory
Optimization
Algorithms under uncertainty

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.

A Regression Approach to Learning-Augmented Online Algorithms
Keerti Anand
Rong Ge Department of Computer Science Duke University Durham, NC 27705 ronggeEcs duke. edu
Department of Computer Science
Duke University
Durham, NC 27705
kananddca. duke.edu
Amit Kumar
Debmalya Panigrahi
Department of Computer Science Indian Institute of Technology Hauz Khas, New Delhi 110016 amitkêcse, iitd. ernet.in
Department of Computer Science
Duke University
Durham, NC 27705
debmalya@cs, duke, edu
Abstract
The emerging field of to predict future input parameters and thereby improve the performance of online algorithms. Since these parameters are, in general, real-valued functions, natural approach is to 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 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 statistical error.
online algorithms uses ML techniques
Introduction
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 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 using ML predictions online algorithms, but does not address the question how these predictions are generated. This raises the question: what
learn from data that will improve the performance of online algorithms? Abstractly, this question comes in two inter-dependent parts: the first part learning problem where we seek learn 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 the first part of this design pipeline, namely develop regression approach generating ML predictions for online algorithms.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Before delving into this question further, we note that there has been some recent research that focuses on the learnabllity of predicted parameters online algorithms. Recently, Lavastida er al. [3], building on the work of Lattanzi et al. 322. took 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-vate vealev function, which motivates regression approach to earning-augmentt 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 (RCH framework. In this framework, there as an input sequence Σ 01, 2..... available offiie,, and the actual online input is prefix of this sequence Er = 01, 02,02...., or, where the length of the prefix 7 revealed online. Namely, in each online step t> 0, there are two possibilities: either the sequence ends, i... T = t, 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 Σ, o...... Tr. The goal is to obtain a solution that is of minimum cost among all the feasible solutions for the actual input sequence Σy-
We will discuss applicability of the ONLINESEARCH framework in more detail in Section 1.2 but for quick illustration now, consider the ski rental problem in this framework. In this problem, if the sequence continues on day 1, 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 ONLINES 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 + e for a aepee-prrretter 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.c., 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.
1.1 Our Contributions
As a warm up, we first give an algorithm called DOUBLE for the ONLINESEARCH problem without predictions in Section 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-DOUS ONLINESEARCH problem with predictions. We show that the PREDICT-AND- DEDDICT-A DOUBLE algorithm has a consistency of 1 1++ and robustness of O(1/c), for any hyper-parameter c > O. We also show that this tradeoff between consistency and robustness is asymptotically tight.
for the
Our main contributions are in Section 4 In this section, we model the question of obtaining a learning- augmented algorithm for the ONL assume that the input comprises a feature vector x that is mapped by an unknown real-valued function to an input for the ONLINESEARCH problem In the training phase, we are given a set of labeled samples of the form (z, z) from some (unknown to the algorithm) data distribution D. The goal of the learning algorithm is to produce mapping from the feature space 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 E obtains a competitive solution for the actual input & in the test sample (that is unknown to the algorithm).
problem in a regression framework. Specifically, we
The learning algorithm employs regression approach in the following manner. It assumes that the function ʃ 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
2

---

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 (#ad) for obtaining competitive ratio of 1 ++ c, where H and d respectively represent the log- log-range of the optimal cost and measure of the expressiveness of the function class F called its pseudo-dimensee 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 2, 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.
We also
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 given the cost of optimal solution. In that case our algorithms gives a competitive ratio c(1 + e), which can still be better than the competitive ratio without predictions (see examples in next subsection).
1.2 Applicability of the ONLINESEARCH framework
The ONLINESEARCH framework is applicable whenever an online algorithm benefts 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 in more detail in section 3) successively predicts the optimal value of the solution and appends the corresponding solution to its output.
(explained
Ski Rental with Multiple Options. Generalizations of the ski rental problem with multiple options
have been widely studied (e.g.. [ 19I), recently with ML predictions [44). Suppose there are V options (say coupons) at our disposal, where coupon i costs us C, and is valid for d; number of days. Given such a setup, we need to come up with a schedule: {(4,, ix), k = 1, 1.2.... that instructs us to buy coupon ig time lg. (The classic ski rental problem corresponds having only two coupons C₁ = 1, di = 1 and C2 = B, d2 - 20.) Our ENACHE framework is applicable here: solution that allows to buy coupons valid time L is also a valid solution for all times s S I. Further,
can be implemented efficiently as we can compute (t), for any time& & using a dynamic program.
DEDICCT-NND-DUBEE
Online Scheduling, Next, we consider the classic online scheduling problem where the goal is to assign jobs arriving online to set of identical machines so to minimize the maximum load 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 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 D. The ONLINESEARCH framework applicable here with a slight modification: whenever PREDICT-AND -ODU-----UBLE 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 ł jobs is valid for any prefix. We get a competitive ratio of 1.5 + Oc) 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 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 ad advattaee of this result. In this case, the application is not as direct, because predicting OPT does not yield the better algorithm. Nevertheless.
Intuitively. the notion of aseudo-dimensie extends that of the well-known VC dimension from binary to real-valued functions.
3

---

an inspection of the algorithm in [5] reveals the following strategy: The items are partitioned into three groups. The items of size 2 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 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 ONLINESEARCE framework where we predict OPT'. As earlier, the ONLINESEARCH framework can be applied with slight modification: whenever PREDICT-AND AND-DOUBLE tries to buy a solution corresponding to a predicted value of OPT', we execute the -.5competiiive algorithm based on this value. The problem still satisfies the property that a solution for / items is valid for any prefix.
1.3 Motivation for a cognizant loss function
In this work, we explore the idea 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 the user features to predict their behavior in terms of the workload submitted to the server. A typical feature vector would then be binary vector encoding of the set of users eurrently active in the system, and based 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 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.
1.4 Related Work
There has been considerable recent work in incorporating ML predictions in online algorithms. Some of the problems include: auction pricing (36), ski rental [41
13 44 6) caching [35 28 45)
scheduling [1
32 39 frequency estimation (27. Bloom filters 38 online linear optimization 16
speed scaling 11 set cover [12, bipartite and secretary problems [.. 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 33 regression approach to the problem in this paper.
In contrast, we use
The PAC learning framework was first introduced by 443 in the context of learning binary classifica- tion 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 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 hypothesis is taken to be the expected squared loss, and gave uniform convergence results for this setting. In this paper, we use demenoniiennioon and corresponding sampling complexity bounds in quantifying the complexity of the regression learning problem of predicting input length.
dimension to

---

2 ONLINESEARCH without Predictions
As warm up, we first describe simple algorithm called DOUBLE (Algorithm [T for the ONLI NESEARCH 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 building block for the algorithms that we will develop later in the paper, hence, we describe it and prove its properties below.
First, introduce some notation.
Definition 1. We use (PT(t) to denote an optimal (offline) solution for the input prefix of length t; overload notation to denote the cost of this solution by (PT as well.
Definition 2. Given an input length T and any a > O, we use MIN-LENGTH(a,T T) to denote the smallest length t such that OPT(t) 2 a OPT(T). The monotonicity property of OPT ensures that MIN-LENGTH(AL T) > T if a > 1, and MIN- MIN-LENGTH((,)) 7) S T otherwise.
Algorithm 1 DOUBLE
Input: The input sequence I. Output: The online solution SOL.
Set i == 0. To := 1, SOL := 0.
for f 1.2....,
if If(-i
Set Ti+1 MIN-LENGTH(2, Tz). Add OPT(T:+1 1) to SOL..
Increment
Theorem 1. The DOUBLE algorithm is 4-competitive for the ONLINESEARCH problem.
3 ONLINESEARCH with Predictions
In the previous section, we described simple online algorithm for the ONLINESEARCII 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 /' for the input length T of an ONLINESEARCH problem instance. Naively, we might trust this prediction completely and buy the solution OPT(?). While this algorithm perfect the prediction accurate, it can fail in two ways the prediction inaccurate: (a) < T and therefore (PT(T) < OPT(T), then the algorithm has a large competitive ratio, and (b) 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 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 OtT(t) for > 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 only slighter larger than 7. then the algorithm adds solution that has cost 2 OPT(T), thereby realizing the worst case scenario in Theorem that achieved without any prediction. Our work-around for this issue is to buy OPT(L) for slightly larger than Í. instead of OPT(T) itself, which secures against the possibility of the actual input being slightly longer than the prediction. We call this algorithm PREDICT-A A AND-DOUBLE (Algorithm 2). Here,
hyper-parameter that offers tradeoff between the consistency and robustness of the algorithm. We also use the following definition:
Definition 3. Given input length and any a > we use MAX-LENGTH(O, T) denote the largest length such that OPT(L) S a OPT(T).
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 PREDICT- AND-DOUBLE algorithm below.
5

---

Algorithm 2 PREDICT-AND-DOBBLE
Input: The input sequence Z and prediction T.
Output: The online solution SOL.
Set SOI. := 0, 4 == MIN-LENGTH( (c/5, 7), and L/ == MAX-LENGTH(1 + t//5,))
Phase 1: Execute DOUBLE while < t1.
Phase 2: At = t1, add (P)( to SOL.
Phase 3: If > f2, resume DOUBLE follows:
Set i = 0, Ty ;= 62 +.
for t t2 + 1, + ......
if = T3
Set T++1 MIN-LENGTH(2.r))
Add OPT(T;+1 - 1) to SOL.. Increment i.
Theorem 2. The PREDICT-AND-DOUBLA algorithm has a consistency of + e and robustness of 5 (1+
We also show that this tradeoff between (1 + coonsisttyy and O(1/c) bounds is essentially tight.
Theorem 3. Any algorithm for the ONLINESEARCI problem with predictions that has consistency bound of + must have a robustness bound of Ω (t).
Having shown the consistency and robustness of the PREDICT-AND-DOUBET 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 for large error.
Lemma 4. Given a prediction i for the input length, the competitive ratio of PREDICT-ADDD- given by:
4, 4
(1+ OFT( (PI(T) t1 IT
CR <
4.T
where t represents the minimum value of t that satisfies OPT(t) 2 f OPT(Î) and t2 represents the maximum value oft that satisfies OpT(t) < ( OPT(T))
4 LEARN TO SEARCH: A Regression Approach
In the previous section, we designed an algorithm for the ONLINESEARCI problem that utilizes ML predictions. Now, delve deeper into how 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.
4.1 Preliminaries
An instance (z. 2) of the LEARNTOSEARCH problem is given by feature E X. and the (unknown) cost of the optimal offline solution E [1, M). The two quantities x and & are assumed to be drawn from joint distribution a subset of functions X + [1, M] and tries to obtain the best function f E F that predicts the target variable accurately. For notational convenience, predict the log-cost of the optimal solution. Note that predicting the log-cost of OPT(I') is equivalent predicting the input length T Furthermore, let D denote the input distribution on Y, where Y = [0, II] and И In M: i.c., we assume that (z, 2) D.
X [1, M. A prediction strategy works with hypothesis class J that
set target y In z, i.e., try
When multiple input lengths might have the optimal cost, can just pick the longest one.

---

We define a LEARNTOSEARCH algorithm A as a strategy that receives a set of m samples S ~ D. for training, and later, when given the feature set to the algorithm), it defines an online algorithm for the ONLINESFARCH 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 for a generic description of an LEARN LEARNTOSEARCH algorithm).
test instance (z, y) D (where y is not revealed
Algorithm 3 A general LEARNTOSEARCE algorithm
Training: Given Sample Set S, the training phase outputs mapping M from every feature vector I E X to an increasing sequence positive integers
Testing: Given unknown sample X, define thresholds M (ar) (7o, 71 7I...)
Set i == 0, SOL: = OPT(To 1).
while (Input has not ended)
if' (SOL is infeasible)
SOL OPT(T++1 1). Increment
We will use the notation CR A y) to denote the competitive ratio obtained by an algorithm A on the instance (zz, y). For given set of thresholds (To, Ti ...,, define iT min; d. Then, A pays total cost of E. OPT(T:), and thus the competitive ratio
CRA y) E OPT(T:)
e²
We define the "efficiency" of a LEARNTOSEARE algorithm by comparing its performance with the best achievable competitive ratio. The optimal competitive ratio for a given distribution may be strictly greater than For example, consider the distribution where x is fixed (say z²) and 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 solution costing 4. The competitive ratio for this strategy (in expectation) is 1.25.
Definition 4. A LEARNTOSEARCI algorithm A is said to be e-efficient if
B. v) S p² +
where p² CR (x.yy y) and A is optimal solution that has full knowledge D and no computational limitations.
(x,
The "expressiveness" of a function family is captured by the following standard definition:
Definition 5. A ser S (21. Im. is said to be "shattered" by class of real-valued
functions S + 10, H] if there exists "wimeesees" R = {r1,T2.... ... Tm E [0, H) such that the following condition holds: For all subsets T C S, there exists an f such that of fxx) > rs if and only if x E T. The dioudoddimension of F (denoted as Pdim(F)) is the cardinality of the largest subset X that shattered by F.
4.2 The Sample Complexity of LEARNTOSEARCH
Our overall strategy is to learn suitable predictor function F and use f(z) prediction in the PREDICT-AND- -AADIITTT----DUBLLEEE DOUBLE algorithm. Note that prediction errors on the two sides (over- and under-estimation) affect the competitive ratio of PREDICT-AND-DOLE different ways. we underestimate OPT(T) by factor less than + the competitive ratio remains 1 + O(c). but larger underestimate causes the competitive ratio climb up to 4. On the other hand, we overestimate OP)(T), then the competitive ratio grows steadily by the ratio of over-estimation, until it reaches 5 (1+ + 2). This asymmetric dependence is illustrated in Figure |
(given by Lemma 4 in
At a high level, our goal is to use regression to obtain the best function f E F. But, the asymmetric behavior of the competitive ratio suggests that we should not use a standard loss function in the regression analysis. Let e be the accuracy parameter for the PREDICT-AND-DE -DOUBLE algorithm, and let In OPT(T) and In 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 -OOD-DDUBLE:
7

---

CR
+ D(c)
(++ 1..-oorn
Figure 1: Competitive ratio of the PREDICT-AND-DOUBE function of the input T, where the prediction is T
alort for fixed prediction as
Definition 6. The c-parameterized competitive error is defined as:
5 when y S ÿ In 5
eV - when In < S
&e (v.
1 (y 5) when < S In (1+ 8)
1 when y > 9 + In +nnnnn11)) (1+
We give more justification for using this loss function the supplementary material, and show that standard loss functions do suffice for purposes. Using this loss function, can measure the error of a function for an input distribution or for a fixed input set:
Definition 7, Given a distribution on the set X Y and function f f: % we define
(f) =
Alternatively, for set of samples, S ~ D", define,
ERs 1 m
Σ Lav f(x.))
Our high-level goal is to use samples to optimize for the loss function called e-parameterized competitive error that we defined above over the function class F, and then use an algorithm that translates the empirical error bound 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 and a function family F. we denote an optimization scheme O S + as e- -aampee Error Minimizing (SEM) if returns a function f e F satisfying:
ERs,c(f) inf [R)s,(())] +
JEF
For the rest of this paper, we will assume that we are given an c- SEM routine for arbitrary c 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-DOURE
Algorithm A LEARNTOSEARCH algorithm with accuracy parameter
Training:
Input:
Sample Set S, Function Family FF
Output:
ff output by an c-SEM algorithm O, i.e., ERg.((f) S inf ERS,(f)) +
Testing:
Given new sample x, set ÿ = f(x).
Predicted prefix length: T = maxorr(t) f.
Call PREDICT-AND -DOUBEE with f and c,
We relate the competitive ratio of Algorithm 4 to the error of function f obtained during training:
Lemma 5. Algorithm has a competitive ratio upper bounded by (1 (1+ 3 BRD..()).

---

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 z to y y- we call this the standard model. We relax this assumption in the more general agnostic model, where the function class FF is arbitrary. terms of the error function, in the standard model, we have inf fer F.R,.( jer sR) 0, while no such guarantee holds in the agnostic model.
4.3 Analysis in the Standard Model
Next, we analyze the competitive ratio of Algorithm 4 in the standard model, ie., when jef (f),,(f)= yer ER),e(f) =.
Theorem 6. In the standard model, Algorithm 4 obtains competitive ratio of 1 + O(e) with probability at least 1 - 8. when using O H-dlog Tog samples, where d = PF)
When the cost of the optimal solution OPT(T) is hard to compute, we can replace the offline optimal with an online algorithm that achieves competitive ratio given the value of T get the following: Corollary 7. In the standard model, if there exists c-competitive algorithm for OPT(T) given the value of prefix-length т, Algorithm 4 obttain a competitive ratio of c(1 + O())) with probability at least 1- 6, when using O H-dlog log à
samples, where d = (J)
We also show that the result in Theorem tight up to a factor of H log 1/c:
Theorem 8. Let FF be a family of real valued functions such that there exists a function f : Y that f* (x) = y and let d = Pdim(F). There exists an instance of the LEARNTOSEARCH problem that enforces any algorithm to query 52 dllog
samples in order to have an expected competitive
ratio of + e with probability 2 1 5.
4.4 Extension the Agnostic Model
In the agnostic model, we no longer assume function f E F that predicts the log-cost y perfectly. It possible that the true predictor outside F, or in more difficult scenarios for any feature æ, the behaviour of the log-cost may be entirely arbitrary.
We first show that the loss function e-parameterized competitive error defined earlier is still reasonable proxy for the competitive ratio. Specifically, we show that any algorithm that hopes to achieve competitive ratio of 1 + O(e) must use prediction f E F whose error ERD,,(f) is bounded by O(e). We formally state this below:
Lemma 9. Let A be algorithm for LEARNTOSEARCH that has access predictor ; X + [0, H) for the log-cost Then, there exists distribution D and function f with the property such that ((z,g)>D [CRA(Z, v)] 1
ERD,e
Unlike in the standard model, we no longer have that for any O, E 0. Therefore, we need to first quantify the performance of an ideal algorithm that uses predictors from F.
(f),
Definition 9. Let x(c) = min (f). Then, Ay is the solution to the equation: c = x(c).
Ay 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 o dependd on We first show that this is a reasonable definition in that the solution to the equation is unique:
Lemma 10. For given function family F and distribution D, the value of A unique.
We also give an algorithm that can approximate AF (Algorithm 5)
Lemma 11. | C. (H.dlog log 1 for suitable constants C > 0,8 S 1, and e S Ay, then with probability at least 1 - 8, we have e/6 < AF < 5E/3, where is as returned by Algorithm 5
We are now ready to define our LEARNTOSEAACH algorithm for the agnostic model. This algorithm simply Algorithm 4 where the accuracy parameter is set to the value of & returned by Algorithm 5

---

Algorithm 5 Procedure to estimate A
Input: Sample Set S, and function family F
Let be an accuracy parameter given by the size of the sample set
: Compute: f such that (R), & minser ERg + 3.
Choose
while < (f)
E E 2e.
Recompute f s.t. ERs minser ERs. (f) +
Return 8.
Theorem 12. In the agnostic model for function family F, Algorithm 4 with accuracy parameter
from Algorithm 5 obtains a competitive ratio of + O (Ar) with probability at least 5, when
using O H-dlog
llgg
samples, where d = Pdím((F.
We also lower bound the sample complexity a LEARNTOSEARCH algorithm: Theorem 13. Any LEARNTOSEARCH algorithm that is e-efficient with probability at least 1 log
must query Ω
samples.
4.5 Robustness of Algorithm
So far, we have established the competitive ratio of Algorithm| 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/e), which matches the robustness guarantees in Theorem for the PREDICT-AND-DoV
algorithm.
Theorem 14. Algorithm is 5(1 !) O (+) robust.
5 Conclusion, Limitations, and Future Work
In this paper, we studied the role of regression in making predictions for learning-augmented online algorithms. In particular, problems such as ski rental and its gencralizations, online scheduling, online bin packing, etc. and showed that by using carefully crafted loss function, optimal algorithms for this problem. One assumption that holds for the above problems, but not for other problems such 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 MI. predictions for online problems.
used the ONLINESEARCH framework that includes variety of online
obtain predictions that yield near-
6 Acknowledgements
This research was partially funded by the Indo-US Virtual Networked Joint Center project No. IUSSTE/JC-0177001,, Keerti Anand and Debmalya Panigrahi were supported in part by NSF Awards CCF-1955703, CCF-1750140 (CAREER), and ARO Award 1911NF21 10230. Rong Ge was also supported part by NSF Awards DMS-2031 2031849, CCF-1704656, CCF-184517 (CAREER), CCF-1934964 (TRIPODS), Sloan Research Fellowship, and Google Faculty Research Award.
10

---

References
[1] Lingging Ai, Xian Wu, Lingxiao Huang, Longbo Huang, Pingzhong Tang, and Jian Li. The multi-shop ski rental problem. In Sujay Sanghavi, Sanjay Shakkottai, Mare Lelarge, and Bianca Schroeder, editors, ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS '14 Austin, TX, USA June 20, 2014, pages 463-475. ACM, 2014.
[2] Susanne Albers. Better bounds for online scheduling. SIAM Journal on Computing, 29(2): 459 473, 1999.
[3] Noga Alon, Shai Ben-David, Nicolo Cesa-Biance and David Haussler. Scale-sensitive di- mensions, uniform convergence, and learnability. Journal of the ACM (JACM), 44(4):615-631, 1997.
[4] Keerti Anand, Rong Ge, and Debmalya Panigrahi. Customizing ML predictions for online algorithms. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 Proceedings of Machine Learning Research, pages 303-313. PMLR, 2020.
[5] Spyros Angelopoulos, Christoph Dürr, Shahin Kamali, Mare P. Renault, and Adi Rosén. Online bin packing with advice of small size. In Frank Dehne, förg-Rüdigerr Sack, and Ulrike Stege, editors, Algorithms and Data Structures 14th International Symposium, WADS 2015, Victoria BC, Canada, August 5-7, 2015. Proceedings, volume 9214 of Lecture Notes in Computer Science, pages 40-53. Springer, 2015.
[6] Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Mare P. Renault. Online computation with untrusted advice. Thomas Vidick, editor, 1 1ith Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washinglon, USA, volume 151 of L/Plcs, pages 12:1-52:15. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2020.
[7] Martin Anthony and Peter L. Bartlett. Function learning from interpolation. Comb. Probab. Comput., 933):113-225, 2000.
[8] Martin M Anthony and Peter Bartlett. Learning neural networks: theoretical foundations. Cambridge University Press, 1999.
[9] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev, Secretary and online matching problems with machine learned advice. Hugo Larochelle, Mare Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Infor- mation Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[10] Yossi Azar and Oded Regev. On-line bin-stretching. In Michael Luby, José D. P. Rolim, and Maria Serna, editors, Randomization and Approximation Techniques in Computer Sci- ence, Second International Workshop, RANDOM '8, Barcelona, Spain, October 8- 8-10, 1998, Proceedings, volume 1518 Lecture Notes in Computer Science, pages 71-81. Springer, 1998.
[11] Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented energy minimization via speed scaling. Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[12] Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dun dual method for learning augmented algorithms. Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tiee Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.

---

[13] Soumya Banerjee. Improving online bent-or-buy algorithms with sequential decision making and ML predictions. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[14] Yair Bartal, Amos Fiat, Howard J. Karloff, and Rakesh Vohra. New algorithms for an ancient scheduling problem. In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual A ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 51-58. ACM, 1992.
[15] Peter L. Bartlett, Philip M. Long, and Robert C. Williamson, Fat-shattering and the learnaiilityy of realevalued functions. J. Comput. Syst. Sci., 52(3):434 452, 1996.
[16] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online learning with imperfect hints. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 822 831. PMLR, 2020.
[17] Martin Böhm, Jirí Sgall, Rob van Stee, and Pavel Vesely. two-phase algorithm for bin stretching with stretching factor 1.5, J. Comb. Optim., 34(3):810-828, 2017.
[18] Cecil C Craig. On the tchebychef inequality of bernstein. The Annals of Mathematical Statistics, 1(2):94-102, 1933.
[19] Rudolf Fleischer. On the bahncard problem. Theor. Comput. Sci., 268(1):161-174, 2001.
[20] Rudolf Fleischer and Michaela Wahl. Online scheduling revisited. In Mike Paterson, editor, Algorithmss - ESA 2000, 8th Anmual European Symposium, Saarbrücken, Germany, September 5-8, 2000, Proceedings, volume 1879 of Lecture Notes in Computer Science, pages 202-210. Springer, 2000.
[21] Michaël Gabay, Vladimir Kotov, and Nadia Brauner. Online bin stretching with bunch tech-
niques. Theor. Comput. Sci., 602: 603-103-113, 2015.
[22] Michaël Gabay, Nadia Brauner, and Vladimir Kotov. Improved lower bounds for the online bin stretching problem. 4OR, 15(2): 189- 2017.
[23] Gabor Galambos and Gerhard Woeginger. An on-line scheduling heuristic with better worst- case ratio than graham's 's list scheduling. SIAM Journal on Computing, 22(2):349-3555 1993.
[24] Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, Califormia, USA, pages 2319-2327, 2019.
[25] Todd Gormley, Nicholas Reingold, Eric Tomn, and Jeffery Westbrook. Generating adversaries for request-answer games. In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithums, pages 564-565, 2000.
[26] Ronald L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal of Applied Mathematics, 17(2)416-429, 1969.
[27] Chen Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning- based frequency estimation algorithms. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, IA, USA, May 6-9, 2019. OpenReview.net, 2019.
beaseing-based
[28] Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted caching with predictions. In 47th International Colloquium on Automata, Languages, and Programming. ICALP 2020, 2020.
[29] David R Karger, Steven J Phillips, and Eric Torng. A better algorithm for ancient scheduling problem. Journal of Algorithms, 20(2):400-430, 1996.
[30] Michael J. Kearns and Robert F. Schapire. Efficient distribution- free learning of probabilistic concepts. J. Comput. Syst. Sci., 4843).464-497, 1994.
12

---

[31] Hans Kellerer and Vladimir Kotov. An efficient algorithm for bin stretching. Oper. Res. Lett., 41(4):343-346 33443,6,,,,, 2013.
[32] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1877-1877. SIAM, 2020.
[33] Thomas Lavastida, Benjamin Moseley, R Ravi, and Chenyang Xu. Learnable and instance-robust predictions for online matching, flows and load balancing. arXiv preprint arXiv:2011.1174. 2020.
[34] Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. Rent, lease, or buy: Randomized algorithms for multislope ski rental. SIAM Discret. Math., 26(2):718-7366 2012.
[35] Thodoris Lykouris and Sergei Vassilvitskii. Competitive eaching with machine learned advice. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmssmsssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 3302-3311. PMLR, 2018.
[36] Andres Muñoz Medina and Sergei Vassilvitskii. Revenue optimization with approximate bid predictions. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 1858-1866, 2017.
[37] Adam Meyerson. The parking permit problem. In 46th Annual IEEE Symposium Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 274-284. IEEE Computer Society, 2005.
[38] Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Desa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 462-471, 2018.
[39] Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In Thomas Vidick, editor, 1thh Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of L.Pllss, pages 14:1-14:18. Schloss Dagstuhl- Leibniz-7entrum für Informatik, 2020.
[40] David Pollard. Empirical processes: theory and applications. In NSF-CBMS regional conference series in probability and statistics, pages 1-86. JSTOR, 1990.
[41] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML pre- dictions. In Samy Bengio. Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi and Roman Garnett, editors, Advances in Neural Information Processing Sys- tems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 9684-9693, 2018
[42] Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1834-1845, SIAM, 2020.
[43] Leslie G. Valiant. A theory of the learnable. Commun. ACM, 27(11): 1984.
[44] Shufan Wang, Jian Li, and Shiqiang Wang. Online algorithms for multi- shop ski rental with machine learned advice. In Hugo Larochelle, Mare Aurelio Ranzato, Raia Hadsell, Maria- Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 621 2020, virtual, 2020.
13

---

[45] Alexander Wei. Better and simpler learning-auee augmented online caching. In Jaroslaw Byrka and Raghu Meka, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/ANDOOM 2020, August 17-19, 2020, Virtual Conference, volume 176 of LIPIcs, pages 60:1-60:17. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2020.
14


Reviews:
[{"review_id": "vF9NgYxl_Sf", "reviewer": "Reviewer_Nz3r", "summary": "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. \n\nSecondly (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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper proposes a natural online problem named as the ''online search’’ problem as a common formalization of online problems where knowledge of the value of the optimal solution suffices to obtain better than worst-case guarantees. Unsurprisingly, a natural algorithm based on the common ``doubling trick’’ gives a competitive ratio of 4. Given access to a single predicted parameter $(\\hat{T})$, the proposed Predict-and-Double algorithm gives an essentially optimal tradeoff of $(1+\\epsilon)$-consistency and $O(1/\\epsilon)$ robustness. Both the design and analysis of this algorithm is fairly natural.\n\nThe paper then tackles the important problem of efficiently learning the predicted parameter given only sample access to the data distribution. The paper demonstrates that using traditional loss functions (which are symmetric around the true value) are not sufficient to obtain optimal sample complexity for this setting. Instead, the authors design a specific loss function that is tailored to the behavior of the Predict-and-Double algorithm. \n\nOverall the paper is well-written and easy to read. The paper tackles a timely problem; and the results are non-trivial and interesting.\n\nMinor comments:\n- Line 104: The variable k has already been used for the number of options in the previous line.\n- Line 108, 118, 138: The Predict-and-Double algorithm referred here has not been defined yet.\n- Line 182: A natural idea, then, *is* to progressively …\n- Line 195: Did you mean “largest”?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "aRR2kc1ep8S", "reviewer": "Reviewer_8woq", "summary": "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).\n\nThe 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:\n\nThe 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of the paper seems original and the regression approach may be applicable to other problems, especially when the competitive ratio as a function of the prediction error is asymmetric. For this reason, the paper's contribution has the potential of being significant, but it is hard to judge whether it really is. Some case study might be useful: Does the approach actually lead to practical performance gains for any of the considered problems mentioned in the introduction? How would the feature vector x and the hypothesis class of possible functions f be chosen? For scheduling and online bin packing I do not personally expect much/any improvement because the 1.5 factor loss due to the reduction is already close to the classical competitive ratio, and loss due to prediction error will come on top of this.\n\nThe presentation is mostly clear and overall this paper is a candidate for acceptance at Neurips.\n\nMinor comments:\n- Line 118 and 138 it is hard to understand what you mean by \"tries to buy an OPT\" as we have not read yet what those algorithms do.\n- It was not completely clear to me whether for bin packing you still also need a prediction of the number of items of size between 1/2 and 2/3. If I understand correctly, then the prediction of OPT’ serves as a substitute for this?\n- The order of the arguments y and hat{y} in Definition 6 is different from how it is used in Definition 7.\n\n\nPOST-REBUTTAL COMMENTS:\nI appreciate the example given for what could be used as a feature vector. It is still unclear whether it would lead to practical improvement though. The authors are right that the state-of-the art (in terms of worst-case guarantee) algorithms for bin packing and scheduling are very complicated, but there also exist very simple algorithms with similar guarantees (e.g. BestFit/FirstFit for Bin Packing are 1.7-competitive for Bin Packing and typically much better in practice), so I remain skeptical about practical benefits for these problems. Overall, I retain my slightly positive score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations yes, potential negative societal impact no (checklist says that they are not aware of potential negative societal impact)", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "XdWXG2H9oyf", "reviewer": "Reviewer_2bKw", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*Originality / Significance*\n\nThis paper is completely out of my field so unfortunately I can't talk much on its originality or signification. My understanding is that the authors propose a new regression approach based on a new loss function to generating ML predictions for online search problems. The overall problem appears quite interesting to me.\n\n*Quality*\n\nThe paper tells a complete story. All theoretical results are intuitively explained and they make sense to me. I only have some minor comments listed below.\n1. I don't have a good understanding of how restricted these composability and monotonicity assumptions are. Could you intuitively explain how they are used in the analysis and what will fail without them?\n2. The loss function looks difficult-to-optimize computationally. How can we get an $\\epsilon$-SEM rountine?\n3. There seems to be a mismatch between the upper (thm 12) and lower bound (thm 13) in the agnostic setting.\n\n*Clarity*\n\nThe paper is clearly written and well organized. I particularly like how the authors motivate their final algorithm step by step.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors briefly discussed about limitations and pointed out some future work directions in their conclusion section. I don't have major concerns on this paper, and some minor suggestions are listed in the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5 hours"}, "extra_text": {}}, {"review_id": "0pHBNhYywOM", "reviewer": "Reviewer_nzMd", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this is a technically strong and well-written paper which looks at an important problem in learning-augmented algorithms - namely, how should these predictions be constructed.  This paper nicely complements other recent work on this topic - Anand et al. 2020 and Lavastida et al. 2020.\n\nA minor issue is the assumption that each instance of the online problem is associated with a feature vector x that is revealed to the online algorithm up front (in order to use the learned regression model online).  Some discussion as to how to realize this assumption in practice might strengthen the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is discussion of the limitations of the work, and I do not see any issues in terms of negative societal impact stemming directly from this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work makes progress in the recently popular "learning-augmented algorithms" framework and argues that a regression-based approach forms a correct learning solution for many of the problems. The authors do a complete study of this question; of particular interest is their exploration of the learning problem itself. Here they show that special care must be taken in setting up the loss function for the regression problem to achieve good results. Overall, a solid contribution. 

Decision: Accept (Poster)