$O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization
Authors: Rahul Vaze
Abhishek Sinha
Venue: NeurIPS 2025 poster ()
Keywords: online convex optimization
regret
Primary area: general_machine_learning
TL;DR: An algorithm with a static regret of $O(\sqrt{T})$ and a CCV of $\min\{{\cal V}, O(\sqrt{T}\log T) \}$, for constrained online convex optimization where ${\cal V}$ depends on the geometric properties of the instance .

Abstract: The constrained version of the standard online convex optimization (OCO) framework, called COCO is considered, where 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 simultaneously minimize the static regret and cumulative constraint violation (CCV). 
An algorithm is proposed that guarantees a static regret of $O(\sqrt{T})$ and a CCV of $\min\{{\cal V}, O(\sqrt{T}\log T) \}$, where ${\cal V}$ depends on the distance between the consecutively revealed constraint sets, the shape of constraint sets, dimension of action space and the diameter of the action space. 
When constraint sets have additional structure, ${\cal V}=O(1)$. Compared to the state of the art results, static regret of $O(\sqrt{T})$ and CCV of $O(\sqrt{T}\log T)$, that were universal, the new result on CCV is instance dependent, which is derived by exploiting the geometric properties of the constraint sets.

O(vT) Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization
Rahul Vaze"
School of Technology and Computer Science
Tata Institute of Fundamental Research, Mumbai rahul. vaze@ wazzeggaiie 1 com
Abhishek Sinha
School of Technology and Computer Science Tata Institute of Fundamental Research, Mumbai abhi shek. s wwwnatttttt res
Abstract
The constrained version of the standard online convex optimization (OCO) frame- work, called COCO is considered, where every round, convex cost function and convex constraint function are revealed to the learner after chooses the action for that round. The objective is to simultancously minimize the static regret and cumulative constraint violation (CCV). An algorithm is proposed that guar- antees a static regret of O(VT) and a CCV of min(%, OVVTlog T)), where depends the distance between the consecutively revealed constraint sets, the shape of constraint sets, dimension of action space and the diameter of the action space. When constraint sets have additional structure, y 0(1). Compared the state of the results, static regret of O(VT) and CCV of O(VT log T'), that were universal, the new result on CCV is instance dependent, which is derived by exploiting the geometric properties of the constraint sets.
Introduction
In this paper, we consider the constrained version of the standard online convex optimization (OCO) framework, called constrained OCO or COCO. In COCO, every round i, the online algorithm first chooses an admissible action 2t E 2 C Rdd, and then the adversary chooses a convex loss/cost
function ft x - R and constraint function of the form (x < O, where J, 2 + R is convex function. Since gt's 's are revealed after the action 2, chosen, an online algorithm need not necessarily take feasible actions on each round, and in addition to the static regret
Regret
sup sup Regret,,(x*), where Regret,,("") Σ felar) EM()), UO
(1)
*'E%
t=1
additional metric of interest is the total cumulative constraint violation (CCV) defined as CCV(1.T) Σtn max(g<(x:) 0). Let 2n be the feasible consisting of all admissible tions that satisfy all constraints gi (x) < 0, f [T]. Under the standard assumption that 2' is not
Both authors acknowledge support of the Department of Atomic Energy, Govemment of India, under project no. RTT4001 and Google India Research Award 2023.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

empty (called the feasibility assumption), the goal is to design an online algorithm to simultaneously achieve a small regret (1) with respect to any admissible benchmark x* E 2 and a small CCV.
With constraint sets 9 = (o E 2 ge(x) < 0} being convex for all I, and the assumption T n.9 # 2 implies that sets S, no=_ 9 are convex and are nested, i.e. St S St-1 and
2 E S, for all t. Essentially, set S. 's are sufficient to quantify the CCV.
1.1 Prior Work
Constrained OCO (COCO): (A) Time-invariant constraints: COCO with time-invariant con- straints, i.e. 9r = 9. V [Yuan and Lamperski, 2018, Jenatton et al., 2016, Mahdavi et al., 2012, Yi al., 2021] has been considered extensively, where functions g are assumed be known to the al- gorithm a priori. The algorithm is allowed to take actions that are infeasible at any time to avoid the costly projection step of the vanilla projected OGD algorithm and the main objective was to design an efficient algorithm with a small regret and CCV while avoiding the explicit projection step.
(B) vire-ngrying constraints: The more difficult question is solving COCO problem when the constraint functions, i.e., It ss change arbitrarily with time t. In this setting, all prior work on COCO made the feasibility assumption. One popular algorithm for solving COCO considered Lagrangian function optimization that is updated using the primal and dual variables [Yu et al., 2017, Sun al., 2017, Yi et al., 2023]. Alternatively, [Neely and Yu, 2017] and [Liakopoulos al., 2019] used the drift-plus-penatyy (DPP) framework (Neely, 2010] to solve the COCO, but which needed additional assumption, e.g. the Slater's condition in [Neely and Yu, 2017] and with weaker form of the feasibility assumption (Neely and Yu, 2017]'s.
[Guo et al., 2022] obtained the bounds similar to [Neely and Yu, 2017] but without assuming Slater's s condition. However, the algorithm [Guo et al., 2022] was quite computationally intensive since requires solving convex optimization problem each round. Finally, very recently, the state of the art guarantees on simultaneous bounds regret O(VT) and CCV O(VT log T`) for COCO were derived in [Sinha and Vaze, 2024] with a very simple algorithm that combines the loss function at time t and the CCV accrued till time t in a single loss function, and then executes the online gradient descent (OGD) algorithm on the single loss function with an adaptive step-size. Another extension of [Sinha and Vaze, 2024] can be found in [Lekeufack and Jordan, 2025] that considers COCO problem under predictions about fe's 's and gr's ss See Remark 6 for comparison of this work with [Lekeufack and Jordan, 2025]. Please refer Table for a brief summary of the prior results.
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 xt (x) = arg ming fc(z)) that is also allowed to change its actions over time. However, in this paper, focus our entire attention on the static version. A special case of COCO is the online constraint satisfaction (OCS) problem that does not involve any cost function, i.e., ft = O, Vt, and the only object of interest is minimizing the CCV. The algorithm with state of the art guarantee for COCO [Sinha and Vaze, 2024] was shown to have a CCV of
T) for the OCS.
1.2 Convex Body Chasing Problem
A well-studied problem related to the COCO is the nested convex body chusing (NCBC) problem [Bansal et al., 2018, Argue et al., 2019, Bubeck et al., 2020), where at each round f, convex set Xt C. is revealed such that X C Xt-1, and Xo = x C IRd is a convex, compact, and bounded set. The objective is to choose action H4 E Xt so as to minimize the total movement cost C = Σ ||x, zz- where Io E X is some fixed action. Best known-abe alggo-algsssthms for NCBC [Bansal et al., 2018, Argue et al., 2019, Bubeck al., 2020) choose T, be the centroid or Steiner point of Xx. essentially well inside the newly revealed convex set in order to reduce the future movement cost. With COCO, such approach does not appear useful because of the presence of cost functions fi's 's whose minima could be towards the boundary of convex sets Xt's.
1.3
Limitations of Prior Work
We explicitly show in Lemma 6 that the best known algorithm [Sinha and Vaze, 2024] (in terms of regret and up to log factors for CCV) for solving COCO suffers a CCV of Q(V log T) even for 'simple' problem instances where ft ʃ and St = for all L and d = 1 dimension, for which ideally the CCV should be O1). The same is true for most other algorithms, where the main reason for their large CCV for simple instances is that all these algorithms treat minimizing the CCV as

---

regret minimization problem for functions 9t. What they fail to exploit is the geometry of the underlying nested convex sets S, 's that control the CCV.
1.4 Main open question
In comparison to the above discussed upper bounds, the best known simultaneous lower bound [Sinha and Vaze, 2024] for COCO is PI:TT] ((Vd) and CCV
S2( Sl(vd), where d is the dimension of the action space 2. Without constraints, i.e., 9r = 0 for all t. the lower bound on [Hazan, 2012]. Thus, there is a fundamental gap between the lower and upper
L 11:T = 2( bound for the CCV, and the main open question for COCO is Is it possible simultaneously achieve 2 1:71 ((V)) and CCV ol (T) or [ O(1) for COCO? Even though we do not fully resolve this question, in this paper, we make some meaningful progress by propos- ing an algorithm that exploits the geometry of the nested sets S.'s ss and show that it is possible to simultaneously achieve n:77 O(vT) and CCVp.r] case, give a bound on the CCV that depends on the shape of the convex sets S 's while achieving 8 1:211
(1) in certain cases, and for general
= 11:11=
O(VT). In particular, the contributions of this paper are as follows.
1.5 Our Contributions
In this paper, we propose an algorithm (Algorithm 2) that tries to exploit the geometry of the nested convex sets S.'s. s. In particular, Algorithm at time t, first takes an OGD step from the previous action 2t-1 with respect to the most recently revealed loss function fi-1 with appropriate step-size to reach -1, and then projects yt-1 onto the most recently revealed set S to get 2t, the action to be played at time Let Fe be the "projection" hyperplane passing through 2i that is perpendicular to Tt 1t-1. For Algorithm 2, we derive the following guarantees.
* The regret of the Algorithm 2 is O(vT).
The CCV for the Algorithm takes the following form
When sets S 's are structured, e.g. are spheres, or axis parallel cuboids/regular poly-
gons, CCV is O(1).
For the special case of d = 2, when projection hyperplanes Ft's progressively make increasing angles with respect to the first projection hyperplane Fi, the CCV is O(1). - For general S 's the CCV is upper bounded by a quantity y that is a function of the distance between the consecutive sets S, and S for all the shape of S,'s, dimension d and the diameter D. Since y depends on the shape of S, s, there is no universal bound V and the derived bound is instance dependent.
As pointed out above, for general S,'s, there is no universal bound the CCV of Al- gorithm 2. Thus, we propose an algorithm Switch that combines Algorithm and the algorithm from [Sinha and Vaze, 2024] to provide a regret bound of O(VT) and a CCV that is minimum of and O( log T). Thus, Switch provides a best of two worlds CCV guarantee, which is small if the sets S,'s are 'nice", while in the worst case it is at most O(VT log T).
For the OCS problem, where ft = 0, t we show that the CCV of Algorithm 2 is 0(1) compared to the CCV of O(VTlog T) [Sinha and Vaze, 2024].
2 COCO Problem
On round f, the online policy first chooses an admissible action I, E 2' C Rdd and then the adversary chooses a convex cost function ft L + R and a constraint of the form (x) S 0, where St . + IR is a convex function. Once the action 2; has been chosen, we let f((zz; and full function 9r or the set (z (x) S 0} to be revealed, as standard in the literature. We now state the standard assumptions made in the literature while studying the COCO problem [Guo et al., 2022, Yi al., 2021, Neely and Yu, 2017, Sinha and Vaze, 2024].
Assumption (Convexity) V. C Rd is the admissible set that is closed, convex and has a finite Fuclidean diameter D. The cost function Jt: : L. is and the constraint function gr. : L + R are forvex for all > 1.
3

---

Reference
Regret
CCV
Complexity per round
[Neely and Yu, 2017], 7],
((vT)
O(VT)
Conv-OPT, Slater's condition
[Liakopoulos al., 2019]
O(vT)
((VT)
Conv-OPT, Slater's condition
[Guo et al., 2022]
((vT)
O(T?)
Conv-OPT
[Yi et al., 2023]
((T
O(T1-8/2)
Conv-OPT
[Sinha and Vaze, 2024]
((VT)
log T)
Projection
This paper
((vT)
O,min(Y,vTTogTT)
Projection
Table 1: Summary of the results on COCO for arbitrary time-varying convex constraints and convex cost functions. In the above table, 0 S 3 S 1 an adjustable parameter. Conv-OPT refers to solving a constrained convex optimization problem on each round. Projection refers to the Euclidean projection operation on the convex set 2. The CCV bound for this paper is stated in terms of y which can be (11) depends the shape of convex sets S,'s.
Assumption 2 (Lipschitzness) All cost functions (fe)221 and the constraint functions {gt 1221 are G-Lipschitz, ie., for any n, y E Y, we have (f(()r) f+(y)l S G||ær ull, (ge(x)) - (v) S G|| yll, VI 2 1.
Assumption 3 (Feasibilityy With G, fx E 2: :.(x)) S 0}. we assume that 2* = n 9 + Ø. Any action x² E x² is defined to be feasible.
The feasibility assumption distinguishes the cost functions from the constraint functions and is com- mon across all previous literature COCO [Guo al.. 2022, Neely and Yu, 2017, Yu and Necly, 2016, Yuan and Lamperski, 2018, Yi et al., 2023, Liakopoulos et al., 2019, Sinha and Vaze, 2024].
For any real number 2, we define (z)+ = max(0, 2). Since 's are revealed after the action is chosen, any online policy need not necessarily take feasible actions on each round. Thus in addition to the static² regret defined below
Regret
sup sup (A.T e*
n.77 (2*", Regret (2r((
Σ ((x))) Σ 1(x')
(2)
where an additional obvious metric of interest is the total cumulative constraint violation (CCV) defined as CCVp E9=1(9
Under the standard assumption (Assumption 3) that 2*
is not empty, the goal is to design an online policy to simultaneously achieve small regret with x² 2" and a small CCV.
For simplicity, we define set
S: = =
where S, is as defined Assumption All G''s are convex and consequently, all S, s are convex and are nested, i.c. S, C S.-1. Moreover, because of Assumption 3, each S, is non-empty and particular 2* S, for all After action H, has been chosen, set S, controls the constraint violation, which can be used to write an upper bound on the CCV [1:2] follows.
Definition For a convex set X and a point x & Xs dist(x, x) = mingex ||x vll-
With G being the common Lipschitz constants for ge 's the constraint violation at time t,
T
( < Gdist(r,, St), and CCV (C S G
dist(ar, St).
(4)
3 Algorithm from Sinha and Vaze [2024]
The best known algorithm (Algorithm 1) to solve COCO Sinha and Vaze [2024] (in terms of regret and up to log factors for CCV) was shown to have the following guarantee.
2 The static-nes ness refers to the tixed benchmark using only action x" throughout the horizon of length T'

---

Algorithm Online Algorithm from Sinha and Vaze [2024]
I: Input: Sequence of convex cost functions {ft]== and constraint functions {gr [go)==1 G
common Lipschitz constant, T = Horizon length, D = Euclidean diameter of the admissible set 2 (-) = Euclidean projection oracle on the set 2
2: Let 3 = (2GD)
1, = 2/T (x) = exp(Ax) 1. 3: Initialization: Set 2 CCV(
4: For t fort=1:1 1:
5: Play Zt: observe ft, St. incur a cost of (zz) and constraint violation of (gi (2+))
6: f 3, Dt + - maxx(0,00)) gt).
7:
CCV(L) CCV(L 1) Dr (mte.
8:
Compute V,- (xee where f(()) V(((x) + (CCC((())))))) t 1.
9:
Fe+1 P x (x) m/ V.), where
1}: 1
/2D
10: EndFor
Theorem [Sinha and Vaze [2024]] Algorithm I's pegret = O(vT) and CCV = O(y O(yTlog when f 9t are convex.
We next show that in fact the analysis of Sinha and Vaze [2024] is tight for the CCV even when d = 1 and fz( fxr) and gx(x) g(x) for all t. With finite diameter D and the fact that any xx E 2 belongs to all nested convex bodies S 's, when = 1, one expects that the CCV for any algorithm in this case will be (D). However, as show next, Algorithm I does not effectively make use of geometric constraints imposed by nested convex bodies Se's.
Lemma Even when d 1 and f((x) f(x and ge(x) g(x) for all t, for Algorithm 1, its CCV1: (VVT(VTTV) log T).
1, and let 2 [1, a].a > 2. Morcover, let f((x) f(x) and (x(x) = g(x) for all t. Let f(x) = cx² for some (large) >> 0 and g(r) be such that G = {o g(x) S 0} S [a/2, a] and let [V((x)] < 1 for all æ.
Proof: Input: Consider
Let < x1 < a/2. Note that CtV(t) (defined in Algorithm 1) is a non-decreasing function, and -c For f(x) cx ff(z) 2 for all æ >> 1. Thus, using Algorithm I's definition, it follows that for all / S 6", It < a/2, since the derivative of dominates the derivative of & (CCCV()))g()) until then.
let t" be the earliest time t such that & (CCCV(t))V
Since (xx exp(Ax) with A 1 and by definition [V((x) < for all x, thus, we have 2VT
that by time t*, CCV [1:e]] = (o(vlloggT Therefore, CCV LogTTlogT)
Essentially, Algorithm 1 is treating minimizing the CCV problem as regret minimization for function 9 similar to function f and this leads to its CCV of (o T). For any given input instance with
= 1, an alternate algorithm that chooses its actions following online gradient descent (OGD) projected on to the most recently revealed feasible set S, achieves ((VT) regret (irrespective of the starting action æ1) and O(D) CCV (since any x² E S2 for all t). We extend this intuition in the next section, and present an algorithm that exploits the geometry of the nested convex sets Sy for any d.
4 New Algorithm for solving COCO
In this section, we present simple algorithm (Algorithm 2) for solving COCO. Algorithm 2 is essentially an online projected gradient algorithm (OGD), which first takes an OGD step from the previous action Fz-1 with respect to the most recently revealed loss function fr- with appropriate step-size which is then projected onto S.-2 to reach It-1, and then projects yt-1 onto the most recently revealed set S, to get Ty, the action to be played time t. (3).
Remark 1 Step 6 of Algoritium 2 might appear unnecessary, however, its useful proving Theorem 12.
Since Algorithm 2 is essentially an online projected gradient algorithm, similar to the classical result on OGD, next, we show that the regret of Algorithm 2 is O(vT).
5

---

Algorithm 2 Online Algorithm for COCO
1: Input: Sequence of convex cost functions {f+)== and constraint functions {gr ] G common Lipschitz constant, dimension of the admissible set 2x step size ne Gvl D
Fuclidean diameter of the admissible set 2., Pxx (.) Fuclidean projection on the set 2.
2: Initialization: Set #1 E L arbitrarily, CCV(O) 0.
3: For t 1=
4: Play 3t; observe ft, St. incur cost of (xxe and constraint violation of (g. (x+))
5: Set St as defined in (3)
6:
V/ = S. (xg 7oe f(()))
7:
2+++1 Ss (31)
8: EndFor
Lemma The Regretu:r for Algorithm is O(VT).
Extension of Lemma when ft's are strongly convex which results in Regret = (llog for Algorithm follows standard arguments Hazan [2012] and omitted.
Let H be the action played by Algorithm 2. Then by definition, 2, E St-1- Moreover, from (4), the constraint violation at time t, (t) & Gdist( 22, St). The next action ø[+1 chosen by Algorithm 2 belongs to Sy, however, it obtained by first taking an OGD step from Fe to reach yr and then projects yt onto Sy. Since ft are arbitrary, the OGD step could be towards any direction, and thus, there is no direct relationship between 7141 and xy. Informally, (x1, 22,,.. FT) is not a connected curve with any useful property. Thus, we take recourse in upper bounding the CCV via upper bounding the total movement cost M (defined below) between nested convex sets using projections.
The real challenge is to bound the total CCV for Algorithm 2.
The total constraint violation for Algorithm 2 is L
CCV S <G>
Σ dist(r,, S, SS)
(a)
S
G
Σ |,,, - byll (b) GM,, 7=1
(5)
where in (a) be is the projection of x, onto S₁, i.c. b = Is and in (b) Mr = Et=r || - b, defined to be the total movement cost on the instance , The object of interest is MT.
Bounding the Total Movement Cost My for Algorithm 2
We start by considering structured problem instances where CCV of Algorithm 2 is 0(1), i.e.. independent T.
Lemma 8 alll nested convex bodies S₁
2 2 ... ST spheres then M, S 8/ D 0(1).
Lemma If all nested convex bodies S 2 S₂ 2 ... 2 Sy are cuboids/regular polygons that are axis parallel each other. then M1 - d D 0()..
Interestingly, input instance where Sy's are axis scis-parallel cuboids has been used to derive the only known lower bound for COCO of Regret (.r7 O(vd) and CCV = O(vd) [Sinha and Vaze, 2024].
Remark 2 Lemma 8 and are first results of its kind in COCO, where even for nicely structured instances the previous best known guarantee is CCV 1:21 D(VT log T') [Sinha and Vaze, 2024] or CCV cCV =
O(VT) [Ferreira and Soares, 2025].
Next, we show that similar ((1) CCV guarantee can be obtained for Algorithm 2 with less structured input, however, only when d = 2.
5.1 Special case of d
In this section, we show that if d = 2 (all convex sets S,'s i lie in plane) and the projections satisfy a monotonicity property depending on the problem instance, then we can bound the total CCV for Algorithm 2 independent of the time horizon T and consequently getting O(1) CCV.

---

(m)(c))
X
Fi
5
22
g
S2
h
S
W
Figure 2: Figure representing the
cone Cw, (ct) that contains the con- vex hull of m, and S, with unit vec- tor Wt..
Figure I: Definition of Pt's.
Definition 10 Recall from the desinition of Algorithm yt Ps. ( Te (((x)) and Tr+1
Ps (yi). Let the hyperplane perpendicular to line segment (ye, Tt+11 passing through z(+1 be Ft. Without loss of generality, we let ys & S₁, since otherwise the projection is trivial. Essentially Fe is the projection hyperplane at time t. Let Ht,"" denote the positive half plane corresponding to Ft,
i.e., H," {z x² (ye- It- 1) 2 0}. Refer to Fig. 1. Let the angle between F1 and Fe be Oz-
Definition 11
The instance S 22 2 ... 2 ST is defined to be monotonic if S 0g S IT.
Theorem 12 For d when the instance is monotonic, CCV = O for Algorithm 2.
Theorem 12 shows that CCV of Algorithm 2 is independent of T as long as the instance is monotonic
when d = 2. It worth noting that even under the monotonicity assumption it is non-trivial to upper bound the CCV since the successive angles made by Ft's with Fi can increase arbitrarily slowly, making it difficult to control the total CCV. The proof derived by using basic convex geometry results from Manselli and Pucci [1991] in combination with exploiting the definition of Algorithm 2 and the monotonicity condition.
Finally, in the next subsection, we upper bound Mr, and consequently the CCV for Algorithm 2, when the input has no structure other than S, s being nested.
5.2 General Guarantee CCV
In this subsection, we give general bound on My of Algorithm for any sequence nested convex bodies which depends the geometry of the nested convex bodies (instance dependent). To state the result we need the following preliminaries.
Following (5), b, Ps, (I:) where x, E 0S,-1. where as is the boundary of convex set S, Without loss of generality, x, & Se since otherwise the distance || - bell = 0. Let m, be the mid-point of He and bt, i.e. m tetb
Definition 13 Let the convex hull of m. U St be Cr. Let we be unit vector such that there exists e. > O such that the cone
-w? T (=-me)
Cu,, (c+) x ERT
[[ mm)ll 2 2aj
contains C. Since S, convex, such Wi, C, > 0 exist. For example, w, for which > O since m. & Sr. See Fig. for a pictorial representation.
E, is one such choice
Let C arg maxe, Cue (ct), ot c" =min ct, where by definition, c* 1.
max Crr and w arg max ct Moreover, let
Essentially, 2 ccos-t(c) ) is the angle width of E, with respect wi, i.e. each element of E, makes an angle at most cos 1o()) with wi-
Remark Note that ot only function of the distance || bell and the shape of S, 's in particular, the maximum width of S, along the directions perpendicular to vector 2t by V which
7

---

can be at most the diameter D. oj decreases (increasing the "width" " of cone Owr (ct) as || bell decreases, but small ||, - bell also implies small violation at time from (5).
Remark 4 c² is instance dependent algorithm dependent? For notational simplicity, we have defined Ct using xe (Algorithm 2 specific quantity) and its projection by on St- However, since xte and It-1 have no useful relation between them, can be any arbitrary point on the boundary of St-1, and ee in effect defined with respect to arbitrary 24 E S making it an instance- dependet quantity.
Lemma 14 MT for Algorithm 2 most 2Va(d-1) ( D, where Va is the (d- 1)-dimensional Va-1
Lebesgue measure of the unit sphere dimensions.
Proof Idea Projecting 24 E aS,- onto Se to get b, = s.,( the diameter of Sy is at most diameter of S.-1 - ||=, bell, however, only along the direction b, Hy. Since the shape of S, is arbitrary, as a result, the diameter of St need not be smaller than the diameter of S along any pre-specified direction, which was the main idea used to derive Lemma 8. Thus, prove Lemma 14 we relate the distance ||2 - with the decrease in mean width of a convex body, that is defined as the expected width of the convex body along all the directions that are chosen uniformly randomly (formal definition is provided in Definition 34).
Note that Va/Va-1 = O(1/vd). Thus, from Lemma 14 we get the following main result of the paper for Algorithm 2 combining Lemma 7 and Lemma 14.
Theorem 15 Algorithum 2 has Regret O(VT), and CCV = -vv
Theorem is an instance dependent result for the CCV, compared the prior universal guarantees of Ö(VT) on the CCV. In particular, it exploits the geometric structure the nested convex sets S and derives an upper bound on the CCV that only depends on the 'shape' of S,'s 's via ct. Moreover, e* is only dimension (d) dependent quantity (independent of T) as long as the minimum distance between consecutive constraint sets is not function of I, since the diameter D is constant, whereas all existing algorithms will suffer from CCV of (i(ST(())))) even in this case.
Remark One pertinent question at this time is: What is e* and why should the CCV a problem instance necessarily depend on it? c* corresponds the minimum angle width (via) of the problem instance, the angular width of the 'smallest' cone containing the newly revealed constraint sets. Angle width essentially depends on the width of the convex sets in directions perpendicular to the direction of projection, and controls the total CCV, since successive corvex constraint sets are nested (lie inside each other), the smaller the angle width smaller is the room that an algorithm has to violate the constraints in future steps. Angle width also depends on the distance between I; and St and is potentially large when d(x,, St) small and the diameter along the direction perpendicular to xt. by is large.
e is a fundamental natural object that inherently captures the geometric difficulty in bounding the CCV. The core contribution of this paper is to formalize this by bringing in the novel concept of connecting the reduction of average width of the convex constraint set to the total constraint violation, that entails non-trivial convex analysis. e is in fact small (e.g. lotal CCV is ((VT)) for problem instance then that problem instance does not have enough geometric features to extract via projections. To cover for such instances, we propose the Switch algorithm next to cap the CCV by Ö(VT).
6 Algorithm Switch
Theorem 15 provides an instance dependent bound on the CCV, that is a function of c². If c* is small, CCV can be larger than O(vT log T), the CCV guarantee of Algorithm [Sinha and Vaze, 2024]. Thus, next, we marry the two algorithms, Algorithm 1 and Algorithm 2, in Algorithm 3 to provide a best of both results as follows.
Theorem 16 Switch (Algorithm 3) has regret Regret min {o (v)()))* D). O(VTlogT))
O(VT), while CCV
8

---

Algorithm Switch
1: Input: Sequence of convex cost functions
{ft]=1 and constraint functions {gt G common Lipschitz constant, d dimension of the admissible set L, D = Fuclidean diameter of the admissible set 2, P 5 (+) = Euclidean projection operator on the set V.
2: Initialization: Set 2 E 2 arbitrarily, CCV(0) = O.
3: For ::
4: If CCV( log
5: Follow Algorithm 2 and update
CCV(t) CCV(( 1) max 0}.
6: Else
7: Follow Algorithm with resetting CCV(L- 100 =0
8: Endif
9: EndFor
Algorithm Switch should be understood as the best of two worlds algorithm, where the two worlds correspond to one having nice convex sets S,'s that have CCV independent of T or o(vT) for Algorithm 2, while in the other, CCV of Algorithm 2 is large on its own, and the overall CCV is controlled by discontinuing the use of Algorithm 2 once its CCV reaches vT log I' and switching Algorithm thereafter that has universal guarantee of (V log T) its CCV.
OCS Problem
In [Sinha and Vaze, 2024], special case of COCO, called the OCS problem, was introduced where
Jt for all Essentially, with OCS, only constraint satisfaction is the objective. In [Sinha and Vaze, 2024], Algorithm was shown have CCV of O(VT log T). Next, we show that Algorithm 2 has CCV of O(1) for the OCS, remarkable improvement.
Theorem 17 For solving OCS, Algorithm 2 has [C O (d = 0(1)
As discussed in [Sinha and Vaze, 2024], there are important applications of OCS, and it is important find tight bounds on its CCV. Theorem 17 achieves this by showing that CCV of O(1) can be achieved, where the constant depends only on the dimension of the action space and the diameter. This is fundamental improvement compared to the CCV bound of O(vT log T) from [Sinha and Vaze, 2024]. Theorem 17 derived by using the connection between the curve obtained by successive projections on nested convex sets and self-expanded curves (Definition 20) and then using a classical result on self-expanded curves from [Manselli and Pucci, 1991].
8 Experimental Results
In this section, compare the performance of Algorithm and Algorithm 2 experimentally. We start by simulating the performance of Algorithm and Algorithm 2 on the input that was used to prove Lemma Fig. 3 numerically verifies the claim of Lemma 6 that the CCV of Algorithm is Q(VT log T), while the CCV of Algorithm 2 remains constant.
8.1 Synthetic Data
Next, we consider a more reasonable data setup to compare the performance of Algorithm I and Algorithm 2, where with d = 10. we let fe(x) = ||æ aill1. and is d-dimensional vector that coordinate-wise uniformly distributed between [-1, 1] and is independent across t. Similarly, we consider (z) max(O, /
0.1) where w, is d-dimensional vector that also is coordinate- wise uniformly distributed between [-1, 1] and is independent across L. This choice ensures that æ 0 is feasible for all constraints, i.e., Assumption 3 is satisfied. In Figs. 4a and 4b, we plot the regret and CCV, respectively, for Algorithm and Algorithm 2, and see that Algorithm outperforms Algorithm in both the regret and the CCV.

---

Variation of CCV(T)
150.00 VT (T')
Constraint Violation
100.00
VT (T)
50.00
t"
Algorithm
Algorithm
0.00
125
t*
250
375
500
Rounds (T)
Figure 3: Regret and CCV comparison for input described in Lemma 6.
Variation Regret(T))
Variation of CCV(T)
200
Algorithm 1
Algorithm 2
150
40
Regret
CCV
100
50
Algorithm
Algorithm 2
0
0
500
1,000
1,500
2,000
100
200
300
400
500
Rounds (!')
Rounds (?)
(a) Regret comparison of Algorithm and Algo-
(b) CCV comparison of Algorithm and Algo- rithm
rithm 2
Conclusions
One fundamental open question for COCO is: whether it is possible to simultaneously achieve ( O(VT) and CCV[1.T) = T( or CCV(L.T) = 0(1.. In this paper, we have made substantial progress towards answering this question by proposing geometric properties of the nested convex sets S,'s that effectively control the CCV, The state of the art algorithms [Sinha and Vaze, 2024, Ferreira and Soares, 2025] achieve a CCV of (((T) for very simple instances shown in Lemma 6, and conceptually different algorithms needed achieve CCV of o(VT). We propose one such algorithm and show that when the nested convex constraint sets are well structured, achieving a CCV of O(1) is possible without losing out on O(vT) regret guarantee. We also derived bound on the CCV for general problem instances, that is as a function of the shape of nested convex constraint sets and the distance between them, and the diameter.
algorithm that exploits the
In the absence of good lower bounds, the open question remains unresolved in general, however, this paper significantly improves the conceptual understanding of COCO problem by demonstrating that good algorithms need to exploit the geometry of the nested convex constraint sets.
References
Jianjun Yuan and Andrew Lamperski. Online convex optimization for cumulative constraints. Ad- vances Neural Information Processing Systems, 31, 2018
Rodolphe Jenatton, Jim Huang, and Cédric Archambeau. Adaptive algorithms for online convex optimization with torg-term constraints, In International Conference on Machine Learning, pages
10

---

PMLR, 2016.
Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: online convex op- timization 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 cumu- lative constraint violation analysis for online convex optimization with long term constraints. In International Conference Machine Learning, pages 11998-12008. PMLR, 2021.
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 algorithmss for adversarial contextual bandit. In International Conference on Machine Learning, pages 3280-3288 3288. PMLR, 2017.
Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Yiguang Hong, Tianyou Chai, and Karl H Johans- son. Distributed online convex optimization with adversarial constraints: Reduced cumulative constraint violation bounds under slater's s condition. arXiv preprint arXiv:2306.00 2023.
Michael J Neely and Hao Yu. Online convex optimization with time-varying constraints. arXiv preprint wwXiv:1702.04788. 2017.
Nikolaos Liakopoulos, Apostolos Destounis, Georgios Paschos, Thrasyvoulos Spyropoulos, and Panayotis Mertikopoulos. Cautious regret minimization: Online optimization with long-term budget constraints. In International Conference on Machine Learning, pages 3944-3952. PMLR, 2019.
Michael Neely. Stochastic network optimization with application to communication and queueing systems. Synthesis Lectures on Communication Networks, 311:
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 in Neural Information Processing Systems, 35:36426-36439, 2022.
Abhishek Sinha and Rahul Vaze. Optimal algorithms for online convex optimization with adversarial constraints. In The Thirth-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: /wwp//pppeeeeeeee/////// wet.e/eweeeeeeeeeeeeeeeeeeeeeeee wwwet//orrmmiddTeeeeee iin EwMMBBy.
Ricardo N. Ferreira and Cláudia Soares. Optimal bounds for adversarial constrained online convex optimization, 2025. URL https:
abs 2503. 13366.
Jordan Lekeufack and Michael Jordan. An optimistic algorithm for online convex optimization with adversarial constraints, 2025. http::/:://aaxe http:////w.w....oo//////a/////// wrg/ /tt.a/////22200........ 68060.
Tianyi Chen and Georgios B Giannakis. Bandit convex optimization for scalable and dynamic iot management. IEEE Internet of Things Journal, 6(1):1776- 2018.
Xuanyu Cao and KJ Ray Liu, Online convex optimization with time-varying constraints and bandit feedback. IEEE Transactions on automatic control, 64(7):2665-2680) 2018.
Rahul Vaze. On dynamic regret and constraint violations in 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. 21223999NN000522112222222228
Qingsong Liu, Wenfei Wu, Longbo Huang, and Zhixuan Fang. Simultaneously achieving sublin- ear regret and constraint violations for online convex optimization with time-varying constraints. ACM SIGMETRICS Performance Evaluation Review, 493 2022..
Nikhil Bansal, Martin Böhm, Marek Eliás, Grigorios Koumoutsos, and Seeun William Umboh. Nested convex bodies are chaseable. In Proceedings of the TwentyNimth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1253-1260. SIAM, 2018.

---

C.J. Argue, Sébastien Bubeck, Michael B Cohen, Anupam Gupta, and Yin Tat Lee. A hearly-lineat bound for chasing nested convex bodies. In Proceedings of the Thirtieth Annual ACM-SIAN Symposium on Discrete Algorithms, pages 117-122. SIAM, 2019.
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 Algorithums, pages 1496-1508 SIAM, 2020.
Elad Hazan. The convex optimization approach to regret minimization. Optimization for machine learning, page 287, 2012.
Hao Yu and Michael Neely. A low complexity algorithm with o(vT) regret and o(1) con- straint violations for online convex optimization with long term constraints. arXiv preprint 120.00064..0218.. 2016.
Paolo Manselli and Carlo Pucci. Maximum length of steepest descent curves for quasi-convex functions. Geometriae Dedicata, 38(2):211-227, 1991.
Harold Gordon Eggleston. Convexity, 1966.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We provide complete theorem statements and proofs of all claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in 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 other settings.
fine to include aspirational goals as motivation as long as 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: Our result crucially makes use of feasibility assumption (Assumption 3) which is universally used in the COCO literature. In the absence of good lower bounds, the problem considered the paper question remains open full generality.
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 are encouraged to create separate "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 au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech- speech-to-text system might not be used reliably provide closed captions for online lectures because 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 ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should 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?
13

---

Answer: [Yes]
Justification:
We clearly state the assumptions under which our theoretical results hold.
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 referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple-
mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a 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 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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a 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 all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new 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 a way to re- produce 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 au- thors are welcome to 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [NA]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines http:///.....poooeeeeoooooeeiiie
for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines wwwpp/bbcicgiiddeee/eeeeebieieee
for more details.
The authors should provide instructions on data access and preparation, including how to 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 are reproducible, they 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 in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
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?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
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.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of emrrrs is not verified.
15

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative enror rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
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 of compute required for each of the individual experimental runs as well as 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 t make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: This paper deals with fundamental optimization theory and conform with NeurlPS Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in 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 theoretical paper and the authors do not see any immediate direct
societal impact of this paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied 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 an 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 a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
16

---

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 unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a 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 theoretical 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 the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safery 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 is 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
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not 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.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode. apperssithhod.cccmddaaaaeet com/datasets has cu- rated 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 is not available online, the authors 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 documenta- tion provided alongside the assets?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
17

---

Researchers should communicate the details of the dataset/code/mmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was 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. Crowdsourcing and research with human subjects
Question: For crowdsoureing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, 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 the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.M policy hhnps://eeniinsccocommmeeeeee/ss for what should or should not be described.
18

---

10 Comparison with [Lekeufack and Jordan, 2025]
Remark 6 [Lekeufack and Jordan, 2025] consider the COCO problem when predictions about both cost functions ft's and constraint functions 9r 's are available. With predictions, they show that if predictions are perfect, ((1) regret and CCV is achievable, while if the predictions are totally wrong, in the worst case the regret and CCV are at most as bad as the result of [Sinha and Vaze, 2024]. Intermediate range of results is also obtained depending on the quality of prediction. Essen- tially [Lekeufack and Jordan, 2025] use the prediction wrapper over the algorithm of [Sinha and Vaze, 2024] derive their guarantee.
In this paper, however, we are not assuming any predictions, and are solving the COCO problem with the worst case input, similar to all the prior work listed in Table 1. Moreover, the presented algorithm is conceptually different than [Sinha and Vaze, 2024], and for the first time shows that (1) or instance dependent CCV while having O(VT) regret is possible, which is not the case with prior work even for d 1.
Thus, the setting of [Lekeufack and Jordan, 2025] is completely different and not really comparable with our results.
11 Proof of Lemma 7
Proof: From the convexity of ft's for x² satisfying Assumption (3), have
fx1))) fi(x*) V (x, x²).
From the choice of Algorithm 2 for 24+1, we have
|| - x 11 = || 9 (v:) - x 1|?
(o)
< |1 x" x²1??,
|199.- s. (I)- N/c V. f((:)) =011?
|1( - 7p. V (a:) - x" 112
where incqualities (a) and (b) follow since x² S, for all t. Hence
D141 x= |1 < || x= 2 + n/² V ft (z,) 2n V f (Iz)(Ze =²)),
fz (z: x²) | x= 1 || 211
G2.
Summing this over / = 1 to 7, we get
T
T
2
Σ (f((z)) - fe(x*)) <
V St (xt x²),
| x* x+112
-112441
- x=1
T
+
G.
1=1
t=
1
2 +
G2
1/
4T
< O(DGVT),
where the final inequality follows by choosing 7)-
D C
12
Proof of Lemma 8 and Lemma 9.
[Proof of Lemma 8] Recall the definition that v; E 3 S, from (5). Let ||x, - b = r, then since all S,'s are spheres, at least along one of the d-orthogonal canonical basis vectors, diameter(S, (S.) I diameter(S,_. S - Since the diameter along any of the d-axis is D, we get the answer
Proof:
We would like to remark that the proof short and elementary that should be seen strength. Proof: [Proof of Lemma 9] Proof is identical to Lemma 8.
19

---

13 Preliminaries for Bounding the CCV in Theorem 12 and Theorem 17
Let Ki...., Kr be nested (i.e., K1 K2 K3 2 ... 2 Kr) bounded convex subsets of R Definition 18 of E K1, and 0++1 9 Kets (ot). for ,.....
T. Then the curve
a ((011, (02, 0z). (0r-1,
is called the projection curve K1, KT-
We are interested in upper bounding the quantity
T-1
Σ = max
10 0--ll
(6)
t=1
Lemma 19 For projection curve a E S dei'metttterr K2).
To prove the result need the following definition.
Definition 20 A curve - I& is called self-expanded, ifr every where (t) exists, we have
<n((t), 7(u) >20
for all E I with S. t, where <..>> represents the inner product. In words, what this means is point To self expanded, for every E ? for which there exists the tangent line T, the are (sub-curve) (zo, x) is contained in one of the two half-spaces, bounded by the hyperplane through x and orthogonal to
that y starting
For self-expanded curves the following classical result is known.
Theorem 21 Manselli and Pucci [1991] For any self-expanded curve 7 belonging to a closed bounded convex set of Bd with diameter D, its total length most ()d//2
Proof: [Proof of Lemma 19] From Definition 18, the projection curve is
g ( 02), (02, (0T-1:
Let the reverse curve be = {frit= T-2. T where Ti (OT- oT--1) Thus we are reading backwards and calling it r. Note that since o, the projection of o:-1 on Kr, each piece-wise lin- car segment (Ø,, 0t+1) is a straight line and hence differentiable except at the end points. Moreover, since each a is obtained by projecting 0 onto K, and K C K,, have that the projection hy- P Kx (a(-1) ) and is perpendicular to --00-1 separates the two sub curves (2), (o2, ........ (o,- o,)} and {(o,, oz+ 1), (az+1, 0T_2), ..... (OT-1, 0T)).
perplane F, that passes through
Thus, we have that for each segment rr, at each point where it differentiable, the curve .., lies side of the hyperplane that passes through the point and is perpendicular r,+1. Thus, we conclude that curve is self-expanded.
As result, Theorem 21 implies that the length of r most (iam/eiiae)))((KK) and the result follows since the length of r is same as that of which is E.
14 Proof of Theorem 12
Proof:
Recall that 2. and the definition of F, from Definition 10. Let the center be Ps, (2)().) Let lorh be the earliest for which <(F,, Fi)
Initialize 1, s(1) 1, -11) 1.
BeginProceddne Step 1: D:Definition Phase k. Consider
T(k) arg
t.
If there is no such T(x).
20

---

Phase A ends, define Phase A as Empty, s(x+ [(x) +
Else If
(K)()) Fi) = n Exit
Else If
sKk + 1) = (x)
End If
Increment k = n + 1, and Go to Step 1.
EndProcedure
Example 22 To better understand the definition of phases, consider Fig. 5. where the largest t for which the angle between F; and F1 is at most n/4 Thus, r(1) 3, i.e., phase explores till time = 3 and phase ends. The starting hyperplane to consider in phase 2 is s(2) = 3 and given that angle between F3 and and the next hyperplane F4 more than я /4, phase
empty and phase
2 ends by exploring till t = 4. The starting hyperplane to consider in phase 3 is s(3) 4 and the process goes on. The first time such that the angle between F1 and F, is π is = and thus Lorth 6, and the process stops at time t= 6. This also implies that Sa C F1. Since S; 's are nested, for all 6, S, C Fú. Hence the total CCV after 2 Lorth most GD.
The main idea with defining phases, is to partition the whole space into empty and non-empty regions, where in each non-empty region, the starting and ending hyperplanes have an angle to at most x //4, while in an empty phase the starting and ending hyperplanes have an angle of least /4. Thus, get the following simple result.
Lemma 23 For d = 2, there can be at most 4 non-empty and 4 empty phases.
Proof is immediate from the definition of the phases, since any consecutively occurring non-empty and empty phase exhausts an angle of at least π 7/4.
Remark 7 Since we are in dimensions, for all I. Lorth the movement along the hyperplane Fi and thus the resulting constraint violation after time 2 Lorth is at most GD. Thus, in the phase definition above, we have only considered time till torth and we only need upper bound the CCV till time tot
21

---

Projection
F
F
r(1)
=3
45% line
F3
OGD direction
S
--------
Constraint violation
y/3
y2
X3
XA
Sz
y1
2
Y4
Empty phase
F
π
X1
4
S
X5
Fs
F6 = - F
orth = 6 X7
Xg
Figure 5: Figure corresponding Example 22.
We next define the following required quantities.
Definition 24 With respect to the quantities defined for Algorithm 2, let for a non-emply phase k
T
Tiax (1s)
max
1lve - cll and t" (x)) = arg <(5)<())(>)
max
||ve c//-
<(N)<(
(k) is the time index belonging to phase & for which yt is the farthest.
Definition 25 non-emply phase consists of time slots F(x) = [r(n - 1), (x=) and the angle (F, Fiz) < x/4 for all 11, E [K).. Using Definition 24, partition T (k) as T F(K) g- (k) g (R), where g g-(x) = (,) 1) and T g+(m)+))))) (1*(s) 2,
Thus, (K) and T (x + 1) have one common time slot.
Definition 26 [Definition of 2((s) for
--(k).. Let 2- Tr(())+ For (R(K) (K) + 1, define (k) inductively as follows. ze(x) is the pre-image z441 (K) on F... such that the projection of 2, (x) on F. is ze+1 (1)1(K).
Definition 27 [Definition of (K) for E I (k)]. For E (K), define 2x()) inductively as follows. ze (x)) is the projection of 211((5 on F.-1.
See Fig. 6 for visual illustration of t' (k) and (K).
22

---

Projection
F
F2
45 line
F3
OGD direction
S
(*11=
=3
S2
Constraint violation
Z2
Zz
24
X4
y3
2/2
New Violations
X3
XA
S3
Y1
X2
Y4
Empty phase
F
π
X1
4
S4
X5
F5
F6
F
orth X7
Xg
Figure 6: Illustration of definition of (x) for E T (k). this example, for phase 1, (1) since the distance of y/3 from is the farthest for phase that consists of time slots (1) = (2.3).
Hence (1)+1((11 = 44. E (1))(((1 + 1, ze (1) are such Ze+1 (1) is projection 21) onto F..
The main idea behind defining ze (x)'s is as follows. For each non-empty phase, we will construct a projection curve (Definition 18) using points 2 such that the length of the projection curve upper bounds the CCV of Algorithm 2 (shown in Lemma 33), and then use Lemma 19 to upper bound the length of the projection curve.
Definition |Definition of St for a non-empty phuse k:] Sto41 S
For
(-(K)( (k) + 1, St is the convex hull of US) Fig.
Fort E g+(k), St = S, See
Lemma For a non-emply phase k, for any I E [K),, 1/41 Sq iee. they are nested.
Definition 30 For non-empty phase, x(k) (((--)) n Het Tiny where Tix) has been defined in Definition 10.
Definition 31 [New Violations for T (x)::1 For non-empty phase s, for t T (Kx)(T(( 1),
let
(x(k) = (1)x(k)) - zz (x)]]
23

---

i U
S
S2 U2U
F1
F2
F3
F4
22
23
U2
S3
U1
Z4
S2
25
X5
X5
S4
Figure 7: Definition S,'s where U, are the extra regions that are added to S, to get St.
Lemma 32 For each non-empty phase K, all 24 2x))ss for F(k) belongs to B(c, V2D), where B(c,r) r) is a ball with radius centered at c. In other words, X(k) S. B(c, V2D).
Proof: Recall that for non-empty phase R. [(k) g- ( We first argue about t e T (k)). By definition, (x)++)+1 = (x)++ and T2' (x)+1 E (p)())- Thus, 2x (x)++1 E Bc, 2DD) Next we argue for t E 9 (x)))*((s) + 1. Recall that the diameter of 2 is D, and the fact that Thus, for any non-empty phase k, the distance from belonging to the phase x is at most D, i.e., (max(() S D. Let the pre-image of (x) (Nr onto Fs(K) (the base hyperplane with respect to which all hyperplanes have an angle of at most T 7/4 in phase x) be p(x) such that projection of p(k) onto Fa(ee) is z (1))1(()) From the definition any non-empty phase, the angle between Fs(x) and for E (R) most π /4. Thus, the distance of ((K) from is at most V2D.
Vr S from Algorithm
the farthest
Consider the 'triangle' I1(x) that is the convex hull of (x) (K) and p(x). Given that the angle between (e)(K) and (x)(k)-1 is at most T 7/4, the argument above implies that 2x(x) E I[xx) for t = (K). For = (K)) - 1, (K) ) Fi-1 is the projection of (x=((k) onto S This implies that the distance of (x) (for (x) 1) from is most
D
cos(a (w)) cos (A))
where dt,, is the angle between F,, and F,z- From the monotonicity of angles 0, (Definition 11), and the definition non-empty phase, we have that (g,((x) + (e())) S a/4 and (r))((K)) 2 0, (x)) 2 0. Next, we appeal to the identity
cos(A + B) I cos(A) cos(B) (B)
where A+ B T/4, to claim that 2x(k) E (Tx)) for 1 (n)) 1.
Iteratively using this argument while invoking the identity (7) gives the result that for any t E
T (R)), we have that (x)) belongs to [K)) Since II(x) S B(c, V2D), we have the claim for all
I E 3- (K).
By definition (x)) for E ++()) belong S S Sr. Thus, their distance from c most D.

---

Lemma 33 For each non-empry phase K, and for t E (K) the violation (x) 2 dist(z1, St), where di St) the original violation.
Proof: By construction of any non-empty phase for I. E [()) both a (x) and (x)) belong to Fi-1. Moreover, by construction, the distance of 2z(k) from c at least as much as the distance of Jy from c. Thus, using the monotonicity property of angles 0, (Definition 11) we get the result. See Fig. for a visual illustration.
For each non-empty phase K, by definition, the curve defined by sequence (x(K) for t E (K) projection curve (Definition 18) on sets Sī(k) (note that (K))sss 's are nested from Lemma 29). Moreover, for all E T (n:,, set (Kk C x(16) which is a bounded convex set. Thus, for d = 2 from Lemma 19 the length of curve 2(k) {<z( (1)))()))))))))
Σ (E))
(k( < 2diameter(x
(8)
By definition, the number of non-empty phases till time forh is most 4. Moreover, in each non-
empty phase (I)) S Bc, v2D) from Lemma 32.
Thus, from (8), we have that
Σ
Σ
v(())= S
Σ
diameter(x(1s))
Phase K. non-empty
1E (x))
Phase 6 is non-empty
< 8 diameter ((c, V2D) 1 ((D).
(9)
Using Lemma 33, we get
Σ
dist(r,, 5
(10)
Phase K. non-cmpty
EE (rc)
For any empty phase, the constraint violation the length of line segment (Ix, Ps, (Ix)) (Algorithm 2) crossing it is a straight line whose length is at most O(D). Moreover, the total number of empty phases (Lemma 23) is a constant. Thus, the length of the curve (zz, Ps, (2:)) for Algorithm corresponding to all empty phases is at O()).
Recall from (4) that the CCV is at most G times dist(rr;,)) St). Thus, from (10) we get that the total violation incurred by Algorithm 2 corresponding to non-empty phases is at most O(GD), while corresponding empty phases is OGGD). Finally, accounting for the very first violation dist(z1, S1) < D and the fact that the CCV after time 2 forth (Remark 7) is at most GD, we get that the total constraint violation CCVp. for Algorithm is most O
15 Proof of Theorem 14
Proof:
We need the following preliminaries.
Definition 34 Let K be non-empty convex bounded set in Rdd Let u be unit vector, and ly line through the origin parallel to Let Kú, be the orthogonal projection of K onto ly with length [Ku]. The mean width of K is defined as
1 1 { [Kuldu,
W(K)
(11)
Va Jst
where 8 is the unit sphere in d dimensions and Va its (d - 1)-dimensional Lebesgue measure.
The following immediate.
0 < ((K < diameter(K)
(12)
Lemma 35 Eggleston [1966] For d =
Perimeter(K)
(KK)
π
25

---

Cw1 (cD)
W/
S
u
C
C
m
b
X1
Wt
H u
H
Figure 8: Figure representing the cone Cav, (ct) that contains the convex hull of m and S. with respect to the unit vector wy is unit vector perpendicular to Ha an hyperplane that is a supporting hyperplane C, at m. such that &2 n Hy } and u' (xz m²) 2 0
Lemma 35 implies that W(K) * ((K) ( even if K₁ U U22 = and K K₂ o.
Recall from (5) that Dy E - and by is the projection of xe onto S,, and m, is the mid-point of at and b,, Le. my = zc+b. Moreover, the convex sets S are nested, i.e., S1 2 S2 2 ... 2 Sr. To prove Theorem 14 we will bound the rate which ((S) (Definition 34) decreases function of the length ||+, - -bll--
From Definition 13, recall that Ee is the convex hull of m, U Sp. We also need define 6,-- as the convex hull of x, S,. Since S, S 6G and 6, S S.-1 (since S,- is convex and I; S,-1). 1), have
W(S)) W(S W())) W(
(13)
Definition 36 A, W(G)) ((
The main ingredient of the proof is the following Lemma that bounds A, whose proof is provided after completing the proof of Theorem 14.
Lemma 37
A. s VV- || bell (d - 1) (c))
where of has been defined in Definition 13.
Recalling that c* = min; of from Definition 13, and combining Lemma 37 with (12) and (13), we get that
Σ 2 b 2Va -1)
(2)
diameter(S1),
Va-1
since S 2 S2 ... 2 Sr. Recalling that diameter(Si) S D, Theorem 14 follows.
Proof: [Proof of Lemma 37]
Let H. be the hyperplane perpendicular to vector Let 2y be the set of unit vectors such that hyperplanes H,, are supporting hyperplanes to '6 at point m, such that E6 n H = {m,} and
n" (x,, m 0. See Fig. 8 for reference.
Since b, is projection of 24 onto St, and m, is the mid-point æ4 b,, for u E Vo the hyperplane H', containing and parallel to H, is supporting hyperplane for C,
26

---

Thus, using the definition of K2 from (11),
110e bell
(xe
m.)
A Va J (106,al
du,
(14)
2V
Wo
me|l
since ||ate me/1 || ||25 bul1/ b2
Recall the definition of Cw; (cf) from Definition 13 which implies that the convex hull m, and St, 6, is contained in Cw; (ct). Next, consider 4/ the set of unit vectors such that hyperplanes
Hu are supporting hyperplanes to Owt (ct) point me such that u² uxx mi) 2 0. By definition
6, C Cwz (ct) ) it follows that 2/ %6.
Thus, from (14)
20 - bell
/
u². (Ie - me)
A
S
du
(15)
2Va
| mell
1/1
Recalling the definition of wł (Definition 13), vector u E 2/ can be written as
u = uny + v - 1
where uII w[; |u and since %/1
0 x= / (1F"(( = u² tn S c.
Let 11 = {u_ |u.1 = u, w = 0}. Let 1 be the (n di- Lebesgue measure of I1.
easy to verify that du 2d-2(1 22)-11/2 and and hence from (15)
A. |1+e bell ("t x -1-3 11/2 / (Au V1 Xwx))² (It mm))
| - m.l dui. (16)
Va
Note that Jav. iidur = O. Thus,
||2, - -blll (wo) (x2 mm) (ot 2d - x2)-112 -22 da / dui,
A
dd2 91
2Va
100 mell
(0)
| - bell (wi) (xi - m²) ( Xd-2 dd,
V4-1
J
2V/
1| 1
||0; bell
Va-
2V 1) (ct))=12
|10e - bell
V 2Va(d - 1) (ct)a,
(17)
where (a) follows since Sy, rup = Va-1 by definition, (b) follows since
(w) " (z me)
> of from
1
Definition 13.
16 Proof of Theorem 16
Proof: Since CCV(t) is a monotone non-decreasing function, let Imin be the largest time until which Algorithm 2 is followed by Switch. The regret guarantee is easy prove. From Theorem 15, regret until time tmin at most O (m Moreover, starting from time fmin till T, from Theorem 5, the regret of Algorithm 1 most (VVT I. Thus, the overall regret for Switch is at most O(VT).
For the CCV, with Switch, until time Imin. CCV(mmin) S VTlog time (mins Switch starts to Algorithm which has the following appealing property from (8) Sinha and Vaze [2024] that for
27

---

any 2 Emin where at time Emin Algorithm was started to be used with resetting (tv(t = 0. For any min
(CCCV(t)) + Regret, -
Σ
(#'(CC((T))) + V - tmin.
(18)
where B = =(GGD) -1 = 11 = 2V7 ((x) = exp(Xx) - 1, and X = 2V7 We trivially have
Regret, 2 2D
Dr
2
L. Hence, from (18), we have that for any À 2 and any 2 fmin
2-
CCV S 4GD In(2In(21111)) + 2T)
Since as argued before, with Switch, CCV(lmin) S lo T, we get that CCV p:21 x OlyTlog T).
17 Proof of Theorem 17
Clearly, with ft = 0 for all t, with Algorithm 2, = It and the successive xy's are such that Tt-1 Ss, (z)). Thus, essentially, the curve z (æ1, 22), (Ig, (3), .... (2T-1, (T) formed by
Algorithm 2 for OCS is a projection curve (Definition 18) on S1 2....,2 2 Sr and the result follows from Lemma 19 and the fact that diameter (S:) S D.
28


Reviews:
[{"review_id": "uJHiQXDJO0", "reviewer": "Reviewer_ZKq2", "summary": "This paper addresses the constrained online convex optimization (COCO) setting, where at each round a learner chooses an action before observing a convex cost and a convex constraint. The goal is to simultaneously minimize regret with respect to the best static feasible action and the cumulative constraint violation (CCV). The manuscript introduces a new instance-dependent analysis exploiting geometric properties of the sequence of nested constraint sets. The authors propose an OGD-based algorithm that adapts projections based on set geometry, yielding a static regret of $O(\\sqrt{T})$ and an instance-dependent bound $\\mathscr{V}$ for CCV, which in some structured cases becomes $O(1)$, improving over prior universal guarantees of $O(\\sqrt{T} \\log T)$. The work also introduces a 'Switch' variant that combines the new method with a prior baseline to guarantee the best of instance-dependent and universal CCV bounds.", "questions": "1. In a practical setting, how can one approximate or bound $c^{\\star}$ online? Could a data-driven surrogate guide the switch criterion instead of the hard threshold $\\sqrt{T\\log T}$\n\n2. Can Algorithm 2 be adapted for constraints where projections are expensive (e.g., via linearization or mirror maps)?\n\n3. Is the exponential dependence on d unavoidable? Could random sub-space projections or curvature conditions tame it?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The theoretical results are sound under stated assumptions. The authors explicitly show both regret and CCV bounds, with clear theorem statements and intertwined proofs. The use of geometric analysis to arrive at instance-dependent bounds is a substantial addition to the literature.  The main novelty of this paper lies in leveraging the geometric structure of the feasible sets to derive sharper and sometimes constant CCV bounds. The manuscript introduces the angle width/cone width characterization ($c^*$) for constraint violation, a connection that is, as discussed, unique and previously unaddressed. The 'Switch' algorithm (Algorithm 3) is also a thoughtful way to blend instance-dependent improvements with robust worst-case guarantees.\n\n2. The instance-dependent analysis reveals that previous universal CCV bounds can be loose for \"easy\" cases, and exploiting geometry allows for cases where constraint violations are essentially constant. For example, Theorem 15 encapsulates this by relating CCV to the angular structure of the nested sets. This insight could influence both theory and practice in online optimization and expand the toolkit of algorithm developers for constrained scenarios.\n\n3. The theoretical exposition is generally clear, and assumptions are well stated. Table 1 provides a helpful summary of how this work situates among existing methods. Figures 1 and 2 help to clarify the geometric arguments that underpin the main proofs. The paper contains sufficient concrete definitions and explanations to allow a reader to follow.\n\nWeaknesses:\n\n1. Assumption 3 (perfect intersection of all constraint sets) is strong and not always met in practice. The theory indicates CCV can blow up with d; the manuscript lacks discussion or lower bounds clarifying whether this dependence is intrinsic.\n\n2. The paper is lack of empirical validation. I think a small-scale simulation comparing CCV on toy structured vs. unstructured instances could demonstrate the sharpness of the geometric gains.\n\n3. The central quantity controlling the instance-dependent CCV bounds is $c^{\\star}$. However, the paper leaves implicit how one might actually estimate or compute this for concrete problem instances.", "was_revised": true, "final_justification": "I have no major concerns about the paper aside from the experimental section. The idea of leveraging the geometric properties of the constraint sets is interesting, though the theoretical contribution is not particularly strong. Overall, I am inclined to give it a bordline accept.", "rebuttal": "We thank the reviewer for appreciating our work. In the following we answer in detail all comments posted as Weaknesses as well as all the posed Questions.\n\n1. Assumption 3 (perfect intersection of all constraint sets) is strong and not always met in practice. \n\n\n$\\textbf{Reply:}$ The reviewer is correct in saying that Assumption 3 is strong, however, all prior work on COCO has assumed it (listed in Table 1) to make meaningful progress. Moreover, this assumption is satisfied in a number of practical settings, e.g., when the constraint functions are given by overparameterized neural networks, which are known to perfectly fit (interpolate) arbitrary data [1][1, Section 4].\n\nEven with Assumption 3, solving the COCO problem (to identify the fundamental tradeoff between regret and CCV) has remained open and has attracted a lot of attention. The main goal of this paper is to make significant \nprogress in solving COCO even though under Assumption 3.\nThe results of this paper open new directions for solving COCO by exploiting the geometry of the problem which all prior work has completely ignored. \nEssentially all of prior work has treated minimizing CCV as a regret minimization problem with respect to $g_t$'s and consequently suffers $O(\\sqrt{T}))$ CCV. What we have shown is that exploiting the geometry of the problem $O(1)$ CCV is possible for structured inputs, while instance dependent bounds on CCV can be obtained otherwise, that can be much smaller than $O(\\sqrt{T}))$\n\n2. The theory indicates CCV can blow up with $d$; the manuscript lacks discussion or lower bounds clarifying whether this dependence is intrinsic.\n\n$\\textbf{Reply:}$ The dependence of CCV on dimensions $d$ is quite interesting. Even for the special case when $f_t=0$ for all $t$, in which case the problem is stated as OCS problem (Section 7) in the paper, the CCV for  Algorithm 2 that is essentially an projection algorithm is $O(d^{d/2})$. Immediate question is: whether this exponential dependence is fundamental to the projection algorithm or not. There is some discussion on this aspect in [Argue et al, 2019] paper where after Theorem 1.3 it is stated that in some joint work of O. Angel, F. Nazarov and S. Bubeck, it is shown that there is a problem instance for which the projection algorithm has a CCV of $\\Omega(c^{d/2})$ for some constant $c>1$. However, this work remains unpublished and even after enquiring with the authors in January of this year, it has not been made available. So at this time it remains a conjecture that exponential dependence of CCV on $d$ is unavoidable. On our own, we have not been able to construct such an input and which remains a highly important open question. \n\n\nIn general, the only lower bound known on COCO problem for all algorithms can be found in [Sinha and Vaze, 2024] that shows that simultaneous regret and CCV are both $\\Omega(\\sqrt{d})$. Thus, CCV is definitely a dimension dependent quantity. For the regret, the lower bound is weak, but in terms of CCV, it is hard to say whether the correct bound is $\\Omega(\\sqrt{d})$ or the upper bound of $O(d^{d/2})$ is tight. \n$\\textbf{We will add this discussion in the revision.}$ \n\n\n\n3. The paper is lack of empirical validation. I think a small-scale simulation comparing CCV on toy structured vs. unstructured instances could demonstrate the sharpness of the geometric gains.\n\n$\\textbf{Reply:}$ We agree with the reviewer and plan to add two numerical studies. First, using the same example of fraud detection of [Sinha and Vaze 2024] and second, that is inspired by the example used to prove Lemma 6, for $d>1$ for which clearly the proposed algorithm can exploit the geometry. Preliminary results show order-wise improvement over prior work as expected. We will include both in the final version.\n\n4. The central quantity controlling the instance-dependent CCV bounds is $c^\\star$. However, the paper leaves implicit how one might actually estimate or compute this for concrete problem instances.\n\n$\\textbf{Reply:}$ It is indeed an excellent point. It is not easy to estimate the quantity $c^\\star$ ahead of time since the input is online. However, at time $t$, once $S_t$ is revealed, $c_t^\\star$ can be estimated in principle by  finding the best unit vector $w_t$ and inner product $c_t$ such that $S_t$ is contained in the cone $C_{w_t}(c_t)$. This optimization can be solved efficiently, since both the cone and $S_t$ are convex, however, there is no obvious direct relation between any simple geometric property (e.g. diameter, etc) of $S_t$ and $c_t^\\star$. As noted in Remark 3, $c_t^\\star$ depends on the distance of $x_{t-1}$ and $S_t$ and the width of $S_t$ in directions perpendicular to $x_{t-1}$ and its projection on $S_t$, which can be used to bound $c_t^\\star$ via  trigonometric relations as a function of $d$.  \n\n\n\n\n\n\n5. In a practical setting, how can one approximate or bound $c^\\star$ online? Could a data-driven surrogate guide the switch criterion instead of the hard threshold.\n\n $\\textbf{Reply:}$ If predictions about $S_t$'s are available, one can certainly do so. Otherwise at time $t$, $c_t^\\star$ can be estimated as discussed in previous  point, which controls the eventual $c^\\star$. However, since the algorithm itself does not depend on this quantity for its execution, it is not necessary to approximate it. It is needed only for understanding the CCV guarantee.\n It is an interesting direction that you have suggested for choosing the switching criterion depending on data-driven surrogate guide, we need to think a bit about it.\n %For the switching criterion we have kept the hard constraint but for most instances the threshold will not be met since the iterates of the algorithm \n\n6. Can Algorithm 2 be adapted for constraints where projections are expensive (e.g., via linearization or mirror maps)?\n\n $\\textbf{Reply:}$ We have thought about this issue. In particular, the obvious choice is to use the Approximately-feasible Projection Oracle of [Garber and Kretzu, 2022; 2023] similar to what was done to obtain a projection free algorithm for COCO in [Projection-Free Online Convex Optimization with Time-Varying Constraints, Garber and Kretzu, 2024]. \n \n However, since [Garber and Kretzu, 2022; 2023] only computes an approximate projection, it does not satisfy  the important property that we need: convex sets revealed after time $t$ should lie on one side of the hyperplane perpendicular to the projection vector at time $t$. This is true by definition for exact projections. Thus, it is not obvious how to extend our algorithm and its guarantee when projections are expensive, but remains an important point for future work.\n \n\n\n7. Is the exponential dependence on $d$ unavoidable? Could random sub-space projections or curvature conditions tame it?\n\n$\\textbf{Reply:}$ For arbitrary input instances, it is conjectured that for our projection algorithm exponential dependence on $d$ is unavoidable. See discussion in Point 2 above from paper of [Argue et al, 2019]. When the input has more structure e.g.  spheres, polygons, already we have results Lemma 8 and 9, which show only polynomial dependence on $d$. Moreover, there is a concept of strong convexity of convex sets [2] that involve the notion of curvature for convex sets for which again results similar to Lemma 8 can be derived. So yes, the curvature conditions can tame CCV.\n\nWe hope our response will clarify all comments of the reviewer and  put this paper in the right perspective while sufficiently bringing out the novel features of the paper together with the significantly improved guarantees over the prior work. In summary, we would like to say that  [Sinha and Vaze 2024]  opened a new door in COCO literature which has already led to flurry of activity in a short time. We are opening another one beyond that and expect it to fuel further progress, and would request the reviewers to encourage it.\n\n[1] Belkin, Mikhail, Daniel Hsu, Siyuan Ma, and Soumik Mandal. ``Reconciling modern machine-learning practice and the classical bias–variance trade-off.\" Proceedings of the National Academy of Sciences 116, no. 32 (2019): 15849-15854.\n\n[2] Jean-Philippe Vial,\nStrong convexity of sets and functions,\nJournal of Mathematical Economics,\nVolume 9, Issues 1–2,\n1982,\nPages 187-205."}, {"review_id": "VwxuzF0fLJ", "reviewer": "Reviewer_9P7u", "summary": "This paper tackles the constrained online convex optimization (COCO) problem, where at each round the learner selects an action before observing both a convex cost and a convex constraint function. The goal is to minimize static regret and cumulative constraint violation (CCV). The authors propose a novel algorithm that exploits the geometry of nested convex sets formed by past constraints. The key result is an algorithm that achieves a regret of $O(\\sqrt{T})$ and an instance-dependent CCV bound $O (\\min \\\\{ \\mathcal {V}, O(\\sqrt{T} \\log T) \\\\})$, with $\\mathcal V$ capturing the geometric complexity of constraint evolution.", "questions": "see weakness", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper introduces a geometry-aware algorithm for constrained online convex optimization (COCO) that achieves a regret of $O(\\sqrt{T})$ and an instance-dependent cumulative constraint violation (CCV) bound of $ O( \\min \\\\{ \\mathcal {V}, O(\\sqrt{T} \\log T) \\\\} )$, which can be as small as $O(1)$ when the constraint sets have additional structure.\n\n2. The proposed algorithm departs from prior methods by not treating constraint violation as a regret minimization problem, and instead explicitly exploits the geometric structure of the nested feasible sets formed by time-varying constraints.\n\nWeaknesses:\n1. Although the proposed algorithm demonstrates better cumulative constraint violation compared to [Sinha and Vaze, 2024], and both methods require projections, there is a fundamental difference in the nature of these projections. In [Sinha and Vaze, 2024], the projection is onto the feasible set $\\mathcal{X}$, which is typically simple and easy to project onto in online learning settings. In contrast, the algorithm proposed in this paper requires projecting onto both $S_t$ and $S_{t-1}$ at each round t, where $S_t = \\bigcap_{\\tau=1}^t G_\\tau = \\bigcap_{\\tau=1}^t \\\\{ x \\in \\mathcal{X}: g_\\tau(x) \\leq 0 \\\\}$. In practice, this projection is significantly more challenging, as the structure of $S_t$ can be quite complex, especially when the constraint functions $g_\\tau(x)$ are nontrivial. Therefore, the comparison in Table 1 may not be entirely fair, as it overlooks the increased computational burden introduced by this more complex projection.\n\n2. Another concern lies in the absence of a detailed comparison with [Lekeufack and Jordan, 2025], which also achieves an interpolation between $O(1)$ and $O(\\sqrt{T} \\log T)$ in terms of cumulative constraint violation. Moreover, due to the use of optimistic gradient techniques, their method can interpolate the regret between $O(1)$ and $O(\\sqrt{T})$, which is in fact better than the regret bounds obtained in the present work. A discussion with [Lekeufack and Jordan, 2025] would strengthen the contribution.", "was_revised": true, "final_justification": "While the computationally expensive projection used in this paper may pose practical challenges, it also opens up an interesting and potentially valuable direction for future research in COCO.", "rebuttal": "We thank the reviewer for appreciating our work. In the following we answer in detail all comments posted as Weaknesses as well as all the posed Questions.\n\n1. Costly and Difficult Projections: \n\n$\\textbf{Reply:}$\nEven after sufficient attention, COCO problem has remained unsolved. Thus, our primary objective is to establish fundamental bounds for COCO without enforcing any complexity constraint. As a natural progression, we will consider the complexity implications of it as well which are important as  correctly pointed out by the reviewer. \nIn this paper, bringing in the novel idea of exploiting the geometry of set $S_t$'s we are able to open a new direction for solving COCO, which we believe will be instrumental in (future) complete characterization of best possible simultaneous regret and CCV. \n\nWe give a $\\textbf{three part}$ answer to reviewer's comment on projections as follows.\n\n$\\textbf{Comparison with prior work}$\nAs correctly pointed out by the reviewer, at each time $t$, the algorithm takes (two) projections on two convex  sets $S_{t-2}$ and $S_{t-1}$, which can be costly, however, are always convex programs.\nCompared to this, prior work either takes a projection on $S_1$ always or solves a full-convex optimization problem involving $g_t$ (or $S_t$) at each time $t$. Projections on convex sets are efficiently solvable for all convex sets, however, have simpler complexity guarantees if the sets are `nice'. To claim that projection onto $S_t$ is necessarily more complicated than projection onto $S_1$ is not \nalways accurate, since it depends on the structure of $S_1$ and $S_t$. It might be the case that $S_1$ is more geometrically challenging.  \nTheoretically, at each progressing step of time $t$, i.e. going from $S_{t-1}$ to $S_t$  we are potentially adding one extra constraint to the convex problem corresponding to $g_{t}$. Thus, complexity wise, the problem at each time belongs to the same complexity class, though practically it might be more costly. \n\n$\\textbf{Need for projection}$ \nOne pertinent important question is:  is it necessary for an algorithm to choose a point belonging to $S_{t-1}$ at time $t$? (In particular, our algorithm does so by using projection). We indeed believe so for the following reason. All prior work takes a regret minimization view over constraints $g_t$'s to minimize the CCV. However, it ignores Assumption 3, and because of the small step-sizes of OGD step (which are dictated by regret minimization for OCO) of $O(1/\\sqrt{T})$ or $O(1/\\sqrt{t})$, it does not necessarily choose an action belonging to $S_{t-1}$ and ends up achieving a CCV of $O(\\sqrt{T})$. \nIn light of Assumption 3, to make CCV small, an algorithm has to make ``rapid\" progress towards the final set $S_T$ which can be done via choosing a point belonging to $S_{t-1}$ at time $t$. \nAs we show, our algorithm which chooses action after projecting them onto to the most recently revealed sets $S_t$'s leads to CCV independent of $T$ for structured inputs which was not possible in prior work even for $d=1$ (see Lemma 1).\n\n$\\textbf{Can approximate projections work}$\nAnother thing we have considered is: can Algorithm 2 be adapted when only linear optimization oracle is available similar to [Garber and Kretzu, 2022; 2023, 2024]. In this case, the obvious choice is to use the  Approximately-feasible Projection Oracle of [Garber and Kretzu, 2022; 2023] similar to what was done to obtain a projection free algorithm for COCO in [Projection-Free Online Convex Optimization with Time-Varying Constraints, Garber and Kretzu, 2024]. \n \n However, since [Garber and Kretzu, 2022; 2023] only computes an approximate projection, it does not satisfy  the important property that we need: convex sets revealed after time $t$ should lie on one side of the hyperplane perpendicular to the projection vector at time $t$. Thus, it is not obvious how to extend our algorithm and its guarantee when projections are expensive.\n\n\n2.$\\textbf{Comparison with [Lekeufack and Jordan, 2025]}$: $\\textbf{Reply:}$ [Lekeufack and Jordan, 2025] consider the COCO problem when $\\textbf{predictions}$ about both cost functions $f_t$'s and constraint functions $g_t$'s are available. With predictions, they show that if predictions are perfect, O(1) regret and CCV is achievable, while if the predictions are totally wrong, in the worst case the regret and CCV are at most as bad as the result of [Sinha and Vaze, 2024]. Intermediate range of results is also obtained depending on the quality of prediction. Essentially [Lekeufack and Jordan, 2025] use the prediction wrapper over the algorithm of [Sinha and Vaze, 2024] to derive their guarantee.\n\nIn this paper, however, we are not assuming $\\textbf{any predictions}$, and are solving the COCO problem with the worst case input, similar to $\\textbf{all the prior work}$ listed in Table 1. Moreover, the presented algorithm is conceptually different than  [Sinha and Vaze, 2024], and  for the first time  shows that $O(1)$ or instance dependent CCV while having $O(\\sqrt{T})$ regret is possible, which is not the case with prior work even for $d=1$. \n\nThus, the setting of [Lekeufack and Jordan, 2025] is completely different and not really comparable with our results. To avoid confusion, we will add a short description of [Lekeufack and Jordan, 2025] and contrast with our setting.\n\n\nWe hope our response will clearly put this paper in the right perspective and sufficiently bring out the novel features of the paper together with the significantly improved guarantees over the prior work. In summary, we would like to say that  [Sinha and Vaze 2024]  opened a new door in COCO literature which has already led to flurry of activity in a short time. We are opening another one beyond that and expect it to fuel further progress, and would request the reviewers to encourage it."}, {"review_id": "xEtUohS8qO", "reviewer": "Reviewer_Vy7L", "summary": "This paper studies the constrained online convex optimization problem, where both cost and constraint functions can vary over time. The authors identify that prior state-of-the-art algorithms yield pessimistic, universal bounds on cumulative constraint violation because they fail to exploit the underlying geometry of the shrinking feasible sets. The primary contribution is a novel algorithm that achieves an instance-dependent constraint violation bound while maintaining optimal regret. In contrast to previous methods that treat constraints as part of a surrogate loss function, the proposed algorithm handles them geometrically via projections, enabling it to achieve constant $O(1)$ violation in many well-structured scenarios.", "questions": "1. Could you provide more intuition on the types of problem instances that lead to favorable (large) versus unfavorable (small) values of $c^\\star$?\n\n2. The paper would be enhanced by an empirical evaluation to showcase the practical advantages of the proposed approach.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper makes a significant contribution by showing that $O(1)$ constraint violation is achievable in many scenarios, a large improvement over prior $O(\\sqrt{T})$ results, while still maintaining optimal regret.\n- While online gradient descent and projections are standard tools, the insight to abandon the surrogate-loss approach for constraints in favor of a purely geometric, projection-based method is novel and powerful. The analysis, which connects the cumulative constraint violation to the geometric properties of nested convex bodies is a non-trivial technical contribution.\n\nWeaknesses:\n- The parameter $c^\\star$ is defined as an instance-dependent quantity that depends on the geometry of the entire sequence of constraint sets. It is not clear how one could estimate or know $c^\\star$ in advance, making the bound difficult to use for predicting performance on a new problem. The paper lacks an empirical evaluation or discussion on what values of $c^\\star$ might arise in practice, which leaves a gap between the theoretical result and its practical utility.", "was_revised": true, "final_justification": "The discussion on favorable instances is insightful. I will maintain the current score.", "rebuttal": "We thank the reviewer for appreciating our work. In the following we answer in detail all comments posted as Weaknesses as well as all the posed Questions.\n\n1. The parameter $c^\\star$ is defined as an instance-dependent quantity that depends on the geometry of the entire sequence of constraint sets. It is not clear how one could estimate or know \n in advance, making the bound difficult to use for predicting performance on a new problem. \n \n $\\textbf{Reply:}$ It is indeed an excellent point. It is not easy to estimate the quantity $c^\\star$ ahead of time since the input is online. However, at time $t$, once $S_t$ is revealed, $c_t^\\star$ can be estimated in principle by  finding the best unit vector $w_t$ and inner product $c_t$ such that $S_t$ is contained in the cone $C_{w_t}(c_t)$. This optimization can be solved efficiently, since both the cone and $S_t$ are convex, however, there is no obvious direct relation between any simple geometric property (e.g. diameter, etc) of $S_t$ and $c_t^\\star$. As noted in Remark 3, $c_t^\\star$ depends on the distance of $x_{t-1}$ and $S_t$ and the width of $S_t$ in directions perpendicular to $x_{t-1}$ and its projection on $S_t$, which can be used to bound $c_t^\\star$ via  trigonometric relations as a function of $d$.  \n\n2. Could you provide more intuition on the types of problem instances that lead to favourable (large) versus unfavourable (small) values of $c^\\star$\n?\n\n$\\textbf{Reply:}$ The favourable instances when $c_t^\\star$ (which control $c^\\star$) is large is when the diameter of the body in the direction perpendicular to the direction of projection is small. Informally, at time $t$, if the new set $S_t$ appears narrow from the point $x_t$ from which the projection is being taken, then $c_t^\\star$ is large, since in sufficiently many directions, the diameter is reducing going from $S_{t-1}$ to $S_t$. Intuitively, this helps in bounding the CCV since there is less room in future to accrue constraint violation.\n\nActually something more interesting is true.\nFor the OCS problem (Section 7) where $f_t=0$ for all $t$,   $c^\\star> \\frac{1}{\\sqrt{d}}$ for any problem instance (sets $S_t$'s), which essentially reflects in the result of CCV of $O(d^{d/2})$ in Theorem 17.\nThus, $c^\\star$ captures the main geometric essence of any problem instance, but is not sufficient to bound CCV for the COCO problem because of the presence of loss functions $f_t$'s whose derivatives can be pointing in any arbitrary direction. \n\n3. The paper would be enhanced by an empirical evaluation to showcase the practical advantages of the proposed approach.\n\n $\\textbf{Reply:}$\n We agree with the reviewer and plan to add two numerical studies. First, we will use the same example of fraud detection of [Sinha and Vaze 2024] and second that is inspired by the example used to prove Lemma 6, for $d>1$ for which clearly the proposed algorithm can exploit the geometry. We will include both in the final version.\n\nIn summary, we would like to say that  [Sinha and Vaze 2024]  opened a new door in COCO literature which has already led to flurry of activity in a short time. We are opening another one beyond that and expect it to fuel further progress, and would request the reviewers to encourage it."}, {"review_id": "Hw4mBEjYgv", "reviewer": "Reviewer_EkuZ", "summary": "In this paper, they provide an algorithm for Constrained Online Convex Optimization (COCO) that achieves $O(\\sqrt{T})$ static regret and $\\min ( \\mathcal{V} , O(\\sqrt{T} \\log T))$cumulative constraint violation (CCV).\n$\\mathcal{V}$ is a problem dependent quantity that characterizes the difficulty of the problem.\nThey show that in certain cases $\\mathcal{V} = O(1)$.\n\nThe algorithm is a variant of the well-known Online Gradient Descent algorithm, which is much simpler than previous algorithms in the literature solving COCO. It also outperforms competitors for certain outputs, while being comparable in the worst case.", "questions": "- It seems that $c^*$ does not completely characterize the difficulty of the problem instance. \nThere are instances where Algorithm 2 achieves CCV worse than $O(\\sqrt{T} \\log T)$, but Algorithm 1 achieves $O(\\sqrt{T} \\log T)$. This is the reason you need the Switch algorithm. Can you explain this?\n\n- The cases for which you show that $V = O(1)$ seem very specific. Is this the true or these are cases that come up often in theory/applications?\n\n- Is Table 1 complete? For example, it seems that the work of Liakopoulos et al. is missing.\n\n- Has the COCO problem been explored in the natural bandit setting? If so, does your algorithm extend to this setting?\n\nAlso, feel free to comment on any of the weeknesses.", "limitations": "- The proposed algorithm is better than previous algorithms only in very specific cases.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- They provide formal proofs for all their claims.\n- The illustrations are very helpful for the reader and shed light on the involved math.\n- The proposed algorithm (Algorithm 2) is straightforward. Although it is a twisted version of the well-known OGD, it remains interesting. I find line 6 of Algorithm 2 particularly interesting. This idea might be useful for other settings as well.\n\nWeaknesses:\n- (Is $c*$ the whole story?) It seems that $c^*$ does not completely characterize the difficulty of the problem instance. \nThere are instances where Algorithm 2 achieves CCV worse than $O(\\sqrt{T} \\log T)$, but Algorithm 1 achieves $O(\\sqrt{T} \\log T)$. This is the reason you need the Switch algorithm.\n- I think the write-up can be significantly improved. e.g. line 17: remove \"function\", lines 25-27: poorly written, line 183: (3), lines 186-187: poorly written,  line 244: $C_{w_t}(c_t)$ is a set not a function. Some statements are a bit vague, e.g. Remark 4: \"[...]$x_t$ and $x_{t-1}$ have no useful relation between them [...]\". Also, I think the Lemmas and Theorems should be written in a more formal way, clearly stating the assumptions and the result. \n- In Algorithm 1, I think you don't need $V$ in line 8. It is always equal to 1.\n- You prove Lemma 6 only for one algorithm. I think you should include the proof for other algorithms as well. You can add it in the appendix.\n- The cases for which $\\mathcal{V} = O(1)$ are very specific. For example, in Theorem 2, d=2 and the instance is monotonic.\n- It would be great to include some applications and experiments of COCO. You can also compare your algorithm with previous algorithms in the literature in terms of regret, CCV, runtime per iteration.", "was_revised": true, "final_justification": "The authors addressed all of my questions and are willing to update their paper accordingly.", "rebuttal": "We thank the reviewer for appreciating our work. In the following we answer in detail all comments posted as Weaknesses as well as all the posed Questions.\n\n1. You prove Lemma 6 only for one algorithm. I think you should include the proof for other algorithms as well. You can add it in the appendix. \n\n$\\textbf{Reply:}$ Similar example works and we will add the details.\n\n\n2. It would be great to include some applications and experiments of COCO. You can also compare your algorithm with previous algorithms in the literature in terms of regret, CCV, runtime per iteration.\n\n $\\textbf{Reply:}$\n We agree with the reviewer and plan to add two numerical studies. One is using the same example of fraud detection of [Sinha and Vaze 2024] and other that is inspired by the example used to prove Lemma 6, for $d>1$ for which clearly the proposed algorithm can exploit the geometry. We will include both in the final version. We will compare the performance and the complexity of our new algorithm and previously best known ones.\n\n\n\n\n3. It seems that $c^\\star$ does not completely characterize the difficulty of the problem instance. There are instances where Algorithm 2 achieves CCV worse than $O(\\sqrt{T\\log T})$, but Algorithm 1 achieves  $O(\\sqrt{T\\log T})$. This is the reason you need the Switch algorithm. Can you explain this?\n\n$\\textbf{Reply:}$  $c^\\star$ captures the main geometric essence of the problem instance involving $S_t$'s, but is not sufficient for giving a CCV guarantee for COCO, because of the presence of loss functions $f_t$'s whose derivatives can be pointing in any arbitrary direction. \n\nTo see this, consider the OCS problem (Section 7), where $f_t=0$ for all $t$ where only $S_t$'s matter,  and $c^\\star> \\frac{1}{\\sqrt{d}}$ for any problem instance (sets $S_t$'s), which essentially reflects in the result of CCV of $O(d^{d/2})$ in Theorem 17. Thus, geometrically $c^\\star$ is sufficient but the presence of $f_t$'s and OGD step of Algorithm 2 makes the job of bounding CCV challenging for COCO.\n\n\nGiven that both $f_t$'s and $S_t$'s are arbitrary, we cannot theoretically upper bound $c^\\star$ with a constant always, and use Switch to cap the CCV. \n%For the COCO problem, in presence of $f_t\\ne 0$, the favourable instances when $c^\\star$ is large is when the diameter of the body in the direction perpendicular to the direction of projection is small. Informally, at time $t$, if the new set $S_t$ appears narrow from the point $x_t$ from which the projection is being taken, then $c_t^\\star$ is large, since for sufficiently many directions, the diameter is reducing going from $S_{t-1}$ to $S_t$, which is intuitive.\nIn practice, however, we believe that Algorithm 2 will have CCV of  $O(d^{d/2})$ and the threshold to switch in Algorithm 3 will not be ever reached for large $T$. The reason is Theorem 17 for the OCS problem, where $f_t=0$ for all $t$, and CCV is $O(d^{d/2})$. Even when $f_t\\ne 0$ as in COCO, given that the step size of Algorithm 2 is $O(1/\\sqrt{T})$ most often the deviation of the trajectories of Algorithm $2$ for the OCS problem and COCO problem will be minimal and will result in similar CCV's. In particular, let $x_t^{coco}$ and $x_t^{ocs}$ be the actions taken by Algorithm 2 for the COCO and OCS problem, respectively. Then, using the triangle inequality and the small step-size of OGD, most often\n$$ CCV = \\sum_{t}dist(x_t^{coco}, S_t) \\approx \\sum_{t}dist(x_t^{ocs}, S_t) = O(d^{d/2}).$$\n\nOf course one can create bad inputs for which this is not the case.\n\n\n\n\n\n4. The cases for which you show that ${\\cal V}=O(1)$ \n seem very specific. Is this the true or these are cases that come up often in theory/applications?\n \n $\\textbf{Reply:}$ The special case of spheres used to prove Lemma 8 effectively models the case when $g_t$'s are strongly convex. Generalization of spherical convex sets is strongly convex sets [1] that capture the curvature for convex sets, and are characterized by the size of spherical balls contained in the convex set.  Result of Lemma 8 can be extended for strongly convex sets also.  \n Similarly, Lemma 9 applies to polygons/polytopes which arise when the constraint set is an intersection of fixed number of hyperplanes (quite common in practice and called box constraints) and where at each subsequent time, constraints corresponding to some fixed number of hyperplanes are tightened.\n So yes, the studied special cases are indeed found in theory/applications.\n\n\n \n5. Is Table 1 complete? For example, it seems that the work of Liakopoulos et al. is missing.\n\n$\\textbf{Reply:}$ We apologize  for this inadvertent error. The work of Liakopoulos et al. is mentioned in prior work but somehow got commented out of  Table 1. We will place it back\nsuitably.\n\n6. Has the COCO problem been explored in the natural bandit setting? If so, does your algorithm extend to this setting?\n\n$\\textbf{Reply:}$ By natural bandit setting, we are assuming that you mean the setting where once the action $x_t$ is chosen only $f_t(x_t)$ and $g_t(x_t)$ are revealed. There are several papers on bandit setting for the COCO problem [2-4] with inferior guarantees compared to [Sinha and Vaze, 2024]. In fact, the results of [Sinha and Vaze, 2024] can be easily extended following the Bandit results for the OCO problem, since [Sinha and Vaze, 2024]'s algorithm combines  $f_t(x_t)$ and $g_t(x_t)$ and applies an OGD algorithm for the OCO problem. Our algorithm, however, as stated needs \nto know the full set $S_{t}$ since it needs to take a projection onto it. But $\\textbf{our guarantees will hold}$ with a minimal requirement of an oracle that can provide a single projection onto $S_t$ from any chosen point.\n\n7. Other points mentioned in $\\textbf{Weaknesses}$ are of more precise notation or typographical/formatting type which will be addressed in the revision.\n\nWe hope our response will clearly put this paper in the right perspective and sufficiently bring out the novel features of the paper together with the significantly improved guarantees over the prior work. In summary, we would like to say that  [Sinha and Vaze 2024]  opened a new door in COCO literature which has already led to flurry of activity in a short time. We are opening another one beyond that and expect it to fuel further progress, and would request the reviewers to encourage it.\n\n[1] Jean-Philippe Vial,\nStrong convexity of sets and functions,\nJournal of Mathematical Economics,\nVolume 9, Issues 1–2,\n1982,\nPages 187-205.\n\n[2] Garber, D., and Kretzu, B. 2024. ``Projection-Free Online\nConvex Optimization with Time-Varying Constraints\", In Proceedings of the 41st International Conference on Machine Learning, 14988–15005\n\n[3] Wang Y.,  Wan Y. Wan, and  L. Zhang, ``Revisiting Projection-Free Online Learning with Time-Varying Constraints, ``The Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25).\n\n[4] Sarkar D, Chakrabartty A, Supantha S, Dey P, Sinha A., `` Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints\", arXiv preprint arXiv:2501.16919. 2025 Jan 28."}]

Author rebuttal:

Meta-review: **(a) Summary of the Paper**

This paper studies the Constrained Online Convex Optimization (COCO) problem. The authors propose a new algorithm that leverages the geometry of the time-varying constraint sets to reduce Cumulative Constraint Violation (CCV). The key finding is that, while maintaining the state-of-the-art $O(\sqrt{T})$ regret, this approach can reduce the CCV to a constant $O(1)$ in many structured scenarios.

**(b) Strengths of the Paper**

* The paper's key highlight is its introduction of a novel geometric perspective to solve the COCO problem.
*  Achieving an $O(1)$ CCV addresses a known weakness where prior theories performed poorly on simple instances.
* The paper's mathematical derivations are rigorous and sound.

**(c) Weaknesses of the Paper**

*  The initial draft was purely theoretical and lacked experiments to validate its theoretical advantages.
* The role of a key theoretical parameter, $c^*$, was initially confusing to the reviewers.
*  The new algorithm may be slow in practice due to computationally complex projections.

**(d) Reasons for Acceptance**

 The primary reasons are:
1. The proposed geometric method is a conceptual innovation.
2. The paper's theoretical results represent significant progress.
3. The rebuttal have addressed reviewers' core concerns.

**(e) Summary of Discussion during Rebuttal**

The rebuttal period was decisive. Reviewers raised three main concerns: (1) confusion over the role of the parameter $c*$; (2) the lack of experiments; and (3) the computational cost of the algorithm.

The authors' response was persuasive:
* They clarified that $c*$ is for analysis only and is not needed to run the algorithm. This resolved the reviewers' biggest concern.
* They committed to adding experiments in the final version.
* They explained that their focus was on theoretical exploration, not immediate computational efficiency.
Decision: Accept (poster)