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: This paper studies online covering linear and semidefinite programs, and proposed algorithms that incorporate models with prediction. The main technical results show that the proposal primal and dual learning-augmented algorithm can achieve both consistency (when the prediction is accurate) and robustness (when the prediction is inaccurate). The techniques work for both online linear programs and semidefinite programs. Some empirical evaluations are presented to demonstrate the performance of the proposed algorithmic framework. 
strengths_and_weaknesses: Strengths:
+ The problem is well-motivated, and the contributions seem novel compared to the previous results.
+ The technical proofs in the extended version appear to be solid (but the reviewer didn't check the details).
+ The comparison between online linear programs and online semidefinite programs is well-organized. 

Weaknesses:
- The main results have not been rigorously stated in the main text. Indeed, the informal results in Theorem 1.3 and Theorem 1.4 are not rigorous. The authors put the full algorithms, formal statements of theorems, and all the proofs into the extended version. The main text appears less complete and is more like an extended abstract. 
- The overview of techniques in Section 1.2 is not easy to follow. The overview still appears to be very technical and has many jargons.
- The proof sketch for Theorem 1.3 and Theorem 1.4 on Page 7 and Page 8 does not present sufficient proof ideas, which is not easy to follow.

questions: It is not good to say semidefinite programming is a unifying framework that generalizes quadratically-constrained quadratic programs (QCQPs). The authors may mean that convex QCQPs can be reformulated into a special SDP. However, a general QCQP can be highly non-convex and contain NP-hard instances as special cases. 
limitations: It is fine to put some technical proofs to the extended version. But it is better to make the main text be more independent, not like an extended abstract.
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: An online optimization algorithm is a method where the data of the problem can be presented in a piecemeal fashion, and the optimizer must make certain irrevocable decisions at each step. This is a strong limitation, and usually results in a loss in performance described by the "competitive ratio" (ratio of online optimum to offline optimum). 

The present paper belongs to a growing line of research where one studies online algorithms that receive "advice" on the solution. This advice may come from a predictive algorithm that guesses the next problem instances. The desiderata for a good method in this setting are the following: (1) if the advice is good, then the performance of the method should nearly match the optimal offline solution; and (2) if the advice is not good, the usual, assumption-free competitive ratio is (nearly) achieved.  

In comparison with previous work, such as the one by Bamas et al. in NeurIPS 2020, the main novelties here are twofold. First, the present method can deal with certain "covering LPs" with non-integral constraints. Second, covering SDPs are also considered, which extends the scope of the "primal-dual method". In all cases, one obtains desiderata (1) and (2) above. A small experimental section is also presented. 

Let me add a few words about the main ideas. As mentioned, Bamas et al. consider integral constraints. The present paper allows for fractional constraints; so decision variables must be increased continuously from round to round. The analysis of the method is not terribly difficult, but is a bit subtle and (at least to me) surprising.  
strengths_and_weaknesses: *Strengths*

The paper is easy to read, clear, and seemingly original. The main issues at stake stated and the contribution is quite nice. Some previous results are subsumed by the present manuscript. While I am not an expert on this topic, I am fairly convinced that the extension of the primal-dual method to this setting is non-trivial.

*Weaknesses* 

In practical applications, better control of the constants in the approximation ratios is needed. 


questions: Can you comment a bit more on the motivation for the setting? E.g. where and when would it be a good idea to use these methods. 
limitations: Yes, they have.
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 online linear and semidefinite programming problem and makes use of the predicted optimal solutions to give algorithms. The authors extend the primal-dual learning-augmented framework of online set cover (NeurIPS 2020) to online LP and SDP covering. For online LP covering, they show a $O(1/(1-\lambda))$-consistent and $O(\log \frac{kn}{\lambda}$-robust algorithm, where $\lambda$ is a given parameter, $n$ is the number of variables, and $k$ is the upper bound for the ratio between the maximum positive entry and the minimum positive entry in each column of the constraint matrix. For online SDP covering, the same consistency and robustness are also obtained. If the variables in the (linear or semidefinite) program lie in a bounded region, the robustness can be improved slightly to $O(\log(s/\lambda)$, where $s$ is the sparsity.
strengths_and_weaknesses: Strength:
- Online LP and SDP covering are very important frameworks in the field of online algorithmic design. They capture a large number of problems, such as ski rental, online set cover, and so on. The authors show a general framework to leverage the predicted (fractional) optimal solutions to design non-trivial algorithms. The work is solid and the proposed idea could be widely applied to many online covering problems.

Weakness:
- The robustness ratio matches the pure online worst-case bound only when the condition number $k$ is $poly(n)$, but in the general case, $k$ might be a very large value. The work can be strengthened if the paper has a discussion about the optimality of the consistency-robustness tradeoff. Ideally, prove that the dependence on $k$ is unavoidable when the consistency is $O(1/(1-\lambda))$. Furthermore, the authors can consider the case that $k$ is known in advance and see if a better ratio can be obtained. 
questions: - The definition of ``consistency" in the paper is different from the standard one where the consistency refers to the competitive ratio when the prediction is accurate. In the context, the two definitions are the same because the optimal solution is predicted in the paper, and thus, ADV=OPT when the the prediction is accurate. However, in many other problems, even with an accurate prediction, ADV could be larger than OPT. 

- The statements of algorithm 1 and algorithm 2 miss the update of the dual variables $y$. So when I first read the proof sketch, I got confused. The algorithms provided in the supplementary material are correct I guess. 
limitations: The authors adequately addressed the limitations and I didn't see any potential negative societal impact.
review_title: null

Meta-review: metareview: Thank you for your submission to NeurIPS. The reviewers unanimously found the work to address an important, relevant problem, and the paper to be clear and well-written. All three reviewers unanimously recommend accepting the paper.

Please incorporate reviewer feedback in preparing the camera ready version. In particular, please take care to incorporate the clarifications outlined in your response to Reviewer b8M5.
confidence: Certain
Decision: Accept