Online Learning under Adversarial Nonlinear Constraints
Authors: Pavel Kolev
Georg Martius
Michael Muehlebach
Venue: NeurIPS 2023 poster (2023)
Keywords: online learning
online convex optimization
constrained optimization
adversarial nonlinear constraints
constraint violation oracle

Abstract: In many applications, learning systems are required to process continuous non-stationary data streams.
We study this problem in an online learning framework and propose an algorithm that can deal with adversarial time-varying and nonlinear constraints.
As we show in our work, the algorithm called Constraint Violation Velocity Projection (CVV-Pro) achieves $\sqrt{T}$ regret and converges to the feasible set at a rate of $1/\sqrt{T}$, despite the fact that the feasible set is slowly time-varying and a priori unknown to the learner. 
CVV-Pro only relies on local sparse linear approximations of the feasible set and therefore avoids optimizing over the entire set at each iteration, which is in sharp contrast to projected gradients or Frank-Wolfe methods. 
We also empirically evaluate our algorithm on two-player games, where the players are subjected to a shared constraint.

Online Learning under Adversarial Nonlinear Constraints
Pavel Kolev'. Georg !2 and Michael Muehlebach'
Maa Planck Institute for Intelligent Systems, Tübingen, Germany
Universsty of Tübingen, Tübingen, Germany
{pavel. fpavel.kolev, georg.martius martius, michael. whc.ee/www.eleeeeccchheeeeeeeena de
Abstract
In many applications, learning systems are required to process continuous non- stationary data streams. We study this problem in an online learning framework and propose an algorithm that can deal with adversarial time-varying and nonlinear constraints. As we show in our work, the algorithm called Constraint Violation Velocity Projection (CVV-Pro) achieves VT regret and converges to the feasible set at rate of 1/VT, despite the fact that the feasible set is slowly time-varying and priori unknown to the learner. CVV-Pro only relies on local sparse linear approximations of the feasible set and therefore avoids optimizing over the entire set at each iteration, which is in sharp contrast to projected gradients or Frank- Wolfe methods. We also empirically evaluate our algorithm on two-player games, where the players are subjected to a shared constraint.
1 Introduction
Today's machine learning systems are able to combine computation, data, and algorithms at unprece- dented scales, which opens up new and exciting avenues in many domains, such as computer vision, computer graphics, speech and text recognition, and robotics [Jordan and Mitchell, 2015]. One the leading principles that has enabled this progress is the focus relatively simple pattern recognition and empirical risk minimization approaches, which mostly rely on offline gradient-based optimization and stipulate that the training, validation, and test data are independent and identically distributed.
Somewhat overlooked in these developments the role of non non-stationarity and constraints [Jordan, 2019]. Indeed, emerging machine learning problems involve decision making in the real world, which typically includes interactions with physical, social, or biological systems. These systems are not only time varying and affected by past interactions, but their behavior is often characterized via fundamental constraints. Examples include cyher-physica systems where constraints are imposed by the laws of physics, multi-agent systems that are subjected to shared resource constraint, reinforcement learning agent that is subjected to safety and reliability constraints. particular, in their seminal work Auer et al. [2002] gave reduction for the multi-arm bandit setting to the full information online optimization setting, by employing the multiplicative weights framework [Littlestone and Warmuth, 1994]. This classical reduction was recently extended by Sun et al. [2017] to the contextual bandit setting with sequential hime-varying: risk constraints.
decision-making
This motivates our work, which is in line with recent trend in the machine learning community towards online learning, adaptive decision-makinn study an online problem with slowly time-varying constraints, governed by the following interaction protocol (see Assumption 1.2). In each time step f, the learner commits a decision x; and then in addition to a loss value fe( with its gradient V f((x)) receives partial information about the current feasible set C, : {xr E R" gx(x)) 2 0). where the constraint function ge gxx is defined as
and online optimization. More precisely, we
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(x..(z)).... 0x)]. The quality of the learner' 's decision making is measured, for every T 2 1, by comparing to the best decision in hindsight w arg min Σi ft(x), that is,
T
T Σ f((tt) 1=1
f((e)
subject to gr(TT) 2
(1)
which will be shown to be bounded by ((VT) for our algorithm. The functions fe and gt. are restricted to Ja E F and Jr E G (as defined in Assumption 1.1) and <>> 0 is an explicit constant.
It is important note that our performance objective (1) is symmetric in the sense that the constraint a E CT applies to both the learner's ' decision æт and the benchmark 27 This contrasts prior work by Neely and Yu [2017], Yu et al. [2017]. Sun et al. [2017], Chen et al. [2017], Cao and Liu [2019] and Liu et al. [2022], where a different notion of constraint violation Σ gr(x)) 2 -co -C is used for the learner, while either a single benchmark 2i.r satisfies 9e (x(:r)) 2 0 for all t E {1...., .T or multiple benchmarks {ar]]=_ satisfy x' E arg gin, fz(r). Unlike (1), different requirements are imposed on the learner and the benchmark(s), which leads to asymmetric regret formulations: fe(r)) - Ei= fe(xf.r) and Et= fe(xz)) - E Se(xr), respectively. Furthermore, as our bound (TT) 2- -c/ VT applies for all T 2 1, it implies the cumulative constraint violation bound in Neely and Yu [2017] up constant factor Σ (x(x)) -c -t= 1/vi -2cVT.
Even more intriguing is the fact that our algorithm is unaware of the feasible sets a-priori, and obtains, at each iteration, only a local sparse approximation of C, based on the first-order information of the violated constraints. The indices of all violated constraints at Iy will be captured by the index set [2x) == {i {1...., m} (z.) 0), while G(rz) == [V,,, (Z))) denotes the matrix whose columns store the corresponding gradients. In order to guarantee a regret of O(VT) in (1) we require the following assumptions.
Assumption 1.1. There exist R. Ly, Lgg > 0: 1) F is a class of convex functions, where every f E F satisfies (x)]] < Ly, Vx E Ban, with || the lg norm and BR the hypersphere of radius R centered at the origin; 2) G is class of concave 8g-smooth functions, where every g satisfies [[Vg(>)]| < Lg, Vr E B4R; 3) The feasible set C, is non-empty and contained in BR for all t.
We note that these assumptions are standard in online optimization [Hazan, 2016, Ch. 3]. The learner's task is nontrivial even in the case where the feasible set is time invariant. the feasible set is time varying, additional assumptions allowed to change. These two assumptions, see Part 2 i) and ii) below, are described by the following interaction protocol between the learner and the environment:
required that restrict the amount that the feasible set is
Assumption 1.2. (Interaction protocol) At each time step L E (1,...,7):
T):
1) the learner chooses dee
2) the environment chooses Js E F and 9t E 9 such that i) [1))(x) 9t 9t- (z)] 0(1(),
uniformly for all x E Ban, with -|- |1>0 the E.o norm, and ii) C, is contained in Q == n where
(x- 2 0} is cone centered at for 1 2 and So = IR" (the situation illustrated in Figure 1, more details are presented Appendix A); 3) the environment reveals to the learner partial information on cost fe(w)). fa(zz) and all violated
S, : {xr E R
constraints (zz). (x.. for i e (xx).
The requirements i) |R 9t -ll O(1/t): and ii) C. C O, restrict the feasible sets that the environment can choose. We note that despite the fact that |19. st = O(1/t), 11g1 gell = (In(t)), which means that the sequence of functions St that defines C2 does not converge in general. As result, C, may evolve in such a way that the initial iterates rr, 22, 2to achieve a large cost compared to minzecr Σt= f((x). as these are constrained by the sets C1. C2....,Co .C.. which may be far away from Cr. The second requirement ii) C, C Q avoids this situation and is therefore key for obtaining an ((V)) regret.
Q Q
C.
C
Z1+1
Figure 1: At each time step. the feasible set C, contained in a polyhedral intersection Qi changes slightly and is only partially revealed.
Our setup differs from traditional online convex optimization [Zinkevich, 2003] in the following two important ways:
2

---

i) The environment chooses not only the functions fo but also the nonlinear constraint functions gt- ii) even if g, time-invariant, i.e. 9t = g for all t the learner has only access local information about the feasible set.
That is, the information about the feasible set is only revealed piece-by-piece and needs to be acquired by the agent through repeated queries of a constraint violation oracle.
We propose an online algorithm that despite the lack of information about the feasible set, achieves (VVT) regret, and will derive explicit non-asy non-asymptotic bounds for the regret and the convergence to Cr. We thus conclude that our algorithm matches the performance of traditional online projected gradients Frank- Wolfe schemes, while requiring substantially less information about the feasible set and allowing it to be time-vrrying Perhaps equally important is the fact that instead of per- forming projections onto the full feasible set each iteration, our algorithm only optimizes over local sparse linear approximation. If constraints are nonlinear, which includes norm-constraing or constraints on the eigenvalues of matrix, optimizing over the full feasible set at each iteration can be computationally challenging.
1.1 Related Work
Online learning has its roots in online or recursive implementations of algorithms,, where due to the piece-by-piece availability of data, algorithms are often analyzed in a non i.i.d. setting. A central algorithm is the multiplicative weights scheme [Freud and Schapire, 1997], where a decider repeatedly chooses between a finite or countable number of options with the aim of minimizing regret. This online learning model not only offers a unifying framework for many classical algorithms [Blum, 1998], but represents a starting point for online convex optimization Hazan [2016], and adversarial bandits [Lattimore and Szepesvári, 2020]. Our approach extends this line of work by allowing the environment to not only choose the objective functions/ ft, but also the constraints gt- Due to the fact that our learner only obtains local information about the feasible set, our work is somewhat related to Levy and Krause [2019], Lu et al. [2023], Garber and Kretzu [2022], Mhammedi [2022], where the aim is to reduce the computational effort of performing online projected gradient steps Frank-Wolle updates. More precisely, Levy and Krause [2019] propose an algorithm that directly approximates projections, while requiring multiple queries of the constraint functions and their gradients. A slightly different constraint violation oracle is assumed in Garber and Kretzu [2022]. where the learner can query separating hyperplanes between given infeasible point and the feasible set. Algorithmically. both Garber and Kretzu [2022] and Levy and Krause [2019] depart from online gradient descent, where the latter computes projections via an approximate Frank-Wolf-type Wolf-type scheme. An alternative is provided by Mhammedi [2022] and Lu et al. [2023], where optimizations over the entire feasible set simplified by querying only set membership oracle based on the Minkowski functional. While our approach also avoids projections or optimizations over the entire feasible set, we introduce a different constraint violation oracle that returns a local sparse linear approximation of the feasible set. We call the constraint violation oracle only once every iteration and do not require two-step procedure that involves multiple oracle calls. In addition, we also allow for adversarial time-varying constraints.
In addition, there has been important recent work that developed online optimization algorithms with constraints. In contrast to the primal formulation of our algorithm, these works are based on primal-dual formulations. where the algorithm is required to satisfy constraints on average,
called
long-term constraints. The research can be divided into two lines of work Mahdavi et al. [2012], Jenatton al. [2016], Yu and Neely [2020] and Yuan and Lamperski [2018], Yi et al. [2021] that use set of weaker and stricter definitions for constraint violations and investigate time-invariant constraints, which contrasts our formulation that includes time-varying constraints. A third line of work by Mannor et al. [2009], Chen et al. [2017], Neely and Yu [2017], Yu et al. [2017], Sun et al. [2017], Cao and Liu [2019], Liu al. [2022] focuses on time- varying constraints, where, however, the following weaker notion of constraint violation is used: Σ ge (x.) 2 -cVT, where refers to time and x, to the learner's 's decision. This metric allows constraint violations for many iterations, long as these are compensated by strictly feasible constraints (in the worst case even with a single feasible constraint with a large margin). In contrast, our algorithm satisfies ge (2xt) 2 -c/v VT for all iterations I E (1,.... .., T), where e is an explicit constant independent of the dimension of the decision variable and the number of constraints. This means that we can explicitly bound the constraint violation at every iteration, whereas infeasible and strictly feasible iterates cannot compensate each other.
3

---

An important distinction to Neely and Yu [2017] is given by our performance metric (see also the discussion in Neely and Yu [2017] and Liu et al. [2022]) On the one hand, the work by Chen et al. [2017], Cao and Liu [2019], Liu et al. [2022] use Σ f((x)) - Ei=1 fe(x() as a performance measure, where the iterates 2, are required to satisfy Σx= (x())) 2 -vvT and the optimal solutions zy satisfy z E arg mcc ft(z). On the other hand, the work by Neely and Yu [2017], Yu et al. [2017], Sun et al. [2017] use Et= f((2z)
f( as a performance measure, where the iterates 24 are required to satisfy Σx=1 (1,)) 2 -cyT and the optimal solution कं. satisfies (x( 2 for all E {1...., ,T. This leads to major asymmetry in the way regret is measured: while the iterates of the online algorithm only need to satisfy a cumulative measure of constraint violation, the benchmark Ti.r. which represents the best fixed decision in hindsight, is required to satisfy all constraints ga (x 2 0 for 1 (1...., ,T-- In contrast, the performance metric introduced in (1) is symmetric and imposes the same constraint E Cr (approximately) learner's decision 2T and (exactly) on the benchmark zi-- These features make our algorithm a valuable addition to the algorithmic toolkit of online constrained optimization.
the
Castiglioni et al. [2022] studied the following asymmetric setting with adversarial environment, benchmark 2.7. belonging to arg mingex Et=r Je(a) subject to + - 2 O, online iterates Ie satisfying } Ei= Ie (24) 2 -O(//TT), and regret Σi= f((z)) - fe (27) S O(VT).
Their benchmark and regret formulation can be obtained as a special case of our formulation with time-averaged constraints, that is, when our gr(xx) is chosen + ΣT= (x)).. In contrast, (ZT)
our iterate 2T satisfics + ( 2 -OL//TT) a constraint that is asymptotically the same the one satisfied by the benchmark 24.- We further note that they introduced parameter = x min min;g[m) (z), which is required to be positive and known to the algorithm for achieving ((VT) regret. Notably p >> 0 implies that the intersection of all feasible sets is non-empty, which is a strong assumption (as is knowledge about the parameter p). In our formulation with time-averaged constraints, Assumption 1.2 reduces to the requirement that the feasible set C. belongs to a polyhedral intersection Qt, which does not require a non-emtpy intersection of all C, (has geometrical interpretation and the assumption 119. 9t ll = (11/t) is automatically satisfied). Thus, there are situations, where the regret bound from Castiglioni et al. [2022] becomes vacuous (for p = 0), while our method still provably achieves ((vT) regret. Additional differences are that Castiglioni al. [2022] considers primal-dual methods and assumes that all constraints are revealed after every iteration, whereas our method is primal-only and has only partial information about all violated constraints. The latter point reduces computation and simplifies projections onto the velocity polyhedron, but requires nontrivial inductive argument for establishing O(VT) regret.
Other relevant related studies have investigated online learning problems with supply/budget con- straints. In these settings, the decision maker must choose sequence of actions that maximizes their expected reward while ensuring that a set of resource constraints are not violated. The process terminates either after pre-specified time horizon has been reached when the total consumption of some resource exceeds its budget. Badanidiyuru et al. [2018) introduced the bandits with knapsacks framework, which considers bandit feedback, stochastic objective and constraint functions. They proposed an optimal algorithm for this problem, which was later improved by Agrawal and Devanur [2014, 2019] and Immorlica al. [2022]. Immorlica et al. [2022] introduced the adversarial bandits with knapsacks setting and showed that an appropriate benchmark for this setting is the best fixed distribution over arms. Since no-regret is no longer possible under this benchmark, they provide no-a-regret guarantees for their algorithm.
An important special case of our online learning model arises when the environment is represented by an adversarial player that competes with the learner. This corresponds to a repeated generalized Nash game due to the constraint that couples the decisions of the learner and its adversary. If the adversary plays best response, the resulting equilibria are characterized by quasi-variational inequalities [Facchinei and Kanzow, 2007] and there has been important recent work, for example by Jordan et al. [2023]. Kim [2021], Facchinei and Kanzow [2010] that proposes different gradient and penalty methods for solving these inequalities. Our approach adopts different perspective, rooted in online learning, which allows us to derive non-asymptotie convergence results for first-order gradient-bass based algorithm that can be implemented in a straightforward manner. Our approach is also inspired by the recent work of Muchlebach and Jordan [2022], who propose a similar algorithm for the offline setting.

---

1.2 Main Contributions
We give an online optimization scheme under unknown non- non-linear constraints that achieves an optimal (( (VVT) regret and converges to the latest feasible set at rate of O(1/vT). There are two variants of our problem formulation: The first deals with situations where constraints are unknown but fixed, the second allows constraints to be chosen in a varying and adversarial manner.
Our algorithm, named Constraint Violation Velocity Projection (CVV-Pro), has the following features:
1. It assumes access to new type of oracle, which input zt, returns partial information all currently violated constraints. Namely, the value gt, and the gradient (xte) for all E [xxe).
2. It projects an adversarially generated negative cost gradient V f((e)) onto velocity polyhedron V. (are) == {u E Th"" [V=)( 2 -xg) Vi E [(x:)) Due to the linear and local structure of V. (zt), the projection can be computed efficiently.
3. In contrast to standard online methods that project in each round a candidate decision onto the feasible set, our method trades off feasibility for efficiency. particular, produces sequence of decisions that converges rate of O(L/VT) the latest feasible set.
4. Our method handles time-varying adversarial constraints Jt. provided a decreasing rate of change | 9o (1/tt) and that each feasible set C, belongs Q (see Assumption 1.2). As show in Section 3.1, an important special case where the assumption of decreasing rate of change is satisfied is given by gr = Ej=1 1 Øj. i.e., when represents an average of constraints Gr over time.
1.3 Outline
Section 2 describes our algorithm and considers the situation where Ir is time invariant. This sets the stage for our main results in Section 3 that provide regret guarantees for our new online convex optimization setting with non-stationary, nonlinear, and unknown constraints. An important and interesting application of our algorithm are generalized Nash equilibrium problems, as will be illustrated with a numerical experiment in Section 4. The experiment will also highlight that the numerical results agree with the theoretical predictions.
2
Online learning under unknown, time-invariant, and nonlinear constraints
2.1 Online Gradient Descent
Online gradient descent [Hazan, 2016, Ch. 3.1] is a classical and perhaps the simplest algorithm that achieves optimal O(VT) regret for the setting of a compact, convex, time- invariana, and priori known feasible set. consists of the following two operations: i) 3c+1 = H2 - 77t fe(z)) takes a step from the previous point in the direction of the previous cost gradient; and ii) 2r+1 1 Proic projects y back to the feasible set C, as J/++1 may be infeasible.
In this section, we generalize the online gradient descent algorithm to the setting where the feasible set is unknown a priori and has to be learned through repeated queries of constraint violation oracle that only reveals local information.
2.2 Overview
In Section 2.3, present the pseudo code of our algorithm. In Section 2.4, give structural result showing that Algorithm under Assumption 1.1 and a bounded iterate assumption guarantees an optimal O (vVT) regret and converges to the feasible set at a rate of O1/v/T). In Appendix E, show that the bounded iterate assumption be enforced algorithmically, by introducing an additional hypersphere constraint that attracts the sequence {xx (1:)121 to a fixed compact set.
2.3 Constraint Violation Velocity Projection (CVV-Pro)
We present below the pseudocode of Algorithm for a fixed horizon length T, as it is standard in the literature [Hazan, 2016]. However, we note that our algorithm is oblivious to the horizon length T, i.c., it can run for any number of iterations without knowing I' a priori.
5

---

ge
5 (z4)
ge+)
Tt+1 24 + 14
Virg (1x)
(1x)
(((a))
D+++
96.5
8+1
Figure 2: Illustration of the proposed (CVV-Pro) algorithm. Left: the constraint 9t., is violated by the current solution 22. The cost gradient fiss)) is projected onto the hyperplane (moved by -agt., (xx)) with normal vector (æx). This yields (see Section 2.5), and results in the velocity projection (n 1 for clarity).
Right: next iteration with updated 2, where both and g are changed. Then the procedure is applicd recursively.
Algorithm Constraint Violation Velocity Projection (CVV-Pro)
1: Requirements: See Assumption 1.1
2: Input: 0
3: Initialization: Step sizes {n = avi 1
4: for t 1 to T do
5: Play 2i and observe:
6: cost information fa(e),, (1ar)) and constraint information (1x(2))) Vol(t)))
7:
Construct the velocity polyhedron as follows:
(a( == {u E R" [V))(=))] v -ag((a)), Vi [(x:))
8: Solve the velocity projection problem: v arg min 1ll Vf((2)]]
9: Update: Tz+1 2x 7/20t
10:
end for
Let E C be an arbitrary decision. We show in Claim 2.2 that a<x - 24) (a,)). Hence, the velocity polyhedron Va (2re is always non-empty and well defined.
2.4 Structural Result
Here, we show that Algorithm under Assumption 1.1 and a bounded iterate assumption, guarantees an optimal (VTT) regret and converges to the feasible set at a rate (1IVTT). The bounded iterate assumption will be removed subsequently, which however, will require more complex analysis.
Theorem 2.1 (Structural). Suppose Assumption 1.1 holds and in addition i; E BR for all t E {1...., T}. Then, on input a LF RR Algorithm with step sizes d avt guarantees the following for all Z21 1: (regret) Σt Jz(xx) min
Σr
1= f((x) S 18LFRVT;
(feasibility) g((x)) 2 -
La R
23g
R
for all I E (1...., T} and i E (l....,m).
J
2.5 Proof Sketch of Theorem 2.1
Our analysis establishes, in two steps, an important geometric property that connects the convex costs and the concave constraints via the velocity polyhedron Va(2,), More precisely, show that the inner product -r](x;) (xz. 2,) < 0 for all t E {1...., T). This property will be crucial for deriving the regret and feasibility bounds.
In the first step, we leverage the constraints' concavity and show that the vector a(x) xx)) belongs the velocity polyhedron (z(z)).
Claim 2.2. Suppose gi is concave for every i (1....,m), Then a(x - x1) E Va(z:) for all C. In addition, & int(C) implies (x),(x;)] T [x 2x] 2 for all x E C.

---

Proof. Let r E C be an arbitrary feasible decision, satisfying (x) 2 0 for all i E {l....mm) Since 9i is concave, we have (x())) + [Vg, ( [ mı] 2 9: (x( 2 0 and thus [Vg, [x: mi (x,). The second conclusion follows by 2t & iC), which implies gi (z+ 0.
In the second step, show that r. (are x²) S 0, where r; U + (e( is such that -r; belongs to the normal cone NVv((.)((r) (1)) of the velocity polyhedron (1+) evaluated at the projection it.
Lemma 2.3 (Main). Let be the projection of - -V Vx((z)) onto the polyhedron (xz) such that 2/- - (x+) E (at), where -tt E (v.. Then, -r (x - -x) S for all x CC.
Proof. By definition, the normal cone Nv, (1z) is given by {u E R" u uu ve) S 0, Ve E V. (ar)). Then, by construction -rx (=.) (vx) and thus it holds for every E Va( that -r, [V m]] I O. The proof proceeds by case distinction:
Case 1. Suppose xe is in the interior C. Then, (1a) = 0. which implies Vf((())) E Va(1:) IR
and thus Fi- = 0.
Case 2. Suppose xe is on the boundary outside of C, i.e., [(x))) A 0. By Claim 2.2, have [2,) [z xz] 2 0 for all C. By construction, U/ (z)) and thus v(x) + 2,
V. (zx). The statement follows by applying = v(x) to - [u e, S O.
L
Regret. To establish the first conclusion of Theorem 2.1 (regret), we combine the preceding geomet- ric property with the analysis of online gradient descent. Since E F is convex, upper bound the regret in terms of the gradient of ft, namely Σ fe(())) (x7) < Et [Vf((z)]] (x+ - x
and then we show that the following inequality holds
(((()) (x+ 2
11t ||ell
=
ry
T (xz 2T)) + | - 1: - || - 21
2
217
|1 x 1|2
|,1+1 - 13711
(2)
21/s
Moreover, in Appendix (see Lemma D.2), we upper bound the velocity ||va]| S a - x4
fa Combining Assumption 1.1 and x, E Ba yields uniform bound ||0:|| S Va. where for a = LF/ R we set V. == 4bz. The desired regret follows by a telescoping argument and by convexity of the cost functions Sa F..
Feasibility. For the second conclusion of Theorem 2.1 (convergence to the feasible set at a rate of 1/VT), we develop a non-trivial inductive argument that proceeds in two steps. In Appendix D (see Claim D.6), we give structural result that bounds the constraint functions from below. In particular, for every i E [xx;)) we have 9 (I1+1) 2 (1 - (1)) - 1/ y/ 3g and for every i g T(x;) it holds that (x(+1)) -7 Va VaBg/al.
Using an inductive argument, we establish in Appendix D (see Lemma D.5) the following lower bound: gı(zz)) > -Citt where e 2Va (Lg + Va.8/aa. Choosing a Ly/ R implies that Va 4Ly. Then, the desired convergence rate to the feasible set follows for the step size 1) av? since
2Va
Log + BgVa = -8
Lg R
R Vi
-cn = avi
43g
3 Online Learning under Adversarial Nonlinear Constraints
3.1 Problem Formulation
In this section, we consider an online optimization problem with adversarially generated varying constraints. More precisely, at each time step t, the learner receives partial information on the current cost Jt and feasible set C, and seeks to minimize (1). To make this problem well posed, we restrict the environment such that each feasible set C. is contained in Q. (see Section 1) and the rate of change between consecutive time-varying constraints decreases over time, We quantify a sufficient rate of decay with the following assumption.
7

---

Assumption 3.1 (TVC Decay Rate). We assume that the adversarially generated sequence {gi he21 of time-varying constraints is such that for every E Ban and all 2 1, the following holds 1 (x)) 98
I 1- + 33gg] R².
We note that Assumption 3.1 essentially only requires || (2) (x)) 3 O(1/t), as R can be chosen large enough such that the bound is satisfied. Of course, will appear in our regret and feasibility bounds, but it will not affect the dependence
or T (up to constant factors).
An important special case where Assumption 3.1 satisfied, is summarized in the following Lemma. The proof is included in Appendix F (see Lemma F.7 and Lemma F.8).
Lemma 3.2. Suppose the functions It.s satisfy Assumption 1.1 and in addition there is decision Ft,i E BR such that (1,a( = 0 for every 2 and i E {1,...,m).. Then the time-averaged constraints (x,(x))= == Ei=19e. (t,(()) satisfy Assumption 1.1 and Assumption 3.1.
3.2 Velocity Projection with Attractive Hypersphere Constraint
We show in Appendix E that the second assumption in Theorem 2.1, namely, "z,, E BR for all t > can be enforced algorithmically. We achieve this in two steps.
1"
1) Algorithmically, we introduce an additional hypersphere constraint Im+1 (2:) = 2 - || that attracts the decision sequence {2+ 112 to a hypersphere BR and guarantees that always stays inside a hypersphere BAR with slightly larger radius.
More precisely, we augment the velocity polyhedron in Step 3 of Algorithm as follows: ()())) V. (2re) ||=||| & R, otherwise
(=t) = {u E (x() [Vgm+1 (xt)] 0 22 -agm-1
2) Analytically, we give refined inductive argument in Appendix F (see Lemma E.5), showing that 9m+1 (xt) 2 -7R / V
15, ||re|l S 4R and || S 7LF, for all 2 1.
3.3 Main Contribution
Our main contribution is to show that Algorithm with the augmented velocity polyhedron (zz). achieves optimal ((vT) regret and satisfies gr(ZT) 2 (0(/VT) convergence feasibility rate. Due to space limitations, we defer the proof to Appendix F.
Theorem 3.3 (Time-Varying Constraints). Suppose the functions (tle satisfy Assump- tions 1.1, 1.2 and 3.1. Then, on input R, Ly > 0 and E BR, Algorithm I applied with a LF/ R, augmented velocity polyhedron V.) and step sizes 1/: = avt+13 guarantees the following for all
T 2 1: (regret)
Ei f((1)) - min Et f((x)) < R4T,
(feasibility)
(1,)(z1) 2 265
Lo
+ 480
VF+T5 for all t E (1...., T and i E (1....,m}
112
(attraction)
(m)1( 2 27
Ra for all (I.
VE+15'
Our regret analysis in Theorem 3.3 builds upon the following key structural result that generalizes Lemma 2.3 to time-varying constraints. In particular, in Appendix F (see Lemma F.3), we show that given the feasible set Cr Qr, it holds for every I Cr that -r (a Ix) < 0 for all t (T). As a result, similar argument in (2) shows that the regret bounded by O(VT).
T).
Moreover, we note that the linear and quadratic dependence on R in Theorem 3.3 is consistent in length units. Let the radius/ R be of length units f, then the Lipschitz constant Lx. which can be viewed as the supremum over the & norm of the gradient is of 1/6 units, and the 3g smoothness constant (associated with Hessian) is of 1/E² units. This means that the regret bound in Theorem 3.3 has the same units as ft, while the feasibility bound has the same units as gt.
Simulation examples
Two-player games with shared resources are excellent example for demonstrating the effectiveness and importance of our online learning framework. We apply our algorithm and show numerical experiments that support our theoretical findings.
8

---

We choose random instances of a two player game with linear utility and constraints. In particular, we consider the following optimization problem
min max x T Ay subject to C5 + CDU 1 zE y
(3)
where An {x E R"
Di=1 1, 2 0} is the probability simplex. Each component of the utility matrix A R=x" is sampled from the normal distribution and the constraint matrices Cz. Cy E [0, 1|mxx have each of their components sampled uniformly at random from [0. 1].
(a)
(b)
two-norm of crror
regret
100
1 F.
100
2/
V 00
regret
2/v
10-1
50
10
m0
1,000
2,000 3,000 4,000
10
10
10
10
10
rounds
rounds
(c)
max avg violation
10
(el (ta) 1/v2
10
10
10
10a
10a
10s
104
rounds
Figure 3: (Setup) The CVV-Pro algorithm is executed on five random instances of the two-player game with shared resources (Section 4.1). The thick line is the mean and the thin lines indicate the minimum and the maximum over the five runs. (a) The regret follows the predicted O(VT) slope. (b) The CVV-Pro algorithm achieves a convergence rate of O(1/v[) for the averaged decisions T; := EE=1 Ig towards T In our experiment, we set a == 21 c000- Similar behavior is reported for the averaged decisions y, of the adversary. (c) The maximal constraint violation expressed by min,g/(e,) (x.) converges at a rate of O(1 / /E), as predicted by our theoretical results. (Compute) For the implementation of CVV-Pro have used the MATLAB R2019a numerical computing software. The computation of the experiment takes ahout 4 hours machine with CPU: Intel(R) 17-6800K 3.40 GHz with cores, GPU: NVIDIA GeForce GTX 1080, and RAM: 32 GB.
4.1 Online Formulation
The problem in (3) can be modeled with our online learning framework (1) by choosing costs fe(x) := x Ay, and time-averaged resource constraints gr(x) := + Σ Gr(x), where the function (x(x) : 1- - Thus, the constraint in (3) is included as an average over the past iterations of yr. The strategy for choosing V/. will be described below and, as we will see, the average of y over the past iterations converges. This ensures that the feasible set C, (defined in (1)) is slowly time-varying, while the averages of x, and y over past iterates converge to equilibria in (3). Further, by refined version of Lemma 3.2 (see Lemma F.6 Appendix F), the time- averaged constraints gr(x) satisfy Assumption 3.1.
In each iteration, Algorithm seeks to minimize the online problem and commits decision It. The adversary computes the best response ÿt with respect to the decision I2 by solving arg max A, x Ay. To make the dynamics more interesting, the adversary then commits with probability 0.8 to de and with probability 0.2 to a random decision & i.c., 0.89, + 0.26, where the random variable & is sampled uniformly random from the probability simplex An.
As both players optimize over the probability simplex (z, y E An,) the sequence of decisions fxches is automatically bounded. Thus, we can apply Theorem 3.3 with the original velocity polyhedron, as discussed in Appendix E. We implemented our algorithm with n 1/(avt) and 100.

---

4.2 Experimental Results
We report results from numerical simulations with decision dimension n = 100, m = 10 shared resource constraints, T = 4000 iterations, and five independently sampled instances of the two-player game. The learner's 's regret, depicted in Figure 3a, shows clear correspondence with the theoretical prediction of O(VT). Figure 3b presents the maximal constraint violation -(x)) 1 Σi= gt,(( which follows the predicted O(1/VT) convergence rate. We also conclude from Figure 3c that the learner's 's averaged decisions 2T = + E 2y converge at a rate of O(1/v TT). Similarly, the averaged decisions 3/r of the adversary also converge at rate of O(1/VT) We note that there is little variability in the results despite the different realizations of the matrices A, Cz. Cy.
Contrasting CVV-Pro and Online Gradient Descent In Appendix C, we show that our (CVV-Pro) algorithm outperforms the standard Online Gradient Descent algorithm in the two-player game from above. In particular, our algorithm achieves a lower regret and a runtime improvement of about 60%. Further, the percentage of violated constraints decreases rapidly and plateaus at 20%.
The amount of improvement in execution time likely to be greater for higher-dimensional problems, where fewer constraints tend to be active at each iteration. Moreover, when the constraints are nonlinear, which includes l, norm or spectral constraints, optimizing over the full feasible set can be computationally challenging. In contrast, the velocity projection step in CCV-Pro is always a convex quadratic program with linear constraints, regardless of the underlying feasible set.
Broader Impact
is important to emphasize that our work is theoretical, and the main contribution is to design and analyze novel algorithm that combines techniques from the seemingly distant fields of online convex optimization (online gradient descent) and non-smooth mechanics (velocity space, see Muehlebach and Jordan [2022]). Nevertheless, the list of potential applications includes, but is not limited to: adversarial contextual bandits with sequential risk constraints Sun et al. [201 7]. network resource allocation Chen et al. [2017]. logistic regression Cao and Liu [2019], Liu et al. [2022], ridge regression and job scheduling Liu et al. [2022]. two-player games with resource constraints (Section 4), system identification and optimal control (Appendix B).
6 Conclusion
We propose an online algorithm that, despite the lack of information about the feasible set, achieves (VVT) regret. We further ensure convergence of violated constraint min (or((g((()) (xT), 0} at a rate of (L/V/T) and derive explicit constants for all our bounds that hold for all T 2 1. We thus conclude that our algorithm matches the performance of traditional online projected gradients or Frank-Woo schemes, while requiring substantially less information about the feasible set and allowing the feasible be varying Perhaps equally important is the fact that instead of performing projections onto the full feasible set at each iteration, our algorithm only optimizes over a local sparse linear approximation. We show the applicability of our algorithm in numeric simulations of random two-player games with shared resources.
Acknowledgements
We acknowledge the support from the German Federal Ministry of Education and Research (BMBF) through the Tübingen AI Center (FKZ: 01IS18039B) Georg Martius is member of the Machine Learning Cluster of Excellence, EXC number 2064/1 Project number 390727645. Pavel Kolev was supported by the Cyber Valley Research Fund and the Volkswagen Stiftung (No 98 571). Michael Muehlebach thanks the German Research Foundation and the Branco Weiss Fellowship. administered by ETH Zurich, for the support. We thank anonymous reviewers for comments, which helped improve the presentation of the paper.
10

---

References
Shipra Agrawal and Nikhil R. Devanur. Bandits with concave rewards and convex knapsacks. In ACM Conference on Economics and Computation, 2014.
Shipra Agrawal and Nikhil R. Devanur. Bandits with global convex constraints and objective. Operations Research, 67(5):1486-1022, 2019.
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002.
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. Journal of the ACM, 63(3):1-55, 2018.
Avrim L. Blum. On-line algorithms in machine learning, Online Algorithms: The State of the Art, pages 306-325, 1998.
Xuanyu Cao and K. J. Ray Liu. Online convex optimization with time-varying constraints and bandit feedback. IEEE Transactions on Automatic Control, (177)2666-26800 2019.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Giulia Romano, and Nicola Gatti. unifying framework for online optimization with long-term constraints. In Advances in Neural Information Processing Systems 36, 2022.
Tianyi Chen, Qing Ling, and Georgios B. Giannakis. An online convex optimization approach to proactive network resource allocation. IEEE Transactions on Signal Processing, 65(24):6350-6344, 2017.
Francisco Facchinei and Christian Kanzow. Generalized Nash equilibrium problems. Quarterly Journal of Operations Research, 5:173-210, 2007.
Francisco Facchinei and Christian Kanzow. Penalty methods for the solution of generalized Nash equilibrium problems. SIAM Journal on Optimization, 20(5):2222-255 -2533, 2010.
Yoav Freud and Robert F. Schapire. decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119-13) 1997.
Dan Garber and Ben Kretzu. New projection-fis algorithms for online convex optimization with adaptive regret guarantees. In Conference on Learning Theory, 2022.
Elad Hazan, Introduction online convex optimization. Foundation and Trends in Optimization, 13-4):157-325, 2016.
Nicole Immorlica, Karthik Abinav Sankararaman, Robert E. Schapire, and Aleksandrs Slivkins. Adversarial bandits with knapsacks. Journal of the ACM, 69(6):40:1440:477 2022.
Rodolphe Jenatton, Jim Huang, and Cedric Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. In 33th International Conference on Machine Learning, 2016.
M. I. Jordan. Artificial intelligence the revolution hasn't happened yet. Harvard Data Science Review, 1(1):1-8, 2019.
M. I. Jordan and T. M. Mitchell. Machine learning: Trends, perspectives, and prospects. Science, 349(6245):255222 260, 2015.
Michael I. Jordan, Tianyi Lin, and Manolis Zampetakis. First-order algorithms for nonlinear gen- eralized Nash equilibrium problems. Journal of Machine Learning Research, 24:38:1-38:46, 2023.
Jong Gwang Kim. Equilibrium computation of generalized nash games: A new Lagrangian approach. In 22nd Conference on Economics and Computation, 2021.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithmss Cambridge University Press, 2020.

---

Kfir Y. Levy and Andreas Krause. Projection free online learning over smooth sets. In 22nd International Conference on Artificial Intelligence and Statistics, 2019.
Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):112-6111 1994.
Qingsong Liu, Wenfei Wu, Longbo Huang, and Zhixuan Fang. Simultaneously achieving sublinear regret and constraint violations for online convex optimization with time-varying constraints. Performance Evaluation, 49(3):455, 2022.
Zhou Lu, Nataly Brukhim, Paula Gradu, and Elad Hazan. Projection-free adaptive regret with membership oracles. In International Conference on Algorithmic Learning Theory, 2023.
Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: online convex optimization with long term constraints. Journal of Machine Learning Research, 13(81):2503) ):2503- 2528, 2012.
Shie Mannor, John N. Tsitsiklis, and Jia Yuan Yu. Online learning with sample path constraints. Journal of Machine Learning Research, 10(20):599-509 2009.
Zakaria Mhammedi. Efficient projection-free online convex optimization with membership oracle. In Conference on Learning Theory, 2022.
Michael Muchlebach and Michael I. Jordan. On constraints first-order optimization: view from non-smooth dynamical systems. Journal of Machine Learning Research, 23(256))1-47, 2022.
Michael J. Neely and Hao Yu. Online convex optimization with time-varying constraints. arXiv preprint 17Xivv/702.047000 04783, 2017.
Wen Sun, Debadeepta Dey, and Ashish Kapoor. Safety-aware algorithms for adversarial contextual bandit. In 34th International Conference Machine Learning, 2017.
Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and Karl H. Johansson. Regret and cumulative constraint violation analysis for online convex optimization with long term constraints. In 38th International Conference Machine Learning, 2021.
Hao Yu and Michael Neely. low complexity algorithm with o(vt) regret and O(1) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 21(1):1-24 2020.
Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic constraints.
In Advances in Neural Information Processing Systems 30, 2017.
Jianjun Yuan and Andrew Lamperski. Online convex optimization for cumulative constraints. In Advances in Neural Information Processing Systems 31, 2018.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In 20th International Conference Machine Learning, 2003.
12


Reviews:
[{"review_id": "CCrgrHC0Lt", "reviewer": "Reviewer_dZ67", "summary": "CVV-Pro is an online learning framework for non-stationary data streams, with support for handling constraints that may be unknown,  adversarially time-varying, and nonlinear. It doesn't assume that the feasible set is known, but proves that the algorithm still converges to it a rate of 1/sqrt(T). The method is designed to target complex online optimization and adaptive decision making tasks, with applications in two player games with shared constraints. \n\nThe method makes a few assumptions:\n1. It allows constraints to be relaxed and violated. Instead of ensuring feasibility at each step, it makes the violations converge to zero at a rate of O(1/sqrt(T)).\n2. An oracle exists that returns the value and the gradient for all the violated constraints.\n3. Constraints are allowed to vary in time, but at a decreasing rate of change at <= O(1/t)\n\nUnder these constraints, the paper proves that optimal regret at O(sqrt(T)) can be achieved. It is shown to be more efficient than online methods that project the candidates onto the constraint manifold (feasible set), but this may be expected since this method allows for the constraints to be actually violated, which would certainly reduce the loss faster.\n", "questions": "1) I don't understand 2.ii in L61. If Q_t = U(Q_t, S_t), and Q_0 is already R^n, how does this tell us anything useful? It just keeps getting a union of R^n with its subsets, which makes all Q_t's equal to R^n? I don't understand how Fig 1 clarifies this. I think either the union is wrong, or the initial condition. 2.i in L60: were these supposed to be g_t(x_t) instead of g_t? This makes it look like g_t's are converging, but the paper says in L68 that we should \"Note that ||g_t-g_1|| = O(ln(t))\", so it's not necessarily converging (but how do we \"note\" that?). The paper says that assumption 2.ii avoids this situation, but because I don't understand what 2.ii tries to achieve with the union, I don't get this part. I understand in essence what the paper tries to do, but I can't make what I read match what I understand.\n\n2) What is the difference from using the constraint gradients directly to update x_t a la gradient descent? Why do you think this is a better method?\n\n3) Why not make online gradient descent also relaxed so that projections are allowed to violate the constraints by a threshold, provided losses are better? That would give a more apple to apple comparison. \n", "limitations": "Like I mentioned above, I think the main limitation comes from all the assumptions (constraint have accessible gradients, vary at a decreasing rate, and can be violated). As the paper only provides a couple of artificial two player games in experiments, it's not clear how limited the actual impact of this work is.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\nThis is my understanding of the method: Similar to online gradient descent, the method gets the losses associated with x_t. But instead of projecting on the right constraint manifold (because we may not know it), the paper assumes that we can compute or get the gradients for each constraint. While the gradients could also be used directly (by turning constraints into soft regularizers), instead the method constructs a polytope from points that are shifted versions of x_t, by the value of the feasibility loss (g_t) in the direction of its gradient, scaled by a hyperparameter. So, in essence it is very similar to gradient descent (which would simply take the average of these points), but then it effectively projects the loss gradient onto this polytope to retrieve an update direction, which is then scaled by a step size and added to x_t.\n\nThis may go around the issue of having very complex constraint manifolds, where a direct projection may not be possible.", "weaknesses": "1) The paper is not easy to read, as a lot of the variables and concepts are not introduced linearly.\n2) Assumptions may be making the applicable problems very artificial, which takes away from the impact\n3) Figures need a bit more polish as they help a lot with understanding the main idea behind the paper.\n4) Experiments are pretty weak.\n5) No comparison with pure gradient descent\n\nDetails:\n1) The paper is not easy to read, as it sometimes skips introducing crucial variables. The reader needs to read ahead and jump back and forth to understand everything. For instance, g_t(x) is not explicitly defined on L30 (although clear from context later on). The reader can only guess that it is some sort of feasibility function. Confusingly x^* doesn't have a time index in Eq 1. L_F is not introduced in L50, presumably a smoothness index. B_70R in L50 is not explained (where does 70 come from?). The paper mentions that these assumptions are standard in online optimization literature, but skipping these details makes it hard for a new reader to understand the paper.\n\n2) It's very hard to make sense of all the assumptions the paper makes. Does allowing to violate constraints make sense? Does it make sense to assume that we have access to the gradients of the constraints? Does allowing the constraints to vary at decreasing rates correspond to any realistic setting for a practical problem? It feels like the paper is attempting to come up with an optimal algorithm for a problem that doesn't exist.\n\n3) I didn't understand Figure 1 at all. Figure 2 does almost a good job in explaining the method, but it is too imprecise. The arrows look hand drawn, and the actual area that we should focus on is very small.\n\n4) Experiments consist of artificially created two player \"games\", simulated a handful of times, and compared against a method that does assume constraints should not be violated. It's not clear to me where the real impact lies. The paper mentions tons of related work, including ones it was \"inspired from\", but there is no apple to apple comparison of any sort. The only results show that for the artificial setting the authors picked, their proof is consistent with the simulated results.\n\n5) Since the method has access to the gradients, and allows violating the \"constraints\", a much simpler baseline would be to simply add the constraint gradient losses to the gradient descent. This is already commonly done in other fields, and allows for efficient optimizers like Adam to be used. Since they also have gradients, constraints can also be time varying and nonlinear, with unknown feasible sets. Without comparing against this simple and powerful baseline, I'm not sure I understand the value of this method. \n\nFor instance, spectral normalization of the operators is known to help with training GANs, and it can either be done by explicit normalization, or by adding soft regularizers that pull the solution toward the right manifold. The papers that try these two methods are:\nRegularizer: (Yoshida & Miyato 2017) \" Spectral norm regularization for improving the generalizability of deep learning\"\nNormalizer: (Miyato et. al) \"Spectral normalization for Generative Adversarial Networks\".\nThe second paper mentions how normalization (projection) results in sample data dependent gradients unlike the regularizer (Section 2.1), which proves to be superior. This would be an interesting framework to compare the proposed method to these baselines. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable suggestions and constructive feedback.\nWe answer the raised questions below.\n\n**Weaknesses**\n\n1.1 \"The paper is not easy to read ... can only guess that it is some sort of feasibility function.\"\nFollowing the reviewer's comments, we have reorganize and improved the presentation in lines 29-31: \"... constraints, governed by the following interaction protocol (see Assumption 1.2). \nIn each time step $t$, ... $\\mathcal{C}\\_t:=\\\\{x\\in \\mathbb{R}^n\\~|\\~g\\_t(x)\\geq0\\\\}$, where the constraint function $g_t(x)$ is defined as $[g_{t,1}(x),\\dots,g_{t,m}(x)]$.\"\n\n1.2 \"Confusingly $x^*$ doesn't have a time index in Eq 1.\"\nAlthough it is a standard notation in online convex optimization [Hazan 2016] to omit the time dependence for the optimal solution, to improve the clarity, we will add the time index notation.\n\n1.3 \"$L_F$ is not introduced in L50, presumably a smoothness index.\"\nAssumption 1.1 now reads \"There exist $R,L_{\\mathcal{F}},L_{\\mathcal{G}}>0$ ...\n\n1.4 \"$B_{70R}$ in L50 is not explained (where does 70 come from?).\"\nIn Section 3.2, we algorithmically enforce that any decision sequence generated by the learner is attracted to a hypersphere of radius $R$ and more importantly always stays inside a hypersphere with a slightly larger radius $4R$, see lines 278-279.\n(In fact, see lines 28-39 in the appendix, we provide a refined analysis that reduces the radius $70R$ to $4R$.)\nThis property is crucial for establishing a uniform bound on the velocity, which in turn allows us to obtain a $\\sqrt{T}$ regret (lines 238-239).\nWe added a short discussion with the appropriate reference.\n\n2.1 \"Does allowing to violate constraints make sense?\"\nThe constraints are unknown, time-varying and only partial information about them is revealed to the learner.\nMoreover, the learner cannot ensure that $x_t\\in\\mathcal{C}_t$, since the environment reveals a feasible set $\\mathcal{C}_t$ once $x_t$ is committed.\n\n2.2 \"Does it make sense to assume that we have access to the gradients of the constraints?\"\nUnlike previous work (lines $\\\\{119,120,123\\\\}$), which requires full knowledge of all constraint functions, CVV-Pro requires only partial information for all *violated* constraints.\nIn addition, it seems natural to us that the environment can compute derivatives of the violated constraints, as they are typically known analytically.\n\n2.3 \"Does allowing the constraints to vary at decreasing rates correspond to any realistic setting for a practical problem?\"\nAll previous work (line 123) makes certain slowly time-varying assumptions.\nFor further discussion, see our response 2. to (TfpV) and 4. to (pGFm).\n\n2.4 \"It feels like the paper is attempting to come up with an optimal algorithm for a problem\nthat doesn't exist.\"\nWe give the first online algorithm for the challenging setting where the constraints are unknown, slowly time-varying, and only partial information about their violations is revealed.\nThere are already interesting applications, as mentioned in our global response.\nIn addition, we believe that new applications will emerge, similar to the applications of bandits that were first studied in theory decades ago and later applied in practice in areas such as recommendation systems and Internet traffic routing.\n\n3 \"I didn't understand Fig.1 at all. Fig.2 does almost a good job...\"\nAn additional figure for explaining the Assumption is presented in the rebuttal pdf file (which will likely only fit into the appendix) and a modified version of Fig.2 is also provided.\n\n4 \"artificially created two player games; where the real impact lies; no apple to apple comparison...\"\nIt is important to note that the constraints are unknown and only partial information (violations) about them is revealed to the learner. \nIn contrast to primal-dual methods (in related work), we give a primal-only algorithm that tackles a different problem formulation using only partial information. \nWe cannot compare to them, as these methods are not applicable. \nSee also answer to Question 1 of (9WyZ).\n\n5 \"a much simpler baseline would be to simply add the constraint gradient losses to the gradient descent...\"\nThe short answer is: standard online optimization methods cannot efficiently tackle this setting. In particular, in penalty methods the multiplier for constraint violations might need to be chosen arbitrarily high such that regret bound will be vacuous. \nHowever, a recent line of work tackles this problem algorithmically, but their scope is different: either they consider time-invariant constraints (lines 119-120) or a non-symmetric notion of constraint satisfaction and benchmark (lines 123-139).\nSee also answer to Question 1.1 to (9WyZ).\n\n**Questions**\n\n1.1 \"I don't understand 2.ii in L61 ... either the union is wrong, or the initial condition.\"\n\"... I don't understand what 2.ii tries to achieve with the union ...\"\nWe apologize for the typo. The union should be replace with intersection, see the Assumption part of the global response.\n\n1.2 \"2.i in L60: were these supposed to be $g_t(x_t)$ instead of $g_t$?\" \nIt now reads $\\Vert g_{t}(x)-g_{t-1}(x)\\Vert_{\\infty} =\\mathcal{O}(1/t)$ for all $x\\in\\mathcal{B}_{4R}$.\n\n1.3 \"This makes it look like $g_t$'s are converging, but ...\"\nThe series $\\sum_{i=1}^{n}1/i \\approx \\ln(n)$ diverges. \nFurther justification are provided in our response 4. to (pGFm).\n\n2. \"What is the difference from using the constraint gradients directly to update $x_t$ a la gradient descent? Why do you think this is a better method?\"\ni) See our response to Weaknesses 5.\nii) CVV-Pro is a  primal-only algorithm with non-asymptotic regret and convergence guarantees, i.e., for every iteration $t$. \nAlso, the velocity polytope (due to linear constraints) admits an efficient projection computation.\n\n3. \"Why not make online gradient descent also relaxed ... That would give a more apple to apple comparison.\"\nSee our response to Weaknesses 5."}, {"review_id": "E8QUX2ibaq", "reviewer": "Reviewer_7SGB", "summary": "The paper studies a constrained online learning problem. The considered problem has a notion of constraint violation which is different from previous online learning problems. Also, the environment chooses not only a cost function but also a constraint function at each round. The algorithm can observe the cost function and the violated constraint function after playing each action. The authors propose an algorithm called CVV-Pro to solve this problem for both time-invariant and adversarial nonlinear constraints. The algorithm projects the gradients into a constructed velocity polytope in each step. The analysis shows that regret is sublinear and the constraint violation decreases with $O(1/\\sqrt{t})$ for each round $t$.", "questions": "Please see the questions in the Weakness part. Other questions are listed as below.\n\n1. Does the constraint violation bound cover the cumulative constraint violation bound in [1]?\n\n2. In Assumption 1.2, why can $\\mathcal{C}_t$ be contained in $\\mathcal{Q}_t$?\n\n3. In Theorem 3, what is the intuition of the attraction?", "limitations": "The authors may need to address why  Assumption 1.2 and Assumption 3.1 are reasonable. ", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": " The paper considers a novel constrained online learning problem where the environment chooses both the cost function and the constraint function. The proposed algorithm does not require the knowledge of the horizon length $T$ in advance. The paper bounds a new notion of the the constraint violation. The conclusions and the proof sketches are clearly presented. The proposed algorithm may be of interest by the community.", "weaknesses": "The paper can be improved in the following points:\n\n- The time-varying constraints are also considered in [1,2,3]. Thus, it is not appropriate to claim that the setup differs from traditional OCO in terms of the time-varying constraint function.\n\n- Although the considered constraint in (1) requires the constraint for the last round. The previous cumulative constraints [1] should also imply this. \n\n- The bound of constraint violation relies on Assumption 1.2 which requires the change of constraint function shrinks with time and the constraint set $\\mathcal{C}_t$ is contained in $\\mathcal{Q}_t$. It would be better to explain why the two assumptions are reasonable.\n\n\n\n[1] Neely, M.J. and Yu, H., 2017. Online convex optimization with time-varying constraints. arXiv preprint arXiv:1702.04783.\n[2] Yu, H., Neely, M. and Wei, X., 2017. Online convex optimization with stochastic constraints. Advances in Neural Information Processing Systems, 30.\n[3] Cao, X. and Liu, K.R., 2018. Online convex optimization with time-varying constraints and bandit feedback. IEEE Transactions on automatic control, 64(7), pp.2665-2680.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable suggestions and important remarks.\nWe answer the raised questions below.\n\n**Weaknesses**\n\n1. \"The time-varying constraints are also considered in [1,2,3]. Thus, it is not appropriate to claim that the setup differs from traditional OCO in terms of the time-varying constraint function.\"\nWhile exhibiting certain similarities upon initial observation, prior performance measures are quantitatively different.\nOn the one hand, the work by  Chen et al. [2017], Cao and Liu [2019], Liu et al. [2022] use $\\sum_{t=1}^{T} f_t(x_t) - \\sum_{t=1}^{T} f_t(x_{t}^{\\star})$ as a performance measure, where the iterates $x_t$ are required to satisfy $\\sum_{t=1}^{T} g_t(x_t) \\geq -c \\sqrt{T}$ and the optimal solutions $\\\\{x\\_{t}^{\\star}\\\\}\\_t$ satisfy $x_{t}^{\\star}\\in\\arg\\min_{x}\\\\{f_t(x) : g_t(x)\\geq 0\\\\}$.\nOn the other hand (lines 123-139), the work by Neely and Yu [2017], Yu et al. [2017], Sun et al. [2017]  use $\\sum_{t=1}^{T} f_t(x_t)- \\sum_{t=1}^{T} f_t(x^{\\star})$ as a performance measure, where the iterates $x_t$ are required to satisfy $\\sum_{t=1}^{T} g_t(x_t) \\geq -c \\sqrt{T}$ and the optimal solution $x^{\\star}$ satisfies $g_t(x^{\\star})\\geq 0$ *for all* $t\\in\\\\{1,\\dots,T\\\\}$.\nThis leads to a major asymmetry in the way regret is measured: while the iterates of the online algorithm only need to satisfy a cumulative measure of constraint violation, the benchmark $x^{\\star}$, which represents the best fixed decision in hindsight, is required to satisfy *all* constraints $g_t(x^{\\star})\\geq 0$ for $t=\\\\{1,\\dots,T\\\\}$. \nIn contrast, our performance metric is symmetric and imposes the same constraints on the learner as well as the benchmark $x^*$ (soundness is ensured by the slowly time-varying assumption). \nIn particular, for every $T\\geq1$ (as is unknown), let $\\mathcal{C}\\_T:=\\\\{x\\in \\mathbb{R}^n\\~|\\~g_T(x)\\geq0\\\\}$, then we seeks to optimize $\\sum\\_{t=1}^{T} f\\_t(x\\_t) - \\min\\_{x^* \\in \\mathcal{C}\\_T} \\sum\\_{t=1}^{T} f\\_t(x^*)$ subject to $g_T(x_T)\\geq - \\frac{c}{\\sqrt{T}}$.\n\n2. \"Although the considered constraint in (1) requires the constraint for the last round.\nThe previous cumulative constraints [1] should also imply this.\"\nWe respectfully disagree.\nAs explained above Neely and Yu [2017] focuses on time-varying constraints, where, however, the following weaker notion of constraint violation is used: $\\sum_{t=1}^{T} g_t(x_t) \\geq -c \\sqrt{T}$.\nThis metric allows constraint violations for many iterations, as long as these are compensated by strictly feasible constraints (*in the worst case even with a single feasible constraint with a large margin*).\n\n3. \"The bound of constraint violation relies on Assumption 1.2 which requires the change of constraint function shrinks with time and the constraint set $\\mathcal{C}_t$ is contained in $\\mathcal{Q}_t$. It would be better to explain why the two assumptions are reasonable.\"\nSee the Assumption part of the global response.\n\n**Questions**\n\n1. \"Does the constraint violation bound cover the cumulative constraint violation bound in [1]?\"\nOur constraint violation bound $g_T(x_T)\\geq - \\frac{c}{\\sqrt{T}}$ for all $T\\geq1$, implies the cumulative constraint violation bound in Neely and Yu [2017]\n$\\sum_{t=1}^{T}g_{t}(x_{t})\\geq-\\sum_{t=1}^{T}\\frac{c}{\\sqrt{t}}\\geq-2c\\sqrt{T}$.\n\n2. \"In Assumption 1.2, why can $\\mathcal{C}_t$ be contained in $\\mathcal{Q}_t$?\"\nSee the Assumption part of the global response.\n\n3. \"In Theorem 3, what is the intuition of the attraction?\"\nAs explained in lines 271-279, we add an additional hypersphere constraint $g_{m+1}(x_{t})=\\frac{1}{2}[R^{2}-\\Vert x_{t}\\Vert^{2}]$ that attracts any decision sequence $\\\\{x_{t}\\\\}\\_{t\\geq1}$ generated by the learner to a hypersphere $\\mathcal{B}\\_{R}$ and guarantees that it always stays inside a hypersphere $\\mathcal{B}_{4R}$ with a slightly larger radius.\nIn fact, see lines 28-39 in the supplementary, we provide a refined analysis, reducing the radius $70R$ to $4R$, which uses step sizes of the form $\\eta_t=1/(\\alpha\\sqrt{t + d})$, for any constant $d\\geq0$.\n"}, {"review_id": "J7JpJNxgoF", "reviewer": "Reviewer_9WyZ", "summary": "This paper considers an online constrained learning scenario, where partial information about the objective and the constraints, which could potentially be time-varying, is available at each time slot. The proposed algorithm, referred to as \"Constraint Violation Velocity Projection,\" constructs a velocity polytope at each time step and updates the decisions based on the solution to a quadratic velocity projection problem. It is shown that the proposed method leads to a $\\mathcal{O}(\\sqrt{T})$ regret and convergence rate of $\\mathcal{O}(1/\\sqrt{T})$ to the feasible set. Numerical results are also provided to corroborate the theoretical contributions.", "questions": "- How does the proposed method compare with primal-dual Lagrangian approaches? Do these approaches completely fail if the feedback received from the environment is limited, as assumed in this work?\n- Are there applications of the proposed algorithm in the context of constrained reinforcement learning with time-varying constraints and (potentially) partial observability? Following my comment under \"**Weaknesses**,\" this might be an area where the proposed algorithm could shine.", "limitations": "Please refer to my comments under \"**Weaknesses**\" regarding the broader impact and application of the proposed algorithm.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The considered problem is interesting and challenging from the perspective of the limited information available to the learning algorithm and the variation of constraints over time.\n- The paper is well written, and the theoretical analyses of the proposed method could be of interest to the NeurIPS audience.", "weaknesses": "This is mostly a theoretical piece of work, but it is slightly unclear to me what the broader implications of the proposed algorithm would be. The two-player game experimental results presented in Section 4 are interesting, but I wonder if the authors could highlight at least another example use-case of the proposed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable suggestions and important remarks.\nWe answer the raised questions below.\n\n**Weaknesses**\n\n\"This is mostly a theoretical piece of work, but it is slightly unclear to me what the broader implications of the proposed algorithm would be.\nThe two-player game experimental results presented in Section 4 are interesting, but I wonder if the authors could highlight at least another example use-case of the proposed algorithm.\"\n\nAs pointed out by the reviewer, our work is theoretical and its the main contribution is to design and analyze a novel algorithm that combines techniques from the seemingly distant fields of online convex optimization (online gradient descent) and non-smooth mechanics (velocity space).\nHowever, we agree that potential applications are important. \nHere we provide a few and give a more detailed explanation in answering to question 2 below: \nadversarial contextual bandits with sequential risk constraints [Sun et al., 2017], network resource allocation [Chen et al., 2017], logistic regression [Cao and Liu, 2019, Liu et al., 2022], ridge regression and job scheduling [Liu et al., 2022], 2-player games with resource constraints (Section 4), system identification and optimal control. \n\nWe will update the manuscript accordingly. \n\n**Questions**\n\n1.1 \"How does the proposed method compare with primal-dual Lagrangian approaches?\"\n\nThere are two major differences between previous work on unknown and slowly time-varying constraints and ours.\nThe problem formulation in Chen et al. [2017], Neely and Yu [2017], Yu et al. [2017], Sun et al. [2017], Liu et al. [2022] differs in the definition of performance metrics in terms of the benchmark(s) used in the regret and constraint violation criteria, see our response to 7SGB Weaknesses 1.\nMoreover, it assumes that on each time step all constraints are fully revealed to the learner.\nMore specifically, the above primal-dual approaches maintain a dual variable $\\lambda_i\\geq0$ throughout the execution of the algorithm, for every index $i\\in\\\\{1,\\dots,m\\\\}$ corresponding to constraints $\\\\{g_{t,i}\\\\}\\_{t\\geq1}$.\nThat is, in time step $t$, updating the dual variables $\\lambda$ requires information for all constraints $\\\\{g_{t,i}\\\\}\\_{i=1}^{m}$.\n\nIn contrast to prior work, we consider the setting in which *only partial information about the all violated constraints* is revealed to the learner.\nFurthermore, the velocity polyhedral projection allows us to design a primal-only algorithm, that enjoys the following properties:\ni) it requires partial information only for all violated constraints (reducing the number of constraints); and\nii) the velocity projection can be computed efficiently since the constraints are always linear.\n\nWe will make sure that this difference is better discussed in the paper.\n\n1.2 \"Do these approaches completely fail if the feedback received from the environment is limited, as assumed in this work?\"\n\nThe short answer is: the primal-dual Lagrangian approach does not directly extend to the setting of constraint violation oracle, since updating the dual variables requires information for all constraints, in every iteration.\nHowever, it is an interesting open question to extend the primal-dual Lagrangian approach to the setting of only partial information for all violated constraints.\n\n2. \"Are there applications of the proposed algorithm in the context of constrained reinforcement learning with time-varying constraints and (potentially) partial observability? Following my comment under \"Weaknesses,\" this might be an area where the proposed algorithm could shine.\"\n\nThis is an excellent point, which we will discuss in the paper.\nHere are more details about a potential application to system identification and optimal control, where an agent must predict a sequence of actions to minimize costs and satisfy constraints.\nMany real-world systems are subject to wear, tear and drift (e.g., sensors), which naturally leads to non-stationary costs and constraints, corresponding to slowly time-varying functions $f_t$ and $\\\\{g_{t,i}\\\\}\\_{i=1}^{m}$, respectively.\nFurthermore, it is common in optimal control to know analytically both the dynamics model and the cost and constraint functions, so the gradients are naturally available.\nAssuming access to a constraint violation oracle, the above scenario can be cast into our online problem formulation.\nMore specifically, in each episode $t$, an agent $\\phi$ parameterized by weights $\\theta_t\\in\\mathbb{R}^n$ generates a sequence of actions $\\\\{x_{\\ell}\\\\}\\_{\\ell=1}^{H}$ and upon their deployment in the environment, receives a cost value $f_t(\\theta_t)$, gradient $\\nabla f_t(\\theta_t)$ and information for all violated constraints $\\\\{(g_{t,i}(\\theta_t), \\nabla g_{t,i}(\\theta_t)\\\\}\\_{i\\in I(\\theta_t)}$.\n"}, {"review_id": "JsujIC4Uer", "reviewer": "Reviewer_TfpV", "summary": "The paper studies an online learning problem in which the learner aims at maximizing their reward subject to adversarial time-varying nonlinear constraints. The proposed algorithm guarantees a regret upper bound of order $T^{1/2}$ and converges to the feasible set at a rate of $T^{-1/2}$. Intrestingly, the feasible set may be unknown to the learner and slowly change over time. An interesting application described in the paper is computing equilibria in two-players zero-sum games in which players share a common resource. ", "questions": "None.", "limitations": "N.A.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The set-up is very interesting. I particularly appreciated the connection to computing GNEs of some kind. The techniques introduced are novel and may find applications also in related problems. ", "weaknesses": "I would add to the related works, when discussing performance metrics, also some pointers to work on online learning with long-term constraints stemming from the literature on bandits with knapsacks. One example is: \"A Unifying Framework for Online Optimization with Long-Term Constraints\" by Castiglioni et al. (NeurIPS 22) It would be nice to see a discussion of their baselines and how they relate to yours. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable suggestions and constructive feedback.\nWe answer the raised questions below.\n\n**Weaknesses**\n\n1. \"I would add to the related works, when discussing performance metrics, also some pointers to work on online learning with long-term constraints stemming from the literature on bandits with knapsacks.\"\n\nFollowing the reviewer's comments, in addition to lines $\\\\{38,128\\\\}$ where we mentioned the work of Sun et al. [6] on safety-aware algorithms for adversarial contextual bandits, we will expand the related work section to include a discussion of the ``Bandits with Knapsacks'' framework.\nIn particular, we will discuss the works by [1-5], see the references below.\n\n2. \"One example is: \"A Unifying Framework for Online Optimization with Long-Term Constraints\" by Castiglioni et al. (NeurIPS 22) It would be nice to see a discussion of their baselines and how they relate to yours.\"\n\nThanks for the excellent point.\nWe have updated the manuscript with a discussion of Castiglioni et al. [2022].\nNext, we bring into context the study by Castiglioni et al. [2022] and discuss how our baseline relates to it.\n\nCastiglioni et al. [2022] studied the following symmetric setting with adversarial environment, baseline $x^{\\star}$ belonging to $\\arg\\min_{x\\in\\mathcal{X}}\\sum_{t=1}^{T}f_{t}(x)$ subject to $\\sum_{t=1}^{T}g_{t}(x)\\geq0$, iterates $\\{x_t\\}$ satisfying $\\sum_{t=1}^{T}g_{t}(x_{t})\\geq-o(T)$, and regret $\\sum_{t=1}^{T}f_{t}(x_t)-\\sum_{t=1}^{T}f_{t}(x^{\\star})$. \nTheir baseline and regret formulation can therefore be obtained as a special case of our formulation with time-averaged constraints, that is, when our $g_T(x)$ is chosen as $\\frac{1}{T}\\sum_{t=1}^T g_t(x)$. \nWe further note that Castiglioni et al. [2022] introduce the parameter $\\rho=\\sup_{x\\in\\mathcal{X}}\\min_{t\\in[T]}\\min_{i\\in[m]}g_{t,i}(x)$, which is required to be positive and known to the algorithm for achieving $\\mathcal{O}\\_{\\rho}(\\sqrt{T})$ regret. \nWe note that $\\rho>0$ implies that the intersection of all feasible sets is non-empty, which is a strong assumption (as is knowledge about the parameter $\\rho$). \nIn our formulation with time-averaged constraints, Assumption 1.2 reduces to the feasible set $\\mathcal{C}\\_t$ belongs to a polyhedral intersection $\\mathcal{Q}\\_t$, which does not require a non-empty intersection of all $\\mathcal{C}\\_t$ (and has a geometrical interpretation; also note that the assumption $\\lVert g_{t}(x)-g_{t-1}(x) \\rVert_{\\infty} = \\mathcal{O}(1/t)$ is automatically satisfied in this case). \nThus, there are situations, where the regret bound from Castiglioni et al. [2022] becomes vacuous (for $\\rho=0$), while our method still provably achieves $\\mathcal{O}(\\sqrt{T})$ regret.\nAdditional differences are that Castiglioni et al. [2022] considers primal-dual methods and assumes that all constraints are revealed after every iteration, whereas our method is primal-only and has only partial information about all violated constraints.\nThe latter point reduces computation and simplifies projections onto the velocity polytope, but requires a nontrivial inductive argument for establishing $\\sqrt{T}$-regret.\n\nIn summary, our paper retains its novelty and importance also in the light of Castiglioni et al. [2022].\n\n**References on ``Bandits with Knapsacks''**\n\n[1] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks.\nJournal of the ACM (JACM), 65(3):1-55, 2018\n\n[2] Shipra Agrawal and Nikhil R Devanur. Bandits with concave rewards and convex knapsacks. In\nProceedings of the fifteenth ACM conference on Economics and computation, pages 989-1006.\nACM, 2014.\n\n[3] Shipra Agrawal and Nikhil R Devanur. Bandits with global convex constraints and objective.\nOperations Research, 67(5):1486-1502, 2019.\n\n[4] Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, and Aleksandrs Slivkins.\nAdversarial bandits with knapsacks. In 60th IEEE Annual Symposium on Foundations of Computer\nScience, FOCS 2019, pages 202-219. IEEE Computer Society, 2019.\n\n[5] Xuanyu Cao and KJ Ray Liu. Online convex optimization with time-varying constraints and\nbandit feedback. IEEE Transactions on automatic control, 64(7):2665-2680, 2018.\n\n[6] Wen Sun, Debadeepta Dey, and Ashish Kapoor. Safety-aware algorithms for adversarial contextual\nbandit. Proceedings of Machine Learning Research, 70:3280-3288, 2017."}, {"review_id": "cjmsroK3lT", "reviewer": "Reviewer_pGFm", "summary": "This paper studies the online convex optimization subject to certain constrains and assumes that such constrains are slowly changing. The main contribution is a $O(\\sqrt{T})$ regret bound under such constrains.", "questions": "Unfortually, I do not have any interesting technical questions for the authors at this point.", "limitations": "No issue with negative societal impact.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "This paper appears to prove some interesting technical results. However, due to its unclear presentation, I find it challenging to fully appreciate the significance of these findings.", "weaknesses": "The presentation of this paper is very confusing, making it difficult to follow even in the introduction. Let me elaborate on the following points:\n\n1. The purpose of introducing the constraints $\\mathcal{C}_t$ for $t < T$ is unclear. From your regret formulation in (1), it appears to only depend on $\\mathcal{C}_T$. Are you assuming that $x_t$ must be selected from $\\mathcal{C}_t$? This doesn't seem to align with Assumption 2.\n2. There is no clear motivation behind the definition of (1). What is the reason for setting the constraints $g(x_T)\\ge c/\\sqrt{T}$?\n3. The set $I(x_t)$ is not well-defined. Where does $m$ originate from?\n4. What is the rationale for assuming $||g_t-g_{t+1}||\\le O(1/t)$? Why not $1/t^2$, $1/\\log t$, or $1/e^t$? How would the results change under these different bounds?\n5. What novel concept does Algorithm 1 introduce? Is it the construction of the velocity polytope?\n6. Can you highlight the main technical originality in your proofs? They appear to be simple applications of the analysis of online gradient descent.\n7. Could you provide some real-world examples where your results can be applied?\n\nConsidering the issues mentioned above, my recommendation leans towards a \"borderline reject.\" The paper lacks clarity in presentation, and several assumptions and definitions are not adequately justified or explained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable suggestions and important remarks.\nWe answer the raised questions below.\n\n**Weaknesses**\n\n1. \"The purpose of introducing the constraints $\\mathcal{C}_t$ for $t<T$ is unclear. ... Are you assuming that $x_t$ must be selected from $\\mathcal{C}_t$? ...\"\n\nCVV-Pro optimizes (1) for every $T\\geq1$, since $T$ is not a priori known to the learner.\nMoreover, the learner cannot ensure that $x_t\\in\\mathcal{C}_t$, since the environment reveals a feasible set $\\mathcal{C}_t$ after $x_t$ is committed.\n\n2. \"There is no clear motivation behind the definition of (1). What is the reason for setting the constraints $g(x_T)\\geq c/\\sqrt{T}$\"\n\nOur formulation in (1) is symmetric and imposes the same constraints on the learner as well as the optimal decision in hindsight.\nSince the optimal solution $x^{\\star}\\in\\mathcal{C}\\_T$ satisfies $g_T(x^{\\star})\\geq0$, we seek to compute a decision $x_T$ that is close to the feasible set $\\mathcal{C}\\_T$, quantitatively $g(x_T)\\geq - c/\\sqrt{T}$, while maintaining small regret.\nFurthermore, as our constraint violation bound $g_T(x_T)\\geq - \\frac{c}{\\sqrt{T}}$ applies for every $T\\geq1$, it implies the cumulative constraint violation bound in Liu et al. [2022]: $\\sum_{t=1}^{T}g_{t}(x_{t})\\geq-2c\\sqrt{T}$.\nSee our answer to question 1 and weakness 1 to (7SGB) for more details.\n\n3. \"The set $I(x_t)$ is not well-defined. Where does $m$ originate from?\"\n\nBased on your comments and those of the other reviewers, we will improve the introduction accordingly. \n\n4. \"What is the rationale for assuming $\\lVert g_t - g_{t+1} \\rVert\\leq O(1/t)$?\nWhy not $1/t^2$, $1/\\log(t)$, or $1/e^t$?\nHow would the results change under these different bounds?\"\n\nThe short answer is: it balances a trade-off between the rate of convergence to the feasible set and the power of the environment to select feasible sets far away from the initial feasible set.\nIt is important to note that the series $\\sum_{i=1}^{n}1/i\\approx\\ln(n)$ diverges, whereas for any $\\epsilon>0$ the series $\\sum_{i=1}^{n}1/i^{1+\\epsilon}$ converges to a constant.\nIn particular, $\\lVert g_t - g_{t+1} \\rVert\\leq O(1/t)$ allows the environment to select a constraint function $g_T$ whose corresponding feasible set is far away from the initial, in the sense that $\\lVert g_1 - g_{T} \\rVert = \\Theta(\\ln T)$.\nOn the other hand, relaxing the upper bound to say $\\lVert g_t - g_{t+1} \\rVert\\leq O(1/\\sqrt{t})$ results in a slower than $1/\\sqrt{T}$ convergence rate to the feasible set.\n\n5. \"What novel concept does Algorithm 1 introduce? Is it the construction of the velocity polytope?\"\n\nThe short answer is yes: the velocity polytope is one of the novelties. However there is more to it:\n\na) We combine techniques from online convex optimization and non-smooth mechanics.\nMore specifically, we substitute the computationally expensive projection problem in the online gradient descent algorithm with a sparse linear velocity projection problem that admits efficient computation;\n\nb) Our algorithm requires in each iteration only partial information about all violated constraints. \nIn contrast, prior works need full information for all constraints;\n\nc) CVV-Pro handles time varying constraints, under the assumption that the constraints are slowly time-varying and the corresponding feasible sets belong to certain polyhedral intersections (see the Assumption part in our global response). \n\n6. \"Can you highlight the main technical originality in your proofs? They appear to be simple applications of the analysis of online gradient descent.\"\n\nWe find the elegance of the proposed geometric arguments particularly appealing. \nA major technical originality is to prove that the velocity (the algorithm's increments) is bounded, which requires the addition of an (ingenious) ``auxiliary\" constraint, and non-trivial inductive arguments. \n\nMore specifically, the main technical contributions are listed below:\n\n**Time-invariant constraints**\n\nWe show that the velocity projection problem is well defined, as \nthe velocity polytope is always non-empty.\nMoreover, we give an important geometric property showing that the inner product $-r_{t}^T(x^{\\star}-x_t)\\leq0$ for all $t$.\nAssuming the velocity is bounded, we can apply the standard OGD analysis to obtain a $\\sqrt{T}$ regret.\nThen, we give a non-trivial inductive argument that yields convergence to the feasible set at a rate of $1/\\sqrt{T}$.\nTo enforce a uniform bound on the velocity, we augment the velocity polytope with an attraction constraint, ensuring that the learner's decision sequence always remains within a hypersphere of small radius.\nUsing a carefully designed inductive argument, see Lemma C.5, we establish an attraction rate of $1/\\sqrt{T}$, bounded decisions and hence bounded velocities.\n\n**Time-varying constraints**\n\nHere, the previous geometric arguments fail because $x_{T}^*$ does not belong to every feasible set $\\mathcal{C}\\_{t}$.\nThis means that the environment can choose a sequence of costs and constraints such that $-r_{t}^T(x_{T}^*-x_t)>0$ for all $t\\in\\\\{1,\\dots,T-1\\\\}$, making the regret bound vacuous.\nTo avoid this issue, we limit the environment as follows.\nWe show in Lemma D.3 that the polyhedral intersection assumption suffices to extend the above geometric property to the time-varying constraint setting, i.e., $-r_{t}^T(x_{T}^*-x_t)\\leq0$ for all $t$.\nMoreover, the slowly time-varying constraint assumption strikes a balance between the convergence to the feasible set and the power of the environment to select feasible sets that are far away from the initial one (see 4 above).\nIn addition, we show in Lemma D.6 that the time-averaged constraints satisfy the slowly time-varying assumption. \n\n7. \"Could you provide some real-world examples where your results can be applied?\"\n\nFor a detailed answer, we refer the reviewer to the broader implications part of our global response."}]

Author rebuttal:
We would like to thank the reviewers for the time they spent reviewing our paper and for their insightful comments.

Several reviewers recognized the novelty of the setting studied and the theoretical guarantees provided, as well as the applicability of our algorithm to related problems.
More specifically:
[problem formulation] "novel constrained online learning problem" (7SGB), "set-up is very interesting" (TfpV), "interesting and challenging from the perspective of the limited information" (9WyZ);
[technical results] "prove some interesting technical results" (pGFm), "bounds a new notion of the constraint violation" (7SGB), "the conclusions and proof sketches are clearly presented" (7SGB);
[algorithm] "effectively projects the loss gradient onto the velocity polytope" (dZ67), "does not require the knowledge of the horizon length in advance" (7SGB).
[application] "appreciated the connection to computing GNEs" (TfpV), "techniques introduced are novel and may find applications also in related problems" (TfpV), "proposed algorithm may be of interest by the community" (7SGB), "theoretical analyses of the proposed method could be of interest to the NeurIPS audience" (9WyZ).

Thank you for the positive feedback.

The main concerns raised relate to the assumptions (dZ67,7SGB,pGFm) and the broader implications of the proposed method (9WyZ,TfpV):

**Assumptions**

We regret that there was a typo in Assumption 1.2 Part 2, the union symbol should have been an intersection, this caused unnecessary confusion. The corrected version reads:

**(Updated)** the environment chooses $f_t\in \mathcal{F}$ and $g_t\in\mathcal{G}$ such that i) $\Vert g_{t}(x)-g_{t-1}(x)\Vert\_{\infty} =\mathcal{O}(1/t)$ for all $x\in\mathcal{B}\_{4R}$, with $\Vert\cdot\Vert\_{\infty}$ the $\ell\_{\infty}$ norm, and ii) $\mathcal{C}\_t$ is contained in $\mathcal{Q}\_t:=\cap_{\ell=0}^{t-1}\mathcal{S}\_{\ell}$, where $\mathcal{S}\_t:=\\{x\in \mathbb{R}^n \~|\~G(x_t)^{\top}(x-x_t)\geq0 \\}$  is a cone centered at $x_t$ for $t\geq1$ and $\mathcal{S}_{0}=\mathbb{R}^{n}$.

(The situation is illustrated in the rebuttal pdf file and will be added to supplementary.)

The reviewers had concerns about the novelty and necessity of the assumptions.
It is important to note that we are considering an online learning problem where the agent is dealing with unknown and time-varying constraints, and the environment reveals information for them after the learner has made a decision.
In contrast to previous work, where all constraints are fully revealed to the learner at each time step, we focus on the more practical setting where the learner has access to only *partial* information about all *violated* constraints.
For this challenging setting, we give the first online algorithm that enjoys provable guarantees and efficient projection computation due to the linear structure of the velocity polytope.

It is crucial to emphasize that in the above setting one has to make assumptions to obtain non-trivial regret and convergence guarantees.
Further justification is provided in our response 2. to (TfpV) and 4. to (pGFm).

We have updated the manuscript to reflect this discussion, as elaborated in the individual responses.

**Broader implications**

It is important to note that our work is theoretical, and the main contribution is to design and analyze a novel algorithm that combines techniques from the seemingly distant fields of online convex optimization (online gradient descent) and non-smooth mechanics (velocity space).
Nevertheless, the list of potential applications includes, but is not limited to: adversarial contextual bandits with sequential risk constraints [Sun et al., 2017], network resource allocation [Chen et al., 2017], logistic regression [Cao and Liu, 2019, Liu et al., 2022], ridge regression and job scheduling [Liu et al., 2022], 2-player games with resource constraints (Section 4), system identification and optimal control.

More specifically, let us elaborate on system identification and optimal control application, where an agent must predict a sequence of actions to minimize costs and satisfy constraints.
Many real-world systems are subject to wear, tear and drift (e.g., sensors), which naturally leads to non-stationary costs and constraints, corresponding to slowly time-varying functions $f_t$ and $\\{g_{t,i}\\}\_{i=1}^{m}$, respectively.
Furthermore, it is common in optimal control to know analytically both the dynamics model and the cost and constraint functions, so the gradients are naturally available.
Assuming access to a constraint violation oracle, the above scenario can be cast into our online problem formulation.
More specifically, in each episode $t$, an agent $\phi$ parameterized by weights $\theta_t\in\mathbb{R}^n$ generates a sequence of actions $\\{x_{\ell}\\}\_{\ell=1}^{H}$
 and upon their deployment in the environment, receives a cost value $f_t(\theta_t)$, gradient $\nabla f_t(\theta_t)$ and information for all violated constraints $\\{(g_{t,i}(\theta_t), \nabla g_{t,i}(\theta_t)\\}_{i\in I(\theta_t)}$.

We will incorporate this discussion about the applicability. 

We believe our answers and changes detailed in the individual responses clarify the questions and address the raised concerns about our work.



Meta-review: This work proposes a method for online learning under adversarial, time-varying, and nonlinear constraints. Under the assumption that the constraints are slowly changing, and given an oracle that reveals partial information of the violated constraints, the CVV-Pro method obtains $O(\sqrt{T})$ regret and converges to the latest feasible set at a rate of $O(1/\sqrt{T})$. The method is then applied to obtain equilibria for two-player zero-sum games. During the discussion, concerns were raised regarding presentation, the assumptions on the slowly-changing constraints, and the broader applicability of the algorithm. These concerns were adequately addressed for the most part, and given the new formulation of the problem and the novel algorithm, I recommend acceptance.
Decision: Accept (poster)