Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Considering the fact that the worst-case performance of algorithms could be improved by equipping them with good machine-learned predictions, together with the increased use of "multiple" machine-learned models for solving a specific task, with each of them being specialized on a part of the problem, the paper tries to adapt algorithms for the case where multiple machine-learned predictors are used instead of a single one. They try to design algorithms for this case and bound the overhead caused compared to the single predictor case (since now the best predictor should be identified among the $k$ predictors) and the error that the algorithm incurs compared to the case where it is given the best predictor only. They investigate this problem for 3 fundamental problems being bipartite matching, load balancing and clairvoyant scheduling. 

They start by proving that the complexity of looking for $k$ predictions is a factor of $k$ larger than that of a single predictor. 

They further move to the three specific problems. First, they consider the min-cost bipartite matching problem with multiple predictions available. They show the running time of the state of the art algorithm for solving this problem for the case of single prediction is comparable to that of considering $k$ predictions when $k\leq O(\sqrt{n})$ which suggests that learning with $k$ predictions is coming for free in this case.

They further consider the problem of online load balancing (where a weight vector is to be learned to distribute a task between several machines with the goal of minimizing the maximum machine load) and show that there is a polynomial time algorithm that can output $k$ weight vectors which can minimize the expected minimum error with some bounded error which comes with a logaritmic cost with respect to $k$.

Finally they consider the problem of scheduling $n$ jobs on a machine when the time that each process takes for completion is not known prior to the completion of the process (clairvoyant scheduling). The goal is to minimize the sum of the completion times. They show that learning the best $k$ permutations is doable in polynomial time with bounded error compared to the best predictor.
strengths_and_weaknesses: Strengths:
- The paper considers a very well motivated problem. 
- The paper is very carefully written.
- I believe there will be many applications and room for future work. Generalizing the results of the paper for any $k$ predictors solving any task and then bounding the error with respect to the error of each of the predictors would be very interesting.

Weaknesses:
- The supplementary does not match the main. Supplementary is an extended version of the paper and does not include only the proofs of the Theorems or Propositions stated in the main. Some of the mismatches: Theorem 2.1 in the main is Theorem 2.3 in the supplementary, Thorem 5.4 in the main is Theorem 5.7 in the supplementary etc.
- Section 2 is not self-contained. Without referring to the supplementary, it is almost impossible to understand what this section is trying to say or what the results are. Since most of the coming results in other sections are based on Theorem 2.1, I think it is important that enough details about this Theorem is provided in the main.
- The writing could be improved. Sometimes it is very hard to understand what you try to convey by the wording you use. I could not understand the sentence written lines 23-25. I also could not really understand what you try to do in the paper by only reading the abstract. More clear explanations would be great.
-Typo in line 25
- Although all the results are proven and there is no need for experiments to show that the theory works in practice, I believe experiments are missing from the paper and one could design many interesting experimental setups to show that the theory is working in practice.
questions: - How is the quality of the predictors affecting the performance of the final algorithm which takes into account all predictors? For each of the algorithms proposed, which of the following is more fabvorable? to have one very accurate and several very inaccurate predictors, or to have good performance in all predictors? Are the results also dependant on the performance of the worst predictor?

- Why are there no experiments conducted? It would be nice to see whether the running times in practice also match the ones stated in the paper or see the quality of the found solution compared to the algorithm using only the best predictor. Also having multiple machines with different performances and then analyzing the performance of the algorithm would be very interesting. Another set of interesting experiment is to vary $k$. I believe one can think of many more interesting experimental setups that could support the theory.

- Was there a reason for taking this 3 problems? How do you think one can generalize the result for other problems?
limitations: NA
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper attempts to examine solving certain online problems using a set of $k$ predictions and examine the statistical complexity of obtaining a good algorithm that uses such $k$ predictions. These problems include min-cost perfect matching, online load balancing and non-clairvoyant scheduling for total completion time. The task is to perform as well as the best prediction.

strengths_and_weaknesses: Originality: The paper’s work seems to be original. Using $k$ predictions to supplement online algorithms has been explored by multiple works in the past. In this paper, it has been extended to 3 other problems. The algorithmic techniques for Section 3 and Section 4 are fairly standard and known. Exploring the learnability of using such $k$ predictions seems to be a new undertaking. The algorithm for Section 5 also seems to be new work.

Clarity: The non-technical part of the paper is clearly written and easy to understand. Due to paucity of time, I could not verify the technical aspects of the paper but the theorem statements “make sense” to me. I found that the authors motivated the use of multiple predictions well.


Quality: The quality of results and writing is good. I did not check the math for the proofs in Section 5 but the algorithm seems intuitive. The paper is quite theoretical so having experiments/simulations is not warranted but would have been nice to see the proposed algorithm in Section 5 in action (even against synthetic datasets)

Significance: There is a plethora of work currently in Learning augmented algorithms. I find this work to be incremental in the field of using multiple predictions for Online Algorithms. The significance of the work is relevant since algorithms with predictions as a general field has gained so much traction in the community.

questions: Related Work: The related work is quite comprehensive. One of the related works that I found that the authors could contrast their work vis-a-vis learnability is :

Anand, Keerti, et al. "A regression approach to learning-augmented online algorithms." Advances in Neural Information Processing Systems 34 (2021): 30504-30517.

This is because in this work Anand et al did not consider the computational complexity of the optimization procedure that obtains the sample error minimizer. In comparison, the authors in this paper give a technique that is a polynomial time approximation algorithm for obtaining the predictions from the sample set that are O(1) within the best predictions obtainable from ERM. 

Line 290: In this proof of Thm 3.4, won’t the algorithm need to look at all |S| choose k candidate solutions (and that would be exponential in $k$). The claim is that “we can find an O(1)-approximate solution which is of polynomial size in polynomial time”. What exactly in the time complexity and what is the procedure? Please clarify.

limitations: None.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers using multiple machine-learned predictions to improve classic algorithm design. In particular, the work is focused on three problem: min-cost bipartite matching, online makespan minimization, and non-clairvoyant scheduling. For the first problem, the goal is to improve run-time, whereas for the last two the goal is to improve competitive ratio. 

In each setting, the paper gives an efficient algorithms that makes use of multiple predictions. When (at least one of) the predictions are good, the resulting learning-augmented algorithm can achieve better performance than classic, worst-case counterparts. Moreover, the paper works out the learnability conditions, showing that good predictions can be efficiently PAC learned from data.
strengths_and_weaknesses: Strengths
-----
The paper is generally well-written, though with a few minor typos that may be confusing at times. I have listed them in a later section.

The results are novel in light of the recent literature on learning-based algorithms. In particular, this can be seen as a good follow-up on the question of algorithms with multiple predictions, recently initiated by Anand, Ge, Kumar, and Panigrahi ["Online algorithms with multiple
predictions" (ICML 22)]. As the author(s) point out,  Anand et al focus only on a set of online covering problems. The results of this paper do not lie within this framework. I believe this paper is a good addition to this line of work. 

The theoretic claims are correct. 

Weaknesses
----
In my view, some of the results in this work are a bit weak on a technical level. In particular, Section 3 on matching extends Dinitz et al in a fairly trivial fashion. The main algorithm (Algorithm 1) essentially says: take the largest dual prediction and run Dinitz et al single-predictor algorithm. This should be thought as a simple observation.  On the other hand, the algorithmic result of Section 4 on scheduling relies on several key insights of Lattanzi et al ("Online Scheduling via Learned Weights", SODA 20).  The learnability generally follows from a pseudodimension + PAC learning argument, again from Dinitz et al. 

Compared with Anand et al, this paper does not provide a general framework. Rather, it addresses 3 separate problems of different nature. That is, matching is offline and the goal is to improve run-time, but the scheduling problems are online and the goal is to deal with the uncertainty.  
 
Compared with Dinitz et al, the paper does not provide experiments.

Compared with Lattanzi et al, the paper does not address rounding fractional solutions. 

Minor errors and missing references
-----
Line 11: “which prediction is [the] best”

Line 104: another paper that studies non-clairvoyant scheduling in single-predictor setting is “Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms” by Wei & Zhang (NeurIPS 20)

Line 249 reads a bit awkward, which is not making a definition. Maybe remove the “we say that”.

LHS of Line 10 of Algorithm 2 should be $S(j, \beta)$? I suggest the author(s) avoid overloading the notation of $A$ here.

LHS of Line 10 of Algorithm 2 should be $B$ instead of $A$.

Line 314: Optimal schedule, and Line 318: optimal objective value

Line 423 of the supplement: I suggest the author(s) to give a standard reference for constant-approximation of k-median; e.g., “A Constant-Factor Approximation Algorithm for the k-Median Problem” (https://www.sciencedirect.com/science/article/pii/S0022000002918829)

questions: For matching, I am wondering if experimentally one can find multiple predictions can help (for real world or synthetic data). Let's say $k=5$ or $10$.  In principle it may not; that is, the best single prediction (in expectation over the distribution) is generally very good for every single instance in the distribution. My intuition is that if the distribution is somewhat "concentrated" such that the instances generally look alike, then multiple predictions may not help. On the other hand, if the distribution has a "multiple clusters" structure, then having multiple predictions can provide much better coverage and therefore improve performance a lot. Is it possible to formalize this intuitions and give some theory, for matching or graph problems in general?

The recent work by Chen, Silwal, Vakilian, and Zhang [Faster fundamental graph algorithms via learned predictions, ICML 22] shows that using (single) prediction can help to improve the run-time of graph algorithms, beyond the matching problem of Dinitz et al. I think the multiple prediction can be interesting more broadly in speeding up offline graph algorithms. This is another future direction the author(s) can explore. 

For online makespan minimization, can the fractional solution be rounded in an online fashion? A majority of the paper by Lattanzi et al is spent on rounding (their Section 4 and 5).  I think their techniques can be applied here. 
limitations: As I mentioned, the paper does not give a general framework of addressing multiple predictions in learning-based algorithms. In fact, reading its title, I expect they would. 

Some experiments on matching could be very interesting.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Over the last 10 years, a significant line of work has focused on how to augment optimization algorithms with predictions so that (a) improved performance is achieved when the predictions are accurate and (b) worst-case performance is recovered when the predictions are not accurate. In this work, the authors build on the more recent idea to augment optimization algorithms with $k$ predictions. For three canonical tasks, the authors quantify the computational cost (which they show is mostly quite small) to obtain equivalent performance to augmenting the optimization algorithm with the (unknown) best of the $k$ predictors.
strengths_and_weaknesses: The paper is clearly written (although the supplementary material is hard to follow at first, due to interleaving theorem statements, proofs, and intuition like a textbook), and the problem well-motivated. The results are novel and the proofs all seem correct, although the technical contributions of the learning theory arguments are minimal. (For example, I believe Theorem 2.1 can be extracted from (the proofs of) more general results on compositions of VC classes. See Theorem 6.1 of https://arxiv.org/pdf/1105.4618.pdf, attributed to a 1997 textbook.) 

The main limitation of the work is the incremental nature of the contribution and the utility of the results for demonstrating actual improved performance. For all three problems considered, the authors thoroughly cite how past work has considered the single predictor impact. The main contribution is improving (using the notation of Section 3, but the contribution is the same for all three problems)
$$
   \min_{\hat y} E_{(G,c)\sim\mathcal{D}} \ \lvert\lvert y^*(G,c) - \hat y \rvert\rvert_1
$$
to
$$
   \min_{\hat y^1,\dots,\hat y^k} E_{(G,c)\sim\mathcal{D}} \min_{\ell\in[k]} \  \lvert \lvert y^*(G,c) - \hat y^\ell \rvert\rvert_1.
$$
Obviously the second term is no larger than the first term. However, since there is a (sometimes small, but not zero) addition to computational complexity in order to achieve the second term, I think the main quantity of interest is *how much* smaller the second term gets. This should depend on the problem parameters, $k$, and some properties of $\mathcal{D}$ (e.g., how symmetric it is?). This will provide an answer to the question: is the improvement in performance worth the computational cost of considering $k$ predictors over a single predictor?

I do not mean to penalize the authors for their useful characterization of the existing literature, and hence I rate the paper as borderline. If the authors can quantify exactly how much better using $k$ predictors can be in terms of the relevant parameters for the three problems of interest, this would be sufficient to improve my rating to an accept. 

questions: I've detailed this in the body of my review.
limitations: I see no negative societal impacts of this theoretical work.
review_title: null

Meta-review: metareview: The paper was generally well-received by the reviewers, who highlighted the significance of the setup, the strength of the results, and the enjoyable writing in their initial reviews. The additional experimental results provided during the rebuttal phase were particularly appreciated. Eventually we have reached consensus that the paper is clearly worthy of being published at NeurIPS 2022. I encourage the authors to work the additional experiments into the final version of the paper, and take all the remaining comments of the reviewers into account.
confidence: Certain
Decision: Accept