Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization
Authors: Yankun Huang
Qihang Lin
Venue: NeurIPS 2023 poster (2023)
Keywords: Constrained optimization
first-order method
non-smooth optimization
non-convex optimization
TL;DR: Single-Loop Methods for Constrained Optimization

Abstract: We consider a non-convex constrained optimization problem, where the objective function is weakly convex and the constraint function is either convex or weakly convex. To solve this problem, we consider the classical switching subgradient method, which is an intuitive and easily implementable first-order method whose oracle complexity was only known for convex problems. This paper provides the first analysis on the oracle complexity of the switching subgradient method for finding a nearly stationary point of non-convex problems. Our results are derived separately for convex and weakly convex constraints. Compared to existing approaches, especially the double-loop methods, the switching gradient method can be applied to non-smooth problems and achieves the same complexity using only a single loop, which saves the effort on tuning the number of inner iterations.

Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization
Yankun Huang
Qihang Lin
Department Business Analytics
Department of Business Analytics
University of Iowa Iowa City, IA 52242
University of lowa Iowa City, IA 52242 gihang-linOuiowa edu
edu
Abstract
We consider non-convex constrained optimization problem, where the objective function is weakly convex and the constraint function is either convex or weakly convex. To solve this problem, we consider the classical switching subgradient method, which is intuitive and easily implementable first-order method whose oracle complexity was only known for convex problems. This paper provides the first analysis the oracle complexity of the switching subgradient method for finding a nearly stationary point of non-convex problems. Our results are derived separately for convex and weakly convex constraints. Compared to existing approaches, especially the double-loop methods, the switching gradient method can be applied to non-smooth problems and achieves the same complexity using only a single loop, which saves the effort on tuning the number of inner iterations.
Introduction
Continuous optimization with nonlinear constraints arises from many applications of machine learning and statistics. Examples include Neyman Pearson classification 662 and learning with faimesss constraints 777. this paper, we consider the following general nonlinear constrained optimization
min xEX
f(x) s.t. g(x) < O,
(1)
where X' C. IRd is a closed convex set that allows a computationally easy projection operator, f weakly-convex, g is either convex weakly convex. and functions f and g are not necessarily smooth. When 9(x) = max4=1...... (x).
I is equivalent to an optimization problem with multiple
nonlinear constraints (x) < 0 for i
1, 11..........
weakly convex function can be non-convex, so computing an optimal solution of (T) is challenging in general even without constraints. For this reason, theoretical analysis for gradient- based algorithms non-convex problems mostly focuses on an algorithm's 's (oracle) complexity for finding an e- stationary solution for (1). When a problem is non-smooth, finding an e-stationary solution is generally difficult even if the problem convex 47.. Hence, in this paper, we consider finding
nearly e-stationary solution for (I) whose definition will be stated later in Definition 3.2
In the past decade, there have been many studies on non-convex constrained optimization. However, most of the existing algorithms and their theoretical complexity analysis are developed by assuming and gi's are all smooth or can be written as the sum of smooth and a simple non- moo-hhohh functions.
A non-ex eoo-ssxha list of the works under such an assumption includes [34] 80, [8] [55 44 45 43 (22
63 [53] 50 12 22
40 5T. Their results cannot be applied due non-son montsmotttesss in the
problem.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Non-smoothness is common in optimization in machine learning, e.g., when a non-smooth loss function is applied, but there are much fewer studies on non- non-smooth non-convex constrained opti- mization. Under the weak-convexity assumption, an effective approach for solving a non-smooth non-convex problem with theoretical guarantees is the (inexact) proximal point method, where a quadratic proximal term is added to objective and constraint functions to construct a strongly convex constrained subproblem and then a sequence of solutions can be generated by solving this subproblem inexactly and updating the center of the proximal term, Oracle complexity for this method to find nearly e-stationary has been established by 13 54 39 under different constraint qualifications.
The inexact proximal point method is a double-looe algorithm where the inner loop is another optimization algorithm for solving the aforementioned strongly convex subproblems. The complexity results in [13 54 39] require the inner loop solves each subproblem to a targeted optimality gap. However, the optimality gap is hard to evaluate and thus cannot used to terminate the inner loop. Although the number of inner iterations needed to achieve the targeted gap can be bounded theoretically, the bound usually involves some constants that are unknown or can only be estimated conservatively. Hence, using the theoretical iteration bound to stop the inner loop usually leads to significantly more inner iterations than needed, making the whole algorithm inefficient. In practices, users often need to tune the number of inner iterations to improve algorithm's 's efficiency, which is an inconvenience common to most double-loop methods.
On the contrary, a single-loop algorithm is usually easier to implement as it does not require tuning the number of inner iterations. Therefore, the main contribution of this paper is showing that a single- loop first-order algorithm can find nearly e-stationary point of (1) with oracle complexity O ((1/6"),
which matches state-of-the-arr results obtained only by the double-loop methods [3 54 39 The
algorithm we study is the classical switching subgradient (SSG) method proposed by Polyak [59] in 1967, which is intuitive and easy to implement but has only been analyzed before in the convex case. We first show that the SSG method has complexity complexity O(1/e*) when g is convex. Then, we show that the same complexity result holds when g is weakly convex and appropriate constraint qualification holds. We also present some practical examples where all of our assumptions hold, including a fair classification problem subject to the demographic parity constraint []. Our technical novelty is inventing switching stepzize rule to accompany the switching subgradient. In particular, we use a fixed stepsize when the solution is updated by the objective's ' subgradient while use adaptive Polyak's stepsize [33 60) when the solution is updated by the constraint's subgradient. This allows us to leverage the local error bound of the constraint function to keep the solution nearly feasible during the algorithm, which prevents the solution from being trapped at an infeasible stationry point. To the best of our knowledge, this paper is the first to establish the complexity of a single-loop first-order method for weakly convex non-smooth nonlinear constrained optimization. In the appendix, we also extend our algorithms and complexity analysis to the stochastic setting.
2
Related work
Non-convex constrained optimization has long history [36 this subject has been still growing in the machine learning community because of its new applications such as learning with faimess constraints (see e.g., (77)..
16
29
17
30
6
18]
and the interest on
In recent literature, the prevalent classes of algorithms for non-convex constrained optimization include the augmented Lagrangian method (A (ALM), the penalty method (37 79 80
81
38
42
55
44
45
69
43
52
63
53
50 40
5D, and the sequential quadratic programming method [1
34
21
Besides, an inexact projected gradient method is developed by (15) and a level
conditional gradient method is developed by (20]. However, these works all focus on the case where g is smooth and f is either smooth or equals fi + f2. where fi is smooth and non-convex while fa is non-smooth and convex and has a simple structure that allows closed-form solution for the proximal mapping arg miny (f2(v) + ? lly x|| for any x. There are relatively fewer works on non non-convex non-smooth constrained problems. An alternating direction method of multipliers (ADMM) and an ALM are studied by [75] and (78). respectively. for non-conver non-smooth problems with linear constraints while our study considers nonlinear non-smooth constraints. The methods by (0 and 12 can be extended to structured non-smooth case where f= fi + Sa with Si being smooth non-convex and f2 = maxy (y Ax - Φ(y)} with a convex Φ. and g has a similar structure. The method by [1] can handle specific non-smooth non-convex constraint, i.c., g(x) A||x||1 h(x)
}
2

---

where h is a convex and smooth. Compared to these works, our results apply to more general non-smooth problem without those structure assumptions.
When f and in (1) are weakly convex and non-smooth, the inexact proximal point method has been studied by 13 [9 under different constraint qualifications and different notions of stationarity.
Their complexity analysis utilizes the relationship between the gradient of the Moreau envelope
of |I and the near stationarity of solution, which is originally used analyze complexity of subgradient methods for weakly convex non-smooth unconstrained problems (24 27 2 28 61
[3 54 39 are double-loop while our algorithm only uses single loop and achieves the same complexity of O(1/c*) as them under similar assumptions.
83
Our analysis utilizes similar framework. The methods
The SSG algorithm is first proposed by Polyak 59 It has been well-studied for convex problems 558
66 ( and quasi-convex problems [67]. This paper provides the first complexity analysis for the SSG method under weak convexity assumption. Non-smooth non-convex
49
67
72
73
65
68
optimization has also been studied without weak convexity assumption by [82] 46 664 47 19 70
711. These works analyze the complexity of first-order methods for computing an (e, 6) -ooodssti
approximate stationary point, which is more general stationarity notation than what we consider here. However, these works only focus on unconstrained problems.
3 Algorithm and near stationarity
Let ||- be the normm. For / Rd - IR U (+xc), the subdifferential of at x is
ah(x)= = E h(x')= 2 (xx) + (c,x' - x) + o[[|x' xl)), x' + x}: and Ç & 0x(x) is subgradient of / at x. We say h is u-strongly convex (μ 2 0) on X if
h(x)= 2 h(x') + (C, x') 1" 2
x112
for any (x,x) E X x X' and any Ç E 0h(x'). We say h is p-weakly conver (p 2 0) on X if
h(x) 2 h(x') + (c, x) || x11
for any x') E X' x X' and any Ç E (x'). We denote the normal cone of X' at x by Nx and the relative interior of X' by relint(2'). We say point is e-feasible if x X' and g(x) Let (x) be the zero-infinity characteristic function of set X, (+) be the projection mapping to X, and dist(x, A) minye.A ||x - y/| for set A.
We make the following assumptions on ① throughout the paper.
Assumption 3.1. Functions f and g are continuous with 0f(x) & and 0g(x) + 0 on X, and there exists M such that ||C - M and ||C,]| S M for any x E X, C E 0x(x) and C. E 0g(x).
Since T is non-convex, finding an c-optimal solution intractable in general. For non-convex problem, the target is typically to find a stationary point of (I. which is a point x" E X' that satisfies the following Karush- Kuhk-Tucker (KKT) conditions:
+ -Nx(x'), X Xg((")== =0, g(x') 50, 2
where X" R is a Lagrangian multiplier, S E Of(x') and 5 E 0g(x*). Typically, an exact stationary point can only be approached by an algorithm at full convergence, which may require infinitely many iterations. Within a finite number of iterations, an algorithm can only generate an e-stationary point [3). which is point & E X satisfying
dist (2,+ + -xx(2) Sec, (8((3) se,
se 720
(2)
where ā R is a Lagrangian multiplier, č, E af()) and č, E 0g( However, because f and g are non-smooth, computing e-stationary point is still challenging even for an unconstrained problem. Nevertheless, under the weak convexity assumption, it is possible to compute a nearly e-stationary point, which we will introduce next.
Given و > 0, p 2 0 and x e X. we define quadratically regularized problem of
3

---

Algorithm Switching Subgradient (SSG) Method by Polyak [59]
1: Input: x() E X, total number of iterations T, tolerance of infeasibility 6 2 0, stepsize f), and
starting index S for generating outputs.
2: Initialization:
and 0.
3: for iteration { 0, ......
.. T
1 do
4: if g(x(1) I Er then
5: Set ((+1) proj (x(1) )/ for any c E ()((()) and, 2, 1 ru
6: else
7: Set ((+1) = proj. (x - - for any " 0y(x(()) and, if 2 S, J = JU(
8:
end if
9:
end for
10:
Output I: x(() with randomly sampled from I using Prob(T t) /t/ Σ SEl 1/.
Output II: x(r) with 7 randomly sampled from I U using Prob(T t) = nT/ Eeglus Us
f(y) + f x11², s.t. gly) + p f x|| < =0
p 2
(xx) min yea
(3)
2
x(x) arg min
{s(>) +
2 f1y x|| s.l. g(y) + 2 y 1| = 0)
(4)
yex
Following the literature on weakly convex optimization 24 27
13
39 we use the value of
|[x(x) x|| as a measure of the quality of a solution x because it can be interpreted as stationarity
measure. For the purpose of illustration, we assume for now that x(x) is uniquely defined and there exists a Lagrangian multiplier X E IR such that the following KKT conditions of (4) holds.
?, + 0(x(xx - x) + X (2, + p(((x) - x)) E (xx(xx)))
(5)
ā (((((x)) + 1 |x((x) x11 = O, gxx(x)) + _ [1x(xx) - x|| S 0,
7 2 0,
2
where č, (x)( and 2, E Og 0g(x)xx)) Therefore, long ||((x) x|| c, we have
dist (2, + XC,: (x(x) s (p + Ap)c.
Ag((((x)) = Xpe²/2. g (x(x)) S 0.
(6)
This means x(x) is an Oee) --stationary point of the original problem | in the sense of 2 Since x is within an e-distance from 8(x), we call such an x nearly e-stationary point of We formalize this definition as follows.
Definition 3.2. Suppose x(x) is defined in 4 with 2 0. A (stochastic) point x E & is (stochastic) nearly c-stationary point of [ if E (x)
x|| <.
Of course, we can claim xxx) an O(c) -tt)-stationary point of (1) based on (6) only when À in (5) exists and does not go to infinity as e approaches zero. Fortunately, we can show in Lemmas 4.2
5.2 this is true under some constraint qualifications, which justifies Definition 3.2
We present the SSG method in Algorithm for finding a nearly e-stationary point of ① At iteration
S e, for a pre- determined tolerance of infeasibility ez. If yes, the algorithm performs a subgradient step along the subgradient of f. Otherwise, the algorithm switches the updating direction to the subgradient of g. The algorithm records the iteration indexes of the nearly feasible solutions in set I and other indexes in set J. The final output is randomly sampled from the iterates in or I U J with a distribution weighted by the stepsizes 77, 's. An index S is set the algorithm only starts to record I and J when t 12 S. We study the theoretical oracle complexity of Algorithm [ for finding a nearly e-stationary point, which is defined as the total number of times for which the algorithm queries the subgradient or function value of f or g. Our results are presented separately when g is convex and when is weakly convex.
t, we check if the current solution (!)) is nearly feasible in the sense that (xx())
4 Convex constraints
In this section, we first consider a relatively easy case where f is weakly convex but g is convex. In particular, we make the following assumptions in addition to Assumption 3.] in this section.

---

Assumption 4.1. The following statements hold:
A. (x) is p-weakly convex on X' and g(x) is convex on X.
B. (Slater's condition) There exists Xieas E relint(X(') such that g(Xiews) < O.
C. There exists D E IR such that ||x 1x'I x'|l S D for any x and x' in X.
In this section, we choose parameters in (3) such that
i > p and p= 0.
(7)
Under Assumption 4.1
guarantees that (3) is strictly feasible, its objective function is (p - p)-
strongly convex and its constraint function is convex, so x(x) in (4) is unique and Ā in (5) exists. We
first present an upper bound of X that is independent of x. The proof is in Section A.1
Lemma 4.2. Suppose Assumptions 3.7 and 4.1 hold. Given any x E X, let x(x) be defined as in (4)
with (p. p) satisfying and À be the associated Lagrangian multiplier satisfying (5) We have
v ==
= (MD (
(8)
For simplicity of notation, we denote ((x(+) defined in (4) by x() Let E,1-] be the expectation taken only over the random index when the algorithms stop. We present the convergence properties
of Algorithm when and 1/ are static and diminishing. The proof is provided Section
Theorem 4.3. Suppose Assumptions 3.1 and 4.1 hold and A is as in (8). Let ((x(1) be defined
as in (4) with (Ø, p) satisfying and x (() is generated by Output I. Algorithm guarantees
E. (() x(7) S and E., (x(gg((()) S I+A
(pppp) in either of the following cases.
(pppp))
2c (p-p) and T
25M D'M+A2 = 0(1/E)).
Case == 0, 6t = I+A 1}t = 5(1+A]M
26 10-0pp)²
Case 11: S = 6
5MD
D VETI 171 MVFFI and T
50 O(1/et).
<(pppp²
Algorithml 1 is single-loop with (1)) oracle complexity per iteration, so its total complexity is just T = O()C), which matches the shar--o-thheatt complexity by [13 [54] (39. This result can be generalized to the case where there exist additional linear equality constraints Ax b. See the extension of Lemma 4.2 in Section and Remark A.2
Assumption 4.1 C can be relaxed only require that the feasible set, i.e., S (x E X 19(x) < 0}.
bounded instead of X' The same complexity can be achieved by Algorithm T by using a switching step size rule similar to 7/ Proposition This result is provided in Section |A.8 but we recommend interested readers to read Section first to get introduced to this special step size.
Remark 4.4. Property [x((())) ( g) in the theorems above is not required by Definition 3.2 I+A
By Assumption 3.1 A, E, [g(( < E, [g(((T)) + ME, [[[(()) x(1 I Me, which means
nearly esttationary point must be O(e) O(e)-feasible by definition. Property [x((((()))] s (
1+A
implies ((²²) feasibiliy for the output, which is even better.
When g is j--ttroglyy convex with μ > O, we can show that the complexity of Algorithm D is still O(1/e*) but can simply set e, O, which makes T) the only tuning parameter. This makes this single-loop method even more attractive. Due to space limit, we include this result Scction A.5 We also extend our result to the stochastic case in Section An6
5 Weakly convex constraints
Next we consider the case where both f and g are weakly convex but not necessarily convex. Let
g+ (x) = max(((()),00)) L {x E X g(x) 0} and S = (x E X g(() S 03.
We make the following assumptions in addition to Assumption 3.1 in this section.
Assumption 5.1. The following statements hold:
5

---

A. f(x) and g(x) are p-weakly convex on X.
B. There exist È > O, 0 > 0 and p p such that, for any feassible solution x, there exists y E relint((t) such that g(y) + ly -x|1 -0.
C. f= infxex f(x) -00.
Assumption 5.1 is called the uniform Slater's condition by [54] We will present two real-world examples in Section that satisfy this assumption, including fair classification problem under demographic parity constraint, which is one of the applications in our numerical experiments in Section 6.2
In this section, we choose parameters in 33 such that
p P p p.
Under Assumption 5.1
guarantees that 33) is uniformly strictly feasible for any f-feesible x, and the objective and constraint functions of (3 are both (p- p)-strongly convex, so x(x) is uniquely defined and X in (5) exists. In addition, Assumption
5.1 has the following three implications that play
important roles in our complexity analysis.
First, Ā in (5) can be bounded by a constant independent of x and e as long as x is ee-feaiible with S E. This result is similar to Lemma 1 by Ma et al. [54] except that they require X to be bounded but we do not. The proof given in Section B.2
Lemma 5.2. Suppose Assumptions 3.1 and 5.7 Given any e² -e-aasiblle x with any S let R(x) defined as in satisfying (9) and X is the associated Lagrangian multiplier satisfying We have
[x(x)
x|| S M/P and A = 2M/ 2M//200p p).
(10)
Second, the subgradient of the constraint function g(x) + 5x(x)) on L is uniformly away from the origin. The proof is provided in Section B.2 Lemma 5.3. Suppose Assumptions
3.7 and 5.7 hold. It holds for any x E C that
min C, (E
I|S, ull 2 == 100:=v2800 20 p).
(11)
Lastly, note that S is the optimal set of minxex 9+ (x), which is p-weakly convex non-smooth optimization problem with an optimal value of zero. Lemma 5.3 implies that g- (x(x is sharp near the boundary of S, meaning that g+ (x) satisfies a linear error bound in an O(i)nneigboorhood of S. A
similar result for a convex J+ is given in Lemma in [76.. In the lemma below, we extend their result
for weakly convex 94. The proof is in Section B.2 and the second conclusion is directly from (26).
Lemma 5.4. Suppose Assumptions
3.1 and 5.7 hold. It holds for any x satisfying dist(x, S) S v that
(v/2)dist(x (x, S) S g+ (x))..
(12)
Moreover, v < 2M and minxex 9+ (x) has no stationary point satisfying 0 < dist(x, S) < %/-
Since g is non-convex, Algorithm may not even find nearly feasible solution if (9) is trapped at stationary point of g with g(x) > 0, that is, a sub-optimal stationary point of milxxe g (x). Fortunately, the second conclusion of Lemma 5.4 indicates that this situation can be avoided by
keeping dist(x("), S) O(e2) during the algorithm. To do so, we start with (0) E and use ét
O(e2) in Algorithm 1 Moreover, we apply a switching stepsize rule that sets γ) = Oc2)) when / E
and 7/+- (0)
12 when L J, the latter of which is known by the Polyak's 's stepsize 33 60
This way, when g(x(") S G. 12 ensures dist(x("), 5) O(e2). When g g(x(1) > cz. 12) ensures
dist(x("),.)) Q-linearly converges to zero (26). which also guarantees dist(x!"), ,S) O ). As
result, we have g(x(+)) < é² for any t, so problem (3) with x (*) and (p, P) satisfying (g) will be
strictly feasible according to Assumption S.IB. This finding is given in the proposition below with its
proof in Section B.3
Proposition 5.5. Suppose Assumptions
3.1 and 5.1 hold and < E. Also, suppose x(i) is generated by Algorithm 7 using (0) E S, e = min
/e2/M, w/(4p) and
ZMfz min (2//,u/((4p) i
11 g(x (/11 (912
J.

---

Then tist(x!",,S) _ min (e//M,v/ and g(x(1)) I e for any t 2 0. As consequence, x!!) is e-feasible (3) where x(1) and (p. P) satisfies
Let x(1) be x(x(9) defined in (4) with (p. P) satisfying ( The complexity result for the case of
weakly convex constraints is as follows. The proof can be found in Section B.3
Theorem 5.6. Under the same assumptions Proposition 5.5
Algorithm 1 guaranttes E, [||x(7]
[[] S Ce and Er [x(g((((1)) S 6², where C' 2=
L+N D-p²
if we use Output II and set
((2)) i + AE min /,2 (4p)) 0(1/e").
8M (f(x(())
8 = 0 and T
This theorem indicates that Algorithm finds nearly statiiorny point with complexity O(1/e*). To obtain a nearly e-stationary point with e S E, one only needs to replace e in Tt. and T in this theorem above by c/ max(C, 13. This will only change the constant factor in the (11/c*) complexity.
This complexity matches the hart-of-thhearr complexity by 13 54 39
6 Numerical experiments
We demonstrate the performance of the SSG method on two fairness-aware classification problems, which are instances of (T) with convex and weakly convex g's, respectively. We compare with two different double-loop inexact proximal point (IPP) methods [13] 54 [9]. The IPP method approximately solves strongly convex constrained subproblem in each outer iteration, and we use the SSG method in this paper and the ConEx method in 13 as the solvers (inner loop) because they both have the best theoretical complexity for that subproblem. We use IPP-SSG and IPP-ConEx to denote these two implementations of the IPP method. All experiments are conducted using MATLAB 2022b on a computer with the CPU 3.20GHz x Intel Core i7-8700 and 16GB memory.
6.1 Classification problem with ROC-based fairness
Given feature vector E Rd and class label b {1, [1, the goal in binary linear classification problem is to learn a model x E IR' to predict b based on the score x a. Let D = {(a,, b,)) be training set and E(.) be a convex non-increasing loss function. Model x can be learned by solving
n
L' min XEW
[(x)
= n
Σ l(bxx (1oxxaa))
ai)
(13)
where W = fx E Rd] |||| < r). Solving 13) may ensure good classification performance of x but not its fairness. Suppose there exist two additional datasets. One contains the feature vectors of protected group, denoted by D, {a ) and the other one contains the feature vectors of an unprotected group, denoted by D., = { 1h.
between these two groups using the ROC-based fairness metric proposed by [74]. Suppose set threshold 0 and classify data a as positive x a 2 9 and as negative otherwise. The ROC-based fairness measure and its continuous approximation are defined
Ji=1- We want to enhance the fairness
II I(x
a
2
I(x a.
8)
BEe
np
ny
i=1
1pp
R(x)
max
(x a
x a/ - 0)
(14)
dE
Up
Tuu
where = =xp)==x) exp(=)) is the sigmoid function and a finite set of thresholds. If the value of this measure is small, model x produces similar predicted positive rates for the protected and unprotected groups on various f's, indicating the fairness of the model. To obtain a fair x, we balance 133 and [4] by solving
min R(x) s.t. L(x) S L +K. xEW
(15)
7

---

Table 1: Information of the datasets. Groups are males VS females a9a, users with age within [25, 60] VS outside [25, 60) in bank, and caucasian VS non-caucasian in COMPAS.
DATASETS
d
LABEL
GROUPS
A9A 48,842
123
INCOME
GENDER
BANK
41,188
54
SUBSCRIPTION
AGE
COMPAS
6,172
16
RECIDIVISM
RACE
a9a
bank
COMPAS
0455
8.3 static
350-diministinng
0.0
S9G diminshing
SSGdminghing
556
IPP-S8G
IPP-S3G
017
IPP-SSG
Objective
IPP-ConEx
IPP CanEx
ConEx
0.35
6:00
00:2
03
800
04
08
0435
63
03
67
5000
03
03
04
03
35
lteration
lteration
Iteration
Infeasibility
-25
38G-stafc 3SG-diminshhng
SSG-stalic
SSG static
SSG SiG-dmiiishigg
SSG-diminsning
SSG
IPP SSG
IPP-SSG
IPP-ConEx
iPP-ConEs
ConEx
35
04
85
07
21
02
63
05
68
06
04
644
Iteration
Iteration
Iteration
1.30
Near Stationarity
040
S9G-static S3G-dimirishnng
SSG-stafic static
dinishigg
607
SSG diminishing
SSG statio
1:30
(PP-88G IPP IPP-ConEs
SBG
-SS
600
4.00
0:04
000
C315
0:00
82
30
34
35
30
10
81
04
03
855
0.
07
06
13
61
34
64
06
37
03
Iteration
Iteration t
Iteration
Figure 1: Performances vs number of iterations on classification problems with ROC-based fairness.
where x is slackness parameter indicating how much we are willing to increase the classification
loss in order to reduce R(x) to obtain more fair model. Problem (15) is an instance of (1) satisfying Assumptions 3.1
and with
where 3 is defined in
Section
B.1
We solve (15) on three datasets: a9a [41], bank (56) and COMPAS [4]. The information of these
datasets is given in Table We split each dataset into subsets with ratio of 2 1. The larger
is used as ' in the constraint and the smaller set is further split into D, and D, based on a binary
group variable listed in Table
In our experiments, we choose É(z)= =1 (1- 2)+ and first solve (3) using the subgradient method with a large enough number of iterations to obtain L and solution XERM- Then set 0.001L* and r 5| XERM]] and let @ consist of 400 points equally spaced between min, XERMa; 0.5 (max, x - min, a and max; x - 0.5(max; XERMa; - min; xIRMa:).
All methods are initialized at XERM- We implemented the SSG method with both static and diminishing stepsizes. For the static stepsize, we select e, from {10 8 x 10 6 6,5 x 10 1.0-5 53 and ne from (2x 10-4 5x 10 1.100 -,003,0 x 10-3) For the diminishing stepsize, we set E; vr+1 and select E, from (5 10-5 10-1 2 x 1 5 10-1) and Eg from (0.02, 0.05, 0.1, 0.2). We
"E_ and n) vr+1
Ex
8

---

select the best set of parameters that produces the smallest objective value after 5000 iterations. For IPP, we select á from max(p, 1) x {1, 1.5, 2) for all three datasets, and the proximal point subproblem is approximately solved by SSG and ConEx both with 100 iterations. For IPP-SSG, we apply a static stepsize with 6, and тi tuned in the same way as SSG. For IPP-ConEx, following the notation in [3] we set Bg F4I 7 C1 (++11 1) and T .... and select e1 from {20, 50, 100, 200} and C2 from {0.002, 0.005, 0.01, 0.02) by the same procedure adopted by SSG.
We report the performances versus number of iterations of all methods on each dataset in Figure The performances versus the used CPU time will be given in Section C in the Appendix. For SSG, the æ-axis represents the total number of iterations while, for IPP, represents the total number of inner iterations across all outer iterations. The y-axis in each row represents the objective value, infeasibility and near stationarity achieved at each iteration, respectively. To measure near stationarity, we solve (3) with x x(() and parameters 7 using the SSG method with 2500 iterations and use the last iterate an approximation of {(x()). We make sure that the change of [x(((()) x(1| is less than 1 1% if the number of iterations is increased to 5000. Then plot [|x(x(()
( as near stationarity in Figure 1 Since computing x(x()) with a high precision for each time-consuming. we only report near stationarity at 100 equally spaced iterations.
According to Figure the SSG method with diminishing stepsize has the best performance on all three datasets in the sense that it reduces the objective value and the (approximate) near stationarity measure faster than others while keeping the solutions nearly feasible. However, the SSG method with a static stepsize is not always better than the IPP methods. This is consistent with our theoretical finding that the SSG and IPP methods have the same oracle complexity.
6.2 Classification problem with demographic parity
Following the notation in the previous subsection, we consider a binary classification problem with a constraint enforcing demographic parity [I] The measure of demographic parity and its continuous approximation are
a
2 0)
T(x a. 2 0) Rs Ro(x)
=
1 nip Σ
(x a
1 nu Σ
[x(xTaa)
a
- (16)
7hp
Th
(x) is small, model produces similar predicted positive rates for the protected and unprotected groups. To obtain a fair x, we balance (13) and (16) by solving
Fairness measure (x( is special case of R(x) with θ (0). If Ro
min [xx) + XSCAD(x) s.t. Ro(x)= S K.
(17)
Different from 13 the fairness measure is used as the constraint in (17) while the objective function becomes the empirical hinge loss plus the smoothly clipped absolute deviation (SCAD) regularizer [35] for promoting a sparse solution. Here, is a regularization parameter and
2 2/z
0
xz
<
SCAD(x) = Σ s(z,),
s(xx) =
- ? +
+
(18)
3
2 2<
We prove in Section B.T that 17 is an instance of ( satisfying Assumptions p max (2), where, 3 is defined in (77 in Section B.1
3.1 and 5.1 with
We set = 0.2 for all datasets and set ς. = 0.005, 0.02 and 0.02 for a9a, bank and COMPAS, respectively. For SSG, we select 6, from {10-6,2 -,2 10-6 x 10-6, 10-6) and select from (10-4,2 x 10-1,5 10-1, 7.5 x 10-4) for 7 while set n/-- = g(x(())/ll() select the best set of parameters that produces the smallest objective value after 50000 iterations. For IPP, we select ` from max(p. 1) {1, 1.5,2) and the proximal point subproblem is approximately solved by SSG and ConEx both with 600 iterations. For IPP-SSG, we apply a static stepsize with e, and T/ tuned in the same way as SSG. For IPP-ConEx, following the notation in [3). we set 0, ++11 7) (t 1) and T. = + and select from {20, 50, 100, 200} and from (0.002, 0.005, 0.01, 0.02) by the same procedure adopted by SSG. Due to the limit of space, we present the performances vs number of iterations and CPU runtime of all methods in Figure and Figure 4 respectively in Section Ci the Appendix.
for 1 E J. We

---

7 Conclusion
We study the oracle complexity of the switching subgradient (SSG) method for finding nearly c-stationary point of a non-smooth weakly convex constrained optimization problem. We show that the complexity of the SSG method matches the best result in literature that achieved only by double-loop methods. On the contrary, the SSG method is single-loop and easier to implement with reduced tuning effort. This is the first complexity result for a single-loop first-order method for weakly-convex non-smooth constrained problem.
Acknowledgements
This work was supported by NSF award 2147253.
References
[1] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. A reductions approach to fair classification. In International Conference on Machine Learning. pages 60-69. PMLR, 2018.
[2] Ahmet Alacaoglu, Yura Malitsky, and Volkan Cevher. Convergence of adaptive algorithms for constrained weakly convex optimization. Advances in Neural Information Processing Systems, 34:14214-14225, 2021.
[3] Mohammad S. Alkousa. On modification of an adaptive stochastic mirror descent algorithm for convex optimization problems with functional constraints. In Computational Mathematics and Applications, pages 47-63. Springer, 2020.
[4] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. ProPublica, May, 23, 2016.
[5] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1-2):165 2023.
[6] Alfred Auslender. An extended sequential quadratically constrained quadratic programming algorithm for nonlinear, semidefinite, and second-ordes cone programming. Journal of Opti- mization Theory and Applications, 156(2):183-2) 2013.
[7] Anastasia Bayandina, Pavel Dvurechensky, Alexander Gasnikov, Fedor Stonyakin, and Alexan- der Titov. Mirror descent and convex optimization problems with non-smooth inequality constraints. In Large-Scale and Distributed Optimization, pages 181-213. Springer, 2018.
[8] Albert S. Berahas, Frank E. Curtis, Michael J. O' O'Neil, and Daniel P. Robinson. A stochastic sequential quadratic optimization algorithm for nonlinear equality constrained optimization with rank-deficient jacobians. arXiv preprint arXiv:2106. 110.::2000..305.. 2021.
[9] Albert S. Berahas, Frank E. Curtis, Daniel Robinson, and Baoyu Zhou Sequential quadratic optimization for nonlinear equality constrained stochastic optimization. SIAM Journal on Optimization, 31(2):335--1379, 2021.
[10] Albert S. Berahas, Miaolan Xie, and Baoyu Zhou. A sequential quadratic programming method with high probability complexity bounds for nonlinear equality constrained stochastic optimization. arXiv preprint arXiv:2301.00477 2023.
[11] Jérôme Bolte and Edouard Pauwels. Majorization
Majorization-mininie minimization procedures and convergence of sqp methods for semi-algebraic and tame programs. Mathematics of Operations Research, 41(2):442 465, 2016.
[12] Digvijay Boob, Qi Deng, and Guanghui Lan. Level constrained first order methods for function constrained optimization. arXiv preprint 22XV:2205.08011. 2022.
10

---

[13] Digvijay Boob, Qi Deng, and Guanghui Lan. Stochastic first-order methods for convex and nonconvex functional constrained optimization. Mathematical Programming, 197(1):215-279, 2023.
[14] Digvijay Boob, Qi Deng. Guanghui Lan, and Yilin Wang. A feasible level proximal point method for nonconvex sparse constrained optimization. Advances in Neural Information Processing Systems. 33:16773-16784 2020.
[15] Morteza Boroun and Afrooz Jalilzadeh. Inexact-proximms accelerated gradient method for stochastic nonconvex constrained optimization problems. In 2021 Winter Simulation Conference (WSC), pages 1- IEEE, 2021.
[16] James V. Burke. A sequential quadratic programming method for potentially infeasible math- ematical programs. Journal of Muthematical Analysis and Applications, 139(():319-351, 1989.
[17] Coralia Cartis, Nicholas L.M. Gould, and Philippe L. Toint. On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming, SIAM Journal on Optimization, 2 21(4):1721-1734 2011.
[18] Coralia Cartis, Nicholas I.M. Gould, and Philippe L. Toint. Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization. Journal of Complexity, 53:68-94, 2019.
[19] Lesi Chen, Jing Xu, and Luo Luo. Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization. arXiv preprint arXiv:2301.066: 006428, 2023.
[20] Yi Cheng, Guanghui Lan, and H. Edwin Romeijn. Functional constrained optimization for risk aversion and sparsity control. arXiv preprint arXiv:2210.05108, 2022.
[21] Frank E. Curtis, Michael J. O'Neill, and Daniel Robinson. Worst-case complexity of an sqp method for nonlinear equality constrained stochastic optimization. arXiv preprint 12X7:2 2021.
[22] Frank E. Curtis, Daniel P. Robinson, and Baoyu Zhou Inexact sequential quadratic optimization for minimizing a stochastic objective function subject to deterministic nonlinear equality constraints. arXiv preprint arXiv: 207X::2007.0312... 2021.
[23] Damek Davis and Dmitriy Drusvyatskiy, Complexity of finding near-stationary points of convex functions stochastically. arXiv preprint arXiv: 1rXiv:1802.088566 2018
[24] Damek Davis and Dmitriy Drusvyatskiy. Stochastic subgradient method converges at the rate o(k-1/4) weakly convex functions. arXiv preprint arXiv:/802.02298 2018.
[25] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207-233 2019.
[26] Damek Davis, Dmitriy Drusvyatskiy, Kellie J. MacPhee, and Courtney Paquette. Subgradient methods for sharp weakly convex functions. Journal of Optimization Theory and Applications, 179(3):962-988 2018.
[27] Damek Davis and Benjamin Grimmer. Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM Journal Optimization, 29(8):1908-1999 2019.
[28] Qi Deng and Wenzhi Gao. Minibatch and momentum model-based methods for stochastic weakly convex optimization. Advances in Neural Information Processing Systems, 34:23115- 23127, 2021.
[29] Gianni Di Pillo and Luigi Grippo. On the exactness class of nondifferentiable penalty functions. Journal of Optimization Theory and Applications, 57(3):399-410 1988.
[30] Gianni Di Pillo and I Luigi Grippo. Fxact penalty functions in constrained optimization. SIAM Journal Control and Optimization, 27(6))1333-111 1989.

---

[31] Yoel Drori and Ohad Shamir. The complexity of finding stationary points with stochastic gradient descent. In International Conference on Machine Learning, pages 3658-2663 PMLR, 2020.
[32] Dmitriy Drusvyatskiy and Courtney Paquette. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming, 178(1-2):503-55)) 558, 2019.
[33] Ivan Ivanovich Eremin. The relaxation method of solving systems of inequalities with convex functions on the left-hand side. In Doklady Akademii Nauk, volume 160, pages 994-996. Russian Academy of Sciences, 1965.
[34] Francisco Facchinei, Vyacheslav Kungurtsev, Lorenzo Lampariello, and Gesualdo Scutari. Ghost penalties in nonconvex constrained optimization: Diminishing stepsizes and iteration complexity. Mathematics of Operations Research, 46(2):595-627, 2021.
[35] Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association, 134856): 2001.
[36] Roger Fletcher. An & penalty method for nonlinear constraints. In Numerical optimization 1984, pages 26-40. SIAM Publications Philadelphia, 1985.
[37] Wenbo Gao, Donald Goldfarb, and Frank E. Curtis. Admm for multiaffine constrained opti- mization. Optimization Methods and Software, 35(2)3257-333, 2020.
[38] Mingyi Hong, Zhi-Quan Luo, and Meisam Razaviyayn. Convergence analysis of alternat- ing direction method of multipliers for family of nonconvex problems. SIAM Journal on Optimization, 26(1):337-364 2016.
[39] Zhichao Jia and Benjamin Grimmer. First-order methods for nonsmooth nonconvex functional constrained optimization with or without slater points. arXiv preprinl arXiv:2212.00922. 2022.
[40] Lingzi Jin and Xiao Wang. A stochastic primal-dual method for class of nonconvex constrained optimization. Computational Optimization and Applications, 83(1):143-18)) 2022.
[41] Ron Kohavi et al. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In KDD, volume 96, pages 202-207, 1996.
[42] Weiwei Kong. Jefferson G. Melo, and Renato D.C. Monteiro. Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs. SIAM Journal on Optimization, 29(4):2566-259) 2019.
[43] Weiwei Kong, Jefferson G. Melo, and Renato D.C. Monteiro. Iteration complexity of a proximal augmented lagrangian method for solving nonconvex composite optimization problems with nonlinear convex constraints. Mathematics of Operations Research, 48(2):1066-109: 2023.
[44] Weiwei Kong, Jefferson G. Melo, and Renato D.C. Monteiro. Iteration complexity of an inner accelerated inexact proximal augmented lagrangian method based on the classical lagrangian function. SIAM Journal Optimization, 33(1):181-210, 2023.
[45] Weiwei Kong and Renato D.C. Monteiro. An accelerated inexact dampened augmented la- grangian method for linearly-constrained nonconvex composite optimization problems. Compu- Iational Optimization and Applications, 85(2):509-545, 2023.
[46] Guy Kornowski and Ohad Shamir. Oracle complexity in nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 34:324-334, 2021.
[47] Guy Kornowski and Ohad Shamir. On the complexity of finding small subgradients in nons- mooth optimization. arXiv preprins 10346: 2022.
[48] Guanghui Lan, Arkadi Nemirovski, and Alexander Shapiro. Validation analysis of mirror
descent stochastic approximation method. Mathematical Programming, 134(2)4255-58,, 2012.
[49] Guanghui Lan and Zhiqiang Zhou. Algorithms for stochastic optimization with function or expectation constraints. Computational Optimization and Applications, 76(2):461-499 2020.
12

---

[50] Zichong Li, Pin-Yo Yu Chen, Sijia Liu, Songtao Lu, and Yangyang Xu. Rate- cate-improved inexact aug- mented lagrangian method for constrained nonconvex optimization. In International Conference on Artificial Intelligence and Statistics, pages 2170-2178. PMLR, 2021.
[51] Zichong Li, Pin- Yu Chen, Sijia Liu, Songtao Lu, and Yangyang Xu. Zeroth-order optimization for composite problems with functional constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7453-7461, 2022.
[52] Zichong Li and Yangyang Xu. Augmented lagrangian- based first-order methods for convex- constrained programs with weakly convex objective. INFORMS Journal on Optimization. 3(4):373-397 2021.
[53] Qihang Lin, Runchao Ma, and Yangyang Xu. Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization. Computational Optimization and Applications, 82(1):175-224, 2022.
[54] Runchao Ma, Qihang Lin, and Tianbao Yang. Quadratically regularized subgradient methods for weakly convex optimization with weakly convex constraints. In International Conference on Machine Learning, pages 6554-6564. PMLR, 2020.
[55] Jefferson G. Melo, Renato D.C. Monteiro, and Hairong Wang. Iteration Iteration-complet complexity of an inexact proximal accelerated augmented lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems. arXiv preprini 200iv:2006.08045 2020.
[56] Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22-33 31, 2014.
[57] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574- 1609, 2009.
[58] Yurii Nesterov. Lectures convex optimization, volume 137, Springer, 2018.
[59] Boris T. Polyak. A general method of solving extremum problems. Soviet Mathematics Doklady, 8(3):593-597 1967.
[60] Boris Polyak. Minimization of unsmooth functionals. USSR Computational Mathematics and Mathematical Physics, 933):14-29, 1969.
[61] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakly-convex--oncaae min- max optimization: provable algorithms and applications in machine learning. Optimization Methods and Software, 1087-11111 2022.
[62] Philippe Rigollet and Xin Tong. Neyman-pearson classification, convexity and stochastic constraints. Journal of Machine Learning Research, 12:2831-2855, 2011.
[63] Mehmet Fatih Sahin, Ahmet Alacaoglu, Fabian Latorre, Volkan Cevher, et al. An inexact aug- mented lagrangian framework for nonconvex optimization with nonlinear constraints. Advances in Neural Information Processing Systems, 32:13966-13372 2019.
[64] Ohad Shamir. Can we find cear-approximmateeyy-ttatio functions? arXiv preprint arXiv:2002.11966 2020.
points of nonsmooth nonconvex
[65] Fedor S. Stonyakin, Mohammad S. Alkousa, Alexey N. Stepanov, and Alcksandr A. Titov, Adaptive mirror descent algorithms for convex and strongly convex optimization problems with functional constraints. Journal of Applied and Industrial Mathematics, 13(3):577-57,, 2019.
[66] Fedor S. Stonyakin, Mohammad S. Alkousa, Alexander A. Titov, and Victoria V. Piskunova. On some methods for strongly convex optimization problems with one functional constraint. In International Conference on Mathematical Optimization Theory and Operations Research, pages 82-96. Springer, 2019.
[67] Fedor S. Stonyakin, Alexey N. Stepanov, Alexander A. Titov, and Alexander V. Gasnikov. Mirror descent for constrained optimization problems with large subgradient values. arXiv preprint a9Xiv: 00218, 2019.
13

---

[68] Fedor S. Stonyakin and Alexander A. Titov. One mirror descent algorithm for convex constrained optimization problems with non-standard growth properties. arXiv preprint arXiv: 1803.01399 2.
[69] Arnesh Sujanani and Renato D.C. Monteiro. An adaptive superfast inexact proximal augmented lagrangian method for smooth nonconvex composite optimization problems. Journal of Scientific Computing, 97(2):34, 2023.
[70] Lai Tian and Anthony Man-Cho So. Computing goldstein (c, -staatiarry points of lip- schitz functions in ( iterations via random conic perturbation. arXiv preprint arXiv:2112000002, 2021.
[71] Lai Tian, Kaiwen Zhou, and Anthony Man-Cho So. On the finite-time complexity and practical computation of approximate stationarity concepts of lipschitz functions. International Conference Machine Learning, pages 21360-2111 21379. PMLR, 2022.
[72] Alexander A. Titov, Fedor S. Stonyakin, Mohammad S. Alkousa, Seydamet S. Ablaev, and Alexander V. Gasnikov. Analogues of switching subgradient schemes for relatively lipschitz- continuous convex programming problems. In International Conference Matherattcaa Optimization Theory and Operations Research, pages 133-149. Springer, 2020.
[73] Alexander A. Titov, Fedor S. Stonyakin, Alexander V. Gasnikov, and Mohammad S. Alkousa. Mirror descent and constrained online optimization problems. International Conference on Optimization and Applications, pages 64-78. Springer, 2019.
[74] Robin Vogel, Aurélien Bellet, and Stéphan Clémençon. Learning fair scoring functions: Bipartite ranking under roc-based faimess constraints. In International Conference on Artificial Intelligence and Statisties, pages 784-792. PMLR, 2021.
[75] Yu Wang, Wotao Yin, and Jinshan Zeng. Global convergence of admm in nonconvex nonsmooth optimization. Journal of Scientific Computing, 78(1):29 63, 2019.
[76] Tianbao Yang and Qihang Lin. RSG: Beating subgradient method without smoothness and strong convexity. Journal of Machine Learning Research, 19())2236-268, 2018.
[77] Muhammad Bilal Zafar, Isabel Valera, Manuel GomezzRodriguez, and Krishna P. Gummadi. Fairness constraints: A flexible approach for fair classification. Journal of Machine Learning Research, 20(1)2737--278, 2019.
[78] Jinshan Zeng, Wotao Yin, and Ding- Xuan Zhou. Moreau envelope augmented lagrangian method for nonconvex optimization with linear constraints. Journal of Scientific Computing, 91(2):61, 2022.
[79] Jiawei Zhang and Zhi-Quan Luo. A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization. SIAM Journal on Optimization, 30(3):222--2302. 2020.
[80] Jiawei Zhang and Zhi-Quan Luo. A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization. SIAM Journal on Optimization, 32(3):2319 2346, 2022.
[81] Jiawei Zhang, Wenqiang Pu, and Zhi-Quan Luo. On the iteration complexity of smoothed proximal alm for nonconvex optimization problem with convex constraints. arXiv preprint arXiv:2207.06304, 2022.
[82] Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference on Machine Learning, pages 11173-11182 PMLR, 2020.
[83] Siqi Zhang and Niao He. On the convergence rate of stochastic mirror descent for nonsmooth nonconvex optimization. arXiv preprint arXiv:1806.00/73 2018.
14


Reviews:
[{"review_id": "14N16Yu0wp", "reviewer": "Reviewer_aPsS", "summary": "This paper examines the oracle complexity of the switching subgradient method used for solving non-convex constrained optimization problems. The target functions are weakly convex, while the constraint functions are either convex or weakly convex. Remarkably, this method matches the complexity of double-loop methods while only necessitating a single loop implementation.\n\n", "questions": "Assumption 4.1. assumes the boundedness of the solution, is this easily satisfied in practical scenarios?  Moreover,  should you include such a constraint in your second application?\n\n\n\nCan you extend your algorithm for weakly convex problems with linear equality constraints?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors have produced a commendable piece of work in the domain of weakly convex optimization, a specific category of nonconvex problems noted for its favorable theoretical convergence attributes. Although there is an abundance of single-loop algorithms such as subgradient or proximal point for weakly convex optimization, much of the existing literature has focused on unconstrained or simply-constrained issues. It is therefore somewhat unexpected that there are no analogous results in functionally constrained settings. Seen in this light, the technical novelty and contribution of this paper are remarkable.", "weaknesses": "While the authors have provided a comprehensive review of the literature, there seems to be an overemphasis on marginally relevant references. The broad coverage of optimization beyond weakly convex settings, although interesting, does not directly contribute to the key message of the paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for reviewing our paper and providing valuable feedback that helps us further improve our work!\n\n**Comment: ... there seems to be an overemphasis on marginally relevant references. The broad coverage of optimization beyond weakly convex settings, although interesting, does not directly contribute to the key message of the paper.**\n\nIn the revision, we will remove some marginally relevant references in the section of related works, for examples, the ones assuming smoothness, because weak convexity is more interesting when the problem is non-smooth.\n\n**Comment: Assumption 4.1. assumes the boundedness of the solution, is this easily satisfied in practical scenarios?**\n\nIt depends on the applications. To train a real-world machine learning model, one can artificially add a ball constraint as a regularization technique to avoid overfitting. For example, in application (15) in Section 6.1, we add the constraint set $\\mathcal{X}=\\\\{\\mathbf \n x\\in\\mathbb{R}^{d}|\\\\|\\mathbf x\\\\|\\leq r\\\\}$, which guarantees the boundedness of the feasible set. In practical scenarios, one can use cross validation to choose $r$ if necessary. \n\nIf we do not want to assume $\\mathcal{X}$ is bounded, we can replace Assumption 4.1.C with the following assumption.\n\n*C'. There exists $D\\in\\mathbb{R}$ such that $\\\\|\\mathbf{x}-\\mathbf{x'}\\\\|\\leq D$ for any $\\mathbf{x}$ and $\\mathbf{x'}$ in $\\mathcal{S}:=\\\\{\\mathbf{x}\\in\\mathcal{X}|g(\\mathbf{x})\\leq 0\\\\}$.*\n\nHere, $\\mathcal{S}$ is the feasible set. This assumption does not require a bounded $\\mathcal{X}$. For example, when $\\mathcal{X}=\\mathbb{R}^d$, this new assumption means $g$ has a bounded $0$-sublevel set. One example satisfying this assumption is $g(\\mathbf{x})=\\\\|\\mathbf{A}\\mathbf{x}-\\mathbf{b}\\\\|_p-c\\leq0$ where $\\mathbf{A}$ has a full column rank and $p\\geq 1$.  With this change to Assumption 4.1., we can still obtain the same complexity for the SSG method. We will include this new result in the revision. \n\nHowever, if we simply drop the boundedness assumption (Assumption 4.1.C) without making any alternative assumptions, we are unable to prove the same convergence results. This is because this boundedness assumption is critical for ensuring the Lagrangian multiplier $\\widehat\\lambda_t$ is bounded for all $t$ (see Lemma 4.2.) which is needed to prove the desired convergence rates. This boundedness assumption is also made in other papers on non-smooth non-convex constrained optimization, e.g., [14] and [58].\n\n**Comment: Moreover, should you include such a constraint in your second application?**\n\nWe do not need to include such a constraint in the second application, i.e., problem (17). From the theoretical perspective, we have proved in Section B.1.1 in the appendix that (17) satisfies Assumption 5.1, which does not require a bounded $\\mathcal{X}$, so we can just let $\\mathcal{X}=\\mathbb{R}^d$ and apply the convergence result in Theorem 5.6 based on Assumption 5.1. From the modeling perspective, (17) has already the regularization term $\\text{SCAD}(\\mathbf x)$ in the objective function. Hence, there is no need to add a ball constraint for the regularization purpose.\n\n**Comment: Can you extend your algorithm for weakly convex problems with linear equality constraints?**\n\nWe consider two cases in this paper: (1) $g$ is convex; (2) $g$ is weakly convex. In the first case, we can extend our algorithm and theory to allow linear equality constraints. More specifically, we can extend our results to the problem\n\n$\\min_{\\mathbf x\\in\\mathcal{X}}f(\\mathbf x) \\quad \\text{s.t.} \\quad h(\\mathbf x)\\leq 0,\\quad \\mathbf A\\mathbf x=\\mathbf b,$ \n\nwhere $f$ is weakly convex and $h$ is convex. Then we still assume Assumption 4.1 except that 4.1B is changed to  \n\n*B'. There exists $\\mathbf x_{\\text{feas}}\\in\\text{int}(\\mathcal{X})$ such that $h(\\mathbf x_{\\text{feas}})<0$ and  $ \\mathbf A\\mathbf x_{\\text{feas}}=\\mathbf b$..*\n\nIn this case, we only need to implement Algorithm 1 with $g(\\mathbf x):=\\max\\\\{h(\\mathbf x), \\\\|\\mathbf A \\mathbf x-\\mathbf b\\\\|_\\infty\\\\}$. It is known that Slater's condition allows the present of linear equality constraints. This is why we only need $h$ to be strictly feasible. \nUsing this fact, we can still obtain an upper bound of the Lagrangian multiplier similar to Lemma 4.2. Then Theorem 4.3 can be proved in the same way as before using this new upper bound. We will include this new result in the revision. \n\n\nIn the second case where $g$ is weakly convex, although we can still implement Algorithm 1 with the new $g$ defined above, we cannot extend the complexity theorem, i.e., Theorem 5.6, with linear equality constraints, unfortunately. "}, {"review_id": "iuaYKjy4aL", "reviewer": "Reviewer_tsNX", "summary": "The paper considers a weakly-convex constrained optimization problem and establishes the oracle complexity of the switching subgradient method for finding a nearly stationary point.", "questions": "Can the analysis be extended to the case when Assumption 4.1 C is removed (for example, when $\\mathcal X$ is unbounded)? \n\n", "limitations": "n.a.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Considering a single-loop algorithm, the paper can establish the complexity $O(1/\\epsilon^4)$ for a case of weakly-convex constraint. This is a nice result. \n\n2. The paper has a rigorous convergence analysis. ", "weaknesses": "In the numerical experiments, the paper compares a single-loop method with double-loop methods but reports the evolution of objective functions over iterations. This is not fair. The evolution over time should be reported. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for reviewing our paper and providing valuable feedback that helps us further improve our work!\n\n**Comment: In the numerical experiments, the paper compares a single-loop method with double-loop methods but reports the evolution of objective functions over iterations. This is not fair. The evolution over time should be reported.**\n\nAs the reviewer suggested, we have produced the figures showing how the objective value, infeasibility and stationarity measure evolve with CPU time in each algorithm. Please find the figures in the PDF file we submitted for this rebuttal. We will also include them in the revision of this manuscript. \n\nComparing the plots in iterations and the plots in CPU time, we find that the curves of our SSG methods and the IPP-SSG method are almost unchanged, but the curve of the IPP-ConEx method becomes worse when plotted in CPU time. This is because the SSG and IPP-SSG methods only need to compute either $\\mathbf{\\zeta}_f^{(t)}$ or $\\mathbf{\\zeta}_g^{(t)}$ in each (inner) iteration while IPP-ConEx has to compute both $\\mathbf{\\zeta}_f^{(t)}$ and $\\mathbf{\\zeta}_g^{(t)}$ per inner iteration and thus induces additional computation cost. This suggests that the SSG methods we study are more efficient than the primal-dual methods like IPP-ConEx in computation time because the former computes fewer subgradients per iteration.  \n\n**Comment: Can the analysis be extended to the case when Assumption 4.1 C is removed (for example, when $\\mathcal{X}$ is unbounded)?**\n\nIf we do not want to assume $\\mathcal{X}$ is bounded, we can replace Assumption 4.1.C with the following assumption.\n\n*C'. There exists $D\\in\\mathbb{R}$ such that $\\\\|\\mathbf{x}-\\mathbf{x'}\\\\|\\leq D$ for any $\\mathbf{x}$ and $\\mathbf{x'}$ in $\\mathcal{S}:=\\\\{\\mathbf{x}\\in\\mathcal{X}|g(\\mathbf{x})\\leq 0\\\\}$.*\n\nHere, $\\mathcal{S}$ is the feasible set.  This assumption does not require a bounded $\\mathcal{X}$. For example, when $\\mathcal{X}=\\mathbb{R}^d$, this new assumption means $g$ has a bounded $0$-sublevel set. One example satisfying this assumption is $g(\\mathbf{x})=\\\\|\\mathbf{A}\\mathbf{x}-\\mathbf{b}\\\\|_p-c\\leq0$ where $\\mathbf{A}$ has a full column rank and $p\\geq 1$.  With this change to Assumption 4.1., we can still obtain the same complexity for the SSG method. We will include this new result in the revision. \n\nHowever, if we simply drop the boundedness assumption (Assumption 4.1.C) without making any alternative assumptions, we are unable to prove the same convergence results. This is because this boundedness assumption is critical for ensuring the Lagrangian multiplier $\\widehat\\lambda_t$ is bounded for all $t$ (see Lemma 4.2.) which is needed to prove the desired convergence rates. This boundedness assumption is also made in other papers on non-smooth non-convex constrained optimization, e.g., [14] and [58]."}, {"review_id": "EsmZSlSTIK", "reviewer": "Reviewer_DHUQ", "summary": "This paper studies switching subgradient method for solving weakly-convex objective (weakly-)convex constrained problems. The oracle complexity for finding a nearly stationary point is derived for both convex constraint case and weakly-convex constrained (with good initialization). Numerical experiments validate the efficiency of the proposed algorithms on classical machine learing tasks.", "questions": "1. For the weakly-convex constrained case, if we cannot have feasible initial point, does the algorithm SSG converge? If so, what kind of point will it arrive? As we know, it is usually a NP-hard problem to obtain a feasible point for nonconvex constraint. In this case, does the SSG converge to the stationary point satisfying $0\\in \\partial (f+1_{\\mathcal{X}\\cap [g\\leq0]})(x)$?\n2. In Assumption 4.1, it is assumed that the Slater's condition holds. Does it mean that we cannot include the equality constraint $g(x)=0$ for the following analysis?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is overall well written. It is the first single-loop first-order method handling a weakly-convex objective (weakly-)convex constrained problems, which is much convenient to implement compared to double-loop algorithms. The theoretical complexity result is clearly stated and competitive with sound proofs.", "weaknesses": "No obvious weaknesses and please see the questions part for some detailed comments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for reviewing our paper and providing valuable feedback that helps us further improve our work! \n\n**Question 1: For the weakly-convex constrained case, if we cannot have feasible initial point, does the algorithm SSG converge? If so, what kind of point will it arrive? As we know, it is usually a NP-hard problem to obtain a feasible point for nonconvex constraint. In this case, does the SSG converge to the stationary point satisfying $0\\\\in\\\\partial(f+1_{\\mathcal{X}\\cap[g\\leq0]})(\\mathbf{x})$?**\n\nIf we don't have a feasible initial point, the SSG method will still converge but it will not necessarily converge to an nearly $\\\\epsilon$-stationary point under our definition. Instead, it may converge to an infeasible and nearly stationary point of $g$, namely, a point $\\\\mathbf{x}\\in\\mathcal{X}$ that satisfies $0\\\\in\\\\partial(1_{\\mathcal{X}}+g)(\\mathbf{x})$ but has $g(\\mathbf{x})$ significantly larger than $0$. At this point, the subgradient $\\partial 1_{\\mathcal{X}\\cap[g\\leq0]}(\\mathbf{x})$ the reviewer conjectured is not defined. \n\nThis phenomenon can explained by the design of the SSG algorithm. In fact, if $\\mathbf{x}^{(t)}$ is very infeasible so $g(\\mathbf{x}^{(t)})>\\epsilon_t$, the SSG method will keep using the subgradient of $g$ to update $\\mathbf{x}^{(t)}$. Until $g(\\mathbf{x}^{(t)})\\leq\\epsilon_t$, the SSG method is equivalent to the subgradient descend method applied to $\\min_{\\mathbf{x}\\in\\mathcal{X}} g(\\mathbf{x})$. Since $g$ is non-convex, the subgradient descend method may fail to reduce $g$ to zero so $g(\\mathbf{x}^{(t)})\\leq\\epsilon_t$ may never happen, but the subgradient descend method can at least ensure  $\\mathbf{x}^{(t)}$ converge to a nearly stationary point of $g$. Please note that, in this scenario, the subgradient of $f$ is never used so $f$ has zero influence on where $\\mathbf{x}^{(t)}$ converges to. \n\nFrom the explanation above, we also know that non-convex constrained optimization is intractable if the initial solution can be anywhere. Please consider problem $\\min_{x} -(x-1)^3 \\text{s.t.} (x-1)^3+1\\leq 0 $. Here, $x=1$ is an infeasible point but the gradients of the objective and the constraint functions are both zero at this point. In other words, if $x=1$ is the initial solution, all gradient-based methods will get stuck at this infeasible solution. \n\n**Question 2: In Assumption 4.1, it is assumed that the Slater's condition holds. Does it mean that we cannot include the equality constraint $g(x)=0$ for the following analysis?**\n\nWe can modify Assumption 4.1 to allow linear equality constraints like $\\mathbf{A}\\mathbf{x}=\\mathbf{b}$ but not a nonlinear equality constraint like $g(\\mathbf x)=0$. Under Assumption 4.1, the constraint is convex, but adding a nonlinear equality constraint will make the constraint non-convex, which will require a different analysis (e.g. the analysis in Section 5).\n\nLet me provide some details on how we can extend our algorithm and theory to allow linear equality constraints. More specifically, we can extend our results to the problem\n\n$\\min_{\\mathbf x\\in\\mathcal{X}}f(\\mathbf x) \\quad \\text{s.t.} \\quad h(\\mathbf x)\\leq 0,\\quad \\mathbf A\\mathbf x=\\mathbf b,$ \n\nwhere $f$ is weakly convex and $h$ is convex. Then we still assume Assumption 4.1 except that 4.1B is changed to  \n\n*B'. There exists $\\mathbf x_{\\text{feas}}\\in\\text{int}(\\mathcal{X})$ such that $h(\\mathbf x_{\\text{feas}})<0$ and  $ \\mathbf A\\mathbf x_{\\text{feas}}=\\mathbf b$..*\n\nIn this case, we only need to implement Algorithm 1 with $g(\\mathbf x):=\\max\\\\{h(\\mathbf x), \\\\|\\mathbf A \\mathbf x-\\mathbf b\\\\|_\\infty\\\\}$. It is known that Slater's condition allows the present of linear equality constraints. This is why we only need $h$ to be strictly feasible. \nUsing this fact, we can still obtain an upper bound of the Lagrangian multiplier similar to Lemma 4.2. Then Theorem 4.3 can be proved in the same way as before using this new upper bound. We will include this new result in the revision. "}]

Author rebuttal:
We would like to thank all reviewers for reviewing our submission and providing valuable feedbacks. We have provided answers to each reviewer's questions separately. Reviewer tsNX suggested us to report the evolutions of the curves over time instead of over iterations. We have included the new figures in the uploaded PDF file with this rebuttal. 

Meta-review: All reviewers are positive about this paper and want to see it accepted. I went quickly over the paper and the main contributions myself and I find it interesting and thus further support acceptance. Please take into account the reviewers comments when preparing the final version.
Decision: Accept (poster)