Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints
Authors: Ruichuan Huang
Jiawei Zhang
Ahmet Alacaoglu
Venue: ICML 2025 spotlightposter (2025)
Keywords: primal-dual algorithms
stochastic optimization
single-loop algorithms
linear inequality constraints
Primary area: optimization->nonconvex
TL;DR: We develop optimal single-loop primal-dual algorithms for stochastic nonconvex optimization with linear inequality constraints.

Abstract: We propose smoothed primal-dual algorithms for solving stochastic nonconvex optimization problems with linear \emph{inequality} constraints. Our algorithms are single-loop and only require a single (or two) samples of stochastic gradients at each iteration. A defining feature of our algorithm is that it is based on an inexact gradient descent framework for the Moreau envelope, where the gradient of the Moreau envelope is estimated using one step of a stochastic primal-dual (linearized) augmented Lagrangian algorithm. To handle inequality constraints and stochasticity, we combine the recently established global error bounds in constrained optimization with a Moreau envelope-based analysis of stochastic proximal algorithms. We establish the optimal (in their respective cases) $O(\varepsilon^{-4})$ and $O(\varepsilon^{-3})$ sample complexity guarantees for our algorithms and provide extensions to stochastic linear constraints. Unlike existing methods, iterations of our algorithms are free of subproblems, large batch sizes or increasing penalty parameters in their iterations and they use dual variable updates to ensure feasibility.

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints
Ruichuan Huang' Jiawei Zhang 23 Ahmet Alacaoglu 1
Abstract
In particular, when we have the problem
We propose smoothed primal-dual algorithms for solving stochastic nonconvex optimization prob- lems with linear inequality constraints. Our algo- rithms are single-loop and only require single (or two) samples of stochastic gradients at each itera- tion. A defining feature of our algorithm that it is based on an inexact gradient descent framework for the Moreau envelope, where the gradient of the Moreau envelope is estimated using one step of a stochastic primal-dual (linearized) augmented Lagrangian algorithm. To handle inequality con- straints and stochasticity, we combine the recently established global error bounds constrained op- timization with Moreau envelope-based analysis of stochastic proximal algorithms. We establish the optimal (in their respective cases) O(=**) and ( sample complexity guarantees for our al- gorithms and provide extensions to stochastic lin- car constraints. Unlike existing methods, itera- tions of our algorithms are free of subproblems, large batch sizes or increasing penalty parame- ters in their iterations and they use dual variable updates to ensure fcasibility.
min f(x) subject Ax S b,
(2)
XER
we introduce slack variable t = Ax so that Ax-t b and our optimization variable becomes (²). Then, we can equivalently write the problem in the template (1) by using the constraint t I 0, where the set X = { x E R", t S 0} easy to project. As such, we focus on (1) and our results directly apply to solving (2) by using this standard slack variable reformulation.
The assumption of X being -o-pjjectt is without loss of generality. Indeed, when X is not easy to project, we can add a slack variable for x S h similar to the above para- graph, to have a linear equality constrained problem with projectable constraints (cf. (1)). We refer to (Li et al., 2021, Remark 6), for the classical conversion of an e-stationarity point of the problem with the slack variable the original inequality constrained problem. Throughout, we assume that we have access to an unbiased oracle F F(x) such that
[[) f((), and [E| F(x) V f(x)) 5. (3)
A common setting is when f(x) = Eg (x, {)] where E is an unknown distribution that we can draw i.i.d. samples from. In this case, is common to set F(x) f {) where E Vf {)] Vf(x). This will be our main focus.
1. Introduction
We focus on the problem template
Inclusion of the set X in (1) increases the modeling power of (1) significantly, while causing difficulties in the analysis. Many problems fit this template, including constrained and distributed optimization, nonnegative matrix factorization, sparse subspace estimation and collaborative learning, see for example' (Zhang et al., 2022: Hong. 2016). Moreover, reformulations of nonconvex problems are also common by using linear inequality constraints (Zhang al., 2022).
min f(x) subject to Ax = b,
(1)
xEX
where f: Ra + R smooth, the set X RR is poly- hedral, and easy project. In particular, let X be given as X {x: Hx < h) for some matrix // and vector h. Taking H = I, for example, gives this template the ability to model linear inequality constraints.
Algorithm development for (1) and related templates with global complexity guarantees, have been active in the last couple of years (Alacaoglu & Wright, 2024: Zhang & Luo, 2020; Zhang et al., 2020; Lu al., 2024; Li et al., 2021; Lin et al., 2022: Yan & Xu, 2022; Li al., 2024; Boob
Coollast authors Uniivessity of British Columbia Uniiversity of -isconsin-Maddionn 'MIT. Correspondence Jiawei Zhang <jzhang2924@wiis wdis. Ahmet Alacaoglu <ala- caoglu@ math.ubc.ca>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Detaill of some applications are given in Sec. 6 of ex- tended version: https://aree www.oorg/////aa.eeeeeese 07607

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
et al., 2023; Hong, 2016), mainly due the new applica- tions of functionally constrained nonconvex optimization problems in the context of neural network training (Katz- Samuels et al., 2022; Dener et al., 2020). In these applica- tions with problems involving nonconvex functional con- straints, stochastic augmented Lagrangian methods (ALM) have found widespread use, whereas their behavior for even linearly constrained nonconvex optimization of the form (1) remain poorly understood. Our focus is improve our derstanding of stochastic ALM in the context of nonconvex
more precisely the quadratic penalty (QP)) has the form of
Penp(x) = f(x) + - 11 Ax - -bl?.
It is common for algorithms based on the penalty function to require p - oo for convergence (Bertsekas, 2014, Sec. 2.2.5). One major disadvantage of this strategy is that p get- ting larger makes the subproblem of minimizing the penalty function more and more ill-conditioned (ef. (4)).
An influential idea was the introduction of the augmented Lagrangian (AL) function which combined the idea of the Lagrangian and penalty formulations (Hestenes, 1969; Pow- ell, 1969). In particular, the AL function is defined as
optimization, by focusing on the fundamental template (1).
Compared to the setting of convex f. where the global com- plexity analysis is mature for ALM and its stochastic version (Yan & Xu, 2022), nonconvexity of f poses significant diffi- culties in the analysis of ALM. Many works in the literature focus on penalty based algorithms (which will be formally introduced later in this section) that do not perform dual updates (or perform negligible dual updates that we clarify later) (Lu et al., 2024; Li et al., 2021; Lin et al., 2022), rather than primal-dum algorithms such as ALM. However, in prac- tice, dual updates are known to be essential for accelerating convergence. Penalty methods are known to be unstable since increasing penalty parameter causes Lipschitz constant of the subproblems to increase and can lead to numerical issues. These differences in behavior between penalty and augmented Lagrangian methods are well-known, see, for example, the classical books (Bertsekas, 2014, See. 2.2.5) (Nocedal & Wright 1999, Sec. 17.5).
Lp(x,y) = f(x) + (Ax - b. +
2 -1LAx - bll
Augmented Lagrangian methods in the classical literature were favoured because they did not require p to grow ar- bitrarily large. In fact, many instances of ALM converge to the optimal solution with fixed p since the incorporation of the dual variable updates aids in satisfying feasibility (Bertsekas, 2014, Prop. 2.4, Prop. 2.6).
Primal vs primal-dual algorithms. The algorithms based on the penalty function are generally referred as penalty algorithms and are easier to analyze in different settings since they are primal-only algorithms, meaning that they only perform updates on primal variable x where approx- imate feasibility is ensured by - co. In particular, a classical penalty method iterates for k = 1,2,... as
For problem (1) with access to full gradients of f and the full matrix A, optimal complexity with primal-dual methods are obtained in the work of Zhang & Luo (2022). When one has access to stochastic gradients of ff and the matrix A, a recent work by Alacaoglu & Wright (2024) showed optimal complexity guarantees under expected smoothness (see As- sumption 5.2), for the special case of (1) when X = R". However, this latter restriction significantly reduces the gen- erality of the template. For example, modeling standard quadratic programming requires X to be half-space, which was not supported in the analysis of Alacaoglu & Wright (2024). Our goal is to go beyond these results by handling both the case when X * R" as well as the case when we do not have access to the matrix A but only to an unbiased estimate of A, by keeping optimal complexity guarantees. A more detailed comparison of complexity guarantees will be made in Section 6 and summary is provided in Table 1.
Xk+1 arg min f(x) + Pk || bl1 XEX
2
(4)
Select PR+1 > Pl.
The algorithms based on the AL function are generally more difficult to analyze due to the additional dynamics coming from the dual updates which are critical to ensure that the approximate feasibility is attained with constant p. An ALM iteration proceeds for k = 2. by updating
xk+1 22 arg min f(x) + (yk. Ax b) b)++ f blb
XEX
Yk+1 yk + (Axx+1 b).
For penalty methods and ALM, different strategies exist to generate X++1 that approximately minimize the penalty or augmented Lagrangian functions by either iterating multiple steps of gradient descent (GD), known as inexact algorithms, or applying one step of GD, known linearized algorithms (Ouyang et al., 2015).
Lagrangian, penalty and augmented Lagrangian. The standard approach to tackle (1) is to design algorithms oper- ating on the Lagrangian, augmented Lagrangian or penalty functions. In particular, the Lagrangian function is given as
In view of the earlier discussion, when f is nonconvex, most of the literature focuses on either analyzing penalty methods, or analyzing ALM with negligible dual updates and increasing penalty parameters p. due to the inherent
y(x.y)= = fxx) + (Ax- b,y),
with the dual variables y, whereas the penalty function (or
2

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
difficulty in analyzing the dual variable and its effect in convergence. In particular, as also highlighted in (Alacaoglu & Wright, 2024), many of the recent analysis of ALM is of the form of perturbed penalty analysis, meaning that the feasibility is driven by increasing penalty parameters, and the dual updates are designed so that they do not deteriorate the estimates too much. Because of this, the dual step sizes are selected to be small to ensure boundedness of the dual variable (or controlling the growth of the dual variable). We refer to such updates as negligible dual updates since the analyses do not harness the benefit of such updates in ensuring feasibility. Feasibility is driven by large penalty parameters. Some representative examples are (Lu et al., 2024), (Li al., 2021), (Lin et al., 2022), (Li et al., 2024).
in Section 6. A summary is given in Table 1.
1.2. Preliminaries
We denote the indicator function of a convex closed set X as [x(z) 0 if x E X and Ix [x(x) = xo if x & X. The notation O for convex, closed function denotes the subdifferential set and 01x (x) is the normal cone of X at by definition. For matrix A, || denotes its operator norm.
Given closed and convex X, projection onto X is given as projx (x) = arg min vex || - vl1?.
Similarly, we define the proximal operator of f as
proxy(x) arg min [(v) + 2 f1ll -
This is the case even in the deterministic setting and the only method that we are aware that can handle true ALM with fixed penalty parameters and non-negligible dual updates are due to (Zhang & Luo, 2022) that uses a linearized proximal AL function with a dynamic adjustment on the proximal center, which will be clarified in Section 2 since it will form the basis of our algorithmic development.
We say that f is L-smooth when its gradient is I--Lipschitz:
fVxx) f(y)) S L/|x - -yll.
We say that f is p-weakly convex when / - 1122 is convex. An L-smooth function is automatically L-weakly convex. Moreau envelope of the weakly convex f is defined as
1.1. Contributions
(x(x) = min s(v) + 2X v - =/13
v
In this paper, we propose a stochastic smoothed linearized ALM for solving (1) that only uses single sample of stochastic gradient at every iteration. This algorithm also works with constant penalty parameter and incorporates non-negligible dual updates for feasibility where the dual step sizes have the same order as the primal step sizes. We show that this method has its iteration complexity and sam- ple complexity guarantees in the order of O(= Such a sample complexity result is optimal even in the uncon- strained nonconvex case under our assumptions (see As- sumption 1.1) (Arjevani al., 2023). In contrast, the prior results with optimal complexity required large penalty pa- rameters, no dual updates and further assumptions (Lu et al., 2024). We then prove that this complexity can be improved to ())-3) with variance reduction when an additional ex- pected smoothness assumption is made (see Assumption 5.2). Under this stronger assumption, this is the optimal complexity even without constraints (Arjevani et al., 2023).
which can be interpreted envelope has many useful properties such as being smooth when f is nonsmooth and weakly convex, when À is se- lected accordingly. Moreover, stationary points of f and the Moreau envelope coincide (Drusvyatskiy & Paquette, 2019, Lemma 4.3). The gradient of the Moreau envelope can be computed as
notion of smoothing. Moreau
x-1 - (x)).
Stationary points. A succinet way of characterizing a stationary point of (1) is the following: x* is a stationary point if there exists y" such that the following hold:
0 [ + ATy y"
+x"x and 0 = Ax" b.
One may, for example, refer to (Rockafellar, 2000). Accord- ingly, we say that (x,y) is e-stationary if
||Ax bll S E and
(5)
|| < e where v E V + A
+ xxx(x)
We consider extensions of this framework when we have linear constraints that hold in expectation, that is, when the constraints are given as [Açx - bę] 0, with the same complexity guarantees. To our knowledge, this is the first algorithm achieving the optimal O(E-A) benchmark sam- ple complexity for nonconvex optimization with stochastic constraints using one sample per iteration, going beyond the best-known (5) complexity that is achieved for a more general problem that does not capture the structure of linear constraints (Li et al., 2024; Alacaoglu& & Wright, 2024).
which is a common notion used in related works, for exam- ple (Zhang & Luo, 2022).
We also use the following related notion of near-stationarity, as used in (Davis & Drusvyatskiy, 2019). We say that x is e-near stationary if it satisfies
[V)( S,
(6)
where (x(x is the Moreau envelope of the objective function f(x) + [x) + [[v (x) in (1), see also (7). We refer to (Davis & Drusvyatskiy, 2019) for the precise notion of near stationarity.
A more detailed comparison with the related works is given
3

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Reference
Constraint
Oracle
Complexity
Loops
Method
(Alacaoglu & Wright, 2024)
Ax = b
Eq. (3) and
Ō(e-9)
ALM
Asmp. 5.2
(Alacaoglu & Wright, 2024)
E[c(x, {)] = 0, and x Xt
Eq. (3) and
5(=-5)
Penalty
Asmp. 5.2
c(x) = 0,
Eq. (3) and
(Lu et al., 2024)
0(e-9)
Penalty
and X Xt
Asmp. 5.2
E|c(x, {)] = O,
Eq. (3) and
(Li al., 2024)
((
2
Penalty*
and X
Asmp. 5.2
Ax b,
This work
Eq. (3)
O(e
ALM
and X is a polyhedral
[<(A(()x b(c) 0,
This work
Eq. (3)
O(e
ALM
and E X is polyhedral
Ax b, and x E X is a polyhedral
Eq. (3) and
This work
O
ALM
Asmp. 5.2
Table I. Comparison of methods. "This method is referred to as penalty method because the penalty parameter is taken to infinity to ensure feasibility and dual updates do not contribute in achieving feasibility. 'The set assumed to have an efficient projection.
1.3. Assumptions
takes average of z and x,, resulting in the terminology smoothed that we use for the algorithm.
We next state the assumptions that will be used throughout. These assumptions are standard and to our knowledge, the weakest, in the literature for both deterministic and stochas- tic nonconvex problems with linear constraints (Zhang & Luo, 2022; Alacaoglu & Wright, 2024). A more detailed comparison of assumptions will be made in Section 6.
Interpretation 2: Inexact GD on the Moreau envelope. Algorithm 1 can also be interpreted as an inexact gradient descent step on the Moreau envelope of the function in (1), In particular, this Moreau envelope is given as
min xx {s(x) + + "Ixx= 201
Assumption 1.1. For the problem (1), the following holds:
V (z,)
(7)
1. The function f is -mmooth and lower bounded over the feasible set: f(x)= 2 -00 for any x E X and Ax b.
By observing that minimizing the Moreau envelope helps on obtaining mear-stationary point in view of (6) (cf. (Davis & Drusvyatskiy, 2019)), inexact gradient update on this function requires the computation of
2. The set X admits efficient projection and is polyhe- dral. That is, it has the form X {x: Hx < h} for some H, h.
{((x) + - 2e 1=]
arg min xeX.Ax=b
3. We have access to stochastic gradients satisfying (3).
which is a nontrivial optimization subproblem. However, it is easier than (1) because the regularization provides us a strongly convex objective in the subproblem (given that À is larger than Ly). As a result, we can approximate the solution of this problem by applying one iteration of ALM since this problem is a strongly convex optimization problem over linear constraints. We show that just one step of stochastic ALM is sufficient every iteration by using stochastic gradient computed with a single sample and one dual update, followed by the update of the proximal center 2,.
2. Algorithm
We introduce Algorithm in this section. To gain a deeper understanding of the algorithm, we will go over two differ- ent ways of interpreting it.
Interpretation 1: Linearized proximal ALM. Algorithm incorporates a single-step SGD approximation of the prox- imal AL function. This strategy is also known as the lin- carized proximal ALM. In particular, the first step of the algorithm approximates the proximal AL function", that is,
On the surface, this algorithm strongly resembles that of Zhang & Luo (2022), from which we draw many ideas. However, in addition using stochastic gradients, there is another subtle change, on the update of 24+1- Unlike (Zhang & Luo, 2022), we update 2e+1 by using x, to be
X1+1 R arg min V(-)) + 1 1| -x,1?
xEX
by a single step of projected SGD, followed by a dual vari- able update and updating the proximal center 2,, which
'eet that Hu al. (2024) used similar idea in different context.
Nooe that this is also classical function (Rockafellar, 1976).
4

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
able continue the analysis with the bounded variance assumption G (ef. Algorithm 1) instead of boundedness assumption on G, since the latter would require bounded domains. Thanks to this small change in this section, we handle the case with unbounded primal and dual domains.
3.2. Analysis Tools
In our analysis, Moreau envelope of two functions is crit- ical. The first was the Moreau envelope of the composite objective in (I), defined in (7). We next define the Moreau envelope on the proximal AL which is the main function to
analyze projected SGD, cf. (Davis & Drusvyatskiy, 2019)
3. Convergence Analysis
(1/A(x,3,2) -min uEX Lp(u, y) + llu z|2
L 2
In this section, we first provide the main complexity results, then introduce the main analysis tools and proof sketch.
+ 2
x
llu - x (10)
2
3.1. Main Theorem
Another important quantity that has a significant role in the analysis is the proximal point
In view of the two stationarity notions given in Section 1.2, we start with the result showing that Algorithm I outputs point at which the norm of the gradient of Moreau envelope is small, in expectation.
u (x, = arg min I.p (u, y) y) + /
|u
z/|²
uex
2
(11)
+ 2
u x||
For the result, we state the algorithmic parameters. To avoid clutter, we write the orders of the parameters by highlighting their dependences on the problem parameters. The explicit forms of the parameters are given in (25), in App. A.
With this, we trivially have
P1/A y. z) yx..),))
_ おリ 1| ||, 2/12 + | yx) x1
1
12 VT
B
B
VT
(8)
This is the main point of departure from (Zhang & Luo, 2022) where the proximal AL function is used in the analy- sis, in the potential function. This is because (Zhang & Luo, 2022) used a projected full GD step on the proximal AL. function for which, a descent inequality follows directly. In our case, because we apply projected SGD step, be able to handle updates with single-saple stochastic gradients, we need to use the Moreau envelope of the proximal AL function in our potential. This analysis of projected SGD was pioneered in (Davis & Drusvyatskiy, 2019).
# يز A X
+ (I + 1).
We are now ready state the first main result.
Theorem 3.1. Let Assumption 1.1 hold and run Alg. I with parameters from (8). We have that E| (z.-) )ll S E where to is selected uniformly at random from {0..... T 1} with T T=Ω(( (( The stochastic oracle complexity is O(e
In particular, the above result gives us an e-near stationary point in view of (Davis& & Drusvyatskiy, 2019). To get an e-stationary point, we perform a post-processing procedure to obtain the following output from the result of Alg, 1:
The first result a descent result on the Moreau envelope. Lemma 3.3 (cf. Lemma A.5). Under Assumption 1.1, for the x++1 update given in Algorithmm 1, we have
x = =proix (x+- (x Vr+1,
16E [PI/A(X 2++1)
with S 1 where Lx is the Lipschitz constant of ,,(, + 2
< 16E [P1/a (Xi, No+1, (241,
Lg
-x12 (cf. (25)) and
->X 2 1u (xi, N(+1, 2i) - -xel2 + 8XT202
+ 2 (4XTH + 16X72 42² + + /12) Eliz. - zc-1l??
B
G(xr.yr+11 2
Σ
G(x Ne E.)
where 7, = 2/ p|AA||
This follows mostly from (Davis & Drusvyatskiy, 2019) and handles the transition from x, to X in our analysis. One additional error term we have here || - -z 1,,12, due to the change in the proximal center z,, term that was not involved in the analysis of (Davis & Drusvyatskiy, 2019).
for &i i.i.d. and B = (e-2). This is the only place where we use a large batch size and Algorithm only runs with a single sample at every iteration. This post processing step is only done once and does not affect the overall complexity. The details are given in Appendix A.3.
Next, we incorporate the dynamics of the updates on the dual variable y, and the proximal center 2,, These re- sults use some ideas from (Zhang & Luo, 2022) with addi- tional insights. This is because Zhang & Luo (2022) use
Corollary 3.2. Let Assumption 1.1 hold. From the output of Algorithm 1, we can obtain & which is an e-stationary point. The complexity of the whole procedure is O(e
5

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Algorithm 1 Stochastic smoothed and linearized ALM
Initialize: X = Zo E XYyo Yo E IR' and p 2
for t = 0 to T 1 do
Y++1 =y: + Axx; b)
Sample & E E ii.d. and let Gixx, Y111, 21, vf(xx + A Y4+1 + A pAT(Axx
(Ax: b) + + -z,).
X++1= proj (x+ - (x., Ze,
ze+1 = Z, + 3(x, zi)
y) + |1 - 2||2 in their potential, so their analysis only characterizes the change in y and z in this function. Our analysis however, needs to characterize this change in the Moreau envelope of this function. This requires further estimations using the properties of the Moreau envelope, and the proximal point u" (x, Y: 2) (see e.g. Lem. A.6).
sample of stochastic gradients. Hence, it is not clear if it is possible to show a useful inequality with the proximal AL function in the constrained case. In particular, until the work of (Davis & Drusvyatskiy, 2019), convergence analyses of projected SGD required large batches.
In addition to combining the bounds from the previous sec- tion on the change of P1/A, we have to characterize the change in d(y; 2) and (z), for which we can use the fol- lowing estimations, which only use the definition of yr+1 and hence have the same proof as the previous work.
Lemma 3.4. (cf. Lemma A.6) Under Assumption for the iterates of Alg. 1, we have
2E 14111 (x), Nx+1,1+,222 N++1,2(+1)) zt+1)]
< 21E [F11/2(X0,) (x,, 2:)]
Lemma 3.5. (Zhang & Luo, 2020, Lemma 3.2, Lemma 3.3) For d(y, 2) and Vi (z) defined in (7) and (12), we have
-2E(yr+1 - Yr, Au" (Xc, zi) b)
yv,
-BB2z Ze+1, 2u Vx+1, 21) Z++1 2z)-
2d(y Zc-1) 1) - 2d(y',, 2x)
It is easy to notice that combining the last two lemmas will give us a bound on the change of PI/A from t to 1+ On the other hand, the inner products appearing on the right-hand side of the last bound will require an intricate analysis after combining with the terms coming from other components in the potential function, introduced next. One aim, is to make sure we get enough slack to be able to cancel error terms coming from |2++1 zell² in the previous lemma and further errors that will arise as we handle the inner products.
2 21 Ax (y++1, 2,) - b)
+ u(zz11 Ze, Ze+1 + 2t 22x (ye+1,
and
(((z-1) - (((z) S p(zc+1 Ze, 2z x" (zi))
1 1/ 7 11?
+ 20
where 04 = K-LL and
x" x"y,z)= arg min L, (x + -ー ||x z/|²
(13)
3.3. Proof Sketch
xeX
x²(x)= arg min f(x) + / |x z 2
1. ONE ITERATION INEQUALITY ON THE POTENTIAL
(14)
x
As alluded to earlier, we introduce the potential function we work with, which incorporates the Moreau envelopes defined in (10) and (7):
We continue with the main inequality on the potential func- tion with one iteration of Alg. 1. The proof of this lemma is rather intricate and requires a careful combination of the inner products coming from the previous lemmas, and uses the particular update of the proximal center Z,41 as well as parameter selections. Recall that u" (x, y, z) and x (y, 2) appearing in the lemma are defined in (11) and (13).
VA = (x., 2.) - 2d(y 21) + (2)(),)
where we used the new notation
d(y,z) z) = min (x) + - 2/1². xex
(12)
Lemma 3.6 (cf. Lemma A.9). With Assumption 1.1 and parameters in (8) (see (25)), we have for Alg. / that
There are two main changes compared to the analysis of (Zhang & Luo, 2022). The first is that the primal descent portion of our analysis investigates the behavior of the Moreau envelope of the proximal AL function (given in (10) whereas the analysis of (Zhang & Luo, 2022) analyzes the proximal AL function (given in (19)) directly.
EV- - EV4+1 2 cgBl Z1+1 - 2112 27 02222 1/2
- -c u (X,, x, 1|
+ =,,, FxEl|Ax"(y++11 (y zr)
bb1 (15)
The reason for this departure is the well-known difficulty while analyzing SGD for constrained problems with single
where c, = e c, = - c3 = 0(1VTT)
with their precise definitions given in Lemma A.9.
6

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
One novelty in our analysis is to show that this potential function is still lower bounded and decreases, in expectation, up to an error term depends on x² and the variance. To integrate this change into the framework of (Zhang & Luo, 2022) under reasonable assumptions on the stochastic oracle as mentioned earlier in Section 2, we also slightly changed the definition of 2 in the algorithm, due to technical reasons. In particular, in our case, we lose the control over ||x+1 - xel? (since we do not assume bounded domains in this section), whereas the deterministic analysis of (Zhang & Luo, 2022) have natural control over such terms.
An immediate issue here is that the variance of stochas- tic gradients of the proximal AL function scales linearly with and y. Hence, assuming bounded variance would require assuming bounded dual variables, which is a strong assumption that is not satisfied in practice. To go around this difficulty, we have two adjustments, (i) we assume a con- straint qualification (CQ) and compactness of X and (ii) we include a safeguarding procedure in the algorithm to moni- tor when the dual variable gets too large. Under these two modifications, we obtain the same complexity guarantees as our previous setting with deterministic constraints. Assumption 4.1. For problem (16), the following holds:
The other change is the error coming from the variance of stochastic gradients. This causes the complexity to deterio- rate compared to the deterministic case, which is an effect common with algorithms based on SGD, In particular, with correctly selected step size, we obtain a sample complex- ity with the same-order as SGD, which is optimal even for unconstrained nonconvex problems (Arjevani et al., 2023).
1. The feasible set {x: x E Xx = b} is bounded.
2. The origin is in the relative interior of the set { b: x E X).
3. A has full row-rank.
In addition to the assumptions in the earlier setting, we require a Slater's condition as well as compact domains to ensure boundedness of the dual variable. Slater's s condition is classical CQ, see e.g., (Bertsekas et al., 2003, Sec. 5.3.1). Remark 4.2. The choice of M, is given next, which admittedly can be difficult in practice. Let My m x (K(x, 0, 2) 2d(0, z) + (V(2),, M xa {x) +
3.3.2. COMPLEXITY ANALYSIS
After Lemma 3.6, it is straightforward to obtain
E 1 z:l 2| < =²:
Ax (yc+1.2.) bl 2 S 2
|x (xxx=xI b"],, where K is defined in (19) and Me is uniform lower bound of (z.). e.g., f. According to Assumption 4.1, there exists r > 0 such that for any direction d E RA)ge(A), we can find x E X satisfying b| = r and Ax b has the same di- rection as d. Then, we choose M, as M,, > My M2+
E u V+41, 21)
x111 S E?
when T= O(==A) Then, by tedious but straightforward calculations, can directly get the bound the norm of the gradient of the Moreau envelope, (Z,),, obtaining near-stationarity. The details appear in Appendix A.2.
A couple more steps let us go from this result to an E- stationary point. The idea is simple: since we know that small (z+)] means that we are near a stationary point, we can perform just one more iteration of SGD with batch size x E 2 to get an e-stationary point, without changing the worst-case complexity. The details are in App. A.3.
In this setting, we only state our theorem for near- stationarity. The e-stationarity would follow in the same way as the previous section by a post- post-processiig step.
Theorem 4.3. Let Assumptions 1.1 and 4. 1 hold and run Alg. 2 with parameters from (8). We have that R3] V V (z--) )ll S where t" is randomly selected from {O,..., T 1} with
T = =(E==t) The stochastic oracle complexity is O(s +
4. Extension to Random Linear Constraints
As mentioned earlier, the optimal sample complexity for nonconvex optimization with Lipschitz V f is O(e-1) (Arje- vani et al., 2023). Our result matches this complexity while handling linear constraints with random sampling.
We turn to the case when constraints are sampled, that is, we do not have access to the full matrix A, or vector b but only unbiased samples of them. This is a suitable setting, when, for example, we have a large matrix A. In particular,
we have A = Ee- [Acc] b =
[c<p[be] and use Aç, by in the algorithm. We rewrite the template for convenience, as
5. Extension with Variance Reduction
We now integrate the STORM variance reduction technique from (Cutkosky & Orabona, 2019) into our framework to solve (1) (See 2XXi:25044007607 for extension to stochastic constraints). We obtain Alg. 3, which improves the iteration and oracle complexity from O(=-4) to O(s-3) under a stronger assumption on the oracle, compared to Sec. 3. This (17)
min (x) subject to Ex~ bz] 0. xEX
(16)
In this case, get an unbiased stochastic gradient for proxi-
mal AL, we need to sample two i.i.d. samples of ç:
G(x,y,z, ()(xx))
not only leads to an improved rate, but also to a simpler analysis that does not rely on the Moreau envelope P1/A--
+ 45.y + - bez) + f(xx - 2).
7

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Algorithm 2 Stochastic smoothed and linearized ALM for stochastic constraints with dual safeguarding
Input and Initialization: My - +2M (check Remark 4.2), X 2o E X, yo RT P p 0. for t 0 to T - 1 do
Ye+1 Yt + 77,,, X by.) where & ~ P is generated i.ddd
if [| |I 2 My then
Yt+1 =
Sample &e E E i.i.d. and generate Eg, Yr41 2,, Vxl,(xx. + pxxx - 2,) as in (17)
Xt+1 projx (xt (x, V1+1, Et)
24+1 24 + [x; 2+)
Algorithm Stochastic smoothed and linearized ALM with STORM
Initialize: Xy Zo E No E R", V = N Em Vf(xu, (t), N T1/3 and 2 for /. = to do
Ye+1 Yr + 17 -b) b)
G(x, z,) = vi + A A y141
Ayy11 + PA - b) + +xxx - 21)
X1+1 projx (x, rG((,, 1 2t))
Z++1 = 2, + 3(x: -0- ),)
Sample fi+1 ~ ii.d. and set v fi+1 Vf(x(11: + +11-a) - Vf(x,, Et+1))
Alg. 3 and Alg. mainly differ in the update of stochastic gradient estimate V I 0, Alg. trivially reduces to Alg. 1. We next see that a particular choice of o gives better complexity under Assumption 5.2 (which is stronger than the oracle access and smoothness in Assumption 1.1). Remark 5.1. We only
Lemma 5.3 (cf. Lemma C.4). Under Assumptions 1.1 and 5.2, with parameters
# maxx(2,44g) T-
(20)
JJ = O(T), B 0 a a= 0
minibatch in the initialization, which does not affect the overall complexity. The minibatch size is N = 1/ which is small compared to the total num- ber of iterations T. Iterations of our algorithm only require 2 stochastic gradients, V (xi: 1x+1) and V fX {1+1).
(for detailed parameters, see (82)) we have
24
1
EV. EV+1 2
El - Ze+1 112 +
El[x: - x
3
27
+nn Ax 1xllAxxxxxxx (y++1,
-bl²
b112
For the analysis of Alg. 3, we introduce Assumption 5.2, used, e.g., in (Arjevani et al., 2023). In particular, Arjevani et al. (2023) showed that the oracle complexity O(= is tight under Assumption 5.2 even with no constraints.
E V Vs(x)]1 - (21)
Note that, on a high level, the main difference between Lemma 5.3 and Lemma 3.6 is that the order T in the error term different. In Lemma 5.3, the order of r O(r"), while in Lemma 3.6, the order of is O(72), which contribute to faster convergence rate in for Alg. 3.
Assumption 5.2. We have access to stochastic gradient of ff satisfying (3). For given & ~ E, we can query V f.(xx, {) and V Vy(y <) for different points x, y. Moreover, we have V f (x, E) Vy =) < L x y
Theorem 5.4. Let Assumptions 1.1 and 5.2 hold. We have that E| V (z(-)) )ll I where t" is selected uniformly at random from (O...., T - 1} with T ((==3)) The com- plexity of the whole procedure is 0(s
We introduce the potential V. differing from Sec. 3 and 4. This is similar to (Zhang & Luo, 2022), except the last term which controls the error from the variance. Define
V1 = K (X.. Ve, 21) 2d(y). 2)) + (2,)
1
(18)
6. Related Works
- (xx
48(13 + 1,3)T
We now compare the complexity results for obtaining an e-stationary point, in view of Section 1.2.
where
(xx,y,2) (xp 1 2
(19)
Deterministic objective and deterministie constraints. The setting when objective f in (1) is deterministic is the most well-studied with many results in the classical litera- ture (Bertsekas, 2014). Recent work characterized the global oracle complexity of Lagrangian- based methods or ALM.
One-step evolution of Vú that we analyze next is a key step in the analysis. Compared to (Zhang & Luo, 2022), we have the extra error due to using V, instead of the full gradient.
8

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
With nonlinear and nonconvex constraints, many of the ex- isting works analyzing AL.-based algorithms rely on strong CQs and boundedness assumptions and use large penalty parameters to ensure feasibility (Li et al., 2021; Lin et al., 2022; Kong et al., 2019; Kong & Monteiro, 2023; Kong et al., 2023). The existing frameworks so far fail to capture the importance of dual variable updates, which are, in fact, the main reason behind the ability to use constant penalty parameters while ensuring convergence, see e.g., (Bertsekas, 2014, Sec. 2.2.5). Recent works mentioned above obtained the complexity bound 0(e-3) for general nonlinear con- straints with no specialization for linear constraints. When specialized to convex functional constraints, the best-known -2.5) (Lin et al., 2022). complexity for these methods is O
straints under Assumption 5.2. This work only covered the case X = R and left open the question of handling the case of general X, see (Alacaoglu & Wright, 2024, Sec. 5),
We resolve a special case of this question when X is poly- hedral (covering many applications), allowing our analysis to cover linear inequality constraints. Alacaoglu & Wright (2024) used variance reduction for ff. which meant that they required Assumption 5.2, stronger than Assumption 1.1. In Sec. 5, we get the same complexity as this paper while al- lowing a polyhedral X to cover linear inequality constraints, which cannot be handled by Alacaoglu & Wright (2024).
Moreover, we also get the complexity O(E-*) under As- sumption 1.1. This is optimal under Assumption 1.1 and we refer to (Arjevani et al., 2023) for further details on the lower bounds. In contrast, the work in (Alacaoglu & Wright, 2024) does not have guarantees without Assumption 5.2.
When the constraints are linear, such as (I) with X R", Hong (2016) analyzed ALM with constant penalty param- eters and non-negligible dual updates to get optimal com- plexity (c--2). The case of X f IR" turned out to be sig- nificantly more challenging with many works focusing on variants of ALM with large penalty parameters (depending on the inverse of the final accuracy) to ensure near-feasibility and negligible dual updates that do not help with feasibility (Kong& & Monteiro, 2023; Kong et al., 2023) and obtained the suboptimal complexity Ö(E 0(5-).). The exceptions are the works (Zhang & Luo, 2020; 2022) that showed, for the case X polyhedral, near-optimal complexity O(e-2) with a constant penalty parameter and dual steps with constant step sizes, with no constraint qualification. The key step was the global error bound that our work also relied on. Stochastic objective and deterministic constraints. One important step in generalizing the template to tasks arising in ML was to consider stochastic objectives where we ac- cess unbiased estimates. With general nonlinear constraints and Lipschitzness of f,, the optimal sample complexity is O(s-)), obtained with double loop algorithms (Curtis et al., 2024; Boob et al., 2023; Ma et al., 2020). These works re- quire strong assumptions on the boundedness of the primal domain as well as constraint qualifications, which are often not necessary with linear constraints.
In addition, though (Lu et al., 2024) considers the more general problem with nonconvex functional constraints, they make strong assumptions which are not easy to verify. is not clear if their assumptions would hold with a general polyhedral constraint we have (see e.g., their Assumption (ivv and Eq. (7)). When the constraints are deterministic, we do not have any bounded domain assumption (our See. 3) whereas the assumptions of (Lu et al., 2024) are rather difficult to be satisfied without a bounded primal domain.
Lu et al. (2024) analyzes a Q--based method, whereas we analyze an ALM-variant. ALM is known to be more stable and desirable in practice, but significantly more difficult to analyze, which is because the penalty parameter is fixed in ALM and it increases to infinity for QP. Our ALM algorithm could be extended to stochastic constraints, while (Lu et al., 2024) only handles deterministic constraints. A Alacaoglu & Wright (2024) highlights the importance of analyzing ALM compared to QP methods their Sections 1 and 6.
Stochastic objective and stochastic constraints. This is the most general class, where the existing results come with many assumptions that are not always easy to interpret, similar to the case of stochastic objective and determinis- tic constraints described above (Li et al., 2024; A Alacaoglu & Wright, 2024). The best-known complexity O(= is obtained by using Assumption 5.2, with an inexact, double- loop, ALM in (Li et al., 2024) and by single-loop QP algorithm in (Alacaoglu & Wright, 2024). These results con- cerning ALM need to use large penalty parameters, which renders them essentially as me-mess since the dual up- dates do not contribute to the analysis for ensuring the fea- sibility. Other approaches for solving this sub-case also require double-loop algorithms and stronger assumptions since they focus on generic nonconvex constraint (Boob et al., 2023; Ma et al., 2020), obtaining O without expected Lipschitzness. Hence, in this sub-case, none of these results harness the structure of linear constraints.
Another set of results concerns stochastic optimization with deterministic nonlinear constraints with penalty-based al- gorithms. These works require large penalty parameters to ensure near-iiasyyylity rather than dual updates (Lu al., 2024; Alacaoglu & Wright, 2024). They assume expected Lipschitzness as Assumption 5.2, which is stronger than Lipschitzness of f.f. Since these works focus on nonlinear functional constraints, the analysis requires boundedness assumptions as well as constraint qualifications, unlike our results in Section 3 for deterministic linear constraints.
Alacaoglu& & Wright (2024) considered ALM with a con- stant penalty parameter and non-negligible dual updates and obtained the complexity O(e-3) for linear equality con-

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Acknowledgements
Drusvyatskiy, D. and Paquette, C. Efficiency of minimiz- ing compositions of convex functions and smooth maps. Mathematical Programming, 178:503-558, 2019.
Jiawei Zhang is supported by the startup fund from the Department of Computer Sciences the University of Wis- consin-Madison and the MIT Postdoctoral Fellowship for Engineering Excellence.
Hestenes, M. R. Multiplier and gradient methods. Journal of optimization theory and applications, 4(5):303-320, 1969.
Ahmet Alacaoglu acknowledges the support of the Natu- ral Sciences and Engineering Research Council of Canada (NSERC), [funding reference number RGPIN-2025-066344
Hiriart-Urrun Currut, J.-B. and Lemarechal, C. Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods, volume 306. Springer Berlin Heidelberg, Berlin, Heidelberg, 1st 1993.;1; edition, 1993. ISBN 0072-7830.
Impact Statement
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Hong. M. Decomposing linearly constrained nonconvex problems by a proximal primal dual approach: Algo- rithms, convergence, and applications. arXiv preprint arXiv:1604.00543, 2016.
References
Hu, Q. Qi, Q.. Lu, Z.,, and Yang, T. Single-loop stochas- tic algorithms for difference of max-structured weakly convex functions. In Advances in Neural Information Processing Systems, volume 37, pp. 56738-56765, 2024.
Alacaoglu, A. and Wright, S. J. Complexity of single loop algorithms for nonlinear programming with stochastic objective and constraints. In International Conference on Artificial Intelligence and Statistics, pp. 4627-4635. PMLR, 2024.
Katz-Samuels, J., Nakhleh, J. B., Nowak, R., and Li, Y. Training OOD detectors in their natural habitats. In ICML, 2022.
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199 (1):165-214, 2023.
Kong, W. and Monteiro, R. D. An accelerated inexact dampened augmented lagrangian method for linearly- constrained nonconvex composite optimization problems. Computational Optimization and Applications, 85(2):509- 545, 2023.
Bertsekas, D. Constrained optimization and Lagrange mul- tiplier methods. Academic press, 2014.
Kong, W., Melo, J. G., and Monteiro, R. D. Complexity of quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex com- posite programs. SIAM Journal on Optimization, 29(4):
Bertsekas, D., Nedic, A., and Ozdaglar, A. Convex analysis and optimization, volume 1. Athena Scientific, 2003.
Boob, D., Deng. Q., and Lan, Stochastic first-order meth- ods for convex and nonconvex functional constrained optimization. Mathematical Programming, 197(1):215- 279, 2023.
2566-2593, 2019.
Kong, W., Melo, J. G., and Monteiro, R. D. Iteration com- plexity of an inner accelerated inexact proximal aug- mented lagrangian method based on the classical la- grangian function. SIAM Journal on Optimization, 33(1): 181-210, 2023.
Curtis, F. E., O'Neill, M. J., and Robinson, D. P. Worst- case complexity of an sqp method for nonlinear equality constrained stochastic optimization. Mathematical Pro- gramming, 205(1):431-483. 2024.
Lan, G. First-order and stochastic optimization methods for machine learning. Springer, 2020.
Cutkosky, A. and Orabona, F. Momentum- based variance reduction in non-convex sgd. Advances in neural infor- mation processing systems, 32, 2019.
Li, Z., Chen, P.-Y,, Liu, S., Lu, S.,, and Xu, Y. Rate-improved inexact augmented lagrangian method for constrained nonconvex optimization. In International Conference on Artificial Intelligence and Statistics, pp. 2170-2178. PMLR, 2021.
Davis, D. and Drusvyatskiy, D. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1 21)22207-- 2019.
Dener, A., Miller, M. A., Churchill, R. M., Munson, T., and Chang, C.-S. Training neural networks under physi- cal constraints using a stochastic augmented lagrangian approach. arXiv preprint arXiv:2009.073330 2020.
Li, Z., Chen, P.-Y,, Liu, S., Lu, S., and Xu, Y. Stochas- tic inexact augmented lagrangian method for nonconvex expectation constrained optimization. Computational Optimization and Applications, 87(1):11-1147, 2024.
10

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Lin, Q- Ma, R., and Xu, Y. Complexity of inexact proximal-point penalty method for constrained smooth non-convex optimization. Computational optimization and applications, 82(1):175-23) 2022.
neural information processing systems, 33:7377-7389, 2020.
Zhang. J., Ge. S., Chang, T.-H., and Luo, Z.-Q. Decen- tralized non-convex learning with linearly coupled con- straints: Algorithm designs and application vertical learning problem. IEEE Transactions Signal Process- ing, 70:3312-3327, 2022.
Lu, Z., Mei, S., and Xiao, Bariance-reduces first-order methods for deterministically constrained stochastic non- convex optimization with strong convergence guarantees. arXiv preprint arXiv:2409.00 09906, 2024.
Ma, R., Lin, Q., and Yang, T. Quadratically regularized subgradient methods for weakly convex optimization with weakly convex constraints. In International Conference Machine Learning, pp. 6554 6564. PMLR, 2020.
Nocedal, and Wright, S. J. Numerical optimization. Springer, 1999.
Ouyang, Y., Chen, Y., Lan, G., and Pasiliao Jr, E. An accelerated linearized alternating direction method of multipliers. SIAM Journal on Imaging Sciences, 8(1): 644-681, 2015.
Planiden, C. and Wang, X. Strongly convex functions, moreau envelopes, and the generic nature of convex func- tions with strong minimizers. SIAM Journal on Optimiza- tion,
2016.
Powell, M. method for nonlinear constraints in mini- mization problems. Optimization, pp. 283-298, 1969.
Rockafellar, R. T. Augmented lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of operations research, 1(2):97-116, 1976.
Rockafellar, R. T. Extended nonlinear programming. Non- linear optimization and related topics, pp. 381-399, 2000.
Yan, Y. and Xu, Adaptive primal-dual stochastic gradi- method for expectation-connsraanee convex stochastic programs, Mathematical ProgaatiaaarPrrramaiaa Programming Computation, 14
(2):319-363, 2022.
Zhang, J. and Luo, Z.-Q. A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization. SIAM Journal on Optimization, 30(3): 2272-2302, 2020.
Zhang. J. and Luo, Z.-Q. A global dual error bound and its application to the analysis of linearly constrained non- convex optimization. SIAM Journal on Optimization, (3):2319-2346, 2022. doi: 10.1137/20M135447433 URL https: http::///do... org 10 1137 220337220022 220130471343
Zhang, J., Xiao, P., Sun, R., and Luo, Z. A single- loop smoothed gradient descent-ascent algorithm for nonconvex-conee min-max problems. Advances

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Notation.
Let us note that we define by E, the expectation conditioned on the randomness up to and including X
A. Proofs for Section
In the proofs, let us recall
y(x,y.2) = (xp(x,y) P ||x - 2||2 2
(22)
f(x) + (Ax - b,y) + 2 f11 - bl12 + f11 =212.
With this notation, we have the following, equivalent (11):
X |11 -x1
u (x,,,2)) arg min ueX
K(u,y,
2
(23)
arg min ueX
Lp(u,y,z)
1 || zz|²
2/1u x11
>
We also recall (10).
(x,x(x,8,2) = min
# Lpp (u
u 2/|2
u| x11
ueX
2
2
(24)
min uex
K(u,y,2 z)
+
x
We also introduce here some parameters that are used throughout, for convenience.
# max 4L J.
T = T. + *|||A|| +
A 2L,,
01 Ls
T GX²VT'
(25)
2u + |||
T(2 - -|(A113)
7 min
4||A|2
20/1 A112
8 min
1000 50A 36
(μ L
% = 2p + pl AlI
YK L..
# L, +X
We also mention the following basic facts that are used in the sequel. Fact A.1. For x E X. we have that x + K(x,y- y. z) is strongly convex with modulus == / Ly, and VxK(x,y,2) is L = (I, + 2|| + Lip-ippchitz continuous.
For u E X, u + K(u,y, 2, - >
|x - u/12 is strongly convex with modulus Vs- = 11 Ls + X, and u² (x,,
arg min uex K(u,y,2 2) +
1 x-
11
2
Lemma A.2. (Planiden & Wang, 2016, Lemma 2.19) Let r > The function f is r-strongly convex if and only if
fi(x) = min, f(u) x1|x- u is 1+ -strongly convex.
(n-LA)A
Lemma A.3. The function x (x, y.z) z) is 4-LstX strongly convex.
Proof. By definition, we have
K(u, y,2) - Ix(u) + ||x -ull?
(x/1 y. = min ((,,y, + +x(u) + 7 22ll A Amin
X
2
12

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Recall that 7K - Ly. Then, since (x 1K -stronggly convex, we have ming K(u.y (onyy+)+xxxle (u) - convex, by Lemma A.2. Hence, PP1/1 yx, 2) is strongly convex with modulus
+ 2 2/11x - u |
X
is 7K /A
ATx
7K 7K/A+I
7K/A+I
X+7*
(r- 11-11) P L
A.1. Proofs for Lemma 3.6
In the next lemma, the first part is using the idea of Davis & Drusvyatskiy (2019) to analyze the algorithm under the bounded variance assumption instead of the restrictive bounded stochastic gradient assumption. The second part of the lemma also follows a similar idea as this work, with the exception of the dependence on the changing center point 24- This introduces additional issues, since the stochastic gradient in the update of X depends on 2, whereas the proximal point u' (x,, Ve+1, z(41) (that characterizes the iteration below) depends on Zc+1. Our analysis below estimates this additional error and shows it be in the order of [| zell², which will be handled later.
Lemma A.4. Suppose that Assumption 1.1 holds, for the proximal point u² (x1, 2++1), defined (11) we have the characterization
u'(x Yt41, z1+1) = projx(Tλx; + (1 - A)uu (xe, (x;, Yr41, Ze+1) - T V (x: (x.. Zc+1) (10-1112++1) Ye+1 Z(+1)). (26)
Moreover, for the sequence X calculated as Algorithm with X = 2T and r S ex where T.K- = T.g + Ml A|1 2 + we have
E u" (X., Vc41. - x++1|| & (1
Td 71 Bl (x,, N(41. - xxll (TH + 27 2r222²2222) (2))E) - -2+1112 + 722
4
Proof. From the definition of u² (xe, Y++1, Z441) in (11) (see also (23)), we have
X(x u² (x:. Y++1, Be+ E (u"Kuu(x, (x,, V4+1, R411), Ye+1, 2+11 + (1 (x+,, (e+1)).
Multiplying both sides by the step size t, adding u² (x., 1 2441) to both sides, and rearranging give
TXx, -V K (u" N1+1, Ze-1) 1): Ne+1, 2.- + +1 -A-=-AAj"ae Ye11,
E ux;, yx
Yr+1, 1:41) + 70l (Xt, Zc+),
projx due to 0lx being a cone and proximal operator of a normal cone being the projection the set, have the first assertion.
Since (1 + -(1x))= μ
We next establish the second assertion. Using the just established identity (26), the update rule of x in Algorithm 1, and nonexpansiveness of the projection, we derive
I (xt, Yt+1, Z++1) X++1|l
< T + (1 - =A)u" (Xt, Yt+1, 2--1) - VVxX(u'xxxxx,. Yr41, Ze+1), Ye+1, Ze41) 1- [x: - TG(x, Yr+1, Ze, &)]l
We add and subtract VxK V141, 2:) inside the squared norm on the right-hand side, expand and take conditional expectation to obtain
E, uu (X,, N141. 2411) - x(+1 2
= - ((11-r)(uurte (Xi, (X., N++1, 2141)= - x:) - VV (xi, Ye+1, 2411. 24+1) + + V
+ - 7,,,, Y4+1: 1+1, Z4, Ee) (xx, 21)?
(27)
where the cross term disappeared because
E, [G(x,, Ye+1, Zz, 6.) = V (x
and xx, 1, 2 u² (xx, 1, 1 are deterministic under the conditioning since 1,41 defined in Algorithm I only depends x; (that is, Ze+1 is independent of &
The second term on the right-hand side of (27) is trivially bounded by the oracle assumptions, that is,
E, | (x1, Yet1, 24, Et)
XxK(X, N141, 21)] < o².
(28)
13

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
For the first term the right-hand side of (27), further estimate
[[[1 (xx.
x,) - r VVx((u (x,, N111, (11 (
(1 - - (xx
x1I
+ + ->) (x,,,,, X VxK V+11, VxK(u" (xx 2441))
+ V
(29)
Next, we turn estimating
V ((1 (x 2++1ll
S (x z,) (x
Mxt,,, V (xx, (et,, 2
(30)
Note that, by definition, we have
(x1, Vx (x,, Vr+1, Zi+1) p(zz+11 zz).
Using this and the Lx Lipschitzeess of V
X (K (++++11 1e+1) per Fact A.1, in (30), obtain
V (x,, ,e+1, z+) Vx Ku"("" (x,, Y++1, 7++1); Y++1; 1 S /
zell + Lx||u"((x,,) Ye+1, Ze+1) xell-
We plug this bound into the second term on the right-hand side of (29) after using Cauchy-Schward inequality, and then, we use Young's 's inequality to get
2r(1 - -A (x,, Y1t1, Ze+1) x,, VxK(Xx: Yt+1, VxK (xt1, 21,1) N141, 2et1))
< 27 -
(xx: (Xe, Y241, - x: xxl1(u//2e++ zell Lx ||" (Xe, V141, xxll)
S - +
- x. + + -1Ju((2) - 2e112 Yr+1, Yx4,,
Using the last two inequalities (29), along with Young's 's inequality, we obtain
[I(1 (x)
x,) ~V VV>KKVKK
v1.1 V
< - [A1= - + p)) + 27 (x xxl
+ (T(1 - T\)μ + 2 2,41 zz 12
(31)
We estimate the coefficient of the first term. First, note that 7A S 1, As a result, we have
-1 + 7( A2 + 1³) 2
< 2r 22 + 722 11)
1
- 1 - 2r\ +
- + 2 -A
12 T>
6
= 1 4
where in second inequality, use rd LL } and TH S TLK = TT Finally, since 7(1 - 7)) + 27 < T/ + 2r²,," the proof is completed after taking full expectation of (27) and plugging in (28) and (31).
Lemma A.5 (cf. Lemma 3.3). Let Assumption 1.1 hold. Then, if A = 2LK and T S Algorithm 1 that
6x. we have for the iterates of
1
222
B4H1 S (841,
E El(u" (xt. Nc.1. xxe12
16
ATP 2
TX²1²²
2r
+
2
Eliz: - 2 112
(32)
8-2
2
where 7s = 2/x+ + A|]
14

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Proof. By the definition of P1/A from (24) and u' (x,,,,,, from (23), we have
(x11 2441) - Ye41 Z(+1) + E
(xt, X(+1ll
rA²
S EK(u (xt, Yt+1 2411). Vt.1. 2(+1) +
E
1,,1, -x,11 x1|1
2
8
ATH + xx7
Ar
+
Eliz|- Z1+1 11
+
2
2
Me+1, 2++1) 2
BBll1* (xt, Mt+1, 2(+1) - x:|
ATH x79 El|zz Z 1| +
\r²o²
(33)
2
We next bound the second term on the right-hand side by using Young's inequality as
| Y141, Z+41) - xx112 2 Xx, Ye+1, 2,) xx |u' [x,, N1+1, Zo+1)
u yxe, 2.11
/12
2 2
u Xx: )t+1. - x1112
22l1zz 1|z 21+21? 1122-2+2111
(34)
%
where the last line used (61).
We substitute the last inequality into (33) to conclude.
Since the previous result only allowed us to connect (x/x(Xx+1, Y1+1, 2441) to (x/x Yr-1, 7411), we now need to analyze the effect of changing Yt+1 and Ze+1 in (P1/A- The main idea of this lemma is similar (Zhang & Luo, 2022), where the difference lies in the fact that our potential involves the Moreau envelope of K (x, whereas the potential of (Zhang & Luo, 2022) involves K K(x, y, z). Hence this work considers the change of the arguments in the function K instead of (P1/2- Therefore, our proof uses the properties of the Moreau envelope which was not needed in (Zhang & Luo, 2022).
Lemma A.6. (cf. Lemma 3.4) Suppose that Assumption 1.1 holds. for 91/2 defined in (10), we have for the iterates of Algorithm 1 that
(x..
2 (y: - -141, (Xe, zi) - b)
+ 2
||" (x, 2;) - u (xt1, 2:)
#
2
[2++1 2,, 2u (xx, V++1, - -z-1 - zz)
2
+ | (X1, 2441) u² ux1,, (x+,,,+1,14 21)1
where 7s - p||A|].
Proof. We first consider the change in y argument of 11/X. By using the definition of 11/A in (24), we have
(x/ 21) (1/A 2i) K(u" Yc. > 1|xx u" u'(x..ye. 2c)l2
K(( y 2.) 1|x: uu ux', Ye41, 21)l
>
(x. K(u (xr: Yt. 2t), Y(+1,
>
((' (2), + 2 || u (x,, Ne, 2, ||2
x | u² 2x1, (35)
(x y141,
where the second equality adds and subtracts K yx.
24) 24).
15

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
From the definition of K in (22), it trivially follows that
(uu" (Xt, 2e), yt, 2z) - (xx,(x,,, 2x), Yt+1, 2x) (yt Ye+1, Au" (x,, - b).
Next, the property that K(,, (1,1,,1,2,) 24) + 211 xx112 is %t-ttongly convex with minimizer u' (Xt, Yet,, 24) (see Fact A.I and (23)) to obtain
y(,, Ze,, 2 ||x, u'xx,, (ar (x1((x ) ||x: u 8x41,
u² Ye1,,
Combining the last two estimates in (35) gives the first assertion.
Next, we analyze the effect of changing the z component in 91/A. Similar to the proof of the first assertion, we start with the definition of 11/A and then add and subtract (x'"(xx Yt+1, Z441) obtain
(1/A Y1+1, 2,) P1/A (x+, Yt+1, 2z+1)
X
K(u (Xi, Yr+1, zr). Ve+1, Ze)
+
xx: u² (X,, Y1+1,
2
114 2+1)), M++1 2++1)
X 11 1xx, Yet,
=K(u" (x4,) Yo-1, ze) K(u" Y1+1, 2c.1
+ K(u" (x. 8:), y++1, 2++1) +
x ---uu 1'1, 21)l 211
- -K(u" Ve4, y++1, Z(+1) ||x - u
(36)
First, by definition, of K, it trivially follows that
((uu (e1. v..1. - (xx, 2c41
| Ve+1, 21) z
Iu Yt+1,, 21) 24-1 1|/
For the remaining terms on the right-hand side, again use that ((,ye41;; -l -x 1 is -t-stroglly convex with minimizer u" (Xx: Yc+1, Z(+1) to deduce
K(n (x41 26). Ye+1, 2(41) + // ||x; 12" (xxx
K(u' (xt, V:41, Z141) Yt41). (1111,11+111 Zt+1)
2 ||x;
- vxxxx.,
To Ye1. 2441 u (x+: Yt-1, 212
2
Plugging in the last two estimates in (36) gives the second assertion.
Corollary A.7. Suppose that Assumption 1.I holds, for 1112 defined in (10), if 2 and S 1
6x we have that
TA2
(x1/x(X;, V1, 2.) EXI//(Xee V4411 Bet1) >
E l ux Fr+1, 2c)
xrl1
16
ATH + 2 +
TX2
27
E 21 - Ze41
8-2
mE - b. Au" (x,,
Nc, 21) -
+
E "((2+11 2c, 2u (x,, Y++1, 21) 21+11 zz),
2
where 7s = 2/1 + A|]
16

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Proof. We sum up the results in Lemma A.5 and Lemma A.6, plug in the definition of Y1+1 and discard nonnegative terms on the right-hand side get the result.
Next, we analyze the rest of the terms appearing in the potential function. This lemma is only using the definition of d(y, z) and V (z) and is equivalent to (Zhang & Luo, 2022) and hence omit its proof. Notably, these bounds are agnostic to the algorithm used to generate the sequences. Note that the only difference is that in the result below, we do not use the definition of Ye+1 whereas the proof in (Zhang & Luo, 2022) uses this definition. The rest of the estimattios are precisely the same.
Lemma A.8. (Zhang & Luo, 2020, Lemma 3.2, Lemma 3.3) For the functions d(y, 2) and (z) defined (12) and (7), we have
b) + H
d(yc+1, - d(ye, zi) 2 n/Axx, - Ax
2 [2(+1 Zt, 21+1 + Zz 2xx 2yx"(v+1, Z++1))
(Z(+1)) (Z())= S ((ze+11 - Ze, zt - x (z+)) + 1 21+1l??
201
where 44 is defined in (25).
In the next lemma, we will join the previous lemmas and characterize the change in the potential function.
Lemma A.9 (cf. Lemma 3.6), Let Assumption 1.1 hold. By using the parameters (25) Algorithm 1, we obtain
1 27 (37)
EV,- EV+1 2 cgll Be+1
ze
(xx
xel1² B, (y1+1, 2:) bbl2
where C3 = 60% 7
2rd² 400
Cq = 4.
Proof. Combining Corollary A.7 and Lemma A.8, we obtain
E V Vi+1l = E (xI/ 2 ( (xL+1, V1+1 2(41) + (d(yy+1,2441 - 2d(y),, 22) +2)( - 2 (1(41)
> E 1l (xx. Yt+1, ze) x1 ATM + +x72p2
?X2
T22
Bl -c++ = Ar²
16
87
2
M "E(z,-1 Zz 2u (Xt, Yr41, 2z) 2z 21+1)
-IBE(Ax: b, Au (x., Yr, ko)
b)
2
+ (Ax b, Ax" Axxe(yee1,+ 21)
b) + |B((z+11 - Ze, Ze+1 + 2z - 2x (yr+1, 2(+1))
2/1( - Zz, 24 x" (zx))
P. Ellz ze+1
(38)
04
We next manipulate the terms on the right-hand side. First, by adding and subtracting Ax, on the second argument of the first inner product on the right-hand side, we get
- (Ax - b, Au" (x,, Nv, 2:) - b) = - - bl| n)(x - b, Au (x,, Vo, 2i) Axx).
Consequently, we use this estimate and rewrite the third inner product the right-hand side of (38) with quadratics to have
- Axx, - b, Au" (Xt, yr. ze) - b) + (Ax - Ax (y 2t) b)
= Ax, Ax" (Yz+1, )12 + v|l (yc+1, 2.) b1l - -n n(Ax - b, Au" (X,,
Nr, Au"(x, 21) Axi).
Second, adding and subtracting 2x, in the second argument of the second inner product on the right-hand side of (38) gives
11
/ (z1+1 Ze. 2u" 2x Vc+1. zt) 2xx)) + H (Z(+1 Zz, 2x, Ze Z141).
2 (zL+1 Ze. 2u (xt, V1+1, z:) z z
2
2
For the right-hand side of this term, note that 21+1 2i + A(xx zi) = 2x, -z //3 (zt11 2.) and hence
(Z141 24, 2x, 2t 2(-1)
(2141
24, 2x: 22z)
# 2
(zt+1 24, Zt+1)
2
||z. 21-1112
>
1z Zt41 11
B
23
17

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
where the last inequality is due 5 1.
Next, for the remaining inner products in (38), we have
p u( 2,, 2x+1 + - 2x" (y++1, Zx+1) 2p(2241 24,
x x(()))
Z zel 1 24((2+11 Z4, x (z:) x' (1++1;2++)))
(39)
We can use Cauchy-Schwarz, triangle and Young's 's inequalities on the second term here to get
(Z++1 (z,) - x" (y ((+1) 2 - 1z+
2e|1([[x* (zr) x" (V Z,) + ||x (ye+1, -x"(xxx1111 (V++1:2(+1)1
1 1
2
04 ||:41 z0ll² | x (y++1,
25
where the last step also used (63). Consequently, plugging in this estimate to (39), we obtain
p(
Zz,
Z441
+ Zz 2xx (Yz+1, Ze+1)) 2p((2411 Zz, Z4 x x2,))
1 2/l
||z+1 - -2112 - (C|1x(((2) (2s) x²" (yc+1,
5 02
After combining these estimates in (38), we get
[[[]] [[[++1]
1
T22
3p
1
|5 (X Y1s1, x,l12 3e|13_1
ATH X72
+
p
Bl
1++1
112
x²²02
2
872
04
23
2
-//B(Ax Au' (x,, 21)
Axx)
Ax' (yt+1, )1) + 1/ (yc41, b112
=cE||x* (z.) x" (y4+1,2))) + (Z(41+1 Z₁z u Vc41, x1)
(40)
We will now operate on some terms from the right-hand side of (40), by using Lemma A.11 and A.12. First, we have by Cauchy-Schwarz and Young's inequalities that
yt, Axt) (Ax, b, Au" Yc,
2 A|,, bl1 - Au" A'xn""x;,,X'" yt, 2z) Axel1²
11A; b An (X;, 2,) Au (x,, 2,)12 An (x1,)111,2)) - Ax,
Next, by using the Lipschitzness of u² (xz,',z) 2:) from (60), we have
Au (Xt. 2e) Au" Au"(x, (X.,
<
|| (1 (x,, Nr,
|||l
lly: Y++1ll 112
All
||Ax,
bl(
?
where the last step also used the definition of yt-1- Using this estimation along with (66) gives
{Axx - b, Au A Zt, Axi)
||Ax; - -b12 27|| (xx, xil1
2
7||AA|=>>
411 4||A
+
+ +2111A112)
(X.. Vx., xz|12
2/²
?223
11
[JAx*(y+2)
-112
7
18

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
We next have by Young's inequality that for any 0 > 0:
1L
p(zz+1 Ze, u" Yc+1, zi) xi) 2
Zz+1 - ze11² - (xt,, - xxll?.
40
The inequality derived (65) directly implies
n1|lA1222
Ax Ax" (yc+1, 21)l
722 1x= u (x,, Y1+1, z:)l
The key global error bound given in Lemma A.12 originally proved in (Zhang & Luo, 2022) results
-6pBllx* (y++1, - x" (zx)]l²= 2 -6430² || (V1+1, - bll
Combining these estimates in (40) leads to
E
E[V++1> 2
( XTH AT x²+
T2211
+ 5 +
3p - 1
11
+
1
Bliz 2+111 -
27²02
873
28
40
2
TX2
311A|1BX2n
4||A|100522
2nl AlI - 10
Ellu" (x+, (xx, Ye+1, (+)1,2))
x111?
16
272
?22?
411
177
+
64337
E| (yex1, bll
(41)
2
2
We now estimate the coefficients inside the parantheses, with straightforward but tedious calculations which follow from the parameter settings.
First, we estimate the coefficient of El Z++1 112 in (41): Let μ 2 4Ly, we have 0₁ 2 because 04 p-Ls Then
letting Ç = 6 30 we have
3p 2 54 2
11
1 1
63
Ç
63
Therefore, we have that
11
3p
1
1
11
1
1
z
(42)
2/3
04
2
8
63
Hence, we estimate:
1
TX2 422
coefficient of Eliz, 2c+1 2
AT -
2T2
2
87
63
83'
n/' Let 7 2 2T 2B, S 40+ and μ max 4414,11 = 2LK = 2(4, +| + p), T S
and 7s = p - +7
10X
from Fact A.1. We have - Arp to and -2 112
then
100
112
11
1
coefficient of Elz, Ze+1
24,3
20
100
(n - L + X)2
By B < 1/30, we have 24,3
In addition, using T
<xx² < -/ we fanally obtain:
T06
30,3
(n-Tytxy
14
coefficient of El zet1ll
(43)
303
10
503
Then we estimate the coefficient of E|Ju" (x,, 24) X, 112 (41).
From above assumptions, we can easily get (M-L,)A o' T0 p-LT+
2 because À > 2 2. Moreover, we assume n/ S
p-L.+X
f 3 < T First, by our new notations, we have
TX2
3r/ X2
17 122
coefficient of (xi, ye+1, xx
1/
2p3
16
4-2
2-292
19

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
By 7 2 1 and the definition of Ya. we have
3n'
-3n/22,
X2
x2 (M- -y
Then
47
2
T22
21
coefficient of E B (x:, 24)
x1|12
3n/ X2
1//
122B.
16
(1r L, ))2
With S j S A, v
<
<
we can obtain -31/
3r
2
2
2
2
x
100
+
10
200
400
(p-
L,
A)
400
400
PSA
7/2
x
2u3
2
zx
Hence.
100
100
60
50
100
TA
3
TA2
TA2
TX2
7
coefficient E | (x,, Y141, zt) - Xx
1x,12>
(44)
16
100
400
400
100
400
Last, we estimate the coefficient of Ax| [1]Ax"(y<+1+> (yc+1, b in (41). By 6μ30² I and the definition yo.
Ya. we have
Fx
To
1 " (n- 1o-11--ii A)a
yF²
100 2 100
and -64,822 2 - Hence, we have
78
coefficient of E |Ax (y)41, b11² -
2 "
7
7
2
7
(45)
2 100
6
4
Plugging (43), (44) and (45) to (41), we finish the proof.
A.2. Proof of Theorem 3.1
Proof of Theorem 3.1. We start from the result in Lemma A.9. First, it follows from the definition of z that
||z - 2:+1ll = B1xx+ - zz|l-
So, rewrite (37),
EV. EV+1 2 PegElx zell² + (x (x11, - -x,)11 xx) c, (ye+1, - -bli2- 1
2r200 (46)
For > 0, we have V. 2 which proven in Lemma A.13. It then follows that
(EV; - EV411 = Vo EV S Vo f.
(47)
Then, summing up (46), using (47), and the fact that e, =
0(7), 88cg +(7) from (25), we have
Vo f6-f+ 1 22
zell² + Ellu" (xx, V,41,2)) xx1 Al (yc+1, 2.) bb|3]. CoT E|x;
for some explicit constant Cy-
Dividing both sides by T' rearranging and using the definition T
6XPVT gives
1
6A(Vo ff+ o²)
E x 2e + E| u² (Xx, V1+1, z.) x1112 + EllAAx (ye41, 2z)
-bll
(48)
CoVT
12
Since we have
VV( = pl - x²))))
20

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
by Danskin's theorem, deduce for any
1 [V(2))] = 22 (z(2l]
< Zt x" (yc+1, + || (yc+1, (2:)l
< Ze x" (yr+1, 2r)l + A| (y++1, - bll
< 22 x:1 + ||x: - x (y++ 2z) )| + /| (Y++1, Zt) - bll
K z x + ||x u (x, Yt+1, 2z + ō | (V441.2)) bl1
where the first inequality is by triangle inequality, the second by (A.12), the third by triangle inequality and the fourth by (58).
Next, we take square of both sides, take expectation, use Young's inequality, sum for all t 0, 1, ....., , and use (48) derive
1, divide by T
T-1
T 5
312 72 |xx- u Ye+1, 2011 Ax Zz) - bb12
B
E
3/ - x,
1 T
T
1=0 0
= 0
The result then follows since ta is selected uniformly random from 20.1,,..... 1}.
A.3. Proof of Corollary 3.2
Proof of Corollary 3.2. From the definition of x, we have
E G(x1, 2:) + -(x - xx) + +xx(
-x-
Let us set
Y(11, 2 xx) - -Ax -b) 11(x 22).
(49)
Combining with the optimality condition, we have
V E (Kt pA DA-(AS (Ax- -b) p(* - -z)) + xxx
= V + A yet1 + (x).
Hence, we need to estimate EE|AAx b|| and E||.
For the mini-batch gradient in the post- proceprocessing step, have
vx(x,y, 2) a²
Bl| 2)
(50)
B
which is a standard calculation, see for example, (Lan, 2020, Section 5.2.3). Since = 0(=
this gives us
E ((( VK(x,y, 2
< e²
(51)
First, let us note that the purpose of & is to estimate u² (Xr, Yt+1, Zz), where
u" (Xe, 2c) arg min (I(u) = Y1+1, 2,) A
1 [|| - 3
Note that the gradient of this objective is
Vi(u) = VxK( X(x - xx).
21

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Lincar Incquality Constraints
As result, have VI(x,) V (x1,11)))
Let us also denote
x = projx (x+ (V((x.).
That is, x is the output doing a full-gradient step on X₁. Of course, this is not tractable in our setting, but we only use this as a theoretical tool.
Vc+1; Since this is GD step the objective which is Lg-smooth and convex with optimizer u² u² (x411 2,), the standard
analysis for GD gives
|x[] u (x,, 2:]l < ||x: u
(52)
as long as T S 1
Ixx"
Next, by the definitions of x and x, along with nonexpansiveness of the projection, we have
E|x x|| s EE,1IG((x, YC1,,
2))l
<TEEP
(53)
where the second inequality used (51). In view of (49), estimate ||v|| as
2 ||v|| S V K (Xe, 2.) G(Xe, Y141, + Lx||x, x1+ + xell + -|| bll + + z:11-
On this, multiple applications of triangle inequality give
X X
S
x
+ ||x] - (Xi, Nx41, (X., 2,) xx
+ 2 2|| (x4, xx) xell.
(54)
where the second line is due to (52).
For the feasibility, we have by triangle inequality that
|| zell S
| xill + ||x - 21
(55)
As result, have that
|| 011 - x;1 ||x: - n2 ux Vx11, 2:)1 + ||Ad bll 1|x: 2,
+ (X), G(x,, Ne+1, 2))
(56)
For the feasibility, have
| - bll < ||AR - Ax + ||Ax, bll < |||||| x+Il + ||Ax; - blI.
Now, by invoking the above inequality for t", taking expectation, using Young's inequality, (54), (53) and (48) along with (66), we get that
E|| b|| < 5²
(57)
since = 4).
Finally, using = t", taking square and then expectation of (56), using Young's incquality and then combining (57), (53). (51) and (48) gives the result since T 2(a=1)
22

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
A.4. Auxiliary Results
Lemma A.10, Under Assumption I.I. any x, 2, z' E X, we have
xx u (x, 2) 2 ||x x (y, z)1-
(58)
|| (x, 2) - xI| S ||x x (y,
(59)
||||
I yx 2) - -u'(xx (xx,',2)1 v
|yy - -y'l.
(60)
Ju (x. - u yx,y, z1)|| - 11 %
z - z z'11,
(61)
را ||x (y,z') - -x" sy. z)|l,
1|z z|| >
(62)
Il' -yll 2
NK
xx (y', .)) - -x'(y,2))
(63)
xx* (2) - (2)')]1 -
|| 1/11,
(64)
/ Ls
(u-L,)A where = a- 7s= 1 Laf + X, 7K T.g.
Proof. The proofs for (62), (63), and (64) appear in (Zhang & Luo, 2022), omit these proofs.
We first prove (58). Let us note that x (y, z) minimizes P1/2, see for example (Hiriart-Urruty & Lemarechal, 1993, Theorem XV4.1.7). As a result, we have VxP1/A(x* (y. = 0. From Lemma A.3, we have that 11/A(1; V, 2) is
(/- + strongly convex.
Then, by strong convexity, we have
V Xx (x (x,,) x) 2 7/|x- x' 221
V XxXI/A(X.y,, 2||| 2 7/| x - x z)1,,
where the inclusion used
(y. 2). = 0 established in the previous paragraph as well as Cauchy- Schwarz inequality. Then, using VxP11/XXx, v, = X(x - yx,,,,, we obtain (58).
From definition of u² (x, z),, we have,
K(u" y, 2), z) + (x,, < K(x 2), 2) 2 ||x x" 2)13,
where we also remark that x" (y, 2) X. Combining with K ((x* (y, y. z) K(u (x,y y), (x) the definition of x x"(y, 2) we have (59).
which follows from
The proof' of the other two assertions will use a similar idea to (Zhang & Luo, 2022), but there will be differences in the estimations since this previous work did not use the function /i/AA
For (60), we proceed by using the definition of 1//1 and adding and subtracting K(u" (x,y', 2), y, z) to get
y, 2) + uu 2, - x||² - K(u'(x, y(x
[x,' 2) - -x12
2
= =x(
||u" (x. y.z) - -x12
2
- (xu'(x, y' z)) 2
1z)- ull"(x,x' ,2z - -x1
+ K(u' y' 2), K(u'(x (x,y', ,),, 22)
-T "u u'(x,y', 2) + (y (x, 2) - -b),
23

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
where last step uses r 2,, A I|u x|I being 7 -tStonnyyly convex (cf. Fact A.1) with minimizer u* (x, y, z). as well as the definition of K.
We then argue similarly, this time adding and subtracting K(u" (x. y: y'.)),
yx) 2) + u yx, - x12² (xu"(x, y'. 2) "llu((x,, (x, 2) xx1?
X |u" (x, v,z) x|2
=x(u"(x, 2), z)
K(u'(x,y',
|u" (x: y', -x1²
K(u'(x.y,z),,' 2) K(u (x,y, y.
2 Ts Il' u' (x,y', 2) (y - -y', Au (x, - b). 2
where last step uses that u u K(u,y' y' 2) + 2 I|u x|| is % strongly convex (cf. Fact A.1) with minimizer u ux(x, y'; z) and the definition of K.
Combining the last two estimates give
(y y-y's y', Au Ax"(x, yx, Au" yx,,))))) (xl y. u² u"(xx''''''' ,',
Using Sechh-SSchwarz inequality and the definition of operator norm gives (60).
The proof of (61) is similar to the proof of (60). just completed. In particull,, by adding and subtracting K yx, z), z'), we have
> |x,(xxy,,) - x|I² K(u' ((x)(x.y,2)) + |u yx) xx12
K(u"(x,y,2),,
X 2
= =(uu'xx,y, (x, x K(',,
[x,,"xx,,,2)) xx12
((uu(xx,,,22,,.2)) K (x. 22yz)),. y'),
S - (=x,)
u² (x,
(1|u (x, z||2 1ppp-llu"xxx00 yx, zz(12),
where we used that u + K y, y 2) + u - x| 2 is %s strongly convex with minimizer u" y, z) and the definition of K.
Finally, we add and subtract K(n" (x, 22), y, 2) to get
>
(xx(xx,,,),,,,,)) + 2 ||u x 2) x K(u'
2 | |x'( (x. y, - x||²
=K(u'(x,,,2,,,22)) + u (x, -
マ | (x, y,z) x|12
+ -
K(
2 2 ll ( u'(x,,,
2| || [ (x, - 2| ll'' v,z 2²112),
where we used that + K (uu, y. z') +
is 7o -trongly convex with minimizer u" (x, y222) and the definition of
K.
Combining the last two inequalities give
( (x, z') u uxx,,,,2) z) 2 7//l (x,,,) u yx, z2)
Using Cauchy-Schwand inequality concludes the proof.
24

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Lemma A.11. Under Assumption f.r, Xx. Mt+1, Ze generated by Algorithm I, we have
||
||Ax, Ax (ye+1, 2))1 v
||x; u² Y1t1,
(65)
722
A| ||
||x: -bll
||x - u (xt, (x,, N141, z.)ll + 2| 10)-1,2() -bl??
(66)
72
|||
Al (xx, Yo, (s, Axell
Ilye yc-1ll (/ -xill?
(67)
7/
where Yo are defined in (25).
Proof. The assertion in (65) follows directly from (58) since
|||12>2
|| Ax: Ax" (y 2:]1 s ||A|||| x (yc+1, 211
- (x,
72
Combining the first assertion with Young's inequality gives the second assertion, since
||Ax, b1l2 < Ax,
Ax (y2+1, + A1| (y 2,) bll2
2
72 -|x
+ (xx.
- -b12.
Young's inequality and (60) gives the third assertion
[xxx Vc, Axell
(xxe: Ves
Au - Nx-1 ( Ax,1'
|||
- 2 - ( (xx, -x:1
The proof is completed.
The following important lemma is known as the global error bound in (Zhang & Luo, 2022). This global result holds in its entirety in our case, so we only state it here and refer to where appeared originally for the precise definition of the constant which depends on Hoffmmn constant of certain linear systems.
Lemma A.12. (Zhang & Luo, 2022, Lemma 3.2) If μ > I.g, then we have
(y) x (z) S / Ax (y, 2) - -bll for any y,z,
where ā > O depends only on the constants C1 = (Lf + p A 1 + n1) C2 = -Lg + n. and the matrices A, H and is always finite.
Lemma A.13. If (x, E X x X, we have (1//1 - 2d(y, 2) + 22) 2 f.
Proof. Because x" (y,z) minimizes p1/n (., z)) (see for example (Hiriart-Urruty & Lemarechal, 1993, Theorem XV4.1.7).
we have
(1/x (x/21x z). = K(x" (),,).
We can then deduce
(I)/ - 2d(y. 24)(2)) K(xx(y,z).y..2 2d(y, z) + (z)
= d(y,z) 2d(yy + (z)
V(zz) + (2) (11))
> (zz))
2 f
25

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
The second inequality in the above chain comes from definition, that is, denoting x arg anggiingxx.Ax=bl((1 + z||2} in view of (7), have
d(y, 2) min ((x, xeX
+ f(x))) + 11 11xx; -2|²= (Z)
where the first inequality also uses x E X, which is by definition.
B. Proofs for Section 4
Notation. In this section, we have [V {x)
fx(iill S o² and B|Agx; - -b,,112 < L, then denote the boundedness of variance as G Yr, Ze, Ex) Kx,, Yr, 2,)12 S oz. where the boundedness is proved in B.2.
We start with some helper lemmas before proving Theorem 4.3.
Lemma B.I. Let Assumption 4.1 hold. With the update rule of Yt41 = Yt + ((c, - bba) where Ec, BcclAc,x - -bal
Ax, b, we have
n² BB|
b112 (1 17[1A|1*)
) n
Ed(y 2041) - Ed(y..22) 2 1) b), Ax" Ax (1)41,
b)
32
2Tk
1/ E(24+1 21, Z1+1 Zz
2xx 2y++1 Z1+1))
(68)
(V - (2.) S pl 21 24 x (z+))
P Elz Zt+ 11?
20.
where ,K, da are introduceed in 10, and by Assumption 4.1, we have A bb. 112 S L for some finite L.
Proof. It is easy to derive, for example as (Zhang & Luo, 2020, Lemma 3.2), that
2(11)1.2(+1) - d(yr, 2:) 2 (Ve+1 Ve, Ax" (1)+1,2))) - b) - P
((11-1 Ze, Zc+1 + 2x (yc+1,
2
Hence, by using the update rule of Y(+1, we get
d(ye+1, Z++1) d(yc, 21) 2 (ye+1 -y, Ax Ax"(x,x,z))
(e) - b) + (ye+1 Yr, Ax 2x)+1,))))) Ax Ay,,
+ (21+1 Zz Zt+1 +z 22x" (y z(+1))
2 (y++1 - yr, Ax (y', 21) (0)bb) b) - =111++1 - -vrll 1=12-=11Axx"
Ax (y:, 211
2
" (2111 21, Z1+1 + zz - 2x" (y++1, Z(+1)}
+ 2
||A411 2 (n(Ac.x. b;.), Ax (y,, b) "" L2
|1ye41 yoll
27
(z141 Z1+1 z 2x (y++1, Z(+1))
where we use Cauchy-Schwarz inequality the second step, and the last inequality comes from the bound of TEJ|A xx 1g.11 also (63).
After taking expectation and using tower property along with ye, z, being deterministic under the conditioning, we have
1 2"
|||| E ye+1
Ed(y 2411) Ed(yy, E(mr(Ax, b), Ax" (yt, -b)
2
11
E(z++1
2,+1
Ze+1 + zz 2x(yx+112(41))
2
26

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Then we estimate as
1
|||||*
- b) ((n( b), (y),
2
Ellyc+1 yull
2
27/x
||A||4
2n) b), Ax Ax - b)
11 1/²1?
2
27
1
|||]|
=n Ax (v - -b) + m(((Ax -b), -xx +
Ax Ay 2e)1
+
n²²2²
2
27
2n/ b), Ax (y++1, 21) - b) - (y - Ax (y,, (0,,,))1111 11²
||
Ax
b112
17²1.
32
2
112
A||
[ b), Ax Ax'x'xx(x4 (y++1, m4) - b) Bl
Ax bll²
2 2 - 27
1
32
where the first inequality comes from B1 - ,ę, 199 s L and the second inequality comes from (a, S 12 + (va,, b). And in last inequality we use (63) again.
The estimation of (V 1) (z,) is the same as Lemma A.8. Because the randomness of C. in the stochastic dual update does not change the recursion EV (Z)-1) - (2,), where 21, Zt+1 only depend on the randomness before Çe- Hence we omit the proof here.
This completes the proof.
Lemma B.2. Let Assumption 1.1 and 4.1 hold. By using the parameters (25) in Algorithm 2, then in the iteration t + 1, if the dual update runs as Y1+1 = Yy + n(A,, Xt - bb,). , we obtain
EV,- - 1V 2 22441 - 2r11 + +T,BBllu (x,,
x. +2 (y-r1, bbl
- - (1+ 17|| I2
(69)
22
where C3
# 503'
C,
6r T, and E G 24, E.) V xx. soz
Proof. First, we show y1, Jx, bounded.
Recall that in Equation (17) we have
V AT (A boz) + p((x 2).
(70)
We estimate by using Young's inequalities
El]G(x,, y,, &t) V Kx,, xx,
< 2E) yr, 24 G(xx, 0, Ex) 2E| Zr, E.) VxK(X,,
< H 1 2 0, 21, {x) V (x,, Vt: (t, 2:)11
< 2ELolly; + G(x,, 0, O, 2,, Ex) V 0, 222 + 4E V (x,, 0, 21)
(x 2;)1
< 2L + GE O, Ex) VxK(X, 0, z, )l + 4| |
where in second inequality we use Lo is the Lipschitz constant of G with respect to variable y, then in third inequality we use M, as the upper bound of ||y/|l-
TxKK., yc. is bounded, we denote the upper bound as og. Note that Corollary A.7 still holds for xt, Yt. Ze, X141. Zt41, but the variance is changed to d2 (since this corollary
Because X Yt, Ze are all bounded, E||G(xx,,,, E.)
27

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
and the lemmas used in its proof do not use the partieular form of yc+1). Then combining with Lemma B.I, we have
[V - V = E [PL/A Yt, 2:) - (x Vt+1, 2++1) + 2d(y++1, (011) 2d((y; 24) + 2V (2:) 2 2V+2))
?
ATR
+ +XT² + x22
Bliz -2++1 20+1112 Ar²a3 8
2
(x:. Ze) - -xe11=
16
2
2
(Ax b. Au" (xt. 2t)
b) + "
EE(1111 - 24 2u L Nt+1, 2z) - 2x - 2
2
+ (Ax - Ax (yc+1,
- -b) + +1 - Ze, 21+1 + - 2x (y++1, Z(+1)}
2μB(zz+1 Zz, 2t - x (ze))
P EEllz Ze+1 111
E| Ax - b112
1 + 27
|7
n"² L2,
04
32
where 3/2 EI - blb² - (5
1
L2 is the difference comparing to the deterministic linear constraints result in
1f L2
2
Lemma A.9. We then estimate like Lemma A.9 to have
EV, EV4+ 2 cgs
M++1 2, c- BBlll
A 1 (xt, Yet1, 2c)
xe11²
co C,T Ax (y++1, 24) - -b12- 2r200 02
1
2
1
R|
Ax; - b1l
1f 1
(71)
16
where cg
503
#
Go
2= 400
c= = --
We also have by Young's 's inequality and Lemma A. that
|| 12
1/² E Ax 24) - -bll2- 2:)1
16
R Ax
-b|2
-
2
8/2
E|x, x - u (xx,
Nr+1, (x1,,
8
By the parameter choices, we have 7 proof.
,
G
and
Using these estimations in (71) gives the
400
87
400
Proposition B.3. Under Assumption 4. 1, llyell flIAx soc-bblt bbl2) and r > O is defined as | bl this is guaranteed by our assumption.
I
(zz)) ( ((y))ddyy,,))-1)) 222M where M m x + + z/|2 +
I
r where x is in the relative interior of the constraints. The existence of
Proof. Given X, we have
(z.) - d(y:; 21) 1(X" (2.)) + /
1 (ze)
2² y1, 2x)
1(x (x)( + H
21 [](x) + (yr,, AX) + P |x (zi)
(zx)
AA b112
1 - 1
2
2
[[(X'
(z+) [(x((x)))
+ 1
2 f(x
11 | 21|3]
(yr, Ax - b) _11Axx - bbl2
2
[f(X' (z)) + 14
11 | 2112
P |AAX - -b12
|X (z)) - 2: f(x)
(ye. - b))
2
2
2
> 2M - (y,, - b),
where the first inequality comes from the definition of (z.) and
d(yr,z)) min x(x,
xEX
Finally, in the last inequality, we let
1 [1)(x)) + - [|x =z12 + f111Ax [b13).
M
max (x x
As result, we have the last inequality.
28

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
According Assumption 4. 42), there exists positive r > such that for any direction d E Range we can find X satisfying || bl| = and Ax b has the same direction d. Because yr E Range A) (by assumption 4. (3), [ange(A) = ") we can choose x such that Ax b is of the same direction -y, and || b|l = Then we obtain
(Zz)) d(y,, 22) 2M
(z+) d(yi, 2,) 2M + r yell = lyall =
vt {0, 1, .... T7.
r
This concludes the proof.
Proof of Theorem 4.3
Proof of Theorem 4.3. First, let Mv = maxx, ZE (x, 2d(0,z) 22) and My is uniform lower bound of V (z+), for example, f.
My M2+ where My
Here, We denote the x, z generated by Algorithm 2 at iteration & as xx, Yr. z and the output of iteration L ++ 1 as X Z2+11
I + n(A,xx - bz,) I1 S My. then
E V X,, V1, z,)= V(x++1, Ze41)]
C El 2,+1
z:11²
2,Bl (x,. -x,l2+ 22,EE1 (1141,2)) bbl2
1 17 r121.
2 XT 0z
K
(72)
2:112 + TBBll 1 (x:: + A,,, - b;, (.), 2z) -x- -x.12
(1
17|| 7
+ + (y: + (Ac,x bz.), b11² X 2
n2=L2
where the first inequality use Lemma B.2 and the equality comes from the update of y++1 when |yy: + + (1tt7/(AA4 xx - S My.
If lly, xA,,,x bz. )l > My we have Y1+1 O. Let us use ýc+1; & 2,41 denote the iteration generated with
841 = t + (A,,x bz.). Then
1154+11$441., 20+1) - (11,++1,2141) + 24 (2(+1) 2 10 (2 -
2(41) + (2(+1)
rllše+1l1 - 2M + My
M, - 2M + My
Mv
[K (x, 0, 2d((02) + (Z((Z)) x,2EX
K (xL+1, 0, - 2d(( 2141) + 2 22 (z(+1)
K (X141, Ze+1) (c(y)41,Z2+1) + 22 (Z(+1),
where the first step used d(f241, S K (($411,.441 2(41) and the second line uses Prop. B.3 and V ((++1) 2 My.
Hence have
EV Ye, 24) - (x++1.
KK (Xt, Nc, 21) 2d(y,, 2z) + (2:)) E [K (x<+111 yt+1, 2+41, - 2d(y++1+ Z141) + 24 (z.+1)
2 E K (xe, yc, 21) 2d(y 2)) + (2:)z
(K(((++1 P2+1, 2041) 2d(5 2(41) 24 (2.+1))
2 ألامةة 2:+1 - 11 + 2, EE| u² (xt,, S1411 2r) - xx 21? + 11 Axx+1l1 Ze) - -b12
XT2 - (1+ |7
1,212
7
= =7 2211
2011 + 2,, El u² (x(, + m1(AA X, - be())2) - x.112 + + (y) bz.). - -bll
1 - 1
(1+ 17||_||(
12²
(73)
7
29

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
where in last inequality, we use Lemma B.2, and in the last equality the fact that 2c+1 Z2 3(x; 2z) 21 Y++1 = Yt + (,,A,, X b.,)-
Combining (72) and (73), we have that
E [V, V++1]
x11l+ &,, (ye + m(A,x, b..). bl12 2 c 2,41 +,,12+ (x,, TA,, b..),.)) +
A7 - (1 17
1
2 7
holds for both lly: + [A,, - ba))l )I S My and lly: + (A,, - b;))l > My which means it holds for X Vt+1, Ze+1 generated by Algorithm 2. Then we can telescope as before and the convergence result follows.
We also now sketch the argument for the complexity. We have for the gradient of the Moreau envelope that
V (z,)l
2z x (z:)ll
2t x" (y: + (AG, x; - bc),, (yx n(A,, bz,) 2x) X (2+)
82 x" (y: + (A x, - -b.)) 22)l -x| (y: + 7 Aq - b ) 2,) bl
12 xiIl + ||x x'yr, -n(A,, - bq.) 21 + ø || (y: + 7A -b.)). Zi) - bll
2 x,| || + X - u'(xx"nn (x,, + (, b²,) 21 + o| Ax (y: + (,c, b;,), 2z) b|1,
where the second line by triangle inequality, the second inequality is by Lemma A. 121 and the fourth line by triangle inequality and the last estimation is by (58).
The rest of the proof for the complexity result proceeds the same as Appendix A.2 up to simple changes in the constants, and hence is omitted.
C. Proofs for Section 5
Notation.
Let us note that we define by Rgg the expectation conditioned on all the randomness before &
C.1. Proofs for Theorem 5.3
First, with the idea of the STORM estimator of Cutkosky & Orabona (2019), we have the following lemma to control the variance of the stochastic gradient.
Lemma C.1. (from (Cutkosky& & Orabona, 2019)) Let Assumption 5.2 hold. We have the estimation of the variance as:
B V[(xx)) s (1 (1--a) (1-a))B/ ( + 13) + x:|1 + 3a²
Proof. By the definition of fit1 in Alg. have
Se vs(x++1)
Vf(x(+i(041) + (1 (1-a)((f - vf(xx,(++)) -f()))))))((( f((++))
+1 (1-a) (((x(+1)4+1) +
vf(x;)) (1 - (11a))(f(x)), (f(xe,)(+1)) vx(x411)
(1- =(1-a) V (x:)))
o) - E(+1)))++1)) (((x)+1, ( V/(x+))) (74)
where in the second equality, added and subtracted (1 a) (xx))...
Then, we compute the squared norm of (74) and expand to get
Í fit vf(x++1)11
= (1 -(1o))
// V/( - (x((+1))]
+ -10/111)
VV/x)) (x(+1)))
30

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Next, we take expectation with respect the randomness of ει+1
obtain
E ( V a)) | ([(x)))
+ RRet |1(1 (V(V)(x - (((x), ( v[(x++)) (75)
which is due to Vf (x,) being independent of 1++1. as well as
E [xx)) ((+x))
Be (V((x+1) [/(x))) =0
Finally, we estimate the last term on the right-hand side of (75):
Eee [1(1 - a)) (xx,)) + faf////) V
= =Beeti [V((x(+1 - Vf(x, (1+1) - Vf(x++)) +
< 3E4 [
V (x, 1ll + - Vf(x+1)] G() -/f
I 3 xpl12
3L ||x X 2| oa²0?
where the first equality, we rearrange the terms, and in the first inequality, we use Young's ' inequality. In the second inequality, we use Assumption 5.2, -ysmoohhsssss of f(x) and (x( V S o². We use this estimation in (75) and take total expectation get the result.
Let us recall from (18) that
1
V, K Yt, 22d(y,, 2:) +2) + 48( 1.2)T
|4 VS(x.)]
(76)
where (as (22))
# 2(x = (x, y) + マタ ||| 2|1
(77)
and x VK(x,y,)) is LK- -ipLishciitz with LK Ly + |||A|| + μ (see also Fact A.1).
We already have the descent-type lemma of d(y,, z;) and (z,) in Lemma A.8, and only need to show the descent-type
lemma of K (X,, Yr, Z:). We write K (X,, Nr, k.) K (X++1, Yt+1, Z:+1) as:
[K (X:: 1t+1, zr) K (x 2e)] + [K (x,, Yr, ze) K (xt, Yo+1, 2:)l + [K (X141,
and lower bound each term separately in the following lemmas.
Lemma C.2. Let Assumption 1.1 hold. For the iterates generated by Algorithm 3, we have
1 Lx
N(x1,1 2.) K K(x,, Y1+1, [V](xx) &.111
|
x1
2T
2
Proof. We have, by smoothness of K(:, ((+11,+1,24 Z:):
K(x+11, z S K(X, + (Vx.(xx..+111)))) xx) + Lx
X xx1122
(78)
We estimate the inner product here as
(xx, Xr)1 xx) (111) xx)
+ (V (1t1, -x)).
(79)
We first have, in view of Alg. 3 that
VxK( (4) Vsc.
The definition of X in Alg. 3 gives
(x++1 - X; + N(41,
V(41, Zi), - x(41) 20
(GIx). - -x,) S - X - |
-2 (80)
31

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Lincar Incquality Constraints
Using (V* (x41 ((11; x1) S [((+)( (79); we have
Sell + 27 +||x+11 xzll² along with (80) in
Z,), -x) - 2 [Vxx)) fall
1
| - xel1?
2T
Then the result follows after substituting the last estimate in (78).
Lemma C.3. Let Assumption 1.1 hold. For the iterates generated by Algorithm 3, we have
K(x,. z1) 51-. 2 - -x1 - -b12 +
11
3/
1c+1 - zel1
8
4
(81)
T Vf(x)) - fell
+
LK
11) ||x++1 - -xil?
2T
2
Proof. First, from the definition of in (22), we have
K(,.,),, K(1,, = -1/1 -bll?
Moreover, follows that
K (x(+1: Ve+11, Zi) K V1 2(-1)
11
(||x+11 - -2.12 - ||xet11 Z 113
2
(2++1 2,, 2x,+1 - Zz - -z++1
2
(21+1
2x,+1 - 2x, 2x; 22. 22 22+1)
2
(2+11
Ze, 2x,+1 - 2xx)) + H
(z++1
2z, 2x: -2zz)
|1+1 1 ||
2
1++1 z 2 11|x x+11 2 + /// $112 22+1l12
11
||zt11 2, 11?
2
where the first equality comes from the definition of K. the last inequality, we use (a, b) 2 -llla|12 - ||b| and
Xt. M+4 by the definition of 2 in Algorithm 3.
Fanally combining the above two results with Lemma C.2 and combining like-terms yields the claim.
We next follow with a detailed restatement of Lemma 5.3 and its proof.
Lemma C.4 (cf. Lemma 5.3). Under Assumption 1.1 and Assumption 5.2, with the parameters chosen as:
1 = (2,4x2,
TS min
8T. + 161
/48(L L3))
(μr - 2T
2μ + |||A||
7(2 + 21)
17 min
(82)
8||
A||A|| 220|||A122'
2011
B min
100' 50 36μr²
48 + 17)7²,
where LK- = Ly + |||A||| + μ. ō is defined in Lemma A.12, we have
1 E|xx: - x + " Ax (y--1, 2:) -bll + T TBI vf(x,)11
EV.- EV.+1 2
Bliz: - 2 +
Ax
2,3
87
(83)
- -144(L3 + 137)02
32

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Proof. We denote
V K (x yt,
2d((y;; 24) (z+))
(84)
Joining (81) with Lemma A.8 (since this lemma only uses the update rules of y++1, 2++1 that is common in Alg. and Alg. 3), we have
EV; EV 2 Ax, - b112 + (#
34
E|
Z - -2112
[ fell +
LK
)
2 -1 x++1 -x1l2
27
+ Ax - b, Ax (y k1)
- b) + 1B((z+11 - b1 2+41 + 22 - 2x 2x" (Y141,
2/lE(Zz+11 - Zz, 2z - x (2,)
- - Billz 21+1l1
(85)
First, let us combine the first and fifth terms on the right-hand side to obtain
Ax - - 2mx b, Ax (y.xx"(y+++.2 (yc+1. 2x) b) Ax Ax Ax" (y1+1, 2:11 + (v)+1,))) - bll2. (86)
Next, we combine the sixth and seventh terms on the right-hand side of (85) to get
p(z141 - 2,, 31++1 + 2x (Y1+1, 2c+1)) 2p 22, 2x x((2))
= =1(z++1 Z1, 21+1
2x (y Z1+1) 2x 2
=Allzt+1 zel| 2 24(2z+1 Zz x (y 1(+1) x xxx((x) (zi)).
(87)
We now single out the inner product in the last equality and estimate it by adding and subtracting x" (y1+1, Zi) in the second argument of the inner product:
24(22 2e, xx" (xx=((++,+00 Be+1 + x (2x))
24/22+11 2z, x (Y + x" (y(+), 2.)) + 2p(zz+1 Zz, -x" -X"(++11, 2+) + +x" x²(2))
1 - |1 - -zel? [[||x"(0 (z,) x" (x)41, (88)
2 -Mllze+1 - 2z - x - x (Y++1,
for any Ç, where we used Young's inequality twice. Then, we plug this into (87) obtain
pl Zt, Ze+11 + 2z 2xx (94+1,Z(41). 2p(z141 Zt, Ze x (2.))
2
1
2++1 1111
|1++1 2 1 (z)) x (y++1, 2:)
(89)
where we use (62) to bound the second term the right-hand side of (88), with da being (25).
Then we use (86) and (89) in (85) to obtain
EV-
EV++1 2
11
3p
E
21++ - 11 [E]V - fAIl2 +
1
LK
11
R x1+1 x,|13
3
4
2
2r
2
IAx - Ax (y 21)11 + 7B A - -bll2
/1
El El|ze+11 =1
EE|lzz41 - z 12 - (zz)) - x (y(+1,
P Ellze++1 - 2
0
04
2
14
3/
p
1
El|zz+1 - 21
3
4
03
5
04
2ml 20l1|A|1 [((()((x)) - Sall
T
B (xx:) - -/1111
2
(n
T25)²
1 LK
2
2 4
n||lA12 11111AA112 72( L,)2
E
El|x1+1 - 1
2T
+ (11 - ((6z)) |1|AAx (yc+1, 2,) - bbl?
(90)
33

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
where in the last inequality, Lem. C.6 and Lem. A.12, then combine the like-terms.
Then we need to estimate the coefficients of each terms in the above inequality. Let recall from (25) that 04 1 and let ( 6,3.
We now estimate the coefficient of Bl Zi+1ll² 2 in (90). First, by 04
2.2 we have S 4u and & 4
S 2u. By also using
og
< = 63, we have:
The coefficient of [2| z; Z++1 1|2
34
4/1
1
2μ.
3 4
63
Using 3 $ 1/50, we obtain ( ++4+2)p 5. then we estimate:
The coefficient of Bi|z; - Ze+1l 11 2
/
p
3
53
63
2
We move on to estimating the coefficient of - X - 1|2
in (90). With
S
(n- 2y
||
we have 2n|1 Tip-Lop > S If
we have:
1
LK
The coefficient of E X x
4T
2
Last, we work on the coefficient of E| Ax" (y++1, 2,) - b/l2 in (90). Because Ç = 63, it follows that 1j - -K60 = -7--6111 16,1888
With
7 36pa we have 6u30r² S
g. 6
then we estimate:
the coefficient of Ex| [E]lAxx(yx))) (y++1, 22) - b1|² 2 1l
1
6 2
Next, we estimate the coefficient of ((()) have
f. With 17 S
(n-L,)
have
2y 1412 (m-L,)² - - Finally,
8||l[
EV--
EV-1
2
1 Eliz 12+1112
+
LK
1 El X - x 2 " EI (y++1,
(0)+1,,))-b/] -b]l² Ax E [ - &/1l
3T
23
4r
μ Eliz 21+1/12
1
LK -1 11 Bl|x - x++1l12 Ax 2 -b|1
23
47
+ f(V
- 4
fell
- (xxx - fall..
Then recalling Lemma C.1 and assuming 0 a S 1, we have
E1 V [ < a a) v/(xx)) + -x (91)
We multiply (91) by I, rearrange, and plug into (91), to get
EV. EV+1
1 2,3
Eliz,
Ze+ 1
1
LK
11 |E|x - 11
4T
" Ax "E Ax 21)
-112
E V fxx:) - 6.2111
- v f(+1 [ 12
I E E vx((x))11
3 3(13 + LŽ}TT
Elix, X 200
(92)
Because a 48(13 127772 and < min
we obtain
3LL++164' V48(13+13))
LK
1
3(13
123)T
+
2
16T'
167
34

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Hence, we have
EV; - EV++
11
E E2 Zi+1 112
Ex
E
" -21E [[ (y)+1,2)) - bl1 + f(x))())) f. x 112 +
28
8T
48( 0 + 1.3)T f++1
48(L)) + 12z)T E 5 (x(()) 1 144(L3 + L3)
Finally, move 18(2)+11)+ E V f141
fx(+++1)||=
, |8|l V - Vx(())) || the left-hand side of the above
inequality and use the definition of V in (18) to get the desired result.
C.2. Proofs for Theorem 5.4
First, we need two lemmas for the error bound that helps us analyze the sample complexity that we include for being self-contained.
Lemma C.5. (Zhang & Luo, 2020, Lemma 3.10) Under Assumption 1.1, we have
- - (x VVK(XX =(p +
T(u- - T.f))
||x x xy),
2
where (x. =
|| )
2 and x (y, z) = arg min x K ((x, V.
Proof. First, we denote that x = projx (x V 2)), then by the definition x"x (y, z), we have
(x x x' (y, (y,2),,, 2 0,
where we use the fact that & X.
Then by the definition of projection (that is, ă = (2) = (a- 1-22t 2) 2 240 E X), the definition of &, and x" (y, z) E X, we have
(y, proj -VK( //t -xojxxx--VVXX yV
(y, - (x (x), V +x)= S 0.
Combining above two inequalities and rearranging terms, we have
(x - x
< (8, (x--7//1.s))1-77kkkr/a22)33121-1
- ||
< |Btl://4fk...1111777777xxx733100
z)
[x[[[T] 1) x))
|||||||- (y, 1|
where in the second inequality we use the Cauchy-Schwarz incquality and in the last inequality we use the Lipschitz continuity of VK with respect to x.
By K(x,x y, 2) being (μ+ - Stt-onyyy convex with respect to x (see Fact 1), we have
(x x z), VVK(x, ~VK (y, z), z)) 2 T(μ xx))lxxxx(x,x> (y,
Then, the desired result follows by combining the above two inequalities and using the definition of x = x - xpproxx(x y,
With the next lemma, we proceed to prove that ||x; - x" (y++1, | is bounded by a combination of ||x, - -x++1| and | (x(x))..
Lemma C.6. Under Assumption 1.1, for the iterates generated by Algorithm 3 we have
2
Ix: - x" (y S 7(p L,)
1xx x+till + (u Lu) |4
vf(x,)ll
35

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Proof. Taking x,y, as X ye+1,2, 2e in Lemma C.5, we have
2
|x - xyc+1, T(u Ls)
TVK(X, YCH1. Xx -rooo (x, -
2
Xx -proix (xi Yr-1
7(u- Li)
2
|| (x; (X, Nc+1, z,)) (x 2,))l
T(p - L1)
2
2
|x| x1+1ll + (x- | ff(xx))l.
T(p Ls)
where the second inequality comes form triangle inequality and the last inequality comes from the fact that projx is nonexpansive and (Xe, 2t) G(xe, Yx41, Vx(xx) - Vf..
We now continue with the proof of Theorem 5.4.
Proof of Theorem 5.4. Because Ze+1 Z4 = [xx zt), 22 -(T) and 2 =((r) in view of Lemma C.4, hence there
exists constant C such that we get from (83):
EV;- EV++1 2 (T 2 +|| (x: -xxxx+4)ll xx+1)ll Ax (y++1. - bll + (xx, - ffal
- 144 (L] + L3)) 0273.
(93)
Then, summing up (93) over 0, 1, ...., we have
T-1
Vo VV 2
Σ CT 2012+ E+I xx+1)12 (y - bbl² + +E(()( ffll
- 144 (L) + 13) TT.
(94)
From the definition, we have K (xx, y.z) 2 d(y, z) (since d(y,z) z) mmixxex x K(x, y, 2)) and (z) d(y, z) (see also
Lemma A.13), then
V. V.= K(x,, 2d(y,, 2,) + 2V(22,) 2 v((z)) 2
Consequently, we have
V ((xi.)1,2.)) 2d(y,, 2.) (2.) + 48(L3 + 12)T E E St (/xx)))
(95)
Let r = 1/33 and use mini-batch in the initial step where we will have EE v (xxo)l ST-1/3 0² (by the definition of fo and standard computation), then
1
Vo- = K(xo, No. zo) - 20) +2 +
E V vf(x))1
48(L3 + L3)
(96)
a²
< K(Xo, No. 20) - 2d(yo. 2o) + (2) +
48(L3 + -3)
where the right-hand is proportional to constant indeeeedent of T, denote it Co- Combining (94) with (95) and (96), we have
T
C x, 11 + E||T (x. x(11)11 Ax - -b1l +EI &
(97)
<T 2/3 (Co - 1 12)00))
36

---

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Incquality Constraints
Then, for index selected uniformly random from 10,1,-.. 1}. we have
X = O B
- xs+1)12 O(T-2/3),
(98)
E Ax (ys+1, bll² 0(T EIIVS(()) = O
According to Algorithm 3, have
Xs+1 mig (G(xs) 2e), x') + x, +01x(2))
By the definition of Xs+1, we have
2 0 E G(xx. + (x,+1 x.) + +Ix (xs+1).
(99)
We now
== (x((x++1 G(xxs),+41/ 2 -x)+ x,) xx,)
PA (Ax,+1 -A) b)
-1(xx++ =e).
Now, by using the definition of K (xx, y, z) from (19) and (99), obtain (cf. (5))
v Vf(x++1) + A
y--1 A
0Ix
We now derive the guarantees on the feasibility and the norm of v. First, by triangle inequality, we have
Axx+1 - bll 2 || (y (ys+1. z.) - bll ||Axx+1 - Ax+ll + |A(x, - x (y++1, 2a)ill
2|1.||
2|1
< || 2.) - bll +|||||| Xo+1 Xxll + T(p Izg) ||xs - Xa+1
vs(x))]
p Lgg
0
(100)
where in the second inequality, we use Lemma C.6 and the last estimate uses (98).
Then, we have by triangle inequality that
|| < || K 1st1,, - V V 2s+1, 2.)
Vo+1,2.)
G(x.,
+ 2 [|x+1 - x. + ||||||| Ax,,+1 - bll + - zz
$ LLx -) ||x x, [
f. p|A|||| - bll +H((xx zoll ||x+11 xxl))
= O
"xx,, where in first inequality, we introduce term V (X., Ys+1, 2.) and then use triangle inequality. The second inequality used Lipschitzness of K, the definition of G. and the triangle inequality. The last step uses (98) and (100) and p = =1(1) since it chosen arbitrarily in Alg. 3.
37


Reviews:
[{"review_id": "2KW6mzN6lW", "reviewer": "Reviewer_WK98", "summary": "This work proposed stochastic algorithms for solving nonconvex optimization problems with linear inequality constraints. The main idea is to treat the original nonconvex constrained problem as a nonsmooth optimization problem, and solve it by leveraging the Moreau envelope smoothing technique.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful review and their detailed questions. We really appreciate their effort in evaluating our work.\n\n> The reviewer suggests discussing the following paper by Hu et al, 2024.\n\nThank you for pointing out this relevant work! We agree that this paper focuses on a different problem with different goals. We will include a discussion of the algorithm design in this paper and its similarity to our work, in the final version of our paper.\n\n> It would be a lot clearer if there is a table summarizing existing and the proposed methods and highlighting the main contributions of this work.\n\nWe will add this table to our paper. We also include it here for reference. For further complexity comparisons (and clarifying how we handle $Ax\\leq b$), we refer to our response to Reviewer 1NyX. For the importance of showing guarantees for ALM instead of penalty methods, we also refer to [1]. We solve an open question stated in Section 5 of [1].\n\n$$\n\\text{Objective: } \\mathbb{E}_\\xi [f(x,\\xi)]\n$$\n\n| **Reference** | **Constraint**                                                                         | ** Oracle** | **Complexity**                              | **Loops** | Method  |\n| ------------- | -------------------------------------------------------------------------------------- | ----------- | ------------------------------------------- | --------- | ------- |\n| [1]           | $A x = b$                                                                              | ①           | $\\widetilde{\\mathcal{O}}(\\varepsilon^{-3})$ | 1         | ALM     |\n| [1]           | $\\mathbb{E}[c(x,\\zeta)] = 0$ and $x \\in X$ where $X$ is easy to project on  | ①           | $\\widetilde{\\mathcal{O}}(\\varepsilon^{-5})$ | 1         | Penalty |\n| [2]           | $c(x)=0$  and $x \\in X$ where $X$ is easy to project on                                                                              | ①           | $\\mathcal{O}(\\varepsilon^{-3})$             | 1         | Penalty |\n| [3]           | $\\mathbb{E}[c(x,\\zeta)] = 0$  and $x \\in X$ where $X$ is easy to project on                                                           | ①           | $\\mathcal{O}(\\varepsilon^{-5})$             | 2         | Penalty |\n| This work     | $A x \\leq b$                                    | ②           | $\\mathcal{O}(\\varepsilon^{-4})$             | 1         | ALM     |\n| This work     | $\\mathbb{E}_\\zeta[A(\\zeta)x - b(\\zeta)] \\leq 0$ | ②           | $\\mathcal{O}(\\varepsilon^{-4})$             | 1         | ALM     |\n\nOracle ①: for a given random seed $\\xi$, we need to sample $\\nabla f(x, \\xi)$ and $\\nabla f(y, \\xi)$, satisfying:\n\n$$\\mathbb{E}_\\xi[\\nabla f(z,\\xi)]=\\nabla f(z)$$ \n\nand \n\n$$\\mathbb{E}_\\xi\\|\\nabla f(z,\\xi)-\\nabla f(z)\\|^2\\leq \\sigma^2$$ \n\nfor $z=x$ and $z=y$ and,\n\n $$\\mathbb{E}_{\\xi}\\|\\nabla f(x,\\xi)-\\nabla f(y,\\xi)\\|^2\\leq L^2\\|x-y\\|^2$$\n\nOracle ②: we only evaluate the stochastic gradient at a single point $x$ for seed $\\xi$, satisfying\n\n $$\\mathbb{E}_\\xi[\\nabla f(x,\\xi)]=\\nabla f(x)$$\n\nand\n\n$$ \\mathbb{E}_\\xi\\|\\nabla f(x,\\xi)-\\nabla f(x)\\|^2\\leq \\sigma^2$$\n\n[1] Alacaoglu, and Wright. “Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints.” AISTATS 2024\n[2] Lu, Mei, Xiao. Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees arXiv, 2024.\n[3] Li et al. Stochastic inexact augmented Lagrangian method for nonconvex expectation constrained optimization. COAP 2024\n\n> Typo: in line 123, the right column, a ')' is missing \n\nThank you! We will fix the typo.\n\n> In line 194 (left column), the definition of the function $L_\\rho(x, y_{t+1}, z_t)$ seems missing. Should it be $L_\\rho(z_t, y_{t+1})$ instead?\n\nIt is a typo. In line 194, $L_\\rho(x, y_{t+1}, z_t)$ should be $L_\\rho(x, y_{t+1})$ (which is defined in line 97). And in Algorithm 1 and 2 (line 224 and 338), $L_\\rho(x_t, y_{t+1}, z_t)$ should be $L_\\rho(x_t, y_{t+1})$.\n\n> The method design and analysis seem interesting and solid to me, but the lack of experiment is the main weakness.\n\nWe ran a preliminary experiment to validate our theory. This result also shows that our algorithm converges faster than [I]. We consider the stochastic quadratic programming problem:\n\n$$\\min_{x} \\mathbb{E} \\frac{1}{2} x^T Q(\\zeta) x + r(\\zeta)^T x: \\mathbb{E}  [A(\\xi) x - b(\\xi)] = 0, \\ell_i \\leq x_i \\leq u_i$$\n\nwhere $x \\in \\mathbb{R}^{n}$, $Q(\\zeta) \\in \\mathbb{R}^{n \\times n}$, $r(\\zeta) \\in \\mathbb{R}^n$, $A(\\xi) \\in \\mathbb{R}^{m \\times n}$, and $b(\\xi) \\in \\mathbb{R}^m$.\n\n| **Iteration** | ALM(ours) | **Penalty method [I]** |\n| ------------: | --------: | ---------------------: |\n|           1e5 |    0.5036 |                 0.7050 |\n|           1e6 |    0.0454 |                 0.5017 |\n|           2e6 |    0.0219 |                 0.2656 |\n|           5e6 |    0.0152 |                 0.2025 |\n|           1e7 |    0.0082 |                 0.1755 |", "claims_and_evidence": "The main claim of this paper is that the proposed method can achieve a complexity of $O(\\epsilon^{-4})$ in terms of solving nonconvex optimization with linear inequality constraints. This claim is supported by the analysis.", "methods_and_evaluation_criteria": "The idea behind the proposed method makes sense.", "theoretical_claims": "I briefly checked all the proofs in the appendix, and I do not see any major issues.", "experimental_designs_or_analyses": "The paper has no experiment.", "relation_to_broader_scientific_literature": "The main contribution of this work is to show a way of using the Moreau envelope technique in solving the family of constrained optimization problems. Similar strategy may apply to other setting.", "essential_references_not_discussed": "There is a previous work studied the nonsmooth min-max problem and proposed a very similar algorithm. Although the ultimate goals are different, as they do not consider any constraints, I believe it still worth to discuss due to the high similarity in the method design.\n\nQuanqi Hu, Qi Qi, Zhaosong Lu, and Tianbao Yang. Single-loop stochastic algorithms for difference of max-structured weakly convex functions. In Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, 2024.", "other_strengths_and_weaknesses": "The method design and analysis seem interesting and solid to me, but the lack of experiment is the main weakness.", "other_comments_or_suggestions": "As someone who is not familiar with the constrained optimization literature, I find the motivation to be vague while reading the first section, especially when many details on existing works are deferred to the last section. It would be a lot clearer if there is a table summarizing existing and the proposed methods and highlighting the main contributions of this work.\n\nTypo: in line 123, the right column, a ')' is missing in the gradient of Moreau envelope.", "questions_for_authors": "In line 194 (left column), the definition of the function $L_\\rho (x,y_{t+1},z_t)$ seems missing. Should it be $L_\\rho (z_t,y_{t+1})$ instead? The same issue exists in Algorithm 1 and Algorithm 2.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kKO3TYW1hV", "reviewer": "Reviewer_srvF", "summary": "The authors introduce smoothed primal-dual algorithms for solving stochastic nonconvex optimization problems with linear inequality constraints. Their approach builds on an inexact gradient descent framework for the Moreau envelope, where the gradient is approximated using a single step of a stochastic primal-dual augmented Lagrangian algorithm. They also establish the $\\mathcal{O}(\\epsilon^{-4})$ sample complexity guarantee for their algorithms and provide extensions to stochastic linear constraints.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful review and their detailed questions. We really appreciate their effort in evaluating our work.\n\n> The reviewer asks to avoid \"the algorithm is free of large batch sizes\" in the abstract and elsewhere, as the post-processing step requires a batch size $\\mathcal{O}(\\varepsilon^{-2})$.\n\nWe respond to this question in two parts.\n\nFirst, in our Theorem 3.1, we can get the $\\varepsilon$-near stationary point without the post-processing step, hence this result is completely free of large batch sizes.\n\nSecond, for the result in Corollary 3.2, we use the post-processing step **only once** to get $\\epsilon$-stationary point (we refer to our answer below for the difference between stationarity and near-stationarity), whereas other works that use large batch sizes require it in **every iteration**. For example, the work [I] not only considers linear equalities but also uses increasing mini-batch sizes at every iteration (see Remark 2 of [I]). Moreover, such a post-processing step is standard and has been used in earlier works, for example, [II, Appendix H] that also use single-sample algorithms at every iteration.\n\n[I] Huang, Chen, and Huang. \"Faster stochastic alternating direction method of multipliers for nonconvex optimization.\" ICML 2019.\n\n[II] Alacaoglu and Lyu. \"Convergence of first-order methods for constrained nonconvex optimization with dependent data.\" ICML 2023.\n\nAs a result, we still argue that our method has a much more benign batch-size requirement: we use a large-batch size for **only one** iteration, and only for the optional post-processing step. Hence, our algorithm uses a single sample at every iteration. We will clarify this in our final revision. \n\n> \"The title mentions linear inequality constraints, ... This inconsistency is confusing—what is the main problem the authors aim to solve?\"\n\nSorry for the confusion!\n\nWe focus on the problem with the linear inequality constraint $Ax\\leq b$. Let us see why it is a special case of our problem formulation. Let us start from\n$$\n\\min_x f(x) \\quad \\text{s.t.} \\quad Ax \\leq b.\n$$\n\nSpecifically, we introduce a slack variable $s$, set $Ax - b = -s$, and $s \\geq 0$, and write the equivalent problem as:\n\n$$\n\\min_{x\\in\\mathbb{R}^n, s\\geq 0} f(x) \\quad \\text{s.t.}\\quad [A \\; I]\\begin{bmatrix} x \\\\ s \\end{bmatrix} = b.\n$$\n\nSetting\n$$\\begin{equation*}\nz=\\binom{x}{s}, ~~Z = \\mathbb{R}^n \\times \\mathbb{R}^m_+, ~~B=\\begin{bmatrix} A & I \\end{bmatrix}, ~~~ g(z) = f(x)\n\\end{equation*}$$\nthen we have\n$$\\begin{equation*}\n\\min_{z\\in Z} g(z)\\colon Bz=b,\n\\end{equation*}$$\n\nwhich is precisely the problem in Eq (1) where $Z$ is indeed polyhedral, which is required by $X$ in Eq (1). We will clarify this in the final version.\n\n> In Assumption 1.1.2, the set is defined as $X = \\{Hx \\leq h\\}$. If the studied problem involves linear inequality constraints, why is $X$ treated separately from $Ax = b$?\n\nHere, without loss of generality, we can always assume $X$ to be easy to project (if not, we can always use slack variables to reformulate the problem and require projecting on simple sets such as $\\{x: x\\geq 0\\}$), please see also our response to Reviewr 1Nyx. This means each of our projections have closed-form solution. And as explained in our response above, we handle the constraint $Ax \\leq b$ by reformulating it into equality constraints with slack variables.\n\nThe technical reason we treat them separately is because we would like to ensure that dual variable remains unconstrained (Note that writing the Lagrangian with an inequality constraint will require the dual variable to have a sign).\n\n> The paper presents two definitions of $\\varepsilon$-stationary points—one in line 140 and another in (3). Are these definitions equivalent?\n\n These are different notions, as emphasized in our text. Line 140 defines an **$\\varepsilon$-stationary** point, while Eq. (3) defines an $\\varepsilon$-**near stationary** point. Intuitively, near stationarity indicates proximity to a stationary point, making it slightly weaker than stationarity. Our results show near-stationarity without the post-processing step, whereas stationarity requires post-processing. These two definitions are commonly used in the literature.,such as Davis & Drusvyatskiy (2019). We will clarify this further in our final version.\n\n> What does $L_\\rho(x,y,z)$ represent in line 194? In line 98, it only involves $x$ and $y$.\n\n Thank you for pointing out this typo, which we will fix. Please see our response to Reviewer WK98.\n\n> It is essential to add some to empirically validate the performance of the proposed algorithm.\n\nWe ran some experiments to validate our theory. Please see our response to Reviewer WK98, and we will include the experimental results in the final version.\n\n> It could be better to have a table.\n\nPlease see the table in our response to Reviewer WK98. We will include the table in our final version.", "claims_and_evidence": "I guess the authors should avoid stating that \"the algorithm is free of large batch sizes\" in the abstract and elsewhere, as the post-processing step requires a batch size of $\\mathcal{O}(\\epsilon^{-2})$.", "methods_and_evaluation_criteria": "This paper primarily focuses on the convergence analysis of the proposed algorithm, without presenting any experiments. While I understand the overall idea, certain aspects remain unclear, as noted in my previous comments.", "theoretical_claims": "1. The title mentions linear inequality constraints. However, in (1), the constraint is given as $Ax = b$, which represents a linear equality constraint. Then, in line 145, the constraint changes to $Ax \\leq b$. This inconsistency is confusing—what is the main problem the authors aim to solve?\n\n2. In Assumption 1.1.2, the set is defined as $X = {Hx \\leq h}$. If the studied problem involves linear inequality constraints, why is $X$ treated separately from $Ax = b$?\n\n3. The paper presents two definitions of $\\epsilon$-stationary points—one in line 140 and another in (3). Are these definitions equivalent?\n\n4. What does $L_{\\rho}(x, y, z)$ represent in line 194? In line 98, $L_{\\rho}$ only involves $x$ and $y$.", "experimental_designs_or_analyses": "There are no experiments included. It is essential to add some to empirically validate the performance of the proposed algorithm.", "relation_to_broader_scientific_literature": "I do not see much connection to the broader scientific literature, as this paper focuses solely on algorithm analysis. However, the proposed algorithm has the potential to be applied to other machine learning problems.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "See the summary and theoretical claims sections.", "other_comments_or_suggestions": "It could be better to have a table summarizing all the related algorithms, their convergence guarantees, and their complexities.", "questions_for_authors": "Please answer my questions from other sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Sn1LLrhdwy", "reviewer": "Reviewer_EKoh", "summary": "The paper proposes smoothed primal-dual algorithms for solving stochastic nonconvex optimization constrained by deterministic or random linear inequality constraints. This is both an important advance in theory, and could be useful practically.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful review and their detailed questions. We really appreciate their effort in evaluating our work.\n\n---\n\n>(first paragraph of intro) should mention the assumption that $X$ is a set easy to project on. Currently, it gives a misleading impression of handling all linear inequality constraints.\n\nThis is a good point! We first wish to emphasize that assuming $X$ is easy to project is without loss of generality.\nSuppose that $X=\\{x\\mid Hx\\le h\\}$ is difficult to project. We can add slack variables to reformulate this problem so that we can handle it by projecting on simple set $\\{ x: x\\geq 0\\}$ and multiplications by $H, H^T$. Specifically, we can rewrite the original optimization problem as\n$$\n\\min_{x, s} f(x): Ax = b, Hx + s = h, s \\geq 0\n$$\n\nwhere $s$ is the slack variable. Then the set defined by inequality constraints  $\\{(x,s)\\mid s\\ge 0\\}$ is easy to project on and we can dualize the equality constraints $Ax=b,Hx+s=h$ in the Lagrangian function and use only multiplications with matrices $A, A^T, H, H^T$.\nIn summary, for problems with linear equality and inequality constraints, we can assume $X$ is easy to project without loss of generality. We also refer to our response to Reviewer srvF.\n\n> Th. 3.1 gives a complexity result for all iterates ($z_t$). In view of the proximal point interpretation of the method, one would think that the last iterate has better properties. Is that so?\n\nThis is a good question. However, in nonconvex stochastic optimization, the last iterate generally may not have better properties, and typically we need to sample a point from among all the iterates. For example, in [1]  (Algorithm 1 and 2), the authors also need to  randomly draw output x from $(x_t)^T_{t=1}$ at uniform. There are more examples, please see Section 6, in textbook [2]. In summary, in the stochastic case, we believe that it is hard to use the proximal point interpretation of ALM to improve the last iterate guarantees, because even without linear constraints, we are not aware of last iterate guarantees for single-loop algorithms for nonconvex stochastic optimization.\n\n[1] Lin, Jin, Jordan. On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems, ICML 2020.\n\n[2] Lan. First-order and stochastic optimization methods for machine learning. Springer, 2020.\n\n> On penalty methods: other penalty strategies (e.g., $Pen(x) = f(x) + \\rho \\| Ax - b \\|_2$) do not require $\\rho \\to \\infty$. This part is unclear.\n\nIndeed, in principle, there are papers about exact nonsmooth penalty methods, however we are not aware of complexity results with such a method for our stochastic problem. If the reviewer knows of such a reference, we would be happy to include it. We are taking advantage of the dual variable updates to avoid large penalty parameters. Our focus on ALM instead of nonsmooth penalty methods is because ALM has been a popular method in practice and our aim is to improve its theoretical understanding. The importance of analyzing ALM-based algorithms is also emphasized in the work of Alacaoglu&Wright, 2024 and in fact, we solve an open question stated in the Section 5 of this work. \n\n> Line 117 on the right: “...and lambda is selected accordingly”, is it a useful property of the Moreau envelope? This part feels weird in the sentence.\n\nBecause in line 117, we only assume $f$ is weakly convex, we must select $\\lambda$ accordingly to ensure the Moreau envelope is also smooth. For example, if $f$ is $\\rho$-weakly convex, then we need $\\lambda < \\frac{1}{\\rho}$. We will revisit the sentence\n\n> Line 194: augmented Lagrangian $L_\\rho(x_t, y_{t+1}, z_t)$ is mentioned, while in the rest of the paper, only two arguments are used.\n\nThank you for pointing out this typo, which we will fix. Please see the response to reviewer WK98.\n\nFinally, we wish to thank you so much for your careful reading and suggestions about the phrasing at many places, we will carefully incorporate your suggestions in our final version.", "claims_and_evidence": "The claims are correct, as far as I can tell.", "methods_and_evaluation_criteria": "There are no experiments described.", "theoretical_claims": "The proofs are correct, as far as I can tell.", "experimental_designs_or_analyses": "There are no experiments described.", "relation_to_broader_scientific_literature": "The literature is fairly presented.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "- l. 42 (first paragraph of intro) should mention the assumption that X is a set easy to project on. Currently, it gives a misleading impression of handling all linear inequality constraints.\n- on penalty methods: other penalty strategies (eg, Pen(x) = f(x) + \\rho \\| Ax-b \\|_2) do not require $\\rho \\to \\infty$. This part is unclear.\n- Th. 3.1 gives a complexity result for all iterates (z_t). In view of the proximal point interpretation of the method, one would think that the last iterate has better properties. Is that so?\n- l. 117 on the right: “...and lambda is selected accordingly”, it is a useful property of Moreau envelope? This part feels weird in the sentence.\n- l. 123: missing parenthesis\n- l. 143 on the left: “When we have the problem” is not followed by a clause.\n- l. 160: x -> y\n- l. 170 on the left: the full stop after -/infty.\n- l. 182 on the right: “outputs a points”\n- l. 194: augmented Lagrangian L_ρ(x_t, y_t+1, z_t) is mentioned, while in the rest of the paper, there are only two arguments used. The three-argument version (with z_t) does not make sense, because the \"smoothing operation\" is performed \"outside\" L_ρ. \n- l. 217 on the right: “This post processing step… ...do not affect”\n- l. 237 on the left: “Moreau envelope are critical”\n- l. 254 on the right: “This which requires…”\n- l. 295 on the right: “...decreases, in expectation,u p to an error term depends \\tau^2 and the variance”\n- l. 397 on the left: “the best-known rate have been”\n- l. 422 on the left: “which is obtained with either double loop algorithms” not followed by “or…”\n- l. 435 on the left: “Since these work focuses”\n- l. 557: should be \"u \\in X\"\n\nMinor things:\n\n- l. 143 on the left: “When we have the problem” is not followed by a clause.\n- l. 117 on the right: “...and lambda is selected accordingly”, it is a useful property of Moreau envelope? This part feels weird in the sentence.\n- l. 170 on the left: the full stop after -/infty.\n- l. 182 on the right: “outputs a points”\n- l. 217 on the right: “This post processing step… ...do not affect”\n- l. 237 on the left: “Moreau envelope are critical”\n- l. 254 on the right: “This which requires…”\n- l. 295 on the right: “...decreases, in expectation,u p to an error term depends \\tau^2 and the variance”\n- l. 397 on the left: “the best-known rate have been”\n- l. 422 on the left: “which is obtained with either double loop algorithms” not followed by “or…”\n- l. 435 on the left: “Since these work focuses”", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WNgZKMT3y0", "reviewer": "Reviewer_1NyX", "summary": "This paper investigates a single-loop ALM-type algorithm for solving linearly constrained nonconvex optimization problems. The framework accommodates both stochastic objective functions and stochastic constraints. Theoretical analysis demonstrates that the proposed algorithm achieves competitive complexity.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful review and their detailed questions. We really appreciate their effort in evaluating our work.\n\n> Numerical examples\n\nWe ran a preliminary experiment to validate our theory. Please see our response to Reviewer WK98.  \n\n> Additionally, the differences from previous work should be highlighted, as this paper heavily relies on the smoothed technique, which has been extensively studied in analysis.\n\nWe want to highlight that, to our knowledge, this is the first algorithm achieving the optimal $\\mathcal{O}(\\epsilon^{-4})$ sample complexity for stochastic nonconvex optimization problems with stochastic constraints using only one sample per iteration.\n\nFirst, in view of [1], which works for unconstrained min-max problems, the descent property cannot be guaranteed when their idea is applied to constrained problems. To address this issue, we introduce a potential function specifically designed for constrained settings, ensuring the descent property. We also use the gradient of the Moreau envelope, in place of the function $\\nabla K$ used in works of Zhang and Luo, see for example Lem A.7 and A.8 and the estimations using these.  We note that projection causes extra difficulties with stochastic gradients, see for example the work of Davis&Drusvyatskiy, 2019.\n\nFurthermore, in the case of stochastic linear constraints, we propose a novel technique \"pulling back the dual variable\", which ensures boundedness of the dual variables. This property is critical but cannot be guaranteed by the deterministic analysis framework.\n\nWe will add these descriptions in the final version.\n\n[1] Yang et al. Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity, AISTATS 2022\n\n> Inequality constraints\n\nThanks for the good question (please also see our response to Reviewer srvF). We clarify that our work can solve problems with constraint $\\{x: Ax\\leq b\\}$ by only projecting on the set $\\{x: x\\geq 0\\}$ and multiplying with $A, A^T$.\n\nIn fact, the assumption on projectability of $X$ is without loss of generality. \n\nSuppose that ${x: Hx\\le h}$ is difficult to project. We can add slack variables to reformulate this problem to make the set defined by inequality constraints easy to project. Specifically, we can rewrite the original problem as\n\n$$ \\min_{x, s} f(x): Ax = b, Hx + s = h, s \\geq 0 $$\nwhere $s$ is the slack variable.Then the set defined by inequality constraints  $\\{(x,s)\\mid s\\ge 0\\}$ is easy to project and then we can handle the equality constraints $Ax=b,Hx+s=h$  by using simple products $A, A^T, H, H^T$, due to our algorithm design.\n\nIn summary, our assumption on $X$ being projectable is without loss of generality and for any inequality constrained problem, we can introduce slack variables so we only require projecting onto the simple set $\\{x: x\\ge 0\\}$\n\n> Comparisons with Alacaoglu&Wright, 2024\n\nThe sample complexity $O(1/\\epsilon^4)$ achieved by our algorithm is already optimal under our assumptions and oracle model, as established by [2] ([2] shows $O(1/\\epsilon^4)$ is even optimal for unconstrained problems). The improved complexity in Alacaoglu & Wright (2024) relies on a stronger stochastic oracle and additional smoothness assumptions. Specifically, our oracle assumes access to only one stochastic gradient $\\nabla f(x, \\xi)$ at a single query point $x$ per iteration, with $\\xi$ sampled from the distribution $P$. Under this oracle, the lower bound is $\\Omega(1/\\epsilon^4)$ [2], matching our complexity.\n\nHowever, Alacaoglu&Wright, 2024 require a stronger oracle: they assume availability of two stochastic gradients $\\nabla f(x;\\xi)$ and $\\nabla f(y;\\xi)$ evaluated at two different points $x,y$ for the same sample $\\xi$. Additionally, they make a stronger smoothness assumption:\n\n$\\mathbb{E}_{\\xi}\\|\\nabla f(x,\\xi)-\\nabla f(y,\\xi)\\|^2\\leq L^2\\|x-y\\|^2$,\n\nwhich is not required in our analysis.\n\n[2]Arjevani et al. Lower bounds for non-convex stochastic optimization. Math. Program. 2023.  \n\nIn addition, under the same stochastic oracle and the additional smoothness assumption, we can achieve the complexity of $O(\\varepsilon^{-3})$ by combining our ALM framework with the STORM variance reduction. This is a straightforward extension of our techniques and we can provide a proof sketch in the discussion stage if the reviewer wishes. We will add this result in the final version. The only difference in this algorithm would be in the definition of $G$:\n\n$$G(x_t, y_{t+1}, z_t) = F_t + A^{\\top}(Ax_t - b) + \\lambda(x_t - z_t)$$\n\nwhere \n\n$$F_{t+1} = \\nabla f(x_{t+1}, \\xi_{t+1}) + (1 - \\alpha) (F_t - \\nabla f(x_t, \\xi_{t+1}))$$\n\n> Step sizes\n\nOur stepsizes are chosen as order $1/\\sqrt{T}$, as standard in stochastic optimization. We refer to the textbook [3].\n\n[3] Lan. First-order and stochastic optimization methods for machine learning, 2020.\n\n> Choice of $M_y$\n\nSorry, the choice of $M_y$ was given in our proof of Thm 4.2, we will add it to main text in the final version.", "claims_and_evidence": "Yes, it is clear.", "methods_and_evaluation_criteria": "The complexity measure studied is standand.", "theoretical_claims": "Yes, I think the main theorem makes sense.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "This paper builds upon the approach of Zhang & Luo (2020, 2022) and extends it to the stochastic setting.", "essential_references_not_discussed": "The literature is well discussed.", "other_strengths_and_weaknesses": "Although this is a theoretical paper, validating the proposed algorithm with numerical examples would strengthen its contributions. Additionally, the differences from previous work should be highlighted, as this paper heavily relies on the smoothed technique, which has been extensively studied in analysis.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Are inequality constraints handled solely through projection? From the problem formulation, it appears that they can only be incorporated into the set $X$. Could you clarify this?  \n\n2. The paper states that the key difference from Alacaoglu \\& Wright (2024) is the inclusion of additional constraints in $X$. However, the complexity result in Alacaoglu \\& Wright (2024) is $O(\\epsilon^{-3})$, which is better than the result presented in this paper. Could you provide further explanation on this? Is there potential to improve the complexity in this paper, and what are the underlying reasons?  \n\n3. I notice that in Theorem 3.1, the stepsizes $\\tau$, $\\eta$, and $\\beta$ decrease as the number of iterations $T$ increases. Would this lead to impractically small stepsizes in real applications? How should these parameters be set in practical implementations?  \n\n4. How should the threshold $M_y$ be chosen in Algorithm 2? If it is set too small, $y$ may always remain at zero, potentially causing issues with the feasibility update. Could you provide guidance on selecting an appropriate value for $M_y$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes single-loop smoothed primal-dual algorithms for solving stochastic nonconvex optimization problems with linear inequality constraints. The proposed method achieves a convergence rate of $1/\epsilon^4$, and the analysis extends to cases with stochastic linear constraints.

Strengths:

The paper makes a solid theoretical contribution to the literature on constrained nonconvex optimization. The convergence analysis is technically sound, with all reviewers generally agreeing that the proofs are correct and the complexity result matches the worst-case lower bound under the assumption in the paper.

Weaknesses:

The lack of empirical validation is a major shortcoming noted across all reviews. In the AC's opinion, this is understandable given that the contribution of this paper clearly focuses more on the theoretical complexity analysis. The main theoretical limitation is the requirement that $X$ must be a polyhedron. We hope this can be relax in the future work. 

If this work is accepted. Please include the following items in the revision:

1. Reviewers suggested adding a summary table comparing existing methods and highlighting what is new in this paper. It seems the authors have such a table in the rebuttal to begin with.
2. A review suggest citing a closely related work (Hu et al., NeurIPS 2024) that employs similar techniques in different problem settings. 
3. Show how STORM can be used get the $1/\epsilon^3$ complexity under the stronger assumption.
4. Add more discussion on Lu et al, for example, like comments in your reply. It should be as important as Alacaoglu&Wright in your literature review, but it is not discussed as much in the current version.
5. Somewhere in the paper, refer readers to Li, Chen, Liu, Lu, Xu (https://arxiv.org/abs/2007.01284) for the corresponding between the 
$\epsilon$-stationary point inequality constrained problem and the equality-constrained problem after adding slack variable. If you have space to explain in details in your paper, that will be even better. 

AC
Decision: Accept (spotlight poster)