Online Convex Optimization with Hard Constraints: Towards the Best of Two Worlds and Beyond
Authors: Hengquan Guo
Xin Liu
Honghao Wei
Lei Ying
Venue: NeurIPS 2022 Accept (2022)
Keywords: online convex optimization
hard constraints
cumulative absolute violation
best of two worlds and beyond

Abstract: This paper considers online convex optimization with hard constraints and analyzes achievable regret and cumulative hard constraint violation (violation for short). The problem distinguishes itself from online convex optimization with soft constraints, where a violation at one round can be compensated/cancelled by a conservative decision at a different round. We propose a RECtified Online Optimization algorithm (RECOO) and consider two settings: fixed constraints and adversarial constraints. Both settings have been considered in the literature. Compared with existing results, {\em RECOO achieves the best of two worlds and beyond.}  For the fixed-constraints setting, RECOO achieves $O\left(\sqrt{T}\right)$ regret and $O(1)$  violation, where $T$ is the learning horizon. The best known results in this case are $O(\sqrt{T})$ regret and $O\left(T^{1/4}\right)$ violation. For the adversarial-constraints setting, it guarantees $O(\sqrt{T})$ regret and $O(T^{3/4})$ violation, which match the best existing results.  When the loss functions are strongly convex,  RECOO can guarantee $O(\log T)$ regret and $O(1)$ violation for fixed constraints, and $O(\log T)$ regret and $O(\sqrt{T\log T})$ violation for adversarial constraints. Both these results are order-wise better than the existing bounds. The regret and violation bounds mentioned above use the best fixed decision in hindsight as the baseline. This paper further considers a dynamic baseline where the comparator sequence is time-varying. This paper shows that RECOO not only improves the existing results in the fixed-constraints setting  but also {\em for the first time,} guarantees dynamic regret and violation bounds in the adversarial-constraints setting. Our experiment results confirm that RECOO outperforms several existing algorithms for both fixed and adversarial constraints.  

Online Convex Optimization with Hard Constraints: Towards the Best of Two Worlds and Beyond
Hengquan Guo ShanghaiTech University guohg@shanghaitech edu.
Xin Liu ShanghaiTTech University Luuzin7@@hanghaitecch edu on
Honghao Wei University of Michigan, Ann Arbor honghaow@umich.co edu
Lei Ying
University of Michigan, Ann Arbor leiying@umichh Saniggumich..omm edu
Abstract
This paper considers online convex optimization with hard constraints and analyzes achievable regret and cumulative hard constraint violation (violation for short). The problem distinguishes itself from online convex optimization with soft constraints, where violation at one round can be compensated//caneelee by a conservative decision at a different round. We propose a RECtified Online Optimization al- gorithm (RECOO) and consider two settings: fixed constraints and adversarial constraints. Both settings have been considered in the literature. Compared with existing results, RECOO achieves the best of two worlds and beyond. For the exeedconstraints setting, RECOO achieves (VT) regret and O(1) violation, where T is the learning horizon. The best known results in this case are O( regret and O (T1/1) violation. For the adversaaiil-comstraantts setting, guarantees O(VT) regret and O(T3/44 violation, which match the best existing results. When the loss function strongly convex, RECOO can guarantee Ollog T) regret and O(1) violation for fixed constraints, and Ollog T') regret and OlvTlogT) viola- tion for adversarial constraints. Both these results are order-wise better than the existing bounds. The regret and violation bounds mentioned above the best fixed decision in hindsight as the baseline. This paper further considers a dynamic baseline where the comparator sequence is time-varying. This paper shows that RECOO not only improves the existing bounds for the fixed-constraints setting but also for the first time, establishes dynamic regret and violation bounds for the ddversarial-consrraae setting. Our experiment results confirm that RECOO outperforms several existing algorithms for both fixed and adversarial constraints.
Introduction
Online convex optimization (OCO) is general framework for modelling and studying online decision- making in uncertain environments [24, 10, 21J, where the learner adapts its decisions to minimize loss function to maximize utility function when interacting with the environment in real-time. OCO has broad range of applications such as online advertising [18, 3], resource allocation in network systems [9, 2, 33), load balaneing in queueing systems [13, 15], and personalized healthcare [36, 26), etc. Specifically, given an unknown convex loss function fe(-), the learner makes decision Iz each round to minimize the total loss over T rounds, i.e. minzex Σ fe(2x), where the loss
& CCorresponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

of decision is revealed after is executed. In practice, the decisions are often subject to a variety of operational constraints. For example, in online advertisement systems, users, who submit bids to advertise their items in order to maximize their click-through-rates, often have weekly or monthly budget; and in a patient onboarding system, the hospital assigns an incoming patient to medical unit to optimize the quality of treatment subject to personnel and medical resource constraints. To consider these applications, we study constrained online convex optimization (COCO) with ge(-) being convex constraint function and ge(zz) & 0 being the constraint at round t. In COCO, the learner aims at minimizing the total loss while keeping the constraint violation to its minimum.
One possible method to satisfy the constraints is to project the decision into the feasible set each round [10]. However, such projection may not be possible when the constraints (e(-) are adversarial and unknown before hand. Even if gx is known before hand, projection based methods (e.g., projected online gradient descent) may require heavy computation when ge (.) is a complicated function because it is equivalent to solving a constrained quadratic optimization problem [12. 17, 34). This has motivated projection-fres online learning methods such as the online Frank- Wolfe algorithm [12] where the projection operator at each round is by linear programming with the exact same constraint functions. Recently, a sequence of studies have considered COCO with soft constraints, where the constraints are allowed to be violated at some rounds as long as they are satisfied in the long term [17, 14, 20, 32, 25, 5, 4, 34, 27] (in other words, the severity of constraint violation is evaluated based on Σ, gu (x.)). We call them soft constraints because the constraint violation at one round could be compensated in a different round. In other words, a decision sequence might have zero constraint violation based on the metric despite violating the constraint(s) at almost every round.
For example, consider a decision sequence such that (xx) = { { -1000, 1, 1, 1, 1,1] 1] with 1000 ones. For such a sequence, we have Σ It (3:) all rounds except the first round. While some constraints such as budget or fairness constraints are naturally soft constraints, stronger notions of constraint and constraint violation are needed for other applications, in particular, for safety-criticll applications. In this paper, we consider a stronger notion of constraint violation as in [35, 30, 31]
for all T, but the constraint is violated at
T V(T) = Σ te (zx),
where that the operator (.)+ = max(-,0) 0) is imposed at every round and all violations during the decision process are added up. We call this hard constraint and the metric cumulative hard constraint violation. If a decision sequence has small V(T), it implies the constraints are satisfied most of the time during the learning. For example, consider the same example, V(T) = 1000 instead of under this stronger notion of constraint violation. In this paper, we consider the following two settings:
Fixed constraints (xx)) g(x)). Vt, where the constraint function remains the same over time but is not necessarily known to the learner. Note the setting of known and fixed constraints in [14, 17, 30, 34] a special case of ours.
Adversarial constraints gr (z), where the constraint function (e(x) is unknown when making decision at round and can be arbitrarily and adversarially chosen, as in [25, 20, 31].
We will show that RECOO is unifying algorithm that achieves small regret and violation in both settings. Next, we summarize our main contributions and compare them with the most related works.
1.1 Main contributions
This paper develops a RECtified Online Optimization algorithm, called RECOO, for COCO-Hard (COCO with hard constraints). RECOO is a unifying algorithm for both fixed and adversarial constraints. By introducing rectifiers in both "decision-making" and "penalty update" components, RECOO maintains minimum penalty price for constraint violation and encourages conservative/pessmiisti decisions, which is the key to minimizing the cumulative hard constraint violation.
Algorithm:
Regret and violation bounds: We first consider the best fixed decision in hindsight as the baseline (also called the static baseline). The main theoretical results are summarized below.
For fixed constraints, RECOO achieves O(VT) regret and 0(1) violation for convex loss functions, and O(log I') regret and O(1) violations for strongly-convex loss functions.
2

---

For adversarial constraints. RECOO achieves O(vT) regret and O(T violation for con- vex loss functions, and (llog T) regret and OlyTlogg) violation for strongly convex loss functions.
We then consider a dynamic baseline where the comparator is time-varying with path length Pr and establish the following results.
For fixed constraints, RECOO achieves O(vPrT) regret and Ollog 7) violation, where Pr is the path length of the feasible comparator sequence defined by Pr - | Ve with 9s (v(,)) & 0, E [T] as [37, 30].
2
For adversarial constraints, RECOO achieves O (PrVT) regret and O(T3/1) violation.
The comparison with most related works are summarized Tables and 2, from which we can see that RECOO achieves and improves the state-of-the-art results for both settings ("N/A" means results to the best of our knowledge). Below are a few highlights we would like to mention:
For fixed constraints and the static baseline, RECOO only improves the results in [30] but also answers a conjecture in [30] that O(1) violation may be achievable under Slater's ' condition (the condition holds when there exist a positive > and x X' such that ge(x)) & c, [T]).
We proved that the conjecture is true even without Slater's condition.
For adversarial constraints, the static baseline, and strongly convex loss functions, RECOO reduces the O regret and O(T2-e/2) violation in [31] to O(logT) and O(y7log T),
respectively.
For fixed constraints and the dynamic baseline, RECOO improves the violation from ((vT) in [30] to Oloo 7),, while maintaining the same regret bound.
For adversarial constraints and the dynamic baseline, RECOO achieves O (PrVT) regret and O(T3/4) violation, which are the first regret and violation bounds in this setting.
Reference
Loss Function
Regret, Violation
Dynamic Regret, Violation
[35]
O(VT), O(T3/4)
N/A
[30]
Convex
O()T), O(TI/)
O(VPTT) O(VT)
RECOO
O(vT), O(1)
O(PP, T), Olog
[35]
Olog T), O(yTlog
N/A
[30]
Strongly Convex
O(log 7), O(ogg
O (TPT))) O(vT) O(VPTT), Olog
RECOO
O(log T'), O(1)
Table 1: Our results and related work for fixed constraints.
Reference
Loss Function
Regret, Violation O(vT). O
Dynamic Regret, Violation
[31]
N/A
RECOO [31]
Convex
O(vT). O(T3/4)
O(PrVT), O(T
O(T*2). OTT)-0/2)
N/A
Strongly Convex
RECOO
(log O(yTlogT) O(PrVT), Voloo
Table 2: Our results and related work for adversarial constraints.
The key idea behind these results is the rectified penalty imposed when making decisions. which enable us to develop simple yet effective self- beffdooudingg relation that quantifies the trade-off between the regret and the cumulative hard constraints. The analysis is tailored for the cumulative hard constraints and is different from the trift-plus-penally method used in [30, 31, 34], where the constraint violations have been established by bounding the dual variables (also called virtual queues).
Analysis:
1.2
Related work
COCO has been studied in the literature [17, 25, 20, 16, 6. 22, 35, 30, 31). We have already presented detailed comparison with the existing results on COCO-Hard. We next review some of recent results on COCO-Soft, COCO with soft constraints.

---

COCO-Soft with fixed constraints: [17] studies COCO-Soft and proposed an algorithm that achieves O(vT) regret and O(T3/4) violation. This result has been extended in [14] to charac- terize the regret-violation tradeoff, in particular, the proposed algorithm achieves O(T regret and O(T' violation, where e controls the trade-off. Assuming Slater's 's condition holds, the algorithm in [34] achieves O( ((VT) regret and ((1) violation and is designed based on powerful "drift-plus- penalty" method, which inspires some of the design in RECOO.
COCO-Soft with adversarial constraints: Adversarial constraints are more difficult to satisfy but have been considered in the literature [25. 20, 16, 22]. For COCO-Soft with adversarial constraints, the authors in [25] developed an online mirrored descent type algorithm that achieves O(vT regret and ((73/4 violation. Later, [6, 16] generalized the baseline in [25] and still achieve O( (V) regret and O(T8/4) violation. With Slater's 's condition, [20] presents an online gradient descent algorithm based on the dríft-plus-penali method [19]. which achieves (v regret and ((vT) violation.
[22] extended the result to an online optimization with sub-modular losses. Note the key to reducing the constraint violation in these works is a refined bound on virtual queues (or dual variables) using
the Lyapunov drift method under Slater's 's condition. It remains open that whether O(73/4) violation can be reduced with adversarial constraints (soft or hard) while keeping O(vT) regret without Slater's condition.
COCO-Hard
In this section, we formally define COCO-Hare HarO. Consider the following online convex optimization problem: At each round t E [2], the learner makes decision Ia and then observes the loss f(())) and constraint function ga(+) after the decision is executed. The goal of the learner is to generate decision sequence (21,222 2............................... (2..........
2r-1, 2T} to minimize the total loss Σ fz(zz) and the hard constraint violation Σ/= (zz).
To quantify the performance of online convex optimization algorithm for COCO-Hard, will first compare it with a static baseline, called the best fixed decision in hindsight, which is the solution to the following offline COCO.
Offiine COCO
The offline COCO formulated as follows
min X
f((r) subject to: ge(x) & O.VLttTT,
where X' is a "simple" convex set (e.g., positive quadrant or probability simplex), (ff(-)) are convex loss functions and (gr(-)} are convex constraint functions. The optimal solution x* to offline COCO is called the best single decision in hindsight, a widely used baseline for COCO [10, 17, 25, 32).
Based offline COCO, the regret and constraint violation of online algorithm defined below.
Regret and cumulative hard constraint violation (or violation for short)
T f((ae) Σ f((x*),
T
R(T) Σ
(3)
T
V(T) Σ (xx)
(4)
3 RECOO: A rectified online optimization algorithm
We present RECOO, an online optimization algorithm with the rectified decision and penalty update.
RECOO A Rectified Online Optimization Algorithm
Initialization: xn E X,, Q(0) = 0, fo(x) = go = O, Va E X' and learning rates o4, Tit Tt-
Fort I,.

---

Set: ) -))))_11(2))
Rectified decision: find the optimal solution of x, by solving:
Itt arg min < Ii-1) + Q(t 1)9(-((4) aa-1/ rt-1
xeX
Observe: value (z(e and constraint function ge(-)-
Rectified penalty update: update the estimates of penalty variables Q(t) as follows:
Q(1) = max (Q(L
(Q(1-1) 1) d (p))..))
In RECOO, the learning rates oy, 7Jt "It are chosen differently depending on whether the loss function is convex or strongly convex, but are oblivious to the type of constraints (fixed or adversarial). The choices of learning rates can be found in the theorem statements.
We explain the intuition behind RECOO and the importance of the "rectifiers". The Lagrange function of the offline optimization problem (2) is defined be
L(,,
Σ Le(de,
Σ fe(x) Ae))(
where { are the dual variables associated with the constraints in (2).
Since we have no prior knowledge of fc(-) when making decision zt. we estimate with the first-order approximation at 2t-1 based on the historical information as follows
f((z)) ft-1 (x=-1) (VIe-((t-1); 3i-1))
Moreover, replace the original constraint function gr(-) with (-- and the dual variables A with Q(t -t such that Q(t 1));-((x) is rectified approximator of ge We also added the the regularization (or smooth) term arl| xz 2 that helps the stability of the algorithm. Note this
design is related to penalty-base based proximal optimization where we aim to minimize an approximated fz()) w.r.t. proximal operator on the "old" rectified function )
In the penalty update of Q(t), we first rectify the original constraint function ge(-) with g (-) and add it to Q(t-1) such that penalty increases when violation occurs in each round. Further we rectify Q(t) with a round-dependent constant 7): to impose a "minimum" penalty price. The design of rectified penalty update induces conservative decisions in the decision-making step to minimize constraint violation. Note that different with the traditional primal-dual algorithm that does not rectify the constraint violation and impose minimum penalty price, and when the price (dual variable) zero, the algorithm can take very aggressive decisions that lead to large hard violation. This not problem when primal-dual -ual algorithm is used numerical method for solving a constrained optimization problem, but leads to overly aggressive decisions and large violation when applying it to COCO. For similar reason, RECOO rectifies the amount of violation (t(x)) in the decision-man -akiing step so the violation does not become negative to prevent overly optimistic decisions. We will see that the rectifiers in both decision-maie making and penalty update leads to upper bound on "regret + violation" as a whole (Lemma 1). which further leads separate upper bounds on regret and (hard) constraint violation. This approach is different from the primal-dual optimization that quantifies the constraint violation indirectly by bounding the dual variables/virtual queues.
Finally, we comment that our algorithm only needs to solve an "almost" unconstrained optimization problem (X' is usually a simple set like the box constraints). Therefore, we might find its close-form with the inverse operation of the function by taking "gradicnt zero" or mrddient-based methods are sufficient to find the minimizer. For example, we could use the accelerated method in [23] to find the minimizer with linear and dimension-free converge rate. Our algorithm more efficient than the projection online gradient descent algorithm [38] and online Frank- Wolfe algorithm [12], and has similar complexity with [30, 34]. Moreover, our algorithm does not assume any information on the type of constraints apriori and projection- methods are only feasible when the constraint set is available beforehand.
mexximal-gradiee
We next analyze the regret and violation of RECOO as defined in (3) and (4) based on the following standard technical assumptions on the feasible set, loss and constraint functions.
5

---

Assumption The feasible set X' is convex with diameter D such that 1|z- < D, D', e X.
Assumption The loss function is convex and Lipschitz continuous with Lipschitz constant F such that (f((x) - ff(('') & F||x- - d'I1, Vx, x' E X.VI. VL.
Assumption The constraint function functtion is convex and Lipsehitz continuous with Lipschitz constant G such that (3) 9=(=") & Gl Il), Vx, x' X, Vt. For ease of exposition, assume 91(0) & 0.
Note Assumption 1 implies the feasible set X' is bounded. Assumptions and mean the loss and constraint functions have bounded gradients. With these assumptions, we are ready present our main result of RECOO for both fixed and adversarial constraints.
Theorem Choose a = vt, Ttt = Vt, and " = t2+c, where E 0. Under Assumptions 1-3, RECOO algorithm achieves the following regret and constraint violation bounds:
F2 D2
R(T) <
+
VT (fixed or adversarial constraints),
4
V(T) EF² + FD
1
+ D2 (fixed constraints), and
G 4 +
FD 5+ ) 2D²) T (adversarial constraints).
V(T) & r2
Remark For fixed constraints, Theorem establishes the optimal order-wise results of O(vT) regret and O(1) violation since 52( ()) regret is the well-known lower bound for OCO with general convex loss and (1) )1) is the best
have. For adversarial constraints, by carefully choosing the learning rates in RECOO, we can establish trade-off of O(T)) regret and -(T))=/2) cumulative violation where e E [1/2, 1) (see details of Corollary in Appendix C). Moreover, Theorem suggests that large may imply small upper bounds of constraint violation. Our experiment results in Section 4 show that a small e (e.g., 0.01 or 0.1) is sufficient to keep the violation small.
Next, we show Theorem can be further improved when the loss function is strongly convex. Assumption 4 The loss functions fe(.), Vt, are j-sttronly convex in X for μ 0, Lee f((x') > fe(z) + (x' x, fx)))) + _ - x'12,, Va, x' E X, Vt.
With Assumption 4, we are able to establish a O(log T') regret whiling keeping the violation bounds at the same or a smaller order.
Theorem Choose the learning rates to be a ut Tt = vt, = té Vt E [T], where e >> 0.
Under Assumptions 1-4, RECOO achieves the following regret and violation bounds:
2 (1 + log I)) (fixed or adversarial constraints),
R(T)
2p
F2
1+ -) (fixed constraints), and
V(T) + FD
11
F2
G
1 1 _ E p. + D2 VT(1 log 7) (adversarial constraints).
V(T)
+
FD
11
Remark The O(lgg T) regret is a well-known result in OCO (unconstrained) for a strongly convex loss function [11]. Therefore, for fixed constraints, our results are order-wise sharp because O(1) violation is the best one can achieve.
Extension to a dynamic baseline
So far, the main results are against static baseline x² = x* Vt. We next analyze the performance of RECOO against a dynamic bascline as in [37, 30], where 2 could be different from x but with limited variation such that D"'1 | x & Pr. We define the regret against the dynamic baseline to be Ryynamic (T) > f((xz) - - fe(x)). Without any modifications, we show that RECOO algorithm can achieve ((vT(1 Pr)) regret and O(1) violation in the following theorem.

---

Theorem Under Assumptions 1-3, let the learning rates be = = = tà +c, At E [T] where E 0. Let { be the optimal solution to (2) with an additional constraint that 2 I++11 - xell = Pr. RECOO achieves the following bounds on the regret and cumulative constraint violations:
F
R.ynamic (T)
+
D2
+ 2DPP)
vT+1 ++1 (fixed adversarial constraints),
2
V(T) EF FD 1 1
(1+²)
+ + (fixed constraints), and
G² +
FD 5+ ! 2D T (adversarial constraints).
V(T) F2
Remark 3 RECOO achieves O (PIVT) regret and O(1) violation for fixed constraints, which improves O (Pr regret and (/4 violation in [30]. Moreover, RECOO achieves (Pr-T) regret and ((T3/1) violation for adversarial constraints, which is new result. As shown in Corollary 2 in Appendix F, combining RECOO with expert-tracking proposed in [37], we achieve O (VPIT) regret and Ollog T) violation for fixed constraints, which improves O (vPrT) regret and O violation in [30].
Next, we provide the detailed analysis of Theorem 1. The proof' Theorem 2 and Theorem 3 can be found in Appendix.
3.1 Proof of Theorem
We first introduce key lemma that establishes upper bound "regret plus violation" each round t, which we called self-bounding property.
Lemma (Self-Bounding Property) Let be any feasible solution to offline COCO (2) and xa be the optimal solution returned by the RECOO algorithum. We have
F2
fc(x,) - fa(x) + ((t)))((441)
&
arl|z
x11² as||z x++1
(5)
4ac
Define x to be the optimal solution to offline COCO in (2) and let = x* in Lemma 1, we establish the regret and the constant violation bounds in Theorem
Proof of Theorem 1: fixed constraints
Note that Q(t)a, (#e+1) is nonnegative. Based on (5), we have
F
f((2,) fx(**)
+ a, a,1x**
xrl1² 1= xe+1
(6)
4a,
F2
(x++1) & (x++1)
+ (f((z)) fe(x*)] )1 + ax11x* rz r212 2212-oi x1+111?
(7)
4a;
which we will use next to establish the bounds on regret and violation.
Regret bound: We sum up inequality (6) for t 1,... T and have
22 T
[n(a - f((x)))
(a
( 2x11
at
F2
T
2
(at-)
where the first inequality holds by dropping the last negative term and the last inequality holds by Assumption 1. Choose 0₁ = Vl, we have
F2 D2 VT.
( - f((x*)) &
7

---

Violation bound: We substitute the definition of 0. (-) in (7) and have
9r. (x(+1) &
F2
+
[5((x))
- [1(x*))
Ott
It - x 12- at
1a++1 x=1]
4Q(t)am
Q(th
Q(t)
Q(t)
F
2
|1++1
x011
41
8I+E
t2+e
where the second inequality holds by Q(t) > 1/2 according to the rectified penalty update Q()) max (Q(t 1) + 9r (m) The inequality implies that
T
(((()) - f((x") +++
2
x* x²12
x
96 (2(+1)
+
11
FD
FD
D
E
where the second inequality holds by Lemma 6, which includes the detailed calculations of the three terms above. Note that the left-hand-side of inequality (8) is not the violation because the index mismatch (the violation at round i is ot (ax) not 9e" 1))
For fixed constraints, i.e. (x))) g(z), the inequality above implies that V(T) := g < F² + FD (1 + !) + D We have proved the first part of Theorem for the fixed constraints. Let us continue with (8) to prove the second part of Theorem for adversarial constraints.
Proof of Theorem 1: adversarial constraints
To quantify V(T) Ei=1 Di (11) for the adversarial constraints, we need to establish the rela- tionship between g; (xx)) and 9, (I++1) to address the index mismatch, which can be bounded by || - xxll2 as shown in the following lemma.
Lemma 2 Under Assumptions 1-3, RECOO achieves for any
G²
ge (zx) - g6 (I1+1)
&
+ + - x++1l?
43
The next lemma further quantifies Σt_ |1:441 - 1212
Lemma Under Assumptions 1-3, RECOO achieves
T
1011 - 2.12² < 4FDDT D². Σ
Take summation of this equality in Lemma 2 from = 1 to T, and we have
T
G2T
T
(xx) - ge (I(+1)) <
Σ
x - x1+1 1
43
G
<
+ 4FD
73/4 + D2T1/4
where the last inequality holds by letting 1/4 Combining (8) and (9) completes the proof.
Experiments
In this section, we present synthetic and real dataset experiments for evaluating the performance of RECOO with fixed and adversarial constraints. We compared RECOO with the algorithms in [35, 30] for the fixed-constraints setting; with the algorithm in [31] for the adversarial-constramn setting; and with the algorithms in [31, 32] for the data-et setting. All results are obtained by averaging over 500 trials and reported with 95% confidence interval.
Fixed constraints Similar to [30], we considered loss functions fe(x) (((t), x), where 0(1) time varying and unknown at round t; and the fixed constraint function Ar & b, where R

---

A E R and b E IR'. We chose the number of total rounds to be T = 5, 000, and chose {(t)
(t), (t), (s()), where (1) U- +t!:10);
02(() ) U)-1,0) when & E [1, 1500] u
[2000, 3500] u [4000, 5000] and (t) e (0. 1) otherwise; and (t(t) = (-1) where (ut) is random permutation of vector [1 : 5000]. Let U(0.1,0.5g 0.5), & i & 3, & 2, and 4; 0.3), & & 3, respectively.
{a/0 & 21 & 1, & 22 E 1], Ar,
We compared RECOO with the algorithm in [35] and Algorithm and Algorithm in [30], where the learning rates are summarized in Table
Appendix G, which are the values suggested in [35] and [30]. Figure la illustrates the trajectories of the cumulative loss > fx,)), where we observe that all algorithms have similar trends while RECOO achieves the best cumulative loss. Figure Ib shows RECOO achieves the smallest cumulative violation. In particular, the (mean, variance) pair of RECOO for loss and violation are (-500.23, 38)78) and (0.05, 0.008) at the end of the learning horizon; that of Algorithm in [30] (-507.17, 36.46) and (0.23, 0.007); that of Algorithm 2 in [30] are (- 5-9.999990000 36.73) and (0.16, 0.008); and that of Algorithm [35] are (-504.8) 1044881,36..0 36.82) and (980.64, 10.49). These results and Figure 1 confirm that RECOO outperforms the existing algorithms w.r.t both cumulative loss and violation.
RECOO
1000
RECOO
Algorithm in [30]
Algarithm [30]
-100
Algorithm in [35)
Algorithm in [30)
Constraint Violation
800
Algorithm [35]
Algorithm 2 in [30]
2000
600
-300
400
400
200
-500
190
3000
1000
2000
3000
4000
5000
1000
2000
3000
4000 5000
Round
Round
(a) Loss
(b) Cumulative Violation
Figure 1: Experiment with fixed constraints
1750
RECOO Algorithm [31]
RECOO Algorithm [31]
40000
1500
Constraint Violation
1250
30000
1000
20000
750
1000
500
10000
1000
250
1000
2000
4000 Round
3000
5000
1000
2000
3000 Round
4000
5000
(a) Loss
(b) Cumulative Violation
Figure 2: Experiment with adversarial constraints
Experiment with adversarial constraints We considered OCO with adversarial constraints similar as the one in [31]. The loss function was chosen to be fe(x) [I) x y(t]l² with H()) E 10 x E IR10 and y(1) R where H() ~ U(-1, 1), & 4,1 < & < 10, and (t) Σ (t) E, with e; being the standard normal random variable for any i. The constraint functions were chosen to be ge(xr) A(t)x b(t) with A(I) 2 and b(t) R2,
where (t) U(0, 2), j,t and b,(t) UO. 1), Vi, t, respectively.

---

We compared RECOO with Algorithm in [31], where the learning rates are summarized in Table 4 in Appendix Figure 2 includes the cumulative losses and violations. variance) pair of RECOO for loss and violation are (42510. 14, 18.38.00 38.05) and (713.45, 1.60) at the end of learning horizon, respectively while that of Algorithm 1 in [31] are (43011 1.29, 56.17) and (1684.17, 2.85). Therefore, RECOO performs better, especially in terms of the cumulative violation, which further shows the "rectified" design reduces the cumulative hard constraint violation.
particular, the (mean,
Experiment of online job scheduling in distributed data centers We also tested our algorithm for online job scheduling
distributed data center similar as [32]. We considered a distributed data center with server clusters located at different regions. The incoming jobs arrive at front-end load balancer and will be scheduled different clusters fulfill the service. The service capability of a cluster is function w.r.. its energy consumption and the energy prices vary across locations and times. The goal is to minimize safety-critical jobs. This problem can be formulated as constrained online convex optimization problem and solved by our algorithm.
energy cost while guaranteeing real-time processing of
Specifically, we considered r = 10 regions, each region has 10 clusters, and each time/round has 5 minutes. Let 24 10:00 be the energy allocation vector of all clusters round t, where the ith entry is the energy allocation of cluster i. Let f((1))) = (Ce, Xz), where et E 100 are the energy prices at time t. Let gt (x²) d -ー (xr,)),, where A is the number of job arrivals during time t and (,,,) = 4 log [1 + 4xy,;) is the service capacity of cluster at round t. The constraint violation represents the number of delayed jobs (jobs not severed in real-time). In the experiment,
used the electricity price trace (i.e., {cr}) between 05/01/2001 2017 and 05/ 10/ 2017 at 10 different regions in New York city from NYISO [1]. We calibrated job arrivals of realistic traffic pattern from [28] with a non-stationary Poisson process {Ar} to replace the stationary traffic studied [32].
We compared our algorithm with [31] and [32], where learning rates are summarized in Table 5 in Appendix G. We plotted average energy costs and constraint violations in Figure 3. shows that our algorithm achieves better performance on the loss and constraint violation (the number of delayed jobs) compared [31] and [32].
30000
RECOO Algorithm 1 [31]
RECOO
Algorithm in [31] Algorithm in [32)
25000
Algorithm [32]
Average delayed joobs
400
Average Cost
20000
300
15000
1100
2116
2008
2014
200
10000
5000
100
2700
2130
1000
2000
0
500
1000 1500 2000 2500 Round
Round
(a) Average Costs
(b) Average Cumulative Violation
Figure Experiment of online job scheduling in a distributed data center
Conclusions
In this paper, we studied online convex optimization with hard constraints (COCO-HAS -ard) under two settings: fixed constraints and adversarial constraints. We proposed RECtified Online Optimization algorithm (RECOO) and proved achieves the best of two worlds and beyond. The algorithm improves the best-known results for the fixed-constraints, matches the best results for the adversarial- constraints, outperforms the state-of-art results when the loss functions are strongly-convex. The experiments confirmed our thcoretical results.
10

---

References
[1] New york ISO open access pricing data. http:///www.miiss..oom.
[2] Kamiar Asgari and Michael J. Neely, Bregman-style online convex optimization with energy- harvesting constraints. Proc. ACM Meas. Anal. Comput. Syst. (POMACS), 2020.
[3] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Dual mirror descent for online allocation problems. In Proceedings of the 37th International Conference on Machine Learning. PMLR, 2020.
[4] Xuanyu Cao and K. J. Ray Liu. Online convex optimization with time-varying constraints and bandit feedback. IEEE Transactions on Automatic Control, 64(7):2665-2680, 2019.
[5] Xuanyu Cao, Junshan Zhang, and H. Vincent Poor. A virtual-queue-baser algorithm for constrained online convex optimization with applications to data center resource allocation. IEEE Journal of Selected Topics in Signal Processing, 12(4):703-716, 2018.
[6] Xuanyu Cao, Junshan Zhang, and H. Vincent Poor. Online stochastic optimization with time- varying distributions. IEEE Transactions on Automatic Control, 160441884--1847, 2021.
[7] Nicolo Desa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[8] Gong Chen and Mare Teboulle. Convergence analysis of proximal-like minimization algorithm using bregman functions. SIAM Journal on Optimization, ((3))538-545 1993.
[9] Tianyi Chen, Qing Ling, and Georgios B. Giannakis. An online convex optimization approach proactive network resource allocation. IEEE Transactions on Signal Processing, 65(24))6350- 6364, 2017.
[10] Elad Hazan. Introduction online convex optimization. Foundations and Trends@ in Opti- mization, 2(3-4): 2016.
[11] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning. 69(2):169- 192, 2007.
[12] Elad Hazan and Satyen Kale. Projection-free online learning. In Proceedings of the 29th International Coference International Conference on Machine Learning, 2012.
[13] Wei-Kang Hsu, Jiaming Xu, Xiaojun Lin, and Mark R. Bell. Integrated online learning and adaptive control in qucueing systems with uncertain payoffs. Operations Research, 70(2): 166- 1181, 2022.
[14] Rodolphe Jenatton, Jim Huang, and Cédric Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. In International Conference on Machine Learning. pages 402-411. PMLR, 2016.
[15] Ramesh Johari, Vijay Kamble, and Yash Kanoria. Matching while learning. Operations Research, 69(2):655-611, 2021.
[16] Nikolaos Liakopoulos, Apostolos Destounis, Georgios Paschos, Thrasyvoulos Spyropoulos, and Panayotis Mertikopoulos. Cautious regret minimization: Online optimization with long-term budget constraints. In Proceedings of the 36th International Conference on Machine Learning, 2019.
[17] Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: online convex optimization with long term constraints. The Journal of Machine Learning Research, 13(1):2503- 2528, 2012.
[18] H. Brendan McMahan, Gary Holt, D. Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, Sharat Chikkerur, Dan Liu, Martin Wattenberg, Arnar Mar Hrafnkelsson, Tom Boulos, and Jeremy Kubica. Ad click prediction: view from the trenches. KDD, 2013.

---

[19] Michael J. Neely. Stochastic network optimization with application to communication and queueing systems. Synthesis Lectures on Communication Networks, 3(1):1-211, 2010.
[20] Michael J Neely and Hao Yu. Online convex optimization with time-varying constraints. arXiv preprint arXiv: 1702.0/700.04783,, 2017.
[21] Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:
2019.
[22] Omid Sadeghi, Prasanna Raut, and Maryam Fazel. A single recipe for online submodular maximization with adversarial stochastic constraints. In Advances in Neural Information Processing Systems, 2020.
[23] Mark Schmidt, Nicolas Roux, and Francis Bach. Convergence rates of inexact proximal- gradient methods for convex optimization. In Advances in Neural Information Processing Systems, volume 24, 2011.
[24] Shai Shalev-Shwartz. Online learning and online convex optimization. Found. Trends Mach. Learn., 4(2):107-194, 2012.
[25] Wen Sun, Debadeepta Dey, and Ashish Kapoor. Swaet algorithms for adversarial contextual bandit. In International Conference Machine Learning, pages 2288. PMLR, 2017.
[26] Ambuj Tewari and Susan A. Murphy. From Ads to Interventions: Contextual Bandits in Mobile Health. Springer International Publishing, 2017.
[27] Xiaohan Wei, Hao Yu, and Michael Neely, Online primal-dual mirror descent under stochastic constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(2):1-3,, 2020.
[28] Qizhen Weng, Wencong Xiao, Yinghao Yu, Wei Wang, Cheng Wang, Jian He, Yong Li, Liping Zhang, Wei Lin, and Yu Ding. MLaaS in the wild: Workload analysis and scheduling in Large-Scale heterogeneous GPU clusters. 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22), 2022.
[29] Lin Xiao. On the convergence rates of policy gradient methods. arXiv:2201.07443 2022.
arXiv preprint
[30] Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and Karl Johansson. Regret and cumulative constraint violation analysis for online convex optimization with long term constraints. In International Conference on Machine Learning, pages 11998-12008, PMLR, 2021.
[31] Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and Karl H Johansson. Regret and cumulative constraint violation analysis for distributed online constrained convex optimization. arXiv preprint urXiv: 105.00311, 2021.
[32] Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic con- straints. Advances in Neural Information Processing Systems, 30, 2017.
[33] Hao Yu and Michael J. Neely. Learning-aided optimization for energy-harvestin devices with outdated state information. IEEE/ACM Transactions on Networking, 27 27(4):100-1511, 2019.
[34] Hao Yu and Michael J. Neely. A low complexity algorithm with O(VT) regret and O(1) constraint violations for online convex optimization with long term constraints. The Journal of Machine Learning Research, 21(1):1-24, 2020.
[35] Jianjun Yuan and Andrew Lamperski. Online convex optimization for cumulative constraints. Advances in Neural Information Processing Systems, 31, 2018.
[36] Mohammad Zhalechian, Esmaeil Keyvanshokooh, Cong Shi, and Mark P. Van Oyen. Personal- ized hospital admission control: contextual learning approach. Available at SSRN 3653433,
2020.
12

---

[37] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environments. Advances Neural Information Processing Systems, 31, 2018.
[38] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pages 928-936, 2003.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [No] We didn't find any major limita-
tions in applying our results constrained online convex programming.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "K8lM4H8dAu", "reviewer": "Reviewer_DX8X", "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.", "questions": "Let me know if I miss something about the relation with classical online convex optimization problems.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies a well known important problem.\nThe paper is well written and provides a detailed comparison with previous works.\nThe paper provides new techniques that are useful to obtain better regret and violation bounds to the problem.\n\nI have a huge concern about the significance of the result, at least for the setting with fixed constraints.\nIn 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.\nThe 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]).\n\nHowever, 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)$.\nMoreover, 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.\n\nPost-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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Iah9IOLI-9", "reviewer": "Reviewer_YFq8", "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.", "questions": "I have already mentioned many of my suggestions and questions earlier. In addition:\n- 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)\n- 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.\n-  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.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Paper is well-written and the authors have done an excellent job motivating the problem and giving intuitions for their algorithm.\n- The literature review is comprehensive and clearly compares and contrasts related works to this paper.\n- 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.\n\nWeaknesses:\n- 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).\n- 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.\n- 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.\n- The notion of path length $P_T$ has been used several times in the paper before it is finally defined on page 6.\n- 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.\n- 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7aSayy5W-I6", "reviewer": "Reviewer_iYny", "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. ", "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.'", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ The presentation is clear. \n+ The theoretical results are new and important. \n+ The experiments provide a comprehensive view of their algorithms. \n\nWeaknesses:\n+ 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0xu4iq-fTeY", "reviewer": "Reviewer_bywb", "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. \n", "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? \n", "limitations": "This works addresses the potential social impacts. \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Clarity\n\nThe 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. \n\nSince 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. \n\nOriginality\n\nConsidering the hard constraint in OCO is novel and also important for real-world problems. \n\nQuality\n\nThe 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. \n\nSignificance\n\nThe result is important for the real-world problem and besides, they improve the CV bound in a few settings compared to the existing results.  \n\n\nLimitation\n\nThe 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.   \n\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept