SAPD+: An Accelerated Stochastic Method for Nonconvex-Concave Minimax Problems
Authors: Xuan Zhang
Necdet Aybat
Mert Gurbuzbalaban
Venue: NeurIPS 2022 Accept (2022)
Keywords: saddle point problems
nonconvex optimization
stochastic gradient
accelerated methods

Abstract: We propose a new stochastic method SAPD+ for solving nonconvex-concave minimax problems of the form $\min\max\mathcal{L}(x,y)=f(x)+\Phi(x,y)-g(y)$, where $f,g$ are closed convex and $\Phi(x,y)$ is a smooth function that is weakly convex in $x$, (strongly) concave in $y$. For both strongly concave and merely concave settings, SAPD+ achieves the best known oracle complexities of $\mathcal{O}(L\kappa_y\epsilon^{-4})$ and $\mathcal{O}(L^3\epsilon^{-6})$, respectively, without assuming compactness of the problem domain, where $\kappa_y$ is the condition number, and $L$ is the Lipschitz constant.  We also propose SAPD+ with variance reduction, which enjoys the best known oracle complexity of $\mathcal{O}(L\kappa_y^2\epsilon^{-3})$ for weakly convex-strongly concave setting. We demonstrate the efficiency of SAPD+ on a distributionally robust learning problem with a nonconvex regularizer and also on a multi-class classification problem in deep learning.

SAPD+ : An Accelerated Stochastic Method for Nonconvex-Concave Minimax Problems
Xuan Zhang Department of Industrial and Manufacturing Engineering Pennsylvania State University University Park, PA,USA. xxz358@psu.edu
Needet Serhat Aybat
Department of Industrial and Manufacturing Engineering Pennsylvania State University University Park, PA,USA. nsa100psu.cm edu
Mert Gürbüzzalaban
Department of Management Science and Information Systems
Rutgers University Piscataway, NJ, USA mg1366erutgers. edu
Abstract
We propose a new stochastic method SAPD+ for solving nonconvex-concays mini- max problems of the form min max L(x, y) = f(x) + & y) gly). where fig are closed convex and (xx y) is a smooth function that is weakly convex in x, (strongly) concave in y. For both strongly concave and merely concave settings, SAPD+ achieves the best known oracle complexities of OLLKg +) and O(L ), respectively, without assuming compactness of the problem domain, where Ky the condition number and I. is the Lipschitz constant. We also propose SAPD+ with variance reduction, which enjoys the best known oracle complexity of ( for weakly convex-strongly concave setting. We demonstrate the efficiency of SAPD+ on a distributionally robust learning problem with nonconvex regularizer and also on a multi-class classification problem in deep learning.
Introduction
We consider the following saddle-point (SP) problem:
min max C(x, y) è f(x) ((x, v) g(v),
(1)
# yE>
where X' and y and m dimensional Euclidean spaces, the function + X' y - R is smooth and possibly nonconvex in X' and -troongy concave in y E y for some H, 2 0 -with the convention that for H, = 0, & is merely concave (MC) in y, and the functions f and g closed, convex and possibly nonsmooth. In this paper, we consider a particular case of nonconvexity, i.c., assume that ((.,)) v) is weakly convex (WC) for any fixed y dom g y. Weakly convex functions constitute a rich class of non-convex functions and arise naturally in many practical settings for machine learning (ML) applications [ (35, precise definitions will be given later in Section In practice, WC assumption is widely satisfied, e.g., under smoothness see remark most of
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the work in related literature considering nonconvex- (sttronlyy concave SP problems provide their analyses under the premise of weak convexity. The problem ( with Hy 0 is called a weakly convex-strongly concave (WCSC) saddle-point problem, whereas for My = 0, it is called weakly convex-merely concave (WCMC) saddle-point problem. Both problems arise frequently in many MI settings including constrained optimization of WC objectives based on Lagrangian duality [22). Generative Adversarial Networks (GAN) (where z denotes the parameters of the generator network whereas y represents the parameters of the discriminator network (3), distributional robust learning and learning
with weakly convex loss functions such as those arising in deep learning 14. 35
problems with non- non-decomposable losses
B5
There are two important settings for (T): (i) the deterministic setting, where the partial gradients of are exactly available, (ii) the stochastic setting, where only stochastic estimates of the gradients are available. Although, recent years have witnessed significant advances the deterministic setting 66 19 23 24 25
36 38; : our focus in this paper will be mainly on the stochastic setting, which is more relevant and more applicable to ML. problems. Indeed, due to large-dimensions and the sheer size of the modern datasets, computing gradients exactly is either infeasible or impractical in ML practice, and gradients are often estimated stochastically based on mini-batches (randomly sampled subset of data points) as in the case of stochastic gradient-type algorithms.
K3
There a growing literature on the WCSC and WCMC problems the stochastic setting. Several met- rics for quantifying the quality of an approximate solution to (I) have been proposed in the literature. A common way to assess the performance is to define the function ((.) max ((- y) and measure the violation of first-order necessary conditions for the non-convex problem m ((x). Given the primal iterate sequence {æ* 1k20 of stochastic SP algorithm and a threshold > 0, commonly used metric is the gradient norm of the Moreau envelope (GNME); indeed, the objective is to provide a bound K, such that B[|| (xr+))) [1x
S c for all k 2 Ke, where Φ denotes the Moreau
envelope of the primal function & -see Definitions
3 4 and 5 Another commonly used natural metric
is the gradient norm of the primal function (6-) [4 17 16 26 37,, abbreviated as GNP, where the aim is to derive K₂ such that E. [[]VV((aa)) e-first-order Nash equilibrium (FNE) and its generalized versions also exist in the literature [32 33)
S e for all k 2 K Other metrics such as the notion of
When using any of the aforementioned metrics, the ultimate goal is establish a bound on the oracle (sampling) complexity, i.e.. Ek- by. where by denotes the batch-size for iteration 2 0. For the WCSC setting. it crucial to note that GNME, GNP and FNE metrics are all equivalent in the sense that convergence in either of them implics convergence in the other two metric for WCSC problems (23) In this paper, for the WCSC setting, adopt both GNME and GNP the main performance metrics to analyze our algorithms; indeed, in Theorem 2 we show that, when the non-smooth part f() = 0, we can convert GNME guarantee GNP guarantee by incurring only little additional cost compared to the computational cost required for the GNME guarantee, and the overall worst-case complexity (in terms of worst-case dependency to the target accuracy remains the same for both metrics. When the non-smooth part f()) * O, we also obtain similar guarantees and show equivalence between the metrics based on GNME and the generalized gradient mapping. On the other hand, for the WCMC setting, we provide our guarantees in GNME metric as é is not necessarily differentiable for this scenario. Moreover, our work accounts for the individual effects of Legz Tezy: Tays and Lay. i.c., the Lipschitz constants of V Vz v). V V=, -, v (z,-) and V V,, y) (see Assumption 2). respectively, instead of using the worst-case parameters L A max m Laz, Lynn Lyy J. while the majority of related work ignore the influence of these block Lipschitz constants in their analyses. We emphasize that using the worst-case parameters will lead to theoretically conservative step sizes, and this phenomenon has been validated in the work (43
the relevant existing work for WCSC and WCMC problems closest to our setting. More specifically, in Table [ for the stochastic setting, we report the (oracle) complexity with respect to the GNP and GNME as the performance metrics for WCSC and WCMC problems, respectively, and the batch-size (number of data points in the mini-batches) required at every iteration. We also report whether the method is based on a pariance-reductio bR-based methods mentioned in Table use a small batch-size b' all iterations except for few, where they need large batch-size b 2 b' once in every q iterations. The period is equal to the number of times small batches are sampled consecutively plus one, and it is also an algorithm parameter. Therefore, for VR-methods, we report the batch size as a triplet (b', b, g). In the column "Compactness" we list whether achieving the specific complexity requires assuming compactness of the primal and/or dual domains.
Contributions.
(VR) technique.
2

---

Ref.
Complexity
Compactness
Vasea
Batchsize
Weakly Convex-Strongly Concave (WCSC) problems
Rafique
35
Olc log(e"))
O(1)
Yan al.
O(e Ole log(e
(%
O(1)
Yang et al.
4
(n,
0(1)
al.
OLLAGE
(n.
X
OnkyE" ?)
Bot and Bohm
O
(n, n)
O(syc
Huang al.
17
O uy 3)
(n,
O
) O D(Rye"1)
Huang al.
(5.3)
Luo et al.
26
O
(x,3)
O
) O ( ") O(nyc]]
Xu et al. 3
OL
(2,3)
(Nne
Ol "), ONNet
SAPD+, Theorem
OLLAye O(LAGE
(n.
0(1)
SAPD+, Theorem
(n,
( ) Olage 3), O(e
Weakly Convex-Merdl Concave (WCMC) problemss
Rafique et 33
O
Jog (Le 21)
(),))
0(1)
Bot and Bohmn
O(L'c-))
(n.y)
0(1)
al
O O(13--
(n.
0(I)
SAPD+, Theorem
(n.
0(1)
Table 1: Summary relevant work WCSC and WCMC problems. For the column "Compactness", we
use y and n to indicate when the results require compactness and when do not require it. respectively; the first argument is for primal domain and second is for dual domain. For batchsize, we use (b', b, q) format for VR-based methods to state small batch (B'), large butch (b), and frequency (ạ) employed within the algorithm.
Table notes: FFor WCSC setting, [35 assumes 2(: y) - c (.y is weakly convex and g(-) ) strongly convex. In [39]. L = & and & need not be smooth, rather second moment of stochastic subgradients is assumed to be uniformly bounded. When I-smooohh ( y) and (xx.)) are cesshiiss the results in [3 imply (T x3e "lo"""" (w/Kig
complexity. The complexity results reported here are different than those 17 [6] The issues in their proofs leading to the wrong complexity results are explained Appendix The
notation O ignores logarithmic factors.
To make the comparison of our results with the existing work casier, we provide the results in the table for the worst-case setting, where Kiy A L, and we report the e-, Ky- and L-dependency of the My complexity results for the existing algorithms. That being said, our results have finer granularity in terms of their dependence to the individual effects of Lzz, Lay Lyz and Lyy as we mentioned earlier.
Our contributions (also summarized in section
follows:
We propose a new stochastic method, SAPD+, based on the inexact proximal point method (iPPM). In this framework, one inexactly solves strongly convex-stronge concave (SCSC) saddle point sub-problems using an accelerated primal-dual method, SAPD (43). Theorem we establish an oracle complexity of O OLLxg (xxy)")) for WCSC problems, and unlike the majority of existing work we not require compactness for neither the primal nor the dual domain. To our knowledge, our bound has the best Ky dependence in the literature; indeed, prior to this work, without using variance reduction, the best known complexity was O (LLnee shown in 41 hence, we establish a (1gy) improvement.
We propose a variance-reduced version of SAPD+ in Theorem 4 For WCSC setting, SAPD+ using variance reduction achieves an oracle complexity of (T 3) -this bound has the best e-dependency in the literature to our knowledge, and among all the methods with the O(e-3) complexity, our approach has the best condition number, Ky, dependency; indeed, prior to this work, the best known complexity was ( -)); hence, we establish ((sy) factor improvement.
For the WCMC case, our proposed algorithm SAPD+ results in ( complexity, which is the best to our knowledge, improving the best known complexity by log (L/e²) factor.
Finally, demonstrate the efficiency of SAPD+ distributionally robust learning problem and also on a (worst-case) multi-class classification problem in deep learning.
Notation. Throughout the paper, || denotes the Euclidean norm. Given f R." + R U (x)) a closed convex function, prox (z) argmin,, fw) + 1 ||w x1|² denotes the proximal 2x
map of f. Given random w. let V. V, ())) and V2 w) denote unbiased estimators of (x, and (Z, Moreover, given random mini-batch B (w;),_.- we let V ())( Eh V2 wi) to denote the stochastic gradient estimate based on the batch B, and we define V, TB((s) similarly.
3

---

2 Preliminaries
We start with describing the notion of weak convexity. Definition 1. h R - RR U (+x0 is y-weakly convex if + M(x) + =/11=112 is convex.
Definition 2. A differentiable function h R > RU is L-smooth if > 0 such that for
Vx, E dom h,
Vh(2')Il - L| = z'1l-
Remark 1. If a function is L-soooth, then is also L-weakly convex.
Remark I shows that weak convexity is a rich class containing the class of smooth functions. In the rest of the paper, we consider the SP problem in T. Next, we introduce our assumptions.
Assumption 1. f X -R (+ and g: y R U (+00) are proper, closed, convex functions.
Let &b : X x y - IR be such that (i) for any y E domg C V, ((.,y) is 7-weakly convex and bounded from below; for any x E dom f C X, ((xx,)) -) is py-strongly concave for some By 2 (iti) & is disferentiable
open set containing dom f domg) g.
Assumption 2. There exist Lazy Luy 2 O, Lazs Lyz > 0 such that V ((, - (I 9) <
Lan [ =1 + Lezy bly TlI and 1V y) V (F, T)ll Lyg 1 Ill + Loyg 11 Tll for all x, B dom? f C X. and F E domg C V.
Assumption [ |lllww convexiyy in z while requiring (strong) concavity in the y variable. As- sumption 2 is standard in the analysis of first-order methods for solving SP problems. It should be noticed that when Tyzz = Tay = O, the problem in [ can be solved separately for the primal and dual variables; hence, it is natural to assume Tayz, Tony > O.
Suppose that we implement SAPD, stated in Algorithm I on the SCSC problem
+
min max C(x, v) + zEX yey
|| - roll²
(2)
2
for some given A > 0 and zo E X -trong convexity follows from C(: y) being w-eeklly convex.
We make the following assumption on the statistical nature of the gradient noise as in, e.g., [3].
Algorithm SAPD Algorithm
1: Input: T, 0 Mas 2o, yo. N
2: Q y) +- 2( + Mat |a 2012
Assumption 3. Given arbitrary xo E X and Pe > O, let { ( sequence be generated by SAPD, stated in Algo- rithm D running on Q There exist
3: ÿo + 0
4: for 0,1,2...., N do
5:
E4 + V, yki Bkiw 0g.
6: Yk+1 + prox, o0 (y) + 0
Sz, 8y 2 O such that for all k 2 O, the stochastic gradients VI li+li
7: Øk+1 + prox, (2x 7 V xe (ar,, w[))
Gh+1 + V, ( N++1:wē+1 V (3rk, yes
V (In, yks we) and random sequences (wf) k. (wK) satisfy the conditions:
end
10: (UN. = I Ex=o (1RR11
(i) E z ( Mk+1; =xx (ork Mk++1] = (x
(ii) E V & (Zx, uk: wx) likk yu] = v yı));
(ii) E V ( Met wf) (z 2k+ 1r Mk++a] S 53.
(iv) V y x (T Me w v ( 8k )l P yk] I 6%
Assumption 3 says that the gradient noise conditioned on the iterates is unbiased with finite variance"] Such assumptions are common in the literature, e.g., 11 43), and are satisfied when gradients are estimated from randomly sampled data points with replacement.
For WCSC minimax problems, a commonly adopted definition for e-stationary is based on Moreau envelope, e.g., see 23 39]. It is inspired by Davis and Drusvyatskiy' work [9] for solving weakly convex minimization problems. For the sake of completeness, we briefly review this idea below.
Definition 3. Let Ø : Rdd + R U {+oc] be y-weakly convex. Then, for any À (0, Moreau envelope of & is defined as Φx Rdd - such that dhx (x) A min ((w) + 1 || 21/2.
2x
When we run SAPD, stated Algorithm on we use the convention that V. (E+1WEE) A Viz, (++1iw] + (Mx + (xx 20).

---

Lemma 1. Leró: : + ( be a y-weakly convex fimction. For any given À E (0, (0, ox() well-defined on X. Moreover, (o) x >- pr for x N; hence, Φx is X -moothh where prox (z) argmin (0(w) + 1 IIw - x =²]]
22
Definition 4. Under Assumption let o, 6² R + R (+00) such that o(x) & max (( y) and 6² (x) = x(xx f(z) for x E dom f. i.e. (x)x) A maxDEy D(a, y) g for x E dom f.
Remark Under Assumption 7 since $(: y) is y-weakly convex for any y E dom g. d² is n-weakly conve 21 hence, Φ is also y-weakly convex. Note that
prox (x)
argmin + 2x w x0 argmin max [(w, y) + 2 =112. (3)
wEX
WEX
yEy
Furthermore, when By 0, of is differentiable on dom
In the following definition, we introduce the notion of e-stationary with respect to the GNME metric. Definition 5. A point x. is e-stationary point of 7-weakly convex function VV S for some À E (0, c = 0, then Ze is stationary point of Φ.
Thus, from Lemma 1 computing an e-stationary point de. for is equivalent to searching for I., such that I| prox (a.)]l is small. Recall that for any X E (0,--)), ps (z) is well-defined and unique. We also observe from 3 that prox (-) computation is indeed an SCSC SP problem. To compute v. such that ||,, prox xroxxx((xe)) is small, it is natural to consider the iPPM algorithm - e.g.. see 18] A generic iPPM generates {#i)220 such that =/=1 x prox (x1)). i... proximal steps "inexactly" " computed for / 2 O, starting from an arbitrary given point xg E X.
In the next section, we describe the proposed SAPD+ method, an iPPM algorithm employing SAPD to inexactly solve the SCSC subproblems arising in the iPPM iterations.
3 The proposed algorithm SAPD+ and its analysis
The convergence and robustness properties of SAPD for SCSC SP problems are analyzed in [ For the WCSC SP problems, as we explained in the previous section, the main idea is to apply the iPPM framework as stated in SAPD+ (see Algorithm 2 which requires successively solving SCSC SP problems. In the rest, the counter for iPPM outer iterations is denoted with & E E4. At each outer proxxØ(*0) (x().. which is well-defined for À E (0); hence, to derive our preliminary results, we fix À = (Juz + 7)- for some given Me > 0- 0 thus, L(x. y) + #ort7| 1| 1 is SCSC in (z, y) with moduli (pz, Mgy and has a unique
iteration 2 1. we inexactly compute the prox map, i.e., = R prox
saddle point. Consider the following SCSC SP problem:
min max C' C((2z)) v) A f(x) + (xx ( where &' (I. (r + Mr + ? || zb1? (4)
2EX yEy
2
We will construct {a faiV== C dom! f by inexactly solving 4 each outer it-
Algorithm 2 SAPD+ Algorithm
eration E Z4 through running SAPD for N, E Σ, iterations we will spec-
1: Input: {T, 0 Ma). (x8) v8) E X x V. (No E 2
2:
for 0, 1,2, do
ify N₂ E Z, later. Next, we briefly explain the main step of SAPD+ with VR-flag-false. The statement in line of Algorithm 2 means that (2f+1. 1ost..yf. y generated using SAPD, where is dispa- lyed in Algorithm[] iideedd, SAPD is run on (4) for N₁ iterations with SAPD param-
3: VR- = false then
4:
(x) 1+1 1+1
.Yo + SAPD(T, a. 0, Me, wb. yá. Ne)
5:
else
6:
(#)+1 yo ++1 VR-SAPD(T, 0, Mer wi 2o. Ni)
7:
end if
8:
end for
eters (T, a, 0) and starting from the initial point (#). v6)- To analyze the convergence of SAPD+, we first define the gap function G' for 1-th SAPD+ iteration:
(5) Recall that L is an SCSC function; therefore, i) it has unique saddle point denoted by (x.f, v²), and it is important to note that xf prox (a1) for Φ(x) = max,sy L(x, v) and (7 + mx) -x)) ii)
G g'(x,, v) a max L'x, v/) min C'(a'vv). y). e'eX
v'EY
One can argue that oz (-)- + 2 -11 1| is pointwise supremum of convex functions.
5

---

for any (x.y)= E domf f x domgi g, the following quantities are well-defined
(v) argmin (x', y=(x) _ argmax L' (z, argmax L(z, v/). x'E
(6)
y'Ey
v'EY
Thus, it follows that (² v) = (x)x)(())) - L' (v) Moreover, for (æ, E dom f x
dom g. we also define ((z, y) e supwey C(x, in L(x', ,y). Assumption ensures that G is well defined.
Next, we first provide our oracle complexity the GNME metric under the compactness assumption of the primal-dual domains; later, in section 3.1 we show that under particular subdifferentiability assumption compactness requirement can be avoided.
Assumption 4. dom f and dom g are compact sets.
Theorem 1. Suppose Assumptions
and 4 hold. Let pz = 7, 0 1, T, a and N be chosen as
N 33 maxxx + anjo): min Zug tha 425
min 24n0" po 45124
Lay
2B07
Then, for any
0. when VR VR-flag-salse,
SAPD+ guarantees e-ttationary 3/. + 1. which requires C. stochas-
& e, for T 2 (z): 38)
tic first-order oracle calls in total where
C. C==0(( maxf Las dondbbyy + maxt maxe Lyn
1oappmiiin- ) + [ ) G( v8).
Proof. See appendix A for the proof.
Remark 3. Since E. [mint=o..... Vox((() S min E. [ VV the guarantees given in Theorem I falso hold achieving E min [[xx(()] S.
Remark 4. For any y E dom g. since Φ v) Lan-smooth, it is necessarily Laa-weakly convex; hence, 7 Luzz To gel a worst-case complexity,
_ max{Ley Lyzs Luzi Lyy Ky & L/Hty max(6es 8yt, ? = L.
Our oracle complexity C. in Theorem can be simplified as Ce Ce= O 0mm00mxm (max(1, f 3 (.l0leeiin)
In fact, Li al. (2IV (see also (421) provide lower complexity bound for class of first-order stochastic algorithms that do not use variance reduction. The lower bound for finding e-stationary points of smooth WCSC
problems in GNP metric is Q(LAoly + =*),, where Dg 6(xo) -mingex 6(x) and No is an
arbitrary initial point.
For À > O, the map Gy IRd -> Rd defined as Consider e = f + 6- as given in definition
Gx A
prox,, (i AV (i))
is called the generalized gradient mapping and its norm is frequently used in optimization for assessing stationarity (see e.g. [T]. Theorem I provides guarantees in the GNME metric. Theorem / shows that given an c-stationary point in GNME metric (see definition (5) in expectation, we can generate such that x S c for some > O, i.e., an e-stationary point in generalized gradient mapping metric, within ((1/c2) SAPD iterations. Indeed, when f()) O, this metric and the GNP metric are the same.
Theorem 2. Suppose Assumptions 2 hold, and Te, an e-stationary point for the y-weakly convex function (6-) maX&ey C(-.) in expectation, i.e. EI (xx)))) S for some fixed X E (0, Y1) is given. Then, there exists some T, T, 0 see eq. (35) in appendix B such that initialized from xe. SAPD, stated in Algorithm | can generate t such that x
< e within Ö(+)) stochastic
first-order oracle calls, where (-)-)= = max ((:.) - g(y) so that o = f + as in Definition
Proof. See appendix B for the proof.
Remark 5. Based on Remark 3 the random vector De in Theorem 2 can be chosen as a/e where
t. argmingsesT [V (2)))]
However, since t., not be computed in practice we provide an alternative method in the appendix to generate a point x. such that E[[ (x. S within stochastic first-orrr oracle calls see Theorem in appendix D
δ LxxD(2a)D))) + L 2 2

---

3.1 Relaxing the compactness assumption
In Theorem [ we assume that dom If and dom 9 are compact sets, e.g., f(.) = 1x(()) and g(-) = 1y (-), where X с X' and Y C y compact convex sets. In this section, we show that SAPD+ can also handle unbounded domains under the following assumption.
Assumption 5. For f and closed convex, suppose J, Bg > O such that inf[[sy]l : 85 E (f())) < By for all x E &omm and inf inf ||gg||: 8y E =ag(v)) I By for all y E domg.
Remark 6. Assumption Soolds when f is indicator function of a closed convex set (not necessarily bounded) or for f Ra + R URU {+00} such that dom f is open and f is Lipschitz. Two important examples for this scenario are: (i) f(-) 0, (ii) f is norm, e.g., f1-, lzz,, or the Nuclear norms.
The existing work based on iPPM framework either require compactness, e.g., 339, or some special structure on L, e.g., [35]. This is also true for VR-based methods, e.g. 26 37 To our knowledge, ours is the first one to overcome this difficulty and strictly improve the best known complexity bound for the WCSC setting without compactness assumption; moreover, the same idea also works simultaneously with variance reduction technique that will be discussed later (see section A Finally, the same trick for removing compactness assumption for the WCSC setting also helps removing the compactness assumption for the primal domain in WCMC setting and still improve the best known complexity for this setting as well (see section 5)
Remark 7. In [23). when f = g = O, boundedness of dual space is required while Assumption 5 is weaker requirement. Furthermore, based on the discussion with the authors of [39], compactness of the domain is needed for their proof to hold. In [J7y, the sub-level set {x : d(x) + f(x) S a} is required to be compact for all > 0. There are simple convex functions that do not satisfy this condition such as fxx = max(0, x). Bot and Bohm [4] use milder assumptions than [23] without requiring compactess; however, their complexity is the same as the complexity of (23)
Theorem 3. The result of Theorem [ continues to hold, if one replaces the compact domain assump- tion, i.e. Assumption with Assumption
Proof. See appendix for the proof.
Algorithm 3 VR-SAPD Algorithm
4 Variance reduction
1: Input: T, o, 0, Ma, 2o, yo. N. b, Uz. bg.
((x, y) t- 2(2, v)+ "*5*" ||x zoll
Variance reduction techniques have been found useful for solving SCSC problems in finite sum form, e.g.,
3: Let B5 B5.88 be random mini- samples with [B]| = |B8] b
wo + Vy (20, yo). 50 + wo
5: for k 2 0 do
34 -see also [5] using Richardson- Romberg extrapolation in solving SCSC problems with noisy gradi- ents to obtain improved practical performance.
Mk++ f prox,, (yx + 03x) if mod(k; q) == 0 then
7:
8:
7ik + V, " (Ix, Bl++1)
9:
else
10:
Let I% be random mini-batch sample with [Tx] = by
11:
UK + V. क (TR, 1k-1)) V Tzg (#k-1, Vc) + 0k-1
In this section, we equip SAPD+ with
12: end if
SPIDER variance reduction tech-
13:
16+1 --rxxxx, y (I2
TUk)
nique [1], a variant of SARAH [3]] 31 More precisely, for inexactly solving SCSC subproblems given
14: Let 18 be random mini-hatch samples with
|B = |B%+1 =
15:
if mod(k + 9) = 0 then
in 44. we propose using VR-SAPD
16:
wk-1 4- V, Q By,, (I++1.We+1)
as stated in Algorithm 3. Note
VR-SAPD employs large batchsize
17:
else
18:
Let x be mini-batch sample with IT%_a = b2y
of b in every 9 iterations and use
small batchsizes of by and K2 for the rest. We prove that SAPD+ us-
19:
qu+1 + V , ,, 11 (IL+1, B0+11) - V, 2T (I vk)
20:
Wk-1 +- wv + Ge+1
ing variance reduction, i.e., with
21:
end if
VR-flag-true, achieves an oracle 22: 8o+11 <- (1 (1+ 0)wx+1 1- Own
complexity of OLLnke- hence, 23: end for
24: Output: (ĀN, (N) 1/2 Ex (a vk-1)
show an (Fsy)) factor improve- ment over the best known complexity in the literature to our knowledge.
Here, we use V, Veg (Zz, yu) to represent [871 Eujes, V, Byi 0z where BE (00 jim is the biti-batch with |B]] = b and we define V. Ve (zV, 20+1) similarly. In addition, I (wf and
7

---

IV = [w with [TA = U/ and Till iy denote the small mini-batche for generating V V, (ax, Me)
and V. (Ix Me+1). When we run VR-SAPD on a generic subproblem as in (2) we use the convention that V. (FA, g6+1) A V. Dng (Ix, g6+1) + (Mt + 7)x 20).
Throughout this section we make a continuity assumption on the stochastic first-order oracles similar to [17 16 26 B7].
Assumption 6. Alzzz Luzgs Tayz: yy such that Va, I E dom f C X and Vy, y E dom g C V,
1 (2,0(, V, 2 (E, D: wIll - Lya || Ø1| + Lvelly- 5l1. w.p. 1,
(10)
V..
(Z, 8: W|ll & Lanl| all + Loylly- Tl1. w.p. 1.
Assumption 7. Consider SAPD+ with VR fl-flag= true. We assume (i) for any k 2 O, the random mini-batches B. Bi, Ig and TV consist of independent elements, and By independent from By- für i E {K- - 1, B Ig are independent of (Ix, Vet1), and B%, TV are independent of (æi, Ui).
Remark 8. For fimite-sum type problems of the form ming maXy n. - P2(x, v), we can set the stochastic gradient according to (1, yi w) = V. D. y) and V (, v; = V v, Tw y) where w is uniformly drawn at random from {1, (1....,m1 n]. Therefore, if mini-batch samples drawn from {1.....n} n uniformly at random with replacement; batches will be independent of the past iterates satisfying Assumption 7
Theorem 4. Suppose Assumptions 6
Moreover, either Assumption f or Assumption holds. Let P1 7, 0- = L, andd T, o. b and N be chosen as follows:
(Tye + Lax + + 2(1 1)
(Lez + 27)²
10L
N
2(1 + max {
[1
Moo 1
(2lyg Lyz + 2(q 1)
1
101.
82 max 1115
3605
1 My
1
by
(11)
For any c > O and parameters Uzz by, E N+, when fl-flag = true, SAPD+ guarantees c-stationary.
min E x S for T 2 2889(20) vi) 3. which requires T(Nb/q+N(L + v,))
stochastic first-orddr first-order oracle calls in total, where
N = 0 max { Lya + Lua
q L2
9 Lig
Luw + Lyz 9 1
9 Liy
}).
(12)
7
72
b/ 7p
By
by 22
U/ 7Hp
Proof. See appendix for the proof.
Remark 9. For any y E dom g. since 4(-, v) smoohh it is necessarily Lux- weakly convex; hence, 7 S. Liz. To get a worst-case complexity, consider the setting in (8. and let b', b/ = R. Then, Theorem implies that setting b - 00 (Kg 2) N = O1Ly + +22g), and T'= O( (.Stnf leads
to Nb/q+ NO O Roy a N +kyb' + kzgg) Thus, setting / Ky and b' =/ /bri, leads the oracle complexity of T(Nb/g + NU = O ( noleg.902
Remark 10. The results in Theorem f continues to hold under a weaker form of Assumption as in [26 37/, ie.. we replace eq. (10) with
F 1 v ()m) (,,
2T 1|= =112 + 2T y 511
E
| (v. - 2. ]|
< 22 x1I² + 22 llv - ul
Weakly convex-merely concave (WCMC) problems
In this section, we state the convergence guarantees of SAPD+ for solving WCMC problems. In particular, we will consider (T) such that f(-) = 0 and My = 0. i.e., ((x,)) is merely concave for all E X. Instead of directly solving (I) in WCMC setting, we will solve an approximate model
obtained by smoothing the primal problem in similar spirit to the technique in [30]. More precisely,
we approximate ①I with the following WCSC problem: given an arbitrary ÿ E dom g, consider
- Pg lly 011
min max ((x, y) 2 ②(2, v) g(v), where ((x,)) 2 ((x xEX yEy
(13)
2
8

---

Theorem 5. Under Assumptions
2 consider ① such that f(-) = 0. My = 0, and Dy -
Vn lly1 y2ll< oo. When either Assumption 4 or Assumption 5 h for any given e > O, SAPD+ with Va- = false, applied to (3) with By = O(²² (i(e/(Li) (LD))), }) is guaranteed to generate &e E X' such that E [ S e for X 1/(27) within (l1 stochastic first-order oracle calls.
Proof. See appendix G for the proof.
6 Numerical experiments
The experiments are conducted on PC with 3.6 GHz Intel Core i7 CPU and NVIDIA RTX2070 GPU. We consider distributionally robust optimization and fair classification. In the rest, n and represent the number of samples in the dataset and the dimension of each data point, respectively. In this section, SAPD+ means calling SAPD+ with VR-f fallsag- and SAPD+VE VR means calling SAPD+ with VR-flag-true.
Distributionally Robust Optimization (DRO). First, we consider nonconvex-regularizz variant
of DRO problem [ 28 20
43 40 which arises in distributionally robust learning. Let (a, b, /= be the dataset where a, R are the features and b, {-1, 1) are labels. The DRO problem is
1 Σ (x(((z))) - f(x) g(v).
(DRO) min max
(14)
ZERd DEY
where (xx) = log(1 + exp 6 x)) is the logistic loss, f(x) = m. Σ I+ox?
is a nonconvex
regularizer (2). (vy) 1 1 111 and Y A EyER 1 y 13 here, 1 denotes the vector with all entries equal to one. This problem can be viewed as a robust formulation of empirical risk minimization where the weights y: are allowed the worst case empirical risk. We perform experiments on three data sets: i) a9a with n = 32561, 6000, d 5000; iii) sido0 with 12678, d 4932. The
deviate from 1/n: and the aim is to minimize
d 123; it) gisette with dataset sido0 is obtained from Causality Workbenct while the others can be downloaded from LIBSVM repository
20], i.e., a 10, 711 10-3 Parameter tuning. We set the parameters according to 40
7/2 = 1/nn.. We compare SAPD+ and SAPD+VR against PASGDA 4. SREDA [26). SMDA, SMDA-VR 117 algorithms. As suggested in [26). we tune the primal stepsizes of all the algorithms based on a grid-search over the set {10 $ 10 10 } and the ratio of the primal stepsize to dual stepsize, ie., T/O, is varied to take values from the set {10, 10 1 10*). }. For all variance reduction based algorithms, i.e., for SAPD+VR, SREDA, SMDA-VR, we tune the large batch size & |B] from the set (3000, 6000}, and the small batch size 6' | from grid search over the set {10, 100, 200). For the frequency parameter q, we let q = 8' = | for SAPD+VR and SMDA-VR (as suggested in (17): ): for SREDA, when we set and m (SREDA's 's inner loop iteration number) to (n/| as suggested in (26). we noticed that SREDA does not perform well against SAPD+VR and SMDA- VR. Therefore, to optimize the performance of SREDA further, we tune q. m from grid search over { {10, 100, 200). For methods without variance reduction, i.c., for SAPD+, SMDA and PASGDA, we also use mini-batch to estimate the gradients and tune the batch size from {10, 100, 200) as well. For SAPD+ and SAPD+VR, we tune the momentum 0 from (0.8, 0.85, 0.9} and the inner iteration number from N {10, 50, 100).
Results. To fairly compare the performances of algorithms using different batch sizes, we plot loss against epochs in x-axis5) In fig. [ we plot the average loss against the epoch number based on 30 simulations (runs). The standard deviations of the runs are also illustrated around the average in lighter color as shaded regions. We observe that SAPD+ and SAPD+VR consistently outperforms over other algorithms. For a9a, gisette, sido0 datasets, the average training accuracy of SAPD+ are 84.06%, 41%1 96,,3% and of SAPD+VR are 84.33%, 97. 97.69%, 97.46%. respectively. The best performance for a9a, gisette. sido0 among all the other algorithms are 75.92%, 93. 93.07%, 96.43%, respectively. More importantly, we observe that as an accelerated method, SAPD+VR enjoys fast convergence properties while still being robust to gradient noise.
'htp::/www..cuuaalty inf. "https://www.osh www.eesseeeeeeeeeeeeom edu.tedu.t/ tiln/iibssmtoollsaaaasttttaaann 'an epoch is completed whenever an algorithm does one pass over the whole data set through sampling mini-bathes without replacement.
hawpaalllnneeepppppe---eoee phpapage=sastsses

---

Figure 1: Comparison of SAPD+ and SAPD+VR VR against PASGDA on real-data for solving eq. (14) with 30 times simulation.
4 SREDA
26 SMDA, SMDA-VR
29a
50000
SARD+
SAPD+VR
0.6-
SAPD+WK
0.35
0.40
SAPD
SARD-VB
SMDA
0.5
SNDA
SHDA
SREDA
SHDAVR
804
SREDA
SNDA VR
3
0.25
SREDA
SHOA-VR
PASEDA
0.3
0.20
PASGDA
0.2
0.10
Eooch
Epoch
Figure SMDA VR 17
Comparison of SAPD+VR against other Variance Reduction algorithms, SREDA 26
on real-data for solving eq. (1
with 30 times simulation.
MNIT
F-MMST
CIFAR10
3.07
SMDA-VR SREDA
SA
SHIDAVII SREDA
SAPD-VVR
3.17
SHDA-R
SAPD-VR
SREDA
3
2.96
3.13
2.93
2.9
3.0
Epoch 80
100
Epoch
Epoch
Fair Classification. In the context of multi-class classification, Mohri et al. 27 propose training a fair classifier thorough minimizing the worst-case loss over the classification categories. In the spirit of 32 171. we adopt a nonconvex convolutional neural network (CNN) model as a classifier and set the number of categories to 3, resulting in minimax problem of the form:
min max TEX DEV
Σ (:l((x) - s()),
8.l. Σ y1 1, 31 2 0, Vi
(15)
where x E I² represents the parameters of the CNN, and 4, l2 & correspond to the loss of three categories whose details given in appendix H g(v) l1 is regularizer with 1) > 0. We train (15) on the datasets to classify: i) gray-scale Hand-written digits f0. 2, 3} from MNIST; ti) fashion images with target classes (T-shirt/top,, Sandal, Ankle boot) from F-MNIST: idi) RBG colored images with target classes ( Pllane, Truck, Deer) from CIFAR10. For both MNIST and F-MNIST p = 43831, 18000 and d 28 x 28 and for CIFAR10 p 61411, 15000, and d 32 x 32 x 3.
We let the regularization parameter 77 = 0.1 as suggested in [17] We compare SAPD+VR against the other VR-based algorithms SREDA and SMDA VR over 30 runs. We tune the primal stepsizes of SAPD+VR and SREDA by grid search over the set {10- - 2.5 5
10 10-3 10 3} and the ratio of primal to dual stepsizes, i.e., T/O. is chosen from {10, 10 5 103, 103). For SMDA-VR, the primal and dual stepsizes are 10 and 10 as suggested in [17 -we also tried stepsizes bigger than the suggested; but, it caused convergence issues in the experiments. We set the large batchsize [B] 3000 and the small batchsize [Z] = 200 for all algorithms and data sets; the frequency = 200 is used for SAPD+VR and SMDA-VR, and tune q for SREDA taking values from {10, 50, 100, 200). The momentum for SAPD+VR is tuned taking values from (0.8, 0.85, 0.9) and inner iteration number is tuned from N (10, 50, 100). For SREDA, that SAPD+VR outperforms the other bR-based algorithms clearly in terms of both the average loss and the standard deviation of the loss.
tune the inner loop iteration from {10, 50, 100). Fig. shows
Conclusion
In this paper, we considered both WCSC and WCMC saddle-point problems assuming we only have an access to an unbiased stochastic first-oracle with finite variance. This setting arises in many applications ranging from distributionally robust learning to GANs. We proposed new method SAPD+, which achieves an improved complexity in terms of target accuracy e for both WCSC and WCMC problems; moreover, our bound for SAPD+ has a better dependency to the condition number Ky for the WCSC scenario. We also showed that our algorithm SAPD+ can support the SPIDER variance-reduction technique. Finally, we provided numerical experiments demonstrating that SAPD+ can achieve a state-of-the-arr performance on distributionally robust learning and on multi-class classification problems arising in ML.
10

---

References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] Anestis Antoniadis, Irène Gijbels, and Mila Nikolova. Penalized likelihood regression for generalized linear models with non-quadratic penalties. Annals of the Institute of Statistical Mathematics, 63(3):585-613 615, 2011.
[3] Amir Beck. First-order methods in optimization. Society for Industrial and Applied Mathemat- ics, Philadelphia, PA, 2017.
[4] Radu Ioan Bot and Axel Böhm. Alternating proximal-gradient steps for (stochastic) nonconvex- concave minimax problems. arXiv preprini (xXXi:20077.36055 2020.
[5] Bugra Can, Mert Gurbuzbalaban, and Necdet Serhat Aybat. A Veduceee Stochastic Accelerated Primal Dual Algorithm. arXiv e-prints, page arXiv:2202.09688, February 2022.
[6] Ziyi Chen, Shaocong Ma, and Yi Zhou. Accelerated proximal alternating gradient-descent- ascent for nonconvex minimax machine learning. arXiv preprint arXiv:2/12.//666 2021.
[7] Ziyi Chen, Yi Zhou, Tengyu Xu, and Yingbin Liang. Proximal gradient descent-ascent: Variable convergence under KL geometry. arXiv preprint arXiv:2102.04653 2021.
[8] Amó Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). arXiv preprint 151 1.002729, 2015.
[9] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207-239, 2019.
[10] Dmitriy Drusvyatsky and Adrian S Lewis. Error bounds, quadratic growth, and linear conver- gence of proximal methods. Mathematics of Operations Research, 43(3):919-948, 2018.
[11] Alireza Fallah, Asuman Ozdaglar, and Sarath Pattathil. An optimal multistage stochastic gradient method for minimax problems. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 3573-3579. IEEE, 2020.
[12] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. Advances in Neural Information Processing Systems, 31, 2018
[13] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengi Generative adversarial nets. Advances in Neural Information Processing Systems, 27, 2014.
[14] Mert Gürbüübalabaa,, Andrzej Ruszczyíski, and Landi Zhu. A stochastic subgradient method for distributionally robust non-convex learning. arXiv preprint arXiv:2006.00873, 2020.
[15] Erfan Yazdandoost Hamedani and Neodet Serhat Aybat. A primal-dual algorithm for general convex-concave saddle point problems. arXiv preprint arXiv: 1803.00000 2018.
[16] Feihu Huang. Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth-order and first- order momentum methods from mini to minimax optimization. Journal of Machine Learning Research, 23(36):1-70, 2022.
[17] Feihu Huang, Xidong Wu, and Heng Huang. Efficient mirror descent ascent methods for nonsmooth minimax problems. Advances in Neural Information Processing Systems, 34, 2021.
[18] Alfredo N Iusem, Teemu Pennanen, and Benar Fux Svaiter. Inexact variants of the proximal point algorithm without monotonicity. SIAM Journal Optimization, 13(4); 10800 2003.
[19] Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex- nonconcave minimax optimization? In International Conference on Machine Learning, pages 4889. PMLR, 2020.

---

[20] Jonas Moritz Kohler and Aurelien Lucchi. Sub- sub-sampled cubic regularization for non-convex optimization. In International Conference on Machine Learning. pages 1895-1904. PMLR. 2017.
[21] Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie. Complexity lower bounds for nonconvex--tronglyycoo concave min-max optimization. arXiv preprint arXiv:2104.08700. 2021.
[22] Zichong Li and Yangyang Xu. Augmented lagrangian-basse first-order methods for convex- constrained programs with weakly convex objective. INFORMS Journal on Optimization, 3(4):373-397, 2021.
[23] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-coneayy minimax problems. In International Conference on Machine Learning, pages 6083 6093. PMLR, 2020.
[24] Tianyi Lin, Chi Jin, and Michael. L. Jordan. Near-Optimal Algorithms for Minimax Optimization. arXiv e-prints, page arXiv:2002.02417, February 2020.
[25] Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive approximation for one-sided non-convex min-max problems: algorithms and applications. IEEE Transactions on Signal Processing, 68:3676-3691, 2020.
[26] Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex-stronge strongly-concave minimax problems. Advances in Neural Information Processing Systems, 22005666-257,20000
[27] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In International Conference on Machine Learning, pages 4615-4625. PMLR, 2019.
[28] Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In Advances in Neural Information Processing Systems, pages 2208- 2018-221,,220 2016.
[29] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach stoc. programming. SIAM Journal on Optimization, 19(4):1574- 1609, 2009.
[30] Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127-152, 2005.
[31] Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: novel method for machine learning problems using stochastic recursive gradient. In International Conference Machine Learning, pages 2613-2621. PMLR, 2017.
[32] Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. arXiv preprint arXiv:1902.08297, 2019.
[33] Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first- order nash equilibria in nonconvex-coneee smooth min-max problems. SIAM Journal on Optimization, 31 31(4):2508-255 2021.
[34] Balamurugan Palaniappan and Francis Bach. Stochastic variance reduction methods for saddle- point problems. In Advances in Neural Information Processing Systems, pages 1416-1424, 2016.
[35] H Rafique, M Liu, Lin, and T Yang. Non-convex min- max optimization: provable algorithms and applications in machine learning (2018). arXiv preprint arXiv: 1810.
[36] Kiran Koshy Thekumparampil. Prateck Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. arXiv preprint arXiv:1907.015:: 005.01543. 2019.
[37] Tengyu Xu, Zhe Wang, Yinghin Liang, and Vincent Poor. Enhanced first and zeroth order variance reduced algorithms for min-max optimization. 2020.
12

---

[38] Zi Xu, Huiling Zhang. Yang Xu, and Guanghui Lan. A unified single-loop alternating gradient projection algorithm for nonconvex-come coneeveeeeeeeeeeeeeeeeeeeeeeeeee and nonex--noccnccwe minimax problems. arXiv preprini vrXiv:2066.00032 2020.
[39] Yan Yan, Yi Xu, Qihang Lin, Wei Liu, and Tianbao Yang. Optimal epoch stochastic gradient descent ascent methods for man-max optimization. Advances in Neural Information Processing Systems, 33:5789-5800 5800, 2020.
[40] Yan Yan, Yi Xu, Qihang Lin, Lijun Zhang, and Tianbao Yang. Stochastic primal-dual algorithms with faster convergence than o(1 (1/vT) for problems without bilinear structure. arXiv preprini arXiv: 1904. 101 2019.
[41] Junchi Yang, Antonio Orvieto, Aurelien Lucchi, and Niao He. Faster single-loop algorithms for minimax optimization without strong concavity. In International Conference on Artificial Intelligence and Statistics, pages 5485-5517. PMLR, 2022.
[42] Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of aiiroonve-sttronlyyyconcee minimax optimization. In Uncertainty in Artificial Intelligence, pages 482-492. PMLR, 2021.
[43] Xuan Zhang, Necdet Serhat Aybat, and Mert Gürbüzzalaban. Robust accelerated primal-dual methods for computing saddle points. arXiv preprint 1rXiv 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Although improve the existing best known bounds, there is still room to improve Ky dependence based on
the existing lower complexity bounds 21 42 unless the lower complexity bounds loose.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "tyqan038WNw", "reviewer": "Reviewer_JXF9", "summary": "The authors analyse the performance of a stochastic method (SADP+ and variance reduced SAPD+) for solving weakly convex-strongly concave  and weakly convex merely concave saddle-point problems. Under milder assumptions than previous works (no compactness needed), they prove that SADP+ (and its VR counterpart) obtain complexities which have better dependencies in the condition number for WCSC problems and a $\\log$ improvement for WCMC problems. ", "questions": "- how would you justify the originality / significance of your results when building on the works of [14] [42]", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Please keep in mind that this submission is unfortunately *not* in my area of expertise. \n\nThough the paper is very dense and compact, it is is overall well written and easy to follow,  The contributions are clearly stated and all the results are introduced and commented. Table 1 provides (what seems to be) an extensive summary of the relevant related results. They show an improvement of the order $\\kappa_y^2$ for WCSC problems ($\\kappa_y$ for WCMC problems) which seems significant. I am however not capable of judging whether relaxing the compacting assumption is a significant improvement over previous results. \n\nThe numerical experiments are convincing: several algorithms are compared, the two settings are clearly explained and hyperparameter selection is given each time. \n\nMy major concern regarding the submission is the importance and significance of their results. The algorithm they consider is the natural stochastic version of the APD algorithm proposed in A PRIMAL-DUAL ALGORITHM FOR GENERAL CONVEX-CONCAVE SADDLE POINT PROBLEMS [14] (which is oddly not cited in the main text). Furthermore SADP+ was already analysed in ROBUST ACCELERATED PRIMAL-DUAL METHODS FOR COMPUTING SADDLE POINTS [ 42] for strongly convex-strongly concave problems. Hence I have concerns regarding the originality of the paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jlh4pwYy23F", "reviewer": "Reviewer_DZXf", "summary": "This paper is concerned with weakly convex-strongly concave (WCSC) and weakly convex-merely concave (WCMC) saddle-point problems. A new stochastic method, SAPD+, is proposed, which is based on the inexact proximal point method. Compared with the existing works, the proposed method does not require compactness for neither the promal nor the dual domain, and can achieve the best $\\kappa$ dependence. This result is nice and outstands much of the work. In addition, they also proposed a variance-reduced version of SAPD+ and achieves the best known complexity. \n", "questions": "1. Note that function $Phi(\\dot, y)$ is assumed to be weakly convex and smooth. Since a smooth function is necessarily weakly convex, the reviewer is wondering whether the assumption that the function $Phi(\\dot, y)$ is weakly convex is redundant and should be removed?\n\n2. In the work of Davis and Drusvyatskiy [8], an additional upper bound of the gradient norm is required for weakly convex objective functions. The reviewer is wondering how this assumption is relaxed in this present work? Please explain.\n\n3. Regarding the assumption on the compactness.\n(1) In Section 2.2, the authors relax the compactness assumption by introducing an additional upper bound on the subgradient norm. This additional assumption should be mentioned in the Contribution, since the boundedness of feasible domains is replaced by the boundedness of subgradient.\n(2) The reviewer is also wondering whether Assumption 5 is more realistic than Assumption 4. More advantages of using this assumption instead of the assumption on the compactness should be explained in detail.\n\n4. Does the VR parameters (b', b, q) have influences on the performances? It is not clear from the present work. \n\n5. Some typos to be fixed: \n(1) Line 200 ``Suppose Assumption 1, 2, 3 and 4....'' should be ``Suppose Assumptions 1, 2, 3 and 4....''\n\n(2) Line 285 ``Suppose Assumption 1, 3, 6 and 7....'' should be ``Suppose Assumptions 1, 3, 6 and 7....''", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "originality: This paper is well organised in general. In Introduction, the motivation, problem formulation and literature review are included. Contributions are listed in a clear way. The main results and the proofs are easy to follow. The reviewer only has one minor comment related to the originality of this work: In the conclusion, it is suggested that some future directions should be included.\n\nquality: The results are technically sound and theoretically supported. The algorithm proposed is also new.\n\nclarity: The proof is thorough and clear. The simulation and the comparison are adequate. \n\nsignificance: This paper takes the stocastic setting of the nonconcave-convex mini-max saddle point problem, which, compared with the determinstic setting, is more realistic and practical since the modern datasets have large-dimensions and computing its exact gradients is infeasible. In addition, this paper relaxes the commonly adopted assumption that both the promal and the dual domain should be compact, which is a significant improvement compared with existing works. The assumptions and results obtained in the work are well explained relative to existing works. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "MpKxNtYNUsa", "reviewer": "Reviewer_yayL", "summary": "This paper proposed SAPD+ algorithm for differentiable weakly-convex-strongly/merely-concave (WCSC / WCMC) minimax problems, which is based on iteratively solving SCSC subproblems; while further assuming smoothness of the gradient estimator, the proposed algorithm can be incorporated with SPIDER-type technique for solving the problems. The proposed algorithm achieves new SOTA complexities in all three settings.", "questions": "The results here are pretty interesting. While I found it hard to check thoroughly the long proof. My main questions:\n\n1. The algorithm idea is pretty simple, just iteratively augment it to SCSC, and use existing oracle to approximately solve it. The conciseness looks exciting to me. I found that there are also some other literature like PG-SMD [35] and Catalyst [41] which shares similar idea. While here this paper is the first one to achieve such sharp complexity. It would be great if authors can provide any comparison to existing literature, and intuitive understanding on why it achieves acceleration here (and others no).\n\n2. I personally may think that here \"weakly convex\" is a little misleading, Assumption 2 on the Lipschitz smoothness has already implied weak convexity (as mentioned in Remark 3), while the difference should be the modulus of weak convexity. I may view weak convexity be more common in nonsmooth optimization (e.g., [35]), but here the coupling term $\\Phi$ is differentiable (ignoring regularizers $f$ and $g$).\n\nIn general I think the results here are important and significantly improve over existing results. While the presentation can be further polished for better readability.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. Claim an algorithm with new SOTA complexity\n2. The algorithm is pretty simple\n3. Further relax the common compactness assumption\n\nWeakness:\n1. The proof is messy, also too many notations (maybe unavoidable though), I felt hard and confused to follow the idea when reading.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept