Single-loop Algorithms for Stochastic Non-Convex Optimization with Weakly-Convex Constraints
Authors: Ming Yang
Gang Li
Quanqi Hu
Qihang Lin
Tianbao Yang
Venue: Accepted by TMLR ()

Abstract: Constrained optimization with multiple functional inequality constraints has significant applications in machine learning. This paper examines a crucial subset of such problems where both the objective and constraint functions are weakly convex. Existing methods often face limitations, including slow convergence rates or reliance on double-loop algorithmic designs. To overcome these challenges, we introduce a novel single-loop penalty-based stochastic algorithm. Following the classical exact penalty method, our approach employs a  hinge-based penalty, which permits the use of a constant penalty parameter, enabling us to achieve a state-of-the-art complexity for finding an approximate Karush-Kuhn-Tucker (KKT) solution. We further extend our algorithm to address finite-sum coupled compositional objectives, which are prevalent in artificial intelligence applications, establishing improved complexity over existing approaches. Finally, we validate our method through experiments on  fair learning with receiver operating characteristic (ROC) fairness constraints and continual learning with non-forgetting constraints.

Published in Transactions on Machine Learning Research (01/2026)
Single-loop Algorithms for Stochastic Non-Convex Opti- mization with Weakly-Convex Constraints
Ming Yang
myong edu
Deportment of Computer Science Engineering
Tezas ABM University
Gang Li
gong-liötamu. edu
Deportment of Computer Science Engineering
Texas ABM University
Quanqi Hu
quanqi-ha@tamuu edu
Department of Computer Science & Engineering TEras A&M Universily
Qihang Lin
gllaagg-linnuwioveeee edu
Tippie College of Business
The University of Towa
Tianbao Yang
Satabooo--nngggaaaaaa edu
Department of Computer Science Engineering
Texas ABM University
Reviewed on OpenReview: https: openreview. net/ forum? id= aCgOR2KvAI
Abstract
Constr optimization with multiple functional inequality constraints has significant ap- plications in machine learning. This paper examines crucial subset of such problems where both the objective and constraint functions are weakly convex. Existing methods often face limitations, including slow convergence rales or reliance on double-loop algorithmic designs. To overcome these challenges, we introduce a novel single-loop penalty- stochastic algorithm. Following the classical exact penalty method, our approach employs hinge- based penalty, which permits the use of constant penalty parameter, enabling to achieve state-of-the-art complexity for finding an approximate Karush-Kuhn-Thuen (KKT) solution. We further extend our algorithm to address finite-sum coupled compo- sitional objectives, which are prevalent in artificial intelligence applications, establishing improved complexity over existing approaches. Finally, we validate our method through ex- periments on fair learning with receiver operating characteristic (ROC) fairness constraints and continual learning with non-forgetting constraints.
1 Introduction
This paper focuses solving the following non-linear inequality constrained optimization problem:
min F(x), s.t. hx(x) S 0, ==
(1)
where F' and hg, l I,..., are stochastic, weakly convex and potentially non-smooth. This general formu- lation captures wide range of practical optimization problems where non-smoothness arises in the objective and constraint functions. Inequality constrained optimization arise in many applications in ML/ AT, including continual learning (Li et al. 2024a), fairness-awer aware learning (Vogel et al. 2021), multi-clase Seyman-Peearsie classification (mNPC) problem (Ma et al.] 2020), robust learning (Robey et al. 2021), policy optimization problem for reinforcement learning (Schulman al., 2015), and distributed data center scheduling prob-
lem Yu et al.] 2017).

---

Published in Transactions on Machine Learning Research (01/2026)
Table 1: Comparison with existing works. We consider that both objective function and constraint function oracles are stochastic. In the Constraint column, hg mcans multiple constraints, k from to m. In Convexity column, NC means Non-convex, WC means Weakly Convex, C means Convex. The monotonicity column means non-decre.sing. The last column Complexity means the complexity for finding an (nearly) e-KKT
point of equation] 1
Reference
Loop
Objective
Constraints
Smoothness
Convexity
Monotonicity
Complexity
Alacaoglu & Wright
2024
Single Loop
F(.)
Ri-)) =0
F,h
NC
none
Ole-
Li ct al.
2024b
Double Loop
F(- g(1+
h(()) =
F,h
C (g),, NC (F,A)
none
Ma ct m|
2120
Double Loop
P(o)
hu()
none
WC (1,
none
Oir ") Ole-")
Boob et aL.
2024
Double Loop
F(-)
hu(-) <
nome
WC (F, hu)
none
mang & Lin
2023
Single Loop
F(-)
h(f-) 50
noue
WC [F), C (t)
none
Ole *)
Li et sl.
2021a
Single Loop
E, f.la.11))
hu()) 5
fi hg
NC (f..9.hh))
none
Ole-7)
Lau & Xm1 2025
Single Loop
PG)
1v(-)00
none
WC (F.by)
none
Oir ")
Ours
Single Loop
none
WC.F,ha)
none
Ole "
Ours
Single Loop
E, ((ggg())))
hx(-50
nome
WC (Ji 9i. ha)
J
Ole-1) Ole-1)
Ours
Single Loop
2x()500
f:.
WC (hg)
none
In optimization literature, many techniques have been studied for solving convex constrained optimization problems, including primal-dual methods (Huang et al.) [025 Boob et al., [203 Pu al.] 2024 Nediè
& Ozlaglar, 2009), augmented Lagrangian methods (Birgin & Martnez 2014); penally methods (Boyd & Vandenberghe 2004), and level-set methods (Lin et al., 2018). However, the presence of non-convexity
in the problem often complicates algorithmic design and convergence analysis, while non-smoothness and
stochasticity add additional layers of difficulty.
Several recent studies have explored stochastic non-convex constrained optimization under varions assump- tions. Ma et al. (2020) and Boob et al. (2023) initiated the study of stochastic optimization with weakly convex and non-smooth objective and constraint functions. Inspired by proximal-poii methods for weakly- convex unconstrained optimization (Davis & Grimmer 2019), they have proposed double-loop algorithm, where a sequence of convex quadratically regularized subproblems is solved approximately. They have de- rived the state-of-the-arl complexity in the order of O(1/c5) for finding nearly <-KTT solution under a uniform Slater's condition and strong feasibility condition, respectively.
Recently, Alacaoglu & Wright 2024] ; Li et al. 2024a Huang & Lin 2023 have proposed single-loop algorithms for stochastic non-convex constrained optimization. However, these results either are ricted to smooth problems with equality constraints {Alacaoglu & Wright 2024) or suffer from an iteration complexity higher than ((1/e) (Li et al. 2024a Huang & Lin 2023). This raises intriguing question: "Can we design single-loop method for solving non-smooth weakly-comee stochastic constrained optinázation problems to match the state-of-the-ee complenity of O(1/c5) for finding nearly <-KTT solution!'
We answer the question in the affirmative. We propose a novel algorithm based on the well-studied exact penalty method (Zangwill 1967: Evans et al., 1973). Different from Alacaoglu & Wriight (202)); Li et al. (2024a) who used quadratic or squared hinge penalty, we construct a penalty of the constraints using the non-smooth hinge function, i.e., by adding 1 -En [x)x(x)]+ into the objective, where 3 is penalty parameter. Despite being non-smooth, the benefits of this penalty function include (i) it preserves the weak convexity of in the penalty: (ii) it allows using constant 3 as opposed to a large B required by the squared hinge penalty (Li ct al. 2024a); (iii) it introduces the structure of finito-sum coupled compositional oplimization (FCCO), enabling the use of existing FCCO techniques in the algorithmic design. Consequently, this approach establishes state-of-the assumption similar to those in Li et al. (2024a); Alacaoglu & Wright (2024). We summarize our contributions as follows.
m
complexity for achieving a nearly e-KTT solution, under a regularity
We propose a non-smooth, hinge-based exact ponalty mothod for tackling non-convex constrained optimization with weakly convex objective and constraint functions. We derive a theorem to guar- antee that nearly e-stationary solution of the penalized objective is a nearly cKKT solution of the original problem under regularity condition of the constraints.
We develop algorithms based on FCCO to tackle a non-smooth weakly convex objective whose unbiased stochastic gradient is available and structured non-smooth weakly-convex objective that
2

---

Published in Transactions on Machine Learning Research (01/2026)
is of the FCCO form. We derive ttate-of-the-art complexity of ((c-9) for finding nearly c-KKT solution.
We conduct experiments on two applications in machine learning: learning with ROC fairness con- straints and continual learning with forgetrgg constraints. The effectiveness of our algorithms are demonstrated in comparison with an existing method based on squared hinge penalty function and double-loop method.
2 Related Work
Despite their long history of study, recent literature on optimization with non-convex constraints has intro-
duced new techniques and theories for the penalty method (Lin et al. 2022), Lagrangian methods (Sahin
et al. 2019 Sun & Sun 2024
Li et
al. 2024b 2021 p. the sequential quadratic programming methods Bera-
has et al. 2021 2025
Curtis et al. 2024 Na et al. 2023) and trust region method (Fang et al. 2024). These
works mainly focused on the problems with smooth objective and constraint functions. On the contrary,
based on Moreau envelopes, Ma et al. (2020) Boob et al. (2023 : Huang & Lin 2023): Jia & Grimmer 2002
have developed algorithms and theories for problems with non-smooth objective and constraint functions.
However, these methods cannot be applied when the objective function has a compositional structure. The
method by Li et al. (2024a) can be applied when the objective function has a coupled compositional structure, but it requires the objective and constraint functions to be smooth. Compared to their work, relax the smoothness assumption, but assume the monotonicity of the outer function in the compositional structure.
Alacaoglu & Wright (2024) studies a single-loop quadratic penalty method for stochastic smooth nonconvex equality constrained optimization under a generalized full-rank assumption on the Jacobian of the constraints. Under a similar assumption, Li ct al. (2024b) proposed a double-loop inexact augmented Lagrangian method using the unn-eetu variance-reducel proximal stochastic gradient algorithu a subroutine. Both Alacaoglu & Wright (2024) and Li et al. 2024b) consider only smooth equality constraints and hence are not applicable to non-smooth constraint functions. Ma et al. (2020) and Boob et al. (2023) studied weakly convex non-smooth optimization with inequality constraints. They proposed double-loop
methods, where a sequence of proximal-point subproblems is solved approximately by a stochastic subgra-
dient method (Yu et al. 2017) or a constraint extrapolation method (Boob et al. 2023). Under a uniform
Slater's condition and strong fcasibility assumption, respectively, Ma et al. (2020) and Boob et al. (2023)
establish a complexity of (L1/e)). Under the uniform Slater's condition, Huang & Lin (2023) proposed a single-loop switching subgradient method for non-smooth weakly convex constrained optimization problems, but the complexity of their method is O(1/E)) when the constraints are stochastie.
Motivated by applications from continual learning with non-forgetting constraints, Li et al. (2024a) intro- ducod a single-loop squared hinge ponalty mothod for a FCCO (Wang & Yang 2022) problem, where the objective function takes the form of (e(s-()) and the constraints are non-convex and smooth. They establish a complexity of O(1/²") under the generalized full-rank assumption on the Jacobian of constraints. Our results can be easily extended to FCCO problem with nonconvex but unnecessarily smooth inequality constraints. We show that our method improves the complexity to ((1/c)) in two cases: (1) fi, Is and hy are non-smooth weakly convex and fi is monotone non-decreasing, and (2) fa and gi are smooth nonconvex but h2 is non-smooth weakly convex. Note that the second case includes the special case where fi, 9: and hg are smooth non-convex. A comparison with prior results in presented in Table I
We also note that some works have considered transferring inequality constraints into equality constraints by adding a slack variable for cach constraint (Fukuda & Fukushima, [017 Ding Wright 2023 Li et al. 2021 However, these approaches either require stronger second-order conditions to ensure that KKT solution to the equality--oonsraiind constrained problem also applies to the original eeequality-constrainee problem (Fukuda & Fukushima| 2017: Ding & Wright, 2023), or they rely on the boundedness of constraint functions to guarantee this transfer (Li et al.) 2021) (cf. Section 4.3 for more discussions). Even when such transformation is feasible, algorithms for non-smooth stochastic raint functions remain underdeveloped, underscoring the uniqueness and significance of our contributions.
Finally, we would like to acknowledge a concurrent work by Liu & Xu 2025). Their study also explores penalty method for problems with weakly convex objective and constraint function. The key differences
3

---

Published in Transactions on Machine Learning Research (01/2026)
between work and theirs are: (i) although they consider vector-valued function consisting of multiple components, they treat multiple constraint as single one, i.e. they need to compute mini-batch estimators of all constraint functions at each iteration in their algorithm. In contrast, we do sampling on the constraint functions, and only require estimating ((1) constraint functions at each itcration. (ii) they do not directly use the hinge penalty function, but instead adopt a smoothed version of it; and (iii) they employ the SPI- DER/SABE /SRAH technique to track the constraint function value, which requires periodically using large batch sizes. In contrast, we track multiple constraint function values by employing the MSVR technique (Jiang using only a constant batch size.
et al.
2022
3 Notations and Preliminaries
Let ||-I| be the f2-norm. For vb Id + [U(+,,,, the subdifferential of ie at x is 0x((x) = ER (xx) 2
(xx)+ + (G.'' +X[[x''' x' + x}, and ( E @xb(x) denotes a subgradient of 1b at x. Let []+ = max (0. .
denote the hinge function. We say vb is p-strongly convex (μ 2 0) if (x) 2
for
any (x, x') and any Ç 0x)(x). We say & is p-weakly convex (p> ( (xx
for any (x, and any Ç E (x)(x') We say v is I-smooth (L 2 0) if [x(x) - vxx) + (Vx('x
1 xx12 for any (x,x).. For simplicity, we abuse (v((x) to denote one subgradient from the corresponding
subgradient set when no confusion could be caused.
Throughout the paper, we make the following assumptions on
Assumption 3.1. (a) F is Po- Po-weakly convex and L Lipsschht contimuous; (b) h+)()) is P1-weakly convex and L,-Lipschitz continnous for ==
For a non-convex optimization problem, finding a globally optimal solution is intractable. Instead, a Karush- Kuhn-Tucker (KKT) solution is of interest, which is an extension of a stationary solution of an unconstrained non-convex optimization problem. A solution x is KKT solution to (1) if there exist À (A1,..., Am) e RT such that 0 E 0F(x) + Σx= xx,)h(x), hxx I 0, Vk and (x = 0 wk. Of interest in non-asympiotic analysis is finding an e-KKT solution given below.
Definition 3.2. A solution x is an cKKT solution to 11 if there exist A = (A1, Am) J E RT such that dist (0, 0F(x) + Ex= (x)) S hx(x) S e, V,Y and (x) (x) Se e if hx 2 0 or d = 0 if hu (x) < 0 for == I.....,,7
However, since the objective and the constraint functions are non-smooth, finding an kKKTT solution is not tractable, even the constraint functions are absent. Let consider simple example min& |x]. The only stationary point is the optimal solution x, = O, and any + 0 is not e-stationary solution (e < 1) no matter how close x to O. In other words, unless the iterate generated by the algorithm can exactly land on x = 0, it will not produce an e-stationary point. To address this issue, an effective approach for solving non-smooth optimization is to approximate the original problem by a smoothed one using different smoothing techniques, including Nesterov's 's smoothing Nesterro 2005), randomized smoothing (Kornowski & Shamir 2022). and Moreau envelope (Davis & Grimmer] (201)). Based on Moreau envelopes, Ma et al. [2020g ; Boob al. (2023): Huang & Lin (2023); ; Jia & Grimmer (202)) have developed algorithms and theories for problems with non-smooth objective and constraint functions, which derives a nearly e-KTT solution. We follow Moreau envelopes technique on non-smooth weakly convex optimization and consider finding a nearly e-KT solution defined below.
I if there exist x and À = (AI,..., Am) E RT such that (i) ||x - x|| < Oc), dist(0, (F(x) + Ems dxāh(x). S c, (ii) (x) S c, Vk, and (ii) Aeh (x) S if (x) 2
Definition 3.3. A solution x is a nearly eKKT solution to
or 2 = 0 if (x) < 0 for A = ==1,...,, 1,...,m.
In order to develop our analysis, we introduce the Moreau envelope of p-weakly convex function di Φo(x) == miny {d(y) + 1 Ilyy x[]?], where 0 < <p1 The Moreau envelope is an implicit smoothing of the original problem (cf. Lemma B.1 in Appendix). Hence, if we find x such that (V)o())) S c, then we can say that x is close to point x that is e-stationary Davis & Grimmer 2019 We call x a nearly e-stationary solution of minx (xx).
Remark: Our current formulation focuses on the non-smooth case, there is also a simple extension in the smooth setting. Suppose the objective and constraint functions are smooth, using the Lipschitz contiuity of the gradients, and that of constraint. functions, it is easy to prove that a nearly e-stationary point is also
4

---

Published in Transactions on Machine Learning Research (01/2026)
O(c)-stationary point. This is because ||x x||2 S O(e) and leveraging the Lipschitz comunit condition, every condition in the definition of nearly <-KKT solution can be converted to that on x.
4 A Hinge Exact Penalty Method and Theory
The key idea of the hinge-based exact
penalty method to solve the following unconstrained minimiza- Evans et al. 1973), where
tion Zangwill 1967
a penalty parameter:
min x(x) == F(x)+ + B Th
Ex_, [xx(x)]++
(2)
For clarity of notation, we define h (x) [hg (x)]++ Let ahh (x)x(x)]+ E [0, be the subdiffercntial of [2]+ at h4 (x), and let 0hi (x) be the subgradient in terms of x.
Lemma 4.1. Under Assumplion 3.1
((x)
in is C-weakly convex and L-Lipschilz, where C po + 3p
and L = LF + BLr.
Our hinge exact penalty method is to employ a stochastic algorithm for finding an e-stationary solution to (x) for some < 1/C. We establish a theorem below to guarantee that such x is a nearly e-KKT solution to
Thcorem 4.2. Assume that there crists ö > 0 such that
aht o ont
1
dist 0, m
2 8, VX E V
(3)
where V= fx: maxx (x) > 0}. If x is an e-slationary solution to Φx(x) for some < I/C and a constand 3 > (e+ Lr)/ö, then x is a nearly EKKKT solution to the original problem Proof. Let x = proxoo (x). By optimality of X, we have
B m
0 0F(x)
+
oh (x) (x) -x-x)/
m
k=1
Since VDbo(x)]] S e, then we have ||x
x
V (x s 0c. Then we have
8 m
dist 0, (.0F(x)
+
ah (x) S [|( x)/01 s..
m
Since (x) = (x) (see Bauschke al.
2217
Corollary 16.72)), where
if hu (x) > 0, if hy (X) = 0, cd]ha(E)]++
&x
[0, 1]
0 if (x) < 0,
there exists d S6a 2 0, vk such that dist (0, (F) + Ex= (x)hx(x) Se. Thus, we prove condition (i) in Definition 3.3. Next, let us prove condition (ii). We argue that max; (x) s 0. Suppose this does not hold, Le., max; (x) > 0, we will derive a contradiction. Since Iv E OF(xx such that
m
B ET ah (x) || 2 35 LF, m k=1 which is a contradiction to the assumption that 3 > LF)55 Thus, max; hy (x) S O. This proves condition (ii). The last condition (iii) holds bocause: Ag m
c2 dist (o.v+ 8
m k=1 ang (xx) 2 dist (0.0
ET
(4)
which is zero if (x))) < O; and \xhx(x) s 0.
not spccific to our mothod but is shared by all ponalty- based approaches, including recent works such Alacaoglu & Wright (2024), Li al. (2024b), and Li Li et al. (2024a). This assumption reflects fundamental challenge in non-convex constrained optimization: without condition such as (3), the problem becomes ill-posed and is generally unsolvable using first-order methods. There is potential to slightly relax assumption 3 In our current formulation, we assume
Assumption (3)
(3) holds over the entire set V. However, it may suffice to require (3) to hold only on a subset. of V, defined as V. = fa : 2 max hx(x)) > 0} for some constant c O. This is a strictly weaker assumption.
Under this relaxation, the algorithm can be initialized within the feasible region and proceed with step sizes chosen carefully to ensure that all intermediate iterates remain within Ve- Note that even if some
5

---

Published in Transactions on Machine Learning Research (01/2026)
iterates become slightly infeasible, as long the step size is sufficiently small, the gradients of the constraint functions will guide the iterates back toward feasibility. This way, we can still conduct the same convergence analysis just select feasible initial point Xo and proceed with step sizes chosen carefully. This strategy has been successfully adopted in prior work (e.g., (Huang & Lin 2023
4.1 Sufficient Conditions for Eq. 3
Next, we provide some sufficient conditions for 13
First, we consider simple setting where there only one constraint h(x) S 0. The lemma below states
two conditions sufficient for proving the condition 3
The proof of Lemma 4.3 and 4.4 are presented in
Appendix B
Lemma 4.3. there erists p. 0, 0 such that (i) h(x) miny h(y) S dist(O, Oh(x))² for any x 2p
satisfying h(x) > O; and (ti) miny h(y) S -c, then condition 3 holds for ó = /2cu.
Remark: Note that the condition (i) in the above lemma is the PL condition of h but only for points violating the constraint. We can easily come up function h to satisfy the two conditions in the lemma. Let us consider h(x) = -1² Then Vh(0) = 0, which means I = 0 is a stationary point but not global optimum of h. The global optimal are x E (1,-1} and ming h(y) = -1, and hence condition (ii) holds. Any x such that (xx) > 0 would satisfy x > /2 or < -22. For these x, we have Vh(x) = 2x for x > v2 or
Vh(x) 22 for < 22.. Then for [x] 22, h(x)) miny h(y) x² 1 [Vh(=]]" holds for p 2. Hence 2μ
condition (i) holds.
Next, we present a sufficient condition for (3) for multiple constraints. The following lemma shows that the full rank assumption of the Jacobian matrix of H(x) (ha (x)(x..... (xm)....)x (x)) at that violate constraints is a sufficient condition.
Lemma 4.4. If (H) is full rank for max; h& (x) > O, i.e, dist(0, Amin (xH( a 0, Vx such that maxa hx(x) 0, where (x(x) denotes the set of sub-Jacobian matrices and Xmin denotes the set of their mēnimum singular values, then the condition
3 holds for 5 = o/m.
We refer to the above condition as Full-Rank-at- Raank-at-Voolainn--- Violating- condition (FRVP). We note that the FRVP condition for differentiable constraint functions has been used a sufficient condition in Li et al. 2024a) for ensuring
[x z (x)+
(5)
which is central to proving the convergence of their squared-hinge penalty method for solving inequality constrained smooth optimization problems: ming F(x), s.t. hx(x) S 0. k = 1,...,,7. m.
A stronger condition for equality constrained optimization with hx(x) 0, 1....,m m was imposed in Alacaoglu & Wright (2024), where they assumed that [/V Hxx)ll 2 8 (x)],, Vx. To ensure this, their method requires the full-rank Jacobian assumption to hold at all points, whereas our approach only requires
it at constraint-violatinn points. In our experiments, verified that the condition in Lemma 4.4 holds on
the trajectory of the algorithm. Detailed results are provided in Table in Appendix
4.2 Issue with squared-hings penalty
Let us discuss why using the squarod-hinge penalty function as in et al. (2024a). For simplicity of exposition and comparison with prior works, we consider differentiable constraint functions here. Using a squared- -inge penalty function gives the following objective:
B m
+(x) = F(x) +
m [hx())
(6)
Note that this objective is also weakly convex with wcak-convexity parameter given by Po + 8p1- However, the key issue of using this approach is that needs to be very large to find an (nearly) e-KTT solution. Using the same argument as in the proof of Theorem 4.2 for showing max; hy hx()) 0, the inequality

---

Published in Transactions on Machine Learning Research (01/2026)
becomes:
8 m 2 V+
E k= [Ix (h,
B
88 [|[ Lp,
Vha (x)
2
hox [x)] (x)
|lvll
where the last step follows the assumption in 5 Since [M()] contradiction we need to set B to be very large. In Li et al. (0244a) , it was set to be the order of O(1ee). As result, (--) will have large weak-convexity and Lipschitz parameters of the order O(1/e). This will lead to complexity of (2) if we follow existing studies Hu et al. 2024) to solve the problem in (6) without
+ could be very small, in order to derive a
the smoothness of and hy. which will be discussed in Section
4.3 Issue of solving an equivalent equality constrained optimization
One may consider the following equivalent equality constrained problem:
min
F(x), s.t. hx(x)= + o = 0, 1....,
(7)
x,8 8m
where $1, $1,..., Sm are introduced dummy variables. A solution x" is KKT solution to above if there exists
x= = (A1....,A..) Xm) E Rm such that 0 E OF(x*) I,..., m. However, this does not provide guarantee that x, is a KKT condition to the original constrained optimization problem as À is not necessarily non-negative. For instance, consider min 2 s.l. - S x < After adding slack variables, we have min æ s.t. x + + = 1, -x + $ = 1. However, (x, $1, = (1,0, becomes a stationary point with multipliers = (-1,0), but it not a stationary point in the original problem.
,x AESE = 0, Vk, and hx(x*) + = 0 for Ak- =
While several studies (Fukuda & Fukushima 2017 Ding & Wright 2023 have employed stronger second- order conditions to ensure that a KKT solution of the equality-constrrincc problem 7 can be converted into one for the original inequalitycoonstraneed problem, these conditions generally do nol hold for the problems we consider. Moreover, when these second-order conditions fail to be satisfied, the approach of solving the equality-constraaneed problem becomes ineffective. Our solutions will not suffer from this issue.
Specifically, Proposition 3.6. in Fukuda Fukushima (017)) shows that if a stationary solution to the equality--constranned problem (formulated using squared slack variables) satisfies the second-order suffi- cient condition (SOSC), then it is also stationary solution to the original inequality-constrainee problem (after simply removing the slack variables). Theorem 3.3. in reference (Ding & Wright, 2023) proves a similar result but under the weaker second-order necessary condition (SONC). To the best of our knowledge, no other conditions have been established in the literature.
Both SOSC and SONC conditions above are quite strong, as they require all first-order stationary points of the equality-coustrrineed problem to be also second-order stationary points at the same time. Un- fortunately, neither SOSC nor SONC is implicd by the assumptions made in our paper. This is truc even if we further assume our problem is second-order differentiable. Since our focus is on first-order methods, our assumption is related to first-order conditions only. In fact, in general, our problems may not even have gradients (non-smooth), let alone the Hessian matrix in SOSC and SONC. While the results in Fukuda & Fukushima ) Ding & Wright (2023) may be useful in practice as potential certificates of stationarity, their applicability is limited in practice. For example, one could first find stationary point for the equality- constrained problem, and then verify whether SOSC or SONC holds at the obtained solution. If lucky enough and they hold, one can conclude that the solution is stationary for the original mnequaliyy-constranne problem. However, if unlucky and these second-order conditions do not hold, we do not know if the solution is stationary for the original problem. In contrast, our method directly finds stationary point for the ineouaiitty-consttained problem without requiring such verification, hence there is no need to implement the verification procedure.
Another way is to use non-ncgative slack variables as following:
min
F(x), s.t. hx(x) + 8k
0, 1,...,
X. x. 20 where $1,-.., Sm introduced dummy variables. Li ct al. 2021 presents some discussion how to convert <KKT solution to the above equality constrained into KKTT solution to the original inequality constrained optimization. However, such guarantee requires that boundness of the constraint functions.
7

---

Published in Transactions on Machine Learning Research (01/2026)
Algorithm 1 Algorithm for solving equation 2 under Selting 1
Initialization: choose Xo, 10, 7/2 and 17.
for t 0 to T 1 do
3: Sample _ C (l.....in}
4: for each k E B² do
5: Sample a mini-batch 22
Update n (1 r2 u22 (x 122 (3,x)) - hx 1 end for
8: Let 1+1 u2, k $ Bi 226
9: Compute G [ EnEBy (x,; (2, Gi = T8 Eces 0f(x(:{)
10: Update X1+1 Xt - (G (2))
11:
end for
5
Stochastic Algorithms
In this section, we consider stochastic algorithms for solving 2 for F(x) = Exff(x, ()], which has been considered in Ma et al. (2020); Huang & Lin (2023 ; Boob et al. 2023 Due to limit of space, we present extension and analysis of compositional objective F(x) " Ei= I (Eglgi(x, (x.((xxx)) ())) in the Appendix Without loss of generality, we assume the constrained functions are only accessed through stochastic samples. Below, we let h(x, B3) [8] hxe with mini-batch of samples B. We make the following assumptions regarding hg, and f.
Assumption 5.1. For any x, assume there exists (x(x, {), and (x, E), where & is random variable, such that (a) E[ (x) = h2 (x) and Elah, (x, E)] E ah, (b) (x(lbx(x,E) h,( s L |x yll: (c) Eg 6x11/x(x,5 - (x) S oh.
Assumption 5.2. For any assume there exists 0f(x, where Ç is random variable such that Ex0f(x,C) C) e (x) and [x]]0=((x) - 0f(x {)
The key to our algorithm design is to notice that the hinge-based exact penalty function Σx= (x)]+ is special case of non-smooth weakly-convex finite-sum coupled compositional objective as considered in Hu et al. (2024), where the inner functions are (x) and the outer function is the hinge function that is monotone and convex. Hence, we can directly utilize their technique for computing a stochastic gradient estimator of the penalty function.
The subgradient of the penalty function is given by m E (x)+ However, computing (x(x) and (h, is prohibited due to its stochastic nature or depending on many samples. To this end, need an estimator for (x(x) and Öh+(x), (hy can be simply estimated by its mini batch estimator. The challenge is to estimate (x(x) using mini-batch samples. The naive approach that estimates h+(x) by its mini-batch estimator does not yield a convergence guarantee for compositional optimization. To address this issue, we use the variance reduction technique MSVR for estimating constraint functions hx(x), Ak (Jiang et al. 2022). which maintains and updates an estimator ug,x for each constraint function 14. We present the key steps in Algorithm 1 In particular, at the t-th iteration, we construct a random mini-batch B² C (1...., m), then we update the estimators of hy (x;), & E B by Step 6 where 72 E (0, (0,1),2/= B.1(1-2] + - 72, and B, is muini-batch of samples for estimating hy (xt). Then the gradient of the penalty function and the objective function at x, can be estimated by G Gf in Step 10, where [u]_a'4 is the derivative of the hinge function at uh Then, we can update X by using SGD with G + G/2 as the stochastic gradient estimator.
m-15.11
Since the estimator U2,k produced by MSVR is used to approximate the true constraint value during opti- mization, it is useful to clarify how it behaves over itcrations. Our analysis of Lemma B.3 shows that as long as //2 0, /// /2 + 0, and I 1 oo, the error |uš hx (xx)] converges to zero. This guarantees that the solution converges to a KKT point asymptotically. For the asy-asympiooiic case with > 0, although dhe may fluctuate around zero near the feasibility boundary, such oscillations can be effectively controlled by choosing sufficiently small 7) and 72 This ensures that the hinge-based constraint hx(x)) S is reliably enforced. In our experiments, did not observe any instability in constraint. satisfaction.
8

---

Published in Transactions on Machine Learning Research (01/2026)
The convergence of the algorithm for finding an e-stationary solution oo(x) is given below. The proof of the theorem is presented in Appendix
Theorem 5.3. Suppose Assumptions 3.1 5.1 and 5.2 hold. Let 72 - = ( ), - 1 12,
3.m ) after
T 0 BB where 8 selected uniformly at random from {1, (T)...,T).
3 (Buu))))) iterations, the Algorithm I satisfies
S from some 0 0011ppo+p1100
Remark: While we state the convergence results for a given e, it is also possible to state the convergence for a given 7. In this case, we can let 7,72 depend on T, which can yield the same complexity result. Tn practice, these hyper- parameeessss are always tuned to achieve the best performance. For example, in the first experiment we choose the initial learning rate from (10-3, 10 10-4) and apply a standard decay schedule; in the second experiment we use the same magnitude choices as in Li al. (2024a). These settings are fully reported in the experimental section, and our results show that they work well in practice.
we demonstrate Algorithm 1 can find nearly eKKTT solu- tion to the original problem I in the following Corollary. The proof is provided at the end of Appendix
Combining the results from Theorem 5.3 and 4.2
C
Corollary 5.4. Suppose Assumptions
3. 1
5.
5.2 and equation
hold. Let Y/2 = -0(1BA
0 0(18.11Aa11 and a conslant B> > 0 after T O( 8
ileralions, the Algorithm can find nearly e-KTT solution x; where condition (i) in Definition 3.3 holds in expectation, conditions (ti)
p'm
B2
and (tii) in Definition 3.3 hold with probability 1 - (()) for the original problem [7]. And if (xx)) < +00,
the conditions (ii) and (Mi) hold in expectation. f is selected uniformly at random from {1,...,T).
Remark: Corollary 5.4 shows that Algorithm I can find a nearly c-KKT solution the original problem ①1
+ iterations, which matches the state-of-the-art complexity of double-loop algorithms (Mal et al. 2020 Boob et al.] 2023). It is better than the complexity of O(1/c") of the single-loop algorithm proposed in Huang & Lin (2023). It is noticed that Liu & Xu (0025 also achieve the same complexity of O()). While both works achieve comparable complexity guarantees, our contribution lies in different algorithmic design and problem setting: We directly operate on the hinge penalty instead of a smoothed surrogate. Specifically, our MSVR estimator is designed for estimating many sequences while only accessing 0(1) sequence for update. This makes it greatly suitable for us to handle many constraint functions. In contrast, the SPIDER estimator requires accessing all sequences at the same iteration, which is not efficient for handling many constraint functions.
with T
6 Applications in Machine Learning
6.1 AUC Maximization with ROC Fairness Constraints
We consider learning a model with ROC fairness constraints (Vogel et al. 2021). Suppose the data are divided into two demographic groups D,- {aa", b)) and D. [(a b"") f where denotes the input data and b E }1] denotes the class label. A ROC fairness is to ensure the ROC curves for classification of the two groups are the same. Since the ROC curve is constructed with all possible thresholds, we follow Vogel et. al. (2021) h by using a set of thresholds r = (....... Tm to define the ROC fairness. For each threshold т, we impose a constraint that the false positive rate (FPR) and true positive rate (TPR) of the two groups are close, formulated as the following:
np 16b = ()0(( (af) 7)
1
Du
h (w)
:=
I(b = (30(sw(a() - T) - K -K
+
np 1=1
i=1
ap
h (w)
1b -100 -)
1(61 -1)o(ss(((a)) (a)aaa))-a--)a))(a((()) 0,
up 1=1
The 1=1
where (-) denotes a parameterized model, 022) is the sigmoid function, and k > 0 is tolerance parameter. For the objective function, we use a pairwise AUC loss:
F(w) D+I|D_
-1
Σ
Σ
(s(,,x,)) s(w,
X;ED+ XjED-
9

---

Published in Transactions on Machine Learning Research (01/2026)
Hige,
Hinge, 6 B-
Concraae 10
0:44
0.4
-00
0233
2017
033
0000
Squareed tinge, 8-200
Squared Hige. 5- 920
Squared Hinge, S- 802
Squared Hige, 1000
0.2
0.4
4.00
-2a0
Epach
4pach
SparT
20009
Figure 1: Training curves of 15 constraint functions of different methods for fair learning on the Adult dataset. Top: hinge-based penalty method with different 8 Bottom: sunared-hinge--e based penalty method with different B. Each curve (c.g., legend train_tps ttr___tr_tth___t t_. denotes constraint function h (w) (resp. with 7 = 3); similarly, ferii__pr_th____ represents the constraint function hy- (w) with T = 3.
Adult
COMPAS
Chexpert
8.02
DC4
Conatrel Dantew
4.22
AUC Valae
9:22
0.21
821
1.50
4.66
823
545
Spoch
Specs
4.31
36
2,007
340
Figure 2: Training curves of objective and constraint violation of different methods under a parameter set sinting when they satisfy the constraints in the end. Dashed lines correspond to objective AUC values (y-axis on the right) and solid lines correspond to constraint violations (y-axis on the left).
where D denote the set of positive/negative examples regardless their groups, respectively.
Our proposed penalty method solves the following problem:
min F(w) 2|T E.er Bhh (w)]+ + 3|6, (w)]++
(9)
w
It is notable that the above problem does not directly satisfy the Assumption However, the Algorithm
with a minor change is still applicable by formulating [h+ [w)]+ fggh,, ( where f(() - [g] g(h)
[h| and (w)) + Ei Hbb =s)o(s((a)) - T). As result, f is monotonically non-decreasing and
convex, g is convex, and h, is smooth function, which fits another setting in Hu et al. (0224) The only change to Algorithm is to maintain an estimator of h+,1, 7 E T and handle [h, [w]+ similarly.
Setting. For experiments, we use three datasets, Adult and COMPAS used in Donini et al. 2018). CheX- pert [Irvin et al.) 2019), which contain male/femmn felee,, Caucasian Coucasian/noo--ee Wonn-Caucasian, and male/ female groups, re- spectively. We set r T= (-3, -2, -1, ... .3). For models, we use a simple neural nork with 2 hidden layers for Adult and COMPAS data and use NenseNet121 for CheXpert data (Yuan al. 2021 We implement Algorithm ! with setting 1/2 0.8, %/2 0.1, 0.005. We compare with the algorithm in Li et al. (2244a) which optimizes squared- hinge penalty function. For both algorithms, we tune the initial learning rate in f1c-3, 1c-4) and decay it at 50% and 75% epochs by factor of 10. We tuned B = {1,44 8, 10, 20, 40, 80, 100) for our hinge exact penalty method and 3 = {10, 40, 80, 100, 200, 400, 800, 1000} for squared hinge penally method. We also compare a double-loop method (ICPPAC) Boob et al. 2023 Algorithm 4) for Adult and COMPAS, where we tune their 1 in (0.1, 0.01), - in {1, 10, 100), μ in (1e-2, 1c-3, 1c-4), and fix 8, to 0.1. We do not report ICPPAC on the large-scale CheXpert data because it is not efficient due to back propapttong 15 individual constraint functions every iteration. We run each method for total 60 epoches with batch
10

---

Published in Transactions on Machine Learning Research (01/2026)
Sigasree 800
Spoch
Figure 3: Training curves of constraint values in zero-one loss of different methods for continual learning with non-forgetting constraints when targeting the foggy class. Top: hinge penalty method with different 3; Bottom: squared-hinge penalty method with different 3.
Target Foggy
Target Overcast
Terget Tunnel
0.00
Squared Hengen
singe
0.25
Tiaarre Hengen por
Hinge P
D20
Constrate Visatoo
0.20
Constraine 10R300
pog 6MCC
1009
0.10
12
60
-2.22
Ppoch
Figure 4: Comparison of training curves between the hinge penalty method and the squared-hinge penalty method when both methods satisfy the constraints in the end. Dashed lines correspond to target accuracy improvement over the base model (y-axis on the right) and solid lines correspond to constraint violation terms of zero-one loss (y-axis on the left).
size of 128. As optimization involves randomness, we run all the experiments with five different random seeds and then calculate average of the AUC scores and constraint values.
Result. We present the training curves of values of constraint functions in Fig. I on Adult dataset to illustrate which 3 value satisfies the constraints. For the hinge exact penalty method, when 3 20, all constraints are satisfied. In contrast, the squared hinge penalty method requires much larger 8 800 to satisfy the constraints at the end. We include more results on COMPAS and CheXpert in Appendix A We compare the training curves of objective AUC values and the constraint violation measured by the worst constraint function value at cach epoch of different methods in Fig. on different datascts. These results demonstrate that the hinge exact penalty method has a better performance than the squared hinge penalty method terms of the objective AUC value when both have a similar constraint satisfaction, and is competitive with if not better than ICPPAC method.
6.2 Continual learning with non-togggg constraints
Continual learning with non non- non-etrggtning constraints has been considered in (2024a) ) which is termed the model developmental safety. We consider the same problem of developing the CLIP model while satisfying developmental safety constraints:
t,)D Law (w, t. T; .I,), s.t. he Lv(w, Dx) [w D&) S 0, =1,
min F(w, , D) = Σ
11

---

Published in Transactions on Machine Learning Research (01/2026)
The Letr (w, TT )I)) , is two-way contrastive loss for each image-text pair (x,, t.)
Yuan et al. 2022
Lar 4i, ;;: -r log exp( (w, x.) E2 (1)/T)
21JET, exp( Fi (w. x;) (2
exp(B2 (,) Bi (w, x.)/T)
- log
Exjer,
P2 (2 Ea (w, (w,x:)/T)'
where E1 xw) and E2( denotes (normalized) encoded representation of image x and text t, respectively. T denotes the set of all texts to be contrasted with respect to (w.r.t) x, (including itself) and IJ denotes the set of all images to be contrasted w.r.t 4, (including itself). Here, the data D is target dataset. [ Dx) = (x..))D., & x,, V:), where & is a logistic loss for the k-th classification task. 2 to optimize the hinge penalty function.
We use our Algorithm
Setting. We follow the exactly same experiment setting as in Li et al 2024ap. We experiment on the large- scale diverse driving image dataset, namely BDD100K (Yu et al. 2020). This dataset involves classification of six weather conditions, i.e., clear, overcast, snowy, rainy, partly cloudy, foggy, and of six scene types, i.., highway, residential area, city street, parking lot, gas station, tunnel. We consider three objectives of contrastive loss for finetuning a pretrained CLIP model to target at improving classification of foggy, tunnel and overcast, respectively. For cach task, we use other weather or scene types to formulate the constraints, ensuring the new model does not lose the performance on these other classes. The data of the objective for the target class are sampled from the training set of BDD100K and the external LAION400M dataset (Schuhmann et al. 2021 and the data of constrained tasks are sample from BDD100K, where the statistics are given in Li et al. (2024a).
For all methods, we fix the learning rate 1e with cosine scheduler, using weight decay of 0.1. We run each method for a total of 60 epochs with a batch size of 256 and 400 iterations per epoch. We tune 8 in {0.01, 0.1, 5, 10. 20} for our method and in {80, 100, 200, 400, 800} for squared hinge penalty method and set [Bc| = m, | = 10,71 71 = 72 = 0.8, 71 = 7/2 = 0.1, T = 0.05.
Results. We present the training curves of the constraint functions as measured by zero-one loss in Fig. 3 for different methods with different 3 values on targeting foggy class. We can see that when B 10, our hinge penalty method will satisly all constraints. In contrast, the squared hinge penalty method needs a much larger B = 800 to satisfy all constraints. The constraint curves when targeting overcast and tunnel are
presented in Figs. 5 G in Appendix A
Fig. compares the training curves of the target accuracy improvement between our hinge penalty method and squared-hings penalty method when both satisfy the constraints. According to the Fig. A our hinge penally method converges faster in terms of the objective measure when they exhibit similar constraint satisfaction in the end.
7 Conclusion and Discussion
In this paper, we have studied non-convex constrained optimization with a weakly-convex objective and weakly convex constraint functions, which are all stochastic. We developed a hinge-based exact penalty method and its theory to guarantee finding a nearly e-KT solution. By leveraging stochastic optimiza- tion tochniques for non-smooth veakly-convex finite-sum coupled compositional optimization problems, we developed algorithms for solving the penalty function with different structures of the objective functions. Our experiments on fair learning with ROC fairness constraints and continual learning with non-forgetting constraints demonstrate the effectiveness of our algorithms compared. One limitation of this work is that the rate is still worse than non-convex smooth equality constrained optimization. Different from our hingo-basod exact penalty method, there are some relevant works on smoothed proximal and primal dual methods with constant penalty parameters Pu et al., 2024 Huang et al.) 2025), which involve any dual variables or pri- mal-dual updates and make valuable contributions in convex or linearly constrained settings. It indoed an interesting future direction to explore whether primal-dual techniques can be extended to fully non-convex constrained optimization in the stochastic setting, potentially achieving even better convergence guarantees.
12

---

Published in Transactions on Machine Learning Research (01/2026)
Acknowledgments
M. Yang, G. Li, Q. Hu and T. Yang were partially supported by the National Science Foundation Ca- reer Award 2246753, the National Science Foundation Award 2246757 and 2306572. Q Lin was partially supported by National Science Foundation Award 2147253. The authors thank the action editor and the anonymous reviewers for their insightful suggestions and constructive feedback.
References
Ahmet Alacaoglu and Stephen J Wright. Complexity of single loop algorithms for nonlinear programming with stochastic objective and constraints. In International Conference on Artificial Intelligence and Statis- tics, pp. 4627-4635. PMLRR 2024.
Heinz H Bauschke, Patrick L Combettes, Heinz H Bauschke, and Patrick L Combettes. Correction to: conver analysis and monotone operator theory in Hilbert spaces. Springer, 2017.
Albert S Berahas, Frank E Curtis, Daniel Robinson, and Baoyu Zhou. Sequential quadratic optimization for nonlinear equality constrained stochastic optimization. SIAM Journal on Optimization, 31()):1352-1379, 2021.
Albert S Berahas, Miaolan Xic, and Baoyu Zhou. A sequential quadratic programming mothod with high- probability complexity bounds for nonlinear qquality-constraing stochastic optimization. SIAM Journal on Optimization, 35(1):240-22) 269, 2025.
Ernesto G. Birgin and Jos Mario Martnez. Practical Augmented Lagrangian Methods for Constrained Opti- mization. Society for Industrial and Applied Mathematics, USA, 2014. ISBN 161 161197335X.
Digvijay Boob, Qi Deng, and Guanghui Lan. Stochastic first-order methods for convex and nonconvex functional constrained optimization. Mathematical Programming, 197(1):215-279, 2023.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004, ISBN 0521833787.
Frank E Curtis, Daniel P Robinson, and Baoyu Zhou, Sequential quadratic optimization for stochastic opti- mization with deterministic nonlinear inequality and equality constraints. SIAM Journal on Optimization, 34(4):3502-300 3622, 2024.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. STAM Journal on Optimization, 29(1):007-233 2-297-29,,00 2019.
Damek Davis and Benjamin Grimmer. Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. STAM Journal on Optimization, 29(3): 1930, 2019.
Lijun Ding and Stephen J Wright. On squared-variable formulations. ar preprint arXiv:2310.0173 2023.
Michele Donini, Luca Onelo, Shai Ben-David, John S Shawe-Taylor, and Massimiliano Pontil. Empirical risk minimization under fairness constraints. Advances in neural information processing systems, 31, 2018.
James P Evans, Floyd J Gould, and Jon W Tolle. Exact penalty functions in nonlinear programming. Mathematical programmingg 4(1):72 97, 1973.
Yuchen Fang, Sen Na, Michael W Mahoney, and Mladen Kolar. Fully stochastic trust-region sequential quadratic programming for equality-consttrined optimization problems. SIAM Journal on Optimization, 34(2):2007 2037, 2024.
Ellen Fukuda and Masao Fukushima. A note the squared slack variables technique for nonlinear optimiza- tion. Journal of the Operalions Research Sociely of Japan, 60:262-277 07 2017. doi: 00.15807/jonsj.60.22
Quanqi Hu, Dixian Zhu, and Tianbao Yang. Non-smooth weakly-convex finite-sum coupled compositional optimization. Advances in Neural Information Processing Systems, 36, 2024.
13

---

Published in Transactions on Machine Learning Research (01/2026)
Ruichuan Huang, Jiawei Zhang, and Ahmet Alacaoglu. Stochastic smoothed primal-dual algorithms for nonconvex optimization with linear inequality constraints. aiv preprint arXi::2504.07607, 2025.
Yankun Huang and Qihang Lin. Oracle complexity of single-loop switching subgradient methods for non- smooth weakly convex functional constrained optimization. Advances in Neural Information Processing Systems, 36:61327-613400 2023.
Jeremy Irvin, Pranav Rajpurkar, Michael Ko, Yifan Yu, Silviana Ciurea-lleus, Chris Chute, Henrik Mark- lund, Behzad Haghgoo, Robyn Ball, Katie Shpanskaya, et al. Chexpert: large chest radiograph dataset with uncertainty labels and expert comparison. In Proceedings of the AAAT conference on artificial intel- ligence, volume 33, pp. 590 597, 2019.
Zhichao Jia and Benjamin Grimmer. First-order methods for nonsmooth nonconvex functional constrained optimization with or without slater points. arXiv preprinl ar arXiv:2212.0092 2022.
Wei Jiang, Gang Li, Yibo Wang, Lijun Zhang, and Tianbao Yang. Multi-block-single-ppee probe variance reduced estimator for coupled compositional optimization. Advances in Neural Information Processing Systems, 55:32499-32511 2022.
Guy Kornowski and Ohad Shamir. Oracle complexity in nonsmooth nonconvex optimization. Journal of Machine Learning Research, 23(314):1 44, 2022. URL http://jmlr, http:://jml...rg/ppatpppo p .html
Gang Li, Wendi Yu, Yao Yao, Wei Tong, Yingbin Liang, Qihang Lin, and Tianbao Yang. Model de- velopmental safety: A safety-centric method and applications in vision-language models, 2024a. URL
petps://arxiin http:////aaiiivoo/aa////////// wwtg/abs//4111
03955
Zichong Li, Pin-Yu Chen, Sijia Liu, Songtao Lu, and Yangyang Xu. Rate-improved inexact augmented lagrangian method for constrained nonconvex optimization, 2021. URL http:://aaxxvv..g/aa///////s
01284
Zichong Li, Pin-Yu Chen, Sijia Liu, Songtao Lu, and Yangyang Xu. Stochastic incxact augmented la- grangian method for nonconvex expectation constrained optimization. Compulational Optimization and Applications, 8711:1177-147, 2024b.
Qihang Lin, Runchao Ma, and Tianbao Yang. Level-set methods for finite-sum constrained convex opti- mization. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3112-3121. PMLR, 10-15 Jul 2018. URL httph: htttps://proceedingg
mlr. wtt.ppeee//////nn....ttttt.
Qihang Lin, Runchao Ma, and Yangyang Xu. Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization. Computational Optimization and Applications, 82(1): 175 224, 2022.
Wei Liu and Yangyang Xu. A single-loop spider-type stochastic subgradient method for expectation- constrained nonconvex nonsmooth optimization, 2025. URL httpps//aaxx...rrr///////...01 19214
Runchao Ma, Qihang Lin, and Tianbao Yang. Quadratically regularizod subgradicnt methods for weakly convex optimization with weakly convex constraints. In International Conference on Machine Learning, PMLR, 2020.
pp.
Sen Na, Mihai Anitescu, and Mladen Kolar. An adaptive stochastic sequential quadratic programming with differentiable exact augmented lagrangians. Mathematical Programming, (1):7))221 1911,1991111 2023.
A. Nedić and A. Ozdaglar. Subgradient methods for saddle-point problems. J. Optim. Theory Appl. 142 (1):205-228, July 2009. ISSN 0022-3239. doi: 10.1007/810957-009-9822 URL https://dol.org/1t 1007/s10957-009-9322
Yu. Nesterov. Smooth minimization of non-smooth functions. Mathematical Progummmig 177 2005. doi: 10.100//110107:000--55555 httppp///aal.agg//....o////00000
14

---

Published in Transactions on Machine Learning Research (01/2026)
Wenqiang Pu, Kaizhao Sun, and Jiawei Zhang. Smoothed proximal lagrangian method for nonlinear con- strained programs. arviv preprinl or arxi:2408. 15047, 2024.
Alexander Robey, Luiz Chamon, George Pappas, Hamed Hassani, and Alejandro Ribeiro. Adversarial robustness with semi-infinite constrained learning. Advances in Neural Information Processing Systems, 1166198-6215, 2021.
Mehmeet Fatih Sahin, Ahmet Alacaoglu, Fabian Latorre, Volkan Cevher, et An inexact augmented lagrangian framework for nonconvex optimization with nonlinear constraints. Advances in Neural Infor- malion Processing Systems, 32, 2019.
Christoph Schuhmann, Richard Vencu, Romain Beaumont, Robert Kaczmarczyk, Clayton Mullis, Aarush Katta, Theo Coombes, Jenia Jitsev, and Aran Komatsuzaki. Laion-400m: Open dataset of clip-filtered 400 million image-text pairs. arXiv preprint Xrxx:2111.0211,, 2021.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889 1897. PMLR, 2015.
Kaizhao Sun and Xu Andy Sun. Dual descent augmented Lagrangian method and altornating direction method of multipliers. SIAM Journal on Oplimizalion, 34(2):1679 1707, 2024.
Robin Vogel, Aurélien Bellet, and Stephan Clémençon. Learning fair scoring functions: Bipartite ranking under roc-based fairness constraints. In International conference on artificial intelligence and statistics, pp. 784-792. PMIR, 2021.
Bokun Wang and Tianbao Yang. Finite-sum coupled compositional stochastic optimization: Theory and applications. arXiv preprint orXiv:2202.12331 12399, 2022.
Fisher Yu, Haofeng Chen, Xin Wang, Wenqi Xian, Yingying Chen, Fangchen Liu, Vashisht Madhavan, and Trevor Darrell. Bdd100k: A diverse driving dataset for heterogeneous multitask learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 2636 2645, 2020.
Hao Yu, Michael Necly, and Xiaohan Wei. Online convex optimization with stochastic constraints. Advances in Neural Information Processing Systems, 30, 2017.
Zhuoning Yuan, Yan Yan, Milan Sonka, and Tianbao Yang. Large-scale robust deep AUC maximization: A new surrogate loss and empirical studies medical image classification. Tn 2021 TEFF/CV International Conference Computer Vision, ICCV 2021, Montreal, QC, Canada, October 10-17, 2021, pp. 3020-3029. IEEE, 2021. doi: 00010///CCV48892222220.000 00303
URL https:://di..org//////
Zhuoning Yuan, Yuexin Wu, Zi-Hao Qiu, Xianzhi Du, Lijun Zhang, Denny Zhou, and Tianbao Yang. Prov- able stochastic optimization for global contrastive learning: Small batch does not harm performance. In International Conference on Machine Learning, pp. 25760 25782. PMLR, 2022.
Willard Zangwill. Non-linear programming via penalty functions. Management science, 13(5):344-25) 358,
1967.
15

---

Published in Transactions on Machine Learning Research (01/2026)
A More Experiment Results
The experiments of AUC Maximization with ROC Fairness Constraints in our paper is run on a GPU server with 10 A30 24G GPUs. Each seed in this experiment takes about 4 hours to complete. The experiment of continual learning with non-forgetting constraints is run on two A100 40GB GPUs. Each seed in this setting takes approximately 12 hours to finish. These runtimes are comparable across all methods since they share identical model architectures and computational setups, including the learning-rate schedule, weight decay, batch sizes, and the selections of [Bel and [Ba]. We tune the penalty coefficient B, which allows to study how different methods reduce constraint violations and how their performances in the objective value change when the constraints are satisfied. This consistent setup provides a fair and controlled comparison of the optimization behavior of all methods.
We give other experiment results in this Appendix. First, we compute the minimum singular value 5 of the Jacobian matrix of violating constraint functions in our experiments at different solutions to verify the conditions in Lemma 4.4 as shown in the Table 2 For the first. experiment, we compute based the Adult dataset at the initial model, final model, and two randomly selected intermediate epochs. For our second experiment, we compute when Target Foggy at both the initial and final models. All results demonstrate that the minimum singular value a of (x) remains positive, which is consistent. with the theoretical guarantee stated in Lemma 4.4
Experiment 1 (Adult) Minimum Singular Values a of (x
Initial Model
Epoch 30 Epoch 45 Final Model
0.000648
0.000112
0.000102
0.000101
Experiment (Target foggy)
Initial Model Final Model
Minimum Singular Values of (x)
24.1038
16.3397
Table 2: Minimum singular values a of the Jacobian matrix (x(x) at different solution.
For targeting overcast we consider other weather conditions except for foggy as protected tasks due to that there is a lack of foggy data in BDD100k for defining significant constraint. For the same reason, we consider other scence types except gas station as protected tasks for targeting tunnel. We use the mostly same experiment setting with the case target foggy only difference when tuning 3. We tune 3 = (0.01, (.101,0.1,11 0,1, 10, 20} for hinge-based penalty method and S {0.1, 1, 20, 50, 100, 200) for squared hinge penalty method when target overcast. When target tunnel, tune 3 {0.01, 0.1, 1, 10, 20) for both hinge-based penalty method for squared hinge penalty method. The training curves of target overcast and tunnel show in Fig. and Fig. 6 The training curves on dataset COMPAS and Chexpert show in Fig. 7 and Fig. for experiment ROC Fairness Constraints.
B Technique Lemmas
To prove our main theorem, we need the following lemmas.
The following lemma follows from standard result (Davis & Drusvyatskiy 2019 Lemma B.1. Given weakly conver funclion & and 0 < (p) then the envelope dh is smooth with gradient given by Voo(x)= = 8- 0-1(x- prozos(x)), where
prozos (x) == arg
o(y)) 20 lly -x112 J. 2 0p In addition, dist(O, do(x)) S (|V
arg min
(10)
The smoothness constant of 0e is 011
Lemma B.2. [Lemma [Jiang et al. |022/] Consider update 226. Under Assumptions
3.1
5. 1 and
D.1
by selling 7 = Bi0 + (1 11--m1 m), for m < 2: the funclion value variance E(+1 = Σ ||
ga (x++1) x
can be bounded
13 m E n
8nL2
Xt+1 - x+l1 2 BlO
(11)
[
n B
16

---

Published in Transactions on Machine Learning Research (01/2026)
Epech
Squareed 300
Mar
Figure 5: Training curves of constraint values in zero-one loss of different methods for continual learning with non-forgetting constraints when targeting the overcast class. Top: hinge penalty method with different 3; Bottom: squared-hinge penalty method with different B.
Hiage
Hage: F 10
Dry sire
Spoch
Spach
Espured tirge 0.03
Scceree
3012
Powch
Ryarts
Figure 6: Training curves of constraint values in zero-one loss of different methods for continual learning with non-forgetting constraints when targeting the tunnel class. Top: hinge penalty method with different 3; Bottom: squared-hinge penalty method with different B.
Lemma B.3.
[Lemma 1 (Jiong et al., 2022)) Consider the update Line in Algorithm 4 Under As- [8.1 + (1 72), for 72 I 1 the function vatue variance 2,
sumplions 3.1
and 5. j
by selling 7/2 [1
pt+1
1
FTT hy (x(+11)11 can bounded as -=
||
|B m
8mL3 E[|xx+11 [B.]
x2 2T71B, o
E ET S (1
ET]+
(12)
m B2,
From the analysis of Lemma 4.5 in Hu et al. 2024), the following two inequalities hold true based on Lemma
B.2 and Lemma B.3 For simplicity, we use constant 2 max(2L? 2,3 L3 20 + 2L3 + 2,5 13)
1B
1 (x(o)) + 4mLanM
1/2 1/2 on |B 1/2
(xx) u1 S (1
(13)
2m
1/2 1Bcl
and
E
1g (xx)
wf 5 (1
18l )z
1
1/ gx(x)
4nI. Mn
+
27 1/2 |B
og
(14)
2n
|B\ 1/2
17

---

Published in Transactions on Machine Learning Research (01/2026)
Hinge, d
Concraat 1P
2:44
0291
033
0054
Squared --10
Squarrd
Squareed Hinge, BD
Squared Hinge,
0220
024
-200
Spoch
Epach
200ch
Figure 7: Training curves of 15 constraint functions of different methods for fair learning the COMPAS dataset. Top: hinge-based penalty method with different B; Bottom: squared-hinge-basee based penalty method with different B.
Fingu
Ming 8 10
290
0:00
Cm
Cinibra F8
Combain
1.00
2013
Tonch
Tomce
Squered tinge, p=:
Scuacedd Ilrgge 100
Souared Elagge 2 200
Coralaatt Volle
Combrart
Conetrar4
C.00
6.13
Figure 8: Training curves of 15 constraint functions of different methods for fair learning on the CheXpert dataset. Top: hinge-based penalty method with different 8; Bottom: squared-hinge-based penalty method with different B.
4.1 Notice that have assumed F(-) to be po-weakly convex in Assumption 3.1 By the definition of weak convexity, it suffices to show [hx(x)]+ to be pi-weakly convex for all h = 1...
Proof of Lemma
Let [*)]] denote any element in ([hx(z))+ Given any h E (1....,m} and x. x', following from the convexity [:]+, we have
[ha(x)]= [ha((r)) (0)x((2))++((()) 1(x'))
(1))(2))) ((0h) (x'), ) - -x') )
P || x' (12 2
(15)
2 (Ohu(a' )01h (2)) x')
01 2
x x' 2/11?
where (a) follows from the fact [>)(2 2 for all x' and the P1-weak convexity of h+(:), and (b) follows from the fact [h (x')]4 S 1.
18

---

Published in Transactions on Machine Learning Research (01/2026)
To show the L-Lipschitz continuity of Φ(-), utilize the LF and Lą-Lipschitz continuity of F(.) and hyg (-) to obtain that for any x, x' we have
m [1ox (2)))++
[0()) - -(z') S [F(x) P(x')l
[[<(,))]+
m
8
$ LF -=
11 (z) (2))l
m
(16)
8
LF |2
x'll
La ||
xell
m
k=
$ (LF
3L4)
r/||-
Proof of Lemma 4-3 Our goal is to prove that there exists constant > 0 for any x such that h(x) > 0 (violating the constraint), we have dist(0, Oh(x)) 2 8.
By conditions (i) and (ii) and the fact that h(z) O, we have
dist(0, 0h(x))²
c << h(x) min h(y) -
2/z
This means ((ist(0,0h(x))) 2 /2cu =:
Proof of Lemma 4.4 Let & (m),,,,,Em), where & defined
if hx(x)) > 0, (x(x 0,
EN
[0. 1]
E {(hx(x)]'4
if hv(x) 0,
For any and any sub-Jacobian G(x) E (x)),, let (x) denote its k-th row (so 9x(x) E (x)).
m
m
Σ
[x)((x) = [G c
(x))+
km
Let ; fx: max (x) > 0}. For any x E V we have
1 Σ alha (x)]+ 2 1 G(x) E 2 Amin (G(x)) ||E|| 2 Amin (G(x)).
1
dist 0, m k=1
By the assumption that dist((0, Amin (OH(x))
0, Vx such that max; (x) 0, have
Amia (G(x))
2 o VG(x) (H(x).
Therefore, for all x V,
( 1 Σ 8/ha(x0)+++ dist
0,
m
C Proof of Theorem 5.3
Proof. The objective function
3 Σ
min ((x) = (x 5)
[x)
(17)
F(x)
R
(
19

---

Published in Transactions on Machine Learning Research (01/2026)
For simplicity, denote x, == proxg:p(xx). Consider change in the Moreau Envelope
Ey[min ((x) P | x1+111
E, 1 (x(+x(x+))))
(x,) P
[|x x++1 11
2
(x,) + P
xx - (xt n + (
2
(xxx)) 9 || x111 ple, (n) x,, G + G2) + 172 f.M²
2
PM
+ pn) (x,)
x,, R. (G1)) + pn - xx, x,, B, + 1y
(18)
2
where the second inequality uses the bound of E, + G3 which follows from the Lipchitz continuity and bounded variance, denoted by M² 2 20 + 21' + 2 Here,
8
E. [A E (x()),
G. E
Σ
Ohe (x))(u2
m
Next we give the bound of (R, x,, Eg]l] and (x, - xx, E. (G5)).
To this end, first we give the bound of
(x, xt, [GH)). Since F po-weakly convex, we have
F(x)) - F(x:) 2 OF(x)) (x: - xx)
Po
2 ||x - Xx 112
2
Then it follows
0F(x)) (xi xz) S F(x:) - F F(x:)
Po
| x 111
(19)
2
Next we bound (x: - Xx, [.GG) For given k (L...., m], we get
[xx(x - k 2 (u², (xx - u2,n))
2 |ub (xx(xx)) - - + ahk T (x. x.) P1 2 ju2_ - - =5,n)) + [u, eit.el',,me (xx))x) (x: x;)
1x: - xx(13]
2
PI ||x 10-xx,1 x,11?
2
where the first inequality uses the convexity of function [+,,, the second inequality uses the fact [u] 2 0 and the weak convexity of (.), and the last inequality uses the fact that S [už, S 1. Then follows
B
jub M4s, (1xx Txx= xx)
xx)
8
[ - -ub,el+ [ug, (hx(xx)) - x(,,)) + Pl
||x: x
113
(20)
772
2
Adding above two estimation equation 19 and equation 20 back to equation 18 we have
xx, Er (G+) + (m) X1, Ee,,.[ (G& + 17² PM²
E, [ (11pp((((11)) S (1/p(x)) + pn(xx
2
7, 11)p(x)) +
2MM
+ p F(xx) - F(x:)= + Pu ||xe xx||²]
2
2
3
+ PM
[[xx( -ub,ul+ - -Iug,o (1x) - wb2, +
|x x x3
2
k=1
(x)) 172 pMy
+ pm F(X.) F(x:) + PO ||x, xx|13]
2
2
3 + pm
[Mnn(xx)]++ (x+))+ + [xx(x:)] - lub -Iug.el' (Pra(Xx) - =b/ + PI
||x xx11 112
2
(21)
20

---

Published in Transactions on Machine Learning Research (01/2026)
By Lemma 4.1 x|2
the function @ is C-weakly convex. We have (p-C), ())stronn convexity of x x(xx + 2l
1 ((x,) (xx+)
(xx,) - |x: - xxl1²) - (2(x)) + -21lxx= x: <212)) -
- 2 -x,11 11?
2
C 2
p) , xel1?.
Then we get
1
C
F(X) Fxx)) + 8 (xx)( [xx )]+) (xx,) +(xx) 1 [x -x,12.
(22)
778
Plugging inequality equation
22 to equation 21 get
E, ( 1/ (x++1)
I 1 (x1) + 11
PMM
pr)
Pb
3 f1
+
C
d) 1|&, xel1?
2
2
2
3
[xa(xx)]+ - [u2 - [ug (hx - ub2x))
+ pr)
1=1
Setting 28 + +
C
2 we have
2
E. (x(01/((x++1)
I (x)) +1, ",2Phr² pM1
0² |2 x,112 + PM
Thu (x,)l+ - 112 - -[ug, (hx( - -u2,n) u5iin)
"
S {11/ + 1,2 -,2p/r/² DM²
33
[
4
+ pm
[x]]xx - 1u6, [ub (x:) - vb/2m
2
m
Since 0 < [u2, S 1, we get
E2 1h (x++1) - (x,) + +
PM²
7
V (xx,))
2pm m k=1
3
Σ [,x())))
(23)
2
Taking the full expectation on both sides of equation
23 and applying the inequality of equation 13 we have
E $ (x+((()
2M
- E 1 (x())
+ 17
"
[[| V (x))1(
2
2
1Bol212
m
+ 4mLMnM
27/2 2/2 oh
+ 2 (1
1
- hx(x))ll
+
2m k=1
1B.122 1/2
1/2
12,
Taking summation from -= 0 1o T -
yields
E (((11/(XTT)] S (x)) + 27 TM2
DM²
17
T-1
Elll
1 (x,
2
2m 1 m
1122 (xo)ll T 8
4722 1/2 0n
2p133
+ T
1/ m
BBok
1/2
|B2 1/2
where we use the fact that _0- ming (xx) and dividing both sides by T, we obtain
11 < for all μ [0, Lower bounding the left-hand-side by
1
E|| //)))11
T
2 1 (
C m23p
mp3nM
8p"/ 1/2
<
min xxx) npM²
+ +C
n/T
T 72 B.
Bahh
1/2
|2, 1/2
21

---

Published in Transactions on Machine Learning Research (01/2026)
where C = max 8
Σ k= |122, h (xx 32L 16 }. As weset set M² > 203 and en +32 C
2, with 7/2 = ( 3+
18
), 17 = 0 | v 1/2,", and T = O
B8 B2, 17238) ) we have
m
mm
1 T-1
Blll V (x) = 0
T
1=U
By Jensen's inequality, can get / < O(e), where 8 is selected uniformly at random from {I....,T)
Now, we will prove that x; a nearly c-KTT solution, where (i) holds expectation, (ii) and (iii)
Definition 3.3 hold in high probability, to the original problem
Proof. Proof of Corollary
5.4 Let X = prox1/p4 (x:)- By optimality of Xg, we have
8 m
0 E (F(x)
ohg (xx) (x; xx)pp
k=l
Since (x+ S O(e), then we have |B||x x
Elll
/ (x)) S c/p. Then we have
E dist (F, +
Σ th (xx))
[8 x;) c.
Since 0h (x;) = (x;))((x) (see (Bauschke et al.
2017
Corollary 16.72)), where
if hy (x;; > 0,
&
[0 if hu (X²) 0, E E00ha(x;)++
if h4 (x;) 0,
there exists X E 95x
2 0, Vk such that EElist (0, (x;)) + Em= dx;))(())) S e. Thus, we prove condition
(i) in Definition under equation
3.3
Next, let us prove condition (ii) holds with probability - O()). Since 3v E OF(x),
8 we have
(,v+ m
3 En
ah (xt) 2 dist (o. m Em ah aht ||/ 2 38 LF 2 0.
dist
(24)
Therefore,
dist v +
ah (x:))
m
k=1
8
dist v
Oh (xx)) max hy (x₂) > c Prob(max (x;))) > c)
m
k=1
(ist v + m
thg (x))) max (x,) s Prob(max hx(x)) I E)
k=1
Prob(max (xxx)) (335 - Lr)
As result,
Prob(max (x,) > E) 5 38 -F 0(e)
(25)
Thus, it holds with probability 1- Oce) that max; hy (x;) S e. When max hy (x;) S e, we have \xhx((x)) 2
A max; by (x;) S (c) as X A5x, It then follows from equation 25 that Prob (Apha 2 O()) S {(().
m
This proves that (x;) I ((e) with probability -(e). If 1 (x:) < too for any l and X3, this high
probability result can be replaced by Elmax, hy (x:) S O(e) and ( s O(c).
22

---

Published in Transactions on Machine Learning Research (01/2026)
Algorithm 2 Algorithm for solving equation 2 under Setting 11 Initialization: choose Xo, B, 711 72 and 17.
for oort- 0 to T- do
3: Sample 8 C (1,....n) Bi c [1 m.
4: for each i E B do
5: Sample a mini-batch Bi,
Update uf, by W1, - n)uf, (x; (1i 1; B(,)), end for
8: Let 1+1 = - B
Compute G1 18T Lies (i,
10:
for each k E Bº do
11:
Sample a mini-batch 222
12:
Update 22z (1 72 u2) (2h 1é (x:: B3,,)) - ha 1x,-1;12,,0
13:
end for
14:
1+1 Let 2,6
2 k $ B:
15:
Compute G 18:1 EneBy (h Ba Mu,,,, GĀ 1854
Eseor 0f(x):)).
16:
Update X1+1 Xt (G G22)
17:
end for
D
Analysis of Setting II
Now, let us consider the second setting where F(x) = 1 Eis (xx the same form of the penalty function, which is a coupled compositional function. Let gi gx(x) (x, ()). We make the following assumption regarding f..
()]). Indeed, this objective is of
Assumption D.1. Assume fx is deterministic and T.y-Lipchitz contimuous. For any x,y, Exllg: C) - 9, () < L - y/12, Blla,(x, <) (x)) I og and either the following conditions hold: (i) is monotonically non-decreasing and peawly convex, gx(x) is Po-weakly convex; (ii),i Lyy-smooth, g((x) is smooth.
To tackle this objective, we also need to maintain and update estimators for inner functions (x(x.. At the 1-th iteration, we randomly sample an outer mini-batch B' E (1,...,n) n), and draw inner mini-baich samples Bi, for each i B to construct unbiased estimations g, (x,; Bi.). The variance-reduced estimator of gi (x,)
denoted by wi,s updated by:
1 = (1 - -1) + (x, + 7 (x;; - gi (x1-1;B1,,)
(26)
1-1 + 1 - n. where [B] = |B%. Then, we approximate the gradient of F(x,) by: where 71 E (0, 1), [81(1->1)
G = |B4
Σ (x;;
(x:; B1,05
(27)
iEB
Then we update x similarly as before by X x, () Gb)- Due to the limit of space, we present full steps in Algorithm] 2
The convergence of Algorithm 2 under condition (i) of Assumption
D.1 is stated in Theorem D.2 and that
under condition (ii) of Assumption D.1 is stated in Theorem
D.3
Theorem D.2. Suppose
Assumption
3.1
5_1
D.1
with condition
(i) hold.
Let m
7/2 -O(min { [1,, 1B2.l 1 ()) "
O
13
B. min min | 1/2 (
After T
n² Omaxf 1/2 1/2, [8i.1] max{ a 8m } (²)
itterations, the Algorithm satisfies E||l ( S
[sp [B.]
from some ((1(ppo + pi,)),, where is selected uniformly at random from (1..... T}
Remark:
Combining the above result and that Theorem
4.2 Algorithm needs = 0 ) to achieve
nearly cKKT solution to the original problem equation the single-loop algorithm considered in Li et al. (024a)
It is better than the complexity of O(1ee) of
23

---

Published in Transactions on Machine Learning Research (01/2026)
Theorem D.3. Suppose Assumption
3.1
5.1 and D. with condition
(8) hold.
Let
Ominn
4. 1
2)),
7
(min
[B||8
2
After
T
Omaxx mg
iterations, the Algorithm satisfies [XIV+)((;)II from some X = ((1((po + P13)), where selected uniformly at random from {L....,T}
nga
B det })
n
$
Proof of Theorem D.
The objective function is minx 4xx, D) = 1
(x)) + 3 the (x)++
F(x)
(x)
For simplicity, denote x, == proxo:p(xi). Consider change in the Moreau envelope
E, (1 (1(01/((x+11) E, [min (xx - | x [13]
s (x,, + P
R x
2
Ex)((x;) + p
| - -(x- - (G + G
2
< ((x,)) + p ||x, - xx112 + pE, (n) x,, Gf + G2) + 172 pPM?
2
2
x,, E [G]) + pn X1, Ex +7² PM2
+ pm/3x (
(28)
where the second inequality uses the bound of [||] + |] which follows from the Lipchitz continuity, denoted by M² 2 2, + 2
[GG E - Σ (og
(x,)", E.
B m
Σ ahu (1,
Next we give the estimation of (x: x,, E, (Gi) and (x, - x,, E, (G]). For given E {l....,n). we have
(()1()))) (((,,))) 2 01((1),)) (gx(8)) (2x(x)) w1,1) PS (19:(xx)) w1,
2
2 of((4),)) (g((x)) (h,)) - (x)) - (x(x))1 - Ps ()(1)((x()) vi,+112
2 0f((H),) (xx(xx) - -i, + +x, T - x1) 0 - xx11²] م - xel12 2 - Ps p)(lg((x)) - u1.
2 0 (g((x)) ((((x.)))))))))))))))))))))))))) - u(,)) + as T) (x,) [xx - xx) - -Pgls + py [i)) - x,112 (x1))x(xx) - uf.
2
where the first inequality holds by py-weakly convex of fúr the second inequality holds by the monotonically non-docreasing of fi and the third incquality holds by Pg- Po-wcakly convexity of gi, the last incquality holds by and 0 < afi( < Ly. Then it follows
Og.(x)))))))) x.) S ((l)(()))) - Se(ut,)) - ai:(()))) - -(
+( (OgLI
xel1 2112 (x)) u/..11]] (29)
Next we bound (x, - xx,, Ex(G)) For given & E (l.....m}. from equation
20
we have
Jub,el'' ahu (x+) (xe- xx) < 3
[x+]]+ - [2b -1 (a.ll///hhh (hr - ubja) + PI ||x; 112
8
2
(30)
24

---

Published in Transactions on Machine Learning Research (01/2026)
Combining inequality equation 2% equation 29
and equation 30 yields
E, 1 (1)(1((((11))) S 1 11/p(x)) + pn(x4 - xx, B.Gi) + pm(X x,, E, + 112 1,2Pp?
2
< (x)pp(x)) + 112 =PM?
2
+ pM
Ji(o: (x:)) Si(u),)) (sx((x) - w(,)) + Pgots
+ 1,
x.11² + x111++ (x)lox(x)) -vi x1,
2
+
[nu (x,)++ - -1ug,0+ -
- xl2x) +
P1
|x2 - xxl13]
178
2
(xx( + 11
PM²
pm
POLs
+ pg p3(1))13x. - x1|1?
pm)
3
P1
& - x
2
n 1=1
2
m
k=1
(x())(X))) fx())(x))) + fil9i(x))) - f((u1,) - a.((u),))) (g((xx) uut + pxlla((x)) - -1
pm) 71
pr)
3
[xx)(=)]++ - [xx(x))]+ + Il (x+)]+ [ub - (hu())) wh/h)
(31)
From Lemma 4.1
the function + C-weakly convex. We have (ā-C) -0s-srong convexity of + +(x)
$ |x x 2
C -)] x.112.
2(x.) -x(x)) S $1 2
We gel.
m (xx(( [xx(x))++) (xx.) 4xx:) S 1
C
Σ
- xel2. (32)
2
Plugging inequalities equation 32 to equation
31
we get
E, (x)x())))1)
+ 1/2 (x))
PM12
+ pm
PgLes
+ 11 + + +
C - -))1 ||x, xrl1
2
1
f(())(x))) f((u),)) 0f (g.(xx)) wi + +)(ll((xx1) - .1.
+ pm
71
[Nu (x:))+ -lug [ub.tl4 (xx) wbwm)
+
25

---

Published in Transactions on Machine Learning Research (01/2026)
Set P 2 + L + 8 + - = 2: we have
Fx 1/1 (x+1)]
1 (1) + t11 pp/ - 11 1² |x x111
1
[x(()(Xx)) - si((),)) afi(u) (gi(xx) - w
-u( + psll91(x)) - -1.113
PM
[A (xx)]+ - 112 (ha -5hx)
+
(1,( 1/ pMM 17 2 [V1111(x))11
1
[x())(x))) - f((( af((uf,)) (g:(xx) w(,)) + prll9)(x:) -uf
pM
[xx]]+ - 112, - [v2, (ha -v2, -62,x)]
+ pM
Using the Lipschitz continuity of and the fact that 0 S [ub 1, we get
E [x(01//(x(-1) S 1)/ + 17 PM2
/ 112 + 2pL nm
(x,) - ui,ill
1=1
3
+ P
Σ 1g:
11, + 2p1
11 (xx) u2
(33)
k=1
Taking the full expectation on both sides of equation 33 and adding the result of Lemin and equation
B.2 equation
14
13
we have
E (x(+1]]
PM2 +
$ E 1/ (x,))
"
2
2
+ 2pm
1B/21
1
|u g. (x5)))
AnL,LyM
2L 1/2
og
2n
71
1B
1/2 m/
1/2
im1
+ pn [pr(1
|B|71
a
|| g (xx))1
8n²11 L
2y103ps
n
n
11222
B1,s
+ 2pn8 (1
1Bcl2
1
m
1u22 hx(x))ll
4mLunM
272 1/2 |22 1/2
ah
2m
m
1Bh2 1/2
Taking summation from 0 T 1 yields
E E(D1/
PM
" T
< (x))
+ 2
V (x))
2
2
2n 1
8n SnI.gL.pMM
AT, 1/2
0g"
2pp
Ls
(xxx))l
ll T
+
|
Y1 n
//////2 1/2
|B2,11/2
1
8n² 17² L.PpM²
+ 2r10'ps
pn
Inf (xxx))11 +T
B
1B
2m
8m AmLnmbh
47 1/2 0h
2
1/ ha (xo))l +
+ T
BBl
1/2
13 1/2
1=
26

---

Published in Transactions on Machine Learning Research (01/2026)
where we use the fact that Ei=o (1 n4) - # Lower bounding the left-hand-side by miny o(xx) and dividing both sides by T, we obtain
B|ll V /
T
Cp Ty
8m [Bel
( (x1/((1)
min x
[xx)] + npM²
max
1/1"
[
+ C
TM
max
3m
122
+ 2/2 p max
8
+
7
71/2
[
B
y
|B [B,,|1/22
1/2
|B
where we set 7/1 = 72- y and
= (8L -
1
Ju - (x00))l. - Σ Σ
n
|ug gi (x
1,,
12,88
m
u2, hx(xx))
11
7
1=1
32وم ps ps. 16L ووg 40 1opps,161. 16h,, 16
Paks As we set M 2 2 + 2,32 13 and
+ Ps L5 + 3 + 2 21
with
O ( [|B
1
2
3
= Ommin
have n 3m m B2
| |Bal
1/2
gz
and T Ommax B 172
B2
173
[
max
{
n B
B
T
Blll V 2 (x, xx, | OE.)).
T
By Jensen's inequality, we can get |||| V // (x) S 0(()), where f is selected uniformly random from T....,T).
Now, we give the proof of Theorem D.3
Proof of Theorem D.3. From equation 28 also denote x, proxa/p(X.) and consider change in the Moreau envelope, we have
By 1/001/(X S (1/p(x,) + pn(X, -,, (,,,,[(G]) + po(:x - xx, B,(G + 2MM² where the gradient can be bounded by M, where M 2 2, 2,38T.7 and
(34)
2
3
E, G E 72
Σ f (g((x.)
E. E
Σ Sh (xx (x,),,u
m
Next give the bound of (xe xx, E, G and (x, - xx, (.)))
It's easy to verify that F is p
where LeF = I,g + Ly Then we have
F(xi) S F(X) + (VF(X)) - xx) + LFF
1|x x111
2
LFF
= + VF(x)),x - -xi)+
||3 - xel1
2
vx(a((x)) (V((x) 1 n
V(((u)))) (
Xt xi)
n
(T -x)).
27

---

Published in Transactions on Machine Learning Research (01/2026)
Then, we have
xx)1 = | π
11
E, E,
(xx) x, xi)
$ F(x)) F(xi) + Lvr
1
|x
x11 1| + LFF 13 1212 + L Lg
(x:(xx) -/.e11114. xell
i=1
S F(x)) - F(x:) + (2L + 2 - xol12 +1/1+22/111 Lg
119:(x)) - 21i,11?.
From the equation 20 we have
B E, & x1)] = 8
u (xx( ( - X1)
k=1
B
[1x - [u2, - (02,)'((hxxx) - -12,a) + P1
|| -x,ll²
xxl1²]
2
1=1
Adding above two estimation to equation
34
we have
E, 11/11/(x0+11 S (1/a(x)) + pn(xi - x,, E, + pn(x: xx, + +1, ?
2
s (1/p(x)) + +1² ??M?2
2
+ pn F(x,) - F(xx) + (2L + 2L - xel12 2I Lg Σ (1::(x;) - -uf =1/=11]]
B
[1x(xx)]++ -hh (x: + (xx))+ - [ub, - [ub,l's (hx (xx) -(,,)) + PI |x - x1(2] 1331-x1'-
+ pn) m
(35)
2
Since smoothness of F implies the weakly convexity of F, we still have (p - -s)-st convexity of x + ((x) + - -ox--x11 x112
C - S 512 - p)][x - x.112.
(xx,)= - (xx,)
Adding above inoquality to equation
35 we have
E, (((01/((X++1)] S (x:) + 11"
PM2
+
p1(22 + 2L 3 + 2
C -)][x - xxl12
2
1
n2
B m
+ +2 L 11
1gx(x))
- + jmn
[hx(x+)]+=
fub,0+ (Ma(xe)) - wb/,0
m
1=1
If we set 2L + L + P +
C
2
2.
we have
DM²
Eg ( (x(((()] (1/)(x)) 172
|x, x112
1
3 [hx(xx)]+ -[bb,u+ (ha(s)) - 2b.wm)
+ +2L Ly pT)
(xx)(x)) - -uful12 112 + pm
(he(xx))
n
22
1 Σ
3
< (1/)(x1) + 172
/111/(()))11111111110 + 2L pp
(1),(x.) - uirll + 2pm
(xi) - u6/
2
2
==1
k
where we the fact 0 ~ [ub,'' 1.
28

---

Published in Transactions on Machine Learning Research (01/2026)
Adding the result of Lemma B.2 and inequality equation 13
we get
pM
([ - 1 x + 17=
Bill V /
18
1
L L
27 9
4g
+ 2pm L7 1 1
|u 9x(xx)11 +
1B1272
11
(1 2
|Bcl2
1
||22 (x0))1
4m 4
212 1/2
Th
2m
m
|B 1/2
1 1/2
k=1
Taking summation from t= 0 to T - yields
[[01/0(XT])
< ([01/ + +1 2 PM²
|8|l V /
t=
8n2 1. L. M
+ 2pm
L1 Lu
n
|ui 9b (xo))l T
-T
|3/71
1312711
1B
1m1
2m
SmLaMM
472
1/2
+ 2
11 (x(x))ll +
+ T
|Ba |Bal12
1/2
12 1/2
k=1
where we use the fact that E (1 1) S.
Lower bounding the lefl-hand-side by minx (x) and dividing both sides by T, we oblain
T [|[| V (
Σ
2
+ Cp
3m
< T/
(1/p(())
min ((x)] + 11MM
maxt f
Ty
[
|Ba
M2
1/-
70
+ C
+
+ |B2
+
1/2
BB2
|B1,1|
where we use 71 722 = 7 and
1
1
C = max
Lg
||u 9: 9x (xo))
1/ hx(xx))
2m1
k=1
32L 32L,, 8L Lyog 16
As we set 2 22 L3 and 2L 2L L, + then with y O(min ng
{
B2 ct [ 22),
g
3
77 O Omin
18, 1/2222
[15 |1.. 1/22
pm
}) and T (max
m,
n
B
}), have
(x)])
T
By Jensen's incquality, we can get V (x: < 0O(c), where f is selected uniformly at random from (1....,?) TT).
29


Reviews:
[{"review_id": "oU1HSQkrmF", "reviewer": "Reviewer_oUVS", "summary": "", "questions": "", "limitations": "", "rating": null, "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": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a single-loop penalty-based stochastic algorithm for optimization problem where both the objective and the inequality constraints are weakly-convex and potentially non-smooth. The idea is to use a non-smooth, hinge-based penalty function, which permits the use of a constant penalty parameter,  and achieve a complexity of $\\mathcal{O}(\\epsilon^{-6})$ for finding a near $\\epsilon$-KKT solution.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The complexity analysis is standand. I checked all the proofs in the appendix, and do not see any major issues.", "audience_yn": "Yes", "audience_explanation": "For optimization researchers,  the main contribution is a single-loop stochastic algorithm that achieves an $\\mathcal{O}(\\epsilon^{-6})$ complexity for non-smooth, weakly-convex constrained problems. The novelty lies in using a hinge penalty and only requires a constant parameter rather than one that must go to infinity, which is an interesting result.\n\nThe analysis under non-smooth settings is also useful for applied researchers. It directly addresses the structure of many modern ML problems.", "requested_changes": "1. The estimation of the stochastic gradient is not clear now, please make it clearer. For example, the $\\mathcal{B}_c^t$ should be a set, but in the Algorithm1, there is \"$\\mathcal{B}_c^t \\in${1,...,m} \". \n\n2. The end of the proof of Thm 5.3 seems to use Eq. (3) as an assumption when proving condition (ii)\n\n3.  Why \"since the objective and the constraint functions are non-smooth, finding an ϵ-KKT solution is not\ntractable\", could you involve some insights and discussion? And if the objective and constraint functions are smooth, is there some way to convert a near-stationary point to a stationary point？\n\n4. Considering that the main contribution of this work is the use of a penalty method with a constant penalty parameter, there are some works that use primal-dual type methods, which also permit a constant penalty parameter. I believe it is worth discussing these works, for example:\n\n[1]Wenqiang Pu, Kaizhao Sun, and Jiawei Zhang. Smoothed proximal lagrangian method for nonlinear constrained programs, 2024\tarXiv:2408.15047\n\n[2]Ruichuan Huang, Jiawei Zhang, and Ahmet Alacaoglu. Stochastic smoothed primal-dual algorithms for nonconvex optimization with linear inequality constraints. In Forty-second International Conference on Machine Learning, 2025.\n\nMinor thing:\n\n5. In the comparison with the work by Liu & Xu (2025), there is 'they consider only one constraint function'. However, I checked that in Liu & Xu (2025), they use a vector-valued function.", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NlvZcRIkOL", "reviewer": "Reviewer_Mi55", "summary": "", "questions": "", "limitations": "", "rating": null, "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": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a single-loop stochastic algorithm for solving non-convex constrained optimization problems where both the objective and constraint functions are weakly convex and possibly non-smooth. The authors base their approach on an exact penalty formulation using a hinge penalty rather than the more common squared-hinge penalty. They argue that this non-smooth penalty preserves weak convexity, allows a constant penalty parameter instead of a large one growing with $1/\\epsilon$, leads to a theoretical complexity of $\\mathcal{O}(\\epsilon^{-6})$ for obtaining a $\\epsilon$-KKT point, which is a competitive good rate matching the best double-loop algorithms, and extends naturally to finite-sum coupled compositional objectives. The complexity improvement over existing literatures mainly by using a hinge penalty that keeps $\\beta$ constant, avoiding the blow-up in weak convexity parameters; and using variance-reduced stochastic gradients in a single-loop structure. Two applications are reported: Fair learning with ROC-based fairness constraints, and continual learning with non-forgetting constraints. Empirical results compare the hinge-based penalty against squared-hinge and double-loop baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Most of the results with proofs are correct and well supported by evidence. I have the following comments.\n\n1. The central theorem (Theorem 4.2) relies on a strong regularity condition (Eq. 3), which effectively assumes a uniform lower bound on the gradients of the constraints across all infeasible points. I believe that relaxing Eq. 3 to impose only an upper bound $c$ is a more reasonable assumption. As the authors mention, under this relaxation the algorithm can be initialized within the feasible region and proceed with carefully chosen step sizes so that all intermediate iterates remain within $V_c$, as adopted in (Huang & Lin, 2023). Could the authors clarify how this relaxation affects the final convergence rate, and whether it is one of the reasons their method achieves better complexity than (Huang & Lin, 2023)?\n\n2. Although Algorithm 1's penalty gradient $G_2^t$ is, in principle, an unbiased estimator of the sampled constraints' gradient (as it is computed only over the active mini-batch $B_c^t$), the proposed estimation strategy may introduce considerable instability. The main concern is that the non-smooth hinge derivative $[u_{2,k}^t]'$ is evaluated using a noisy stochastic estimate $u_{2,k}^t$ rather than the true constraint value $h_k(x_t)$. Near the feasibility boundary, where $h_k(x_t) \\approx 0$, small fluctuations in $u_{2,k}^t$ can cause oscillations around zero, making $[u_{2,k}^t]'$ switch between 0 and 1. This behavior can result in oscillatory and inconsistent constraint enforcement, thereby degrading both convergence stability and feasibility control. The issue may be amplified when the number of constraints $m$ is large, since most stored estimators $u_{2,k}$ become stale at any given iteration. Could you comment on this? \n\n3. The algorithm’s step size $\\eta$, inner rate $\\gamma_2$, and iteration number $T$ all depend explicitly on the unknown target accuracy $\\epsilon$. This makes the complexity guarantee non-constructive and the method difficult to implement in practice, as the required parameters cannot be chosen without knowing $\\epsilon$ in advance.", "audience_yn": "Yes", "audience_explanation": "The topic of stochastic constrained optimization with weakly convex objectives is timely and relevant to the optimization and machine learning theory community, which forms part of TMLR’s readership. The paper builds on a well-studied framework single-loop algorithms. While the theoretical development represents an incremental step beyond existing results and the assumptions could be further relaxed for broader applicability, the work nonetheless contributes to refining our understanding of this line of methods. The experimental validation, though limited in scope, provides some empirical insight into the algorithm’s behavior. Overall, the paper will likely be of interest to readers already following advances in stochastic nonconvex optimization.", "requested_changes": "1. The paper needs to explicitly specify the regularity assumptions for each constraint function $h_k$, clarifying when differentiability is required and when only subgradients are available. In several parts of the analysis, the notation $\\nabla h_k$ and $\\nabla H(x)$ is used informally, even though the stated assumptions (e.g., weak convexity and potential non-smoothness) suggest that subdifferentials would be more appropriate. The authors may replace occurrences of $\\nabla h_k$ and $\\nabla H(x)$ with the corresponding subdifferential forms $\\partial h_k(x)$ and $\\partial H(x)$, respectively, and to clearly state the conditions under which these subdifferentials coincide with classical gradients.\n\n2. There is a disconnect between the deterministic notion of a nearly $\\epsilon$-KKT solution defined in Definition 3.3 and the stochastic guarantees actually established in Appendix D. The definition requires deterministic satisfaction of all KKT-like conditions, whereas the algorithmic analysis only proves them in expectation or with high probability.\n\n3. The fairness and continual-learning experiments are presented only through training curves without runtime comparisons. Important implementation details (batch sizes, $\\gamma$ parameters, and $\\beta$ selection) are omitted or inconsistent between text and pseudocode.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "90G1o451nr", "reviewer": "Reviewer_2i7i", "summary": "", "questions": "", "limitations": "", "rating": null, "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": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers an important constrained optimization problem where both the objective and constraint functions are weakly convex.\n\nStrengths:\nThe proposed approach employs a hinge-based penalty, which permits the use of a constant penalty parameter, enabling us to achieve a state-of-the-art complexity for finding an approximate KKT solution.\n\n Weaknesses:\n1. The authors may have overstated the novelty and achievement of their theoretical complexity bounds. The paper claims to achieve an SOTA complexity for finding an approximate KKT solution. However, the complexity of $\\mathcal{O}(1/\\epsilon^6)$ achieved by the proposed algorithm has also been established in prior works for similar problem settings. For example, A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization. CoRR abs/2501.19214 (2025) .\n\n2. The result presented in Theorem 4.2 (or the main convergence theorem) should rigorously state that the output $\\mathbf{x}$ is a nearly $\\epsilon$-KKT solution in expectation, since the objective function may be stochastic.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The conclusions of Theorem 4.2 and Theorem 5.3 support the claims made in the paper.", "audience_yn": "No", "audience_explanation": "This paper is very similar to the paper,  A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization. CoRR abs/2501.19214 (2025) .", "requested_changes": "The submission requires several critical revisions concerning its theoretical claims and rigor. First, the comparison in the related works section is inaccurate: the authors must correct their description of Liu and Xu (2025), which also considers multiple constraint functions via a vector-valued function. Relatedly, the paper must include Liu and Xu (2025) in the complexity comparison (e.g., in Table 1), as its $\\mathcal{O}(1/\\epsilon^6)$ rate matches the claimed state-of-the-art result. Furthermore, for theoretical correctness, all definitions and theorem conclusions (especially Theorem 4.2 and Theorem 5.3) concerning the approximate KKT solution must be qualified by \"in expectation,\" given the stochastic setting. Finally, the authors must resolve the inconsistency between the conclusions of Theorem 4.3 and Theorem 5.3 (one requiring an $\\epsilon$-stationary solution and the other achieving only a nearly $\\epsilon$-stationary solution), which currently renders the proof chain for the final $\\epsilon$-KKT solution non-rigorous. \n\nA minor suggestion is to motivate the choice of the MSVR technique over SPIDER and to formalize the notation in Assumption 5.2.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)