Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions

Authors: quanqi  hu
qi  qi
zhaosong  lu
tianbao  yang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 18:27:43

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.

Main paper: 
 introduction: 
 In this paper, we consider a class of non-convex, non-smooth problems in the following formEQUATIONwhere the sets Y ⊂ R dy , Z ⊂ R dz are convex and compact, and the two component functions ϕ(x, y) and ψ(x, z) are weakly-convex in terms of x and strongly-concave in the terms of y and z, respectively. Both component functions are in expectation forms, i.e., ϕ(x, y) = E ξ∼D ϕ [ϕ(x, y; ξ)] and ψ(x, z) = E ζ∼D ψ [ψ(x, z; ζ)]. We refer to this class of problems as the Difference of Max-Structured Weakly Convex Functions (DMax) Optimization. DMax optimization unifies two emerging families of problems in optimization field, difference-of-weakly-convex (DWC) optimizationEQUATIONand weakly-convex-strongly-concave (WCSC) min-max optimization Thus, DMax optimization has a wide range of applications in machine learning and AI, including applications of DWC optimization (e.g., positive-unlabeled (PU) Learning [39] , non-convexCorrespondence to: Tianbao Yang <tianbao-yang@tamu.edu>.Table 1 : Comparison with existing stochastic methods for solving DWC problems with nonasymptotic convergence guarantee. * The method SBCD is designed to solve a problem in the form of min x {min y ϕ(x, y) -min z ψ(x, z)} with a specific formulation of ϕ and ψ. However, the method and analysis can be generalized to solving non-smooth DWC problems.Smoothness of ϕ, ψ Complexity Loops SDCA [26] ϕ: Smooth O(ϵ -4 ) Double SSDC [39] ϕ or ψ: ν-Hölder continuous gradient O(ϵ -4/ν ) Double SBCD * [45] Non-smooth O(ϵ -6 ) Double SMAG (ours)Non-smooth O(ϵ -4 ) Single sparsity-promoting regularizers [39] , Boltzmann machines [26] ) and applications of min-max optimization (e.g., adversarial learning [31, 22] , distributional robust learning [8, 28] , learning with non-decomposable loss [28] ). In recent years, the scale of data and models significantly increased, leading to 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(ϵ -4 ) are double-loop. As a result, these methods are complex regarding the implementation and require extensive hyperparameter tuning. To close this gap, we propose a single-loop stochastic algorithm for DMax optimization and provide non-asymptotic convergence analysis to match the state-of-the-art non-asymptotic convergence rate.The main challenges of designing a single-loop method for DMax optimization are threefold. 1) given the weakly-convex nature of the component functions, their difference F (x) is not necessarily weakly-convex, resulting in a non-smooth non-convex optimization problem. 2) the component functions max y∈Y ϕ(x, y) and max z∈Z ψ(x, z) require solving maximization subproblems, making unbiased estimations of their subgradients inaccessible. 3) existing work on 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, 3] to the component functions individually and take their difference as a 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, we perform only one 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 are sufficient to achieve a state-of-the-art 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] or require smoothness of the objective function [47, 43] .Contributions. We summarize the main contribution of this work as following.• We construct a new framework DMax optimization that unifies the DWC optimization and WCSC min-max optimization. Based on a Moreau envelope smoothing technique, we propose a singleloop stochastic algorithm, namely SMAG, for DMax optimization in non-smooth setting, which achieves O(ϵ -4 ) 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(ϵ -4 ) convergence rate. • Finally, we present experimental results on applications including Positive-Unlabeled (PU) Learning and partial AUC optimization with an adversarial fairness regularizer to validate the effectiveness of our proposed algorithms. 
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. A comprehensive review on the developments of DC programming can be found in [18] . Despite the [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 [16] . [15] 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 was established in [26] . The 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 a convergence rate of O(ϵ -4 ). 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ölder continuous gradient, i.e., ∥∇f (x) -∇f (x ′ )∥ ≤ ∥x -x ′ ∥ ν for all x, x ′ , they proved a convergence rate of O(ϵ -4/ν ). 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.Recently, another approach to tackling the non-smoothness in DC problems has been considered. Following the smoothing technique in non-smooth weakly-convex optimization literature [3] , [32, 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 one component function is smooth or the proximal-point subproblems can be solved exactly. Following a similar idea, [45] studied a problem in the form of min x F (x) := min y ϕ(x, y) -min z ψ(x, z), where ϕ and ψ are in some specific formulations, and proposed a double-loop algorithm with O(ϵ -6 ) convergence rate. Although the ϕ and ψ are non-smooth, their analysis heavily relies on the properties in the given formulation, especially the structures in the dual variables y, z, 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 Weakly-Convex-Strongly-Concave Min-Max Optimization. Stochastic WCSC min-max optimization has been an emerging topic in recent years. Most of the existing works focuses on the smooth setting, i.e., the objective is smooth [12, 19, 49, 43, 47, 43] or the stochastic gradient oracles are Lipschitz continuous [23, 42, 11, 21, 38] . To the best of our knowledge, [29] is the first work that considers non-smooth WCSC min-max problems. They considered a special structure where the maximization over y given x can be simply solved and it is solved with O(1/ϵ 2 ) times. They proposed a nested method Proximally Guided Stochastic Mirror Descent Method (PG-SMD) that achieves a convergence rate of O(ϵ -4 ). Later, [40] further relaxed the assumption by removing the requirement of the special structure, and proved that their nested method Epoch-GDA has a similar convergence rate of O(ϵ -4 ). Another line of work studies a special case of the general non-smooth non-convex min-max optimization, where the objective is assumed to be composite, i.e., ϕ(x, y) = f (x, y) -g(y) + h(x), so that f is smooth while g, h are potentially non-smooth [1, 48] . Both works established O(ϵ -4 ) 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. 
preliminaries: 
 Notations. For simplicity, we denote Φ(x) := max y∈Y ϕ(x, y), Ψ(x) := max z∈Z ψ(x, z), y * (•) := arg max y∈Y ϕ(•, y), and z * (•) := arg max z∈Z ψ(•, z). We use ∥ • ∥ to denote the Euclidean norm of a vector and P C (•) to denote the Euclidean projection onto a closed set C. We use the following definitions of general subgradient and subdifferential [3, 30] . Definition 3.1 (subgradient and subdifferential). Consider a function f : R d → R ∪ {∞} and a point x with finite f (x).A vector v ∈ R d is a general subgradient of f at x if f (y) ≥ f (x) + ⟨v, y -x⟩ + o(∥y -x∥) as y → x.The subdifferential ∂f (x) is the set of subgradients of f at point x.For simplicity, we abuse the notation ∂f (x) to denote one subgradient from the corresponding subdifferential when no confusion could be caused. We use ∂f (x) and ∇f (x) to represent an unbiased stochastic estimator of the subgradient ∂f (x) and the gradient ∇f (x) respectively. A function f :D → R is said to be L-smooth if ∥∇f (x) -∇f (x ′ )∥ ≤ L∥x -x ′ ∥ for all x, x ′ ∈ D. A function f : R d → R ∪ {∞} is δ-weakly convex if f (•) + δ 2 ∥ • ∥ 2 is convex. A mapping M : D → R l is said to be C-Lipschitz continuous if ∥M(x) -M(x ′ )∥ ≤ C∥x -x ′ ∥ for all x, x ′ ∈ D.Consider solving a non-smooth problem min x f (x). One of the main challenges is that the ϵstationary point, i.e., a point x such that dist(0, ∂f (x)) ≤ ϵ, which is the typical goal for smooth problems, may not exist in the neighborhood of its optimal solution. A classical counter example would be f (x) = |x|, where for ϵ ∈ [0, 1) the only ϵ-stationary point is the optimal solution x = 0. A standard solution to this issue in weakly-convex setting is to use a relaxed convergence criteria, that is to find a point no more than ϵ away from an ϵ-stationary point. This is called a nearly ϵ-stationary point, and is widely used in non-smooth weakly-convex optimization literature [4, 29, 41, 50, 51, 19] . In fact, finding a nearly ϵ-stationary point for f (x) can be achieved by finding an ϵ-stationary point of f γ (x), the Moreau envelope of f (x). Assume function f is δ-weakly-convex, then its Moreau envelope and proximal map are given byf γ (x) := min x ′ f (x ′ ) + 1 2γ ∥x ′ -x∥ 2 , prox γf (x) := arg min x ′ f (x ′ ) + 1 2γ ∥x ′ -x∥ 2 .Existing work [3] has shown that with γ ∈ (0, δ -1 ) and x = prox γf (x), we have∇f γ (x) = γ -1 (x -x), f (x) ≤ f (x), dist(0, ∂f (x)) ≤ ∥∇f γ (x)∥.Moreover, prox γf (x) is 1 1-γδ -Lipschitz continuous [32] . Now we consider the DMax problem (1) . By Danskin's Theorem, the weak convexity assumption of ϕ(•, y) and ψ(•, z) naturally leads to the weak convexity of Φ(•) and Ψ(•). Since the weak convexity assumption of component functions does not guarantee the weak convexity of their difference function F (x), one may neither 1) use nearly ϵ-stationary point of 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 2 in [45] ). Given ϵ > 0, we say x is a nearly ϵ-critical point of minx {F (x) := Φ(x) -Ψ(x)} if there exist v, x ′ , x ′′ such that v ∈ ∂Φ(x ′ ) -∂Ψ(x ′′ ) and max{E∥v∥, E∥x -x ′ ∥, E∥x -x ′′ ∥} ≤ ϵ.To tackle the second issue, we take the Moreau envelope of Φ(•) and Ψ(•) individually and define the smooth approximation of F (x) asEQUATIONThe recent work [32] has proven that F γ (x) is indeed smooth.1: Input Initial points: x 0 ϕ , x 0 ψ , x 0 , y 0 , z 0 . Hyper-parameters: γ, η 0 , η 1 .Stochastic (sub)gradients: ∂x ϕ, ∇y ϕ, ∂x ψ, ∇z ψ. 3: for t = 0, . . . , T -1 do 4:x t+1 ϕ = x t ϕ -η 1 ( ∂x ϕ(x t ϕ , y t ) + 1 γ (x t ϕ -x t )) 5:y t+1 = P Y y t + η 1 ∇y ϕ(x t ϕ , y t )6:x t+1 ψ = x t ψ -η 1 ( ∂x ψ(x t ψ , z t ) + 1 γ (x t ψ -x t ))7:z t+1 = P Z z t + η 1 ∇z ψ(x t ψ , z t ) 8: G t+1 = 1 γ (x t -x t+1 ϕ ) -1 γ (x t -x t+1 ψ ) 9:x t+1 = x t -η 0 G t+1 10: end for 11: return x t ϕ or x t ψ with t uniformly sampled from {1, . . . , T }Proposition 3.3 (Proposition EC.1.2 in [32]). Assume Φ(•) and Ψ(•) are δ ϕ , δ ψ -weakly convex respectively. Then F γ (x) = Φ γ (x) -Ψ γ (x) is L F -smooth, where L F = 2 γ-γ 2 min{δ ψ ,δ ϕ } .Moreover, one can show that a good approximate stationary point x of F γ (•) and a good approximation point x ′ to the proximal points prox γΦ (x) and prox γΨ (x) can guarantee that x ′ is a nearly ϵ-critical point of min x F (x).Lemma 3.4 (Lemma 3 in [45] ). Assume Φ(•) and Ψ(•) are δ ϕ , δ ψ -weakly convex respectively, and0 < γ < min{δ -1 ϕ , δ -1 ψ }. If x is a vector such that E[∥∇F γ (x)∥ 2 ] ≤ min{1, γ -2 }ϵ 2 /4, and x ′ is a vector such that E[∥x ′ -prox γΦ (x)∥ 2 ] ≤ ϵ 2 /4 or E[∥x ′ -prox γΨ (x)∥ 2 ] ≤ ϵ 2 /4, then x ′ is a nearly ϵ-critical point of min x F (x). 
algorithms and convergence: 
 Since we aim to minimize the smooth function F γ (x), the natural strategy is to perform gradient descent to update the variable x. Following from the properties of Moreau envelope, the gradient of F γ (x) is given byEQUATIONwhere the blue component is the gradient of Φ γ (x) and the green component is the gradient of Ψ γ (x). However, the proximal points prox γΨ (x) and prox γΦ (x) are not accessible in general. Indeed, these proximal points are the optimal solutions to minx ′ {Φ(x ′ )+ 1 2γ ∥x-x ′ ∥ 2 } and min x ′ {Ψ(x ′ )+ 1 2γ ∥x- x ′ ∥ 2 }respectively, and Φ(•) and Ψ(•) are typically not accessible because they are the value functions of possibly sophisticated maximization problems. Thus, we maintain two variables x t ϕ and x t ψ as the estimators of prox γΦ (x t ) and prox γΨ (x t ) respectively, and maintain another two variables y t and z t as the estimators of arg max y∈Y ϕ(prox γΦ (x t ), y) and arg max z∈Z ψ(prox γΨ (x t ), z) respectively. At each iteration, we update x t ϕ and x t ψ by one step of stochastic gradient descent, and update y t and z t by one step of stochastic gradient ascent. Finally, we compute the gradient estimatorG t+1 = 1 γ (x t -x t+1 ϕ ) -1 γ (x t -x t+1 ψ ) of ∇F γ (x t) and update x t by one step of gradient descent. The resulting algorithm is presented in Algorithm 1.DWC Optimization. For DWC problem (2), the associated functions Φ(•) = ϕ(•) and Ψ(•) = ψ(•) are directly accessible. Thus the variables y t and z t in SMAG are no longer needed. The simplified SMAG algorithm for DWC optimization is presented in Algorithm 2.WCSC Min-Max Optimization. For WCSC Min-Max problem (3), the second component function Ψ = 0 can be ignored, and thus variables x t ψ and z t are no longer needed. However, this brings a change to the gradient of F γ (x t ) as it now becomes∇F γ (x t ) = γ -1 (x t -prox γΦ (x t )).The simplified SMAG algorithm for WCSC Min-Max optimization is presented in Algorithm 3.Algorithm 2 SMAG for DWC Optimization 1: for t = 0, . . . , T -1 do 2:x t+1 ϕ = x t ϕ -η 1 ( ∂x ϕ(x t ϕ )+ 1 γ (x t ϕ -x t ))3:x t+1 ψ = x t ψ -η 1 ( ∂x ψ(x t ψ ) + 1 γ (x t ψ - x t )) 4: G t+1 = 1 γ (x t+1 ψ -x t+1 ϕ )5:x t+1 = x t -η 0 G t+1 6: end for 7: return x t ϕ or x t ψ with t ∼ {1, . . . , T } Algorithm 3 SMAG for WCSC Min-Max Opti- mization 1: for t = 0, . . . , T -1 do 2: x t+1 ϕ = x t ϕ -η 1 ( ∂x ϕ(x t ϕ , y t )+ 1 γ (x t ϕ -x t ))3:y t+1 = P Y y t + η 1 ∇y ϕ(x t ϕ , y t ) 4: G t+1 = 1 γ (x t -x t+1 ϕ )5:x t+1 = x t -η 0 G t+1 6: end for 7: return xt with t ∼ {0, . . . , T -1}In this section, we present convergence results for Algorithms 1-3. To proceed, we make the following assumption for DMax problem (1). Assumption 4.1. Considering DMax problem (1), we assume that(i) ϕ(•, y) is δ ϕ -weakly convex, and ψ(•, z) is δ ψ -weakly convex. (ii) ϕ(x, •) is µ ϕ -strongly concave, and ψ(x, •) is µ ψ -strongly concave.(iii) ϕ(x, y) and ψ(x, z) are differentiable in terms of y and z respectively, ∇ y ϕ(•, y) is L ϕ,yx -Lipschitz continuous, and∇ z ψ(•, z) is L ψ,zx -Lipschitz continuous.(iv) There exists a constantF * γ > -∞ such that F * γ ≤ F γ (x) for all x.(v) There exists a finite constant M such that E∥ ∂x ϕ(x, y)∥ 2 ≤ M 2 , E∥ ∇y ϕ(x, y)∥ 2 ≤ M 2 , E∥ ∂x ψ(x, z)∥ 2 ≤ M 2 , E∥ ∇z ψ(x, z)∥ 2 ≤ M 2 for all x ∈ R dx , y ∈ Y and z ∈ Z.It shall be noted that Assumption 4.1(iii) only requires partial smoothness of ϕ and ψ, and is to ensure the Lipschitz continuity of y * (•) := arg max y∈Y ϕ(•, y) and z * (•) := arg max z∈Z ψ(•, z). This follows from existing results. Lemma 4.2 (Lemma 4.3 in [19] ). Consider problem max y∈ Ŷ f (x, y) for any x ∈ R dx , whereŶ ⊂ R dy is a closed convex set. Assume that f (x, y) is µ-strongly concave in y for each x ∈ R dx ,and∇ y f (•, y) is L yx -Lipschitz for each y ∈ Ŷ. Then arg max y f (•, y) is Lyx µ -Lipschitz continuous.A Lipschitz smooth function f (x, y) is guaranteed to have Lipschitz continuous partial gradient ∇ y f (•, y), while the reverse statement is not necessarily true. For example, consider a functionf (x, y) = y ⊤ h(x) -g(y) with non-smooth C-Lipschitz continuous h(•) and strongly convex g. Then f (x, y) is non-smooth but the partial subgradient ∇ y f (•, y) = h(•) -∇g(y)is Lipschitz continuous with respect to the first argument. Another example is given by f (x, y) = f 1 (x) + f 2 (x, y), where f 1 is weakly convex and f 2 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(iii) by directly assuming that y * (•) and z * (•) are Lipschitz continuous. In addition, Assumption 4.1(v) is standard in non-smooth optimization literature [3, 39, 10] .Here we give a brief outline of the convergence analysis. First of all, we present a standard result [7] .Lemma 4.3. Suppose that F γ (•) is L F -smooth and x t+1 = x t -η 0 G t+1 with 0 < η 0 ≤ 1 2L F . Then we have F γ (x t+1 ) ≤ F γ (x t ) + η 0 2 ∥∇F γ (x t ) -G t+1 ∥ 2 - η 0 2 ∥∇F γ (x t )∥ 2 - η 0 4 ∥G t+1 ∥ 2 .This implies that the key to bounding the gradient ∥∇F γ (x t )∥ 2 is to obtain a recursive bound for the gradient estimation error ∥∇F γ (x t ) -G t+1 ∥ 2 . Following from the true gradient formulation 5, we haveEQUATIONIn other words, the error of the gradient estimation G t+1 can be bounded by the estimation errors of x t+1 ϕ and x t+1 ψ . Thus, we construct recursive bound for the proximal point estimation errors ∥x t+1 ϕprox γΦ (x t )∥ 2 and ∥x t+1 ψprox γΨ (x t )∥ 2 individually. In fact, these two errors share almost identical analysis due to similar assumptions and updates. Here we only present the result for function ϕ, as the result for ψ directly follows.Lemma 4.4. Suppose that Assumption 4.1 holds, 0 < γ < 1/δ ϕ , andη 1 ≤ γ 2 (1/γ-δ ϕ ) 2. Then the sequences {x t }, {y t }, {x t ϕ } and {G t } generated by Algorithm 1 satisfyE∥x t+1 ϕ -prox γΦ (x t )∥ 2 + E t ∥y t+1 -y * (prox γΦ (x t ))∥ 2 ≤ (1 - η 1 (1/γ -δ ϕ ) 2 )E∥x t ϕ -prox γΦ (x t-1 )∥ 2 + (1 -η 1 µ ϕ )E∥y t -y * (prox γΦ (x t-1 ))∥ 2 + 2η 2 0 η 1 γ 2 (1/γ -δ ϕ ) 3 + L 2 ϕ,yx η 2 0 η 1 µ 3 ϕ γ 2 (1/γ -δ ϕ ) 2 E∥G t ∥ 2 + 12M 2 η 2 1 .Finally, combining Lemma 4.3, inequality (6) and Lemma 4.4 yields the following convergence result for Algorithm 1. Theorem 4.5. Suppose that Assumption 4.1 holds, 0< γ < min{δ -1 ϕ , δ -1 ψ }, η 1 = O(ϵ 2 ), and (ii) There exists a constantη 0 = τ η 1 . Then after T ≥ O(ϵ -4 ) iterations, the sequences {x t }, {x t ϕ } and {x t ψ } generated by Algorithm 1 satisfy E[∥x t ϕ -prox γΦ (xt -1 )∥ 2 + ∥x t ψ -prox γΨ (xt -1 )∥ 2 + ∥∇F γ (xt -1 )∥ 2 ] ≤ min{1, γ -2 }ϵ 2 /4,F * γ > -∞ such that F * γ ≤ F γ (x) for all x.(iii) There exists a finite constant M such that E∥ ∂ϕ(x)∥ 2 ≤ M 2 and E∥ ∂ψ(x)∥ 2 ≤ M 2 for all x ∈ R dx .By setting ϕ(x, y) = ϕ(x) and ψ(x, z) = ψ(x), namely independent of y and z, in DMax problem (1), 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< γ < min{δ -1 ϕ , δ -1 ψ }, η 1 = O(ϵ 2 ), and η 0 = τ η 1 . Then after T ≥ O(ϵ -4 ) iterations, the outputs x t ϕ and x t ψ of Algorithm 2 are both nearly ϵ-critical points of problem (2) .For WCSC min-max problem (3), we reduce Assumption 4.1 to the following. Assumption 4.8. Considering WCSC min-max problem (3), we assume that (i) ϕ(•, y) is δ ϕ -weakly convex, and ϕ(x, •) is µ ϕ -strongly concave.(ii) ϕ(x, y) is differentiable in terms of y, and ∇ y ϕ(•, y) is L ϕ,yx -Lipschitz continuous.(iii) There exists a constantF * γ > -∞ such that F * γ ≤ F γ (x) for all x.(iv) There exists a finite constant M such that E∥ ∂x ϕ(x, y)∥ 2 ≤ M 2 and E∥ ∇y ϕ(x, y)∥ 2 ≤ M 2 for all x ∈ R dx and y ∈ Y.By setting ψ(x, z) = 0 in DMax problem (1), we obtain the following convergence result for Algorithm 3, which is an immediate consequence of Theorem 4.5.Corollary 4.9. Suppose that Assumption 4.8 holds, 0 < γ < 1/δ ϕ , η 1 = O(ϵ 2 ), and η 0 = τ η 1 , Then after T ≥ O(ϵ -4 ) iterations, the output xt of Algorithm 3 is a nearly ϵ-stationary point of problem (3).It shall be mentioned that for WCSC min-max problem (3, we use nearly ϵ-stationary point as the convergence metric. This is standard in weakly-convex optimization literature [3] . 
applications: 
 In this section, we introduce two applications of DMax optimization, PU learning for DWC optimization and partial AUC optimization with adversarial fairness regularization for WCSC min-max optimization. We also show experimental results on both applications.In binary classification task, the optimization problem is commonly formulated as the minimization of empirical risk, i.e., min w∈R d 1xi∈S ℓ(w; x i , y i ) where ℓ(w; x i , y i ) is the loss given the model parameter w on a data point x i and its ground truth label y i . Given the scenario where only positive data S + are observed, then the standard approach becomes problematic. One way to address this issue is to utilize unlabeled data S u to construct unbiased risk estimators. To be specific, [13] formulated the PU learning problem as following minEQUATIONwheren + = |S + |, n u = |S u |, π p = P r(y = 1)is the prior probability of the positive class. If ℓ(w; x, y) is weakly convex in terms of w, then Problem ( 7) is a DWC problems. In particular, in our experiments we consider linear classification model and hinge loss.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 or DWC problems with non-smooth components, including SDCA [26] , SSDC-SPG [39] , SSDC-Adagrad [39] and SBCD [45] .Datasets. We use four multi-class classification datasets, Fashion-MNIST [36] , MNIST [5] CI-FAR10 [14] and FER2013 [6] . To fit them in binary classification task, we consider the first five classes as negative for Fashion-MNIST, MNIST and CIFAR10, and the first four classes as negative for FER2013. For Fashion-MNIST, MNIST, CIFAR10, we follow the standard train-test split. For FER2013, we take the first 25709 samples as the training data, and the rest as for testing.Setup. For all datasets, we use a batch size of 64 and set π p = 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.e., µη t /(µ + η t )), and η 1 in SMAG are all tuned from {10, 1, 0.2, 0.1, 0.01, 0.001}. The learning rate of the outer loop in SDCA and η 0 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/γ 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 1 . For all tested datasets, the performance of SMAG surpasses the baselines. Among the baselines, SBDC is the generally the next best choice. However, since SBDC is a double-loop method, it has one more hyperparameter compared to SMAG.We also present the ablation study of SMAG regarding the parameter γ in Figure 2 included in the Appendix. [44, 46, 20, 9] and has shown great success in large-scale real-world tasks, e.g., medical image classification [46] and molecular properties prediction [35] . One-way partial AUC (OPAUC) is an extension of AUC that has a primary interest in the curve corresponding to low FPR. To be specific, OPAUC restrict the FPR to the region [0, ρ] where ρ ∈ (0, 1). A recent work [52] proposed to formulate OPAUC problem into a non-smooth weakly convex optimization problem using conditional-value-at-risk (CVaR) based distributionally robust optimization (DRO). The formulation is given byEQUATIONwhere S + , S -are the sets of positive and negative samples respectively, n + = |S + |, n -= |S -|, and w denotes the weights of encoder network and classification layer. The pairwise surrogate loss is defined by L(w; x i , x j ) = ℓ(h(w, x i ) -h(w, x j )) and we use squared hinge loss as the surrogate loss, i.e., ℓ(•) = (c -•) 2 , where c > 0 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: where σ(w, w a , x) denotes a predicted probability that the data has a sensitive attribute a = 1 by using a classification head w a on 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 a fairness regularization:EQUATIONIt 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 on OPAUC problem with adversarial fairness regularization (9) are SGDA [19] and Epoch-GDA [40] .Dataset. CelebA contains 200k celebrity face images with 40 binary attributes each, including the gender-sensitive attribute denoted as Male. In our experiments, we conduct experiments on three independent attribute prediction tasks: Attractive, 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%/10% split.Setup. For all experiments, we adopt ResNet-18 as our backbone model architecture and initialize it with ImageNet pre-trained weights. The batch size is 128. We set the FPR upper bound to be ρ = 0.3. We train the model for 3 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. α = 0 for SOPA and SMAG * . The initial learning rates for optimizing w are tuned in 0.1, 0.01, 0.001 for all methods, while the weight interpolation parameters, i.e., γ 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. η 1 in SMAG are tuned from {10, 1, 0.2, 0.1, 0.01, 0.001}.Results. We report the experimental results on three fairness metrics [27] , equalized odds difference (EOD), equalized opportunity (EOP), and demographic disparity (DP) in Table 3 . We observe that SMAG consistently achieves the highest pAUC score and lowest disparities metrics across all tasks compared to all other baseline min-max methods. Question: Does the paper provide open access to the data and code, with sufficient instructions 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. Justification: The research conducted in the paper conform, in every respect, with the NeurIPS 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 a single-loop stochastic method for solving DMax optimization and presented a novel convergence analysis showing that the proposed method achieves a non-asymptotic convergence rate of O(ϵ -4 ). 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 ψ(x, •). This strong assumption may limit the applicability of our method. Future work will focus on exploring DMax optimization with weaker assumptions. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? 
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 (e.g., pre-trained language models, image generators, or scraped datasets)?Answer:[NA]Answer: [NA] Justification: The paper does not involve crowdsourcing nor research with human subjects. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS 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. 
 
 Appendix: Recall that Φ(x) := max y∈Y ϕ(x, y), Ψ(x) := max z∈Z ψ(x, z), y * (•) := arg max y∈Y ϕ(•, y), and z * (•) := arg max z∈Z ψ(•, z). Before presenting the proof of Theorem 4.5, we first give the proof of the proximal point estimation error bounds. As we have stated the bound for ∥x t+1 ϕ prox γΦ (x t )∥ 2 in Lemma 4.4, here we present the corresponding lemma for ∥x t+1 ψ prox γΨ (x t )∥ 2 .Lemma A.1. Suppose that Assumption 4.1 holds, 0 < γ < 1/δ ψ , andη 1 ≤ γ 2 (1/γ-δ ψ ) 2. Then the sequences {x t }, {z t }, {x t ψ } and {G t } generated by Algorithm 1 satisfy E∥x t+1 ψ -prox γΨ (x t )∥ 2 + E∥z t+1 -z * (prox γΨ (x t ))∥ 2 ≤ (1 - η 1 (1/γ -δ ψ ) 2 )E∥x t ψ -prox γΨ (x t-1 )∥ 2 + (1 -η 1 µ ψ )E∥z t -z * (prox γΨ (x t-1 ))∥ 2 + 2η 2 0 η 1 γ 2 (1/γ -δ ψ ) 3 + L 2 ψ,zx η 2 0 η 1 µ 3 ψ γ 2 (1/γ -δ ψ ) 2 E∥G t ∥ 2 + 12M(•)) is L ϕ,yx /(µ ϕ (1 -γδ ϕ ))-Lipschitz continuous.For notational convenience, we letΦ t (x, y) = ϕ(x, y) + 1 2γ ∥x -x t ∥ 2 ,x * Φ,t = prox γΦ (x t ), y * t = y * (prox γΦ (x t )).In view of (10) and the update rule of x t+1 ϕ , one hasEQUATIONwhere we use the inequalityE t ∥ ∂x Φ t (x t ϕ , y t )∥ 2 = E t ∥ ∂x ϕ(x t ψ , y t ) + 1 γ (x t ϕ -x t )∥ 2 = E t ∥ ∂x ϕ(x t ϕ , y t ) + 1 γ (x t ϕ -x t ) -∂ x ϕ(x * Φ,t , y * t ) - 1 γ (x * Φ,t -x t )∥ 2 ≤ 4E t ∥ ∂ϕ(x t ϕ , y t )∥ 2 + 4∥∂ x ϕ(x * Φ,t , y * t )∥ 2 + 2 γ 2 ∥x t ϕ -x * Φ,t ∥ 2 ≤ 8M 2 + 2 γ 2 ∥x t ϕ -x * Φ,t ∥ 2 .By (γ -1 -δ ϕ )-strong convexity of Φ t (•, y) and the definition of x * Φ,t in (10) , one has⟨∂ x Φ t (x t ϕ , y t ), x * Φ,t -x t ϕ ⟩ ≤ Φ t (x * Φ,t , y t ) -Φ t (x t ϕ , y t ) - (1/γ -δ ϕ ) 2 ∥x * Φ,t -x t ϕ ∥ 2 , 0 ≤ Φ t (x t ϕ , y * t ) -Φ t (x * Φ,t , y * t ) - (1/γ -δ ϕ ) 2 ∥x * Φ,t -x t ϕ ∥ 2 .Summing up these two inequalities gives(A) ≤ Φ t (x * Φ,t , y t ) -Φ t (x t ϕ , y t ) + Φ t (x t ϕ , y * t ) -Φ t (x * Φ,t , y * t ) -(1/γ -δ ϕ )∥x * Φ,t -x t ϕ ∥ 2 . (12)Notice from the definition of y * t in ( 10) that there exists a particular subgradient ∇ y ϕ(x * Φ,t , y * t ) such that y * t = P Y y * t + η 1 ∇ y ϕ(x * Φ,t , y * t ) . Using this and the update rule of y t+1 , we haveEQUATION)By µ ϕ -strong concavity of Φ t (x, •), we haveEQUATIONCombining ( 12) and ( 14) yields(A) + (B) ≤ -(1/γ -δ ϕ )∥x * Φ,t -x t ϕ ∥ 2 -µ ϕ ∥y * t -y t ∥ 2 .Using this inequality, ( 11) and ( 13), we haveE t ∥x t+1 ϕ -x * Φ,t ∥ 2 + E t ∥y t+1 -y * t ∥ 2 ≤ (1 -2η 1 (1/γ -δ ϕ ) + 2η 2 1 /γ 2 )∥x * Φ,t -x t ϕ ∥ 2 + (1 -2η 1 µ ϕ )∥y * t -y t ∥ 2 + 12M 2 η 2 1 (a) ≤ (1 -η 1 (1/γ -δ ϕ ))∥x * Φ,t -x t ϕ ∥ 2 + (1 -2η 1 µ ϕ )∥y * t -y t ∥ 2 + 12M 2 η 2 1 (b) ≤ (1 -η 1 (1/γ -δ ϕ )) 1 + η 1 (1/γ -δ ϕ ) 2 ∥x t ϕ -x * Φ,t-1 ∥ 2 + 1 + 2 η 1 (1/γ -δ ϕ ) ∥x * Φ,t-1 -x * Φ,t ∥ 2 + (1 -2η 1 µ ϕ ) (1 + η 1 µ ϕ )∥y t -y * t-1 ∥ 2 + 1 + (η 1 µ ϕ ) -1 ∥y * t-1 -y * t ∥ 2 + 12M 2 η 2 1 (c) ≤ 1 - η 1 (1/γ -δ ϕ ) 2 ∥x t ϕ -x * Φ,t-1 ∥ 2 + 2 η 1 (1/γ -δ ϕ ) ∥x * Φ,t-1 -x * Φ,t ∥ 2 + (1 -η 1 µ ϕ )∥y t -y * t-1 ∥ 2 + (η 1 µ ϕ ) -1 ∥y * t-1 -y * t ∥ 2 + 12M 2 η 2 1 (d) ≤ 1 - η 1 (1/γ -δ ϕ ) 2 ∥x t ϕ -x * Φ,t-1 ∥ 2 + (1 -η 1 µ ϕ )∥y t -y * t-1 ∥ 2 + 2η 2 0 η 1 γ 2 (1/γ -δ ϕ ) 3 + L 2 ϕ,yx η 2 0 η 1 µ 3 ϕ γ 2 (1/γ -δ ϕ ) 2 ∥G t ∥ 2 + 12M 2 η 2 1 ,where (a) follows from the assumptionη 1 ≤ γ 2 (1/γ-δ ϕ ) 2, (b) uses the fact that ∥a + b∥ 2 ≤ (1 + α)∥a∥ 2 + (1 + 1 α )∥b∥ 2 for any α > 0, (c) follows from bounding the coefficient of each term from above, and (d) uses 1/(1 -γδ ϕ )-Lipschitz continuity of prox γΦ (•), L ϕ,yx /(µ ϕ (1 -γδ ϕ ))-Lipschitz continuity of y * (prox γΦ (•)) and the update rule of x t .Finally taking expectation over all randomness yields the desired result.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 γ, η 0 and η 1 in Algorithm 1 are chosen as follows:0 < γ < min{δ -1 ϕ , δ -1 ψ }, α = min 1/γ -δ ϕ 4 , 1/γ -δ ψ 4 , µ ϕ , µ ψ , τ = min γ 2 α 2 4 , µ 1.5 ϕ γ 2 α 1.5 4L ϕ,yx , µ 1.5 ψ γ 2 α 1.5 4L ψ,zx , ν = min 1, 2τ γ 2 α , L F = 2 γ -γ 2 min{δ ψ , δ ϕ } , η 1 = min γ 2 (1/γ -δ ϕ ) 2 , γ 2 (1/γ -δ ψ ) 2 , 1 2L F τ , min{1, γ 2 } min {α, τ } να 768τ M 2 ϵ 2 , η 0 = τ η 1 .Then we have1 T T -1 t=0 (E∥x t+1 ϕ -prox γΦ (x t )∥ 2 + E∥x t+1 ψ -prox γΨ (x t )∥ 2 + E∥∇F γ (x t )∥ 2 ) ≤ min{1, γ -2 } ϵ 2 4 ,and consequently x t ϕ and x t ψ are both nearly ϵ-critical points of problem (1), wheneverEQUATIONP 0 = 2η 0 η 1 γ 2 α E∥x 1 ϕ -prox γΦ (x 0 )∥ 2 + E∥y 1 -y * 0 ∥ 2 + E∥x 1 ψ -prox γΨ (x 0 )∥ 2 + E∥z 1 -z * 0 ∥ 2 .Proof. For notational convenience, letEQUATIONFrom Proposition 3.3, we know that F γ (•) is L F -smooth. By this, 0 < η 0 ≤ 1 2L F , and Lemma 4.3, one hasEQUATION)Notice that∇F γ (x t ) = γ -1 (prox γΨ (x t ) -x t + x t -prox γΦ (x t )) = γ -1 (prox γΨ (x t ) -prox γΦ (x t )), G t+1 = γ -1 (x t+1 ψ -x t+1 ϕ ). Using these, (10) and ( 16), we haveEQUATIONIt follows from this and ( 17) thatEQUATIONLet x * Φ,t and y * t be defined in (10) . Invoking Lemma 4.4, we haveE∥x t+2 ϕ -x * Φ,t+1 ∥ 2 + E∥y t+2 -y * t+1 ∥ 2 ≤ 1 - η 1 (1/γ -δ ϕ ) 2 E∥x t+1 ϕ -x * Φ,t ∥ 2 + (1 -η 1 µ ϕ )E∥y t+1 -y * t ∥ 2 + 2η 2 0 η 1 γ 2 (1/γ -δ ϕ ) 3 + L 2 ϕ,yx η 2 0 η 1 µ 3 ϕ γ 2 (1/γ -δ ϕ ) 2 E∥G t+1 ∥ 2 + 12M 2 η 2 1 .Recall that x * Ψ,t and z * t are defined in (16) . By Lemma A.1, one hasE∥x t+2 ψ -x * Ψ,t+1 ∥ 2 + E∥z t+2 -z * t+1 ∥ 2 ≤ 1 - η 1 (1/γ -δ ψ ) 2 E∥x t+1 ψ -x * Ψ,t ∥ 2 + (1 -η 1 µ ψ )E∥z t+1 -z * t ∥ 2 + 2η 2 0 η 1 γ 2 (1/γ -δ ψ ) 3 + L 2 ψ,zx η 2 0 η 1 µ 3 ψ γ 2 (1/γ -δ ψ ) 2 E∥G t+1 ∥ 2 + 12M 2 η 2 1 .Let α be given in the statement of this theorem. Using this and the last two inequalities above, we haveEQUATIONEQUATIONSumming up inequalities ( 19), (20EQUATIONWe now introduce a potential functionEQUATIONand rewrite inequality (22) asE[F γ (x t+1 )] + P t+1 ≤ E[F γ (x t )] + (1 -β)P t -βE∥∇F γ (x t )∥ 2 + 48η 0 η 1 M 2 γ 2 α + η 3 0 η 2 1 γ 4 α 4 + L 2 ϕ,yx η 3 0 η 2 1 µ 3 ϕ γ 4 α 3 + L 2 ψ,zx η 3 0 η 2 1 µ 3 ψ γ 4 α 3 - η 0 4 E∥G t+1 ∥ 2 ,whereEQUATIONThis inequality, together with the choice of η 0 and τ specified in this theorm, yieldsE[F γ (x t+1 )] + P t+1 ≤ E[F γ (x t )] + (1 -β)P t -βE∥∇F γ (x t )∥ 2 + 48η 0 η 1 M 2 γ 2 α .Taking average of these inequalities over t = 0, . . . , T -1 yieldsEQUATIONEQUATIONwhere we use F * γ ≤ F γ (x T ) due to Assumption 4.1(iii). Recall that η 0 = τ η 1 and ν = min{1, 2τ γ 2 α }. Using these, ( 23) and ( 25), we haveEQUATION(P t + E∥∇F γ (x t )∥ 2 ) ≤ F γ (x 0 ) -F * γ + P 0 νβT + 48η 0 η 1 M 2 νβγ 2 α .By (24) and the choice of α, η 0 and η 1 specified in this theorem, one hasmin{1, γ -2 }νβγ 2 αϵ 2 384η 0 M 2 = min{1, γ 2 } min η1α 2 , η1τ 2 ναϵ 2 384η 1 τ M 2 = min{1, γ 2 } min {α, τ } να 768τ M 2 ϵ 2 ≥ η 1 , which implies that 48η 0 η 1 M 2 νβγ 2 α ≤ min{1, γ -2 } ϵ 2 8 .Suppose that T satisfies (15) . It then follows from (24) , η 0 = τ η 1 , and the expression of η 1 thatT ≥ 16(F γ (x 0 ) -F * γ + P 0 ) min{1, γ -2 } min{α, τ }νϵ 2 max 2 γ 2 (1/γ -δ ϕ ) , 2 γ 2 (1/γ -δ ψ ) , 2L F τ, 768τ M 2 min{1, γ 2 } min {α, τ } ναϵ 2 = 8(F γ (x 0 ) -F * γ + P 0 ) min{1, γ -2 }νβϵ 2 , which implies that F γ (x 0 ) -F * γ + P 0 νβT ≤ min{1, γ -2 } ϵ 2 8 .Hence, for any T satisfying (15) , one has1 T T -1 t=0 (E∥x t+1 ϕ -x * Φ,t ∥ 2 + E∥x t+1 ψ -x * Ψ,t ∥ 2 + E∥∇F γ (x t )∥ 2 ) ≤ min{1, γ -2 } ϵ 2 4 ,which together with x * Φ,t = prox γΦ (x t ) and x * Ψ,t = prox γΨ (x t ) yields1 T T -1 t=0 (E∥x t+1 ϕ -prox γΦ (x t )∥ 2 + E∥x t+1 ψ -prox γΨ (x t )∥ 2 + E∥∇F γ (x t )∥ 2 ) ≤ min{1, γ -2 } ϵ 2 4 .Since t is uniformly sampled from {1, . . . , T }, we haveE[∥x t ϕ -prox γΦ (xt -1 )∥ 2 + ∥x t ψ -prox γΨ (xt -1 )∥ 2 + ∥∇F γ (xt -1 )∥ 2 ] ≤ min{1, γ -2 } ϵ 2 4 .It then follows from Lemma 3.4 that x t ϕ and x t ψ are both nearly ϵ-critical points of problem (1) . • 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 a 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 to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe 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.Justification: There is no 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 no 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 as 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

2. 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?

3. (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. 

I 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.
questions: questions: See weaknesses.
limitations: limitations: See weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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".

2. (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.
questions: questions: 1. Are the proof ideas useful to give single loop algorithms for non-smooth convex minimization via Moreau smoothing, with optimal rates?

2. Optimality: Is the $\epsilon^{-4}$ rate achieved optimal in these settings?
limitations: limitations: N/A
paper_summary: paper_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.
This paper achieves the best complexity of order $O(\epsilon^{-4})$.
Futhermore, the agorithm of this paper only use a single loop which is easy to implement and tune the hyperparameters. 

A typo: Line 3, it should be $\Psi(x) = \max_z \psi(x, z)$.
strength_weakness: strength_weakness: No
questions: 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.
As 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.
So, I wonder whether the results of this paper is useful enough.
limitations: limitations: No
paper_summary: paper_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.

Using 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.

Experimental 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.
strength_weakness: strength_weakness: **Problem Statement and Novelty:**
The 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.

**Complexity Analysis:**
Upon 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.

**Algorithmic Technique:**
The 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.

I welcome further discussion on these points to ensure a comprehensive evaluation. Thanks!
questions: 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.
Regarding 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: limitations: The paper is theoretical, and I believe there is no need to confirm societal impact.

Comments: comment: Thank you for acknowledging our responses and the positive feedback.
Thank you for acknowledging our responses. We are glad to hear that it addresses your concerns.
Thanks for your response! I have no additional problems. I will keep my score, which is on the positive side. I am willing to support the acceptance of the paper.
Thank you for the clear response. I have slightly increased my score, particularly for the clarification of the main difference between the analysis of SMAG and SBCD, which serves as the new proof technique.