Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints
Authors: Abhishek Sinha
Rahul Vaze
Venue: NeurIPS 2025 poster ()
Keywords: Online convex optimization
Regret bounds
Learning with constraints
Primary area: general_machine_learning
TL;DR: This paper presents a tunable algorithm for online convex optimization with adversarial constraints that significantly reduces cumulative constraint violation below $O(\sqrt{T})$ by trading it off with regret.

Abstract: We study Online Convex Optimization with adversarial constraints (COCO). At each round a learner selects an action from a convex decision set and then an adversary reveals a convex cost and a convex constraint function. The goal of the learner is to select a sequence of actions to minimize both regret and the cumulative constraint violation (CCV) over a horizon of length $T$. The best-known policy for this problem achieves $O(\sqrt{T})$ regret and $\tilde{O}(\sqrt{T})$ CCV.  In this paper, we improve this by trading off regret to achieve substantially smaller CCV. This trade-off is especially important in safety-critical applications, where satisfying the safety constraints is non-negotiable. Specifically, for any bounded convex cost and constraint functions, we propose an online policy that achieves $\tilde{O}(\sqrt{dT}+ T^\beta)$ regret and $\tilde{O}(dT^{1-\beta})$ CCV, where $d$ is the dimension of the decision set and $\beta \in [0,1]$ is a tunable parameter. We begin with a special case, called the $\textsf{Constrained Expert}$ problem, where the decision set is a probability simplex and the cost and constraint functions are linear. Leveraging a new adaptive small-loss regret bound, we propose a computationally efficient policy for the $\textsf{Constrained Expert}$ problem, that attains $O(\sqrt{T\ln N}+T^{\beta})$ regret and $\tilde{O}(T^{1-\beta} \ln N)$ CCV for $N$ number of experts. The original problem is then reduced to the $\textsf{Constrained Expert}$ problem via a covering argument. Finally, with an additional $M$-smoothness assumption, we propose a computationally efficient first-order policy attaining $O(\sqrt{MT}+T^{\beta})$ regret and $\tilde{O}(MT^{1-\beta})$ CCV.

Beyond Ö(VI) Constraint Violation for Online Convex Optimization with Adversarial Constraints
Abhishek Sinha
Rahul Vaze
School of Technology and Computer Science
Tata Institute of Fundamental Research Mumbai 400005, India
abhishek, sinha@tifr. res. in, rahul. vaze@gmail.com
Abstract
We study Online Convex Optimization with adversarial constraints (COCO). At each round learner selects an action from a convex decision set and then an adversary reveals convex cost and convex constraint function. The goal of the learner is to select a sequence of actions to minimize both regret and the cumulative constraint violation (CCV) over horizon of length T. The best-known policy for this problem achieves O(VT) regret and Ö(VT) CCV. In this paper, we improve this by trading off regret to achieve substantially smaller CCV. This trade-off is especially important in safety-critical applications, where satisfying the safety constraints is non-negotiable. Specifically, for any bounded convex cost and constraint functions, we propose an online policy that achieves D(VdT++ 9 regret and ((d CCV, where d is the dimension of the decision set and 3 [O. 1] is a tunable parameter. We begin with special case, called the CONSTRAINED EXPERT problem, where the decision set is probability simplex and the cost and constraint functions are linear. Leveraging a new adaptive small-loss regret bound, we propose computationally efficient policy for the CONSTRAIE AINED EXPERT problem, that attains O(VT'n In + 7 regret and 0(r In N) CCV for N number of experts. The original problem is then reduced to the CONSTRAINED EXPERT problem via covering argument. Finally, with additional M -ssmoothness assumption, we propose computationally efficient first-order policy attaining OVVMT T regret and Ö(MT1-B) CCV.
Introduction
Online Convex Optimization (OCO) is a standard framework for sequential decision-making under adversarial uncertainty [Hazan, 2022]. At each round s S T, a learner selects an action zy from convex decision set X' with finite diameter D. The environment then reveals convex, Lipschitz continuous cost function ft : X + R. and the learner incurs a cost of f( The objective is to minimize the regret relative to the best fixed action in hindsight. For any comparator action x" X, the regret is defined as: Regret, (a') -
T f((x)) - f(('') [=l
T
The worst-case regret defined be suparex Regret,,(x") is well-known that simple algorithms such as Online Mirror Descent (OMD) attain an O(VT) worst-case regret, which is also minimax optimal [Hazan, 2022].
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Online Convex Optimization with adversarial constraints (COCO) generalizes the standard OCO framework and underpins a variety of emerging applications. including Al safety [Amodei al.. 2016, Sun et al., 2017], fair allocation [Sinha, 2024], online ad markets with budget constraints [Liakopoulos et al., 2019], and multi-task learning [Ruder, 2017, Dekel et al., 2006]. In COCO, on each round 1 & s T, the learner selects an action 2, from convex decision set X' with diameter D. The adversary then reveals two convex functions a cost function ft : X ++ R and a constraint function gt X ~ IR For simplicity, we make the following mild assumption:
Assumption 1 (Bounded Cost and Constraints). The cost and constraint functions functiins are bounded within their domain. In particular, via appropriate translation and scaling, we assume that 0 ft. 9t 1, Vt.
the Appendix for a brief discussion on Assumption The constraint function gr corresponds to constraint of the form hz) s O where we define I=(x)) = max(0, h,.2)))))) Thus, gx(x;) quantifies the penalty incurred by the learner for violating the hard constraint of he (z) S at round t. If an action x' satisfies (xxx) )== = O, Vt, then is feasible throughout the horizon. To measure long-term constraint violation of a policy, we define Cumulative Constraint Violation (CCV) as:
See Section 8.1
CCVT (a(())) [=1
Since the constraint on each round is revealed after the learner selects action - and may be chosen adversarially it is generally impossible for an online policy to satisfy the constraints on every round. Therefore, to ensure the problem is well-posed. one must impose some restrictions on the constraint functions [Mannor al., 2009]. In the COCO literature, the following feasibility assumption is universally made [Sinha and Vaze, 2024, Guo et al., 2022, Neely and Yu, 2017, Yuan and Lamperski, 2018, Yi al., 2021].
We define the feasible set X to be the subset of actions that satisfy the constraints across all rounds:
X = {x E X (e(x) = 0, Vtz 1}.
(3)
Assumption 2 (Feasibility). The feasible set is non-empty, i.e., X # Ø.
The feasibility assumption is not essential for our results. In particular, our algorithmic and analytical techniques naturally extend to the more general setting where the feasible actions are allowed to violate the constraints up to a prescribed budget of By [Sarkar et al., 2025]. Please refer to Appendix 8.6 and Theorem 6 for this generalization.
In the COCO problem, the regret of any policy is computed relative the best feasible action in hindsight, i.e.,
Regret,
sup Regret, xtex
Goal: The standard objective in the COCO problem is to design an online policy that achieves both small regret and small cumulative constraint violation (CCV). In this work, our primary focus on designing a flexible framework that minimizes the CCV to the extent possible, while ensuring that the regret remains sublinear in the horizon length T. This trade-off is particularly important in safety-critica applications, such as autonomous driving, where reducing constraint violation (e.g., safety breaches) takes precedence over minimizing regret (e.g., fuel or battery optimization, commute time reduction).
Background and Our Contribution
Recently, Sinha and Vaze [2024] proposed a computationally efficient first-order policy for the COCO problem, which achieves O(VT) regret and Ö(vT) CCV. They also established the tightness of their results in the high-dimensional regime, where the dimension d of the decision set X' is at least T. is well-known that even in the standard OCO problem. where gt O, Vt, the regret is lower bounded by ((VT). even for d 1 [Hazan, 2022, Theorem 3.2]. Thus the unconditional O(VT) regret guarantee for COCO cannot be improved. However, the question of whether one can achieve CCV substantially smaller than Ö(VT) under additional natural assumptions was left open.
Our main contribution in this paper to affirmatively answer this question. In particular, we show that in the fixed- dinensionl setting where d << T, it is possible to achieve significantly smaller

---

cumulative constraint violation (CCV) while appropriately trading off the regret. Furthermore, when the cost and constraint functions are smooth, we show that computationally efficient online gradient descent-baset policy can achieve improved guarantees. A summary of our results is provided in Table From the table, we also note that with an appropriate choice of the parameters (3 = 1), our proposed policy achieves (In 7' CCV in the special case of ONLINE CONSTRAINT SATISFACTION (OCS) problem when all cost functions are zero and the only goal is to satisfy the constraints [Sinha and Vaze, 2024].
key technical ingredient in our analysis the use of small-loss regret bounds, also known as L' bounds in the online learning literature bounds yield guarantees that improve upon the minimax optimal O(VT) rate for standard regret minimization problem when the fixed comparator incurs small cumulative loss. In Section we extend these classical results by proposing a new adaptive policy for the EXPERT problem that achieves a small-loss regret bound in the general setting where the per-round loss vectors can be potentially unbounded. In Section 3, we consider special case of COCO, called the CONSTRAINED EXPERT problem, where the decision set is an N-dimensional simplex and the cost and constraint functions are linear. In Section 4, we reduce the general COCO problem to the CONSTRAINES EXPERT problem via a covering argument. In Section 5, we give a computationally efficient first- order policy with improved bounds for smooth and convex functions. Due to space constraints, experimental results have been deferred to Section 8.7 in the Appendix.
and Lugosi, 2006, Orabona, 2019]. These
Reference
Regret
CCV
Complexity
Assumptions
Jenatton et al. [2016]
O(1 (11)-))))1-8)
-(1
Projection
FC
Neely and [2017]
((VT)
(vVT/n)
Conv-OPT
Slater condition
Yuan and Lamperski [2018]
O O(Tmax(8,1-1))
O(TI-8/2)
Projection
FC
Yu and Neely [2020]
O(VT)
O(L/n)
Conv-OPT
Slater, FC
Yi et al. [2021]
O ((
O(T(L-1)22
Conv-OPT
FC
Guo et al. [2022]
O(VT)
O
Conv-OPT
Yi et al. [2023]
((THAX(A11-)))
O(T1-813
Conv-OPT
Sinha and Vaze [2024]
O(VT)
Õ(VT)
Projection
Vaze and Sinha [2025]
O(VT)
Instance dependent Ö(T In N) O Ö(MT1-9)
Projection
This paper
O N + +TØ)
O(N)
CONSTR. EXPERT
This paper This paper
Ó(VII 1
O(T")
d-dim. decision set
O(VMT +3
Projection
Smooth
Table 1: Summary of the key results the COCO problem. In the above table, 3 [0. 1] is tunable parameter, y> 0 denotes the Slater's constant, denotes the number of experts, d denotes the dimension the decision set X, . denotes the smoothness constant, and Ó(-) hides polylogarithmic factors in T. CONSTR. EXPERT refers the CONSTRAINED EXPERT problem described in Section 3, Conv-OPT refers solving constrained convex optimization problem on each round, Projection refers to Euclidean projection operation on decision set X,, and FC refers to the Fixed Constraints setting.
Intuition for the results: We now give some intuition for why the Cumulative Constraint Violation (CCV) can expected to be made smaller than the current-best bound of Ö(VT) by crucially utilizing small-loss regret bounds. Consider the Online Constraint Satisfaction (OCS) problem, introduced by Sinha and Vaze [2024], where all cost functions are identically equal zero and the goal is minimize the CCV only. Let the constraint functions (i.e., {gr 's), be non-negative, M Mssmooth and convex.
For solving this problem, we run the Online Gradient Descent policy on the sequence of con- straint functions with an adaptive step size schedule. Specifically, we choose the next action as I++1 = PROIx (2t - n V.), where V. Vgc(2,) and the step sizes are adaptively chosen as 2
2 1. The following small-loss regret bound achieved by this policy for non-negative smooth functions is well-known [Orabona, 2019, Theorem 4.25] (please the

---

statement of Theorem 4 in Section for a quick reference):
T [ - E
g 4D + -DN M M E E1
(5) Now, if we choose the comparator u to be feasible action by setting u x" X", we have (((x') 0, Vt. Thus the regret bound (5) implies CCVT Ei g0(x)) 4D which is constant independent of T. This result is surprising the O O(VT) lower bound for regret holds even for linear functions [Hazan, 2022].
In this paper, generalize this observation by exploring the trade-off between regret and CCV while taking into account both the cost and constraint functions. Our main result roughly says that any (Regrety, CCVr) pair with Regrety 2 @(VT) and Regrety x CCVT = Õ(T) is achievable.
1.1
Prior work
Online convex optimization with constraints has been extensively studied under various modeling assumptions. Table 1 provides a summary of key results in the literature.
In the fixed-constraint setting, where gt g for all f, Yi et al. [2021] proposed a policy that achieves O(1 regret and O(r(1-8)/2) CCV. Under the stronger assumption of Slater's condition, which requires the existence of uniformly strietly feasible action x X' such that gi (x(x)) ) -1 for some constant > and all f, Yu and Neely [2020] showed that the CCV can be reduced to ((1/n) while maintaining ((VT) regret.
The problem becomes significantly more challenging in the presence of time-varying adversarial constraints. Under Slater's condition, Neely and Yu [2017] developed an algorithm achieving O(VT) regret and O OVVT/n) CCV. However, since this condition is quite strong, difficult verify in practice, and leads to vacuous CCV bounds as 17 0", recent works have focused on avoiding this assumption.
Guo et al. [2022] proposed an algorithm that needs to solve separate offline convex optimization problem in each round, achieving O(VT) regret and 0(73/4) CCV. Subsequently, Sinha and Vaze [2024] introduced simpler gradient-based policy that improves the CCV bound to Ö(VT) while still maintaining O(VT) regret. See also Lekeufack and Jordan [2024], Lu et [2025], Supantha and Sinha [2025], Sarkar et al. [2025] for various extensions of their result. More recently, Vaze and Sinha [2025] proposed an algorithm that achieves O(VT) regret and constant CCV for some special classes the constraint sets.
The algorithms proposed in this paper make use of Lipschitz-adaptive small-loss regret bounds. Small-loss regret bounds for the standard regret minimization problem with bounded Lipschitz constants, where the regret scales with the cumulative loss of the benchmark (instead of the time horizon T)), have been well studied Dessa-Bianchi et al., 1997, Auer et al., 2002, Hazan and Kale, 2010]. Mhammedi et al. [2019] propose Lipschitz-ddaptive algorithms in the EXPERT setting. which rely on multiple restart phases and incur additional computational overhead. Similarly, Cesa-Bianche et al. [2007] uses doubling trick to estimate the unknown parameters. Restarting learning algorithms during their course of execution is practically wasteful as it discards past data prior to the restarts. To the best of our knowledge, continuously adaptive, scale-free variants of the small-loss regret bounds the EXPERT setting have not been investigated before in the literature. In the following, we review the EXPERT problem and derive adaptive small-loss regret bound.
2 Preliminaries: Adaptive Small-Loss Regret Bound for the EXPERT Problem
The Prediction with Expert Advice problem, also known as the EXPERT problem in the literature, refers to repeated game where, in each round t 2 1, the learner chooses a probability distribution Pe over a set of N' experts (experts may be identified with the set of actions). After that, the adversary chooses bounded loss vector 4 e [0, 1] where (1) denotes the loss for the eth expert, i é [N]. Consequently, the learner incurs an expected loss of fe(pt) = (4, round 1. The full loss vector 4, is revealed to the learner at the end of round L. The learner's objective is to choose sequence of distributions {pt) 12 to minimize its regret over T rounds. The EXPERT problem the full full-information counterpart of the Multi-armed Bandit (MAB) problem [Bubeck et al., 2012).

---

The Exponential Weights algorithm, also known as Hedge, is well-known solution to the EXPERT problem. The Hedge algorithm selects the tth expert on round & with probability
1-1 Pr (i( = exp (-n 1 (())22 ie [N].
(6)
where 77 > 0 is suitably chosen learning rate and Z is the normalizing constant. Hedge is known to achieve the following small-loss regret bound [Cesa-Bianchi and Lugosi, 2006, Corollary 2.4]:
Regret, = LT LT Li")") < (1)((t)) In +InN,
where LT = ET= (47, Pc) is the learner's cumulative loss, Lr(i") L is the cumulative loss of comparator arm i* [[V]. See also the Squint algorithm proposed by Koolen and Van Erven [2015]. The small-loss bound (7) offers a significant improvement over the standard O(VT) regret bound when the comparator's s loss is small, i.e., Lr(i*) o(T)). While the bound (7) is well-known, it assumes that that all loss values are bounded [Cesa-Bianchi and Lugosi, 2006, Section 2.4]. However, for reasons that will become clear in the sequel, cannot (7) in algorithm, we will need to control the regret when the losses, defined appropriately by the algorithm, are unbounded.
To address this technical challenge. Theorem I presents a small-loss regret bound for the EXPERT problem that generalizes (7) by accommodating potentially unbounded losses. This regret bound is achieved by an adaptive variant of the Hedge policy that employs self-confident variable learning rate. The full pseudocode for this policy is provided in Algorithm in Appendix 8.2.
Theorem Consider the EXPERT problem with N experts. Let the vector l denote the losses of the experts at round 2 1, where 1e(1) 2 O, Vi,t. t. The losses need not be uniformly bounded above for all rounds. Let Gr be an upper bound to [|ll satisfying the the following conditions':
1. The sequence {Gt]e1 monotonically non-decreasing. i.e., G. 2 G1-1. Vtz G, 1.
2. The growth of G2 in consecutive rounds is bounded: max G constant 2 1.
G S y for some known
Then the following adaptive Hedge algorithm, which selects the ith expert with probability (i) exp(-1pbz-1(1)) Vi, with adaptive learning rate Tb. /G-1 regret bound:
Nn achieves the following
Le-++G..1
L Lr(i') s 27V Lr(P) IN Gr
(8)
In the above, L_ EE=-I(P; denotes the algorithm's 's cumulative loss up to round t and Lir) (+-) is the cumulative loss of any comparator expert i" e [N] up to round T.
=
See Appendix 8.3 for proof of Theorem 1.
Remarks: 1. The monotonicity assumption on the sequence (Gr entails no loss of generality, since one always define new sequence of upper bounds G max1grse Gr which is monotonic by construction.
2. The proof of Theorem I is non-trivial because the value of GT is unknown in advance. As result, we cannot simply rescale all losses by GT and directly apply the small-loss bound in (7) to the normalized losses. Instead, we carefully design adaptive learning rate schedule that accounts for the growth of the loss scale and the cumulative loss of the best expert over time.
3
The CONSTRAINED EXPERT problem: Simplex Decision Set, Linear Cost, and Linear Constraint Functions
In this section, we focus on an important special case of the COCO problem, called CONSTRAINED EXPERT problem, where the cost and constraint functions are linear and the decision set is the
Naturally, the ( Gat sequence is causal i.e., G, can be computed only after observing the loss vector 4 round
5

---

N - 1-dimensional simplex AN, i.e.
N x AN PERN
In this problem, each round i, the learner first computes a distribution Pt AN over N experts, and then it samples an expert from the distribution Pt. Choosing expert incurs a cost of ft(1) and a constraint violation of ge(i). Consequently, the learner incurs an expected cost of fp(t) and expected constraint violation of g: (gt.Pa) Pt) on round l². Both the cost vector fz and the constraint vector are revealed to the learner at the end of the round. The feasibility assumption (Assumption 2), specialized to this setting, implies that there exists at least one expert i" [[]] such that ge (t*) 0, vt. The learner's objective is to generate sequence of distributions {pe ) that minimizes both the regret and the cumulative constraint violation (CCV).
(ft.Pt)
3.1 An Online Policy for the CONSTRAINED EXPERT Problem
Let Φ : + R be non-decreasing convex Lyapunov function, to be specified later, and let i" be an uniformly feasible expert with (x()") O, Vt. As stated earlier, the existence of i" is guaranteed by Assumption 2. Let (t) denote the cumulative constraint violation (CCV) to round t, which evolves as follows:
((t) = Q(t 1) (9t.
We now use the regret decomposition framework introduced by Sinha and Vaze [2024] to design an online policy for the CONSTRAINED EXPERT problem. Using the convexity of the Lyapunov function $ (.), we have for any s T: ((((t)))(((C)
('(Q(t))((() -ttltt))----tt---
(a) ('(((I))(:.Pp))
(() (e())),
(10)
where (a) follows from Eqn. (9) and (b) uses the fact that gi = 0, Vt. Adding the term (fr.P.)
f((i") ) to both sides of the inequality, we obtain
((Q(1)) ((Q(1- - 1)) - s (ft + 4' Define the 1hh surrogate cost function fe AN to be the following linear function:
(11)
f.(p) (fi + & ((((())):: p), 1
(12)
Summing up Eqn. (11) for 1 s obtain the following regret decomposition inequality:
- (((())))9((C0)) + Regret, (i*)
)+ s (i"))
(13)
In Eqn. (13), Regret,(("') (f ex.) and Regret, Σtz (fi - ev) correspond to the regret for the original cost functions {fe) and the surrogate cost functions (fi) respectively, with respect to a feasible expert i" E [N].
Algorithm 1 presents our proposed online policy for the CONSTRAINED EXPERT problem. It employs the adaptive Hedge subroutine from Theorem to select the sampling distributions {pt)1a which minimize Regrety (i") appearing on the RHS of Eqn. (13). Observe that the surrogate cost function ft involves the term & (Q(()), which may grow indefinitely with as Q(t) grows. Hence, it is imperative to use the adaptive Hedge algorithm (Algorithm 4) which can handle unbounded loss, in contrast to the standard Hedge algorithm (6), which assumes bounded loss vectors. The following theorem gives upper bound to the regret and CCV achieved by Algorithm 1.
Theorem 2. Consider the Lyapunov function o(x) eλx where X = T- (2ccl N), 10, and B [0, 1] is a tunable parameter. Then, under Assumptions and Algorithm I achieves the following guarantees for the CONSTRAINED EXPERT problem for any feasible expert e [N]:
Regret, (i*) O(VTIN T + In,, CCVr = O(T'~8 In In
In particular, if Ja 0, VL, upon setting 3 = 1, we obtuin CCV,
2To simplify the notations, we use the same symbol for denoting a linear function and its associated coefficient vector.

---

Algorithm 1 Algorithm for the CONSTRAINED EXPERT problem
Input: Number of experts N. Horizon length T, Cost vectors (fr) and Constraint vectors
(9e) Tunable parameter / e [0, 1].
2: Parameter settings: ((x) e^= À (2cn 10.
3: Initialization: Set Q(0) 0, Algorithm's loss Lo Experts' cumulative loss Lo 0, Go
1 + ('(())))
4: for each = do
5: Compute self-confident learning rate
In
7/
(14)
VGL-
L-1+ G
6: Play adaptive Hedge by choosing the ith expert with probability
N (i( exp(-1) (1))/ Σ exp((mml(-1 vie [N].
7: Observe the vectors ft.gt. gt. Incur a cost of (ft,Pr) and constraint violation of (9t. Pt).
8:
Update CCV and Gr:
Q(t) Qt- 1) (9t, G. = 1 (Q((t))
9: Compute the surrogate cost vector: f, = + D' ((((())) (coordinate-wise vector addition)
10: Update the cumulative loss of the algorithm and the cumulative loss of each expert
L Ī + (fe,p)) (((i) L,-1 fc(1). ie [N].
11: end for each
Experimental results, presented in Section 8.7 of the Appendix, qualitatively support the expected variations of Regret and CCV function of the parameter 3.
3.2 Proof of Theorem 2
Define the sequence G2 1 (Q(()) 2 O, where the Lyapunov function ((-) is chosen as specified in the statement of Theorem 2. From the definition of the surrogate costs (Eqn. (12)), it follows that Gę is an upper bound to the maximum component of the surrogate cost vector:
f I|5 (l((
t'(Q()) G., Vt.
Since Qtt) is denreeeernsnnggnn in and the function ((-) is convex, follows that the sequence (Gt) i>1 also -ocrrecea..... Furthermore, from Lemma 2 in the Appendix, we have that max1 G 1.08. Thus all conditions Theorem are fulfilled with y 1.08, and we can use the small-loss regret bound (8) of the adaptive Hedge algorithm for the surrogate cost sequence (ft) Let [N] be uniformly feasible expert which incurs zero constraint violation every round, i.e., gc 0, Vt. The cumulative surrogate cost incurred by expert i" can be upper bounded as:
Gr.
Lr(i")= = (1((') ((()))+((Q(()))(()))) ('(Q(1)) ST
where we have used the fact that |l.fel 1 and (i")") = 0, Vt Hence, using the small-loss regret bound (8), the regret for the surrogate cost functions with respect to any feasible arm i" can be upper bounded as:
Regret(,((")) s T(T + c(1 (Q(T)))
(15)
where have used the fact that max(2y, 7) 10 (say). Using the inequality /
/i VT. x 2 0, y 2 0, and substituting the upper bound from Eqn. (15) into the regret decomposition
7

---

inequality (13), we obtain
((Q(T)) + Regret,(1))
< )(Q(0)) VTINN+ + (IT(( InN
(( In.V
(16)
1. Bounding the CCV: Using the fact that Regretz [T(('')))))) -T, inequality (16) yields
eQQT)) <T+1+v/ThN ev XTe2Q(T) In N + (AcIn ()()) cln..
(17)
(arr11))/((c11) (2cIn N) ensures that AcIn N s 1/2. Using this inequality to bound the coefficient of the penultimate term on the RHS of Eqn. (17) and transposing, we obtain
Since T 2 1, our choice of the parameter À = >
e (Q(1) < max
cv In Ne N clu N
Since the maximum value on the RHS is achieved by at least one term on the right, comparing the LHS with each term the RHS separately and simplifying, obtain the following bound for CCV:
Q(T) (c1 02 In T' c3 In)
(18)
where 01 C22 C2 are universal constants.
2. Bounding the Regret: Transposing the term & (Q(T)) e ^Q(T) to the RHS of Eqn. (16) and using the fact that AcIn N & 1/2 for our chosen parameter X, we obtain
Regret, (i' s 1 TVn
Ne AC()/2
1 (Q() cln..
Using the fact that - hx? s Tb
vb the above inequality implies the following regret bound:
2² XT cluN.
Regret, +lteceTllN
(19)
2
7-(1-) N into Eqns. (19) and Eqn. (18), we obtain the following regret and CCV
Substituting À
bounds:
Regrety = ( ((())))OOOm))))) T + N), CCV Nn N
4 Convex Cost and Constraint functions
In this section, we generalize our previous results to the general convex setting. In particular, we make the following assumption.
Assumption 3 (Convexity and Lipschitzness). All cost and constraint functions are convex and G-Lipschitz. The decision set X' is a bounded subset of the d-dimensional Euclidean space Ied
We begin by recalling the notion of 8-cover from Wainwright [2019]. See Figure in the Appendix for a schematic.
Definition 1 (Covering number). A 8-cover of a set T with respect to metric is set (0',02.... (N) S such that for each T, there exists some i [N] such that p(0, 0¹) s The d-covering number N (8;T, p) is the cardinality of the smallest 8-cover.
Construction: Let NGg = {x=, 22"...,,,""" be the smallest ś-cover the decision set X' with 8= 1/r. Since X' is contained within d-dimensional ball of diameter D, its covering number is bounded by N₂ (1 + 22)d [Wainwright, 2019, Lemma 5.7]. We construct instance of the CONSTRAINED EXPERT problem with Ns experts where the 7th expert corresponds the point x', x'i [N). The cost and constraint violation for the experts are defined as:
i [No]. Intuitively, the learner reduces the complex continuous decision space to a finite set of representative points, allowing to apply the CONSTRAINED EXPERT algorithm.
(1) f((x') (1) (9x(=')
(20)

---

Feasibility: To show the feasibility of the above CONSTRAINED EXPERT problem, consider any feasible action in the decision set x' X' that satisfies gr (x") O, Vt. Let xf be the nearest point in the 6-cover, such that || x || s 8. Using the Lipschitzness of the constraint function, have
GII=" x01 0+ Gó. Hence, from Eqn. (20), it follows that expert i" is feasible as _ ((')) ) Vt.
c (i') = (r(x") s 9x(x") Dt
Algorithm: Our policy is summarized in Algorithm 2 where, on every round, we run Algorithm on the CONSTRAINED EXPERT instance defined above. We then use the output distribution from Algorithm to select the next action as the corresponding convex combination of the points in No-
Algorithm 2 COCO Algorithm for Convex Cost and Constraints
1: Input: A minimal 8-cover of X: Naa {x","² ..... ,,""...,.:",, with d = l/r. Parameter 3 E [0, 1].
2: for each T do
3: Run Algorithm I on the CONSTRAINED EXPERT problem with Nş experts where the cost and constraint vectors are given by Eqn. (20). Obtain the distribution pt over N
4: Play = (i)x
5: end for
Analysis: By Eqn. (20) and Jensen's 's inequality, the cost and constraint violation on any round can be upper bounded by the cost and constraint violation of the CONSTRAINED EXPERT instance
cB .P:) Gö. (x)))) J& (()x')) En((t)) .JE (x())) gt. < ((()))) s (ot 1
In addition, using the L. Lipschitzness of ft, we have f((x') fe (xx' S G8, Vt. Hence, the regret and CCV of Algorithm 2 differs from that of the CONSTRAINED EXPERT instance by at most G8T s G, which is a constant. Finally, using the fact that In Ng = O(dIn 7), we invoke Theorem 2 to obtain the following bounds for Algorithm The results are summarized in Theorem 3.
Regret,(x")) O(V dl (T()) T + dln)), CCV, 0(dr' (InT)²).
(21)
Theorem 3. Under Assumptions 1, 2, and 3, Algorithm 2 achieves Ö(V TT) regret and O(d CCV for any 3 [0, 1].
5 Convex and Smooth Cost and Constraint Functions
While the previous reduction-based approach, given by Algorithm 2, is interesting, it can be compu- tationally prohibitive when the dimension d is large. To address this problem, we now propose an efficient gradient-based policy for the class of non non-negative, smooth, and convex cost and constraint functions, We will make use of the following small-los regret bound achieved by the Online Gradient Descent (OGD) policy for this class of functions.
Theorem 4 (Orabona [2019], Theorem 4.25). Let be a closed non-empty convex decision set with diameter D. Let l,, l1, be arbitrary sequence of non-negative convex and M smooth functions. Let V, be the gradient of 4, at 2,,t 2 1. Pick any In X, set the step sizes adaptively as = DD/2222 1Vr 1, and consider the Online Gradient Descent (OGD) policy with adaptive step sizes which selects the next action as: It-1 PROJ (xt TT( where PROI (-) denotes the Euclidean projection operator on to the decision set X. Then we have:
T Regret, (2) 44(1)) Σ4(4)
T
T M Σ 4(w)+ + 4 uE N.
(22)
In this section, we make the following assumption.
Assumption 4 (Convexity and Smoothness). All cost and constraint functions are convex and M Mssmohth

---

Algorithm and Analysis: Let R IR be non-decreasing convex Lyapunov function, x" é X' be a feasible action, and Qtt) be the CCV up round t. Following identical arguments as in the CONSTRAINED EXPERT problem in Section 3, we define the surrogate cost function
((x) f(()) V (Q(()))(())) xe
(23)
From Assumption 4, it follows that all surrogate cost functions are non-negative, convex, and Mr M(1+ & (Q(()) smooohh. Our proposed algorithm described in Algorithm where we
Algorithm 3 COCO Algorithm for Smooth and Convex Cost and Constraints
Initialization: Choose 21 E X arbitrarily
2: for each t T do
3: Compute gradient V fx(.)) from Eqn. (23)
4: Set the step size 7 D/ D/ 2/ /|
5: Choose next action using OGD: #++1 = PROJX (2+ - 1/6 V.)
6:
end for
run the standard OGD policy on the surrogate cost functions {4 = h21, with adaptive step sizes given by Theorem 4. It is crucial to note that the step sizes {me )21. which are derived from the past gradients, are oblivious to the smoothness parameter Mr, which is unknown a priori. Using Eqn. (22) from Theorem 4, the regret for the surrogate costs for any feasible action x can be bounded as:
Regret'
/D MTV1 + ('( + 4(1 ('(((T))D
(24)
We have used the fact that the cumulative surrogate cost is upper bounded by Σ. f((x)) S as (xx") 0, vt 1. The regret bound (24) becomes algebraically identical to Eqn. (15) under the substitutions e + 4, In + D. Thus, reusing the same analysis and parameter choices (including the Lyapunov function) from the proof of Theorem 2, we arrive at the following result.
Theorem 5. Let 3 E [0, 1] be tunable parameter, and define the Lyαpuлov function as 4(x) e²x with A= (1-88) /(SDD Then, under Assumptions 1, and 4, Algorithm 3 achieves the following guarantee for any feasible action x² e X²:
Regret, O(DVMT MT T D2M), CCV, *MT))
In particular, if ft = 0, Vt, upon setting | = 1, we obtain CCVT O(M
See Section 8.6 in the Appendix for an extension of the above result that relaxes the feasibility as- sumption (Assumption 2) by allowing the benchmark x² to violate the constraints within prescribed long term budget of BT.
Conclusion
In this paper propose online policies for the COCO problem that achieve improved cumulative constraint violation (CCV) by carefully trading it off with regret. These results are particularly important in applications where violating the constraints budget-constrained advertising. An important direction for future work is to design computationally efficient algorithms that achieve sharper CCV guarantees in the fixeddimeensionl setting without the smoothness assumption. Additionally, it would be interesting to establish matching lower bounds.
costly, such autonomous driving
7 Acknowledgement
This work was supported by the Department of Atomic Energy, Government of India, under project no. RTI4001 and by Google India faculty research award. The authors gratefully acknowledge com- ments from the anonymous reviewers, which substantially improved the quality of the presentation.
10

---

References
Elad Hazan. Introduction to online convex optimization. MIT Press, 2022.
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in ai safety. arXiv preprint arXiv:1606.06565. 2016.
Wen Sun, Debadeepta Dey, and Ashish Kapoor. aafety algorithms for adversarial contextual bandit. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3280-3288. PMLR, 06-11 Aug 2017. URL https://///// http:////oceeeeng/eeeeee mlr. wea..presssvii sunnn7a. html.
Abhishek Sinha. FanditQ:Fair Bandits with Guaranteed Rewards. In Negar Kiyavash and Joris M. Mooij, editors, Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, volume 244 of Proceedings of Machine Learning Research, pages 3227-3244. PMLR, 15-19 Jul 2024. URL https http:///ppoeegneeeeeee mlr press/v244 w4w/////2//44.......aa htmml.
Nikolaos Liakopoulos, Apostolos Destouiis, Georgios Paschos, Thrasyvoulos Spyropoulos, and Panayotis Mertikopoulos. Cautious regret minimization: Online optimization with long-term budget constraints. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3944-3952. PMLR, 09-15 Jun 2019. https: pngp/eedooeee..... mlr. S.r.ppesssvv97 Liakopoulss19.. html.
Sebastian Ruder. An overview of multi-task learning in deep neural networks. arXiv preprint 10Xv:11706.05098, 2017.
Ofer Dekel, Philip M Long, and Yoram Singer. Online multitask learning. In International Conference on Computational Learning Theory, pages 453 467. Springer, 2006.
Shie Mannor, John N Tsitsiklis, and Jia Yuan Yu. Online learning with sample path constraints. Journal of Machine Learning Research, 10(3), 2009.
Abhishek Sinha and Rahul Vaze. Optimal algorithms for online convex optimization with adversarial constraints. In The Tiihth- Annual Conference on Neural Information Processing Systems, 2024. URL https: / wwwtforumiiideeeeeeeeeeeet JMnBy.
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-3666 36439,, 2022.
Michael J Neely and Hao Yu. Online convex optimization with time-varying constraints. arXiv preprint arXiv: 1702.0077, 2017.
Jianjun Yuan and Andrew Lamperski. Online convex optimization for cumulative constraints. Advances in Neural Information Processing Systems, 31, 2018.
Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and Karl Johansson. Regret and cumulative constraint violation analysis for online convex optimization with long term constraints. In International Conference on Machine Learning, pages 11998-12008. PMLR, 2021.
Dhruv Sarkar, Samrat Mukhopadhyay, and Abhishek Sinha. Online learning for approximately- convex functions with long-term adversarial constraints. arXiv preprint arXiv:2508. 16992, 2025.
Nicolo Cesa-Bianche Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv: arXiv:1912..00 1912. 2019.
Rodolphe Jenatton, Jim Huang, and Cédric Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. In International Conference on Machine Learning, pages 402-411. PMLR, 2016.
11

---

Hao Yu and Michael J Neely. A low complexity algorithm with ((VT) regret and (1)) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 21(1):1-24, 2020.
Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Yiguang Hong. Tianyou Chai, and Karl H Johansson. Distributed online convex optimization with adversarial constraints: Reduced cumulative constraint violation bounds under slater's 's condition. arXiv preprint arXiv:2306.. 00140, 2023.
Rahul Vaze and Abhishek Sinha. o(vT) static regret and instance dependent constraint violation for constrained online convex optimization. arXiv preprint arXiv:2502.05019 2025.
Jordan Lekeufack and Michael Jordan. An optimistic algorithm for online convex optimization with adversarial constraints. arXiv preprint arXiv:2412.08066 2024.
Yiyang Lu, Mohammad Pedramfar, and Vaneet Aggarwal. Order-optimal projection-free algorithm for adversarially constrained online convex optimization. arXiv preprint arXiv:2502.16744, 2025.
Subhamon Supantha and Abhishek Sinha. Universal dynamic regret and constraint violation bounds for constrained online convex optimization. arXiv preprint arXiv:2510.01867, 2025.
Nicolo Bianchi, Yoav Freund, David Haussler, David P Helmbold, Robert E Schapire, and Manfred K Warmuth. How to use expert advice. Journal of the ACM (JACM), 44(3):427-485, 1997.
Peter Auer, Nicolo Cesa- Bian-Bi,cchh, and Claudio Gentile. Adaptive and self-confident on- on-line learning algorithms. Journal of Computer and System Sciences, 64(1):48-75, 2002.
Elad Hazan and Satyen Kale. Extracting certainty from uncertainty: Regret bounded by variation in costs. Machine learning, 80:165-188, 2010.
Zakaria Mhammedi, Wouter Koolen, and Tim Van Erven. Lipschitz adaptivity with multiple learning rates in online learning. In Conference Learning Theory, pages 2490-2511. PMLR, 2019.
Nicolo Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for predic- tion with expert advice. Machine Learning, 66(2)321-332, 2007.
Sébastien Bubeck, Nicolo Cesa-Bianchi, al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
Wouter M Koolen and Tim Van Erven. Second-order quantile methods for experts and combinatorial games. In Conference on Leurning Theory, pages 1155-1175. PMLR, 2015.
Martin Wainwright, Higg--iieessonal statistics: non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Abhishek Sinha. Source code for "Beyond Ô(VT) Constraint Violation for Online Convex Optimization with Adversarial Constraints"; A. Sinha, R. Vaze. httpa://github. com/ abhishek-sinha Coanha-tifr/CCCOOO LLLE//CoO--improeee--eo CCV, 2025.
Haipeng Luo. Lecture 4. Introduction to Online Learning. 2017. https://haipeng: /
courses/CSCI699/ indexx html.
12

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide complete theorem statements along with detailed proofs for all claims presented the paper.
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 the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our results critically rely the feasibility assumption (Assumption 2), which is standard in the COCO literature. While this assumption widely adopted, remains an interesting direction for future work to explore how and to what extent it be relaxed. Additionally, as discussed in the conclusion, deriving matching lower bounds remains an open and important problem.
Guidelines:
The answer NA means that the paper has no 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 a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested 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 approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex- system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
13

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We clearly state the assumptions under which our theoretical results hold. Complete proofs of all theoretical claims have been provided either in the main paper or in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but 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 complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The complete experimental set up with all relevant parameter values has been included in Section 8.7 of the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken 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 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 is often one good way 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 large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
14

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should 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 faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code has been made publicly available [Sinha, 2025].
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/ cublic/guides/ wwwps//oooeSamaisiiiiiiiii
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips wnnps.cccppppp wwtppccwcc/ccacccccccccccccc mublic/guides Seuide//Cooeeueeeee
ssionPolicyy 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
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification; The complete experimental set up with all relevant parameter values has been included in Section 8.7 of the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: Since our paper proves bounds on the worst-case performance metric, error- bars are not essential for the experimental results.
Guidelines:
15

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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 or the standard error of the mean.
OK to report I-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Relevant details have been provided in Section 8.7 of the Appendix.
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 rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported 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 https: ttcttps//neuriie cc/pubblccBchiiccuuiieee
Answer: [Yes]
Justification:
The paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiciii..))
10. Broader impacts
Question: Does the paper discuss both potential positive socictal 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 socictal consequences of this paper.
16

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has societal impact or 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 specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards 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]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
17

---

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

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we 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 is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
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 LLM policy (https: : //nnruurpp.... for what should or should not be described.
19

---

8 Appendix
8.1 On the Boundedness Assumption
Assumption implies that there exist constants K,, Kg such that
[f(()) & Ky, (ax(z)) K g. V X, V/2 1.
Since the constraint function is non-negative, the above implies
[f())) K,, os (x( Kg. Vx E X, Vtz 1.
Now consider the following translated and scaled version of the cost and constraint functions:
[x(x)= = f((x) 1 (+(x)= = 9((x)
+
x E 21121.
2Kg 2
Kg
is easy to verify that 0 s Je, Tt s 1, 2 1. Hence, we can work with these modified cost and constraint functions.
P.S. With the feasibility assumption (Assumption 2), we can even obtain an explicit expression for Kg. Let x' be feasible action. Using the G-Lipschitzness of the function Jt, have
(x) 9((x") G| x= s 0+ GD.
Thus we can take Kg = GD. Consequently, we only need to assume the cost functions to be bounded.
8.2 Pseudocode for the Adaptive Hedge Policy
Algorithm 4 Adaptive Hedge Algorithm for the EXPERT problem with Unbounded Losses
Input: Number of experts N, Horizon length T, Non-negative and potentially unbounded loss vectors (4) 1.
2: Initialization: Algorithm's loss Żo 0, Losses of the experts Lu 0, Go 1.
3: for each 1: T do
4: Compute self-confident learning rate
In 7) VG-1 L +GG
(25)
5: Play adaptive Hedge by choosing the thh expert with probability
(r( Tx- Σ
exp((=n vie [M].
==1
6: The loss vector 1, is revealed to the learner
7: Update the algorithm's 's and experts' losses
i. + 4 + (le,p)), La +- I4-1 4
8: G₁ is an upper bound || such that s Gte//G S
9: end for each
8.3 Proof of Theorem
Our proof adapts the arguments given in Luo [2017] while accounting for unbounded losses. Let (i) denote the cumulative loss of the thh expert up to round t, i.e., L,(i) 4 [N].
20

---

Define the potential function 2,(n) = 1,,og
Ei-1 exp(-n
We have
N
E exp( (ncp(()))a(i))
(x(n:) - 1 (1)c
In
118
Σi exp(- - (
In
Σ pr(i) exp exp(((x(((i)
1/
(a)
(6)((1)
In
(c( -n)((i+++
1/1
2
In
1- 1-lpp)))))
2h Σ (1)( 2
i-1
(6)
S
(pr,
11)
T1t Σ
Pr (1)
2 F=1
y²
where in incquality (a), we have used the fact that e the fact that + y e0, Vy E R. Thus we have that
S 1
y
2
Vy 2 0, and in (b), we have used
N
(pt, (x) s &r- 22-1(m)) 2.h1)
Σ (1)
2
Summing the above inequality for 1 S $ T yields
LT
T
4p)
T Tht
N
T
#o(m)
(17+1)
Σ
Σ
(1)
Σ
(T)()R))) -b(()))
2 i=1
(a)
In N
1 In
T
N
Σ
G
Σ (())))(()=
MF+1
MT+1
(1)
T
(p)
T
V(r+ LT(i") + Gr
Σ
(1))))
22
T
G
(4)
(B)
(26)
where, in (a) we have used the fact that |14||~< & G,, and (b) we have used the expression (25) for the learning rate along with the fact that G, GG and G, s Gt,
To bound term (A) in Eqn. (26), observe that
L. = É (p), i G. s +
Hence,
T
T
L. L. (c) &
f(h for dx
Tz 2 LT,
T GG
VL,
where in inequality (c), we have used the monotonicity of the sequence (Le)ret-
Furthermore,
be readily verified that the potential function +>( is non-decreasing in vj as (n) 2 [Luo, 2017]. Since the learning rate 7h is non-increasing in 4, we conclude that each term in term (B) in Eqn. (26) is non-positive. Hence, using the inequality Va+ bs Va + /b, from Eqn. (26), we have
L s 2n LT InN + LT(i*) + GrVyInN.
In the above, we have used the fact that y 1. Solving the above quadratic inequality using Lemma 1 below, conclude that the adaptive Hedge policy enjoys the following small-loss regret bound for the EXPERT problem:
(T-Lr(i") s (21))s222/rrrt) 2T/LT((i)Grrn IN Gy
21

---

8.4 Proof of Auxiliary Lemmas
Lemma (A quadratic inequality). Consider the following quadratic inequality x² S az + b, where
2 0,b2 O. Then we have x²² & a² + avb..
Proof. Solving the given inequality using the usual quadratic formula and the fact that v + y VI+ vy, 2, 2 O,, we have
a
a + 46
a a 2Vb
Vb.
Hence,
x² < + +b= bb
Lemma 2 (Bounding 7). Let (()) exx x²= (- (2cln) where 10. Define G2 1 ((((())),tz and maxistsT GL11"
G.,,
Then have y 1.08.
Proof. Since 0 $ 9t $ 1, from Eqn. (9), we have
Q(t) Q(t 1) + (9),p)) (Q(t +.
(27)
Thus
G2 (011 (a) (Q1((( 1 (e-((()
S
1 XeAQ(1-1) S Se,
(28)
G
where in (a) we have used inequality (27). Since N 2 and 1, we have À (2eln 2) Hence,
Eqn. (28) implies that
7 2/(21m2))) s 1.08.
8.5 Construction of a Minimal 8-cover of the Decision Set
X
Figure 1: Schematic depicting the greedy construction of minimal 8-cover of the decision set X. If a point x e X' not covered yet, we construct a ball of radius 8 centred at x and include the point x in the d-cover. The process continues till the entire set X' is covered.
22

---

8.6 Relaxing the Feasibility Assumption
In this Section, we relax the feasibility Assumption by allowing the benchmark actions to violate the constraints up to given budget Br O. In particular, we consider the following feasible set of actions which are budget feasible in the long term:
I XB, = f [g(t)sBp)) Br).
(29)
We now replace Assumption 2 with the following assumption. Assumption 5 (Long-term Feasibility). The feasible set is non-empty, i.e., &B + Ø.
Note that By X" when By = O. Since 0 s 9r s (Assumption I), we clearly have X = X, where X is the entire decision set. Thus, without any loss of generality, we can assume that By s T.
8.6.1 The Generalized Regret Decomposition Inequality
We now generalize the regret decomposition incquality (13) by taking into account the long-term feasibility constraint (29). Let 4 R + I be any non-decreasing convex Lyapunov function defined as in Section 5 and let x" Xi any long-term feasible action satisfying the budget constraint (29). Recall that CCV evolves as Q(I) Q(t - 1) + 91 (x²). Hence, using the convexity of ((.), we obtain
-10 f((x')
((Q())) (f((x;) (f((x") (((()))((zz)) (1(())))((=')
where, unlike in Section 5, the violation 9r gx (x*) in this case could be strictly positive. Summing up the above inequalities, we conclude
( Regrety (x")
Regrety (x"))++()))()))))))))) Σ g((x') El
(6)
Regret((x") ( ((((()))
(30)
where, before, Regrety (x") and Regrety (x") denote the regrets for learning the original cost functions (ftr respectively w.r.t. the long-term feasible benchmark x" (see Eqn. (23) for the definition of the surrogate cost functions). In the above inequality, the upper bound in step (a) follows from the monotonicity of the CCV (Q(t)) (2))) and the convexity of the Lyapunov function (-), while step (b) uses the budget constraint for x² By.
functions (f and the surrogate
In the following, consider the case of convex and smooth and constraint functions under the relaxed feasibility assumption (see Section 5). The analysis for the CONSTRAINED EXPERT problem is identical.
8.6.2 Convex and Smooth Cost and Constraints with Long-term Budget Constraints
Inequality (30) of the same form the regret decomposition inequality (13) under Assumption albeit with an extra additive term E' (Q)T)) Br appearing on the right-hand side. By using the same exponential Lyapunov function as before (with the parameter À now adapted to the budget Br), we can analogously solve the above functional inequality and derive the corresponding regret and CCV bounds under long-term violation budget constraints.
Br can be The cumulative cost of the surrogate functions under any long-term feasible action x² E &
upper bounded as
=(())=E(()) T
T Σ gx(x") @ T ('(Q(T)) Br, (31) (+'((())(("") (8) T (++'(((())
where in inequality (a), we have again made use of the convexity of the Lyapunov function and the non-decreasing property of the CCV, and in (b), have used the budget constraint for x". Hence,
23

---

using Eqn. (22) from Theorem 4, the regret for the surrogate costs under the action of Algorithm can be upper bounded as:
Regret)(x")
(MMT++ (VT++cVTT((C))) (3 Br.
4(1+ (((()))))
(32)
where CI2, C2, C3 are generic constants which depend only the problem-specific parameters M and D. If necessary, the reader can easily figure out the explicit values of these constants in each line of the derivation below.
As in Section 3.1. we now set Φ(-) to be the exponential Lyapunov function, i.e., 4(x) == exp(Ax), for suitable value of the parameter À which will be fixed later. With this choice, the regret decomposition inequality (30) yields
AQ(T) + Regret, (x") s ci SIVT + xotoTTTTTe/Aeet0 ca)
We now choose some À such that X
Hence, the above equation yields
(Q(T) Regret, (x') C + x2
(33)
The Regret and CCV bounds obtained by solving the above inequality.
Bounding the CCV: Using the fact that Regrety (x*) 2 -T, Eqn. (33) yields
(Q(T) c T C2VTTe 2 )
This implies the following bounds for Q(T):
Q(T) (x*) + log + log?") = O(x log?").
Bounding the Regret: Starting from inequality (33) once again, we have the following upper bound on regret
Regrety S
NPTM) AQ(T).
2
vb 0, and taking x (2((T/2 the regret can be further upper Using the fact that ar hx a² bounded as follows:
45
& xI
Regret, (x') S ScVT
2
Finally, choosing A min( 2ng T (1-8)) for some 3 1, obtain the following trade-off
Q(T) Ō(max Br. ))) Regret, O VT, TO)).
(34)
As an example, Br /*, then by choosing 3 3/3, we obtain Regret, (x*) ( and CCV, = cCV==
OTT%)..
The above results are summarized in the following Theorem.
Theorem 6. Let Br 2 0 be the prescribed long-term constraint violation budget. Consider the Lyapunov function ((z) xx with X - where 3 [0, 1] is tunable parameter and c is constant which depends the problem parameters (D and M) as discussed above. Then, under Assumptions 1, 4, and 5, Algorithm achieves the following guarantee for any long-term feasible benchmark action x² X
Regrety (x") Ommax( VT,T")), (T.ax(Br,TI1))))
24

---

Fig.A: Cumalative Regret
Fig B: Cummative Condrrant Viclation (DCV)
Expert CDCO (Acactive Hedge) Grod based C2G0
800
Cummuttte Reggat
202
100
Expert COC0 (Adantre
Grudinbbused COCO
1000
2000
3000
4000
5000
1.000
2000
4000
5000
stop
Fig C:Adaptie Hedge: Action Probabl liss
Fig D: Gradient COCD: Actio Probabiitees
110
Expertaduxx
Exper Agortnnox
20
15
15
-02
-02
000
000
1000
Figure 2: Comparison of the proposed adaptive Hedge-based policy (Algorithm 1) with 8 0.75 and the OGD-based policy from Sinha and Vaze [2024, Algorithm 1]. (A) Regret vs. time. (B) Cumulative Constraint Violation (CCV) vs. time. (C) Selection frequency of experts under our adaptive Hedge-based policy. (D) Selection frequency experts under OGD-based policy. The proposed policy quickly identifies and sticks to the best feasible expert, leading to significantly lower CCV, whereas the OGD-based policy initially selects infeasible experts and takes longer to converge.
8.7 Experiments
Problem instance: We consider the CONSTRAINED EXPERT problem on a synthetic dataset with N = 20 experts over horizon of length 7' = 5000. Two experts are designated as special: the best feasible expert, denoted by E", and the best unconstrained expert, denoted by UE", The expert feasible, with i.i.d. costs drawn from distribution with mean fe. 0.21, and zero constraint violation on all rounds, i.e., 9E- 0.0. In contrast, UE' is infeasible, with i.i.d. costs and constraint violations having smaller mean fus- 0.11 and higher average constraint violation 9ue- 0.91, respectively. The remaining experts incur i.i.d. random costs with mean f 0.41 plus a zero-mean periodic component over time, and their constraint violations are i..d. with mean 0.6. Additionally, two more experts, DE; and DEg, distinct from both E* and UE" are made feasible by setting their constraint violations zero all rounds. Table 2 summarizes the parameters used in the experiments. The experiments have been run on a quad-core CPU with 8 GB RAM. The source code has been made publicly available [Sinha, 2025].
Expert(s)
Index
Average
Average constraint violation
E' #12
fE. = 0.21
Øg. 0.0
UE"
#S #3, #6
f 0.11
9E- 0.91
DE2
fE. 0.41
Øs- 0.0
The rest
[20] < 6,
f 0.41
GE- 0.6
Table 2: Parameter settings for generating cost and constraint vectors for N 20 experts.
Summary of the results. Parts (A) and (B) of Figure 2 compare the performance our proposed adaptive Hadge-based policy (Algorithm 1) with 8 0.75 with that of the Online Gradient Descent
25

---

Consirii Segut as Time
Canoiein CCV Time
14
Corvlallee Genatvant Vedation
122
Cunsesttvv Begren
Figure Performance comparison for different values of 3
(OGD)-based policy proposed by Sinha and Vaze [2024, Algorithm 1]. From the plots, is evident that the proposed algorithm incurs significantly lower cumulative constraint violation (CCV) while maintaining sub-linear regret.
To gain deeper insight into the working of the algorithms, parts (C) and (D) of Figure 2 show the relative frequency with which each expert is selected by our algorithm and the OGD-based policy, respectively. These plots clearly demonstrate that the adaptive Hedge-based policy quickly identifies the best feasible expert and predominantly selects thereafter. In contrast, the OGD-based policy initially incurs substantial amount of constraint violation by frequently selecting infeasible experts. Only after considcrable number of rounds does converge the best feasible expert and begin exploiting it consistently.
Figure 3 illustrates the trade-off between regret and eumulative constraint violation (CCV) for different values of the tuning parameter / in the proposed policy. As 3 increases from 0.6 to 0.9, the algorithm incurs lower CCV the expense of higher regret. This behavior aligns with the theoretical performance guarantees established in Theorem 2.
26


Reviews:
[{"review_id": "uO19T3s9xz", "reviewer": "Reviewer_D1DS", "summary": "In this paper, the authors revisit the COCO problem. The COCO problem is defined as follows: in each round, a learner selects an action from a convex decision set, after which an adversary reveals both a convex cost function and a convex constraint function. The learner's objective is to minimize both regret and cumulative constraint violation (CCV), where CCV quantifies the total amount by which the constraints are violated over T rounds.", "questions": "NA", "limitations": "there is no negative social impact.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "It is well established that in the standard Online Convex Optimization (OCO) setting, where the constraint function gt = 0 for all t, achieving regret smaller than O(√T) is fundamentally impossible—even in one-dimensional problems. As a result, the O(√T) regret guarantee for the COCO problem is unimprovable in the general case. However, whether CCV can be made substantially smaller than O(√T) under additional natural assumptions has remained an open question.\n\nThe current state-of-the-art achieves O(√T) regret and O(√T) CCV. The authors make a significant contribution by introducing a tunable trade-off between regret and CCV. Specifically, under bounded convex cost and constraint functions, they propose an online policy that achieves a regret of O(√dT + T^β) and a significantly smaller CCV of O(dT^{1−β}), where d is the dimension of the decision set and β \\in [0,1] is a user-defined parameter. This approach offers a meaningful improvement, allowing practitioners to flexibly balance regret minimization and constraint satisfaction based on problem-specific priorities.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a brief summary of our work and positive comments."}, {"review_id": "6gxO3USDxJ", "reviewer": "Reviewer_FioB", "summary": "This paper studies online convex optimization with adversarial constraints (COCO), where the learner’s goal is to minimize both the regret and the cumulative constraint violation (CCV). The main contribution of the paper is to show that by leveraging small-loss bounds, it is possible to achieve a more flexible trade-off between constraint violation and regret minimization. Specifically, the proposed method guarantees a regret bound of $\\mathcal{O}(\\sqrt{T} + T^{\\beta})$ with a corresponding constraint violation of $\\mathcal{O}(T^{1-\\beta})$, where $\\beta$ is a tunable parameter chosen by the learner to balance the trade-off.", "questions": "* Could the authors provide a more detailed comparison with Lipschitz adaptivity techniques in PEA and OCO? Please refer to the first point in Weakness for more details.\n\n* The feasibility assumption seems rather strong, as it requires the comparator to strictly satisfy the constraints. Is it possible to derive regret bounds where the comparator is allowed to violate the constraints slightly, for example allowing CCV up to $\\mathcal{O}(\\sqrt{T})$?", "limitations": "Yes. One limitation of the paper is the computational efficiency of the algorithm in the OCO setting. This issue is partially addressed by imposing a smoothness assumption on the loss functions in Section 5.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\n* The results in this paper recover those of [Vaze and Sinha, 2025] while offering a flexible mechanism for trading off between regret and CCV.\n\n* The idea of applying small-loss bounds to the analysis of the COCO problem is novel and insightful to me.\n* the paper is well-written and structured\n\n## Weaknesses\n\n- **Comparison with related work and technical contribution:** One of the main technical contributions is the development of an algorithm for the prediction with expert advice setting with unbounded losses. However, this problem appears closely related to the Lipschitz adaptivity problem in online learning, where scale-free algorithms have been studied. For example, \\[1, Section 2] provides a scale-free second-order bound. It seems the derived second-order bound also implies the small-loss bound by simply upper bound the loss functions by $G_T$. The paper would benefit from a more detailed discussion comparing these related results and techniques.\n\n- **Tightness of the bound:** While the use of small-loss bounds in COCO allows more flexibility in trading off regret and constraint violation, it is unclear how tight the proposed bounds are. The authors claim on lines 67–68 that *“Thus the unconditional $O(\\sqrt{T})$ regret guarantee for COCO cannot be improved.”* However, this statement is not entirely clear. It appears that the learner is allowed to violate constraints, whereas the comparator must strictly satisfy them. If we permit $O(T)$ CCV, it is unclear whether $O(\\sqrt{T})$ regret truly constitutes a lower bound. \n\n[1] Lipschitz Adaptivity with Multiple Learning Rates in Online Learning. COLT 2019.", "was_revised": true, "final_justification": "My initial concern about the paper was the novelty of the small-loss bound (Theorem 1) and the omission of prior work on Lipschitz adaptivity in PEA. During the rebuttal, I realized that this bound is not the main contribution of the paper, and the authors committed to adding more discussion on this point. This addressed part of my concern, so I increased my score to 4 to reflect the positive evaluation.", "rebuttal": "$\\textbf{On the comparison with related work and technical contribution:}$\n\nWe thank the reviewer for highlighting the relevant reference [3]. Our adaptive regret bound for the Hedge algorithm, presented in Theorem 1, indeed lies within the broader context of Lipschitz adaptivity, an active research area within the online learning community. The bound in Theorem 1 serves as a key intermediate result leading to one of our main contributions, namely Theorem 2.\n\nIn the case of convex and smooth cost functions, we employ a standard small-loss bound (Theorem 4). However, for the setting of Prediction with Expert Advice in Section 2, we design a new algorithm with a self-confident, adaptive learning rate (Algorithm 4). This design choice is motivated primarily by computational efficiency, as we elaborate below.\n\n\nTo recall the relevant results from [3]: after generalizing the Squint algorithm, [3] proposes two Lipschitz-adaptive algorithms for the Experts setting, both of which rely on multiple restart phases and incur additional computational overhead.\n\nIn contrast, our proposed self-confidence-based algorithm (Algorithm 4) is conceptually simpler and more efficient. It employs a closed-form multiplicative update rule, avoiding costly operations such as Gaussian CDF evaluations (required in [3]) and the restart logic. This simplicity is achieved by leveraging the specific form of the surrogate cost function (given by Equation (11)), whose gradient sequence satisfies a structural property: the ratio of consecutive gradients is bounded by a known constant $\\gamma$ (see Theorem 1 and Lemma 2).\n\nWe will incorporate this clarification into the revised version of the paper.\n\n\n\n\n\n$\\textbf{On the tightness of the bounds:}$\n\nWe emphasize that the $\\Omega(\\sqrt{T})$ lower bound on regret holds even when the online learner is permitted to violate the constraints by up to $O(T)$. This non-trivial result was established in [1, Theorem 3], which constructs a high-dimensional instance (with dimension $d \\geq T$) where both regret and cumulative constraint violation (CCV) are individually and unconditionally lower bounded by $\\Omega(\\sqrt{T})$ for any online learning policy.\t\n\n\n$\\textbf{On the feasibility assumption:}$\n\nWe agree with the reviewer that the feasibility assumption, although commonly adopted in the COCO literature [1,2], is rather strong. However, 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 [4][1, Section 4]. \n\nThat being said,  in the following, we show that our proposed techniques are strong enough to handle the case when the offline benchmark is allowed to violate the constraints up to a given budget, say $B_T$, i.e., \n$$\\sum_{t=1}^T g_t(x^\\star) \\leq B_T, $$\nwhere, as before, the non-negative function $g_t$ encodes the penalty for constraint violation on round $t.$\n\nLet $f_t$ be the cost function and $g_t$ be the constraint function for round $t$. Similar to Eqn (10), the convexity of the Lyapunov function implies:\n$$\n\t\\Phi(Q(t)) -\\Phi(Q(t-1)) + (f_t(x_t)- f_t(x^\\star)) \n\t\\leq \\big(f_t(x_t) + \\Phi'(Q(t))g_t(x_t)\\big) - \\big(f_t(x^\\star)+\n\t\\Phi'(Q(t))g_t(x^\\star)\\big) + \\Phi'(Q(t))g_t(x^\\star).\n$$\n\n\nWhere, unlike before, the quantity $g_t(x^\\star) $ could be strictly positive as the benchmark need not be feasible on every round. Summing up the above inequalities, we have \n\n$$\n\t \\Phi(Q(T)) - \\Phi(Q(0)) + \\text{Regret}_T \n\t\\stackrel{(a)}{\\leq} \\text{Regret}'_T +  \\Phi'(Q(T))\\sum_t g_t(x^\\star)\n\t\\stackrel{(b)}{\\leq} \\text{Regret}'_T +  \\Phi'(Q(T))B_T,\n$$\n\nWhere, as before, $\\text{Regret}_T$ and $\\text{Regret}'_T$ \n\ndenote the regrets for learning the original cost functions $(f_t)$ and the surrogate cost functions $(\\hat{f})$ respectively (see Eqn. (22) for the definition of surrogate cost functions). In the above inequality, the upper bound in step (a) follows from the monotonicity of the sequence $(Q(t))_{t \\geq 1}$ and the convexity of the Lyapunov function $\\Phi(\\cdot)$, while step (b) uses the budget constraint on $x^\\star.$ \n\nThe above inequality is of the same form as the regret decomposition inequality (12) in the paper with an extra additive term $\\Phi'(Q(T))B_T $ appearing on the right hand side. By using the same exponential Lyapunov function as in the paper (with the parameter $\\lambda$ now adapted to the budget $B_T$), we can analogously solve the above functional inequality and derive the corresponding regret and CCV bounds in the relaxed benchmark setting. \n\nWe will include the above discussion in the revised version. \n\n\n $\\textbf{References}$\n \n [1] Sinha, Abhishek, and Rahul Vaze. \"Optimal algorithms for online convex optimization with adversarial constraints.\" Advances in Neural Information Processing Systems 37 (2024): 41274-41302.\n \n [2] Guo, Hengquan, Xin Liu, Honghao Wei, and Lei Ying. \"Online convex optimization with hard constraints: Towards the best of two worlds and beyond.\" Advances in Neural Information Processing Systems 35 (2022): 36426-36439.\n \n [3] Mhammedi, Zakaria, Wouter M. Koolen, and Tim Van Erven. \"Lipschitz adaptivity with multiple learning rates in online learning.\" In Conference on Learning Theory, pp. 2490-2511. PMLR, 2019.\n \n [4] 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."}, {"review_id": "kRrBx9Icxj", "reviewer": "Reviewer_628F", "summary": "This paper revisits online convex optimization with adversarial constraints (COCO), where an adversary reveals a convex cost function and a convex constraint function at each round. This work improves upon previous best-known result $O(\\sqrt{T})$ regret and $\\tilde{O}(\\sqrt{T})$ cumulative constraint violation (CCV) by achieving a  smaller CCV by trading it off with regret. To achieve this result, this paper considers the  constrained expert problem, similar to learning with expert advice (LEA). Furthermore, the authors propose a computationally efficient policy for the constrained expert problem.", "questions": "1. Could the authors clearly articulate the technical novelty and contributions of this work? In particular, why do the theoretical results in Table 1 represent a significant improvement over prior work? \n2. According to the preliminaries, smoothness can be leveraged to obtain small-loss bounds, i.e., problem-dependent bounds. However, in this paper, the theoretical results for smooth functions remain in terms of $T$, i.e., they are problem-independent. Therefore, it is unclear to me why smoothness does not lead to a problem-dependent bound in the context of the COCO problem.\n3. According to the description of Algorithm 1, the proposed method appears to be a direct application of the PEA framework combined with adaptive learning rates. Could the authors elaborate on the technical challenges addressed in this work?", "limitations": "Compared to existing COCO algorithms, this paper adopts the PEA framework, which requires maintaining multiple experts. As a result, the proposed algorithm incurs additional computational complexity.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n* This paper conducts an in-depth study of COCO and presents a rich set of theoretical results, including constrained expert with $N$ experts, $d$-dimensional decision set, and $M$-smooth cost and constraints. \n\nWeaknesses:\n\n* The writing of this paper needs improvement, and the formatting should be refined—for example, Table 1 exceeds the page margins significantly. \n* The main theoretical results of this paper do not significantly improve upon prior work. \n* The proposed method appears to directly adopt the existing prediction with expert advice (PEA) framework, and the technical novelty is limited.", "was_revised": true, "final_justification": "After the rebuttal and discussions with the authors, I recommend a borderline accept. This paper indeed makes a technical contribution to COCO. Although the improvement in CCV is not as significant as the authors claim, the trade-off between regret and CCV is still meaningful.", "rebuttal": "$\\textbf{Comment:}$ *The writing of this paper needs improvement, and the formatting should be refined—for example, Table 1 exceeds the page margins significantly.*\n\n$\\textbf{Response:}$ We apologize that the reviewer found the paper difficult to read. To better assess this difficulty, we had a relook at the paper, and upon some reflection, we would like to make the following\nimprovements that we believe will significantly improve the readability and flow of the paper. \n\n*Moving Section 3 before Section 2, and moving Section 2 to the Appendix.* Currently, Section 2, which consists of preliminaries, impedes the flow since the Constrained Expert problem studied in Section 3 is the first main object of interest. For the Constrained Expert problem, writing out the main objectives, i.e. simultaneously bounding the regret and CCV will be fleshed out in equations for better exposition. \n\nInstead of starting Section 3.1 with the analysis of Algorithm 1, we will first define Algorithm 1, together with sufficient intuition and explanation. Following this, the main idea needed for the analysis, as currently described in Section 3.1, will be presented. \n\nWe will also move the full proof of Theorem 2 to the Appendix and instead discuss its implications after presenting the statement of Theorem 2. \n\nA better transition between Section 3 and Section 4 will be added for smooth reading experience. Moreover, we will discuss the inherent difficulty of deriving the results of Section 3 from the more general case in Section 4.\n\n\nIn Section 5, we will move the prior result (Theorem 4) to the Appendix, and directly present the algorithm and its guarantees together with the intuition of the surprising result that CCV is independent of dimension d when the cost and constraint functions are $M$- smooth. This is surprising since the lower bound of [2] for both regret and CCV is $\\sqrt{d}$ when functions are just Lipschitz.\n\nWe will also reformat Table 1 and ensure that all formatting issues are resolved in the final version.\n\n\n\n\n$\\textbf{Comment:}$ *According to the description of Algorithm 1, the proposed method appears to be a direct application of the PEA framework combined with adaptive learning rates. Could the authors elaborate on the technical challenges addressed in this work?*\n\n$\\textbf{Response:}$\nWe would like to clarify that the central focus of the paper is on improving cumulative constraint violation (CCV) bounds for the constrained online learning (COCO) problem, rather than on designing adaptive algorithms for the classical Prediction with Expert Advice (PEA) problem *per se*.\n\nThe main technical challenge lies in the need to handle both cost and constraint functions simultaneously, while ensuring optimal regret and CCV bounds. Although lines 5–6 of Algorithm 1 correspond to the PEA setting, lines 7–10 demonstrate how the PEA subroutine is leveraged to reduce the constrained learning problem to an instance of PEA in a novel way.\n\nTheorem 1, which provides a small-loss regret bound for the PEA problem, is used as an essential intermediate result. It enables us to derive Theorem 2, which extends the state-of-the-art CCV bounds in the COCO literature. Thus, the contribution is not merely an application of known techniques, but a carefully structured reduction that leads to improved theoretical guarantees in the challenging constrained setting.\n\n\n$\\textbf{Comment:}$ *According to the preliminaries, smoothness can be leveraged to obtain small-loss bounds, i.e., problem-dependent bounds. However, in this paper, the theoretical results for smooth functions remain in terms of $T$, i.e., they are problem-independent. Therefore, it is unclear to me why smoothness does not lead to a problem-dependent bound in the context of the COCO problem.* \n\n$\\textbf{Response:}$ We would like to clarify that the goal of this work is not to derive problem-dependent regret bounds for the standard OCO setting under the smoothness assumptions, as such results are already well-established in the prior literature. Instead, our objective is to utilize the small-loss bounds to achieve a sublinear regret and significantly improved CCV guarantees (in terms of the horizon length $T$) for the constrained learning (COCO) problem.\n\nThe surprising result in this paper is that, although smoothness does not help improve the regret lower bound (which remains $\\Omega(\\sqrt{T})$ even for linear losses [1]), it can still be exploited to reduce the CCV significantly. This is a novel and perhaps unexpected phenomenon. Existing COCO algorithms did not take advantage of problem-dependent small-loss bounds in this way, which is why they were limited to $O(\\sqrt{T})$-type CCV guarantees [2,3]. In contrast, our work proposes an efficient gradient-based algorithm that shows how  smoothness can lead to sharper bounds on constraint violation $(\\tilde{O}(T^{1-\\beta}))$, even when regret remains sublinear $\\tilde{O}(\\sqrt{T} + T^\\beta), \\beta \\geq \\frac{1}{2}.$\n\nExploring whether smoothness can be further leveraged to derive problem-dependent bounds in the COCO setting is an interesting research direction. We leave a full investigation of this question to future work.  \n\n\n$\\textbf{References}$\n\n[1] Elad Hazan. Introduction to online convex optimization. MIT Press, 2022.\n\n[2] Sinha, Abhishek, and Rahul Vaze. \"Optimal algorithms for online convex optimization with adversarial constraints.\" Advances in Neural Information Processing Systems 37 (2024): 41274-41302.\n\n[3] Guo, Hengquan, Xin Liu, Honghao Wei, and Lei Ying. \"Online convex optimization with hard constraints: Towards the best of two worlds and beyond.\" Advances in Neural Information Processing Systems 35 (2022): 36426-36439."}, {"review_id": "geh80WHYbq", "reviewer": "Reviewer_NUnN", "summary": "This work investigates the COCO setting, that is, online convex optimization with constraints. In such a setting, the state-of-the-arts result is an algorithm that attains $\\widetilde{O}(\\sqrt{T})$ regret and violation without Slater's condition. This works improves the result by showing that $\\widetilde{O}(\\sqrt{T}+ T^{\\beta})$ regret and $\\widetilde{O}(T^{1-\\beta})$ violation is attainable. The problem is solved by focusing on the expert (MAB with full feedback) setting, where the employment of small-loss regret minimiser, Lyapunov functions and surrogate functions allows to attain the desired result. Thus, a $\\delta$-covering allows to reproduce the same results in the COCO setting (paying a cost in terms of computational complexity). Finally, the authors show that OGD with adaptive learning rate (and surrogate functions) attains similar results when the objectives (cost and constraints) functions are smooth.", "questions": "See weaknesses", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The contribution and the results are clear. The authors did a good job in presenting the core ideas behind the functioning of the algorithm and their analysis.\n\nWeaknesses:\n\n1. The paper strongly relies on the techniques of [Sinha and Vaze. 2024], that is for both Lyapunov functions and surrogate functions. Similarly, the algorithm for small-loss regret guarantees is a simple modification of existing ones [Luo, 2017]. Thus, the algorithmic novelty is limited.\n2. The result for the COCO setting is attained at the cost of paying a $T^d$ computational complexity.\n3. The technical analysis is not particularly involved. \n\nOverall, even if the paper is not breakthrough from a technical perspective, I still believe that the results are interesting and that the way the authors combine existing algorithms and techniques to attain the desired theoretical guarantees is valuable.\n\nMinor:\nI believe that the presentation of the paper can be improved, for example, by reducing the dimension of the related works table. Moreover, the checklist still has some [TODO] in it.", "was_revised": true, "final_justification": "As pointed out in my response to the Authors, their rebuttal did not particularly change my evaluation of the paper. Overall, I still believe that the new trade-off between regret and violation is interesting, that is why I keep my borderline accept score. Nonetheless, I certainly believe that the paper somehow combines existing techniques to achieve desired results. Additionally, I want to acknowledge that I am not familiar with the \"Lipschitz adaptivity\" literature; thus, I cannot comment on Reviewer FioB concerns in detail. Nonetheless, I believe that potentially overlooking a line of research could worsen the quality of the work.", "rebuttal": "$\\textbf{Comment}:$ *The paper strongly relies on the techniques of [Sinha and Vaze. 2024], that is for both Lyapunov functions and surrogate functions. Similarly, the algorithm for small-loss regret guarantees is a simple modification of existing ones [Luo, 2017]. Thus, the algorithmic novelty is limited.* \n\n$\\textbf{Response}:$ While our work builds on the Lyapunov and surrogate function techniques introduced in [1], we apply them in a novel and insightful way. Specifically, we demonstrate that small-loss regret bounds in standard OCO can be leveraged to obtain substantially improved bounds on the cumulative constraint violation (CCV) in the constrained setting, thus surpassing the long-standing $O(\\sqrt{T})$ barrier for CCV. This connection is both non-trivial and, to the best of our knowledge, previously unexplored.\n\nMoreover, unlike the unconstrained OCO setting, where the $\\Omega(\\sqrt{T})$ lower bound persists even under smoothness assumptions, we establish a rather surprising result that smoothness allows for much sharper CCV guarantees. This result hinges critically on Theorem 1, which stands alone as a significant algorithmic contribution to the problem of Lipschitz adaptivity - an active area within the online learning community. We further elaborate on this point in our response to Reviewer FioB.\n\n$\\textbf{Comment}:$ *The result for the COCO setting is attained at the cost of paying a computational complexity.*\n\n \n$\\textbf{Response}:$ We emphasize that the $O(T^d)$ complexity applies **only to Algorithm 2**, which reduces the COCO problem to an instance of Prediction with Experts Advice problem (PEA) with a large number of experts. Recognizing this computational cost, we further introduce Algorithm 3 - an **efficient** first-order algorithm that achieves strong guarantees under a mild smoothness assumption. This balance between generality and computational efficiency is an important aspect of our contribution.\n\n$\\textbf{Comment}:$ *The technical analysis is not particularly involved.*\n\n\n$\\textbf{Response}:$ One of the key strengths of our work is the development of a clean and elegant analysis that improves upon the best-known bounds for the COCO problem. While our proofs are intentionally streamlined for clarity, the underlying insights, particularly the use of small-loss regret bounds to control CCV, are novel and non-trivial.\n\nSome of the prior works (e.g., [2,3]) rely on complex primal-dual algorithms with intricate analyses. In contrast, our methods are simpler in structure but more effective in outcome - surpassing the state-of-the-art bounds. We believe that achieving improved guarantees through conceptual simplicity reflects depth, not lack of sophistication.\n\n\n$\\textbf{On the formatting issues}:$\nWe thank the reviewer for pointing out the formatting concerns. We will correct the table formatting and address all checklist-related issues in the final version.  \n\n\n$\\textbf{Comment}:$ *Overall, even if the paper is not breakthrough from a technical perspective, I still believe that the results are interesting and that the way the authors combine existing algorithms and techniques to attain the desired theoretical guarantees is valuable.*\n\n$\\textbf{Response}:$ We thank the reviewer for the positive assessment and appreciation of our overall contribution.\n\n\n$\\textbf{References}$\n\n[1] Sinha, Abhishek, and Rahul Vaze. \"Optimal algorithms for online convex optimization with adversarial constraints.\" Advances in Neural Information Processing Systems 37 (2024): 41274-41302.\n\n[2] Guo, Hengquan, Xin Liu, Honghao Wei, and Lei Ying. \"Online convex optimization with hard constraints: Towards the best of two worlds and beyond.\" Advances in Neural Information Processing Systems 35 (2022): 36426-36439.\n\n[3] Yi, Xinlei, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and Karl Johansson. \"Regret and cumulative constraint violation analysis for online convex optimization with long term constraints.\" In International conference on machine learning, pp. 11998-12008. PMLR, 2021."}]

Author rebuttal:

Meta-review: **(a) Summarize the scientific claims and findings of the paper**

For online convex optimization with adversarial constraints (COCO), this paper proposes an online policy that achieves $\tilde{O}(\sqrt{dT}+T^{\beta})$ regret and $\tilde{O}(T^{1-\beta})$ CCV, which can improve upon previous result $\tilde{O}(\sqrt{T})$ for CCV by trading it off with regret, where $\beta$ is a tunabe parameter. Compared to previous work, their method requires additional smoothness assumption. 

**(b) What are the strengths of the paper?**

Under additional assumptions, this paper establishes a tighter CCV bound for the COCO problem. The analysis that combines the small-loss regret bounds with the regret-decomposition framework is novel and insightful. 

**(c) What are the weaknesses of the paper?**

The authors should include the exact regret and CCV bounds for the general case. Compared to prior work, the reported improvement in the CCV bound comes at the cost of a worse regret. This limitation should be stated more clearly.

**(d) Provide the most important reasons for your decision to accept.**

My decision to recommend acceptance is based on the paper’s improved theoretical results and its novel analysis that leverages small-loss regret bounds for the COCO problem. 

**(e) Summarize the discussion and changes during the rebuttal period.**

* **Reviewer D1DS** assigned a positive score and raised no questions. 
* **Reviewer FioB** raised concerns regarding the technical novelty, the optimality of the results, and the feasibility assumptions. 
* **Reviewer 628F** raised concerns about technical novelty, writing clarity, and the significance of the results. 
* **Reviewer NUnN** raised concerns about technical novelty, computation complexity, and the presentation. 

During the rebuttal, the authors addressed the issues from all reviewers. Reviewer D1DS and NUnN maintained the original positive score, and Reviewer FioB and 628F increased the score from negative to positive.
Decision: Accept (poster)