Optimal Algorithms for Online Convex Optimization with Adversarial Constraints
Authors: Abhishek Sinha
Rahul Vaze
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Online Convex Optimization
Regret bounds
Constraint violation bounds
Primary area: online_learning
TL;DR: We propose a new learning policy for online convex optimization with adversarial constraints. The proposed policy attains the optimal regret and cumulative constraint violation bounds.

Abstract: A well-studied generalization of the standard online convex optimization (OCO) framework is constrained online convex optimization (COCO). In COCO, on every round, a convex cost function and a convex constraint function are revealed to the learner after it chooses the action for that round. The objective is to design an online learning policy that simultaneously achieves a small regret while ensuring a small cumulative constraint violation (CCV) against an adaptive adversary interacting over a horizon of length $T$. A long-standing open question in COCO is whether an online policy can simultaneously achieve $O(\sqrt{T})$ regret and $\tilde{O}(\sqrt{T})$ CCV without any restrictive assumptions. For the first time, we answer this in the affirmative and show that a simple first-order policy can simultaneously achieve these bounds. Furthermore, in the case of strongly convex cost and convex constraint functions, the regret guarantee can be improved to $O(\log T)$ while keeping the CCV bound the same as above. We establish these results by effectively combining adaptive OCO policies as a blackbox with Lyapunov optimization - a classic tool from control theory. Surprisingly, the analysis is short and elegant.

Optimal Algorithms for Online Convex Optimization with Adversarial Constraints
Abhishek Sinha, Rahul Vaze
School of Technology and Computer Science Tata Institute of Fundamental Research Mumbai 400005, India
sinsahikisinnahiiir. res. in, rahul. wwweegmail.cc.oooommm com
Abstract
A well-studied generalization of the standard online convex optimization (OCO) framework constrained online convex optimization (COCO). COCO, on every round, convex cost function and convex constraint function are revealed to the learner after it chooses the action for that round. The objective to design an online learning policy that simultaneously achieves small regret while ensuring small cumulative constraint violation (CCV) against an adaptive adversary interacting over a horizon of length T. long-standing open question in COCO is whether an online policy can simultaneously achieve O regret and Ó CCV without any restrictive assumptions. For the first time, we answer this in the affirmative and show that simple first-order policy can simultancously achieve these bounds. Furthermore, in the case of strongly convex cost and convex constraint functions, the regret guarantee can be improved to O(og T) while keeping the CCV bound the same as above. We establish these results by effectively combining adaptive OCO policies as a blackbox with Lyapunov optimization classic tool from control theory. Surprisingly, the analysis is short and elegant.
Introduction
Online convex optimization (OCO) is standard framework for modelling and analyzing broad family online decision problems under uncertainty. In the OCO problem, on every round f, an online policy first selects an action from a closed and convex admissible set (a.k.a. decision set) X. Then the adversary reveals a convex cost function fc, resulting in a cost of fxx)). The goal of an online policy to choose an admissible action sequence {z,)²- so that its cumulative cost is not much larger than that of any fixed admissible action chosen in hindsight. In particular, the objective minimize the static regret defined below
T Regrety = sup sup Regrety((x") where (egret,(x')) = M(a)) E (f.)., stex
(I)
The term static refers to using a fixed benchmark, specifically only action x² throughout the horizon of length? T.
In this paper, we consider generalization of the standard OCO framework. In this problem, on every round f. the online policy first chooses an admissible action I; X, and then the adversary chooses a convex cost function ft : X + R and & constraints of the form It. (z: s O, i [R]] where R is convex function for each i [k]] Since Jt, 's are revealed after the action is
gr.i X
Notations: For any natural number n, define [m]] 21, ... n1. For any real number z, define
z))
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

chosen, an online policy need not necessarily take feasible actions on each round, and the obvious metric of interest in addition to (1) the total cumulative constraint violation (CCV) V(T) defined as
T CCVr = V(T) máx máx (T) where V,(T) = (oi)(
(2)
Let X' be the feasible set consisting of all admissible actions that satisfy all constraints gr,( s O, i E [k]] [T'] Under the standard assumption that X' is not empty, the goal is to design an online policy to simultaneously achieve a small regret (1) with respect to any admissible benchmark x' xX and small CCV (2). We refer to this problem
the constrained OCO (COCO). The assumption X + Ø will be relaxed in Section for the Online Constraint Satisfaction (OCS) problem where the cost functions are set to zero, and the objective is to minimize just the CCV.
COCO arises in many applications, including online portfolio optimization with risk constraints, resource allocation in cloud computing with time-varying demands, pay-per-click online ad markets with budget constraints [Liakopoulos et al., 2019], online recommendation systems, dynamic pricing, revenue management, robotics and path planning problems, and multi-armed bandits with fairness constraints [Sinha, 2024a]. The necessity for revealing the constraints sequentially may also arise, e.g., in communication-linin the feasible set at a time (e.g., combinatorial auctions). See Section 4 for an application of the COCO framework in fraud detection which involves binary classification with highly-imbir iiballnnceddd dataset.
settings, where it might be infeasible to reveal all constraints defining
1.1 Related Work
In a seminal paper, Zinkevich [2003] showed that for solving (1), the ubiquitous projected online gradient descent (OGD) policy achieves an O (VTT) regret for convex cost functions with uniformly bounded sub- sub-gradients A number of follow-up papers proposed adaptive and parameter- freee versions of OGD [Hazan et al., 2007, Orabona and Pál, 2018]. See Orabona [2019], Hazan [2022] for textbook treatments of the OCO framework and associated algorithms.
Unconstrained OCO:
Constrained OCO (COCO): (A) Time-invariant constraints: A number of papers considered COCO with time-invarinn invariatt constraints, i.e., It.: 9t. V t [Yuan and Lamperski, 2018, Jenatton et al., 2016. Mahdavi al., 2012, Yi et al.. 2021]. These works assume that the functions ge are known to the policy a priori. However, they allowed the policy to remain infeasible on any round to avoid the costly projection step of the vanilla projected OGD policy. Their main objective was to design an efficient policy (avoiding the explicit projection step) with small regret and CCV.
(B) Time-varying constraints: Solving the COCO problem when the constraint functions, ie.. St. change arbitrarily with time / is more challenging. In this case, except for Neely and Yu [2017] and Liakopoulos et al. [2019]. most of the prior works construct some Lagrangian function and then update the primal and dual variables [Yu et al., 2017, Sun et al., 2017, Yi et al., 2023]. However, the performance bounds obtained with this approach remain suboptimal. Both Neely and Yu [2017] and Liakopoulos et al. [2019] use the drift-plus- ceft--plus--enalty (DPP) framework introduced by Neely [2010] to solve the constrained problem under various assumptions. In particular, Neely and Yu [2017] proposed a DPP-based policy for COCO upon assuming the Slater's ' condition, i.e., gt.; ) -m), for some 17 > Vi,t. Clearly, this condition precludes the important case of neganege constraint functions (e.g.. constraint functions of the form max(0, ga (z))). Furthermore, the bounds obtained upon assuming Slater's condition depend inversely with the Slater's constant 17 (usually hidden under the big-Oh notation). Since 1/ could be arbitrarily small, these bounds could be arbitrarily loose. I Liakopoulos et al. [2019] extended Neely and Yu [2017]'s result by considering a weaker form of the feasibility assumption without assuming Slater's 's condition. Furthermore, although these DPP-based results are interesting, they have not been able to provide improved regret or CVV bounds when the cost functions ft's 's are strongly convex because of the linearization step inherent in this approach.
In a recent paper, Guo et al. [2022] considered COCO and obtained the best-known prior results without assuming Slater's 's condition. However, in addition to yielding sub-optimal bounds, their policy is quite computationally intensive since requires solving convex optimization problem on each round. Compared to this, all policies proposed in this paper take only single gradient-descee descent step and perform only one Euclidean projection on each round. Please refer to Table for brief summary of the results and Section A.5 in the Appendix for qualitative comparison. The COCO problem has been considered in the dynamic setting as well [Chen and Giannakis, 2018, Cao and Liu, 2018, Vaze, 2022, Liu et al., 2022] where the benchmark x in (1) is replaced by x that is also

---

Reference
Regret
CCv
Complexity per round
Assumptions
Mahdavi et al. [2012]
O(VT)
O(T
Projection
constraints
Jenatton et al. [2016]
O(Tmax(b.10))
O(T
Projection
Time-invariant constraints
Sun al. [2017]
((VT)
"(T
Bregman Projection
Neely and [2017]
(VTT)
((VT)
Conv-OPT
Slater condition
Yuan and Lamperski [2018]
0(1mex(611-0)
O(TI-8/2)
Projection
Time- Inne-invariant constraints
Yu and Neely [2020]
O(VT)
O(1)
Conv-OPT
Slater & Time-invariant constraints
Yi ct al. [2021]
((T
O(TO-913)
Conv-OPT
Time-invariant constraints
et al. [2022]
)
-(3)-P13)
Projection
Strongly convex cost
Guo et al. [2022]
O(VT)
O(T
Conv-OPT
Guo et al. [2022]
(log
OVTTlg T)
Conv-OPT
Strongly convex cost
Yi ct al. [2023]
O(Tmax(41-0)
O
Cony-OPT
Yi et al. [2023]
((log(T))
0 (VTTlog)
Conv-OPT
Strongly convex cost
This paper
((VT)
0 ( TTogg T)
Projection
This paper
O(log
0 MVTTlog T)
Projection
Strongly convex cost
This paper
T)
0 (T
Projection
Strongly convex cost, Regrety O,
Table 1: Summary of the results COCO. Unless stated otherwise, we assume arbitrary time-varying convex constraints and convex cost funcctions. In the above table, 0 s 8 1 adjustable parameter, is the strong convexity parameter the strongly convex cost functions. Conv-OPT refers solving constrained convex optimization problem on cach round. Projection refers to the Euclidean projection operation on the convex set X. For typical convex sets (e.g. Euclidean box, probability simplex), projection operations are substantially more efficient than solving constrained convex optimization problem.
allowed to change its actions over time. However, we focus our attention on achieving the optimal performance bounds for the static version. A special case of COCO is the ONLINE CONSTRAING AINT AATISFATTION (OCS) problem that does not involve any cost function, i.e., ft = O, VI, and the only object interest is the CCV, The OCS problem becomes especially interesting in the setting where the feasible set may be empty.
1.2 Our Contributions
In this paper, we consider both COCO and OCS problems and make the following contributions.
1.
We propose efficient first-order policy that simultaneously achieves O(VT) regret and O(VTlog T) CCV for the COCO problem. Our result breaks the Long-standing O(T%) barrier for the CCV and matches the lower bound (derived in Theorem 3, previously missing from the literature) up logarithmic term. For strongly convex cost functions, the regret guarantee is improved to O(log T) while keeping the CCV bound the same as above. Under an additional assumption that the regret is non-negative, we obtain a further improved logarithmic CCV bound in the strongly convex setting (see Table 1).
2. We additionally consider special case of the COCO problem, called Online Constraint Satisfaction (OCS), under relaxed feasibility assumptions and obtain sub-linear CCV bounds.
3. On the algorithmic side, our policy simply runs an adaptive first-order OCO algorithm as a blackbox a specially constructed convex surrogate cost function sequence. On every round, the policy needs to compute only two gradients and an Euclidean projection. This is way more efficient compared the policies proposed in the previous works [Guo al., 2022, Neely and Yu, 2017], which need to solve expensive convex optimization problems on each round while yielding sub-optimal bounds. Furthermore, in the special case of time-invariant constraints, our results yield an efficient first-order OCO policy with competitive regret and CCV bounds [Mahdav et al., 2012, Jenatton al., 2016, Yi et al., 2021].
4. Our results are obtained by introducing a crisp and elegant potential mic technique simultaneously controlling the regret and the CCV. brief, the regret and CCV bounds are derived from single inequality that arises from plugging in off-the-shelff adaptive regret bounds in a new regret decomposition result (Eqn. (6)). This new analytical technique might also be of independent interest.
baseid algorith-

---

5. Finally, in Section 4, we evaluate the practical performance of our algorithm in the online credit card fraud detection problem with highly imbalanced dataset.
2 The Constrained OCO (COCO) Problem
2.1 Assumptions
We now state the assumptions considered in this paper. These assumptions are standard in literature on the COCO problem [Guo et al., 2022, Yi et al., 2021, Neely and Yu, 2017].
Assumption 1 (Convexity). The cost function ft X + R and the constraint function It., : X H R are convex for all t 2 i, [k]. The admissible set (a.k.a. the decision set or the action set) X = R closed and convex and has a finite Euclidean diameter D.
Assumption 2 (Lipschitzness), All cost functions {ft)t21 and the constraint functionn {gt, (et,s)ee(K]) ke[k), 's are G-Lipschitz, In other words, for any 2, y E X, we have
(f(()) - fe(y) s G||z - yll. 19t,s gt.s (v)) G|| vll. Vt [K].
Unless specified otherwise, the norm ||-Il will refer to the standard Euclidean norm and ff will refer to an arbitrary subgradient of a convex function f. Assumption 2 implics that the form of the gradiiradeents of the cost and constraint functions are uniformly upper-boundee by G over the admissible set X' Finally, we make the following feasibility assumption about the constraint functions.
Assumption 3 (Feasibility). There exists a feasible action x' EX s.I. (t., set X' is defined to be the set of all feasible actions. The feasibility assumption implies that X Ø.
) s $O, VI,i. The feasible
The feasibility assumption distinguishes the cost functions from the constraint functions and is commonly assumed in the literature [Guo et al., 2022, Neely and Yu, 2017, Yu and Neely, 2016, Yuan and Lamperski, 2018, Yi et al., 2023, Liakopoulos et al., 2019]. In Section 3, we will consider a constraint-only variant of the problem where the feasibility assumption (Assumption 3) will be relaxed. See Appendix A.1 for brief discussion the assumptions.
Remarks: On each round, multiple constraints of the form (t.) s $0,i E [1e] can be replaced by single new constraint (x))) & 0 where the constraint function Oe is defined to be the pointwise maximum of the given constraints, i.e., (I) max (z). E X. It is easy to verify that if each of the constraint functions { satisfies the above assumptions, then the constraint function It defined above also satisfies the assumptions. Hence, throughout this section and without loss of generality, we will assume that only one constraint function is revealed on each round. That being said, under the relaxed feasibility assumption in Section 3, this trick does not work and there we will need to consider the full set of & constraint functions.
2.2 Online Policy for COCO
Recall that compared to the standard OCO problem where the only objective is to minimize the Regret [Hazan, 2022], in COCO, our objective is twofold: simultaneously control the Regret and the CCV. See Section A.2 in the Appendix for preliminaries on the OCO problem and some standard results which will be useful in our analysis. In the following, we propose a Lyapunov function lunetion-based policy that yields the optimal Regret and CCV bounds for the COCO problem. Although for simplicity, we assume that the horizon length T is known, we can use the standard doubling trick for an unknown T.
2.3 Design and Analysis of the Algorithm
To simplify the analysis, we pre-process the cost and constraint functions on each round as follows.
On every round, we first clip the negative part of the constraint function to zero by passing it through the standard ReLU unit. Then, we scale both the cost and constraint functions by a positive factor 3, which will be determined later. In other words, we work with the pre-processed inputs f. f 9i- + =( Hence, the pre- rrepprceeseed functions are 3G-Lipschitz and ğ, 0, Vt.
Pre-processing:
In the following, we derive the Regret and CCV bounds for the pre-processed functions. The bounds for the original problem are obtained upon scaling the results back by 8-1 in the final step.

---

Algorithm Online Policy for COCO
Input: Sequence of convex cost functions {ft]T- and constraint functions {9))
common Lipschitz constant, T' Horizon length, D Euclidean diameter of the admissible set
X, Px(+)= Euclidean projection operator the X'
2: Parameter settings:
1. Convex cost functions: / (2GD) V 1,X= 2/T ((x) exp(Ax)
8G In(Te) ((x) = =x?
a-strongly convex cost functions: | 1,
3: Initialization: Set 1 X arbitrarily, Q(0)= =
4: for each 1 do
5: Play Z2. observe 9t, incur of f((zz) and constraint violation of (*
6:
f. - ft, max Or (x+).
7: @(t) = 1) 1)+
8:
Compute (sub)gradient V. = VV=((((z)) where the surrogate function fi is defined in Eqn. (5)
9:
Tt+1 Px m/ V.), where
22n
for convex (AdaGrad stepsizes)
2/ -1 1V-11
71-
for strongly convex costs (H,= strong convexity parameter fa: 2 1)
E H."
10: end for each
2.3.1 Defining the Surrogate Cost Functions
Let Q(t) denote the CCV for the pre-processed constraints up to round t. Clearly, Q(t) satisfies the simple recursion Q(t) Q(t - + (xx),, 1, with Q(0) Recall that one of our objectives is to make Q(t) small. Towards this, let Φ R4 + R_ be any non-decreasing differentiable convex potential (Lyapunov) function such that ((0) Using the convexity ((-), we have
((Q()) s ((Q(1-1) 1)) ((Q(t- + (Z))))
- ((()))((()(((1))))))
Hence, the change (driff) of the potential function ((Q(t)) on round can be upper bounded ((Q(t)) - ( - 1)) s ((((()))
(4)
Recall that, in addition to controlling the CCV, we also want to minimize the cumulative cost Σi (xxe) (which is equivalent to the regret minimization). Inspired by the stochastic drift-plus- penalty framework of Neely [2010], we combine these two objectives to single objective of minimizing a sequence of surrogate cost functions {ft) which are obtained by taking a positive linear combination of the drift upper bound (4) and the cost function. More precisely, we define
(5) In the above, V is suitably chosen non-negative parameter be determined later. In brief, the proposed policy for COCO, described in Algorithm I, simply runs an adaptive OCO policy on the surrogate cost function sequence (feh with a specific choice of the potential function ((-), the parameter V, and step-size sequence ) as dictated by the following analysis.
f((z) = f(()) + (Q)))) 2 1.
2.3.2 The Regret Decomposition Inequality
Let x" e X' be any feasible action guaranteed by Assumption (3). Plugging in the definition of surrogate costs (5) into the drift inequality (4), and using the fact that gr (x" 0, VT 1, we have
(x*)) fx (x"), Vr 1. Summing the above incqualities for rounds 5 S and using the fact that (0) 0, we obtain
((Q(T)) ( - 1)) + v(f
(((())) /'Regret, s Regret((x") (x"), Vx e eX"
(6)
where Regret, on the LHS and Regret, on the RHS of (6) refer to the regret for learning the pre- processed cost functions (e and the surrogate cost functions { hea respectively. We will use
5

---

the following upper bound on the fo-norm of the (sub)gradients G2 of the surrogate cost function ft defined in Eqn. (5):
Gx ((V) S (z)vf(==)]+++ - (Q(E)) & 3G(V+ (Q()))
(7)
where in (a), we have used the triangle inequality for & norms and in (b), we have used the fact that all pre-processed functions are SG-Lipschitz.
2.3.3 Convex Cost and Convex Constraint Functions
We now apply the regret decomposition inequality (6) to the case of convex cost and convex constraint functions. Let choose the regret-minimizing OCO subroutine for the surrogate cost functions to be the OGD policy with adaptive step sizes (a. AdaGrad) described in part of Theorem in the Appendix (see Algorithm 1). Plugging in the adaptive regret bound (24) on the RHS of (6), setting = (2GD)-*, and using Eqn. (7), we arrive at the following incquality valid for any t 2 1:
((Q(1)) + (xgret,(""")) S Σ (+'(Q(+))) +VVL
(8)
In deriving the above result, have utilized simple algebraic inequalities (x + y)² 2(x +²) and Va+ S va + Vb, a, 2 O. Now recall that the sequence {Q(t)) non-negative and non- decreasing as 2 O. Furthermore, the derivative D'(-) is non-decreasing as the function (-)) is assumed be convex. Hence, bounding all terms in the summation on the RHS of (8) from above by the last term, we arrive at the following inequality for any feasible x' e X
(()())) Reegret, (x") s 4 ((((t))
(9)
The simplified regret decomposition inequality (9) constitutes the key step for the subsequent analysis.
Performance Analysis
An exponential Lyapunov function: We now derive the Regret and CCV bounds for the proposed
policy (Algorithm 1) by choosing (c-) to be the exponential Lyapunov function: Φ(x) exp(Az) where the parameter À 2 0 will be fixed later. Clearly, the function o(.) satisfies the required
conditions for a Lyapunov function it is non-decreasing and convex function with ((0)= = 0.
Bounding the Regret:
With the above choice for the Lyapunov function 4(-), Eqn. (9) implies that for any feasible x' ex and for any E [T], we have
exp()Q(t)) 1 + VReeret, (x")= s A Xexp(XQ(t)) VVV.. Transposing the first term on the above inequality to the RHS and dividing throughout by V, we have:
1 exp(AQ(t)) (AV7-1).
Regret, (x") s Vt+ V
(10)
V
Choosing any As 1 the last term in the above inequality becomes non-positive for any te [T]. .T. Hence, for any x² E X", we have the following regret bound
Vt [T]. Regret, (egret,(x")= Vi+ V
(11)
Bounding the CCV: Since all pre-processed cost functions are 8G (2 Dt
2 2-1 Hence, from Eqn. (10), we have trivially have Regret,(x") E. (fo(x.) fx())) 2 2D that for any \ - and any Ee [T] exp(AQ(t))
1+2V 1 - Q(t) In 1->Vt
(1 XVt) s 2t
(12)
V
V
Choosing A= 1 2V 1, and scaling the bounds back by 8-1 = 2GD, we arrive at our main result. Theorem 1. For the COCO problem with adversarially chosen G- G-Lipschitz cost and constraint functions, Algorithm 1, with 3 = (2GD) -1 V 1, 1,, ((x) exp( 2²= 1, yields the following Regret and CCV bounds for any horizon length T 2 1:
Regret, s 2GG((Vt+)) 1), Vt e [T], CCV, S 4GD (2(
In the above, D denotes the Euclidean diameter of the closed and convex admissible set X.

---

2.3.4 Strongly Convex Cost and Convex Constraint Functions
We now consider the setting where each of the cost functions ft, 1, is a-strongly convex for some a > 0. The constraint functions St 's are assumed to be convex as before and not necessarily strongly convex. In this case, choose the pegret-miniiizinn cost functions to be the OGD algorithm with the step-size sequence as given in part 2 of Theorem 6 in the Appendix (see Algorithm 1). Since the cost functions are known to be a-strongly convex, each of the surrogate cost functions (5) is V aaastroogly convex. Hence, using the bound from Eqn. (7), choosing the scaling parameter be 1, and simplifying the generic regret bound given by Eqn. (25), we obtain the following regret bound for learning the surrogate cost functions {fr)ei
OCO subroutine for the surrogate
VG2
G (Q((Q()))) T
Regret, s a (1 (1+1)(t)+
aV Σ
x' EX
(13)
In the above, we have used the standard bound for the Harmonic sum: Σt- + S 1 In(t), as well as the fact that (a + b)² < 2(a² + b²). Substituting the bound (13) into the regret decomposition inequality (6), and using the non-decreasing property of the sequence (Q(7))r21 and the derivative oo (.), we obtain
(Q(()) + ('Regret (x") VG
G a (1+In(t)) at ( (L++)())(((((())) Vx" Xx,Vt. (14)
Finally, choosing (-) as the quadratic Lyapunov function, i.e., ((x) x² we arrive the following result for strongly convex cost and convex constraint functions.
Theorem 2. For the COCO problem with adversarially chosen o-strongly convex, G-Lipschitz cost functions and G-Lipschitz convex constraint functions, Algorithm 1, with 3 1,
8G In(ee) ((x) x² yields the following Regret and CCV bounds for any horizon length T 2 1
(oggT) Regret,(x") G ( CCV, = / ), Vx E EX, Vt [T].
Furthermore, if the worst-case regret is non-negative in some round I (i.e., sup Regret (x") ) 2 O), then the CCV can be further improved to CCV1 0 logT) while keeping the regret bound the same.
Please refer to Appendix A.6 for the proof of Theorem 2.
The second part of the theorem surprising because says that when the regret is non-negative, a stronger logarithmic CCV bound holds for not necessarily strongly convex constraints. In Appendix A.7, we give example of an interesting class of adversaries, called conver adversary, for which the non negaavvte regret assumption holds true in the OCO setting.
Remarks:
2.4 Lower Bounds
We now show that under Assumptions 1, 2, and 3, the regret and the CCV of any online policy for the COCO problem for T rounds are both lower bounded by 2(VT) provided the problem is high-dimensional. Recall that if the constraint function 9r 0, Vt, then the COCO problem reduces to the standard OCO problem, and 2( (T) is a well-known regret lower bound for OCO [Hazan, 2022, Theorem 10]. In this case, we trivially have CCV 0. The main challenge in proving lower bound for COCO simultaneously bounding both the regret and CCV. Prior work does not give any simultancous lower bounds since the standard adversarial inputs used to derive the lower bound of Hazan [2022] do not satisfy the feasibility assumption (Assumption 3). We derive the lower bound by constructing sequence of cost and constraint functions that satisfy Assumption 3 in d-dimensional Euclidean box of unit diameter.
Theorem 3. Under Assumptions 1, 2, and 3, for any choice of the horizon length and online policy, there exists problem instance with dimension d 2 T where min(Regrets CCVr) = =
In high-dimensional problems where d >> T, the above lower bound matches with the upper bound given in Theorem 1. The proof of Theorem can be found in Appendix A.4.
7

---

3 The Online Constraint Satisfaction Problem (OCS)
In this section, study special case of the COCO problem, which involves only constraint functions and no cost functions. The OCS problem arises in many practical settings, including the multi-task learning problem (see Section A.3 in the Appendix for a brief discussion). In Section A.8 in the Appendix, we also establish a connection between the OCS problem and the well-studied Convex Body Chasing problem [Argue al., 2019]. The setup is similar to the COCO setting on every round t 2 1. an online policy selects an action I; from a closed, bounded, and convex admissible set X _ Rd After observing the current action zt, the adversary chooses constraints of the form gt. (z) & O, i E [k), where each 9t,i : X' - R is a convex function. Let be any sub-interval of the horizon [1. The cumulative constraint violation (CCV) V(T) for the OCS problem is defined as the maximum signed cumulative constraint violation in any sub-interval:
V(T) máx V. (T), where V.(T) max Σ (z)) i i-1
(15)
2=[1,2] 1eT
The objective is to design an online learning policy so that V(T) is as small as possible. It is worth noting that in the OCS problem, we consider a soft constraint violation metric maxy Σtez (x,) instead of the hard violation metric E (z), as in COCO. This allows for compensating the infeasibility on one round with strict feasibility on other rounds. In contrast with the COCO setting, without Assumption 3, running a no-regret policy the pointwise maximum of the constraint functions no longer works as the CCV of any fixed benchmark could grow linearly with T. In the OCS problem, we relax the feasibility assumption (Assumption 3), and consider the following two distinct alternatives instead.
1. S-feasibility: Here, we assume that there is an admissible action x² с X that satisfies the aggregate constraints over any interval of S rounds. However, unlike Liakopoulos et al. [2019], which also considers the same assumption, the value of the parameter S is not necessarily known to the policy a priori. Towards this end, we define the set of all S-feasible actions X's as below:
Xs = fa" E X: Σ Fra(x") ) s 0, subbinttervals I = [1,7], [ = S, S,vie [+]]. TEL
(16)
We now replace Assumption 3 with the following weaker version: Assumption (S-feasibility). Xs + Ø for some 1 1 S T.
Clearly, Assumption is weaker than Assumption as X S Xs, VS 2 1. Note that even when the individual constraint functions satisfy S S-feasibility, their pointwise maximum need not satisfy S-fcasibility. Hence, unlike COCO under Assumption 3, this problem cannot be solved by simply running a no-regret policy the pointwise maximum of the constraints.
Pr-conntra adversary In this case, we drop any feasibility assumption altogether. As a consequence, any static admissible benchmark x' E X also incurs CCV.
Definition 1. An adversary is called Pr-constrained if its minimum static CCV is PrF, i... F min ex max ExsI (xx( = Pr, where F is a normalizing factor denoting the maxi- mum absolute value of the constraint functions within the compact admissible set X.
As before, the value of Pr is not necessarily known to the policy priori.
3.1 Designing an OCS Policy with a Quadratic Lyapunov function
We define a process Q(1 Q(1== (Q))) [A]), 1, which tracks the CCV:
Q,(1)= ( (Q())))
Q.) 0, 1.2 1, Vi [k].
(17)
Notably, in contrast to COCO, we do not clip the constraint functions in the above recursion. Expanding Eqn. (17), which is also known as the queueing recursion or the Lindley process [Asmussen, 2003, pp. 92], and using the definition in Eqn. (15), we have the following relation for all i [k]:
Vi(T) max max (0, max Σ (...(())) 7=0
max Qi(!). [-1
(18)
s=t-7
Equation (18) indicates that to control the CCV (15), it is sufficient to control the Q(1) process. Similar to the COCO problem, we combine the classic I Lyapunov method with adaptive no-regret OCO policies to control the Q(t) process.
8

---

A Quadratic Lyapunov function: We consider the quadratic potential function +(Q(t))
Σ (t), 1. Since ((x)-)² zr", Vx I, from Eqn. (17), we have
(+( (Qi(t- (Q 1)Q.(t))))())))))))))))) (,(t),,,)z)))
3 2 00000 + (t)())=)(((())(00000)))
[ie
(19)
where in (a), we have used the AM-GM inequality. Rearranging Eqn. (19), the change of the potential function (Q)())) round can be upper bounded as follows
+ -
Σ ((t-)))((--1)) i=1
((())).
(20)
[=1
Similar (5), we now define a surrogate cost function fi :x R linear combination of the constraint functions with the coefficients given by the vector Q(t), ie.
f((z) 2 (.(t)..(.)).
(21)
Clearly, the surrogate cost function fi)- is convex since the coefficients Qi(t)'s non-negative and the constraint functions are convex. Our OCS policy, described below, simply runs regret- minimizing adaptive OCO subroutine the surrogate cost function sequence (21).
The OCS policy (Algorithm 2): Pass the surrogate cost functions {ffete to the AdaGrad algorithm which enjoys a data-dependent regret as given in part of Theorem 6 the Appendix (Eqn. (24)).
Algorithm 2 Online Policy for OCS
1: Input: Sequence of convex constraint functions (9t.)) kc[ closed and convex admissible set X with a finite Euclidean diameter D, Px Euclidean projection operator the X'
2: Output: Sequence of admissible actions {x1
3: Initialization: Set 21 X' arbitrarily, Q,(0) 0, Vi [A:].
4: for each each round 2 1 do
5: Play zt, observe the constraint functions [[t.)) revealed by the adversary.
6: [Update (()) (t) (Qi(t 1) (x,, ii [k].
7: [Compute a subgradient] V. = (x,) 2 (((t)Vg..(zz).
8: [AdaGrad step] Compute the next action 2++1 Px(xx B7, V.), where ?)-
VID
2//21 1V
9: end for each
3.2 Performance Bounds
Theorem Under Assumptions 2, and Algorithm 2 achieves the following CCV bound for the OCS problem: V(T) Omax(1/ST S)).
Theorem 5. Under Assumptions and 2, Algorithm 2 achieves the following CCV bound for the OCS problem for any Pr-constrained adversary as given in Definition I:
V(T) O(PH*TT7))) O(VT).
Trivially, we have S T and Pr T. In the non-trivial case where either S Pr increases sub-linearly with the horizon length T, the above theorems yield sublinear CCV bounds.
4 Experiments: Credit Card Fraud Detection
We first formulate the credit card fraud detection problem in the COCO framework. Assume that we receive a sequence of d-dimensional feature vectors (2) and the corresponding binary labels (ae for sequence of credit card transactions, where each transaction either be legitimate (label = 0) or fraudulent (label 1). The problem
Classification with a highly imbalanced dataset:

---

ROC
Variation of CCV
1.00
0.95
True Postive Rate
11.00
300
01.5
0.50
CCV
200
0.25
0.20
100
0.65
under ROC curver
0.07
0.2
0.4
0.6
0,8
1.0
0.
90003
500000
200040
290331
Falke Positivn Rate
Rounds
Figure 1: ROC curve obtained by varying À
Figure 2: Typical variation of the CCV with time
predict the label in for each transaction ž before its true label y/ E {0,1) } is revealed. Typically, legitimate transactions outnumber fraudulent transactions by orders of magnitude. Since the goal to detect any fraudulent transactions (even at the cost of a few false alarms), maximizing the classification accuracy alone is insufficient due to the significant class imbalance. We propose the following reformulation for this problem within the COCO framework.
Formulation: Let nr ( .)) be the likelihood of class 1 for the feature 2t; given by a parameterized model with parameter æ. Hence, the log- ligelikeihood [(t) of the data on round t can be expressed as:
[(t) ye log( (21, (1 31 log(1 ÿ x)).
We train the model by maximizing the sum of log- likelihoods for legitimate transactions, subject to the constraint that all fraudulent transactions have likelihood value close to (i.e., the sum of the log-iikelshoods of the fraudulent transactions remains close to zero):
T max E ve) log(1 ()(,,,))), s.t.
T
Σ ye log( (=+, 2 O.
(22)
The above problem (22) can be immediately recognized to be an instance of COCO with the following cost and constraint functions:
(x) = -11- - y+) log(1 - (=,,:))) (x(x)) -ye log(ún (=,, t. 1.
In our experiments, we consider the common scenario in which the likelihoods are modeled by the output of feedforward neural network. Note that the feasibility assumption (Assumption 3) is naturally satisfied as the overparameterized neural network models are known to perfectly fit the data [Belkin et al., 2019]. However, in this case, the functions f, and It are generally non-convex.
Experiments: We experiment with a publicly available credit card transaction dataset [Dal Pozzolo al., 2014]. This highly imbalanced dataset contains only 492 frauds (~ 0. 0.17%) out of 284, 807 reported transactions. Fach data point has D., = 30 features and binary labels. We choose a simple network architecture with single hidden layer containing H/ 10 hidden nodes and sigmoid non- lincarities. Unlike previous algorithms, our algorithm is especially suitable for training neural network models as it only needs compute the gradients (via backward pass) and evaluate the functions (via forward pass). Initially, all weights are independently sampled from a standard normal distribution. The network is then trained using Algorithm on a quad-core CPU with 8 GB RAM. The projection operation corresponds to L2 no-mmmallzztionn The code has been publicly released [Sinha, 2024b].
Results: Given the severe class imbalance, the area under the ROC curve, which plots the True Positive Rate (TPR) against the False Positive Rate (FPR), is appropriate metric evaluate any prediction algorithm for this problem. By varying the hyperparameter X, we obtain the ROC curve shown in Figure 1. The under the ROC curve is computed to be 0.92, which is excellent score (cf. ideal score = 1.0), notwithstanding the fact that, unlike the standard resampling-bass based techniques, the algorithm learns in an entirely online fashion starting from random initialization. Figure illustrates the expected sublinear variation of CCV during one of the algorithm runs.
5 Conclusion
In this paper, we proposed efficient online policies for the COCO problem with optimal performance bounds. We also derived sublinear CCV bounds for the OCS problem under a set of relaxed assumptions. Our analysis is streamlined, leveraging Lyapunov theory and adaptive regret bounds for the standard OCO problem. In the future, exploring dynamic regret bounds and bandit extension of the COCO problem would be interesting.
10

---

Acknowledgement
This work was supported by the Department of Atomic Energy, Government of India, under project no. RTI4001 and by Google India faculty research award. The first author was also partially supported by US-India NSF-DST collaborative grant coordinated by IDEAS-Technology Innovation Hub (TIH) at the Indian Statistical Institute, Kolkata. The authors gratefully acknowledge comments from the anonymous reviewers, which substantially improved the quality of the presentation.
References
Nikolaos Liakopoulos, Apostolos Destounis, Georgios Paschos, Thrasyvoulos Spyropoulos, and Panayotis Mertikopoulos. Cautious regret minimization: Online optimization with long-term budget constraints. In International Conference Machine Learning, pages 3944-3952. PMLR, 2019.
Abhishek Sinha. BanditQ Fair Bandits with Guaranteed Rewards. In Uncertainty in Artificial Intelligence. PMLR, 2024a.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-936, 2003.
Elad Hazan, Alexander Rakhlin, and Peter Bartlett. Adaptive online gradient descent. Advances in neural information processing systems, 20, 2007.
Francesco Orabona and Dávid Pál. Scale-free online learning. Theoretical Computer Science, 716:
50 69, 2018.
Francesco Orabona. A modern introduction online learning. arXiv preprint arXiv: 2019.
Elad Hazan. Introduction to online convex optimization. MIT Press, 2022.
Jianjun Yuan and Andrew Lamperski. Online convex optimization for cumulative constraints. Advances in Neural Information Processing Systems, 31, 2018.
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.
Mchrdad 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.
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.
Michael J Neely and Hao Yu. Online convex optimization with time-varying constraints. arXiv preprint arXiv: 04780,777333 2017.
Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic constraints. Advances in Neural Information Processing Systems, 30, 2017.
Wen Sun, Debadeepta Dey, and Ashish Kapoor. Safety-aware algorithms for adversarial contextual bandit. In International Conference on Machine Learning, pages 3280-3288. PMLR, 2017.
Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Yiguang Hong, Tianyou Chai, and Karl Johansson. Distributed online convex optimization with adversarial constraints: Reduced cumulative constraint violation bounds under slater's 's condition. arXiv preprint arXiv:2306.000 406,00/49, 2023.
Michael Neely. Stochastic network optimization with application to communication and queueing systems. Synthesis Lectures on Communication Networks, 3(1):1-211, 2010.
11

---

Hengquan Guo, Xin Liu, Honghao Wei, and Lei Ying. Online convex optimization with hard con- straints: Towards the best of two worlds and beyond. Advances Neural Information Processing Systems, 11336426-36433 2022.
Tianyi Chen and Georgios B Giannakis. Bandit convex optimization for scalable and dynamic iot management. IEEE Internet of Things Journal, 6(1):1276-128)) 2018.
Xuanyu Cao and KJ Ray Liu, Online convex optimization with time-varying constraints and bandit feedback. IEEE Transactions on aulomatic control, 64(7):2655-2680, 2018
Rahul Vaze. On dynamic regret and constraint violations constrained online convex optimization. In 2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt), pages 9-16, 2022. doi: 10. 10129999/110111521...0000 99302...
Qingsong Liu, Wenfei Wu, Longbo Huang. and Zhixuan Fang. Simultaneously achieving sublinear regret and constraint violations for online convex optimization with varying constraints. ACM SIGMETRICS Performance Evaluation Review, 49(3):4-5, 2022.
Hao Yu and Michael J Neely. A low complexity algorithm with ((VT) regret and o(1) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 21(1):1-24 2020.
Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and H Karl. Regret and cumulative con- straint violation analysis for distributed online constrained convex optimization. IEEE Transactions on Automatic Control, 2022.
Hao Yu and Michael Neely. A low complexity algorithm with o (T) regret and o(1) constraint vio- lations for online convex optimization with long term constraints. arXiv preprint 160::2604.02218. 2016.
CJ Argue, Sébastien Bubeck, Michael B Cohen, Anupam Gupta, and Yin Tat Lee. nearly-lineat bound for chasing nested convex bodies. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 117-122. SIAM, 2019.
Søren Asmussen. Applied probability and queues, volume 2. Springer, 2003.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical varianee trade-off. Proceedings of the National Academy of Sciences, 116632):15449-15855 2019.
Andrea Dal Pozzolo, Olivier Caelen, Yann-Ael Le Borgne, Serge Waterschoot, and Gianluca Bon- tempi. Learned lessons credit card fraud detection from a practitioner perspective. Expert systems with applications, 41(10):4915-4928, 2014. The dataset is available for download at htttps:/wwee kaggle com//ataasets/nlg-ulb httpa///rreedttrrrrrraaadee
Abhishek Sinha. Source code for "Optimal Algorithms for Online Convex Optimization with Adversarial Constraints"; A. Sinha, R. Vaze. https://gi com/ hoom/abhiseeeeee. sinha-tifr/ COCO, 2024b.
Max Hopkins, Daniel M. Kane, Shachar Lovett, and Gaurav Mahajan. Realizable learning is all you need. In Proceedings of Thirty Fifth Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 3015-3069. PMLR, 02-05 Jul 2022.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari. Online linear optimization via smoothing. Conference on Learning Theory, pages 807-823, 2014.
Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Delay-tolerant online convex optimization: Unified analysis and adaptive-gradien algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
12

---

Sebastian Ruder. An overview of multi-task learning in deep neural networks. arXiv preprint arXiv:1706.05098 2017.
Ofer Dekel, Philip Long, and Yoram Singer. Online multitask learning. International Conference on Computational Learning Theory, pages 453-467. Springer, 2006.
Keerthiram Murugesan, Hanxiao Liu, Jaime Carbonell, and Yiming Yang. Adaptive smoothed online multi-task learning. Advances in Neural Information Processing Systems, 29, 2016.
Nikhil Bansal, Martin Böhm, Marek EliáS, Grigorios Koumoutsos, and Seeun William Umboh. Nested convex bodies are chaseable. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1253-1260. SIAM, 2018.
Sébastien Bubeck, Bo' az Klartag, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Chasing nested convex bodies nearly optimally. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1196-1508, SIAM, 2020.
13

---

A Appendix
A.1 Discussion on Assumptions 1, 2 and 3
Assumptions and 2 are standard in the online learning literature. The feasibility assumption (Assumption 3) is analogous to the realizability assumption in learning theory [Hopkins et al., 2022] and is commonly used in the COCO literature [Neely and Yu, 2017, Yu and Neely, 2016, Yuan and Lamperski, 2018, Yi et al., 2023, Liakopoulos et al., 2019]. Assumption 3 requires the existence of a single admissible action x' ε X' that satisfies the constraints in every round. Consequently, all constraint functions are required to non-positive over a non-empty common subset. This assumption is weakened in Section 3, Assumption 4, which only requires the existence of fixed admissible action x" that satisfies the constraints on average. Specifically, Assumption 4 requires that the sum of the constraint functions evaluated at some admissible x' over any interval of length S is non- non-positive. Notably, throughout the paper, we do not assume Slater's 's condition as it does not hold in many problems of interest Yu and Neely, 2016]. As result, unlike many previous works [Yu et al., 2017], our bounds are independens of Slater's ss constant, which can be Furthermore, we do not restrict the sign of either cost or constraint functions, allowing them to take both positive and negative values.
A.2 Preliminaries on Online Convex Optimization (OCO)
The standard OCO problem can be described as repeated game between an online policy and an adversary [Hazan, 2022]. Let X' S IKd be convex decision set, which we refer to as the admissible set. In each round & 2 I, an online policy selects an action H, E X. After the action de is chosen, the adversary reveals a convex cost function f: : X + R. The goal of the online policy is to choose an admissible action sequence {>1 so that its total cost over horizon length T is not significantly larger than the total cost incurred by any fixed admissible action x' 6 X. More precisely, the objective to minimize the static regret, defined as:
T
T f((z))
Regrety sup Regrety-(x"), where Regrety(xx)) 2*
Σ
ff E=1
(23)
Algorithm 3 Online Gradient Descent (OGD)
Input: Non-empty closed convex X' R2, sequence of convex cost functions (ff)
step
sizes 1/, ... '/r 0, Fuclidean projection operator Px (-) onto the set X'
2: Initialization: Set I1 e X arbitrarily
3: for each round f 2 do
4: Play It. observe ft, incur a cost of ft(x)).
5: Compute a (sub)gradient V, (z.)).
6: Update 1t+ Px - V.).
7: end for each
In a seminal paper, Zinkevich [2003] showed that the online gradient descent policy, outlined in Algorithm 3. run with an appropriately chosen constant step size sequence, achieves sublinear regret bound Regrety- O(VT) for Lipschitz-conting continuos convex cost functions. In Theorem 6, we recall two standard results further refined data- data-dependent adaptive regret bounds achieved by the OGD policy with appropriately chosen adaptive step size sequences.
Theorem 6. Consider the generic OGD policy outlined Algorithm
1. [Duchi al, 2011], [Orabona, 2019, Theorem 4.14] Let the cost functions (fehez be vID .l 2 1, where
convex and the step size sequence be adaptively chosen as 2/E,,, G
D is the Euclidean diameter of the admissible set X and G2 (IV 2 1. Then Algorithm achieves the following regret bound:
T Σ
Regrety S V2D
G3
(24)
14

---

The OGD policy with the above adaptive step-size sequence is known as (a variant of) the AdaGrad policy the literature (Duchi et al., 201
2. [Hazan el al., 2007, Theorem 2.1]
] Let the cost functions (fe) be strongly convex and let He O be the strong convexity parameter' for the cost function ft- Let the step size sequence
be adaptively chosen as Tt Σ.-1 H." 1. Then Algorithm 3 achieves the following regret bound:
1 Σ G. 2 t- E H
Regrett
(25)
Similar adaptive regret bounds are known for various other online learning policies well. For structured domains, one can use other algorithms such as AdaFTRL [Orabona and Pál, 2018] which gives better regret bounds for high-dimensional problems. Furthermore, for problems with combinatorial structures, adaptive oracle-efficient algorithms, e.g., Pollow-the-Perturbeel-- (FTPL)-based policies, can be employed [Abernethy et al., 2014, Theorem 11]. Our proposed policies are agnostic to the specific online learning subroutine used for the surrogate OCO problem what matters that the subroutine provides adaptive regret bounds similar (24) and (25). This flexibility allows for an immediate extension of our algorithm to wide range of settings, such as delayed feedback [Joulani al., 2016] combinatorial actions.
A.3 Online Multi-task Learning as an Instance of the OCS Problem
Online policy
Action
Tasks Constraint functions
(x
Shared weights
zec
9e.2 (24)
ge,e(w))
Loss feedback
Figure 3: A schematic for the online multi-task learning problem
Consider the problem of online multi-task learning where a single model is trained to perform a number of related tasks [Ruder, 2017, Dekel et al., 2006, Murugesan al., 2016). See Figure for a simplified schematic of the multi-task learning pipeline. In this setup, the action naturally corresponds the shared weight vector that specifies the common model for all tasks. The loss function for the ,th task on round is given by the function (.. [k]] A task is assumed be satisfactorily completed (e.g., correct prediction the case of classification problems) on any round if the corresponding loss is non-positive. As an example, using linear predictors for the binary classification problem, the requirement for the jth task on round can be taken to be (x.) = (z). O, where žt,j is the feature vector for the jth task. The goal in multi-task learning is to sequentially update the shared weight vectors {xt] so that all tasks are successfully completed. Formally, we require that the maximum cumulative loss of each task over any sub-interval grows sub-linearly. Since the weight vector is shared across the tasks, the above goal would be impossible to achieve had the tasks not been related to each other [Ruder, 2017]. Theorem 4 and Theorem give performance bounds for Algorithm 2 under different task-relatedness assumptions.
'The strong convexity of fe implies that fe(v) f((x) (Vf+(r),
#1 vll Vz,ye X, Vt.
15

---

A.4 Proof of Theorem 3
We prove the Theorem via constructing an explicit input sequence for which no online policy can have better than (VVT) regret and CCV.
Action space X: Let d T. Let X' be the d-dimensional cuboid 0 24 Va isis d. Clearly, the Euclidean diameter of X' is 1.
For each round we will only consider the case when only one constraint is revealed, i.e., 3 k On round l....,d, choose the constraint Ie be 2t S _ or 24 4v7 with equal 4v7
Input:
probability of 3 for (#1,...,,ad)) X. Thus, at round only the 1th dimension has effective constraint. If the chosen 9: is x2 4/a then pick ft f --al. otherwise pick ft = ayal
For any online policy A, the expected constraint violation round & is least z Thus, the overall expected constraint violation over rounds ( I,..., d is at least Ld 8
Moreover, the expected cost is least
[x:) of A least _ for each t I,..., d, and the overall cost [8| //
8va
Recall that the choice of input has to satisfy Assumption 3, i.e. X Ø. We next demonstrate that for the prescribed input x" E X
Choosing feasible x": When Ii is such that the constraint is Ze 4/7 choose x' X such that a; = 1 for t 1,2,....d d, while if Ie is such that I2z 1yd' then choose xi 4/d t 1, 2, .....: d. Thus, single vector satisfies the revealed constraints. Moreover, with this choice of x", the overall cost of x, Ex is O.
3
3 for
t/d
Since d = T, we get that for any online policy A its regret is at least R(VT) and the cumulative constraint violation is Si( ((VT).
A.5
Comparison with Previous Works
A.5.1 Neely and Yu [2017], Yu et al. [2017] and Liakopoulos al. [2019]
Policies proposed by Yu al. [2017] and Liakopoulos al. [2019] are almost identical Neely and Yu [2017]. The policy proposed in Neely and Yu [2017], however, is highly customized, does not fully exploit the best guarantees available for the standard OCO problem, and obtains sub-optimal performance bounds that depend inversely on Slater constant, which is assumed to be strictly positive. In nutshell, Neely and Yu [2017] choose the next action F++1 using the algorithm described below. For all rounds t 2 1, define the following evolution for Q(t):
(t)) (Q(t - 1) + ge (2+)) v ge (x: - =x=1))* Q(0) =
(26)
The next action is chosen by solving the following quadratic optimization problem:
1t+1 = arg min ø
[(VV" f((x)) + (z),,) + alkx 1
where V and a are suitably chosen parameters. In comparison, we have a different and simpler update rule:
Q(t) = ()) (2)))) Q(0)= =
(27)
200
We then construct a convex surrogate function f((x) f((x)+ aGD e R/T is then passed directly to the AdaGrad subroutine.
(ge (x)),, whose gradient
We emphasize that Theorem 1, which shows that it is possible to simultaneously achieve O(VT) regret and ((VT) CCV in the convex setting without assuming Slater's condition, is highly surprising and unexpected. fact, Liakopoulos et al. [2019, Section 4] had previously commented that:
Remarks:
16

---

"... On the other hand, the point O(VT), O(VT) achieved by Neely and Yu [0017] for K= = is not part of our achievable guarantees; we attribute this gap to the stricter Slater assumption studied by Neely and Yu [2017]."
Theorem squarely falsifies the last conjecture.
A.5.2 Guo al. [2022]
The policy in Guo et al. [2022] is a slightly modified form of the policy proposed in [Neely and Yu, 2017]. In particular, it chooses the action by solving the following quadratic optimization problem over X::
xz arg min (V- - Q(t 1)7--19;11 ar-1llx- x2-111²] nex
where the Q variables are updated as follows:
Q(t) = max max((((t + 70-19--1(x))
Here dt,, Tt, "t are suitably chosen learning rate parameters. Essentially, this policy trying find the local optimum of an augmented Lagrangian under the online information model (ft and dr are revealed after action I; chosen). Since their augmented Lagrangian involves the constraint function 9t-1. their policy needs to solve a full-fledged constrained convex optimization problem over the after having full access the constraint funetion. In comparison, our policy, rather than using approximations to Lagrangian and adding regularizers, makes full use of the well-developed theory for OCO and uses first-order methods that need to compute only a gradient and perform one Euclidean projection each round.
A.5.3 Jenatton et [2016]
The policy proposed by Jenatton al. [2016] is based the idea of primal-dual algorithm for optimizing the augmented Lagrangian
f((z) + (g((2) x²
where d/2 X2 is the augmentation term. The primal variable x, and the dual variable A are updated by executing projected gradient descent and gradient ascent the Lagrangian follows:
Tt+1 Px(xx V. (x)
and
A = (h + 44 (
where fr. Th, and hr are parameters to be chosen.
A.6 Proof of Theorem
Bounding the CCV:
Choosing (xx) x in Eqn. (14), we have for any feasible x² X²
VC² (1+In(t)) Q2) In(T)) Q²( VRegret, (a') a
(28)
aV
where, the last term in the RHS, we have used the fact that t s T. Setting V 8G 8G In(T)) transposing the last term on the RHS to the left, the above inequality yields
and
(t 2V Regret, (x") GVG2 (n+)).
(29)
Since the cost functions assumed to be G-Lipschitz (Assumption 2), trivially have Regret, (x*) (fo f((x)) -GDt. Hence, from Eqn. (29), obtain
GD @²(1) < 2VGDL 2VG2 (1 (1+In(1) = Q(1) (0) 4G GD
(n(T))+++ ln
where step (a), we have substituted V= 8G" (TTe) Hence, we have the following bound CCV, [
0(1
17

---

Bounding the regret: Using the above choice for the parameter V and the fact that Q² 2 0, from Eqn. (29), we have
2VG²
2V (x")
a (1+In(t)).
This leads the following logarithmic bound for regret for any feasible x² e
G
Regret, (x)) a (1 In(t).
A sharper CCV bound under the non-negative regret assumption: We now establish an improved CCV bound when the worst-case regret is non-negative on some round Let sx Regret, 2 0 for some round / 2 1. Letting V SG In(Te) as above, from Eq. (29) we have
2VG2 (1(1) s (1+In(1) = Q(1) 0 ( (T)
Comment: From the above proof, immediately follows that the same conclusion holds even under the weaker assumption of Regret, 0 log
A.7 Adversaries Ensuring Non-negative Regret
Convex adversary: An adversary is called convex if for any sequence of action sequence (2t) ( the adversary chooses the cost function sequence {ft) such that for any T 2 1, we have
T
T Σ f(TT),
(30)
where Tr = T ST Tt. Hence, by definition, convex adversary guarantees non-negative regret with respect the average action ãr for all rounds. the following, we give two examples of convex adversaries.
Fixed adversary: An adversary which always selects fixed convex function f all rounds is convex adversary. In this case, Eqn. (30) holds due to the Jensen's 's inequality.
2. Minimax adversary: Let F denote arbitrary non-empty set of convex functions defined on the admissible set X. Consider an adversary M, which, upon seeing the selected action 2r, chooses the worst cost function fi from the set F round L::
Jt E arg max f(x:). fef
We now show that M a convex adversary. By definition, for any round 7 [T],
we have
1 T
(x = fr(x7)
T El
Summing up the above inequalities for each E [7]. we have
Σ
T ΣーΣ Σ{(T))
T
Σ M(xx,) E f((T))
(31)
where inequality (a) follows upon applying Jensen's inequality each cost function. Eqn. (31) shows that M is convex adversary.
P.S. It can be easily seen that Fixed adversary is special case of Minimax adversary where F= =f}..
18

---

A.8 Connection Between OCS and the Convex Body Chasing Problem
well-studied problem related to the OCS problem is the nested convex body chasing (NCBC) problem [Bansal et al., 2018, Argue et al., 2019, Bubeck et al., 2020], where at each round t, convex set Xt S. X is revealed such that X S Xc-1. where Xo = X E is a convex. compact, and bounded set. The objective is to choose x2 E Xx so as to minimize the total movement cost across rounds C = ΣT_ I|ze 12-1, where Zg is some fixed action. In NCBC, action is chosen after the set Xt revealed. This the constraints Jt., 's are revealed at round t. Moreover, note that the nested condition Xx S Xr-1 is stricter than Assumption 3, which is applicable to the OCS problem. However, as we show next, a feasible algorithm for NCBC also provides an upper bound on the CCV of the OCS problem under Assumption 3.
contrast to the OCS problem, where I; must be chosen before
In this reduction, we define Xt as the intersection of the first kt convex constraints Jr, S 0, S T S t, é [K], revealed up to round for the OCS problem. It is easy to see that X convex and Xt E Xt-1, Vt. Let Fe be the action chosen by an algorithm A for the NCBC problem after the set Xt revealed. Note that X + Ø, thanks to Assumption for the OCS problem on round t, ensuring that action y/ is chosen before the set Xt is revealed. The resulting th constraint violation for the OCS problem at round is given by
We now choose y/ := 2t-1 as the action
(a)
(Ve) S gt., (1te) Dr,, (3)-1) s Glly - V/+all
where (a) follows from the feasibility of A for NCBC, M++1 2, Xt and hence (v.+() 0. Summing across rounds = 1...., T, and taking the max over all the k constraints, we get that the CCV using A for the OCS is upper bounded by Σl= Gllye- - 9-1lll s ΣL Gi| x s G- CA. where CA is the movement cost of A for the NCBC problem.
From prior work Bansal et al. [2018], Argue et al. [2019], Bubeck et al. [2020], it is known that for NCBC, Steiner point-based algorithm that chooses T2 as the Steiner point of X can achieve CA d)) where c 12d. Thus, the Steiner point-based algorithm (even though computationally intensive) provides an O(Vdlog constraint violation for the OCS as well. However, this result effective for problems where VTllo = o(T). Our result efficiently overcomes this hurdle and provides a bound under weaker feasibility assumptions even beyond Vd d o(T) a setting that is better motivated in practice for modern deep learning applications which are characteristically high-dimensional.
A.9 Proof of Theorem 4
Generalized regret decomposition: Then, from Eqn. (20), we have
Fix any S-feasible benchmark x² e Xs, as given by Eqn. (16).
((T) 1) s 2 ((()))))))
2 (()) +2 k (.(())))))z))
k
f(xx)) fxx)) + Σ (((T))nn(t')
Summing up the above inequalities from r = 1o =t, we have
* ((T))) EO(( (t) & Regret', (x') 31 6-1 1-1
(32)
where Regret' (.) refers to the regret of the surrogate costs before. We now bound the last term by making use of the S-feasibility of the action x² as given by Eqn. (16). Let us now divide the entire interval [1, f] into disjoint and consecutive sub-intervals (I, ///5 each of length S (except the last interval which could be of a smaller length). Let Q;( be the value of the variable Qi(-) at the beginning of the 5th interval. We have
[1/8] Σ (.(7))).(x")) = Σ (Q.()) - (117)
[t/ST Q Ena(s"). Σ
(33)
3-1 rel,
TEI,
19

---

Using the boundedness assumption, let (t,( F, Vr e X',,,, Using the Lipschitzness property of the queueing dynamics (17) with respect to time, we have
max
rEZ;
Substituting the above bound into Eqn. (33), we obtain
Σ (((())))))=')) (1+ -(S F(S-1)) r-1
(34)
where in the last term, we have used the S-feasibility of the action all intervals, except possibly the last interval. Substituting the bound (34) into Eqn. (32), we arrive at the following extended regret decomposition inequality:
(t) s Regret((x") 2 St+ 2F (.((+)
*
(35)
==1
Eqn. (35) leads to the following bound the cumulative constraint violation.
A.9.1 CCV Bound
We now apply the generalized regret decomposition bound given in (35) to the case of convex constraint functions. Substituting the regret bound (24) of the AdaGrad policy into Eqn. (35), we have
# 3
& c3S Σ Qi(t)+ca5*
Σ 1-1
20()ssa
Σ
+
where the constants e₁ = oz 0z O(P), O(KF²) are problem-specific parameters that depend on the bounds on the gradients and the maximum value of the constraint functions, the number of constraints, and the diameter of the admissible set. Defining Q² = Σ, (t), we obtain:
@1(1) sc +0( c38 Σ Q1(1)++45*
Since Qi(t) Ft, Vi, the above inequality can be simplified to
$ Σ (TT)+ + cas c
@1(1 scr V
1/21,
(36)
where we have defined d = oskF Cz. To solve the above system inequalities, note that for each 1 7 S t, we have
@²(T) sa (+))
Σ (
Summing up the above inequalities for 1 5 r t and defining 2, = V Q²(T), we obtain
z < ci + S + S²5
i.e., z? s
S,St, 525
Le., Z, = 0(ma((t,1V5,$vV))
Substituting the above bound for 7(t) in Eqn. (36), have for any t 1:
@²(t) O St, St,
i.e. Q(!) O(max( (V St,
Hence, Q,(1) s Q(1) (tmax()St,))) [k).
, S)),
The final result follows upon appealing to Eqn. (18).
20

---

A.10 Proof of Theorem 5
We will use a similar line of arguments used in the analysis of an S-constrained adversary for suitable value of S to be determined later. We start from Eqn. (33), which holds for any value of the sub-interval length Pr-constrained adversary, we know that there exists benchmark x² с X such that for any interval Ij and any E [k:], we have:
and any arbitrary adversary. Furthermore, from the definition of
Σ
(=) PrP,
TEI,
where F is the maximum absolute value of the constraint functions as given in Definition 1. Hence,
[MS]
F 1
1i gra(tt)
Pr
2i()
TEL,
PrF [t//]
PIF Σ Σ -0(0)))((1))) (T())
Σ
S
j=1 j
Hence, from Eqn. (33), we have that
((())))((')) s (1+ t
t
PfF
(
Σ Q((T) $ m=1
P
s (((++))(++
(T)))
S r=1
Substituting the above bound into Eqn. (32), we have that
# 2O((+ s Regret((=")) 2 2 (++ F 1 k
Σ ΣΣO(). --1-=
Plugging in the regret bound of the AdaGrad policy for the surrogate cost functions, the above equation yields
i Σ
F 1 k S ΣΣ
Σ Oi(1) S 2K
2 1-1
(())
(37)
Using Souchy-Schwarze incquality, the last term of the above inequality can be upper bounded by
FV.F kt
Σ
Q((T))
1=1
Hence, we have the following inequality which holds for any 1 S S and stTst:
Ho(()) 5 (GDVEK+ (GDVER
2PrFVkl
Σ Σ
+ 2S (S) t).
(38)
1=1
Summing up the above inequalities for 1 S STSS and defining 7; E. Σ (T( have:
zž S (GDVI*+ 2KrF
tZ, + 2kF t(S Ps)
S
2max (GDV
F kt
)t 2.F +2 Ps)+))+++))))
The above inequality implies that
2PFFVkt
Ze S max
(GDV2k
)t, (.FF((((++)((+++))
S
2PTFVKT KT
2ax
(GDV2k+
T2F PP))
(39)
S
21

---

where in the last step, we have used the fact that 5 7 and S S T. Now, let us choose S P7 PT With the above choice of S, from the above inequality, we have the following bound for Z,
2. S 2 max (GDV ",, + +
where we have used the fact that Pr s T. Substituting the above bound in (38), we have for any 1 i s and any t T
# (t) @ + :00 OO(T),
i-1
where in (a), we have used the fact that 7 S 2 Pr in bounding the last term. Hence, we have the following upper bound on the queue lengths for any 1 T
[(( [1Q(1)22 TP O(VT)
The final result follows upon appealing to the relation (18).
22

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We give complete proofs of all claims made in the paper (either in the main paper or in the Appendix).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We clearly state the assumptions under which our results hold.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
23

---

Answer: [Yes]
Justification: We clearly state the assumptions in the main paper and give complete proofs of all claims (either in the main paper in the Appendix)
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have publicly released the code that it can be used to reproduce the main experimental results reported in this paper. Link to the codebase, which includes detailed instructions on how to run the code, has been included in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
24

---

reproducible, they 5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: We have publicly released the code with clear instructions on how to replicate the experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines futtps://ning cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/nips. wc/public/gute gwwcc//gge/////eeeee /odeeee/ooouemmiiacccc ieaibbmsssioPP. ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Sufficient details have been provided in the paper. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Since the paper deals with worst-case guarantees against adversarial inputs, statistical guarantees are superfluous. Choice of random seeds used the experiments have been clearly specified in the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
25

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Compute details have been mentioned in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: :tttpp::///eurre /ww.rpsu..../// cc cethce/
Answer: [Yes]
Justification:
This work conforms with the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is a foundational work on online learning and does not have a direct socictal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
26

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This thcoretical paper does not pose any such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The public dataset used in the experiments has been appropriately cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
27

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The code we have released is well documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper doess not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
28

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "oSnrVKwoDU", "reviewer": "Reviewer_pcig", "summary": "The major part of this paper studies adversarial OCO with unknown, time varying constraints in the soft-enforcement setup, wherein at each round, both a loss $f_t$, and constraints $g_{t,i}$ are revealed. The performance metrics are the usual regret $\\mathrm{Regret}_T = \\sum_t f_t(x_t) - f_t(x^*),$ and the cumulative constraint violation $\\mathrm{CCV}_T := \\max\\_i \\sum\\_t (g\\_{t,i}(x\\_t))^+,$ where $(\\cdot)^+ = \\max(0,\\cdot),$ and $x^*$ is the best-in-hindsight competitor that satisfies _all_ of the constraints, i.e., $\\forall i, t: g_{i,t}(x^*) \\le 0$. \n\nThe paper shows that under the standard smoothness assumption, a simple modification of OGD, which can be seen as OGD on a loss that regularises constraint violation through a Lyapunov function, ensures that both $\\mathrm{Regret}_T$ and $\\mathrm{CCV}_T$ are $\\tilde{O}(\\sqrt{T})$, without any further assumptions, as were made by prior work when deriving such a result. Further, under strong convexity, the regret bounds improve to $\\log T$ with the same CCV bound. Surprisingly, under strong convexity, the CCV bounds further improve to $\\log T$ if $\\mathrm{Regret}_T > 0$. The authors complement this result with a lower bound that simultaneously asserts that these metrics must both be larger than $\\sqrt{T}$, at least if $T \\le d,$ the dimension of the space.\n\nThe remainder of the paper is devoted to defining and studying the 'Online Constraint Satisfaction' (OCS) problem, which relaxes the assumption that a point satisfying all constraints exists, and demands methods for selecting $x_t$ such that $\\sum g_t(x_t)$ is small over all intervals in $[1:T]$. Under natural relaxations of the existence of an $x$ satisfying all constraints (either by assuming that some $x$ satisfies all \"somewhat aggregated\" constraints, or quantitatively demanding that some $x$ has limited violation across all subintervals), the authors again show that a modified version of OGD, similar in spirit to their earlier method, ensures that the resulting sequence $x_t$ has low violation in the aforementioned strong sense.", "questions": "A suggestion: Definition 1 mixes the definition of the concept of $P_T$ with a bunch of editorialising, which just makes it hard to see what the object being defined is. I would suggest that the definition simply states that $P_T = \\frac1F \\min \\max \\cdots,$ and all of these comments are moved appropriately to either before or after it, but certainly not within the definition itself.", "limitations": "This is fine", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "OCO with unknown constraints has attracted significant interest in recent years, amidst a general rise of interest in multiobjective online learning. I think that the paper makes a valuable contribution to this subfield by removing technical assumptions present in prior work, and by presenting an elegant algorithm with a slick and surprisingly simple analysis for the same. I further find the OCS problem interesting, and the results towards this quite powerful and elegant. I think that this paper will certainly be of interest to the online learning community at neurips.", "weaknesses": "My only real grouse with the paper is the lower bound of Theorem 3, which I find to be overstated. The theorem is presented as \"under assumptions 1, 2, and 3, the regret and CCV are $\\Omega(\\sqrt{T}),$ but the proof only defines a single instance where this occurs, and this further requires the strange assumption that the dimension of the domain $d$, exceeds $T$. I would much prefer that this is made explicit, e.g., to say something like _for any $d, T$ and algorithm, there exists an instance with a single time-varying constraint such that the method suffers $\\min(\\mathrm{regret}\\_T, \\mathrm{CCV}\\_T) = \\Omega(\\sqrt{\\min(T,d)}$._ This still makes the main point of the statement, but is explicit about the strength of the bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\textbf{Lower Bound of Theorem 3}$\n\n$\\textbf{Comment:}$ ``My only real grouse with the paper is the lower bound of Theorem 3, which I find to be overstated. The theorem is presented as - under assumptions 1, 2, and 3, the regret and CCV are $\\Omega(\\sqrt{T}),$ but the proof only defines a single instance where this occurs, and this further requires the strange assumption that the dimension of the domain $d$, exceeds $T$. I would much prefer that this is made explicit, e.g., to say something like for any $d, T$ and algorithm, there exists an instance with a single time-varying constraint such that the method suffers $\\min(\\mathrm{regret}_T, \\mathrm{CCV}_T) = \\Omega(\\sqrt{\\min(T,d)}$. This still makes the main point of the statement, but is explicit about the strength of the bound.\"\n\n$\\textbf{Reply:}$ The reviewer is correct in pointing this out, and we will make the necessary changes to correctly reflect the strength of the result. \n\nOn $d\\ge T$ being a  ``strange assumption,\" we would like to note that when the cost and constraint functions are given by deep neural networks (see, e.g., our experimental setup on the anomaly detection problem discussed below), typically, the dimension of the parameters ($d$) is an order of magnitude larger than the number of data points ($T$). \n\nTechnically, please note that as far as we know ours is the first result in the literature for the COCO problem that simultaneously lower bounds the regret and CCV (cumulative constraint violations) even under this assumption. It would certainly be interesting to remove this restriction and prove a lower bound with a constant dimension.\n\n\n\n$\\textbf{Suggestion to fix Definition 1}$\n\n$\\textbf{Comment:}$ ``A suggestion: Definition 1 mixes the definition of the concept of $P_T$ with a bunch of editorialising, which just makes it hard to see what the object being defined is. I would suggest that the definition simply states that $P_T = \\frac1F \\min \\max \\cdots,$ and all of these comments are moved appropriately to either before or after it, but certainly not within the definition itself.\"\n\n$\\textbf{Reply:}$ We agree with the suggestion, and in our revised version, we will make Definition 1 clearer.", "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": "", "extra_scores": {}}, {"review_id": "LdxcWpMLPd", "reviewer": "Reviewer_FrRh", "summary": "The authors study Online Convex Optimization (OCO) under adversarial constraints of the form $g_{t,i}(x) \\leq 0$ where $g_{t,i}$ are arbitrary convex and Lipschitz. The authors design a simple algorithm based on Lyapunov optimization which obtains an optimal regret rate and simultaneously optimal constraint violation (CCV) of $\\widetilde O(\\sqrt{T})$, and prove a matching lower bound. Their algorithm is based on performing projected OGD updates on surrogate loss functions which are a combination of the objective functions and the constraint functions, with coefficients that depend on a predetermined potential function. For strongly convex losses, the authors establish an improved logarithmic regret bound while maintaining the $\\widetilde O(\\sqrt{T})$ constraint violation.", "questions": "Beside the points I raised under \"Weaknesses\", I would appreciate it if the authors could address the following:\n* The authors remark that the setting of $k$ constraints is equivalent to the single constraint setting by defining the constraint function as the pointwise max over the constraints. While this is true in the offline setting, there is a subtle point in the online setting where the definitions of CCV are not equivalent. Specifically, for $k$ constraints the CCV is essentially a maximum over sum while for a single constraint the CCV is a sum over maximum which is only larger, and thus it suffices, when proving an upper bound, to consider the single constraint setting. I think the authors should elaborate a bit on this point since this is not trivial at first glance.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The authors provide the first provably optimal algorithm in the general COCO setting for convex and Lipschitz loss functions and constraints.\n* The algorithm is strikingly simple and the its analysis is not too complicated given standard OCO regret bound from the literature.\n* The paper is nicely written and the authors provide an overview of the analysis which helps understand the technical contributions.\n* A single algorithmic framework obtains the optimal regret bounds for both convex & Lipschitz and strongly convex settings, with changes made only in choosing the hyperparameters of the algorithm.", "weaknesses": "* The authors do not formally define the interaction protocol in the online setting studied in this paper. Specifically, from lines 27-28 is is implied that the adversary chooses the loss function $f_t(\\cdot)$ adaptively after seeing $x_t$, which of course cannot be the case if sublinear regret is obtained. It is my understanding that the adversary is actually oblivious (the functions and constraints are fixed in advance) and the functions are only revealed to the algorithm after choosing $x_t$. In any case, the authors should properly define the interaction protocol and the exact notion of the adversary in question.\n* It is a bit unclear to me what are the novel techniques utilized in this paper compared to previous works on constrained OCO. Since the analysis seems relatively simple, I think the authors should elaborate on the technical challenges faced when proving their main results, and what novel techniques they used.\n* While the authors claim to only require a call to a projection oracle at every round, there is a subtle point in which they also call a gradient oracle on a combination of the objective function and the constraint function. I am not an expert in the constrained OCO literature, so if this is a standard assumption in this setting I think the authors should mention it or alternatively formally define the type of gradient oracle used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\textbf{Type of adversary:}$\n\n$\\textbf{Comment:}$ ``The authors do not formally define the interaction protocol in the online setting studied in this paper. Specifically, from lines 27-28 is is implied that the adversary chooses the loss function $f_t(\\cdot)$ adaptively after seeing $x_t$, which of course cannot be the case if sublinear regret is obtained. It is my understanding that the adversary is actually oblivious (the functions and constraints are fixed in advance) and the functions are only revealed to the algorithm after choosing $x_t$. In any case, the authors should properly define the interaction protocol and the exact notion of the adversary in question.\"\n\n$\\textbf{Reply:}$\n\nWe reiterate that we consider an adaptive adversary, not just a weaker, oblivious adversary. To be precise, the adversary chooses the cost function $f_t$ and constraint function $g_t$ $\\it{after}$ seeing the action $x_t$ for round $t$. This is a standard definition of the adaptive adversary in online convex optimization (OCO) literature, $\\it{e.g.}$, the textbook [Hazan, Section 1.1], defines the following interaction protocol:\n\n``$\\textrm{.. At iteration t, the online player chooses}$ $ x_t \\in K.$$\\textrm{ After the player has committed to this choice, a convex cost function}$ $f_t$ $\\textrm{is revealed.\"}$ \n\nSee also [Orabona, Section 2.1], which considers the same interaction protocol. For adaptive adversaries, the standard online gradient descent policy is known to enjoy a sub-linear $O(\\sqrt{T})$ regret [Hazan, Theorem 3.1]. \n\nWhile revising the paper, we will make the description of the adversary more clear.\n\n$\\textbf{Novelty:}$\n \n$\\textbf{Comment:}$ ``It is a bit unclear to me what are the novel techniques utilized in this paper compared to previous works on constrained OCO. Since the analysis seems relatively simple, I think the authors should elaborate on the technical challenges faced when proving their main results, and what novel techniques they used.\"\n\n$\\textbf{Reply:}$ Most of the previous papers on this problem used a primal-dual-based technique, which yielded sub-optimal bounds (see Table 1). In this paper, for the first time, we proved a novel regret decomposition inequality (Eq. 6), which results from an entirely different Lyapunov-based argument. Our analysis hinges on solving the regret decomposition inequality, which gives direct control simultaneously over the regret and constraint violations. On the other hand, the primal-dual-based techniques typically analyze the dynamics of the action sequence and lead to a more involved analysis. One of the major contributions of this paper is to pioneer Lyapunov-based techniques in the online convex optimization literature with a simple and elegant analysis, which should be seen as a strength and not a weakness.\n\n$\\textbf{Access to Gradient oracles:}$\n \n$\\textbf{Comment:}$ ``While the authors claim to only require a call to a projection oracle at every round, there is a subtle point in which they also call a gradient oracle on a combination of the objective function and the constraint function. I am not an expert in the constrained OCO literature, so if this is a standard assumption in this setting I think the authors should mention it or alternatively formally define the type of gradient oracle used.\"\n\n$\\textbf{Reply:}$\n\nAccess to the gradient oracle is standard in OCO literature with first-order methods [Hazan, Chapter 3]. This is typically the `minimal' requirement for obtaining non-trivial results, $\\it{e.g.,}$ the online gradient descent (OGD) algorithm. Alternatives to OGD, such as $\\textbf{ Follow the Regulaized Leader}$-type algorithms require full function access for the previous time steps. Note that in addition to the gradient oracles, many of the previous papers on the same problem (referenced in the paper) required access to the entire constraint function (of the previous step) to solve a convex optimization problem (see algorithms using Conv-OPT in Table 1). On the other hand, our proposed algorithm is much more efficient as it only needs to compute the gradient of the cost and constraint functions at the current action $x_t$. \n\n$\\textbf{CCV bound with multiple constraints:}$ \n\n$\\textbf{Comment:}$ ``The authors remark that the setting of $k$ constraints is equivalent to the single constraint setting by defining the constraint function as the pointwise max over the constraints. While this is true in the offline setting, there is a subtle point in the online setting where the definitions of CCV are not equivalent. Specifically, for $k$ constraints the CCV is essentially a maximum over sum while for a single constraint the CCV is a sum over maximum which is only larger, and thus it suffices, when proving an upper bound, to consider the single constraint setting. I think the authors should elaborate a bit on this point since this is not trivial at first glance.\"\n\n$\\textbf{Reply:}$\nAs the reviewer correctly pointed out, since the sum over max is larger than max over sum, constructing a single constraint function $g_t$ by taking a point wise maximum of $k$ constraints suffices as the resulting constraint function $g_t$ satisfies the feasibility assumption (Assumption 3) and bounding the CCV for $\\{g_t\\}$'s bounds the CCV for each of the individual constraint functions. In the revised version, we will state this point more explicitly.\n\n$\\textbf{References:}$\n\n[1] Introduction to Online Convex Optimization, Second Edition, Elad Hazan, MIT Press (2022).\n\n[2] Orabona, Francesco. \"A modern introduction to online learning.\" arXiv preprint arXiv:1912.13213 (2019).", "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": "", "extra_scores": {}}, {"review_id": "iVkoFV57lf", "reviewer": "Reviewer_G8HN", "summary": "This paper considers online convex optimization with constraint. The authors propose a new surrogate loss function, and by applying traditional online learning algorithms to the surrogate loss, $\\mathcal{O}(\\sqrt{T})$ regret and $\\mathcal{O}(\\sqrt{T \\log T})$ can be obtained in the online learning setting. The result improves the state-of-the-art in the domain.", "questions": "**Minor issues**\n\n1. Line 17\n\n   modelling => modeling\n\n2. Line 198\n\n   Please ensure that $x^\\star$ and $x^\\ast$ are consistent\n\n3. Line 228\n\n   0,) => 0),", "limitations": "Please add a section on limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper proposes an interesting construction of surrogate loss function and transforms the regret analysis of constrained online learning into the analysis of a standard online convex optimization problem. The choice of the regularization function $\\Phi$ is interesting and novel to me.", "weaknesses": "1. Compared with Section 2, the results from Section 3 looks not less interesting and they are not the focus of the paper. I suggest the authors could conduct some demonstrating experiments and reduce the contents in Section 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\textbf{On the relevance of the OCS problem}$\n\n$\\textbf{Comment:}$ ``Compared with Section 2, ... reduce the contents in Section 3.\"\n\n$\\textbf{Reply:}$\n The OCS problem considered in Section 3 is interesting from both technical and practical points of view for the following reasons. On the technical side, it gives non-trivial sublinear bounds for constraint violation with a relaxed feasibility assumption, which is much weaker than Assumption 3, used in Section 2. On the practical side, in Appendix A.3, we show that the multi-task learning problem can be formulated in the OCS framework. Reviewer pcig also shares this view and says ``I further find the OCS problem interesting, and the results towards this quite powerful and elegant.\" \n\n\n\n$\\textbf{Adding Experiments:}$\n\nIn the revision, we plan to add experiments for the following important learning problem.\n\n$\\textbf{Online anomaly detection:}$\n\nWe formulate the online version of the anomaly detection problem (described below) in the COCO framework. Our gradient-based algorithm is especially suitable for training neural network models as it only needs to compute the gradients. The online operation is indispensable in the credit card fraud detection setting, where the algorithm needs to continuously learn in a dynamic environment.\n\n$\\textbf{Setup:}$\n\nWe receive a sequence of $d$-dimensional feature vectors $\\\\{z_t\\\\}, t \\geq 1$ and the corresponding binary labels $\\\\{y_t\\\\}, t \\geq 1$. The algorithm predicts the label $\\hat{y}_t$ for a given data point $z_t$ before its true label $y_t$ is revealed. Typically, the number of legitimate transactions (denoted by class ‘0’) outnumbers the number of fraudulent transactions (denoted by class ‘1’) by orders of magnitude. Since in this problem, we want to always detect any fraudulent transactions, just maximizing the classification accuracy is insufficient for the purpose. \n\n$\\textbf{Formulation:}$ Let $\\hat{y}_t(z_t)$ be the probability for class $1$ predicted by some parameterized model for the feature vector $z_t$. Hence, the log-likelihood $L(t)$ of the data on round $t$ can be expressed as \n\n\\begin{eqnarray}\nL(t) = \\begin{cases}\n    \\log(\\hat{y}_t),  \\textrm{ if }  y_t = 1,  \\\\\\\\\n    \\log(1 - \\hat{y}_t), \\textrm{ if } y_t = 0 \n\\end{cases}\n  \\end{eqnarray}\n\nConsider the following optimization problem for training the model:\n$$ \\max \\sum_{t=1}^T (1-y_t)\\log(1-\\hat{y}_t)$$\n\ns.t. \n\n$$  \\sum_{t=1}^T y_t \\log(\\hat{y}_t) \\geq 0,$$\n\nwhere the maximization is done over the parameters of the model. In other words, we want to maximize the log-likelihood for the legitimate transactions subject to the constraint that all fraudulent transactions have a likelihood close to $1$ (i.e. log-likelihood values close to zero). \nThe above problem can be straightforwardly formulated as an instance of the COCO problem by defining the cost and constraint functions as follows:\n$f_t(x) \\equiv -(1-y_t) \\log(1-\\hat{y}_t(z_t,x)), ~~g_t(x)\\equiv -y_t (\\log(\\hat{y}_t(z_t,x))),$\nwhere $x$ denotes the parameters of the model.\n\nIn our experiments, we consider the common scenario where the prediction probability is modeled by the output of a feedforward neural network. Note that the feasibility assumption (Assumption 3) is naturally satisfied as the overparameterized models often perfectly fit the data.\n\n$\\textbf{Experiments:}$\n\nWe experiment with a publicly available credit card fraud detection dataset [1]. It is a highly imbalanced dataset containing only $492$ frauds ($\\sim 0.17\\%$) out of a total of $284,807$ reported transactions, which makes it a challenging benchmark. \n\n$\\textbf{Dataset and Network Architecture:}$ Each data point has $D_{\\textrm{in}}=30$ features and binary labels.  As a proof of concept, we choose a simple two-layer architecture with $H=10$ hidden nodes and sigmoid non-linearity. All network weights are independently initialized according to a standard Gaussian distribution. The model is then trained in an online fashion using Algorithm 1. \n\n$\\textbf{Results:}$\n\nDue to the high class imbalance, instead of accuracy, the area under the ROC curve, which plots the True Positive Rate (TPR) against the False Positive Rate (FPR), is an appropriate metric to evaluate the performance of any prediction algorithm for this problem. By varying the hyperparameter $\\lambda$, we obtain the ROC curve shown in Figure 1 of the attached pdf. The area under the ROC curve is computed to be $\\approx 0.92$, which is an excellent score (cf. ideal score $=1.0$), notwithstanding the fact that the algorithm learns in an entirely online fashion starting from random initialization. Figure 2 shows the expected sublinear variation of CCV during one of the runs of the algorithm.\n\n$\\textbf{References}$\n\n[1] Dal Pozzolo, Andrea, Olivier Caelen, Yann-Ael Le Borgne, Serge Waterschoot, and Gianluca Bontempi. ``Learned lessons in credit card fraud detection from a practitioner perspective.\" Expert systems with applications 41, no. 10 (2014): 4915-4928.\n\n$\\textbf{Typos:}$ We will fix them in the final version. \n\n$\\textbf{Comment:}$ ``Please add a section on limitations.\"\n\n$\\textbf{Reply:}$ \n\n$\\textbf{Limitations and Future works:}$\n\n$\\textbf{1. Relaxed feasibility assumption:}$ Assumption 1, which requires the existence of a single action which satisfies the constraints on all rounds, is non-trivial to ensure. Our results in Section 3 show that it is possible to relax this assumption considerably for the OCS problem. An interesting open problem is to prove similar bounds for the COCO problem under a relaxed feasibility assumption.\n\n$\\textbf{2. Bandit Feedback:}$ It will be interesting to consider the problem under a weaker bandit feedback model, where the algorithm can only query the values of the cost and constraint functions at points of its choice. \n\n$\\textbf{3. Practical Evaluation:}$ It will be interesting to run large-scale experiments and compare our policy with the existing ones in the literature on the standard benchmark problems.", "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": "", "extra_scores": {}}, {"review_id": "bgw51AePlP", "reviewer": "Reviewer_MH7f", "summary": "In this work, the authors study online convex optimization with adversarial and time-varying constraints, and aim to bound both the regret and the cumulative constraint violation (CCV). Compared with previous studies, the main contributions of this work can be summarized as: 1) a new algorithm with $O(\\sqrt{T})$ regret and $O(\\sqrt{T}\\log T)$ CCV for convex functions; 2) a lower bound of $O(\\sqrt{T})$ for the regret and CCV with convex functions; 3) a new algorithm with $O(\\log T)$ regret and $O(\\sqrt{T\\\\log T})$ CCV for strongly convex functions (or $O(\\log T)$  CCV for strongly convex functions with *non-negative* regret); 4) an extension to the online constraint satisfaction problem.", "questions": "Besides the concerns discussed above, I also have the following two questions.\n1) Is it possible to derive the $O(\\log T)$ regret and $O(\\log T)$ CCV for strongly convex functions without the *non-negative* regret?\n2) Can the authors provide more discussions on the CCV bounds established in Theorems 4 and 5?", "limitations": "The authors have provided some discussions on the limitations of their work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Compared with previous studies, this paper has the following strengths.\n1) For convex functions, an improved algorithm is proposed to achieve the $O(\\sqrt{T}\\log T)$ regret and CCV bounds. By contrast, previous studies can only achieve the $O(T^{3/4})$ CCV bound when keeping the $O(\\sqrt{T})$ regret bound.\n2) A matching lower bound of $O(\\sqrt{T})$ is established for the regret and CCV when functions are convex, which reveals the optimality of the proposed algorithm.\n3) For strongly convex functions, this paper proposed an algorithm with $O(\\log T)$ regret and $O(\\sqrt{T\\\\log T})$ CCV. Although previous studies have achieved these regret and CCV bounds, they need to utilize Conv-OPT per round. By contrast, the proposed algorithm only needs to perform one projection per round. Moreover, if further assuming that the regret is *non-negative*, the CCV can be further reduced to $O(\\log T)$.", "weaknesses": "Although this paper provides some new results for online convex optimization with adversarial and time-varying constraints, I have some concerns.\n1) The lower bound for convex functions only holds for the case with $d=T$ or $d>T$. However, for online problems, it may be common to consider a very large $T\\gg d$, which implies that the optimality of the proposed algorithm for convex functions may only hold in limited cases.\n2) Different from the case with convex functions, the authors do not provide a lower bound for strongly convex functions. So, it is not clear whether the $O(\\log T)$ regret and $O(\\sqrt{T\\\\log T})$ CCV can still be improved. \n3) It seems to be trivial to derive the $O(\\log T)$ regret and $O(\\log T)$ CCV for strongly convex functions under the *non-negative* regret assumption. I cannot find any challenge in the analysis, and the existing algorithms may also enjoy the same result.\n4) Although it may be valuable to develop an extension to the online constraint satisfaction problem, the derived CCV bounds depend on some problem-dependent variables, and thus could be even linear in $T$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\textbf{On the lower bound:}$\n\n$\\textbf{Comment:}$ The lower bound for convex functions only holds for the case with $d=T$ or $d>T$. However, for online problems, it may be common to consider a very large $T\\gg d$, which implies that the optimality of the proposed algorithm for convex functions may only hold in limited cases.\n\n$\\textbf{ Reply:}$\nOur lower bound is in the spirit of constructing an input instance for which no online policy can achieve better $\\it{simultaneous}$ regret and CCV, which happens to consider $d\\ge T$. As far as we know, this is the first such lower bound, even though the literature on COCO is extensive. Since the simultaneous lower and upper bounds match, optimality is established in the strictest sense. \n\nFor the general case when $d<T$, from prior work on unconstrained OCO (special case of COCO without constraints), the regret is $\\Omega(\\sqrt{T})$ anyway. Thus, the only possibility, as correctly pointed out by the reviewer, is that the CCV can be lower when $d<T$, but finding a simultaneous lower bound on regret and CCV in this setting appears challenging. \n\n Furthermore, in the practically relevant setting when the cost and constraint functions are given by deep neural networks (see, $\\it{e.g.,}$ the application to the anomaly detection problem described above), typically, the dimension of the parameters $(d)$ is an order of magnitude larger than the number of data points $(T)$. This implies that the regime $d\\geq T$ is practically relevant as well. \n\n$\\textbf{Strongly Convex Case}:$ It turns out that deriving a matching lower bound for the strongly convex case (which has much better regret and CCV guarantee) is much more challenging. \nEven without constraints, the progression of results for OCO with strongly convex loss functions also followed a similar trend where the  $O(\\log(T))$ regret for OGD was shown much earlier than the lower bound of $\\Omega(\\log(T))$. Finding a tight lower bound for COCO in the strongly convex case is an important problem and something that we are actively working on.\n\n$\\textbf{Bounds under the non-negative regret assumption:}$\n\n$\\textbf{Comment:}$\n\n``It seems to be trivial to derive the $O(\\log T)$ regret and $O(\\log T)$ CCV for strongly convex functions under the non-negative regret assumption. I cannot find any challenge in the analysis, and the existing algorithms may also enjoy the same result.\"\n\n$\\textbf{Reply:}$\n \nTo clarify, under the non-negative regret assumption, only the cost function $f_t$'s are strongly convex while the constraint functions $g_t$'s are just convex. \nSince $f_t$'s are strongly convex, it is expected that regret is $O(\\log{T})$, but the fact that \nCCV is also $O(\\log{T})$ even though the constraints are only convex is the surprising part. \n\nEssentially, the assumption that the regret is non-negative is the main reason for getting $O(\\log{T})$ instead of the expected CCV of $O(\\sqrt{T})$  even though the constraints are only convex, which points to a \nnon-trivial interplay between the strongly convex cost and convex constraint functions through the surrogate loss given by Eqn (5). To the best of our knowledge, this is the first such result in the constrained OCO literature. The simple proof attests to the power of the regret decomposition inequality (Eqn (6)), which we introduce in the literature for the first time in this paper. It is not clear whether some of the previous algorithms for COCO also enjoy this property as they use a much more involved primal-dual-based analysis, which does not give direct control over the regret and CCV as Eqn (6). That being said, we would still highly appreciate it if the reviewer could point us to any appropriate reference for a similar result or with simpler proof in the literature on constrained OCO.\n\n$\\textbf{Discussion on the bounds in Theorem 4 and 5:}$\n\n$\\textbf{Comment:}$ ``Although it may be valuable to develop an extension to the online constraint satisfaction problem, the derived CCV bounds depend on some problem-dependent variables, and thus could be even linear in $T$.\"\n\n$\\textbf{Comment:}$ ``Can the authors provide more discussions on the CCV bounds established in Theorems 4 and 5?\"\n\n\n$\\textbf{Reply:}$\n\nSimilar to the dynamic regret bounds in the OCO literature, which involve path length, the bounds in Theorem 4 and 5 are problem-specific bounds.  It is impossible to obtain sublinear violation bounds in the OCS problem without any restriction on the problem instance. This is because if the constraints are such that their feasible sets change non-trivially on every round, then one needs to control the dynamic regret for the time-varying benchmark, which is known to depend on problem-specific parameters such as path lengths. In this problem, the parameters $S$ and $P_T$ capture the extent of time-variation of the constraints. \nTheorems 4 and 5 show that when the parameters $S$ and $P_T$ are sublinear, our algorithm yields sublinear CCV without making the stringent feasibility assumption (Assumption 3).\n\n$\\textbf{Comment:}$ Is it possible to derive the $O(\\log T)$ regret and $O(\\log T)$ CCV for strongly convex functions without the non-negative regret?\n\n$\\textbf{Reply:}$ It seems highly unlikely to obtain $O(\\log T)$ CCV bound for convex cost functions without making any extra assumptions.", "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": "", "extra_scores": {}}]

Author rebuttal:
In the attached pdf, we report our experimental results for the credit card fraud detection problem.

Meta-review: This manuscript studies the online convex optimization (OCO) problem with constraints, and for the first time, develops an algorithm that achieves both an $\widetilde{O}(\sqrt{T})$ regret and $\widetilde{O}(\sqrt{T})$ cumulative constraint violation assuming only the convexity and Lipschitzness. This improvement is significant since the COCO problem has been studied extensively in the literature. The proposed algorithm is also very neat and efficient, by applying a Lyapunov potential to the Adagrad algorithm, instead of using primal-dual based algorithms in the literature. Despite some significance concerns on the lower bounds (such as the right dependence on $d$) and the assumption $\text{Regret}_T \ge 0$, the reviewers unanimously appreciate the final bounds and neatness of the algorithm. Given that this manuscript completes an important picture of COCO and contains significant algorithmic insights, I'll recommend acceptance.
Decision: Accept (spotlight)