Constrained Online Convex Optimization with Polyak Feasibility Steps
Authors: Spencer Hutchinson
Mahnoosh Alizadeh
Venue: ICML 2025 poster (2025)
Keywords: online convex optimization
online learning
constraints
Primary area: theory->online_learning_and_bandits

Abstract: In this work, we study online convex optimization with a fixed constraint function $g : \mathbb{R}^d \rightarrow \mathbb{R}$. Prior work on this problem has shown $O(\sqrt{T})$ regret and cumulative constraint satisfaction $\sum_{t=1}^{T} g(x_t) \leq 0$, while only accessing the constraint value and subgradient at the played actions $g(x_t), \partial g(x_t)$. Using the same constraint information, we show a stronger guarantee of anytime constraint satisfaction $g(x_t) \leq 0 \ \forall t \in [T]$, and matching $O(\sqrt{T})$ regret guarantees. These contributions are thanks to our approach of using Polyak feasibility steps to ensure constraint satisfaction, without sacrificing regret. Specifically, after each step of online gradient descent, our algorithm applies a subgradient descent step on the constraint function where the step-size is chosen according to the celebrated Polyak step-size. We further validate this approach with numerical experiments.

Constrained Online Convex Optimization with Polyak Feasibility Steps
Spencer Hutchinson'
Mahnoosh Alizadeh
Abstract
mization (Cutkosky al., 2023), and online control (Agar- wal et al., 2019). Furthermore, the OCO problem is directly relevant to various real-world settings, including online ad- vertising (McMahan et al., 2013), internet of things (Chen & Giannakis, 2018), and healthcare (Tewari & Murphy, 2017).
In this work, we study online convex optimiza- tion with a fixed constraint function g Id - R. Prior work on this problem has shown (vT)) regret and cumulative constraint satisfac- tion Σt=19 (xx) < O, while only accessing the constraint value and subgradient at the played ac- tions gxx), (xt). Using the same constraint information, we show a stronger guarantee of any- time constraint satisfaction gxx)) S 0 Vt E [T'. and matching O(VT) regret guarantees. These contributions are thanks to our approach of using Polyak feasibility steps to ensure constraint sat- isfaction, without sacrificing regret. Specifically, after each step of online gradient descent, our algorithm applies subgradient descent step on the constraint function where the step-size cho- sen according to the celebrated Polyak step-size. We further validate this approach with numerical experiments.
Despite the significance of the OCO problem, classical methods for OCO, such as online gradient descent (OGD) (Zinkevich, 2003) and regularized follow the leader (RFTL. (Shalev-Shwartz & Singer, 2007), require orthogonal projec- tions (or similarly costly operations) to ensure that the cho- sen actions are feasible. Such operations are prohibitively expensive in many applications, particularly when the action set X' has a complicated structure. Motivated by the high computation cost of classical methods, Mahdavi et al. (2012) introduced the problem of OCO with long-term constraints, where the player is not required to ensure that the actions are feasible, but instead aims to satisfy the constraints cu- mulatively.
In particular, Mahdavi et al. (2012) considered the action set to be represented by the sub-level set of a constraint function, i.c. X {a Ød : g(x) I 0} for convex' g : R2 + R. In this setting, Mahdavi et al. (2012) gave algorithm that enjoys O(T3/4) regret and ensures cumu- lative constraint satisfaction Σ g(x,) S O, while only observing subgradient and function value the played actions, i.c. 9r g(xx), St 0g(x;). This algorithm uses a primal-dual approach, in which it updates sequences of actions (primal variables) and constraint penalties (dual variables) to simultaneously minimize the regret and the cumulative constraint value. Primal-dus approaches have continued be successful for this problem, as more recent algorithms of this type have been shown enjoy O(V regret with the same constraint guarantees and constraint feedback (Yu et al., 2017).
1. Introduction
We study the problem of online convex optimization (OCO)
where, in each round = 2, .... I', a player chooses ac- tion X; from an action set X' C IRdd and then suffers the cost (x,) according to an adversarially-chosen convex function fe (Zinkevich, 2003). The player's 'a goal is to minimize the regret with respect to the best single action in hindsight,
T
T
Regr Σ fi(x;)
min XEX
E1(x)
The OCO problem has emerged as fundamental setting for various machine learning domains, such as stochastic optimization (Cesa-Bianchi et al., 2004), non-convex opti-
In this work, we take a new approach to this problem by using what we call Polyak feasibility steps, which are sub- gradient descent steps that are taken with respect to the con- straint function and use the Polyak stepsize. This approach is motivated by the fact that the Polyak stepsize is known be effective in unconstrained convex optimization (Polyak,
'Department of Electrical and Computer Engineering, Uni- versity of California-Sant. Barbara, Santa Barbara, Califor- nia, USA. Correspondence to: Spencer Hutchinson <shutchin- son @ ucsb.edu>, Mahnoosh Alizadeh <alizadeh@ ucsb.edu>.
Since the constraint function g R to differentiable, this setting can handle multiple constraints I1. In by defining g(x) = max (x)).
not assumed
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Constrained Online Convex Optimization with Polyak Feasibility Steps
Table 1. State-of-the-art algorithms for OCO with non-smooth functional constraint X = {x E R g(x) 2 0] and first-order feedback 9: = g(x+); St E (g(xx). Our results are highlighted with gray- The results marked with have been extended with Assumption and Thcorem in Mahdavi et al. (2012) as we show in Appendix A. The column "Known Strictly-Feasieee Point?" marked "Yes" if the algorithm requires knowledge of an x E R such that (xx) < 0. and "No" if not.
Reference
Regret
Constraint Guarantee
Known Strictly-Feasible Point?
Mahdavi et al. (2012)
0(19/4)
(xx) S 0
No
Jenatton et al. (2016)
O
Σ |=1 9(x)) I 0
No
Yuan & Lamperski (2018)*
O(T2/3)
1/1 (xx) S 0
No
Yu et al. (2017)*
((VT)
1= g(x)) 50
No
Corollary 1
((VT)
(xx) S 0, Vt E [T]
Yes
Corollary 2
O(VT)
g(xi)
0, vt to O(lo((T))
No
Corollary 2
O(VT)
Σ ((x,) S 0
No
1969). As such, we expect it to be similarly effective when applied to the constraint function in OCO. Accordingly, we design an algorithm that alternates between gradient descent steps with respect to the cost function, and Polyak feasibility steps. This algorithm differs from primal-dual approaches in that maintains a single sequence of iterates (versus the two sequences used by primal-dual algorithms).
strained OCO that solves a convex optimization problem with the constraint function in each round, e.g. (Yu & Neely, 2020; Yi et al., 2021; Guo et al., 2022). We discuss these related works in more detail in the following section.
1.1. Related Work
In this section, we discuss related work on constrained OCO, projection-fre free OCO, and constrained optimization.
We find that our approach enjoys O (T) regret and anylime constraint satisfaction gxx:) S O Vt, while still only observ- ing a subgradient and function value of the constraint at the played actions. Unlike prior methods for constrained OCO, which often trade feasibility for efficiency, our approach enjoys both feasibility and efficiency. Indeed, our algorithm maintains constraint satisfaction in all rounds, while using the same constraint feedback as prior work and avoiding the use of projections. Furthermore, our approach is relevant to safety-critical applications, in which constraint satisfac- tion is paramount and there is often only limited constraint information available.
1.1.1. CONSTRAINED OCO
Mahdavi et al. (2012) studied OCO with a fixed convex constraint function g, and gave an algorithm with O( ((VT) regret and O(T8/1) cumulative violation D(=g((x) that used only first-order constraint feedback, 9t s E 0g(x)). This result was then generalized to (TT regret and (TT1-1/2) cumulative viola- tion for any , E (0, 1) by Jenatton et al. (2016). The same bounds were shown for a stronger notion of constraint viola- tion Ee [+ by Yuan & Lamperski (2018), who also guaranteed that >in (19(=))++) O(T)-9). Finally, Yu et al. (2017) showed O regret and O(VT) cumulative violation in the same setting. With the additional assumption that the constraint gradient is lower bounded near the con- straint boundary (Assumption in Mahdavi et al. (2012)), the aforementioned results can be extended to guarantee no cumulative violation Σ g(x;) S 0 as stated in Table 1. We use the same assumption to show constraint satisfaction for all rounds g < Vt provided that there a known Strictlyffeasible point. Furthermore, the aforementioned works use primal-dual algorithmss which are fundamentally different from our approach of Polyak feasibility steps. In particular, our approach uses the Polyak step-size and a single sequence of iterates, while primal-dual algorithms use two iterate sequences that are linked via the cost and constraint functions.
Our complete results are shown alongside prior work in Table 1. As presented in this table. prior work has shown cumulative constraint satisfaction Ei gxx.) < 0 and re- gret bounds as tight as O(VT) (Mahdavi al., 2012; Je- natton et al., 2016; Yuan & Lamperski, 2018; Yu et al., 2017). We show stronger anytime constraint satisfaction g(xx) S 0 Vt E [T], while also guaranteeing ((VT) re- gret. However, unlike prior work, these guarantees require that there is a known point x E Rd that is strictly-feasible g(x) < O. Nonetheless, we show that when strictly- feasible point is not known, then we can guarantee constraint satisfaction after ([lg((T) rounds, well cumulative constraint satisfaction.
Also, note that Table only includes algorithms that ac- cess the constraint function via the constraint value and subgradient at the played actions g. = g(x,), E 0g(x:). Therefore, it does not include the line of literature in con-
There is also line of literature on OCO with constraints
2

---

Constrained Online Convex Optimization with Polyak Feasibility Steps
that solves an optimization problem involving the constraint function in each round, e.g. (Yu & Neely, 2020; Yi al., 2021; 2022; Guo et al., 2022). This differs from our algo- rithm and those compared in Table 1, which only access the constraint with first-order feedback at the played ac- tions. We note that solving an optimization problem with the constraint function in each round can introduce signifi- cant computational cost.
There is also a growing body of literature that uses the mem- bership oracle (MO) or separation oracle (SO) access the feasible set, e.g. (Levy & Krause, 2019; Garber & Kretzu, 2022; Mhammedi, 2022; Lu et al., 2023; Hu et al., 2023; Mhammedi, 2024). The MO and SO are defined as follows. Given a query point x E R., the MO specifies whether or not x is in the feasible set, while the SO returns a hy- perplane that separates x from the feasible set (if x is not in the feasible set). If the feasible set is the sub-level set of constraint function y (as we consider), then the MO can be constructed by checking if g(x) > 0, and the SO can be constructed using the first-order information at x, i.e. g(x), 0g(x).² We use first-order information only at the played actions, which can therefore only be used to construct a separation oracle and membership oracle at the played action. This is distinct from existing MO and SO- based algorithms, which query the SO and MO at arbitrary points (not just the played actions). Furthermore, existing MO-based and SO-based algorithms require multiple oracle calls per a round. Specifically, existing MO-based algo- rithms use (T)) oracle calls per a round (Lu et al., 2023; Mhammedi, 2022), and existing SO-based algorithms use (log(TT) oracle calls per a round (Mhammedi, 2022; 2024) or (Ks) oracle calls per round (Garber & Kretzu, 2022). Note that we state these bounds for unrestricted T and use to refer to the eccentricity of the feasible set, i.e. K = R/r with rB C X' S RB, which can be arbitrarily large. The fact that our algorithm only requires oracle call per a round can result in significant performance advan- tages over these methods, particularly when the constraint costly evaluate. Furthermore, our approach is applicable to settings where there is only local constraint information available.
Lastly, we point out that related line of literature consid- ers OCO with time-varying constraints, e.g. (Neely & Yu, 2017: Yu et al., 2017; Liakopoulos et al., 2019; Castiglioni et al., 2022; Guo et al., 2022; Kolev et al., 2023). This generalizes the fixed constraints that we consider. Nonethe- less, to our knowledge, none of these works improve on the guarantees shown in Table for the case of non-smooth constraints, and first-order feedback. We also point out that Kolev et al. (2023) gives an algorithm that uses first-order feedback and enjoys bounds on the violation in each round, i.e. g(xx)= < O (+t) However, this work requires that con- straint functions are smooth (i.e. have Lipschitz gradients), making it distinet from our work and those considered in Table 1. Furthermore, Kolev et al. (2023) uses projection on to a polytope in each round, which introduces additional computational cost.
1.1.2. PROJECTION- OCO
In parallel to the literature on constrained OCO, there is line of literature that considers projection-free OCO where the feasible set is not treated as the sub-level set of a func- tion, but rather defined as an arbitrary convex set. Hazan & Kale (2012) initiated this literature by giving an algorithm that accesses the feasible set via a linear optimization oracle (LOO) instead of using projections. This is advantageous because the LOO is often computationally cheaper than the projection. LOO-based algorithms have received signifi- cant amount of attention, e.g. (Hazan & Kale, 2012; Chen et al., 2019; Garber& & Kretzu, 2020; 2022; Wang et al., 2024; Garber & Kretzu, 2024). The state-of-the the---rrttt-ttttt-ee-ee-- for LOO- algorithms with general convex costs and general convex feasible sets is (T3/4) regret and 1 oracle call per a round (Hazan & Kale, 2012). Although our methods give smaller (VVT) regret, we note that the first-order feedback that we use is generally incomparable to the LOO oracle in terms of computationally complexity. Indeed, the first-order feed- back is cheaper to compute for some constraint functions, while the LOO is cheaper to compute for other constraint functions.?
1.1.3, CONSTRAINED OPTIMIZATION
Our approach is inspired by a line of literature in constrained (offline) optimization that uses the Polyak step-size to en- sure convergence to the feasible set, e.g. (Polyak, 2001; Nedié, 2011; Nedić & Necoara, 2019; Necoara & Singh, 2022). However, we point out two key difficulties that arise in the OCO setting: (a) the suboptimality gap of the iter- ates fx(x,) - fx(x*) is not guaranteed to be non-negative, and (b) the constraint feedback is at the played action x; and not at the "intermediate" iterate (labeled y. in Algo- rithm 1). Challenge (a) is particularly difficult to handle because the analysis approach used by Nedié (201 1) (and following works) relies on the suboptimality gap of the it-
the opposite is true in the B. requires a rank-one SVD and B3 a full-rank SVD.
AAn example of this, pointed out by Garber & Kretzu (2022). is the difference in computational complexity for first-order informa- tion and LOO for the nuclear norm ball B. and spectral norm ball B2 in the space of matrices. Computing first-order information for B. and B2 is at worst a full-rank SVD (which is expensive) and rank-one SVD (which is cheap), respectively. For the LOO,
'Given the query point x and first-order information at this point = g(x), s E 0g(x), it follows from convexity that { E
I2d : 1 + (y x) S 03 is a separating hyperplane w.r.t. X
{x E [Rd:gg()) g(())= < 0}.
3

---

Constrained Online Convex Optimization with Polyak Feasibility Steps
erates being non-negative. As result, we require a new analysis approach. However, our approach does suffer larger dependence on the problem parameters (such as the subgradient bound Gg), which can be seen as the "cost" of the adversarial online setting. To handle challenge (b), we use the first-order approximation of the cost function ge + s, (y: - xz) in the Polyak step-size instead of the true cost function g(ye). This first-order approximation avoids the need for constraint information at the intermediate it- erate Yr, while maintaining the advantageous properties of the Polyak step-size (see Section 3.4 for the details). Such a first-order approximation is also ad advantageous in the of- fline setup as seen in the recent work of Singh & Necoara (2025), but the analysis in Singh & Necoara (2025) does not extend to the OCO setting because it requires that the suboptimality gap is non-negative (i.e. [xxx) - fxx) 2 0) and that the cost functions have Lipschitz gradients. Related algorithm designs have also heen considered in the literature on constrained variational inequalities (Zhang et al., 2025), although under the assumption that the constraint functions have Lipschitz gradients (which does not hold in our setting). We further discuss the differences between our algorithm and the algorithm in Zhang al. (2025) in Appendix B.
Online Convex Optimization Online convex optimiza- tion (OCO) is a repeated game between player and ad- versary that is played over ' rounds. In each round E [7', the player chooses an action x from a convex action set X' C R2, and then the adversary chooses a convex function ft : I2 + R. The player aims to minimize the cumulative regret.
T (((x))
Regr == Σ
min XEX
m(x),
We will use the standard assumptions that the action set is bounded and that the cost functions have bounded gradients. These are stated precisely in the following.
Assumption 1. There exists positive real R such that X' C RIB.
Assumption 2. There exists positive real Gy such that [VS((x)]| < G for all x E RB and t. E (T].*
Functional Constraints Following Mahdavi et al. (2012), we study the setting where the action set is defined by a functional inequality constraint X' {x E Rd g(x) S 0), with g Rd - R being non-smooth and convex. In the fol- lowing, we assume that the constraint function has bounded subgradients (Assumption 3) and that the subgradient norm is lower-bounded near the boundary (Assumption 4). These assumptions are also used by Mahdavi et al. (2012) and Je- natton et al. (2016). We also note in Remark that Assump- tion is implied by Slater's condition (i.e. the existence of -trictly-feasíble point) provided that the other assumptions hold. Lastly, note that since the constraint function is non- smooth, this setting can be extended to multiple constraints I1.... 9m by taking g(x) = | 9s (x).
1.2. Notation
We use O(-) for big-O notation and O(-) for the same ig- noring log factors. The 2-norm is denoted by || || and the
2-norm ball is denoted by B = {x Rd |x|| $ 1}. Given a natural number n, we use the notation [<] == {1,2, .... n). The transpose of a matrix M is denoted M A vector of ones and zeros is denoted by and 0, respectively. For
a given x E R. we use the notation [x]+ = max(æ, 0). Lastly, for point z E Rd and closed convex set y C Rdd we use the notation dist(z, )) minyey ||z 1--- yll and my(z)= arg minyey ||z y/|.
Assumption 3. There exists a positive real Gg such that, for all x E RB, it holds that [[0g(x)]| S Gg-
1.3. Overview
Assumption 4. There exists positive reals a,c such that =-}} is nonempty and [[0g(x)]| 2 a for all x E X'.
X" = {x E RRd 9(x)
We specify the problem of OCO with constraints in Sec- tion 2. Then, in Section 3, we give an algorithm for this problem that uses our approach of Polyak feasibility steps. In particular, Section 3.1 gives the description of this algo- rithm, Section 3.2 gives the guarantees of (VTT) regret and anytime constraint satisfaction g(x,)= < O, and Section 3.3 and 3.4 give the regret analysis and feasibility analysis, respectively. Lastly, we give simulation results in Section 4 that demonstrate the functionality of our algorithm.
Remark 1. Assumption 4 holds if Assumption I holds and there exists a strictly-feasible point (i.e. Slater's 'ss condition). We show this Appendix C.I.
3. Algorithm
In this section, we give Algorithm 1, which tackles OCO with functional constraints using our approach of Polyak fea- sibility steps. Notably, Algorithm only uses one constraint query in each round, at the played action 9: = g(xx), St e
2. Problem Setup
We study the problem of online convex optimization with functional constraints. In the following, we first describe online convex optimization generally and then specify the functional constraints.
"This assumption can be weakened slightly for our guarantees
of anytime constraint satisfaction (i.e. Corollary 1). Specifically, only need that |/V (x))l S. Gy for all E X (rather than all x E RB). We discuss this later Remark 2.
4

---

Constrained Online Convex Optimization with Polyak Feasibility Steps
0g(x,), and therefore uses the exact same feedback as Mah- davi et al. (2012). Despite this limited feedback, we will show that Algorithm I ensures constraint satisfaction for all rounds, i.e. g(x,) - 0 for all t E [T].
Algorithm 1 OGD with Polyak Feasibility Steps
input initial action X1 E IRd, step size > O, tighten- ing p 2 0. 1: for == 1... T do
2: Play x; and receive fi-
3.1. Description
3: Query constraint: Jt = g(xx), 8t E dgg(x))
4: Gradient descent: y: - Xt 1/ fe(xx).
At high-level, Algorithm operates by alternating be- tween gradient descent steps (line 4) and Polyak feasibility steps (line 5). We discuss the key ingredients of our Polyak fcasibility steps in the following.
5: Polyak feasibility step:²
X1+1 = IIRE Yy- 19. (y, (yx_xx))) xxxx))+ $1)
|s
end for
Polyak Step-size The design of our Polyak feasibility step motivated by the classical Polyak step-size (Polyak, 1969). In unconstrained convex optimization, using subgradient de- scent with the Polyak step-size is known to be optimal (Boyd et al., 2003), and therefore it is a natural choice to ensure strong feasibility guarantees when applied to the constraint function. This classical step-size uses the function value and subgradient at the current iterate to approximate the optimal step-size in each update. In our setting, this would require the constraint function value at the "intermediate iterate" y which is not available. We address this next.
gradients. Note that tightening the constraint in this manner is a common technique in the constrained OCO literature, e.g. (Mahdavi et al., 2012; Jenatton al., 2016).
Polyak Feasibility Steps Using the ingredients discussed previously, can put everything together to get our Polyak feasibility steps. Indeed, the step-size in line 5 is.
Ig+ + s (y: xx) + pl+
(2)
|s ||
First-order Approximation As discussed previously, the classical Polyak step-size cannot immediately be applied to our setting because it would require the constraint function value at the intermediate iterate y:. Although this is not known in our setting, we do have constraint information at the played action X₁, which should not be too far from the intermediate iterate yz- Therefore, we use the constraint information at x2 to construct first-order approximation of the constraint at Yt.
where the numerator uses the first-order approximation in (1) and the tightening parameter p. As such (2) can be viewed as the Polyak step-size that uses a first-order approximation of the tightened constraint value g(ye) + p. In the analysis, we will see that this step-size ensures that the constraint value is greatly reduced in each step.
3.2. Guarantees
In this section, we give the regret guarantees and constraint satisfaction guarantees for Algorithm 1. In particular, the following theorem (Theorem 1) gives a bound on the regret and constraint violation for arbitrary choice of algorithm parameters 7) p. We will then show how these algorithm parameters can be chosen to get several different guarantees.
g(y.) ~ s (x)-xx) E g(x:)- (y:-x;), (1)
As we will show in the analysis, this first-order approxima- tion is sufficient to maintain the advantageous properties of the Polyak step-size.
Theorem 1. Let Assumptions 1, 2, 3 and 4 hold. Then, playing Algorithm I with 1) > O and p E (0, c) ensures that,
Constraint Tightening Another difficulty that arises in our setting is that the gradient descent step in line 4 might push the sequences of actions out of the feasible set. Indeed, the cost functions are chosen adversarially and therefore we have no guarantees about the direction of the gradient in each round. Therefore, to ensure that the actions are feasi- ble, we use a tightened version of the constraint function g(x) + o where p > is a tightening parameter that to be chosen appropriately. Given that the constraint function is Lipschitz (via Assumption 3), this ensures that there is "buffer zone" between the points that satisfy the tightened constraint gxx) + S 0 and the boundary of the true fea- sible set defined by (x) < O. Therefore, by choosing p proportional to the cost step-size 17. we can ensure that the actions are feasible despite the adversarially-chosed cost
" GIPT. 2R !
Regr S 17
GG
g(xx)= S 1222 Xp) + 1 p, Vt
where X, = E g(x) < -p) and 7 = C
In the following, Corollary 1 specifies a choice of and p that ensures ((VT) regret and anytime constraint satisfac- tion. Note that this result requires that the initial action x1 is ferictly-eeasible. We also point out that these guarantees
When s; = O, we take the update to be x = IT (y+)-
5

---

Constrained Online Convex Optimization with Polyak Feasibility Steps
still hold under slightly weaker set of assumptions, which discuss in Remark 2.
3.3. Regret Analysis
In this section, we give the regret analysis. We separate the regret in to (I) the regret with respect to the tightened feasible set, and (II) the cost of tightening the feasible set,
Corollary 1. Let Assumptions 1, 2, 3 and 4 hold. Suppose a and that (xx)) ) S -a for some a E (0, e). and let VT
Eo G where & = 1 V. It follows that the actions
chosen by Algorithm I satisfy,
Regr = (fi(()) f((x;)) + ((f(()) f((x*)),
[2G G
GG5a 2G,
+ Gja ( VT.
Regr
{a
Term
Term II
g(xx) 5O 11 [ [T],
where x E arg mi Et=1 f((x), and the tightened feasible set is.
Remark 2. The guarantees in Corollary also hold under slightly weaker set of assumptions. In parficular, we only need that V f((x)ll I G3 for all x E X (rather than all X E RBB. We show this in Appendix C.4.
Xp = (xER" g((x) S -p).
(4)
We start with Term I. The key observation is that the Polyak feasibility step (line 5) can be equivalently defined as the projection on to the halfspace Hr in (5) below (with the additional projection on to the ball). In fact, this halfspace He contains the tightened feasible set X, and therefore pro- jecting on will not increase the distance to any point in Xp. This is stated precisely in Fact 1.
Next, we give Corollary 2, which shows that, when X₃ is in RB (and therefore is not necessarily feasible), then the algorithm can ensure anytime constraint satisfaction after (log(T)) rounds. Corollary 2 also shows that when T is sufficiently large, then the algorithm ensures that there is cumulative constraint satisfaction E/= g(x,) < O. Note that the requirement that I' is sufficiently large is also used by prior work that shows cumulative constraint satisfaction (Mahdavi et al., 2012; Jenatton et al., 2016).
Fact 1. The update for Xx+1 in line 5 of Algorithm 1 is equivalent to X1+1 = LRR (1l,, (y:)) where,
He = (xE Rd : + s (x x.) + +
(5)
Corollary 2. Let Assumptions 1, 2, 3 and 4 hold. Consider Algorithum I with X1 RBB 7 2G,G,VT
Ee and p VT"
Furthermore, it holds that H. 2 Xp and therefore that for all x E X, and v E Rd
Then, it holds that,
GG E
GGÉE
+ G₁e) VT,
[T. x S v-xl
(6)
Regr S
4G,
In fact, the classical analysis of OGD (from Zinkevich (2003)) only requires that the projection does not increase the distance to the optimal action, which is ensured by (6) in Fact 1. Therefore, it follows from (6) and the standard analysis of OGD that we have a regret bound with respect to the tightened feasible set, and thus,
202 o²
4G,
g(xi) SO V1 1+
g log
Furthermore, when vT
N
4nGa it additionally holds that, ς
T Σ
g(xx) S O.
Term I S
2R
+ G9..
"
2
Lastly, we give another corollary below (Corollary 3) that allows a small amount of violation in each round, while eliminating the dependence on G2 in the regret bound. In this case, the regret bound is 2RG,vT, which matches what is attained by online gradient descent using full projection on to the action set in each round. At the same time, the constraint violation satisfies g(xx) = =
We defer the complete proof of (7) to Appendix C.3.
Now, we look at Term II. We use Lemma below, which provides a bound on the distance to X, in terms of g. This lemma is conceptually similar to Theorem in Mahdavi et al. (2012). However, it is more general in the sense that it is general error bound on the constraint function, whereas Theorem 7 in Mahdavi et al. (2012) only provides bound on the difference in costs between point in the tightened feasible set and the original feasible set. The proof of Lemma 1 is given in Appendix C.2.
Corollary 3. Let Assumptions 1, 2, 3 and 4 hold. Consider 2R Algorithm I with X1 E RIB, 17 = GT and p = O. Then, it holds that,
Lemma 1. Let Assumptions and 4 hold, and suppose that p [0, c). Then, we have for all RBB that,
Regr $ 222R VT,
02(t 11)
2RG, EVT
gxx:) < 2RG, exp
2G
Vt E [T]
dist(x, x,,) < - [g(x) + pl+
(8)
6

---

Constrained Online Convex Optimization with Polyak Feasibility Steps
It follows from Lemma and the cost gradient bound (As- sumption 2) that,
S dist dx,t"(x,
9p (x)x)²
(b)
||
9p (x)
T Term II (
S dist." (x,
(c)
G
T Σ (fe(IIx,(xx)) (x*)) - f((x)))
S <1-3
G3
dist 2 (x, Xp);
(d)
(a)
where (a) uses the Pythagorean theorem of the projection,
GyTdist(x*, xx))
(b) (b) uses that sT (x - v) 2 gp(x) - gp(v) 2 9p due to the fact that E 0g(x) and v E X,, (c) uses that ||s| - Gg
GfT [x(xx) + p]+ 5 GrLr,
(c)
due Assumption 3, and (d) uses Lemma 1.
where (a) uses the minimality of x (b) uses the cost gradi- ent bound, and (c) uses Lemma and that g(x*) I O.
Using Lemma 2, we will show that the distance between the action x, and the tightened feasible set X, will not increase too much in each round, and therefore that x, always stays close to Xp. The key difficulty in doing so is that Lemma 2 uses the "exact" Polyak step-size, while Algorithm I uses the first-order approximation of the constraint value in the Polyak step-size (i.e. as in (2)). In order to handle this dis- parity, we introduce the "fictitious" iterate Zt+1- We define 2e+1 such that 2 = X, when 8; 0, and otherwise take,
Combining the bounds on Term I and Term II yields,
2R ! " 2
NOT +IPTT
Regr
+
which matches the bound in Theorem 1.
3.4. Feasibility Analysis
[gt + pl+ |sc||2
In this section, we give the feasibility analysis. The central result in this section is Lemma 2 below, which shows that the Polyak step-size shrinks the distance to sub-level set of g. This lemma combines the classical analysis of the Polyak step-size from Polyak (1969) with Lemma 1.
Ze+1
HR
We can interpret Ze+1 as a feasibility step that is taken di- rectly from the previous action x,. Importantly, the update for Z matches the form in (9) and therefore we will be able to directly apply Lemma to analyze 2e+1-
Lemma 2 (Polyak Step-size). Let Assumption 3 and 4 hold, and suppose that E c]. Furthermore, consider the p-sublevel set of g. X, == {x E Idd +g(x) + p S 0}. Consider any x E RIB and s E 0g(x) such that s + O, and let,
Using 2,+1, we study the distance between X and Xpr
dist xp)
S | 1x,, (2(+1)l
S X - Z(+1ll + dist (Zi+1, Np),
[Ø(x) + pl+
X =I=
x
||s||
(9)
Term I
Term II
Then, it holds that,
We start with Term I. First, note that Z;+1 can be written as Zi+1 = As (Il,, (xx),, where He is the halfspace defined in (5). Therefore, it follows that,
1
0²)
dist? dxst? S
dist? (x, Xp).
(10)
G2
Term
|[ (yr)) 1R (11,, (xx))l
Proof. Let = (x) and denote (x(x) g(x) + p. First, note that if (x) O, then (9) becomes x+ x and therefore 9x(x*)+ )= (x) S O and (10) is satisfied with both sides O. Therefore, we take (x) > 0 for the remainder (which ensures that [x)(+ = (x)). Then, it follows that,
|1l (yx) 1lH, (xx))
Ilye xell
(11)
= V
S G,,,
where the first two lines use the non-expansiveness of the projection, and the last line uses the cost gradient bound.
dist dxst ,x²) S 1|xt -
Next, we look at Term II. If S, 0. then it holds that Ze+1 x, and g(x)) = ming (x) < -p, which implies that Term II = O. Alternatively, if s * O, then applying Lemma 2 yields (Term IT)2 < 7 dist 2 (xx, X,), where 7 == 3.. Therefore, it holds in any case that,
gx(x) v112
< ||x
(a)
|s|
= dist? 2 (x, Xx) 2 (x(
||
s
[x - v)
(x)2
|s|
Term II S / Xx)
7

---

Constrained Online Convex Optimization with Polyak Feasibility Steps
Iastantannoss Vialation [
0.05
600
Cammllatvv Vielation
40
0.044
Regret Ry
15 Exo0x
30
20-
0.02
10-
0.01
0-
0.00
1.5
0.0
1.5
2.0
Horison T
X10'
Horizon
X10"
Round
X30"
(a)
(b)
(c)
Figure 1. Experiment results for our algorithm (labeled PFS), alongside the algorithm from Yu et al. (2017) (labeled DPF). We also include a version of the algorithm in Yu et al. (2017) where the constraint is tightened (labeled DPP -T). The points indicate the average over 30 trials and the error bars and shading are 11 standard deviation.
Combining Term I and Term II yields,
0.1
Constraint
1,,t(x+1,,,)))) S (xdist(xx,, Xp) + ,
0.0
Ogtimall Action
t-1 S 7/ dist(xi, - nG Σ
0.1
-0.2
==0
distxiss(x1,, n/g
0.3
V
0.4
where we apply the bound recursively the second line, and use the fact that y E [0, 1) in the third line. Then, applying the the subgradient bound (Assumption 3),
0.5
0.6
-0.6
-0.4
-0.2
0.0
gxxx)= g(x)) - g(11x, (xx)) + ((xxx, (xi)
Figure 2. Actions chosen by our algorithm and the one from Yu et al. (2017) in an experiment.
(x) P
Gg p. VT
and b; are the ith row of A and b respectively. Accordingly,
This matches the constraint violation guarantee in Theo- rem 1.
we take G = /2, R = 1, G, = 1, 0.25 and o -22
In this setting, we implement Algorithm (labeled PFS) with the algorithm parameters chosen according to Theo- rem 1, as well as the algorithm in Yu et al. (2017) (labeled DPP) with the algorithm parameters chosen according to their Theorem 1, i.. a T, V = vT. We also implement the algorithm from Yu et al. (2017) with tightened con- straint (x(x) g(x) p for p E [0, c). as is used in algorithm and that in Mahdavi et al. (2012) and Jenatton et al. (2016). Same as the aforementioned algorithms, we use a decreasing = min(c, ) where e > 0 is a param- eter that we tune to reduce the violation. We choose 20 to ensure that there is a small amount of constraint violation. The tightened version of DPP is labeled DPP-T.
4. Numerical Experiments
Although our primary contribution is our theoretical results, we also give numerical experiments demonstrate the func- tionality of the algorithm and provide some empirical ver- ification of the theoretical results. 6 In these experiments, we benchmark the performance of our algorithm with the algorithm from Yu et al. (2017) as it has the best regret bound among those in Table 1.
We consider 2-dimensional toy setting with quadratic cost functions fx) 33|x 2 and linear constraints Ax < b. We generate by sampling uniformly from [0, 1J2, and take A = [ - T and b- = 0.51, where we use I to denote the x 2 identity matrix. Therefore, we can define the constraint function as g(x) = max;e[4] a x - bi where a;
The results are shown in Figure Precisely, Figure Ia and Figure 1b show the regret and cumulative violation for T 2 10 4x 4x103 ...., 2 10 where the marker indicates
6 *Our experiment code is available at https: //ggth/b. com/ com/shute shtssshthhhhhhccccc h/cotcchhh/oo-ppp Poloaco----o-----oeo-aaaaa Feasibil 1ity- Steps.
Note that the constraint also be written with the infinity-
norm: (xx = || b.
8

---

Constrained Online Convex Optimization with Polyak Feasibility Steps
the mean over the 30 trials and the errorbar indicates the standard deviation. Figure Ic shows the instantaneous viola- tion [g(x+)]+ at each round for fixed T' = 2 x 10², where the line shows the mean over 30 trials and the shading indi- cates the standard deviation. In these results, DPP enjoys smaller regret than PFS. However, DPP incurs constraint violation, while PFS does not incur constraint violation. By augmenting DPP with a tightened constraint, the constraint violation can be substantially reduced shown for DPP-T. However, this also results in larger regret.
with long-term constraints. Advances in Neural Informa- tion Processing Systems, 35:33589-33600 2022.
Cesa-Bianchi, N., Conconi, A., and Gentile, C. On the gen- eralization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9):2000-2057, 2004.
Chen, L., Zhang, M., and Karbasi, A. Projection- bandit convex optimization. In The 22nd International Confer- ence Artificial Intelligence and Statisfics, pp. 2047- 2056. PMLR, 2019.
To provide intuition on the operation of our algorithm, we also include Figure 2, which shows every 300th action cho- sen by the algorithms in one simulation trial. In this plot, it can be seen that PFS takes a conservative approach in grad- ually approaching the constraint boundary, which ensures constraint satisfaction the cost of larger regret.
Chen, T. and Giannakis, G. B. Bandit convex optimization for scalable and dynamic iot management. IEEE Internet Things Journal, 6(1): 1226-1286, 2018.
Cutkosky, A., Mehta, H., and Orabona, F. Optimal stochas- tic non-smooth non-convex optimization through online- to-non-convex conversion. In International Conference on Machine Learning, pp. 6643-6670. PMLR, 2023.
5. Conclusion
In this work, we give an algorithm for constrained OCO that uses Polyak feasibility steps to ensure anytime con- straint satisfaction gxxx) S Vtt and O(VT) regret, while only receiving feedback on the function value and subgra- dient at the played actions. We foresee this approach being particularly relevant to safety-critical applications, where constraints must be satisfied despite having only limited constraint information.
Garber, D. and Kretzu, B. Improved regret bounds for projection-fres free bandit convex optimization. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 2196-2206. PMLR, 2020.
Garber, D. and Kretzu, B. New projection algorithms for online convex optimization with adaptive regret guar- antees. In Conference on Learning Theory, pp. 2326- 2359. PMLR, 2022.
Acknowledgements
This work was supported by the National Science Founda- tion under grant #2330154.
Garber, D. and Kretzu, B. Projection-free online convex optimization with time-varying constraints. In Forty-first International Conference on Machine Learning, 2024.
Impact Statement
Guo, H., Liu, X., Wei, H., and Ying, L. Online convex optimization with hard constraints: Towards the best of worlds and beyond. Advances in Neural Information Processing Systems,
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
2022.
Hazan, F. and Kale, S. Projection- online learning. In 29th International Conference on Machine Learning, ICML 2012, pp. 521-528, 2012.
References
Agarwal, N., Bullins, B., Hazan, E., Kakade, S., and Singh, K. Online control with adversarial disturbances. In Inter- national Conference on Machine Learning, pp. 111-119. PMLR, 2019.
Hu, Z., Wang. G., and Abernethy, D. Riemannian projection-free online learning. Advances in Neural In- formation Processing Systems, 36, 2023.
Jenatton, R., Huang, J., and Archambeau, C. Adaptive algorithms for online convex optimization with long-term constraints. In International Conference on Machine Learning, pp. 402-411. PMLR, 2016.
Boyd, S., Xiao, L., and Mutapeic, A. Subgradi- ent methods. Lecture Notes of Stanford EE392, 2003. URL https://wehh www.ford...rdd....mm.. edu/ class/ee392o/ 20000//surrrddmeehooo pdf.
Kolev, P., Martius, G., and Muehlebach, M. Online learn- ing under adversarial nonlinear constraints. Advances in Neural Information Processing Systems, 36, 2023.
Castiglioni, M., Celli, A., Marchesi, A., Romano, G., and Gatti, N. unifying framework for online optimization

---

Constrained Online Convex Optimization with Polyak Feasibility Steps
Levy, K. and Krause, A. Projection free online learning smooth sets. In The 22nd international conference artificial intelligence and statistics, pp. 1458-1466. PMLR. 2019.
Polyak, B. T. Random algorithms for solving convex in- equalities. In Studies in Computational Mathematics, volume 8, pp. 409-422. Elsevier, 2001.
Rockafellar, R. Convex analysis. Princeton Math. Series, 28, 1970.
Liakopoulos, N., Destounis, A., Paschos, G., Spyropoulos, T., and Mertikopoulos, P. Cautious regret minimization: Online optimization with long-term budget constraints. In International Conference on Machine Learning, pp- 3944-3952, PMLR, 2019.
Shalev-Shwartz, S. and Singer, Y. A primal-dual perspective online learning algorithms. Machine Learning, 69: 115- 142, 2007.
Singh, N. K. and Necoara, I. Stochastic halfspace approxi- mation method for convex optimization with nonsmooth functional constraints. IEEE Transactions on Automatic Control, (0airol,70(1))))))))) 70(1):479 2025. doi: 10. 109/TAC22024. 3426888.
Lu, Z., Brukhim, N., Gradu, P., and Hazan, E. Projection- free adaptive regret with membership oracles. In Interna- tional Conference on Algorithmic Learning Theory, pp. 1055-1073. PMLR, 2023.
Tewari, A. and Murphy, S. A. From ads to interventions: Contextual bandits in mobile health. Mobile health: sen- sors, analytic methods, and applications, pp. 495-517, 2017.
Mahdavi, M., Jin, R., and Yang, T. Trading regret for efficiency: online convex optimization with long term constraints. The Journal of Machine Learning Research, 13(1):2503-2528 2012.
Wang, Y., Yang, W., Jiang, Lu, S., Wang, B., Tang, H., Wan, Y., and Zhang, L. Non-stationary projection-free online learning with dynamic and adaptive regret guaran- tees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 15671-15679, 2024.
McMahan, H. B., Holt, G., Sculley, D., Young, M., Ebner, D., Grady, J., Nie, L.,, Phillips, T., Davydov, E., Golovin, D., et al. Ad click prediction: a view from the trenches. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. pp- 1230, 2013.
Yi, X., Li, X., Yang, T., Xie, L., Chai, T., and Johansson, K. Regret and cumulative constraint violation analysis for online convex optimization with long term constraints. In International conference on machine learning, pp. 11998- 12008. PMLR, 2021.
Mhammedi, Z. Efficient projection-free online convex op- timization with membership oracle. In Conference on Learning Theory, pp. 5314-5390. PMLR, 2022.
Yi, X., Li, X., Yang, T., Xie, L., Chai, T., and Johansson, K. H. Regret and cumulative constraint violation analysis for distributed online constrained convex optimization. IEEE Transactions on Automatic Control, 68(5):2875- 2890, 2022.
Mhammedi, Z. Online convex optimization with separa- tion oracle. arXiv preprint arXiv:2410.02476. 2024. 2024.
Necoara, and Singh, N. K. Stochastic subgradient for com- posite convex optimization with functional constraints. Journal of Machine Learning Research, 23(265): 2022.
Yu, H. and Neely, M. J. A low complexity algorithm with of / /T) regret and o(1) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 21(1):1-24 2020.
Nedié, A. Random algorithms for convex minimization problems. Mathematical programming, 129:225-25 2011.
Yu, H., Neely, M., and Wei, X. Online convex optimization with stochastic constraints. Advances in Neural Informa- tion Processing Systems, 30, 2017.
Nedić, A. and Necoara, I. Random minibatch subgradient al- gorithms for convex problems with functional constraints. Applied Mathematics & Optimization, 80(3):801-833, 2019.
Yuan, J. and Lamperski, A. Online convex optimization for cumulative constraints. Advances in Neural Information Processing Systems, 31, 2018.
Neely, M. J. and Yu, H. Online convex optimiza- tion with time-varying constraints. arXiv preprint arXiv: 170..00220488... 2017.
Zhang, L., He, N., and Muchlebach, M. Primal methods for variational inequality problems with functional con- straints. Mathematical Programming, pp. 1-32, 2025.
Polyak, B. T. Minimization of unsmooth functionals. USSR Computational Mathematics and Mathematical Physics, 93):14-29 1969.
Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In International Conference on Machine Learning, pp. 928-999889988 088936,,25 2003.
10

---

Constrained Online Convex Optimization with Polyak Feasibility Steps
A. Extension of Prior Work to No Cumulative Constraint Violation
In this section, we show how the prior work Yu et al. (2017) and Yuan Lamperski (2018) can be extended to show cumulative constraint satisfaction E ((x)) I 0 under Assumption 4 (which is the same as Assumption 1 in Mahdavi al. (2012)). This follows similar approach Theorem 8 in (Mahdavi al., 2012), but we give for completeness.
The algorithm in Yu et al. (2017) guarantees Regr S CRVT and Σt= ((x) S CvvT for some constants CR. Cv 0. Therefore, by applying this algorithm to the tightened constraint gx(x) == g(x) + p. we can guarantee that > (x(xx) S Cv and,
T
Reg. = [(xi)
Σ (x) S CRVT, XEX,
min
(12)
where X, is the sub-level set of the tightened constraint defined in (4). Choosing P min 6, VT
Cv
(where is defined in
C
Assumption 4) and taking T's N き
ensures that,
Eg(xi) = (xx pP = CVVT -min
Cv 6, VT
T T=0 0.
(13)
Then, with x E arg xix, Ets f((x).
T Reg + (f(())) fa(x*)) s Reg + (fx, - f((x)) S Reg. + dist((( xp)
Regr
1=1
Then, applying Lemma and (12), and using the fact that g(x*) $ 0 yields,
Regr S CRVT + T Gg - [g(x)) + pl+ S CRVT+ T T _ PS CRVT+ GGCv VT.
Therefore, we have shown that the algorithm from Yu et al. (2017) can be extended to show O(VT) regret and cumulative constraint satisfaction Σi=1 (xx) < 0. provided that Assumption 4 holds and that T is sufficiently large, i.e. T Ct Note that the requirement that sufficiently large is also required by other works that guarantee cumulative constraint satisfaction, e.g. (Mahdavi et al., 2012: Jenatton al., 2016).
We a similar process give guarantees for Yuan & Lamperski (2018). The original guarantees in Yuan & Lamperski (2018) are of the form Reg, < CCpTmmx((81188) and 17=19(xx)) S CvT118/2 Therefore, choosing min (e, T877
and taking T 2 275 ensures that Σ ((x)) S 0. Also, the resulting regret
02/0
Regr S 7max(x11111)) GgCv TL-3/2
The order of the bound max 3-11) is minimized when B = 3/4 and therefore, we get that Regr (T2/33). Note that Yuan & Lamperski (2018) also gives a bound of the form [[=((1
CyT and therefore one might hope to guarantee Σ (lg(x)) ) < 0. Unfortunately, the analysis approach does not immediately show this because the tightening parameter p cannot be used cancel out the violation as in (13).
B. Comparison of Algorithm with Related Work
In this section, we discuss the differences between our algorithm design and the algorithm design in Zhang et al. (2025), which studies constrained variational inequalities. Although Zhang et al. (2025) studies a different setting and therefore uses a different analysis, there are some apparent similarities in algorithm design that we discuss here. To illustrate the similarities and differences, we can write our algorithm different form that allows for more direct comparison. particular, when the cost functions are fixed ft = f and the constraint function is smooth, we can write our algorithm (with p 0) as,
[g(x;) - fxx)) Vg(xx)]
vo(xi))
X 1T
Xt v/ fxx))
(14)
V |

---

Constrained Online Convex Optimization with Polyak Feasibility Steps
and the algorithm in Zhang al. (2025) can be written as (see their Algorithm 2).
x X fxx)((;)) - -1 [ag((x) Vx(xx) VVg())))((ox Vg(x)).
(15)
[Vgg(x))]
In both algorithms, the step-size is O VT and a Gg/R in (15). As such, we can see several differences:
Zhang et al. (2025) applies the step-size 7 to the entire third term in (15), while our algorithm in (14) applies the step size only to fxx))) Vg(xx) within the third term.
Zhang et al. (2025) applies the scaling to g(x)) in (15), while algorithm uses no such scaling in (14).
Zhang et al. (2025) uses an additional constraint to ensure that the iterates are bounded, whereas we use a projection on to RB.
C. Missing proofs
C.1. Proof of Remark
In this section, we show that Slater's 's condition implies Assumption 4, provided that Assumption 1 holds.
Proposition 1. Let Assumption I hold. Then, suppose that Slater's condition holds, i.e. there exists positive real & and y E & such that gly) S -E. It follows that Assumplion 4 holds with of and (1 - c) &
2R for any E (0, 1).
Proof. It holds that X' = {x Rd 9xx } is non-empty because there exists z. y such that g(z) (given that X' is nonempty and compact) and g(y) S -. Specifically, since -e [-E, 0) and is continuous (via Corollary 10.1.) in (Rockafellar, 1970)), it holds that there exists such that g(z) -e
Then, we show that [x]] 2 a for all x E X², Indeed for all x E X', it holds for all E (g(x) that,
E ž g 2 g(x) + (y x) = - (y x) 2 -E |s|llly - x 2 -E 2||s|| R
||||| 2 5-6 =11 - --c),2 2R a.
2R
where we use the fact that y - x|| - 2R given that y,y E X C RB.
C.2. Proof of Lemma 1
In this section, we give the proof of Lemma 1. This proof relies the following lemma, which gives several properties of the projection on to the sub-level set of a convex function.
Lemma 3. Consider closed convex function h Rd TR, where we use the notation S = {x Rd h(x) S 0). Let K. be
convex set such that S C K. Assume that, for all x E K., it holds that ||s|| < G for all s E 0h(x), and when h(x) = 0, it
holds that ||s||| 2 a for all E θh(x). Then, take any x E KC such that h(x) > 0. Let 11x and s, E @h(x).
There exists 7 2 and sy E 0h such that:
1. h(2)) = 0,
2. x - = 1
3. 7 ||=_Il
A(x)
4. ||s < S Sz
5. ||s 2 |s
Proof. First, note that the S := show each point in the following.
= fx E Rd h(xx) < 0} is a closed and convex set so this projection is well-defined. Then, we
12

---

Constrained Online Convex Optimization with Polyak Feasibility Steps
1. Suppose the contrary, i.e. that l(z)) for some e O. It follows that z B C Saa as
f(2 - (v) S h(z) + G sctcc=
sup veB
Therefore, z' = +
x-2 xx-2 G
E S and
x| = (1 x - 2|G
| =
1|2 xl| < x||,
x
z.
contradicting the optimality of the minimizer of the distance to S.
know that the vector x z is normal to S at Furthermore, S (x: h(x)= I hzz) = 0} and the conditions of the lemma ensures that 0 is not subgradient of h at z (and therefore is not a minimum of h) so (Rockafellar, 1970) (Corollary 23.7.1) tells us that there exists À 2 0 such that x - z Adh(z). Therefore, there exists y 2 0 and 8 E (z) such that x 2 ||=l
2. Since lxs(x) and S is closed convex
3. It follows from the definition of subgradient of l that,
2) =7 s.S
4(x) 2 h(z) + s (x 2) =s (x-x)
7||$.|1- ||
Rearranging yields,
h(x)
7 S |
4. From the monotonicity of the subgradients of a convex function, it holds that
0 Σ (s: - 8z) T x) =
7
(s= 8x) T 8:
|s_
02 (s= - S2) 8z
|| < s. S..5
5. From #4 and Cauchy-Schwarz,
|| S s, ||s |
|s 2 ||s/||.
Then, give the proof of Lemma 1 in the following.
Proof of Lemma 1. We use the notation (z(x) == g(x) p. First note that when (p(x) S 0. then X, and therefore (8) holds with both sides zero. Next, we consider the case where (x(x > 0. To do so, we will first show that the subgradient
norm of (x) is lower bounded at all x such that (x) = 0. In particular, consider any x such that (x) = 0 (which necessarily satisfies x E RBB), and let z = T -x(x)s-((x) and 82 E 0g(z). Then, follows from Assumption 4 that ||s= ll 2
and therefore we can apply Lemma #5 by setting K. + RIB, 4 g + + a to get that for all s, E 0g(x).
S2 N a. |
Note that we have used the fact that (g(()) +) = (x, 0g(x since they only vary by a constant. Since we know that the subgradient norm of gp is lower bounded the boundary of Xx. we can apply Lemma #3 with K.C. + RB, h 9p- G Gg and get that,
dist(x, Xx) 5 (x)
< (x(x)
|s2
which verifies (8).
13

---

Constrained Online Convex Optimization with Polyak Feasibility Steps
C.3. Proof of (7)
In this section, we prove (7). This combines Fact with the classical online gradient descent analysis from (Zinkevich, 2003).
Proof of (7). Given that x E X, S He and xp Xx X
RB (and both Hr and RB are convex), it holds that,
|x+1 x
Re H1 (y++1)) - x
TT (yt+1) -xpll
ye++ -x/12
S Xx - -)([s((Xx)) - xtil2
xx - x7,1² - 2n/ fc(e))(( T(x (x(-xx) + f
Using this and the convexity of fú, it follows that
Term I
Σ -e(x))
< (x:)) (xt xx)
(xx
(||x: xt112 ||xx+1 - -x,113)
Σ
[f(()))]l
211
17 T
(||x1 - xX11² - ||X+1 - xx,113)
Σ
[V(((x))1
2m
t=1
< R² G
1
2
where the third inequality uses Assumptions and
C.4. Proof of Remark
In this section, we show that the guarantees of Corollary hold under slightly weaker assumptions. In particular, we use the following Assumption 5 instead of Assumption 2. Assumption 5 is weaker than Assumption that it only requires that the cost gradients are bounded for all x E X, rather than all x E RIB
Assumption 5. There exists positive real G5 such that [<()]] S for all x E X and E [T].
We then state the guarantees as a proposition and prove Proposition 2.
Let Assumptions 1, 3, and 5 hold. Suppose that g(x1) S aa for some a E (0, c]. and let p = Jr and Ep where& & = - v/y. It follows that the actions chosen by Algorithm satisfy, GjC.
G2
Gjła 2G,
+ Gja VT,
Regr 1
+
{a
σ
g(x,) 50 (T).
Proof. First, we show that [x,)) & Gy for all E [T] by induction over the first r rounds. The base case holds because X1 E X, C X and therefore (x,)] < Gy by Assumption 5. For the induction step, suppose that [x,)(( < G, for all / E [r]. Then, note that the feasibility analysis Section 3.4 only requires that the cost gradient bounded the previously played actions. In particular, this bound is applied in (11). Therefore, holds that.
g(x++1) & Gyy 2/2 didtt X1, X,) + GGGG 1 /
P.
14

---

Constrained Online Convex Optimization with Polyak Feasibility Steps
implying that ((x+11) (V I Gy, and together with the induction hypothesis, it holds that [[V]( s Gy for all E [r and the induction step is complete. Thus, it holds that || [xx,)]l S Gy for all e [T]. Along the way, we have also shown that X2 X' for all t E [T].
with the specified choice of algorithm parameters. Since X,41 X, it holds that
Next, we show that, because the cost gradients are bounded at the actions, the regret bound holds. In particular, the analysis of Term in the regret analysis (see Section 3.3) holds because it only requires that || [xxx))] S G for all & [7] (as shown in Section C.3). The analysis of Term requires that ft xx because the cost gradients are assumed be bounded on X and therefore all fr Lipschitz X.
fi(x*) - Gyll[x, (x*) x*|| ||. This holds
15


Reviews:
[{"review_id": "c5fsGKhtS4", "reviewer": "Reviewer_3Pxe", "summary": "In this work, the authors study online convex optimization with a fixed constraint function. Their method employs Polyak feasibility steps to guarantee constraint satisfaction without compromising regret. Specifically, they introduce an algorithm for constrained OCO that applies Polyak feasibility steps to ensure anytime constraint satisfaction $g(x_t) \\leq 0, \\forall t$ and $\\mathcal{O}(\\sqrt{T})$ regret.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed review. We have responded to each concern below.\n\n**Q1. The algorithm in the paper closely resembles the one in Liang (2024), which studies constrained variational inequalities.**\n\nWe were not previously aware of the recent work (Liang et al, 2024), which studies variational inequalities with functional constraints. Similar to our work, the algorithm in Liang et al (2024) uses a single iterate sequence and only uses constraint information at the chosen iterates. However, the analysis in Liang et al (2024) *cannot* be applied to our setting for the following reasons:\n\n1. Liang et al (2024) assumes that the constraint functions $g_i$ has Lipschitz gradients (i.e. $\\beta$-smooth), whereas we do not. This assumption is critical to the analysis in Liang et al. (2024), e.g. in equation (5), and therefore we require a different analysis approach.\n2. Liang et al (2024) requires solving a QP subproblem at each iteration. On the other hand, our approach doesn't require solving a subproblem. This is critically important in the constrained OCO literature, because the constrained OCO problem was introduced for the sole purpose of avoiding subproblems and their computational burden. This is explicitly stated in Mahdavi et al. (2012), which introduced the constrained OCO problem.\n3. Liang et al (2024) only studies variational inequalities, which *does not* extend to the OCO setting in general.\n\nAlthough our analysis is completely distinct from the one in Liang et al (2024), there are some similarities in the *algorithm design* for the special case of fixed cost functions $f_t = f$, one constraint function, and  $\\beta$-smooth constraints. In this case, our algorithm can be written as (with $\\rho = 0$),\n$$\nx_{t+1} = \\Pi_{R \\mathbb{B}} \\left( x_t - \\eta \\nabla f(x_t) - \\frac{[g(x_t) - \\eta \\nabla f(x_t)^\\top \\nabla g(x_t)]_+}{|| \\nabla g(x_t) ||^2} \\nabla g(x_t) \\right).\n$$\nAt a high-level, this resembles the version of the algorithm in Liang et al. (2024) for the special case of one constraint function (see Algorithm 2 in Liang et al. (2024)).\nHowever, there are some key differences:\n- Liang et al. (2024) applies the decreasing step-size $\\eta$ to the entire third term, whereas we only apply it to $\\nabla f(x_t)^\\top \\nabla g(x_t)$.\n- Liang et al. (2024) applies the scaling $\\alpha = G_g/R$ to $g(x_t)$.\n- Liang et al. (2024) adds an additional constraint to ensure that the iterates are bounded, whereas we use a projection onto $R \\mathbb{B}$.\n\nThese differences in algorithm design further highlight the needed for distinct analysis between our work and Liang et al. (2024).\n\nWe thank the reviewer for pointing out this work and will add the above discussion to the paper.\n\nLiang et al. \"Primal Methods for Variational Inequality Problems with Functional Constraints,\" arXiv:2403.12859\n\n**Q2. Assumption 4 is too strong and uncommon in the prior literature.**\n\n\nWe respectfully disagree with the statement that Assumption 4 is uncommon in prior literature, as it is used in the fundamental works on OCO with constraints (Mahdavi et al., 2012; Jennaton et al. 2016). To help put this assumption in context, we note that it is implied by Slater's condition (provided that the other assumptions hold). \n\nTo see this, suppose that Slater's condition holds, i.e. there exists $y \\in \\mathbb{R}^d$ and $\\xi > 0$ such that $g(y) \\leq - \\xi$. Then, let $\\epsilon = \\xi/2$ and $\\sigma = \\xi/(4R)$. Then, it holds for any $x \\in \\mathbb{R}^d$ and $s \\in \\partial g(x)$ where $g(x) = -\\epsilon$,\n$$\n-\\xi \\geq g(y) \\geq g(x) + s^\\top(y- x) \\geq - \\epsilon - || s || || y - x || \\geq - \\epsilon - 2 || s || R.\\\\ \n$$\n$$\n\\implies || s || \\geq \\frac{\\xi - \\epsilon}{2 R} =  \\frac{\\xi}{4 R} = \\sigma.\n$$\nThis is precisely Assumption 4.\n\n**Q3. There is an issue with the analysis in that it is possible for $\\mathcal{X}_\\rho = \\emptyset$.**\n\nThank you for pointing this out. This is due to a typo in Assumption 4. There is a missing negative, the $g(x) =\\epsilon$ is supposed to be $g(x) = - \\epsilon$. The claims of the paper remain unchanged by fixing this typo, as the correct form of the assumption is used throughout the analysis. \n\n**Q.4. The result in Theorem 1 heavily relies on the relationship between $\\epsilon$ and $\\sigma$. Could you provide results justifying that the ratio $\\frac{\\epsilon}{\\sigma}$ remains bounded?** \n\nSimilar to prior work (Mahdavi et al., 2012; Jennaton et al., 2016), the terms $\\epsilon$ and $\\sigma$ are assumed to be constants and the regret bound depends on them.\n\n**Q.5. Could you clarify what would change if the tightening parameter were omitted, i.e., if we set $\\rho=0$?**\n\nWe kindly point the reviewer to Corollary 2 in the paper. This corollary shows that choosing $\\rho = 0$ ensures that $g(x_t) \\leq O(1/\\sqrt{t})$.\n\n**Q.6. What is $\\alpha$ in line 314? Are you referring to $\\epsilon$?**\n\nThank you for pointing out this typo. It is supposed to be $\\rho$ instead of $\\alpha$.", "claims_and_evidence": "Yes, the claims are supported by the theorem.", "methods_and_evaluation_criteria": "Yes, the proposed method makes sense for constrained online convex optimization problems.", "theoretical_claims": "Yes. There are some issues:\n1. Issue with $\\mathcal{X}_{\\rho}$ when $g^* = \\min_x g(x) = 0$: In this case, $\\mathcal{X}{\\rho} = \\emptyset$, which would break the analysis in line 300.\n2. The result in Theorem 1 heavily relies on the relationship between $\\epsilon$ and $\\sigma$. If $\\frac{\\epsilon}{\\sigma}$ is very large, the bound will blow up. Could you provide results justifying that this ratio remains bounded?", "experimental_designs_or_analyses": "Yes. This paper only provides a toy example. It would be great to see some large-scale experiments.", "relation_to_broader_scientific_literature": "The key contribution of using Polyak feasible step sizes is closely related to the constrained optimization literature.", "essential_references_not_discussed": "The algorithm presented in this paper closely resembles the one proposed in [Liang, 2024] for Variational Inequality Problems with Functional Constraints and . It would be beneficial to discuss the similarities and differences between these approaches.\n\nReference:\n\n[1]. Liang Zhang, Niao He, and Michael Muehlebach. Primal Methods for Variational Inequality Problems with Functional Constraints. 2024", "other_strengths_and_weaknesses": "Strength:\nIt is great to see polyak feasible stepsize is used in online convex optimization problems.\n\nWeaknessses:\nAssumption 4 is too strong, which is uncommon in prior literature [Yu, 2017], [Yuan, 2018]. It would be helpful to provide some justification and intuition on when this assumption holds.\n\n\nReferences:\n\n[1]. Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic constraints. Advances in Neural Information Processing Systems, 30, 2017.\n\n[2]. Jianjun Yuan and Andrew Lamperski. Online convex optimization for cumulative constraints. Advances in Neural Information Processing Systems, 31, 2018.", "other_comments_or_suggestions": "What is $\\alpha$ in line 314? Are you referring to $\\epsilon$?", "questions_for_authors": "I am curious whether the tightening parameter $\\rho$ is essential for this algorithm. It appears that setting $\\rho = 0$ would still preserve most of the results. Could you clarify what would change if the tightening parameter $\\rho$ were omitted, i.e., if we set $\\rho = 0$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AhyD2qW4nk", "reviewer": "Reviewer_yxBf", "summary": "This paper addresses the problem of Online Convex Optimization (OCO) with constraints, where the goal is to minimize regret while ensuring that the constraints are satisfied anytime. The authors propose an algorithm that combines gradient descent steps with Polyak feasibility steps to achieve $O(\\sqrt{T})$ regret and anytime constraint satisfaction when the strict feasibility point is known. They also provide a guarantee when the strict feasibility point is not known. The authors validate their approach through numerical experiments, demonstrating that their algorithm achieves constraint satisfaction without sacrificing regret performance.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed review. We have responded to each concern below.\n\n**Q1. The contribution is marginal compared to the previous work.**\n\nWe respectfully disagree. The contribution of our paper is an algorithm for constrained OCO that *for the first time* attains anytime constraint satisfaction $g(x_t) \\leq 0$ and optimal regret $O(\\sqrt{T})$, while only using first-order constraint feedback. Unlike prior methods for this problem, which sacrifice feasibility for efficiency, our results show that it is possible to guarantee both feasibility and efficiency. Our approach is based on the use of Polyak steps with respect to the constraint, which has been long overlooked by the OCO literature.\n\n**Q2. My major concern is that the algorithm proposed in the paper has already appeared in previous work (e.g., [1] and [2]).**\n\nYou are correct that similar algorithms have appeared in the offline optimization literature (see Section 1.1.3). However, the theoretical analysis used in the offline optimization literature is not applicable to the OCO setting. Specifically, the offline optimization works mentioned by the reviewer [1][2] *do not* provide applicable analysis for the following reasons:\n- [1],[2] require that the suboptimality gap is non-negative, i.e. $f(\\hat{x}_t) - f^* \\geq 0$, as used in the proofs for Theorem 7 in [1] and Theorem 4.6 [2]. In the online convex optimization setting, there is no guarantee that $f_t(x_t) - f_t(x^*) \\geq 0$, and therefore we need a different analysis approach. See discussion on line 151 right side.\n- [1],[2] only give constraint violation guarantees on the average iterate $\\hat{x} = \\frac{1}{\\sum_{\\tau} \\alpha_\\tau} \\sum_{\\tau}  \\alpha_\\tau x_\\tau$, whereas we provide violation guarantees on every iterate $x_t$, i.e. $g(x_t) \\leq 0$ for all $t$, and therefore need a different analysis approach. Note that we *cannot* simply choose $x_t = \\hat{x}_t$, because we only get feedback at $x_t$ and therefore the algorithm structure would no longer apply.\n- [1] requires constraint information on the intermediate iterate ($v_k$ in the notation of [1]), whereas we only use constraint information at the played actions $x_t$. \n- [2] requires that the cost function has Lipschitz gradients ($\\beta$-smooth) as used in Lemma 4.1 of [2]. Since we do not assume Lipschitz cost gradients, we need a different analysis approach.\n\nLastly, please note that [1] is already cited and discussed.\n\n**Q.3 [2] already proposed the linear approximation in Algorithm 1, which is the same as the \"First-order Approximation\" in the paper.**\n\nThank you for pointing out that this part of our algorithm design is also used in [2], which studies (offline) optimization. We were not previously aware of this recent work. However, please note that the analysis from [2] does not apply to our setting for the reasons mentioned in the answer to Q.2 above. To clarify our contributions in the paper, we will add the following to Section 1.1.3.\n\n\"This technique of using a first-order approximation is closely related to the approach used in the recent (offline) optimization work [2]. However, the analysis in [2] is not applicable to our OCO setting because (a) it requires that the suboptimality gap of the iterates $f( x_t ) - f^* \\geq 0$ is non-negative, (b) only provides guarantees on the average of the iterates as opposed to our guarantees on every iterate, and (c) requires that the cost function has Lipschitz gradients.\"\n\n**Q4. When the strict-feasibility does not hold, the algorithm would have a large period of $O(\\log(T))$ possible violation, which might not be proper for safety-critical applications.**\n\nWithout knowledge of a feasible point, there is no way for any algorithm to ensure constraint satisfaction from the first round. Nonetheless, our results show that in such a setting, we can guarantee that the constraint is satisfied for all but a small number $O(\\log(T))$ of rounds.\n\nIn order to guarantee that the constraint is *always* satisfied, we require the slightly stronger assumption of a known *strictly-feasible* point. This assumption is motivated by the fact that, in safety critical-applications, there is typically a \"safety margin\" that is built in to traditional methods to account for modeling inaccuracies. For example, in personalized healthcare applications, medical standards specify a drug dosage that will be safe to the patient despite some small variations in the patient's characteristics (e.g. weight, blood pressure), and therefore this dosage can be used as a strictly-feasible point.\n\n**Q.5 The paper only considered the setting where the constraints are static.**\n\nThe problem of OCO with fixed constraints is a major problem in the machine learning community. To illustrate this, Google Scholar shows that the first work on this problem (Mahdavi et al., 2012) has been cited 313 times.\n\n**More Experiments:** https://anonymous.4open.science/r/oco_pfs_rebuttal-1050/", "claims_and_evidence": "Yes, the claims are clear and convincing.", "methods_and_evaluation_criteria": "Given the vast literature on OCO with constraints, the paper might consider more baselines. For example, Yuan et al., 2018, could be a good baseline as they studied a strict violation metric.", "theoretical_claims": "I checked the theoretical claims and proofs, and they seem correct.", "experimental_designs_or_analyses": "No specific issues.", "relation_to_broader_scientific_literature": "The contribution is marginal compared to the previous work. \n\nMy major concern is that the algorithm proposed in the paper has already appeared in previous work (e.g., [1] and [2]). [1] leverages the Polyak steps to deal with the stochastic constraints (which seems more challenging), and [2] already proposed the linear approximation in Algorithm 1 (SHAM), which is the same as the \"First-order Approximation\" in the paper. \nThe contribution is marginal. \n\n[1] Ion Necoara and Nitesh Kumar Singh. Stochastic subgradient projection methods for composite\noptimization with functional constraints. JMLR, 2022. \n\n[2] Nitesh Kumar Singh and Ion Necoara. Stochastic halfspace approximation method for convex optimization with nonsmooth functional constraints. 2024.", "essential_references_not_discussed": "Yes, as discussed above [1] and [2].", "other_strengths_and_weaknesses": "Weaknesses:\n\n- If I understand correctly, when the strictly feasibility does not hold as in Corollary 1, the algorithm would have a large period of $O(\\log T)$ where the constraints could violate. This might not be proper for safety-critical applications. \n\n- The paper considered the setting where the constraints are static. This seems less challenging and it would be more convincing to study stochastic or time-varying constraints.", "other_comments_or_suggestions": "Justifying the paper with [1] and [2] above and addressing the weakness above would be convincing. More baselines are needed in the experiments.", "questions_for_authors": "No further questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sHipzz4Yuh", "reviewer": "Reviewer_JVnc", "summary": "The paper investigates online convex optimization subject to fixed convex constraint by incorporating Polyak feasibility steps. This leads to a sublinear regret and different constraint violation guarantees: no violation if initial start satisfies constraint, no violation after $O(\\log T)$ rounds or cumulatively constrained evaluation is small.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your detailed review and positive appraisal of the work. We discuss each of your points below.\n\n**Q.1. typo: line 316 : $y_{t}$ instead of $y_{t+1}$**\n\nYou are correct. Thank you for pointing this out.\n\n**Q.2. section 3.4 begins with using eqn (9), and quoted Fact 1 which was with reference of eqn (2) or line 5 of Algorithm 1, $\\rho$ in different place means different things, although it does not affect the result, but in between line 382 left - line 331 right causes unnecessary confusion.**\n\nThank you for pointing this out. We will adjust our notation to make it clearer.\n\n**Q.3. Result reporting: As theorem 1 is already a consequence of plugging in hyper parameters thus it does not allow seeing how parameter changes yield to corollaries. It only became clear how hyper parameters change after reading section 3.3 and 3.4**\n\nThank you for this suggestion. We agree that it would improve the clarity significantly. We will adjust the presentation of the results accordingly.\n\n**Q.4. the regret scales with multiplicative Lipschitz constants $G_f G_g$, from current analysis it does not seem to be possible to have additative dependence $G_f + G_g$, is this common?**\n\nSimilar dependence on the Lipschitz constant is in the regret bound of prior work Mahdavi et al (2012). In particular, their Theorem 8 has the term $G^{5/2}$, where $G = \\max\\\\{G_g, G_f\\\\}$.", "claims_and_evidence": "The results support the claim", "methods_and_evaluation_criteria": "The paper use standard metric, regret and cost associated with constraint violation", "theoretical_claims": "All steps were checked.", "experimental_designs_or_analyses": "The experiment compared an extension of previous work with current work. Theoretically they can achieve the same bound, empirically the current work seems to be an interpretation between low regret and low violation cost.", "relation_to_broader_scientific_literature": "An new approach to solve constrained OCO problem with comparatively the same rate as the extension from previous work. (The extension was done by the authors)", "essential_references_not_discussed": "Well referenced.", "other_strengths_and_weaknesses": "The paper is well written and easy to follow. The explanation of incorporating Polyak feasibility steps is sensible and theoretically supported.", "other_comments_or_suggestions": "typo: line 316 : y_{t} instead of y_{t+1}\n\nsection 3.4 begins with using eqn (9), and quoted Fact 1 which was with reference of eqn (2) or line 5 of Algorithm 1, $\\rpo$ in different place means different things, although it does not affect the result, but in between line 382 left - line 331 right causes unnecessary confusion.\n\nResult reporting: As theorem 1 is already a consequence of plugging in hyper parameters thus it does not allow seeing how parameter changes yield to corollaries. It only became clear how hyper parameters change after reading section 3.3 and 3.4", "questions_for_authors": "the regret scales with multiplicative Lipschitz constants $G_f G_g$, from current analysis it does not seem to be possible to have additative dependence $G_f + G_g$, is this common?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a $O(\sqrt{T})$ regret analysis for online constrained problems which also guarantees that the constraint $g(x_t) \leq 0$ holds any time for the iterates $x_t$. This is the first such regret analysis to guarantee that the constraint holds (as opposed to a regret over the constraint). 
The method underlying this analysis relies on linearizing the constraint, and using the standard gradient model for the objective. The reviewers have raised that this is very similar to a method used in offline optimization [1] and [2], and that the analysis might also be similar.  Because the reviewers were not overall favorable, I have gone into the details of this paper and the papers that the reviewers find similar [1] and [2]. The similarity in the method is not surprising, this is a variant of one of the most standard SQP type methods. What stands out in this paper is identifying that exactly this variant of the method, together with a carefully constructed analysis could achieve the correct regret and any time feasibility. The analysis in [1] and [2] does not carry over for a number of reasons (including using stationarity conditions that do not hold online). As such, this paper solves an interesting  valid open problem in online learning. Which is why I recommend it be accepted.


[1] Liang Zhang, Niao He, and Michael Muehlebach. Primal Methods for Variational Inequality Problems with Functional Constraints. 2024

[2] Nitesh Kumar Singh and Ion Necoara. Stochastic halfspace approximation method for convex optimization with nonsmooth functional constraints. 2024.
Decision: Accept (poster)