Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions
Authors: Quanqi Hu
Qi Qi
Zhaosong Lu
Tianbao Yang
Venue: NeurIPS 2024 poster (2024)
Keywords: Stochastic Optimization
DC Program
Min-Max Optimization
Non-smooth Optimization
Primary area: optimization

Abstract: In this paper, we study a class of non-smooth non-convex problems in the form of $\min_{x}[\max_{y\in\mathcal Y}\phi(x, y) - \max_{z\in\mathcal Z}\psi(x, z)]$, where both $\Phi(x) = \max_{y\in\mathcal Y}\phi(x, y)$ and $\Psi(x)=\max_{z\in\mathcal Z}\psi(x, z)$ are weakly convex functions, and $\phi(x, y), \psi(x, z)$ are strongly concave functions in terms of $y$ and $z$, respectively.  It covers two families of problems that have been studied but are missing single-loop stochastic algorithms, i.e., difference of weakly convex functions and weakly convex strongly-concave min-max problems. We propose a stochastic Moreau envelope approximate gradient method dubbed SMAG, the first single-loop algorithm for solving these problems, and provide a state-of-the-art non-asymptotic convergence rate. The key idea of the design is to compute an approximate gradient of the Moreau envelopes of $\Phi, \Psi$ using only one step of stochastic gradient update of the primal and dual variables. Empirically, we conduct experiments on positive-unlabeled (PU) learning and partial area under ROC curve (pAUC) optimization with an adversarial fairness regularizer to validate the effectiveness of our proposed algorithms.

Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions
Quanqi Hu Qi
Zhaosong Lu
Tianbao Yang
Department Computer Science Engineering. Texas A&M University
Department of Computer Science, The University of lowa Department of Industrial and Systems Engineering, University Minnesota (quanqi-hi tianbao- yang)aagggnaan edu qi-qiiuiova. edu zhaosong@umn. edu
Abstract
In this paper, we study class of non-smooth non-convex problems in the form of ming maxxeey Φ(x, y) max z (xx,,), where both ((x) maxgey Φ(x, y) and (x) = maX,ez v(x 2) are weakly convex functions, and o(z, y), (xx 2) are strongly concave functions in terms of y and 2, respectively. covers two families of problems that have been studied but are missing single-loop stochastic algorithms, i.e., difference of weakly convex functions and weakly convex strongly- concave min-max problems. We propose stochastic Moreau envelope approximate gradient method dubbed SMAG, the first singlc-loop algorithm for solving these problems, and provide a sate-off-hheant non-asymptotic convergence rate. The key idea the design to compute an approximate gradient of the Moreau envelopes of 4b Y using only step of stochastic gradient update of the primal and dual variables. Empirically, we conduct experiments on resitiv-unllbblle (PU) learning and partial area under ROC curve (pAUC) optimization with adversarial fairness regularizer to validate the effectiveness our proposed algorithms.
Introduction
In this paper, we consider a class of non-convex, non-smooth problems in the following form
min {F(x) 2E3
max 6(I, y) max (z, 2)
(1)
ye
ZEZ
where the sets ) Rd,, 2 Rd: convex and compact, and the two component functions ((2, y) and (x =) are weakly-convex in terms of x and strongly-concave in the terms of y and respectively. Both component functions are in expectation forms, i.c., Φ(z, y) and (xr, 2) EqwDD, [t(x,, [v>x, C)). We refer this class of problems the Difference of Max- Structured Weakly Convex Functions (DMax) Optimization. DMax optimization unifies two emerging families of problems in optimization field, difference- -ffeerencee-o-wwaalllccooomm
SEE-D,lo(s y; {)]
(DWC) optimization
min {F(x) == ((x) - vb()),
and weakkly-oonvexx-stonnlyyy (WCSC) min max optimization
min ZER
F(x)) := max 6(z, y)}-
yE)
Thus, DMax optimization has wide range of applications in machine learning and AL. includ- ing applications of DWC optimization (c.g., positive-unlabelee (PU) Learning [39], non-convex
Correspondence to: Tianboo Yang <tianbao- yangaoo-yngeee yang@tamuuu @tammuttta.....
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Comparison with existing stochastic methods for solving DWC problems with non- asymptotic convergence guarantee. The method SBCD is designed to solve a problem in the form of min, (ming ((I. y) min, (a, =)} with specific formulation of ø and s.. However, the method and analysis can be generalized solving non-smooth DWC problems.
Method
Smoothness of Φ, vb
Complexity
Loops
SDCA
26
Φc Smooth
(
Double
SSDC
39
Φ or th: v-Hölder continuous gradient
O(c4/y
Double
SBCD
45
Non-smooth Non-smooth
O
Double
SMAG (ours)
O
Single
sparsity-promooting regularizers [39. Boltzmann machines [26]) and applications min-max op- timization (e.g., adversarial learning MI 22]. distributional robust learning [8 28 learning with non-decomposable loss [28) ). recent years, the scale data and models significantly increased, leading the demand of more efficient optimization methods. However, all existing stochastic methods for DWC optimization and non-smooth WCSC min max optimization with state-of-the- art non-asymptotic convergence rate O(e are double-loop. As result, these methods complex regarding the implementation and require extensive hyperparameter tuning. To close this gap, we propose single-loop stochastic algorithm for DMax optimization and provide non-asymptotic convergence analysis to match the state-of-the-at non-asymptotic convergence rate.
The main challenges of designing single-loop method for DMax optimization are threefold. I) given the weakly-convex nature of the component functions, their difference F(x) not necessarily weakly-convex, resulting in non-smooth non-convex optimization problem. 2) the component functions maxyey o(x, y) and maX,ez (1, 2) require solving maximization subproblems, making unbiased estimations of their subgradients inaccessible. 3) existing work non smooth problems with DC or/and min-max structures heavily rely on inner loops to solve subproblems to a certain accuracy.
To address the first challenge, we apply Moreau envelope smoothing technique 24 to the com- ponent functions individually and take their difference smooth approximation of the original objective. Inspired by existing work [32 45), we show that solving the original DMax problem can be achieved by solving this smooth approximation. Consequently, the problem is transformed into a smooth problem with two layer of nested optimization structure, the Moreau envelope and the maximization from the min-max structure. In order to avoid inner-loop, perform only step of update for each of the nested optimization problems. Our analysis leverages the fast convergence of strongly convex/concave problems, proving that single-step updates sufficient to achieve state-of-the-ar convergence rate. Although the Moreau envelope smoothing is not new for solving DC
and min-max optimization 32 45 47 43), the existing results either require double loops 32 45
require smoothness of the objective function [7 43
Contributions. We summarize the main contribution of this work following.
We construct a new framework DMax optimization that unifies the DWC optimization and WCSC min-max optimization. Based Moreau envelope smoothing technique, we propose single- loop stochastic algorithm, namely SMAG, for DMax optimization non-smooth setting, which achieves O(e *) convergence rate.
We show that the proposed method leads to the first single-loop stochastic algorithms for DWC optimization and non-smooth WCSC min-max optimization achieving O (1) convergence rate.
Finally, we present experimental results on applications including Uunaabee (PU) Learning and partial AUC optimization with an adversarial faimess regularizer to validate the effectiveness of our proposed algorithms.
2 Related Work
Stochastic DC Optimization. DWC can be converted into Difference-of-convex (DC) programming.
DC programming was initially introduced in 33 and has been extensively studied since then. comprehensive review on the developments of DC programming can be found in [18]. Despite the

---

Table 2: Comparison with existing stochastic methods for solving non-eo non-smooth min- nin--ax problems. The objective function is in the form of pfx, y) = f(z y) g() +h(x). NS and S stand for non-smooth and smooth respectively, and NSP means non-smooth and its proximal mapping is easily solved. WC, stand for weakly-convex and convex respectively. WCSC stands for weakly-conven strongly-coneave, SSC stands for smooth and strongly concave and WCC means weakly-convex. concave. Note that Epoch-GDA and SMAG studies the general formulation Φ(x, = [(x, y).
Method
[(x,y)
gly)
h(x)
Complexity
Loops
PG-SMD
29
NS, WCC
NSP, SC NSP, C
NSP. C NSP.C
O(E
Double
SAPD+
48
SSC
O(E 44
Double
Epoch-GDA
40
NS, WCSC
O(e-4)
Double
StocAGDA
[
SSC NS, WCCC
NSP, C
NSP, C
Ole
Single
SMAG (ours)
O(E
Single
rich literature on DC programming, DC in stochastic setting has rarely been mentioned until recently, Most of the existing studies on stochastic DC optimization are based on the classical method, DC Algorithm (DCA) in deterministic DC optimization. The main idea of DCA is to approximate the DC problem by convex problem by taking the linear approximation of the second component. In
), .z} J. to update zg and thus forms a double-loop algorithm. (34] first proposed stochastic DCA (SDCA) for solving large sum problems of non-convex smooth functions, which was further generalized to solving large sum non-smooth problems in ([6].
other words, DCA solves min, {Ø(x) - (V (Vo(zx),
[1] is the first work that allows both components in DC problems to be non-smooth. The authors proposed a SDCA scheme in the aggregated update style, where all past information needs to be stored for constructing future subproblems. (17] improved the efficiency of the SDCA scheme by removing the need of storing historical information. So far, none of the above work provides non-asymptotic convergence guarantee. The first non-asymptotic convergence analysis authors proposed a stochastic proximal DC algorithm (SPD), which modifies SDCA by adding an extra quadratic term after linearizing the second component function, and proved that SPD has convergence rate of O(E The main drawback of their analysis is that they need the smoothness assumption of the first component function. With very similar algorithm design, [39] managed to partially relax the smoothness assumption. Given at least one of the two component functions having -öHölerr continuous gradient, i.e.. [z) - V f(x')) S || I'Il" for all x, x,,', they proved a convergence rate of ( O(E-4/v). In fact, the Hölder continuous gradient assumption is still fairly strong as some of the common non-smooth functions do not satisfy, for example the hinge loss function.
established in (26). The
Recently, another approach to tackling the non-smoothness in DC problems has been considered. Following the smoothing technique in non-smooth weakly-conves optimization literature B]. B2 25 constructed Moreau envelope smoothing approximations for both of the component functions respectively and established non-asymptotic convergence analysis under deterministic setting and the assumption that either component function is smooth the proximal-point subproblems can be solved exactly. Following a similar idea, 45 studied a problem in the form of min, F(x) := miny ((z, 3) ming (xx 2). where & and are in some specific formulations, and proposed a double-loop algorithm with (cc-6) convergence rate. Although the á and & non-smooth, their analysis heavily relies on the properties in the given formulation, especially the structures in the dual variables y, 2, thus is not trivial to generalize.
Note that none of the aforementioned work is able to solve the DMax problem, as they require unbiased stochastic gradient estimations of the two component functions, which are not accessible in DMax due to the presence of the maximization structure.
Stochastic Non-smooth Seaakly-Conve--Stree -tonnng Min-Max Optimization. Stochastic WCSC min-max optimization has been an emerging topic recent years. Most of the existing works
focuses on the smooth setting, i.e., the objective is smooth [22
or the stochastic To the best of our knowledge, [29]
19
49
43
47 43
gradient oracles are Lipschitz continuous 23 42 is the first work that considers non smothh WCSC min-man problems. They considered a special structure where the maximization over y given æ can be simply solved and is solved with O(1/e²)
21 38
times. They proposed a nested method Proximally Guided Stochastic Mirror Descent Method (PG-
SMD) that achieves a convergence rate of (e) Later, [40 further relaxed the assumption by removing the requirement of the special structure, and proved that their nested method Epoch-GDA
3

---

has a similar convergence rate of OEe Another line of work studies a special case of the general non-smooth non convex min-max optimization, where the objective is assumed be composite. i... 6(x, y) = [xx y) g + h(z), so that f is smooth while y. h are potentially non-smooth [I 48 Both works established O(e (e) convergence rate, and assume f is smooth and strongly concave, g and h are convex but potentially non-smooth and their proximal mappings can be easily solved. However, none of them is applicable to the general non-smooth WCSC min-max optimization.
3 Preliminaries
Notations. For simplicity, we denote (xx) == m o(r y). (x) == m ((x, 2). y,(y)))))))
magga yey a(., y), and =*()) = arg m 2). We use || to denote the Euclidean norm of vector and (e(+) to denote the Euclidean projection onto a closed set C. We use the following
definitions of general subgradient and subdifferential [3
Definition 3.1 (subgradient and subdifferential). Consider function f R. -> R foo} and point with finite (x)). A vector v E Rd is a general subgradient of f at if
f(y) (x) + (u.y z) + +[lly - -x|) as y + X.
The subdifferential (f(x) is the set of subgradients of f point x.
For simplicity, we abuse the notation (z)) to denote one subgradient from the corresponding subdifferential when no confusion could be caused. We use (f(x) and V (xx to represent an
unbiased stochastic estimator of the subgradient (f and the gradient (f(x) respectively. A function f D + R is said to be L-smooth if [[V](x) V fz''ll & Li - x'll for all x, E D. A function f Rd + RU {oo} is 6-weakly convex if f(+) + å 111-112 is convex. A mapping M : R
said to be C-Lipschitz continuous if [lM(x) - -M22M S Cll x'Il for all x E
Consider solving a non-smooth problem min, f(z). One of the main challenges is that the e- stationary point, i.c., point such that dist(0, (x)) I e, which the typical goal for smooth problems, may not exist in the neighborhood of its optimal solution. A classical counter example would f(xx) = |ær.. where for c 1) the only c-stationary point is the optimal solution r = 0. setting is to use relaxed convergence criteria, that find a point no more than away from an c-stationary point. This is called a nearly c-stationary
standard solution to this issue in weakly-conve
point, and is widely used in non-smooth weakly-convex optimization literature 4 22 41 50 T9
In fact, finding a nearly e-stationary point for (a) can be achieved by finding an e-stationary point of (2)), the Moreau envelope of f(xx). Assume function ʃ is 8- d-weakly-conver then its Moreau envelope and proximal map are given by
(z( min { f(x') + |
=1|
pxox,,(x)) == arg min { (f(z') +
1 11 x=[3} 27
27
Existing work 3 has shown that with 7 E (0,8-) and ā == prox,, we have
fz()) = 7
(x -
2), f(0) s f(x), dist(0, af())) - [Vf[(
Moreover, prox [ (x) is 1 1-78 Lipschitz continuous 32
Now we consider the DMax problem 1 By Danskin's Theorem, the weak convexity assumption of p(:3) and (t.,2) 2) naturally leads to the weak convexity of o(-) and (-). Since the weak convexity assumption of component functions does not guarantee the weak convexity of their difference function F(z), one may neither 1) use nearly e-stationary point of F F(x) as the convergence metric, nor 2) directly apply Moreau envelope smoothing technique to F(x). To tackle the first issue, we follow the existing work [45] to use the following convergence metric for non-smooth DWC problems.
Definition 3.2 (Definition in [45). ). Given > we say & is nearly e-critical point of F())) = (xx
min
(x)) if there exist v, v, x such that v E a0(x') - NV and max [B u||. E x' pc x=Il <.
To tackle the second issue, we take the Moreau envelope of ((.) and Vi.) individually and define the smooth approximation of F(x)) as
(x( = (x) - v (a).
(4)
The recent work
33 has proven that (x) is indeed smooth.

---

Algorithm Stochastic Moreau Envelope Approximate Gradient Method (SMAG)
1: Input Initial points: S 2 Io. Yoo 20. Hyper-parameters: 7/ 10 71
2:
Stochastic (sub)gradieent:: d.Ø, Vu Oz Vath.
3: for = O...., do
4:
22 1+1 z 17 ( vi) + (1 - =x1)
5:
M++1
Py e + 1n Vy Vt))
6:
1+1
x 1 (dg (1t 2x)
( xx))
7:
2++1 (zt + V 2/ ( 21)
8: G++1 ( ~ )
(xe x
9: Ft+-1 It 170 G++1
10: end for
return wt or ott with i uniformly sampled from {I...., T}
Proposition 3.3 (Proposition EC.1.2 in 32 Assume D(-) and (-) are 86, d ww-klyy conver respectively, Then F, = 4 (x) - Vr (x) is L--moothh, where Lp 7-24 min(A
Morcover, one can show that good approximate stationary point æ of (-) and good approximation point x' the proximal points prox, (I) and prox, (z) can guarantee that x' is nearly e-critical point of ming (+))
Lemma 3.4 (Lemma < 7 < 6 8 If vector such that F,, S min(1, (2,,," 44 and is vector such that [B|||' & (x)]l < e²/ 4 Bi]|a' prox, (I) < 2/4, then xf is nearly
45
Assume (.)) and (-) are dø, Sy-weakly convex respectively, and
e-critical point of min; F(i).
Algorithms and Convergence
Since we aim to minimize the smooth function F, (2), the natural strategy is to perform gradient descent to update the variable æ. Following from the properties of Moreau envelope, the gradient of (a) is given by
[x prox ,rox,.. (x))
VF,(2)=
prox,
(5)
where the blue component is the gradient of (x)) and the green component is the gradient of (D (z)). However, the proximal points prox, w (x) and prox. (x) are not accessible in general. Indeed, these proximal points are the optimal solutions to min (#(x)) + + -|=-=x'113 and min ( (*x) + - |x- r²11²) respectively. and (+-) and (-) typically not accessible because they are the value functions of possibly sophisticated maximization problems. Thus, we maintain two variables z', and æt as the estimators of prox, (x4) and prox (xx, (zx) respectively. and maintain another two variables Y4 and 2, as the estimators of arg max p(prox, (mx), v) and arg max.ez (prrox,,x/xx))) respectively. update x and zi, by one step of stochastic gradient descent, and update Y1 and by one step of stochastic gradient ascent. Finally, we compute the gradient estimator G = + (xz 1) (z, - + of (F,()) and update 2, by one step of gradient descent. The resulting algorithm is presented in Algorithm
At each iteration,
DWC Optimization. For DWC problem 2 the associated functions ( o(-) and v((:) (t) are directly accessible. Thus the variables y/ and 2; in SMAG are no longer needed. The simplified SMAG algorithm for DWC optimization presented in Algorithm 2
WCSC Min-Max Optimization. For WCSC Min-Max problem the second component function v 0 can be ignored, and thus variables z', and 2, longer needed. However, this brings
5

---

change to the gradient of (1((2) as it now becomes
(z,(2:) y (z+ o ox))),
The simplified SMAG algorithm for WCSC Min-Max optimization is presented in Algorithm 3
Algorithm 2 SMAG for DWC Optimization
Algorithm 3 SMAG for WCSC Min-Max Opti-
for ..... T 1 do
mization
2:
z 4 2 71 (0)
1: for 1 .,..., do
2: 1+1 2/b -7 ( (xb -x))
3:
r m (0 (x))) (a)
2())
3: V++1 = -Py(y + mn V V ut))
4: G++1 = (x +1 x1tt1)
4: G = (1+ - I 1111
5: Ze4- = It - G0
5: Zt+-1 = 24 -1o G
6: end for
6: end for
7: return n' or dl with (
7: return 2; with ~ 10..... -
4.1 Convergence Analysis
In this section, present convergence results for Algorithms 1 assumption for DMax problem ①I)
To proceed, make the following
Assumption 4.1. Considering DMax problem we assume that
(i) d(+ v) is da-weakly convex, and vi(;,2) is faw-weakl convex.
(ii o(z,) :) is p p--Strongly concave, and (zx .) is po Ho--strygll concave.
(iii) olr y) and (i(,,, z) differentiable in terms of y and z respectively, v is Lagar Lipschitz continuous, and V (,)((, is
continuous.
(iv) There exists constant F7 > - such that F7 s (x) for all x.
(v) There exists finite constant M such that El v) < M BlI y)1l s M t/ 2) M V/ 2]] < M for all IRd y y and Z.
It shall be noted that Assumption 4.1 (ii)) only requires partial smoothness of o and v and is to ensure the Lipschitz continuity of y (-) arg max ((-2) and (+) = arg max,ez (1, This follows from existing results.
Lemma 4.2 (Lemma 4.3 in 19) Consider problem max f(r, y) for any x E Rd= where y c IR is a closed convex set. Assume that f(x, y) is p-strongly concave in y for each x E gd,, and V Vyf(. v) is Lipscchh for each E V. Then arg max, f(-.y) is T'x Lipschitz continuous.
Lipschitz smooth function f(, y) is guaranteed to have Lipschitz continuous partial gradient (yf(-,w, while the reverse statement is not necessarily true. For example, consider a function [(x, v) = y h(xx) g(y) with non-smooth C-Lipschitz continuous h((-) and strongly convex Then f(z, 8) non-smooth but the partial subgradient V,f(. h(-) ((-)-Vel Vg(y is Lipschitz continuous with respect to the first argument. Another example is given by f(x, y) = fz( + (z, v). where fi is weakly convex and fa is smooth and strongly concave in terms of y. The latter is indeed seen in our considered application for PAUC maximization with adversarial fairness. In fact, one may replace Assumption 4.1 (ii) by directly assuming that y²()) and =-( are Lipschitz continuous, In addition, Assumption 4. Iv) is standard in non non-smooth optimization literature [ 39 10].
Here we give brief outline of the convergence analysis. First of all, we present standard result (7).
Lemma 4.3. Suppose that F.).)) is Lp-smooth and 2i+1 Et GoG+41 with 0 nju 21.F Then we have
14(4441) $ Fz.),)) 110
VF,( G.+1l12 770 (VF)(
770 ||G 11..
4

---

This implies that the key to bounding the gradient [IV is to obtain recursive bound for the gradient estimation error IVV (1r) G++1ll Following from the true gradient formulation have
we
I [z) G2t1ll2
7 (lat)) o (1 + || prox, (1t))
(6)
In other words, the error of the gradient estimation G(+1 can be bounded by the estimation errors of r2tt1 and & 1 Thus, we construct recursive bound for the proximal point estimation errors - (1=²)]² and || - prox, [x+)]² individually. fact, these two errors share almost identical analysis due to similar assumptions and updates. Here we only present the result for function G, as the result for & directly follows.
Lemma 4.4. Suppose that Assumption 4. holds, 0 < < 1/6g, and T S 72(1/7-6a) 5%) sequences {æt}. {ych. {arr} and {Gr} generated by Algorithm satisfy
Then the
2
B1 1+1 - - (1=+)] + Rellyr-1 y" (pmoxx, (1=)))
$ (111/ - -66) EF EF - prox, (x+- + (1 7/14) - y (x
2
2nd
12 10 To M 22 86)2 B|| + 12M22
+ (1/7
+
(1))
Finally, combining Lemma 4.3 inequality for Algorithm D
(6) and Lemma 4.4 yields the following convergence result
Theorem 4.5. Suppose that Assumption 4.1 holds, 0 < 7 min _6 m = =O(2), and Vo Tmn. Then after T 2 O iterations, the sequences (wa). (2/a and (x/p) generated by Algorithm satisfy Eill=', - prox (xT | prox, (+E-1))1 + ( S
min "/e=//4 /4, and the outputs æt, and st are both nearly e-critical points of problem
Since DMax optimization is a unified framework covering DWC optimization and WCSC min-max optimization, the convergence results of Algorithms 3nd directly follow from Theorem 4.5) To present them, we first provide reduced version of Assumption 4.1 I. DWC problem 2
dirdedt
Assumption 4.6. Considering DWC problem we assume that
(i) <(-) is da-weakly convex, and (-) is 8 weakly convex.
(ii There exists a constant F > oo such that F I (x)x) for all
(iii) There exists a finite constant M such that E| (1))2 < M and ElÖO(=) < M for all Idd.
By setting o(x, u) = 6(x) and (xx = vxx)), namely independent and z, in DMax problem ①. we obtain the following convergence result for Algorithm 2 which is an immediate consequence of Theorem 4.5
Corollary 4.7. Suppose that Assumption 4.6 holds, 0 7 min . m O(E)), and
Yo TTh Then after T 2 (c=a) iterations, the outputs æ and at of Algorithm 2 are both nearly
e-critical points of problem (2)
For WCSC min-max problem we reduce Assumption 4.1 to the following.
Assumption 4.8. Considering WCSC min-max problem we assume that
(i) d( y) is 5, -weekly convex, and ((x,-) Ma stroonly concave.
(i) ő(z, y) is differentiable in terms of y, and V V y) is - -Lisschtt continuous.
(iii There exists constant F oo such that F; < Fx(x) for all x.
(iv) There exists finite constant M such that E 0 1) < M and V w)1 < M² for all z E dd and y E y.
7

---

By setting (2, = 0 in DMax problem I we obtain the following convergence result for Algorithm which an immediate consequence of Theorem 4.5
Corollary 4.9. Suppose that Assumption 4.8 holds, 0 < < 1/86 m O and no TIJ
Then after T 2 ((e=)) iterations, the output æi of Algorithm 3 is nearly e-stationary point of problem 3
It shall be mentioned that for WCSC min-max problem (3) we use nearly e-stationary point as the convergence metric. This is standard in weakly-convex optimization literature 3.
Applications
In this section, introduce two applications of DMax optimization, PU learning for DWC opti- mization and partial AUC optimization with adversarial fairness regularization for WCSC min-max optimization. We also show experimental results both applications.
5.1 Positive-Unlabeled Learning
In binary classification task, the optimization problem is commonly formulated as the minimization of X;, empirical risk, i.e., wen [S] Ex.es (ww;;; y4) where X,, yr) is the loss given the model data point x; and its ground truth label 34. Given the scenario where only positive data S+ are observed, then the standard approach becomes problematic. One way to address this issuc is to utilize unlabeled data S, to construct unbiased risk estimators. To be specific, [13] formulated the PU learning problem as following
parameter
min
[[(w;x,, x, - l(w; -1]] + 1 x:ES+
Σ Th x3 ES.
(wwaaj,-1 -1)
12+
is the prior probability of the positive class. If f(w; x, v) weakly convex in terms of w, then Problem 7 is a DWC problems. particular, in our experiments we consider linear classification model and hinge loss.
where n = |S_|. Suul T. = Prly =
Baselines. We implemented five baselines and compared them with our proposed method SMAG for DWC optimization. The first baseline, stochastic gradient descent (SGD), does not have theoretical convergence guarantee for DWC problems. However, since it is the fundamental method for convex optimization, we include it to show its performance. We also implemented existing stochastic methods for solving DC DWC problems with non-smooth components, including SDCA (26).
SSDC-SPG (39], SSDC-Adagrad [39] and SBCD (55. Datasets. We four multi-class classification datasets, FaSSion-MNIST 36], MNIST 5 CI- FARIO [4] and FER2013 (6) To fit them in binary classification task, we consider the first five classes negative for Mushion-MNISS MNIST and CIFAR10, 10, and the first four classes negative for FER2013. For Fashion MNNIST, MNIST, CIFAR 10, we follow the standard train-test split. For FER2013, we take the first 25709 samples as the training data, and the rest for testing.
Setup. For all datasets, we use batch size of 64 and set up = 0.5. We train 40 epochs and decay the learning rate by 10 at epoch 12 and 24. The learning rates of SGD, SDCA, SSDC-SPG and SSDC-Adagrad, the learning rate of the inner loop of SBCD (i.c., //7e/(1 + m))),, and m in SMAG all tuned from {10, 1, 0.2, 0.1, 0.01, 0.001). The learning rate of the outer loop in SDCA and no in SMAG are tuned from {0.1, 0.5, 0.9). The numbers of inner loops for all double-loop methods are tuned from {2, 5, 10). The in SBCD, 1/7: in SSDC-SPG and SSDC-Adagrad, in SMAG are tuned in (0.05, 0.1, 0.2, 0.5, 1, 2). We run 4 trails for each setting and plot the average curves.
Results. We plot the curves of training losses in Figure I For all tested datasets, the performance of SMAG surpasses the baselines. Among the baselines, SBDC the generally the next best choice. However, since SBDC is double-loop method, it has one more hyperparameter compared to SMAG. We also present the ablation study of SMAG regarding the parameter y in Figure included in the Appendix.
8

---

Rishion-MNE MNIST
NNIST
CIFAR1O
PER2013
SBCO
Spach
Tooch
Taech
Spoch
Figure I: Training Curves of PU Learning
5.2 Partial AUC Maximization with Fairness Regularization
AUC Maximization aims to maximize the area under the curve of true positive rate (TPR) vs false positive rate (FPR). It has been studied extensively 44
and has shown great success in large-scale real-world tasks, e.g., medical image classification [6 and molecular properties prediction [35]. One-way partial AUC (OPAUC) is an extension of AUC that has primary interest in the curve corresponding to low FPR. To be specific, OPAUC restrict the FPR to the region [0, p) where p E (0, 1). A recent work (52) proposed to formulate OPAUC problem into a non-smooth weakly convex optimization problem using aenditional-vale-at-iiee (CVaR) based distributionally robust optimization (DRO). The formulation is given by
46
20
9
min W.SER"+
Fpauc (w,s) = n2+
Σ XLES+
8i sit
Σ (I(w;X;,x)) si)+ XyES-
(8)
pm
where S_ are the sets of positive and negative samples respectively, n4 = =1 n_ =_ - and denotes the weights of encoder network and classification layer. The pairwise surrogate loss is defined by L(w; X,, Xj) E(h(w w, x:) - 1h( xj)) and we use squared hinge loss as the surrogate loss, i.c., (()) = (c ) where c is a parameter.
However, directly solving the above problem may end up with a model that is unfair with respect to some protected groups (e.g., female patients). Hence, we consider a formulation that incorporates an adversarial fairness regularization:
max Fraic (w w.) ))= := Exx,a)_D, {I(a = 1) log(o(w, X)) + I[(a = log( o(w, Wa, x)) }
where a (w, Wa, x) denotes a predicted probability that the data has a sensitive attribute a =1 by using classification head wa top of the encoded representation of x. This adversarial fairness regularization has been demonstrated effective for promoting fairness [37] As a result, we consider OPAUC problem with fairness regularization:
min max Fpan:(W (w.s) s) + a.Fiai w.) + Ao W
2 |/wal
(9)
It is clear that the problem is WCSC.
Baseline. We implement our proposed method SMAG for solving OPAUC problem (8) and OPAUC problem with adversarial fairness regularization (9) We refer the former as SMAG* and the latter as
SMAG. The baseline on OPAUC problem (8) is SOPA, proposed in [52]. The baselines OPAUC
problem with adversarial fairness regularization 9 are SGDA 19 and Epoch-GDA 440.
Dataset. CelebA contains 200k celebrity face images with 40 binary attributes each, including the
gender-sensitive attribute denoted as Male. our experiments, we conduct experiments on three independent attribute prediction tasks: Atractive, Big Nose, and Bags Under Eyes, which have high Pearson correlations [2] [27] with the sensitive attribute Male. We divide the dataset into training, validation, and test data with an 80%/10%//05 split.
Setup. For all experiments, we adopt ResNet- 18 as our backbone model architecture and initialize with ImageNet pre-trained weights. The batch size is 128. We set the FPR upper bound to be p = 0.3. We train the model for epochs with cosine decay learning rates for all baselines. The regularizer parameter is tuned in 0.1, 0.2, 0.5 for SGDA, Epoch-GDA, and SMAG, and the adversarial learning rates are tuned in 0.001, 0.01, 0.1. a = for SOPA and SMAG* The initial learning rates for optimizing are tuned in 0.1, 0.01, 0.001 for all methods, while the weight interpolation parameters,

---

i.., Y in Epoch-GDA and SMAG, are also tuned in 0.1, 0.01, 0.001. The inner loop step is tuned in (5, 10, 15) for Epoch-GDA. 7n in SMAG are tuned from {10, 1.2.2 0.1, 0.01, 0.001}.
Results. We report the experimental results on three fairesss metrics [27]. equalized odds difference (EOD), equalized opportunity (EOP), and demographic disparity (DP) in Table We observe that SMAG consistently achieves the highest pAUC score and lowest disparities metrics across all tasks compared all other baseline min-max methods.
Table 3: Mean + std of fairness results on CelebA test dataset with Attractive and Big Nose task labels, and Male sensitive attribute. Results are reported on 3 independent runs. We use bold font to denote the best result and use underline to denote the second best. Results on Bags Under Eyes are included in the appendix due to limited space.
Big
Methods
PAUCT
FOD]
EOP.
DP
pAuci
RODJ
EOP]
DP!
SOPA
0.8485
0.022
0,2638 + 0.035
0.2488 + 0.032
0.4753
0.025
08039
0.005
0.2829 + 0.0044
0.2269 +: +-0.19
0.4424
0014
SMAG
0.8606
0.003
0,2152 1: 0.020
0.2333
1 0.068
0.4510 1 0.027
0,8078
0.002
0.2735 1: 0.0012
0.2205
4: 0.030
0,4361
0.019
SGDA
0,8509
0001
0.2701
0,020
02518
0.025
0,4860
0.015
0.008
0.002
0.2846
0.003
0.2396
1 0.099
0,4300
0028
0,2290
0.12
SMAG
0.02
0.1648
0.031
0.001
0.2148
0.001
0013
Conclusion
In this study, we have introduced a new framework namely DMax optimization, that unifies DWC optimization and non-smooth WCSC min-max optimization. We proposed single-loop stochastic method for solving DMax optimization and presented a novel convergence analysis showing that the proposed method achieves a non non-asymptotic convergence rate of O(e Experimental results on two applications, PU learning and OPAUC optimization with adversarial fairness regularization demonstrate strong performance of our method. One limitation of this work is the strong convexity assumption on the ((x,-) and (xx, -). This strong assumption may limit the applicability of our method. Future work will focus on exploring DMax optimization with weaker assumptions.
Acknowledgment
We thank anonymous reviewers for constructive comments. Q. Hu and T. Yang were partially sup- ported by the National Science Foundation Career Award 2246753, the National Science Foundation Award 2246757, 2246756 and 2306572. Z. Lu was partially supported by the National Science Foundation Award IIS-221 1491, the Office of Naval Research Award Force Office of Scientific Research Award FA9550-24 005550024--0333 24-1--343.
and the Air
10

---

References
[1] Radu Ioan Bot and Axel Böhm. Alternating concave minimax problems. SIAM J. Optim., 33:1884-1911 2020.
steps for (stochastic) nonconvex-
[2] Luigi Celona, Simone Bianco, and Raimondo Schettini. Fine-grained face annotation using deep multi-task cnn. Sensors, 18(8):2666, 2018.
[3] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model- based minimization of weakly convex functions, 2018.
[4] Damek Davis and Benjamin Grimmer. Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM Journal Optimization, 19(3):1908-13 1930, 2019.
[5] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 191611441-14, 2012.
[6] Ian J. Goodfellow, Dumitru Erhan, Pierre Luc Carrier, Aaron Courville, Mehdi Mirza, Ben Hamner, Will Cukierski, Yichuan Tang, David Thaler, Dong-Hyun Lee, Yingbo Zhou, Chetan Ramaiah, Fangxiang Feng, Ruifan Li, Xiaojie Wang, Dimitris Athanasakis, John Shawe-Taylor, Maxim Milakov, John Park, Radu Ionescu, Marius Popescu, Cristian Grozea, James Bergstra, Jingjing Xie, Lukasz Romaszko, Bing Xu, Zhang Chuang, and Yoshua Bengio. Challenges in representation learning: A report on three machine learning contests, 2013.
[7] Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms of the adam family and beyond, 2022.
[8] Mert Gürbüzzalaban, A. Ruszczynski, and Landi Zhu. A stochastic subgradient method for distributionally robust non-convex and non-smooth learning. Journal of Optimization Theory and Applications, 194:1014 1041, 2022.
[9] Quanqi Hu, Yongjian Zhong, and Tianbao Yang. Multi-block min-max bilevel optimization with applications in multi-task deep maximization. In S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 29552-29565. Curran Associates, Inc., 2022.
[10] Quanqi Hu, Dixian Zhu, and Tianbao Yang. Non-smooth weakly-convex finite-sum coupled compositional optimization. ArXiv, abs/2310.032.1 10.00233, 2023.
[11] Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth-order momentum methods from mini to minimax optimization. ArXiv, abs/2008 081 17, 2020.
[12] Chi Jin, Praneeth Netrapalli, and Michael Jordan. What local optimality in nonconvex- nonconcave minimax optimization? In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 4880 4889. PMLR, 13-18 18 Jul 2020.
[13] Ryuichi Kiryo, Gang Niu, Marthinus Christoffel du Plessis, and Masashi Sugiyama. Positive- unlabeled learning with non-negative risk estimator. ArXiv, 703/1703,,093,, 2017.
[14] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[15] Hoai An Le Thi, Van Ngai Huynh, Tao Pham Dinh, and Hoang Phuc Hau Luu. Stochastic pffcrrecceoo--conee--fuueee
algorithms for nonconvex programming. SIAM Journal on Optimization, 32(3):2263-23) 2293, 2022.
[16] Hoai An Le Thi, Hoai Minh Lc, Duy Nhat Phan, and Bach Tran. Stochastic dea for minimizing a large sum of de functions with application to multi-class logistic regression. Neural Networks, 132:220-2311 231, 2020.
[17] Hoai An Le Thi, Hoang Phuc Hau Luu, and Tao Pham Dinh. Online stochastic dea with applications to principal component analysis. IEEE Transactions on Neural Networks and Learning Systems, 35(5):7035-7047 2024.

---

[18] Hoai An Le Thi and Tao Pham Dinh. De programming and dca: thirty years of developments. Mathematical Programming, 169, 01 2018.
[19] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concay minimax problems. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th Inter- national Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6083-6093. PMLR, 13-18 Jul 2020.
[20] Mingrui Liu, Zhuoning Yuan, Yiming Ying, and Tianbao Yang. Stochastic auc maximization with deep neural networks. arXiv preprint arXiv: 10831, 2019.
[21] Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent minimax problems. In H. Larochelle, M. Ran- zato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20566-20577. Curran Associates, Inc., 2020.
ascent for stochastic nonconvex-strongly-coome
[22] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks, 2019.
[23] Gabriel Mancino-Bai and Yangyang Xu. Variance-reduced accelerated methods for decen- tralized stochastic double-regularized nonconvex strongly-concay minimax problems. ArXiv, abs/2307. 0e//2307.07111 13, 2023.
[24] J.J. Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société Mathématique de France, 93:273-299, 1965.
[25] Abdellatif Moudafi. A Regularization of DC Optimization. Pure and Applied Functional Analysis, 2022.
[26] Atsushi Nitanda and Taiji Suzuki. Stochastic Difference of Convex Algorithm and its Applica- tion to Training Deep Boltzmann Machines. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 470-478. PMLR, 20-22 Apr 2017.
[27] Sungho Park, Jewook Lee, Pilhyeon Lee, Sunhee Hwang, Dohyung Kim, and Hyeran Byun. Fair contrastive learning for facial attribute classification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10389-10398, 2022.
[28] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max op- timization: Provable algorithms and applications in machine learning. arXiv preprint arXiv: 2018.
[29] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. min-max optimization: provable algorithms and applications in machine learning. Optimization Methods and Software, 37(3): 2022.
[30] R.T. Rockafellar, M. Wets, and R.J.B. Wets. Variational Analysis. Grundlehren der mathematis- chen Wissenschaften. Springer Berlin Heidelberg, 2009.
[31] Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying some distribu- tional robustness with principled adversarial training, 2020.
[32] Kaizhao Sun and Xu Andy Sun. Algorithms for difference-of-coonee programs based on smoothing. INFORMS J. Optim., 5:321-339, 2022.
[33] Pham Dinh Tao and El Bernoussi Souad. Algorithms for solving class of nonconvex optimiza- tion problems. methods of subgradients. North Mathematics Studies, 129:249-271, 1986.
[34] Hoai An Le Thi, Hoai Minh Le, Duy Nhat Phan, and Bach Tran. Stochastic DCA for the large-sum of non-convex functions problem and its application to group variable selection in classification. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3394-3403. PMLR, 06-11 Aug 2017.
12

---

[35] Zhengyang Wang, Meng Liu, Youzhi Luo, Zhao Xu, Yaochen Xie, Limei Wang, Lei Cai, Qi Qi, Zhuoning Yuan, Tianbao Yang, and Shuiwang Ji. Advanced graph and sequence neural networks for molecular property prediction and drug discovery. Bioinformatics, 38(9):2579-2586 02 2022.
[36] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. ArXiv, abs/1708.07745; 2017.
[37] Qizhe Xie, Zihang Dai, Yulun Du, Eduard H. Hovy, and Graham Neubig. Controllable invariance through adversarial feature learning. In Neural Information Processing Systems, 2017.
[38] Tengyu Xu, Zhe Wang. Yingbin Liang, and H. Vincent Poor. Enhanced first and zeroth order variance reduced algorithms for min-max optimization. ArXiv, abs/2006.09361, 2020.
[39] Yi Xu, Qi Qi, Qihang Lin, Rong Jin, and Tianbao Yang. Stochastic optimization for DC functions and non-smooth non-convex regularizers with non-asympiotic convergence. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 6942-6951. PMLR, 2019.
[40] Yan Yan, Yi Xu, Qihang Lin, Wei Liu, and Tianbao Yang. Optimal epoch stochastic gradient de- scent ascent methods for min-max optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5789-5800. Curran Associates, Inc., 2020.
[41] Yan Yan, Yi Xu, Qihang Lin, Wei Liu, and Tianbao Yang. Sharp analysis of epoch stochastic gradient descent ascent methods for min-max optimization. arXiv preprint 20Xiv:2002.05300 2020.
[42] Junchi Yang, Xiang Li, and Niao He. Nest your adaptive algorithm for parameter-agnostic nonconvex minimax optimization. ArXiv, abs/2206.000743, 2022.
[43] Junchi Yang, Antonio Orvieto, Aurelien Lucchi, and Niao He. Faster single-loop algorithms for minimax optimization without strong concavity. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 5485-5517. PMLR, 28-30 Mar 2022.
[44] Tianbao Yang and Yiming Ying. AUC maximization in the era of big data and AI: A survey. ACM Comput. Surv.,
2023.
[45] Yao Yao, Qihang Lin, and Tianbao Yang. Large-scale optimization of partial auc in a range of false positive rates, 2022.
[46] Zhuoning Yuan, Yan Yan, Milan Sonka, and Tianbao Yang. Large-scale robust deep auc maximization: A new surrogate loss and empirical studies on medical image classification, 2021.
[47] Jiawei Zhang, Peijun Xiao, Ruoyu Sun, and Zhiquan Luo. A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concant min-max problems. In H. Larochelle, M. Ran- zato, R. Hadsell, M.F. Balcan, and Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7377-7389. Curran Associates, Inc., 2020.
[48] Xuan Zhang, Necdet Serhat Aybat, and Mert Gurbuzbalaban. Sapd+: An accelerated stochastic method for
minimax problems. S. Koyejo, Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 21668-21681. Curran Associates, Inc., 2022.
[49] Xuan Zhang, Necdet Serhat Aybat, and Mert Gürbüzzalaban. Sapd+: An accelerated stochastic method for conconvex-concate minimax problems. In Neural Information Processing Systems, 2022.
[50] Xuan Zhang, Necdet Serhat Aybat, and Mert Gurbuzbalaban. Sapd+: An accelerated stochastic method for conconvex-concave minimax problems, 2023.
13

---

[51] Renbo Zhao. A primal-dual smoothing framework for max-structured non-convex optimization, 2022.
[52] Dixian Zhu, Gang Li, Bokun Wang, Xiaodong Wu, and Tianbao Yang. When AUC meets DRO: Optimizing partial AUC for deep learning with non-convex convergence guaanntee. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 27548-27573, PMLR, 17-23 Jul 2022.
14

---

A.1 share the same proof strategy, only present the proof of A Convergence Analysis
Recall that ((:) m (2x y), (x) maxze z 1b, 2), y (²))) arg max o(: y). and
=²())= arg a 2). Before presenting the proof of Theorem 4.5 first give the proof of
the proximal point estimation error bounds. As we have stated the bound for |ar prox, )l?
in Lemma 4.4 here we present the corresponding lemma for | - - (2x))l?
Lemma A.I. Suppose that Assumption 4.1 holds, 0 7 < 1/6g. and nn (/(1//55)) Then the sequences }-r}- {21 J. {x and {Gt} generated by Algorithm 7 sattisfy
Blaat ++1 prox, (zz))l 11 + 1e11 =" (prox (x+))]1
(1 1/1 (1/1 ).))
|B| prexyo (11-1))1
11/1)BBll =" (proxx (f==1)))l
2
2
2 2. 70
E B| 12M23
(1/7 - 53
m 72 5z)
Since Lemma 4.4 and Lemma
Lemma
A.1 Proof of Lemma
Proof. Recall that ((z) max 6(I, 3) and (²) arg yax Ø(:, y). Observe from As- sumption 4.1 that 4 is we-well convex. It then follows that prox, (-) is 1/(1 -oisshhip continuous, By this, Assumption 4.1 iii) and Lemma 4.2 it is not hard to see that y yprrox (-)) is Lø.y (p y64)) Liipschitz continuous.
For notational convenience, we let
1
e, y) = 6(z, y) +
2n -1 xell?
z = prox (zz),
vi = y (p
(10)
In view of 10 and the update rule of x²' one has
E, |a ++ x², = Eella m d. th (z Ut) - 10
| - x3,111 - -2E, (m ô. 22 (2 1/:), - -xo,)) + E8 |I 0g (x 3131
(11)
< |a - 2221112 2 + 20/1 (0 (z W)) Iō. - -aa)) + + 2n/
1 - 2b.1
72
(4)
where we use the inequality
1
E. 20)11 = E, 1. vr) + - (x/s x1)11
7
= vt) + 1 (o's - xz) 0.0((
(x xre)11
7
2
s 4E, 100(1 211 + 410 (Z v1
72 11 11?
2 2MP - 1 11
By (1 56) -srong convexity of (, y) and the definition of xū. in (10), one has
(0,. 10 (1 vr), ut.. - 2'))) - th ( vt) Φ (x W1.) (1/7 - do)
2 | - 2111'
(1/7
66) | 12.
< 4, - 4 ( vi)
2
15

---

Summing up these two inequalities gives
(A) S &e (1 Wr) (1's w1) + (1 vi) t1 (1 vi) (1/7 - - =/1l? (12)
Notice from the definition of of in 10) that there exists particular subgradient V Vyd(s v²¹) such that
vi Py(vt + Vny0(a vi)).
Using this and the update rule of Mt++1, we have
E, Bellv441 va 2l2 = 1. (ve + m1 V (r') Uc)) - 112
(y + 1/1 V, t (x 1t)) - Py 'h1 (1 )1
< BBellu m V. T (1 m11) (vi + m V V. )112
s llve vi 112 21/ (V (1 vt) ( VE Dt -v2)
(13)
+ E || V,, ( yb) V, ( Vi ||
I l1ve 1/ 11 + 2m D. wo) V (2 Vi v D/ vt) +4n M
By Msg-Stonn concavity of (1. ). we have
(B) (- v, (x Ue .. ve)
(-V, v,
( V,
ve Vv vt)
D. vf) (1 vr)
2 l1yi yell
(14)
N 1 ye 11
(1 )1) + ( v()
= (2 vt) + Le(2' yr) - ( 41) + De De (2b. 8i) - -ollet - yell?
Combining 12 and 14) yields
(A) + (B) S - (1/7 50) lat..e - - Mollye - 12
Using this inequality, and 13 we have
E, Baa ++1 _= 2 + E, 11 - 112
$ (1 11-2mm/ (1/7 56) + 2////>>1lazx - 2./112 (1 2 yell2 + 12M2
(a)
2 (1 m (1/7 - 56))1 = - -1//12 +(1 22m2mo - 11? + 12M2
(M)
$ (1 (1/7 56)) (11 11 (1(7 -do)) ||ay - - 112 (1
|| -
z²,el1
771 (1/17 - 66)
+ (1 2mH4) ((1 + m1Hb))l - 1/2111 + (1+ (m/ -2) 11115-11 - vi 112) + T7
1 mi (1/7- de)
2
|1 x 11: 1/11// / 5,))
| - x1,.112
2
(1 mma) 1/-11
+ +mmp)) ( -111yi_1 - yr 1| + 12M2
(1(1/7 66)
|1 - x x 112 + (1 11---)))l - Ví- 112
2
2no
L g.yz
No 2
+
||G.|12 + 12M
(1/7 - 53
7/
(1/7 -2
where (a) follows from the assumption 7n < (11/7-60) (b) uses the fact that ||a + b1l2 < (1 +
|||l + (1+ 1)[Bb|12 2 for any 0, (c) follows from bounding the coefficient of each term from above, and (d) uses 1/(1 - 76g) Liisshhtt continuity of prox, Lo. / (1 - (-6)))-Lipschic
continuity of y" (prox, (-)) and the update rule of zt-
Finally taking expectation over all randomness yields the desired result.
16

---

A.2 Proof of Theorem 4.5
We first present a detailed version of Theorem 4.5
Theorem A.2. Consider Problem 1 and assume Assumption 4.1 holds. Suppose that the parameters
V, no and In Algorithm 7 are chosen as follows:
1/7
1/7 de
)
0 < minfog' , ,67
=mmin min
722 1 2
min { 1, 7²a S
2r
2 7- m/pminf88 do}
min
LF
4 1 4L
(1/7 ds) 7211/7 -w))
1
min
72) ("
min fa. J vo
min
{ 170 T/
2
768r M2
Then we have
c²
Σ
[ 1 - prox, (xx))l + E1 prox,v (zt))l V. S min(1,
T
"4'
t=0
and consequently z²y and a² are both nearly e-critical points of problem
whenever
1x0F F + Po)
2
768 M
T 2 min a rve? max 772(1/7 20)'22(1/1 - 8,)
FLF,, min 72) min fa, 7) vae (15)
with
2njo
Po =
(Bl1z² prox, (xo))l BBB31 36112 El prox (zo)]1 + --ill²)
7
Proof. For notational convenience, let
x/..t t = prox, (xt),
= arg max ( 2). ZEZ
(16)
From Proposition 3.3 we know that (-) is sm-sth. By this, 0 < 110 S 2h. and Lemma
4.3
one has
1/0 (T((111) S (x)) 110 (x,((.)) G1+1l12 - 1IVF
110 ||++11
(17)
Notice that
V (x+) = 7 (prox,, (xx) - 2x I1+ - prox,o (x+)) = 7 (prox (2x) - proxyo((x))
(+1). ). G4+1 (x x x
Using these, I0 and (16), we have
VFF (zt) G+till² |1> 1 (prox, (xx) prox (2:)) (xx)) x- (x (x
1 2 7 (x x ++1)11 I12
(18)
S 2y (1 - 1
1112 + ||=r,r x// 11e)
It follows from this and (17 that
B(F,(Z411)
< E F., (zx)
+
100
BIl r+1 - , +
1o
El x..2
722
722 To G||
(19)
n70
VF, (1)))
Let 26,, and zi be defined in (10 Invoking Lemma 4.4
we have
E| El
x² 1
112
Elll/442 11+1
(11/7
-66)
El
E
=bb + (1 - 711)) - vill"
2
2no
T 2. Tm
+
+
El|G141 2 + 12
(1/2
-5,33
mP3
2 -80)2
17

---

Recall that zit, and 2x are defined in (16). By Lemma A.1 one has
E 1
++2
I. c+1
11
El| =+11l
(1/7 - dm)
Blla
++1
- .el + (1 7114) BBI -z =2ill
2
2n
12 Vo
B||G++11l 12.2
(1/7 8,)3
7 80
Let a be given in the statement of this theorem. Using this and the last two inequalities above, we have
El +22
22 11? + Elly/+2 Mi+1ll2
s (1 am)) (BB1 =0 2 11lb/++1
3E 2)
(20)
2115
L2 L2 Th
El|G,41 12 12M
m172(1/77 - -6,3
2 80)2
E x xb, .+, 112
EBl22422 21+1l1 1|
< (1 om ) (BI|
J. x. .12 + EE|| - = 11²))
(21)
2nd
T 12
+ mi 22 8,
E| G| + 12.²
1172 83)3
Summing up inequalities
19. 20
20
x
2nl 7
and
2no 21
n yields
2nju
E (2++1))
+
F. 111l 21
R 1112 - vi-1ll 112)
+ 27o
x ++1
1| + E| - 2 12)
7
< E (xxe))
+
21/0
(1
1/20))
[B1lz r + Ellyt++ 1/8 v1l)3)
2/1220
2
+ 2no
(1-
71a
++1
xb,el
1|2 + E El1411 - 2/5 113)
2
(22)
4np
4nd
2L G.yz no
7//A/(1/1 66)3
ai/aa(1/7 -8
aa 60)²
21
20 1
170
Bl|Gr+1112
)
4
24 M 2a
24 M2 22a
No (x)))
We now introduce potential function
2no0
x6,,11 2 - =2]12). (23)
P.
x2 + Ellut+1 11 + Bl
7
and rewrite inequality 22 as
E F (I 11) + P
48mum M
< (x.) + + (1- -)- VF,
72a
T2 Th
T
mh
+ niata
E G
n Aa3
4
18

---

where
a 70
B = min
(24)
2 2
This inequality, together with the choice of vo and specified in this theorm, yields
48mom M
(1 + P2+1 S +1 3)P: 3E V2
y²a
Taking average of these inequalities over & = .,. yields
Fy (xo) - F + Po
48num
E (P. (I++)
(25)
BT
37
where we use F P. (2T) due to Assumption 4.1 (ii). Recall that 1/o = 7th and v min Using these,
2r
7"
23
and
25
we have
E
2
+B
=b,ell 112
B VF,
T
1=0
T-1
VI, < Fx(20) F Po
48nom M vBT2a
PP Σ
+
DST
By 24 and the choice of nlo and specified in this theorem, one has m min { ma
min 1a.1-,1111011000 2
} vac? min ? min {a, r) vo ? 4/1
384%) M2
r M
7687 M2
which implies that
48no7 M
e
v8y2a S min
Suppose that 7 satisfies 15
It then follows from 24 100
TT), and the expression of 1/1 that
(6(F, - F + Po)
2
768- M
T
2L
min(1,,72) min u)
2//
56) 72/17 5x)
min (1, min {a, 7) var
(0F) Fイ Pb)
min
which implies that
(x)) F7 Po
2
min (1,7-1
vST
8
Hence, for any T satisfying 115 one has
T Σ (Batt =²,ell 2 EE| - - x VE, s min 2
T
which together with 25. = prox, (xx) and ai., = prox o (2x) yields
Σ [l - prox, (xx))l + EE| prox prox, (1x) BI s min[1, c
Since Z uniformly sampled from {1,..., T). we have
prox p (1 + || prox (== (VV min 1 -2)
then follows from Lemma 3.4 that of and 5.f are both nearly e-critical points of problem
19

---

A.3 Proof of Corollary 4.7
We present a detailed version of Corollary 4.7
Corollary A.3. Consider Problem 2 and assume Assumption holds. Suppose that the parameters
7, No and IJ Algorithm 2 are chosen as follows:
1/7
8
1/7
dgb
222²
min { 1,
2r
0 m ,871) 1,
min
{1.
2
2
4
(1/7 6②)
1117 6v)
1
m
min fa, r vo
M min
170 -!/--
2L.TT'
768T M
Then we have
T-1 Σ
(1))) < min c²
[B
6+1 - prex (1x))1 + BlI prox
0
and consequently 2 and a.y are both nearly c-critical points of problem
whenever
(6( - F + Po)
2
768TM²
min(1, ain TJVE?
max 772(1/7 - 66) 7211/7 - 6,)
2L
min (1, min far 7) vae
with
27
(Bl|a) prox, ( E|| E prox, (xn)))?)
22a
Since problem 2 and Algorithm are special cases problem [ and Algorithm respectively,
Corollary A.3 directly follows from Theorem A.2
A.4 Proof of Corollary 4.9
We present a detailed version of Corollary 4.9
Corollary A.4. Consider Problem 3 and assume Assumption % no and IjI Algorithm 3 are chosen as follows:
4.8
holds. Suppose that the parameters
1/7 - 5
a22²
p
115722225
== min { 1, 2r
0 <<>9
<5 $ a min amin
min
2
4
4L
(1,72''
(1/r - 6z)
min (1, ?2
min fa, r} va
71 min
170 Tm
2LPT
38
Then we have
2
Σ
[E x
++1 - 6
EE < min -
T
and consequently xe is nearly c-critical point of problem whenever
16(F,(ax) F Po)
384r M2
T2 min min (a, +lve
max /2 5%)
2TFT,
min far r) vac
with
2mjo [EEl(a)
Po = 2
prox, (2o)
Ells1 v6).
Proof. This proof is similar to that of Theorem A.2 except that the inequality 18) is replaced by
[V,( 11+1l12
(xx prox,
(xx
2 (+1)
7
p - -z/5 112
22
20

---

B More Experimental Results
CRTVEa-0.05 genniaa
gumetar1
Figure 2: Ablation Study of SMAG for PU Learning
Table 4: Mean + std of fairness results on CelebA test dataset with Bags Under Eyes task labels, and Male sensitive attribute. Results are reported on independent runs. We use bold font to denote the best result and use underline to denote the second best.
Bags Under
Methods
PAUCT
EOD
EOP:
DP 1
0.2015
0.027
SMAG
0,8261 + 0.004
0.1848
0.023
0.1065
0.046
0.3754
0.033
SGDA
0.8307 1 0.003
0,2026
0.088
0.1096
0.011
0,4028
0.039
EGDA
0.8262 1 0.004
0.2223
0.032
0.1287
4 0.038
0.4200
0.024
SMAG
0,8278 + 0.002
0,1642
0.025
0,0982:
0.034
0,3690
0.029
21

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We have detailed explanation on all items described in the abstract presented in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
22

---

Justification:
We discussed the limitation of this in the conclusion section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specifiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions presented in the main paper. The detailed theorem statements and proof's are presented the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide all the information needed to reproduce the experimental results in the application section.
Guidelines:
23

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code is included in the supplemental material. The data we used are public
datasets.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nisscc/public//uuss http://////iiiee///deuuubiiiiiii
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
24

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provided all the implementation details in the application section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We ran multiple trails for each experiment setting and present the error bars in the plot or table.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Yes. Compute resources information provided in the application section.
Guidelines:
The answer NA means that the paper does not include experiments.
25

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:///aaarrra..coooaaalccccaaa
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pre-trained language models, image generators, scraped datasets)?
Answer:[NA]
26

---

Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: For all assets we used this paper, we cited their original source.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, haperswithcode com/ datasets has curated licenses for some datascts. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
27

---

Answer:
[NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "I889Ly454E", "reviewer": "Reviewer_jGsv", "summary": "The paper studies a class of optimization problem named DMax, i.e., to minimize a loss that is a difference of two max functions. This problem covers both difference of weakly-convex optimization and weakly-convex strongly-concave minimax optimization. Existing algorithms require double-loop structure to solve the inner problem within certain accuracy. This paper proposes a simple single-loop stochastic algorithm that achieves state-of-the-art convergence rates. Empirical experiments demonstrate the effectiveness of the proposed algorithm.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper considers a class of difference of max-structured weakly-convex optimization problems, which can be interesting and novel in its problem fomulation. The proposed algorithm is simple to implement as it is single-loop structured and also clear to understand. The convergence rate matches exsiting works that use more complicated structures of the algorithms.", "weaknesses": "1. There are some typos that may affect readibility. (1) Is the definition of $\\Psi$ in line 3 of the abstract correct? Shouldn't it be $\\max_z\\psi$? (2) I guess that it should be \"Single-Loop\" in the title? (3) In line 27, there is an empty citation for adversarial learning. (4) In line 49, \"sufficient to to\". (5) \"covnex\" in line 4 of Table 2. (6) Should it be $\\partial_x \\psi$ in line 4 of Algorithm 1 and line 3 of Algorithm 2?\n\n2. Although the problem fomulation is interesting in optimization theory, the current applications seem to be limited to only applications of the special cases DWC and WCSC min-max optimization. Therefore, the problem can be a little bit artificial in the sense that these applications do not necessarily require such a formulation. It can be done by studying DWC and min-max separately, and the major benefit is that DMax provides a unified way. Are there examples that DMax gives more applications beyond DWC and min-max optimization?\n\n3. (Minor) Although I like the proposed algorithm, which is simple and clear to understand, it seems like all the technical steps exist before. The paper combines these known results and uses it for a new class of problem. For example, it is well-known that single-loop updates can give the same rate for strongly-concave problems compared to double-loop algorithms that first solve the inner-problems to a required accuracy. It is also known that weakly-convex problems can be handled using Moreau envelope and usually enjoy the same rate as smooth problems. As a result, the convergence rates and theoretical analysis in the paper are not surprising. \n\nI am the emergence reviewer. I do not carefully check all the technical details and proofs in the paper. However, the algorithmic ideas and analysis outline look good to me. I will be on the positive side with a low confidence rate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments and feedback on our paper.\n\n**Q1.** There are some typos that may affect readability\n\n**A:** Thank you for pointing out these typos. We will fix them in our revision.\n\n\n**Q2.** Are there examples that DMax gives more applications beyond DWC and min-max optimization?\n\n**A:** One example can be found in [43] for optimizing partial AUC in a range of false positive rates for binary classification. The objective can be written as \n$\\sum_{i=1}^{N^+}\\phi_{n}(s_{i}) - \\phi_m(s_{i})$, where $s_i=(s_{i1},\\ldots, s_{iN^-})$ denotes the pairwise loss between a positive data $x_i$ and all $N^-$ negative samples, and $\\phi_n$ is the an operator that outputs the sum of the top-$n$ items in the input vector. Since $\\phi_{n}(s_{i}) =\\max_{p_j\\geq 0, \\sum p_j = n}p_j s_{ij}$, as a result, $\\phi_{n}(s_{i}) - \\phi_m(s_{i})$ is a structure of DMax. \n\n\n**Q3:** About the technical novelty.\n\n**A:** It is true that single-loop updates can give the same rate for strongly-concave problems compared to double-loop algorithms that first solve the inner-problems to a required accuracy. However, existing single-loop algorithms for min-max problems all require smoothness of the objective function. In our work, we did not use the smoothness assumption in terms of $x$ and hence the analysis is completely different. In terms of technical analysis, the Lemma 4.4 is novel, which does not exist in any existing work. In addition, we introduce a special potential function $P_t$ as in Eq. (23).  These make it possible for us to prove the convergence of a special error function $E[\\|x_\\phi^t - prox_{\\gamma\\phi}(x_{t-1})\\|^2 + \\|x_\\psi^t - prox_{\\gamma\\psi}(x_{t-1})\\|^2+ \\|\\nabla F_{\\gamma}(x_t)\\|^2]\\leq \\epsilon$ for a randomly chosen $t$.", "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": "", "extra_scores": {}}, {"review_id": "oY5P5vn1Mh", "reviewer": "Reviewer_2iRa", "summary": "The paper considers the problem of minimizing a difference of maximum of two functions, under various regularity assumptions. Two important settings are difference of weakly convex functions and weakly convex strongly concave min-max problems. The authors propose a single loop algorithm with a convergence rate (defined in an appropriate sense) of $\\epsilon^{-4}$. The authors apply their method to positive-unlabeled (PU) learning and partial area under ROC curve (pAUC) optimization with an adversarial fairness regularizer, and compare against existing methods.", "questions": "1. Are the proof ideas useful to give single loop algorithms for non-smooth convex minimization via Moreau smoothing, with optimal rates?\n\n2. Optimality: Is the $\\epsilon^{-4}$ rate achieved optimal in these settings?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is generally well written. The authors motivate the technical challenges well and how to get around them rather.\n2. Getting single loop algorithms with the Moreau smoothing technique is challenging. The authors make important contributions in this regard.\n3. The experimental results are encouraging. The authors show consistent improvement in their applications over the baselines.", "weaknesses": "1. (Writing) The authors should distinguish if the difference/improvement from previous work are \"double loop vs single loop\", and/or faster rates and/or weaker assumptions. For the DWC setting, it seems it is \"double loop vs single loop\", and/or faster rates and weaker assumptions, where as for WCSC, it is \"double loop vs single loop\".\n\n2. (Writing) The authors should mention the notion of optimalities in various settings ($\\epsilon$ nearly critical and $\\epsilon$ near stationarity) eraly on, and remark that they are standard.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments and feedback on our paper.\n\n**Q1.** The authors should distinguish if the difference/improvement from previous work are \"double loop vs single loop\", and/or faster rates and/or weaker assumptions. For the DWC setting, it seems it is \"double loop vs single loop\", and/or faster rates and weaker assumptions, where as for WCSC, it is \"double loop vs single loop\".\n\n**A:** The improvement over baselines can be seen from the difference in terms of assumptions, complexity and number of loops in Table 1 and Table 2. For the DWC setting, our improvement over SDCA [25] lies at weaker assumption and single loop, over SSDC-X lies at weaker assumption, faster rate and single loop, over SBCD lies at faster rate and single loop. In the WCSC setting, our improvement over PG-SMD/Epoch-GDA lies at single loop, over SAPD+ lies at weaker assumption and single loop, and over StocAGDA lies at weaker assumption. \n\n\n**Q2.** The authors should mention the notion of optimalities in various settings (nearly critical and  near stationarity) eraly on, and remark that they are standard.\n\n**A:** Thank you the suggestion. We will revise our draft accordingly.\n\n\n**Q3.** Are the proof ideas useful to give single loop algorithms for non-smooth convex minimization via Moreau smoothing, with optimal rates?\n\n**A:** Thanks for the good question! We have not explored the non-smooth convex minimization via Moreau smoothing. It might be useful in the sense that our technique can be used to argue that with one step update of $x_t'$ for solving  $\\min_{x'}f(x') + \\frac{1}{2\\gamma}\\|x_t - x'\\|^2$, we can establish recursion of $|x'_t -  $  \n\n$ prox_{\\gamma f}(x_t)\\|^2$, where $prox_{\\gamma f}(x_t)$ is the optimal solution to  $\\min_{x}f(x') + \\frac{1}{2\\gamma}\\|x_t - x'\\|^2$. This is the error of gradient estimator of the function $F_{\\gamma}(x_t) = \\min_{x}f(x') + \\frac{1}{2\\gamma}\\|x_t - x'\\|^2$. For deep analysis, we will leave it as a future work. \n\n\n**Q4.** Is the $O(\\epsilon^{-4})$ rate achieved optimal in these settings?\n\n**Response.** We believe so. $O(\\epsilon^{-4})$ rate has been proved to the optimal even in the smooth setting for non-convex optimization [r1].\n\n\nReference.\n\n\n[r1]:  Arjevani et al. Lower bounds for non-convex stochastic optimization.  2019.", "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": "", "extra_scores": {}}, {"review_id": "MXvpYdzfii", "reviewer": "Reviewer_QoFj", "summary": "This paper proposes a stochastic Moreau envelope approximate gradient method dubbed SMAG, the first single-loop algorithm for solving these problems, and provides a state-of-the-art non-asymptotic convergence rate.\nThis paper achieves the best complexity of order $O(\\epsilon^{-4})$.\nFuthermore, the agorithm of this paper only use a single loop which is easy to implement and tune the hyperparameters. \n\nA typo: Line 3, it should be $\\Psi(x) = \\max_z \\psi(x, z)$.", "questions": "This paper considers the problem of a special structure that is the difference of convex functions. However, in this paper, this special structure seems not be used.\nAs I know, for the problem of  difference of convex functions, there are several algorithms can achieve the faster convergenc rate of general non-convex functions.\nSo, I wonder whether the results of this paper is useful enough.", "limitations": "No", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "No", "weaknesses": "No", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments and feedback on our paper.\n\n**Q:** The special structure of the difference of convex functions is not used. \n\n**A:** Thank you for your good question. (1) In this paper the problem considered is the Difference of Max-Structured Weakly Convex Functions (DMax) Optimization, which is more general than the difference of convex functions due to the maximization structure in the two component functions. Hence, we cannot use some technique like linearization of the second component as in previous work on solving difference-of-convex functions.  (2) We do utilize the difference structure to some degree. In particular, we apply Moreau envelope smoothing to each component separately instead of jointly. It is notable that even each component is weakly convex, their difference is not necessarily weakly convex. Hence, applying Moreau envelope smoothing to the joint function would not make sense.  (3) For the difference of weakly-convex functions problem (DWC), we have summarized its existing works in Table 1. To the best of our knowledge, our proposed method is the first single-loop stochastic methods and it achieves the best convergence rate $O(\\epsilon^{-4})$.", "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": "", "extra_scores": {}}, {"review_id": "TpdFmjVc9Y", "reviewer": "Reviewer_gunK", "summary": "This paper introduces a novel optimization problem termed Difference of Max-Structured Weakly Convex Functions (DMax). The DMax problem extends traditional frameworks such as difference-of-weakly-convex (DWC) optimization and weakly-convex-strongly-concave (WCSC) min-max optimization, which are widely utilized in the machine learning community.\n\nUsing a Moreau envelope smoothing technique, the authors propose a stochastic algorithm called SMAG for optimizing DMax in non-smooth settings. This approach not only addresses the DMax problem but also applies to DWC and non-smooth WCSC min-max optimization scenarios, demonstrating comparable convergence rates.\n\nExperimental results validate the efficacy of their algorithms across various applications, including Positive-Unlabeled (PU) Learning and partial Area Under the Curve (AUC) optimization with an adversarial fairness regularizer.", "questions": "In the experiments section, the authors employ a linear classification model with hinge loss (Line 271). However, this setting appears to be a smooth one, potentially limiting the demonstration of the benefits of the authors' method in non-smooth DWC problems, despite SMAG showing superiority over other methods.\nRegarding the large variance in training curves observed, such as in FER 2013 (Figure 1), it raises questions about the stability and robustness of the method in practical applications. To enhance confidence in the results, I suggest exploring parameter tuning to achieve more stable and convincing outcomes.", "limitations": "The paper is theoretical, and I believe there is no need to confirm societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality:**\nThe paper introduces a new optimization problem termed Difference of Max-Structured Weakly Convex Functions (DMax), which extends existing frameworks like difference-of-weakly-convex (DWC) optimization and weakly-convex-strongly-concave (WCSC) min-max optimization. This extension demonstrates a significant level of originality in problem formulation within the field of optimization. By addressing a broader class of problems under the DMax framework, the paper contributes novel insights and methodologies that enrich the theoretical foundations of optimization in machine learning and related fields.\n\n**Quality:**\nThe paper maintains high-quality standards across various aspects. It rigorously establishes the theoretical foundations of the DMax problem and proposes a Moreau envelope smoothing technique for optimization in non-smooth settings. The SMAG algorithm introduced is methodically developed and supported by well-defined lemmas and references, ensuring robustness and reliability in the proposed approach, though I don't check the proofs in detail.\nFurthermore, the experimental validation on applications such as Positive-Unlabeled Learning and partial AUC optimization with adversarial fairness regularization underscores the practical relevance and effectiveness of the proposed methods.\n\n**Clarity:**\nThe clarity of the paper is a notable strength. It effectively communicates complex concepts and methodologies in a clear and accessible manner, making it understandable even for readers with limited expertise in the specific problem domain. The intuitive presentation of algorithms and key steps, coupled with clear explanations of referenced lemmas, enhances readability without sacrificing depth. This clarity not only facilitates comprehension but also promotes transparency in the theoretical derivations and experimental procedures, thereby bolstering the paper's overall impact.\n\n**Significance:**\nBy addressing challenging optimization problems and providing practical algorithms validated in real-world scenarios, the paper significantly advances both theoretical understanding and practical applications in machine learning optimization.", "weaknesses": "**Problem Statement and Novelty:**\nThe paper introduces a new problem that extends traditional frameworks such as difference-of-weakly-convex (DWC) optimization and weakly-convex-strongly-concave (WCSC) min-max optimization, presenting the SMAG algorithm as a solution. However, the paper could benefit from clearer justification of how this generalization represents a significant departure from incremental advancements. This clarity is pivotal for establishing the theoretical contribution within a novel setting.\n\n**Complexity Analysis:**\nUpon examining the complexity results, it is apparent that in non-convex, non-smooth min-max problems, SMAG demonstrates complexity similar to Epoch-GDA under comparable assumptions (Table 2). This finding raises significant concerns about the broader implications for WCSC min-max optimization, particularly considering the emphasis on complexity as a contribution (Line 59). A clearer explanation is needed on how SMAG surpasses existing complexities in this domain, beyond the practical advantage of a single-loop method for tuning, to strengthen the paper's impact solely from a complexity perspective.\n\n**Algorithmic Technique:**\nThe proof and algorithmic technique employed in this study resemble SBCD, utilizing the Moreau envelope to transform non-smooth problems into smooth ones, thereby enhancing accessibility. Hence, it is crucial to clearly delineate why SMAG achieves superior complexity results compared to SBCD or to identify any overlooked aspects that may explain this discrepancy.\n\nI welcome further discussion on these points to ensure a comprehensive evaluation. Thanks!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments and feedback on our paper.\n\n**Q1:** Clarification of  theoretical contribution within a novel setting.\n\n**A.** We proposed a unified framework of analysis for non-smooth DWC and WCSC min-max problems, which leads to single-loop methods that achieves the best convergence rate. Our main contribution is the novel analysis that applies to problems with complex structures (difference of max-structured weakly convex functions) and potential non-smoothness.  In particular, in our technical analysis, the Lemma 4.4 is novel, which does not exist in any existing work. This make its possible for us to prove the convergence of a special error function $\\|x_\\phi^t - prox_{\\gamma\\phi}(x_{t-1})\\|^2 + \\|x_\\psi^t - prox_{\\gamma\\psi}(x_{t-1})\\|^2 + \\|\\nabla F_{\\gamma}(x_t)\\|^2$.\n\n**Q2:** Confusion about the complexity as a contribution (Line 59) for WCSC problems.\n\n**A:** We are sorry for the confusion. For WCSC problem, we did not intend to claim a better complexity, but rather emphasize that it is the first single-loop method with the same complexity as existing double-loop methods. The improved complexity of our algorithm lies at its application to difference-of-weakly convex functions, which can be seen from Table 1. \n\n\n**Q3:** Does the proof and algorithmic technique employed in this study resemble SBCD? \n\n**Response.** NO. The main difference between the analysis of SMAG and SBCD is in the error bounds $E\\|x_\\phi^{t+1} - prox_{\\gamma \\Phi}(x_t)\\|^2$ and $E\\|x_\\psi^{t+1} - prox_{\\gamma \\Psi}(x_t)\\|^2$. For SBCD, they use inner loops to solve for $prox_{\\gamma \\Phi}(x_t)$ and $prox_{\\gamma \\Psi}(x_t)$. In order to reach error bounds $E\\|x_\\phi^{t+1} - prox_{\\gamma \\Phi}(x_t)\\|^2 \\leq O(\\frac{1}{t+1})$ and $E\\|x_\\psi^{t+1} - prox_{\\gamma \\Psi}(x_t)\\|^2 \\leq O(\\frac{1}{t+1})$ at iteration $t$, they need to use $O(t^2)$ inner loop iterations because of the involved maximization. With $O(\\epsilon^{-2})$ outer iterations guarantees a nearly $\\epsilon$-critical point, it leads to a total sample complexity of $O(\\epsilon^{-6})$. In contrast, our analysis directly builds the recursion for $\\|x_\\phi^{t+1} - prox_{\\gamma \\Phi}(x_t)\\|^2 + \\|y_{t+1} - y^*(prox_{\\gamma\\phi}(x_{t}))\\|^2$ in Lemma 4.4. In addition, we introduce a special potential function $P_t$ as in Eq. (23). We are able to build a decreasing recursion in terms of $P_t$, i.e., $P_{t+1}$ in the left, and $(1-\\beta)P_t$ in the right of the bound (cf line 541), where $\\beta<1$. These make it possible for us to prove a better  convergence rate of a special error function $E[\\|x_\\phi^t - prox_{\\gamma\\phi}(x_{t-1})\\|^2 + \\|x_\\psi^t - prox_{\\gamma\\psi}(x_{t-1})\\|^2 + \\|\\nabla F_{\\gamma}(x_t)\\|^2]$ for a randomly chosen $t$.\n\n\n**Q4.** Misunderstanding about the hinge loss (Line 271) as a smooth function. About the large variance in training curves observed, such as in FER 2013 (Figure 1).\n\n**A.** The hinge loss is in the form of $\\ell(x,y) = \\max(0, 1- y * f(x))$ where $x,y$ are the data sample and its label, and $f(x)$ is the prediction score of the sample $x$.  This clearly is a non-smooth loss due to the presence of the function $\\max(0, \\cdot)$. Regarding the variance in the training curves: (i) the large variance of our method for FER2013 is due to a bug in the code, which loads a wrong file of one trial result for plotting. A corrected training curve of our method is included in the attached PDF file of the global rebuttal. It has much smaller variances. (ii) We have also incldued the means and standard deviations of our method on all datasets for references in the attached PDF file. It can be seen that the standard deviations are indeed one order smaller than the loss values. Please also note that the scale of the y-axis is very small, which makes the std more obvious. (iii) We have conducted hyperparameter tuning as stated in lines 283-289. Thank you!", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their valuable feedback. As Reviewer gunK noted, the training curve of SMAG for the FER2013 dataset in Figure 1 exhibits unusually high variance. After careful checking, we identified a bug in the code, which loads a wrong file of one trial result for plotting. We have included the corrected figure in the attached pdf file. We also include the mean and std of loss values of our method on different datasets in the file.

Meta-review: Paper proposes a new Moreau envelope based algorithm for solving a new class of optimization problems called Difference of Max-structured weakly-convex functions (DMax). This generalizes two others problems: Difference of Weakly-Convex functions (DWC) and Weakly-Convex-Strongle-Concave (WCSC) problems. The proposed algorithm is a single loop algorithm, which is more practical than multi-loop methods. It is proven to achieve new state-of-the-art gradient complexity for DWC problems and known state-of-the-art results for WCSC problems. Central idea is to optimize a proxy objective which is difference of Moreau envelopes than optimize the Moreau envelope of the difference. Paper also provides experimental comparison of their algorithm on two different ML problem. 

Obtaining single loop algorithm for Moreau smoothing is known to be challenging. Paper is mostly well written and experimental results are promising. Reviewers also raised a concern that most of the given applications are special cases which are not as general as the formulated problems. This was not satisfactorily addressed. There were also few typos affecting the readability. However, most reviewers recommended acceptance of this paper.
Decision: Accept (poster)