Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper revisits the online knapsack problem using machine-learned predictions in order to improve on prior the competitive ratio of classical algorithms. The authors take a different approach compared to other works in the area of learning-augmented online algorithms. Specifically, instead of having the prediction be a specific value predicting the true value of some parameter, they use intervals to indicate a range of values in which each parameter is predicted to be in. In this case, the parameters predicted are the frequencies of elements of some specific value that will arrive in the future. In the analysis, the authors compute the competitive ratio of their algorithm given that all the predictions are accurate in the sense that the true parameters indeed fall into their corresponding intervals.  The authors show that the competitive ratio of their proposed algorithm is instance optimal with regard to the predictions given and that the competitive ratio improves as the predicted intervals become shorter and match the performance of the algorithm by Zhou et’al when the intervals equal the entire domain.  The predictions are used by the algorithm to prevent too many low-valued elements being selected, while higher valued elements are predicted to arrive later. The choice of this approach is supported by a hardness result simpler threshold based algorithms cannot achieve an arbitrarily good competitive ratio. Also, an application to one-way trading is shown via a reduction to the online knapsack problem and two-stage knapsack variant, in which the algorithm can select elements in a second round (with some penalty on their value), is discussed. Finally, experimental results show the improved performance of the proposed algorithm compared to the algorithm by  Zhou et’al that does not use predictions


main_review: I believe that this paper suggests a very interesting approach for the analysis of learning augmented algorithms by introducing the predictions as an interval. This could fit very well in practice with the idea of machine learning algorithms providing confidence intervals for their predictions. One might need to be careful though, since the error from different confidence intervals could accumulate. It is conceivable that this approach could lead in new results for different problems in the area. Finally, the paper is quite well written and easy to follow.  
limitations_and_societal_impact: The authors as well as myself do not see any potential negative societal impact from this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers a variant of the classical online knapsack problem where each possible value, the size of an item is contained in a known interval (called frequency prediction). The paper proposes an algorithm and shows that its competitive ratio is optimal. Furthermore, the authors show some applications of the problem and the algorithm.


main_review: Comments:
The writing is generally good. However, Summarized descriptions of the proposed algorithms are helpful (such as the algorithmic environment of latex). Also, the protocol of the problem is not clearly written, in that the information of size or profit of item is given to the player before or after the player makes a decision to accept/reject the item. This information is important but is missing. So, I do not fully understand why “predictions” of intervals of sizes are helpful. 

The technical results are non-trivial and strong, in that the proposed algorithm is optimal in some sense. But, the analyses of the paper seem to follow standard approaches of the online algorithm literature (e.g., continuous relaxation) and I am not sure how significant the techniques are. 

Maybe one of my concerns is if the scope of the conference matches the topic of the paper. At a glance, the paper is more suitable for algorithm-related conferences. The problem setting might be interesting from an algorithmic perspective, but I am not aware of any realistic motivations for the formulation. This could be a weakness of the paper unless the authors address motivating applications.

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper studies the online Knapsack problem in the new framework of Learning Augmented algorithms. In this setting the goal is to use predictions to improve the performance of online algorithms. Generally, two properties are wanted: (1) robustness which is a worst case bound of the competitive ratio of the algorithm (even if the predictions are totally incorrect) (2) consistency which is the guarantee that if the prediction are correct then the algorithm should be better than what any online algorithm can do. As noted by the authors in introduction, robustness here is trivial hence the focus of the paper is to obtain the consistency property. Interestingly, they can use rather weak predictions and still manage to obtain an improved bound over what online algorithms can do (more details below). 


The formal definition of the problem is the following. We have a knapsack of unit capacity and n items are revealed in an online fashion. Each item $i$ has a profit $p_i$ and a size $s_i$ (the value of an item is defined as $v_i=p_i/s_i$). The goal is to maximize the profit without exceeding the capacity of the knapsack.  Once an item arrives, the algorithm has to decide whether to take it or leave it.


In the online setting without prediction, an algorithm with competitive ratio of $1/(1+ln(v_{max}/v_{min}))$ is known (if items have infinitely small size) where $v_{max}$ is the max value and $v_{min}$ the min value. It is also known that it is not possible to do better. This result is due to Zhou, Chakrabarty, and Lukose [ZCL08].


The prediction model is the following. Before receiving the instance, the algorithm is given a lower bound $l(v)$ on the total size of items of value $v$ for all $v$. Similarly, an upper bound $u(v)$ on the total size of items of value $v$ is given. These are called frequency predictions. The main result of the author is to obtain an algorithm that is optimal on instances for which the true total volume $s(v)$ of items of size $v$ is in-between the lower bound and the upper bound (i.e. $l(v)\leq s(v)\leq u(v)$ for all $v$), that is, if the frequency predictions are correct. Precisely they design an algorithm that is $\alpha$-competitive where $\alpha$ is the best competitive ratio on all instances for which the frequency predictions $l,u$ are correct.
There is no closed form of the value of $\alpha$ which depends in general on the predictions $l$ and $u$ in some non-trivial way. However they demonstrate that for reasonable predictions, the value of $\alpha$ is much better that what the ZCL algorithm can guarantee.  


The authors also generalize their results to more general problems such as generalized one-way trading and two-stage online knapsack. Finally, they also demonstrate that their algorithm for online Knapsack outperforms ZCL in practice.

main_review: Originality/Quality: I believe the results are non-trivial and very interesting. In particular, an interesting challenge in this problem (that the authors mention) is that simply applying the technique of ZCL with a “threshold algorithm” cannot work in the learning augmented setting. This means that from a technical point of view, new ideas were needed for this problem. 

Clarity: I find the paper clearly written and I believe in the correctness of the results of the paper although I did not check the appendix entirely.

Significance: This paper gives interesting results on a clean and natural problem.

I don’t see any major weakness in this work however I have a few questions/comments for the authors:

(1) In other learning augmented algorithms, there is also a concept of “smoothness” that says that if the prediction is slightly incorrect then the performance of the algorithm does not degrade a lot. Here I understand the prediction is rather weak so you already have some kind of smoothness but what happens if you realize that some frequency prediction is in fact slightly incorrect? Can you still maintain a better guarantee that online algorithms without predictions?

(2) I believe that if the lower bound is equal to the upper bound (i.e. $l(v)=u(v)$ for all $v$) then $\alpha^*=1$. Is this true? If yes, then I would suggest to include a brief explanation of this as I don’t think it is immediately clear from the description of the algorithm.

Typos:

Line 110 : outperform -> outperforms

Line 170 : smallest -> largest ?

Line 176 : a profit of at $\alpha$… -> a profit of at least $\alpha$…


==== UPDATE ==== after reading the author response and discussing with other reviewers, my initial opinion remains: the result and techniques are interesting. I think this is a nice paper. 

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the well-known online linear knapsack problem (and two of its generalizations) in the learning-augmented setting where the goal is to incorporate some ML predictions of the future online input such that the algorithm is consistent when the predictions are good and also robust in case of malicious predictions. The authors show that the threshold-based algorithms (such as the optimal worst-case algorithm for this problem) could not achieve the best competitive ratio in the learning-augmented setting and they provide a novel algorithm to attain this goal. Finally, some experiments on synthetic data sets are provided to verify the superior performance of the proposed algorithm compared to the worst-case algorithm in the setting with predictions.
main_review: Main strengths of the paper:
- The online knapsack problem is extremely well-motivated and therefore, obtaining learning-augmented algorithms for this problem is of potential interest to a wide audience.
- Unlike many previous works in the learning-augmented setting, the techniques used to design the algorithm are quite different from those used in the optimal worst-case algorithm for the problem and so, the theoretical contributions of the work are significant.
- The experiments are well designed to verify and highlight the theoretical results of the paper and show the superiority of the performance of the proposed algorithm.

Main drawbacks of the paper:
- It is really hard to follow all the notations used in the paper and understand the arguments of the proofs. For instance, I am not sure what $B_{\alpha}(\cdot)$ is in Step 4 (Section 3) of the paper. I did not find the definition elsewhere. It would be great if all the notations are summarized in one place for future reference (currently, it is scattered throughout pages 4 and 5)
- The authors need to precisely discuss the size of the additive loss in the competitive ratio (due to discretization) in intermediate cases where $\max_i s_i$ does not approach zero. For example, if we consider the discretization mentioned in the paragraph before Section 1.1 (with $k$ discrete values), what is the exact dependence of $\max_i s_i$ on $k$ and how fast the whole additive loss approaches 0 as $k$ grows larger.
- The proposed algorithm addresses the case where predictions are all correct and the authors mention that a linear combination of this algorithm with the optimal worst-case algorithm leads to a consistent and robust learning-augmented algorithm. However, this linear combination might not be the best way to incorporate both robustness and consistency, and designing a single algorithm that incorporates both the worst-case and predictions usually leads to better results. For instance, if similar to [7], there is a parameter $\lambda \in [0,1]$ denoting our confidence in the predictions, how would the robustness and consistency bounds depend on $\lambda$?
********************************
Post-Rebuttal Update: Thanks to the authors for their detailed responses to the raised questions. While I highly value the theoretical contributions of this work, I still believe that a detailed discussion about the dependence of the additive loss in the competitive ratio (due to discretization) on $k$ and its order of magnitude for finite $k$ is necessary to complement the result of Theorem 1. The authors have described their result in their response, but my main concern was about the dependence of the term $\max_i s_i$ on $k$ (i.e., the magnitude of the additive loss for finite $k$). Also, a precise description of the results in the case of incorrect predictions is required as well. I will keep my initial score for the paper. 

----Final Update-----

After discussing the raised questions with the authors, my concerns were resolved. I will increase my score to 6 for this paper.
limitations_and_societal_impact: This is a theoretical work without any potential ethical concerns. The authors have perfectly described the scope of their proposed algorithm and its limitations.
review_title: null

Meta-review: The reviewers all find the results in this paper to be technically strong and interesting. This paper makes a nice contribution to the area of algorithms with ML predictions. Please address reviewer YbwL's comments regarding the additive loss and the description of the results in the case of incorrect predictions in the final version.
Decision: Accept (Poster)