Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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).

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

The presentation is mostly clear and overall this paper is a candidate for acceptance at Neurips.

Minor comments:
- 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.
- 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?
- The order of the arguments y and hat{y} in Definition 6 is different from how it is used in Definition 7.


POST-REBUTTAL COMMENTS:
I 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.
limitations_and_societal_impact: Limitations yes, potential negative societal impact no (checklist says that they are not aware of potential negative societal impact)
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

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.

A 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.
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 

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.

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.

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

Overall the paper is well-written and easy to read. The paper tackles a timely problem; and the results are non-trivial and interesting.

Minor comments:
- Line 104: The variable k has already been used for the number of options in the previous line.
- Line 108, 118, 138: The Predict-and-Double algorithm referred here has not been defined yet.
- Line 182: A natural idea, then, *is* to progressively …
- Line 195: Did you mean “largest”?

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: *Originality / Significance*

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

*Quality*

The 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.
1. 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?
2. The loss function looks difficult-to-optimize computationally. How can we get an $\epsilon$-SEM rountine?
3. There seems to be a mismatch between the upper (thm 12) and lower bound (thm 13) in the agnostic setting.

*Clarity*

The paper is clearly written and well organized. I particularly like how the authors motivate their final algorithm step by step.



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_title: null

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)