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: The problem focus on an online convex optimization problem in which the learner wants to minimize the regret and at the same time does not want to violate some (known or unknown) constraints too often. In particular, the work focus on hard constraints, i.e., such that a violation at one round cannot be compensated by a strictly feasible decision at a different round. They consider a setting with fixed known constraints, providing a regret bound of $O(\sqrt{T})$ and a violation of $O(1)$. For the setting in which the constraints are adversarial, they provide a regret bound of $O(\sqrt{T})$ and a constraint violation of $O({T}^{3/4})$. Moreover, they consider the case with strictly convex functions, proving better bounds.
strengths_and_weaknesses: The paper studies a well known important problem.
The paper is well written and provides a detailed comparison with previous works.
The paper provides new techniques that are useful to obtain better regret and violation bounds to the problem.

I have a huge concern about the significance of the result, at least for the setting with fixed constraints.
In particular, the problem can be trivially solved considering the convex decision space in which the constraint is satisfied and using a standard regret minimizer on this set. However, this approach usually requires to project on the feasible action space.
The main reason to consider a setting with relaxed constraints (soft or hard) is that in this setting is it possible to design very efficient algorithms that do not require projection on complex set (see for instance the abstract of [15]).

However, your algorithm does not seem efficient. The step Rectified decision in the Algorithm RECOO requires to compute a minimization over a function that includes a generic convex function $\hat g^+_{t-1}(\cdot)$.
Moreover, it seems that your approach is very related to standard online convex optimization problems in which the constraint g cannot be violated. In particular, if I look at your result, the constant $\epsilon$ appears only in the denominator of the regret and violation bounds. So the optimal choice for $\epsilon$ should be $\infty$. In this case $\gamma_t$ is very large and $\hat g^+_t(x)\rightarrow \infty$ when $g^+(x)$ is positive. This is a well known equivalent way to represent classical online convex optimization problems.

Post-rebuttal update: I'm partially convinced by the answers given by the authors. I agree that the algorithm proposed by the authors has a lower complexity w.r.t. standard projection based algorithms. I think that this is one of the main motivation of the work and should be highlighted. I'm still convinced that if we ignore the computational complexity motivation the problem can be solved using standard online convex optimization methods. Indeed, your method reduces to classical online convex optimization when $\epsilon$ goes to $\infty$. I think you should highlight the role of $\epsilon$ and trade of between performances and regret. Finally, I agree with the authors that the analysis is non-trivial for adversarial constraints.
questions: Let me know if I miss something about the relation with classical online convex optimization problems.
limitations: Yes
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: This work studies the online convex optimization problem with 'hard' constraints. Here hard constraints mean that the violation from different rounds can not compensate for each other. The authors propose a RECOO algorithm and apply it to both the fixed constraint setting and the adversarial constraint setting. RECOO outperforms previous algorithms by achieving either a better regret or a smaller violation. At the core of RECOO is a 'rectifying' scheme applied to constraint functions. This work also considers a dynamic regret setting and provides corresponding results of their algorithms. Experiment results back up their theoretical findings. 
strengths_and_weaknesses: Strengths:
+ The presentation is clear. 
+ The theoretical results are new and important. 
+ The experiments provide a comprehensive view of their algorithms. 

Weaknesses:
+ More baseline algorithms may be mentioned in the summary section. For instance, for the fixed constraints setting, a normal online SGD method with a projection w.r.t. the constraint $g$ is also a baseline method. 
questions: + I do not have any specific questions.
limitations: No, the authors suggest 'We didn’t find any major limita375 tions in applying our results to constrained online convex programming.'
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: Online convex optimization (OCO) is a significant part of online learning literature. In real-world applications, there are constraints that need to be satisfied through optimization. This paper theoretically analyzes the constraint OCO under fixed and adversarial settings when the loss is either convex or strongly convex. Unlike the previous works, it considers the hard constraint violation which means that the average constraint violation (CV) is the average of the positive constraint violation and ignores the negative one which can lead to a minima which after a large iteration gives an infeasible solution. It also considers two kinds of regret: 1- static regret and 2- dynamic regret. Under hard constraint assumption,  for all of these different settings, it either recovers the existing results for CV or improves it. 

strengths_and_weaknesses: Clarity

The paper is written clearly with enough explanation for different settings. It explains well the significance of the hard constraint setting. The proofs are presented in an understandable manner. 

Since the paper mainly is theoretical, it is not cleared enough why it gets better CV bound w.r.t. existing results. For example, explain which technical method resulted in that bound. 

Originality

Considering the hard constraint in OCO is novel and also important for real-world problems. 

Quality

The submission is technically sound. I’ve checked the proofs and they look correct and sound. However, the technique they’ve leveraged are not new and have been used in previous works. 

Significance

The result is important for the real-world problem and besides, they improve the CV bound in a few settings compared to the existing results.  


Limitation

The experimental results are just for toy examples. It would illustrate the significance of the proposed method if you have some results on a real-world dataset.   





questions: 1- In the experimental result, we see that the CV bound for the existing methods (Fig 1) also shows the constant bound and not sublinearly as claimed in Table 1 or 2. What do you think is the reason for this observation? 

limitations: This works addresses the potential social impacts.
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: This paper studies an extension of the well-known Online Convex Optimization (OCO) problem where at each round $t\in[T]$, upon committing to an action $x_t$, both a loss function $f_t$ and also a constraint function $g_t$ are revealed. The goal is to minimize the overall incurred loss $\sum_{t=1}^T f_t(x_t)$ while minimizing the hard constraint violation $\sum_{t=1}^T \max (g_t(x_t),0)$. The authors propose a single algorithm called RECOO that obtains state-of-art bounds for static/dynamic regrets and constraint violation for convex/strongly convex losses. The numerical experiments verify the theoretical findings as well.
strengths_and_weaknesses: Strengths:
- Paper is well-written and the authors have done an excellent job motivating the problem and giving intuitions for their algorithm.
- The literature review is comprehensive and clearly compares and contrasts related works to this paper.
- Imposing a time-varying minimum penalty price in the update for $Q(t)$ seems novel and changes the proof techniques for bounding the constraint violation.

Weaknesses:
- While the experiments clearly highlight the theoretical contributions of the paper, they have been done only for synthetic datasets. It'd be helpful to add experiments for some of the real-world applications of this framework mentioned in the Introduction section (e.g., safety-critical applications).
- The claim that the algorithm manages to achieve the "best of two worlds" is a bit misleading. "Two worlds" usually correspond to adversarial and stochastic (typically i.i.d.) constraints, however, in this paper, it refers to adversarial and fixed constraints.
- In the paper, it needs to be clarified what Slater's condition is, how so many of the prior works have assumed this condition holds to obtain better bounds, and how the framework in this paper does not make such an assumption.
- The notion of path length $P_T$ has been used several times in the paper before it is finally defined on page 6.
- The natural static benchmark for this problem should only satisfy the constraint $\sum_{t=1}^T \max (g_t(x),0)$, however, in the paper, the benchmark is further restricted to satisfy $g_t(x)\leq 0~\forall t\in[T]$. The authors should explain and motivate this choice of benchmark, and mention any potential hardness results for regret against the more natural static benchmark.
- The algorithm is quite similar to that of [18] and [30] (putting aside the new idea of rectifying $Q(t)$). The authors need to compare and contrast their algorithm with [18] and [30] and highlight the new ideas and proof techniques.
questions: I have already mentioned many of my suggestions and questions earlier. In addition:
- Does the expert-tracking technique of [33] for obtaining optimal $O(\sqrt{P_T T})$ regret bounds apply to the setting with adversarial constraints as well? (in the paper, you have only applied to the setting with fixed constraints)
- The proofs provided in the text are not very insightful. They could be deferred to the appendix and the space could be used for additional experiments with real-world datasets.
-  In the statement of Theorem 1 and Theorem 3, state that the loss functions are assumed to be convex. It is currently missing.
limitations: The scope of their proposed algorithm has been clearly specified. This theoretical work does not have any potential negative societal impacts and there is no need for addressing it.
review_title: null

Meta-review: metareview: This paper provides an algorithm for online convex optimization with varying unknown constraints. Reviewers agree that the methods involved appear novel and interesting. However, the authors are strongly encouraged to add a discussion of the computational complexity of the method, which may provide the missing tradeoff for the currently free $\epsilon$ parameter.
confidence: Less certain
Decision: Accept