Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper discusses three problems in the context of online computing with a sample. In this context the online algorithm is presented with a random sample of a $p$-fraction of the input sequence, and then as to serve the rest in adversarial order. The three problems are load balancing (of restricted jobs), facility location, and Steiner tree. In all three cases, the worst case competitive ratio is logarithmic in input sequence length, for fully adversarial sequences. This paper shows substantial improvement for, say, constant $p$. In the case of load balancing, the improvement is mostly if the optimum is not too small. In the other two problems, the improvement is more impressive: it's logarithmic in $1/p$. The methods used in the algorithm for the load balancing case (proportional response and multiplicative weights) are also substantially different from the methods used for the other two problems (augmenting a good solution for the sample, using a standard algorithm for the worst case).
strengths_and_weaknesses: This is a very nice paper that gives strong results (mostly for facility location and Steiner tree) in a recently explored model of beyond worst case online computing. The algorithms are simple and natural.

The main weakness is that there are no matching lower bounds. In fact, the authors themselves point out that there is a better worst case result for facility location that has the potential to be used to improve slightly their beyond worst case upper bound.
questions: None.
limitations: Irrelevant.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper looks at the problem of learning in an online setting where instead of seeing all points one by one, they give a sample of the points and then use it as an initial set to achieve better bounds for the problems, the restricted assignment load-balancing problem, the Steiner tree network design problem, and facility location clustering. Assuming a p fraction of the points is observed as a sample, they bound the competitive ratio using a function of p. They provide an algorithm, Learn-&-Load for load balancing which gives a $1+\epsilon$ ratio (plus an additive factor that depends on the logarithm of the number of machines). They also provide algorithms for Steiner tree network design problem and facility location clustering that has a ratio of $O(\log 1/p)$.
strengths_and_weaknesses: - Originality: The idea of using sampling to pre-learn information and improve competitive ratios is an idea they are borrowing from a earlier work as they have stated. Similar ideas have also been used in some online clustering algorithms as well. The work of the paper is to mainly introduce the algorithms that perform well.  They basically use the idea to solve 3 online learning problems. 

- Quality and Clarity: The paper is well written and clearly formatted. It is easy to follow the flow.

- Significance:  This extends the use of the sampling model to cover three interesting problems. However, it is not entirely clear how significant it is to find improved algorithms for this specific set of problems.
questions: How does this compare to the models where you have some hints or predictions on how the data points would be rather than sampling upfront? Just curious.
limitations: The paper states the limitations of the methods they have proposed and the non-optimality of the bounds they have provided for the load-balancing problem. They note that the current method they have suggested cannot be directly improved and leave the discovery of the improved bounds as an open problem.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper develops "Online Algorithms with a Sample" for the problems of online makespan minimisation on related machines, online facility location and online Steiner tree. 

Online Algorithms with a Sample is a relatively new model that assumes that the an arbitrary instance I is chosen by the adversary and the Algorithm receives a random p-fraction of the instance before having to process the instance in an online fashion. The main idea behind the model is that the p-fraction naturally serves as a training set for the algorithm. The paper provides algorithms within this model that essentially have a performance guarantee independent of the size of the input (which is possible in the classic worst-case online model). The exact bounds can be found on lines 49 and 56 of the paper. The (not so surprising) caveat is that the performance now depends on p -- the size of the fraction of the input that the algorithm has access to. Depending on the particular problem and input this can be quite powerful (for example in the unrelated machines scheduling problem if the optimal makespan is much higher than the number of available machines).
strengths_and_weaknesses: Strengths:

I really enjoyed reading the paper, it considers a relatively new but very natural model and proves very interesting results. The highlight, is probably the result on the scheduling problem, which combines known observations with a very simple multiplicative weights update algorithm to derive the obtained result. The latter two results are also quite elegant, although perhaps a tad too simple for justifying acceptance on their own.

Weaknesses:

I could only identify minor weaknesses in the paper. First, it seems that there is an implicit assumption on a known upper bound on the job size with respect to the scheduling problem. This should be discussed further. It would be nice to also have a discussion about where the difficulty lies in extending/adapting the results for the unrelated machines setting. Finally, I think the model lends itself very well to experiments and I would be interested to see to what extent the suggested model outperforms classical algorithms.
questions: Am I right about the implicit assumption regarding the upper bound on the job sizes, or am I missing something?
limitations: Yes, they have.
review_title: null

Meta-review: metareview: This paper gives improved bounds for the assignment load-balancing problem, the Steiner tree network design problem, and facility location clustering in the case when a some of the input is given as a sample.  This is a strong paper at the intersection of online algorithms and learning.
confidence: Certain
Decision: Accept