Efficient Mirror Descent Ascent Methods for Nonsmooth Minimax Problems
Year: 2022

Abstract:
In the paper, we propose a class of efficient mirror descent ascent methods to solve the nonsmooth nonconvex-strongly-concave minimax problems by using dynamic mirror functions, and introduce a convergence analysis framework to conduct rigorous theoretical analysis for our mirror descent ascent methods. For our stochastic algorithms, we first prove that the mini-batch stochastic mirror descent ascent (SMDA) method obtains a gradient complexity of O(κ −4) for finding an -stationary point, where κ denotes the condition number. Further, we propose an accelerated stochastic mirror descent ascent (VR-SMDA) method based on the variance reduced technique. We prove that our VR-SMDA method achieves a lower gradient complexity of O(κ −3). For our deterministic algorithm, we prove that our deterministic mirror descent ascent (MDA) achieves a lower gradient complexity of O( √ κ −2) under mild conditions, which matches the best known complexity in solving smooth nonconvex-strongly-concave minimax optimization. We conduct the experiments on fair classifier and robust neural network training tasks to demonstrate the efficiency of our new algorithms.

text: √ κ −2) under mild conditions, which matches the best known
complexity in solving smooth nonconvex-strongly-concave minimax optimization. We conduct the experiments on fair classifier and robust neural network training tasks to demonstrate the efficiency of our new algorithms.

heading: 1 Introduction
text: Minimax optimization recently has attracted increased interest largely due to advance in many machine learning applications such as generative adversarial networks (GANs) [14, 41], robust neural networks training [32], fair learning [31], federated learning [10], and policy evaluation [43]. In the paper, we study the following nonsmooth nonconvex-strongly-concave minimax problem:
min x∈X max y∈Y
F (x, y) = { f(x, y) + g(x)− h(y) } , (1)
where the function f(x, y) : X ×Y → R is smooth and possibly nonconvex in x ∈ X and µ-strongly concave in y ∈ Y , and the functions g(x) and h(y) are convex and possibly nonsmooth. Here X ⊆ Rd and Y ⊆ Rp are compact and convex constraint sets, or X = Rd and Y = Rp. In many machine learning problems, f(x, y) generally represents loss function and is a stochastic form, i.e., f(x, y) = Eξ[f(x, y; ξ)], where the random variable ξ follows an unknown data distribution. Here both g(x) and h(y) frequently denote the nonsmooth regularization terms such as g(x) = ν1‖x‖1 and h(y) = ν2‖y‖1 with ν1, ν2 > 0. In fact, the above problem (1) comes from many machine learning problems, such as fair classifier, robust training, nonlinear temporal-difference learning in reinforcement learning [43] and robust federated learning [10].
When g(x) = 0 and h(y) = 0 in the problem (1), the classic gradient descent ascent (GDA) methods [40, 27] can effectively solve this problem, which alternatively conducts a gradient descent update on the variable x and a gradient ascent update on the variable y at each iteration. At the same time, some stochastic GDA methods [40, 27, 30, 18, 46, 17] have been proposed to solve the stochastic minimax problem (1), where f(x, y) = Eξ[f(x, y; ξ)]. More recently, some works [2, 4, 8] focus on more general minimax problem (1), where both g(x) and h(y) are possibly nonsmooth. Meanwhile,
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
some (stochastic) proximal gradient descent ascent (PGDA) methods [2, 4, 8] have been presented to solve the problem (1). However, they still suffer from the large sample complexities for finding an stationary point of the minimax problem (1) without some specific strong assumptions such as KL geometry (Please see Table 1).
In this paper, thus, we propose a class of efficient mirror descent ascent methods by using dynamic mirror function (i.e., Bregman function). Specifically, our methods perform an adaptive mirror descent update to variable x and an adaptive mirror ascent update to variable y alternatively at each iteration. Our new algorithmic framework can generate many popular methods and their variants by adopting different mirror functions. For example, by adopting the mirror functions ψ(x) = 12‖x‖
2 and φ(y) = 12‖y‖
2, our methods will include the classic (proximal) gradient descent ascent algorithms. Our main contributions are summarized as follows:
1) We propose a class of novel mirror descent ascent methods to solve the minimax problem (1) by using dynamic mirror functions. Moreover, we provide a convergence analysis framework for our mirror descent ascent methods.
2) We present a faster deterministic adaptive mirror descent ascent (MDA) method, which reaches a lower gradient complexity of O( √ κ −2) than the existing nonsmooth nonconvex minimax
methods. Meanwhile, we propose a fast stochastic mirror descent ascent (SMDA) method, which requires O(κ3 −4) stochastic gradient evaluations to obtain an -stationary point of the problem (1).
3) We further propose an accelerated stochastic mirror descent ascent (VR-SMDA) method by using the variance reduced technique of SARAH/SNVRG/SPIDER [37, 51, 12, 44]. Moreover, we prove that our VR-SMDA reaches a lower gradient complexity of O(κ3 −3).
In fact, when our methods solve the minimax problem (1) without nonsmooth regularization terms, i.e., g(x) = 0 and h(y) = 0, our theoretical results also can apply these minimax problems without nonsmooth regularization terms studied in [27, 28].

heading: 2 Related Works
text: In this section, we review some existing typical minimax optimization methods and stochastic mirror descent methods, respectively.

heading: 2.1 Minimax Optimization Methods
text: Minimax optimization recently has been widely studied in machine learning community. The convergence properties of (strongly) convex-(strongly) concave minimax optimization have been studied in [42, 26, 35, 49]. Due to the popularity of nonconvex models in machine learning, many recent studies focused on the nonconvex minimax problems such as robustly deep neural networks training and GANs. For example, some effective gradient descent ascent (GDA) methods [40, 38, 27, 28, 46, 47, 17, 18, 19, 16] have been proposed for the nonconvex-(strongly) concave minimax optimization. Specifically, Lin et al. [27] studied the convergence properties of both deterministic and stochastic GDA methods. Subsequently, Luo et al. [30] proposed a class of faster stochastic GDA methods based on variance reduced technique of SPIDER [12]. Huang et al. [18] proposed
an accelerated single-loop stochastic GDA method based on momentum-based variance reduced technique of STORM [9]. Recently, the nonconvex-nonconcave minimax optimization problems with some specific structures also have been studied in [34, 48, 11, 33]. Specifically, Yang et al. [48] and Diakonikolas et al. [11] have studied a class of specific nonconvex-nonconcave minimax problems satisfying a so-called two-sided Polyak-Lojasiewicz inequality and stampacchia variational inequality, respectively. More recently, Zhang et al. [50] and Li et al. [24] studied the lower bound of sample complexity for nonconvex-strongly-concave minimax optimization. Xian et al. [45] studied the decentralized nonconvex-strongly-concave minimax optimization. Meanwhile, some research works [29, 2, 4, 8] began to study the nonsmooth nonconvex minimax problem (1).

heading: 2.2 Mirror Descent Methods
text: Mirror descent (a.k.a., Bregman gradient) method [7, 3] is a powerful optimization tool in machine learning, since it can fit the geometry of optimization problems by choosing proper Bregman functions [5, 6]. The mirror descent methods for convex optimization have been studied in [7, 3]. Subsequently, Lei et al. [23] integrated the variance reduced technique to the mirror descent algorithm for stochastic convex optimization. More recently, a variance-reduced adaptive stochastic mirror descent algorithm [25] has been proposed to solve the nonsmooth nonconvex finite-sum mini optimization. Recently, the mirror descent method also has been used to solve minimax optimization problems. For example, Babanezhad et al. [1] presented a mirror-type algorithm for convex minimax optimization. Rafique et al. [40] proposed a class of mirror descent methods for weakly convex minimax optimization. Meanwhile, a new mirror descent-type method [34] has been proposed to solve a class of nonconvexnonconcave minimax problems with a non-monotone variational inequality structure. To the best of our knowledge, recently few work focuses on explicitly using the mirror-decent-type method to solve the nonsmooth nonconvex minimax problems.

heading: 3 Preliminaries

heading: 3.1 Notations
text: For two vectors x and y, 〈x, y〉 denotes their inner product. ‖ · ‖ denotes the `2 norm for vectors and spectral norm for matrices, respectively. ∇xf(x, y) and ∇yf(x, y) denote the partial derivatives w.r.t. variables x and y respectively, and let ∇f(x, y) = ( ∇xf(x, y),∇yf(x, y) ) . ∂g(x) denotes the subgradient set of function g(x). Given a convex closed set X , we define a projection operation ProjX (α) = arg minx∈X ‖x− α‖2. Given the mini-batch samples B = {ξi}bi=1, we let∇fB(x) = 1 b ∑b i=1∇f(x; ξi). Define an increasing σ-algebras Ft := {B1,B2, · · · ,Bt−1} for all t ≥ 2, then let E[·] = E[·|Ft].

heading: 3.2 Standard Mirror Descent Method
text: Given a ρ-strongly convex and continuously-differentiable function ψ(x), i.e., 〈x1 − x2,∇ψ(x1)− ∇ψ(x2)〉 ≥ ρ‖x1−x2‖2, we define a Bregman divergence (i.e., Bregman distance) for any x, z ∈ X :
Dψ(z, x) = ψ(z)− ψ(x)− 〈∇ψ(x), z − x〉. (2)
To solve the problem minx∈X f(x), the mirror descent method [7, 3] uses the following form to update the variable x, for all t ≥ 1
xt+1 = arg min x∈X
{ f(xt) + 〈∇f(xt), x− xt〉+ 1
α Dψ(x, xt)
} , (3)
where α > 0 is stepsize. In the above subproblem (3), the first two terms of its objective function is a linear function approximated the function f(x), and the last term is a Bregman distance between x and xt. Note that the constant terms f(xt) and 〈∇f(xt), xt〉 can be omitted in the above subproblem (3). When choosing ψ(x) = 12‖x‖ 2, we have Dψ(x, xt) = 12‖x − xt‖ 2. Then the mirror descent method will reduce to the standard projected gradient descent method.

heading: 3.3 Some Mild Assumptions
text: In the subsection, we introduce some mild assumptions for the problem (1).
Assumption 1. (Smoothness) For the deterministic and mini-batch stochastic algorithms (MDA and SMDA), we assume that the function f(x, y) has an Lf -Lipschitz gradient, i.e., for all x1, x2 ∈ X and y1, y2 ∈ Y , we have
‖∇f(x1, y1)−∇f(x2, y2)‖ ≤ Lf‖(x1, y1)− (x2, y2)‖. (4)
For our variance-reduced stochastic algorithm (VR-SMDA), we assume that each component function f(x, y; ξ) has an Lf -Lipschitz gradient, i.e., for all x1, x2 ∈ X and y1, y2 ∈ Y , we have
‖∇f(x1, y1; ξ)−∇f(x2, y2; ξ)‖ ≤ Lf‖(x1, y1)− (x2, y2)‖, ∀ξ. (5)
In Assumption 1, the inequality (4) is commonly used in the minimax optimization [27, 2, 4, 8]. While the inequality (5) is frequently used in the variance-reduced stochastic optimization [30, 18]. Assumption 2. Each component function f(x, y; ξ) has an unbiased stochastic gradient with bounded variance σ2, i.e.,
E[∇f(x, y; ξ)] = ∇f(x, y), E‖∇f(x, y; ξ)−∇f(x, y)‖2 ≤ σ2. (6)
Assumption 3. The function f(x, y) is µ-strongly concave w.r.t y, i.e., for all x ∈ X and y1, y2 ∈ Y , we have ‖∇yf(x, y1)−∇yf(x, y2)‖ ≥ µ‖y1 − y2‖. Then the following inequality holds
f(x, y1) ≤ f(x, y2) + 〈∇yf(x, y2), y1 − y2〉 − µ
2 ‖y1 − y2‖2. (7)
Assumption 4. The functions g(x) and h(y) are convex but possibly nonsmooth.
Assumption 3 shows that the function f(x, y) is µ-strongly concave w.r.t y. Assumption 4 shows that the function h(y) is convex. Thus, the function {f(x, y)− h(y)} is strongly concave in y ∈ Y , there exists a unique solution to the problem maxy∈Y{f(x, y) − h(y)} for any x. Let y∗(x) = arg maxy∈Y{f(x, y)− h(y)}, and Φ(x) = f(x, y∗(x))− h(y∗(x)) = maxy∈Y{f(x, y)− h(y)}. Assumption 5. For any α ∈ R, the sub-level set {x : Φ(x) + g(x) ≤ α} is compact. The function Φ(x) + g(x) is bounded below in X , i.e., F ∗ = infx∈X {Φ(x) + g(x)} > −∞.
Assumption 5 is frequently used in nonsmooth minimax optimization [8]. In fact, when h(y) = c where c is a constant, we can only assume the function Φ(x) + g(x) is bounded below in X instead of Assumption 5.

heading: 4 Mirror Descent Ascent Methods
text: In the section, we propose a class of novel mirror descent ascent methods to solve the problem (1). Specifically, we first propose a deterministic mirror descent ascent (MDA) method, and stochastic mirror descent ascent (SMDA) method. Then we further present an accelerated stochastic mirror descent ascent (VR-SMDA) using variance reduced technique of SPIDER [12, 44].

heading: 4.1 MDA and SMDA algorithms
text: When f(x, y) is a deterministic function, we propose a deterministic mirror descent ascent (MDA) method to solve the deterministic problem (1). When f(x, y) = Eξ[f(x, y; ξ)] is a stochastic function, we propose a stochastic mirror descent ascent (SMDA) to solve the stochastic problem (1). Specifically, Algorithm 1 shows the algorithmic framework of the MDA and SMDA algorithms.
In Algorithm 1, we use (stochastic) mirror decent to update variable x, and simultaneously use (stochastic) mirror ascent to update variable y. Specifically, at step 7 of Algorithm 1, we use the mirror descent to update x,
xt+1 = arg min x∈X
{ 〈vt, x〉+ 1
γt Dψt(x, xt) + g(x)
} (8)
= arg min x∈X
{ f(xt, yt) + 〈vt, x− xt〉+ 1
γt Dψt(x, xt) + g(x)
} . (9)
In fact, we omit the constant terms f(xt, yt) and 〈vt, xt〉 in the above subproblem (8). In the above subproblem (9), the first two terms of its objective function is a linear function approximated the function f(x, y) based on (stochastic) derivative estimator vt, and the third term is a Bregman distance between x and xt based on Bregman function ψt. Since the function g(x) is possibly nonsmooth, we
Algorithm 1 (Stochastic) Mirror Descent Ascent Algorithm
1: Input: T , stepsizes {γt > 0, λt > 0, ηt ∈ (0, 1]}Tt=1, mini-batch size b ; 2: initialize: x1 ∈ X and y1 ∈ Y; 3: for t = 1, 2, . . . , T do 4: MDA: Compute partial derivatives vt = ∇xf(xt, yt) and wt = ∇yf(xt, yt); 5: SMDA: Generate randomly mini-batch samples Bt = {ξit}bi=1 with |Bt| = b, and compute stochastic partial derivatives vt = ∇xfBt(xt, yt) and wt = ∇yfBt(xt, yt); 6: Given the mirror functions ψt and φt; 7: xt+1 = arg minx∈X { 〈vt, x〉+ 1γtDψt(x, xt) + g(x) } ;
8: yt+1 = yt + ηt(ỹt+1 − yt) where ỹt+1 = arg maxy∈Y { 〈wt, y〉 − 1λtDφt(y, yt)− h(y) } ;
9: end for 10: Output: xζ and yζ chosen uniformly random from {xt, yt}Tt=1. 11: Output: (for theoretical) xζ and yζ chosen uniformly random from {xt, yt}Tt=1. 12: Output: (for practical) xT and yT .
keep it in the above subproblem (9) as the standard proximal descent algorithm [39]. Similarly, at step 8 of Algorithm 1, we use the mirror ascent to update y,
ỹt+1 = arg max y∈Y
{ 〈wt, y〉 − 1
λt Dφt(y, yt)− h(y)
} (10)
= arg max y∈Y
{ f(xt, yt) + 〈wt, y − yt〉 − 1
λt Dφt(y, yt)− h(y)
} . (11)
In the above subproblem (11), the first two terms of its objective function is a linear function approximated the function f(x, y) based on (stochastic) derivative estimator wt, and the third term is a Bregman distance between y and yt based on Bregman function φt. Moreover, at the step 8 of Algorithm 1, we further use a momentum iteration to update y.
When Bregman functions ψt(x) = 12‖x‖ 2 and φt(y) = 12‖y‖ 2 for all t ≥ 1, we have Dψt(x, xt) = 1 2‖x − xt‖ 2 and Dφt(y, yt) = 1 2‖y − yt‖
2. Under this case, Algorithm 1 will reduce the standard (stochastic) proximal gradient descent ascent algorithm. When Bregman functions ψt(x) = 12x THtx and φt(y) = 12y TGty for all t ≥ 1, we have Dψt(x, xt) = 12 (x−xt)
THt(x−xt) and Dφt(y, yt) = 1 2 (y − yt)
TGt(y − yt), where Ht ρId and Gt ρIp. For example, given α ∈ (0, 1) and ρ > 0, we can generate the matrices Ht and Gt like as in Adam-type algorithms [21, 20], defined as
ṽ0 = 0, ṽt = αṽt−1 + (1− α)∇xf(xt, yt; ξt)2, Ht = diag( √ ṽt + ρ), t ≥ 1 (12)
w̃0 = 0, w̃t = αw̃t−1 + (1− α)∇yf(xt, yt; ξt)2, Gt = diag( √ w̃t + ρ), t ≥ 1 (13)
Under this case, our SMDA algorithm will reduce a novel adaptive gradient descent ascent algorithm.
In the problem (1), the functions g(x) and h(y) are generally nonsmooth, e.g., g(x) = ν1‖x‖1 and h(y) = ν2‖y‖1 with ν1 > 0, ν2 > 0. When Bregman functions ψt(x) = 12x
THtx and φt(y) = 1 2y TGty for all t ≥ 1, and the matrices Ht and Gt are diagonal, e.g., generated from the above (12) and (13), we can use the soft thresholding operator S(a, λ) = sign(a) max(|a| − λ, 0) = arg minz{ 12 (z − a) 2 + λ|z|} to obtain the closed-form solutions of the following subproblems:
min x∈X
{ 〈vt, x〉+ 1
2γt (x− xt)THt(x− xt) + ν1‖x‖1
} , (14)
max y∈Y
{ 〈wt, y〉 − 1
2λt (y − yt)TGt(y − yt)− ν2‖y‖1
} , (15)
where Ht = diag(h1,t, · · · , hd,t) with hi,t > 0 for i ∈ [d], and Gt = diag(g1,t, · · · , gp,t) with gj,t > 0 for j ∈ [p]. Without loss of generality, let X = Rd and Y = Rp, we have
S ( xi,t −
γt hi,t vi,t, γtν1 hi,t
) = arg min
xi∈R
{ 〈vi,t, xi〉+
hi,t 2γt
(xi − xi,t)2 + ν1|xi| } , i ∈ [d] (16)
S ( yj,t +
λt gj,t wj,t, λtν2 gj,t
) = arg max
yj∈R
{ 〈wj,t, yj〉 −
gj,t 2λt
(yj − yj,t)2 − ν2|yj | } , j ∈ [p]. (17)
Algorithm 2 Accelerated Stochastic Mirror Descent Ascent (VR-SMDA) Algorithm
1: Input: T , q, stepsizes {γt > 0, λt > 0, ηt ∈ (0, 1]}Tt=1, mini-batch sizes b and b1; 2: initialize: x1 ∈ X and y1 ∈ Y; 3: for t = 1, 2, . . . , T do 4: if mod (t, q) = 0 then 5: Randomly generate mini-batch samples Bt = {ξit}bi=1 with |Bt| = b; 6: Compute stochastic partial derivatives vt = ∇xfBt(xt, yt) and wt = ∇yfBt(xt, yt); 7: else 8: Randomly generate mini-batch samples It = {ξit} b1 i=1 with |It| = b1; 9: Compute stochastic partial derivatives
vt = ∇xfIt(xt, yt)−∇xfIt(xt−1, yt−1) + vt−1, (18) wt = ∇yfIt(xt, yt)−∇yfIt(xt−1, yt−1) + wt−1; (19)
10: end if 11: Given the mirror functions ψt and φt; 12: xt+1 = arg minx∈X { 〈vt, x〉+ 1γtDψt(x, xt) + g(x) } ;
13: yt+1 = yt + ηt(ỹt+1 − yt) where ỹt+1 = arg maxy∈Y { 〈wt, y〉 − 1λtDφt(y, yt)− h(y) } ; 14: end for 15: Output: (for theoretical) xζ and yζ chosen uniformly random from {xt, yt}Tt=1. 16: Output: (for practical) xT and yT .

heading: 4.2 VR-SMDA Algorithm
text: In this subsection, we propose an accelerated stochastic mirror descent ascent (VR-SMDA) algorithm to solve the stochastic problem (1). Algorithm 2 describes the detailed algorithmic framework of the VR-SMDA method.
In Algorithm 1, we only draw a mini-batch samples Bt = {ξit}bi=1 at each iteration. Clearly, the mini-batch samples will take large variances in our SMDA algorithm. Thus, we use the variance reduced technique of SPIDER in our VR-SMDA algorithm to accelerate it. Specifically, when mod (t, q) = 0, we draw a relative large batch samples Bt = {ξit}bi=1 to estimate our stochastic partial derivatives vt and wt; when mod (t, q) 6= 0, we only draw a mini-batch samples It = {ξit} b1 i=1 (b > b1) to estimate vt and wt in (18) and (19). Since samples It are independent to variables {xt, xt−1, yt, yt−1, vt−1}, by using Assumption 2, we have
EIt [vt] = ∇xf(xt, yt)−∇xf(xt−1, yt−1) + vt−1 6= ∇xf(xt, yt), (20) EIt [wt] = ∇yf(xt, yt)−∇yf(xt−1, yt−1) + wt−1 6= ∇yf(xt, yt). (21)
Thus, the partial derivative estimators vt and wt are biased. As in Algorithm 1, we also use the mirror descent iteration to update x, and use both the mirror ascent and momentum iterations to update y in Algorithm 2.

heading: 5 Convergence Analysis
text: In this section, we study the convergence properties of our algorithms (i.e., MDA, SMDA and VRSMDA) under some mild conditions. All related proofs are provided in the supplementary materials. We first introduce a useful convergence metric ‖Gt‖ (or E‖Gt‖) as in [13, 25] to measure convergence properties of our algorithms. Given the parameters xt at t-th iteration by our algorithms, we define a gradient mapping [36, 13] as
Gt = 1
γt (xt − x+t+1), (22)
x+t+1 = arg min x∈X
{ 〈∇Φ(xt), x〉+ 1
γt Dψt(x, xt) + g(x)
} , (23)
where Φ(x) = f(x, y∗(x)) − h(y∗(x)) = maxy∈Y{f(x, y) − h(y)}. When X = Rd and g(x) is a constant, and ψt(x) = 12‖x‖
2, we have Gt = ∇Φ(xt) = ∇xf(xt, y∗(xt)). Under this case, our convergence metric E‖Gt‖ = E‖∇xf(xt, y∗(xt))‖ is a common convergence metric used in [27].
Since the objective function f(x, y) is µ-strongly concave over y, the standard (stochastic) proximal gradient ascent can easily obtain the global solution of the subproblem maxy∈Y{f(x, y) − h(y)}. Without loss of generalization, in our theoretical analysis, we give the mirror functions φt(y) = 12‖y‖ 2 for all t ≥ 1, and all mirror functions {ψt(x)}Tt=1 are ρ-strong convex. Here, the constant ρ can be seen as a lower bound of the strong convexity of all functions {ψt(x)}Tt=1 as in [25].

heading: 5.1 Convergence Analysis of the SMDA and MDA Algorithms
text: In the subsection, we provide the convergence properties of our SMDA and MDA algorithms.
Theorem 1. Suppose the sequence {xt, yt}Tt=1 be generated from Algorithm 1 using stochastic partial derivatives (i.e., SMDA algorithm). Let 0 < η = ηt ≤ 1, 0 < γ = γt ≤ min( 3ρ4L , 9ηρµλ 800κ2 , 2ηµρλ 25L2f ) and 0 < λ = λt ≤ 16Lf , we have
1
T T∑ t=1
E‖Gt‖ ≤ 4 √ 2(F̃ (x1)− F ∗) √
3Tγρ +
4 √
2∆1√ 3Tγρ + 10σ√ 3bρ
+ 20σ √ ηλ
3 √ γρµb , (24)
where κ = Lf/µ, L = Lf (1 + κ), F̃ (x) = Φ(x) + g(x) and ∆1 = ‖y1 − y∗(x1)‖. Remark 1. Without loss of generality, let Lf ≥ 1µ . Given 0 < η ≤ 1, λ = O( 1 Lf ), γ = min( 3ρ4L , 9ηρµλ 800κ2 , 2ηµρλ 25L2f ) and ρ = O(Lνf ) (ν ≥ 0), we have γ = O(κν−3) and γρ = O(κ2ν−3).
Thus, our SMDA algorithm has a convergence rate of O (√ κ3−2ν T + √ κ−2ν b + √ κ3−2ν b ) . When let
ν = 12 , b = T/κ and √ κ2 T = /3, we have T = O(κ 2 −2) and b = O(κ −2). Since our SMDA algorithm requires 2b stochastic gradient evaluations to estimate the stochastic partial directives vt and wt at each iteration, and needs T iterations, it has a gradient complexity of 2bT = O(κ3 −4) for finding an -stationary point, the same complexity in [4]. When let ν = 4/3, b = T/κ1/3 and√
κ1/3 T = /3, we have T = O(κ 1/3 −2) and b = O( −2). Thus, our SMDA algorithm has a near optimal gradient complexity of 2bT = O(κ1/3 −4), which matches a gradient complexity lower bound given in [24] for solving the problem (1) without the nonsmooth regularization terms.
Theorem 2. Suppose the sequence {xt, yt}Tt=1 be generated from Algorithm 1 using the deterministic partial derivatives (i.e., MDA algorithm). Let 0 < η = ηt ≤ 1, 0 < γ = γt ≤ min( 3ρ4L , 9ηρµλ 800κ2 , 2ηµρλ 25L2f ) and 0 < λ = λt ≤ 16Lf , we have
1
T T∑ t=1
‖Gt‖ ≤ 4 √ 2(F̃ (x1)− F ∗) √
3Tγρ +
4 √
2∆1√ 3Tγρ , (25)
where κ = Lf/µ, L = Lf (1 + κ), F̃ (x) = Φ(x) + g(x) and ∆1 = ‖y1 − y∗(x1)‖. Remark 2. Without loss of generality, let Lf ≥ 1µ . Given 0 < η ≤ 1, λ = O( 1 Lf ),
γ = min( 3ρ4L , 9ηρµλ 800κ2 , 2ηµρλ 25L2f
) and ρ = O(L( 1 2+ν)
f ) (ν ≥ 0), we have 1 γρ = O
( κ(2−2ν) ) . Since
our MDA algorithm requires 2 gradient evaluations at each iteration, and needs T iterations, it has a gradient complexity of 2T = O ( κ(2−2ν) −2 ) for finding an -stationary point. When let ν = 0, our MDA algorithm has a gradient complexity of 2T = O(κ2 −2), the same complexity in [4]. When let ν = 1/2, our MDA algorithm has a lower gradient complexity of T = O(κ −2) than the complexity in [4, 2]. When let ν = 3/4, our MDA algorithm has a near optimal gradient complexity of T = O( √ κ −2), which is the same complexity in [28] for solving the problem (1) without the nonsmooth regularization terms.

heading: 5.2 Convergence Analysis of the VR-SMDA Algorithm
text: In the subsection, we provide the convergence properties of the VR-SMDA algorithm.
Theorem 3. Suppose the sequence {xt, yt}Tt=1 be generated from Algorithm 2. Let b1 = q, 0 < η = ηt ≤ 1, 0 < γ = γt ≤ min( 3ρ4L , ηµλρ 38L2f , 3ρ 19L2fη , ρη8 , 9ρηµλ 400κ2 ) and 0 < λ = λt ≤ min( 1 6Lf , 9µ 100η2L2f ),
we have
1
T T∑ t=1
E‖Gt‖ ≤ 4 √ 2(F̃ (x1)− F ∗) √
3Tγρ +
4 √
2∆1√ 3Tγρ
+ 2 √
2σ√ γρηbLf , (26)
where κ = Lf/µ, L = Lf (1 + κ), F̃ (x) = Φ(x) + g(x) and ∆1 = ‖y1 − y∗(x1)‖. Remark 3. Without loss of generality, let Lf ≥ 1µ . Given 0 < η ≤ 1, λ = O( 1 κLf ), γ = min( 3ρ4L , ηµλρ 38L2f , 3ρ 19L2fη , ρη8 , 9ρηµλ 400κ2 ) and ρ = O(L 1+ν f ) (ν ≥ 0), we have 1 γρ = O(κ 2−2ν). Thus, our
VR-SMDA algorithm has a convergence rate of O( √ κ(2−2ν) T + √ κ(1−2ν) b ). When let ν = 0, b = T/κ
and √ κ2
T = /2, we have T = O(κ 2 −2). Further let b1 = q = O(κ −1) and b = O(κ −2).
Since our VR-SMDA algorithm requires 2b stochastic gradient evaluations to estimate the stochastic directives vt and wt at each iteration when mod (t, q) = 0, otherwise needs 4b1 stochastic gradient evaluations, and need T iterations, it has a gradient complexity of 4b1T + 2bT/q = O(κ3 −3) for finding an -stationary point of the problem (1), which is the same complexity in [30] for solving the problem (1) without the nonsmooth regularization terms.
Remark 4. The above optimal gradient complexities are obtained when given ρ = O(Lν ′ f ) (ν ′ > 0), where Lf is the smooth parameter of objective function f(x, y). Although in the objective function f(x, y), Lf may be large, we can easily change the original objective function f(x, y) to a new function f̂(x, y) = τf(x, y), 0 < τ < 1. Since ∇f̂(x, y) = τ∇f(x, y), the gradient of function f̂(x, y) is L̂-Lipschitz continuous (L̂ = τLf ). Thus, we can choose a suitable hyper-parameter τ to let this new objective function f̂(x, y) satisfy the condition ρ = O(L̂).

heading: 6 Numerical Experiments
text: In this section, we perform two tasks (i.e., fair classifier and robust neural network training) to validate efficiency of our algorithms. Specifically, we conduct these tasks on the Fashion-MNIST dataset as in [38] as well MNIST dataset and CIFAR-10 dataset. Fashion-MNIST dataset and MNIST dataset consist of 28× 28 arrays of grayscale pixel images classified into 10 categories, and includes 60, 000 training images and 10, 000 testing images. CIFAR-10 dataset includes 60, 000 32 × 32 colour images (50, 000 training images and 10, 000 testing images). In the experiment, we compare our algorithms (MDA, SMDA and VR-SMDA) with the existing proximal gradient descent ascent algorithms (MAPGDA [2], PAGDA [4] and PASGDA[4] ) for solving these nonsmooth nonconvex minimax problems. Note that both HiBSA algorithm of [29] and Proximal-GDA algorithm of [8] only are a non-accelerated version of MAPGDA algorithm [2], so we omit them in the comparison methods. The experiments are run on CPU machines with 2.3 GHz Intel Core i9 as well as NVIDIA Tesla P40 GPU.

heading: 6.1 Fair Classifier
text: The first task is to train a fair classifier to minimize the maximum loss over categories. Here, we use a nonconvex Convolutional Neural Network (CNN) model as classifier. Similar to [38], we limit our experiment to the three categories. To be precise, the Fashion-MNIST dataset is limited to T-shirt/top,
Coat and Shirt categories. The MNIST dataset is limited to digital numbers {0, 2, 3}, and CIFAR10 dataset is limited to airplane, automobile and bird. Specifically, we will solve the minimax problem:
min w max y∈Y { 3∑ i=1 yiLi(w) + g(w)− h(y) } , s.t. Y = { y ∈ R3 | yi ≥ 0, 3∑ i=1 yi = 1 } , (27)
where w denotes the parameters in CNN model, and L1, L2 and L3 are the loss functions corresponding to the samples in three different categories. Here we let g(w) = ν1‖w‖1 and h(y) = ν2‖y‖22, where ν1 > 0 and ν2 > 0. Clearly the inner maximization problem is strongly concave, and the outer minimization problem is nonconvex nonsmooth. Thus our theory can be applied.
In the experiment, we let ν1 = 0.001 and ν2 = 0.1 in the above problem (27). For fair comparison, we use the same step size for all methods. Specifically, step-size for w is 0.001 and step-size for y is 0.00001. We apply xavier normal initialization to CNN layer. In our algorithms, we choose the mirror functions ψt(w) = 12w THtw and φt(y) = 12y TGty for all t ≥ 1, where Ht and Gt are generated from (12) and (13) respectively, given α = 0.1 and ρ = 0.00005. We set η = ηt = 1 in our algorithms. We run all deterministic algorithms for 1000 seconds and all stochastic algorithms for 50 epochs. Then we record the loss value. For stochastic methods, batch sizes of PASGDA and SMDA are 3000. For our VR-SMDA, we set the large batch size b = 60000 and the mini-batch size b1 = q = 3000.
Figure 1 shows the loss vs time of different deterministic methods. Figure 2 plots the loss vs epoch of different stochastic methods. From these results, we can find that our algorithms consistently outperform the other algorithms with a great margin. The main reason is that our algorithms use the preconditioned (adaptive) matrices Ht and Gt in updating x and y, respectively.

heading: 6.2 Robust Neural Network Training
text: The second task is to train robust Neural Networks (NNs). Although the NNs have been widely used in many applications such as image classification, they are vulnerable to adversarial attacks such as Fast Gradient Sign Method (FGSM) [15] and Projected Gradient Descent (PGD) attack [22]. In other word, a small perturbation in the input of NN can significantly change its output. Thus, we try to train a robust NN against these adversarial attacks, which generally reformulate this robust training into the following minimax problem:
min w n∑ i=1 max yi∈Y L ( f(ai + yi;w), bi ) , Y = { yi ∈ Rd | ‖yi‖∞ ≤ ε, i ∈ [n] } (28)
where (ai, bi) denotes the i-th data point, and w is the parameter of NN, and yi ∈ Rd denotes is the perturbation added to the i-th data point. Following [38], we approximate the inner maximization problem of the above minimax problem (28) with the following finite max problem
min w n∑ i=1 max { L ( f(âi,0(w);w), bi ) , · · · ,L ( f(âi,9(w);w), bi )} , (29)
where âi,j(w) is the result of a targeted attack on data point ai that is changed the output of NN to label j. Following [38], we can obtain âi,j(w) by using the following procedure: In the last layer of the NN architecture for learning classification on MNIST (Fashion-MNIST) we have 10 different
neurons, each corresponding with one category of classification. For any sample (ai, bi) in the dataset and starting from a0i,j = ai for any j = 0, 1, · · · , 9, we run projected gradient ascent to obtain the following chain of points:
ak+1i,j = ProjY [ aki,j + µ∇a ( Zj(a k i,j , w)− Zbi(aki,j , w) )] , k = 0, 1, · · · ,K − 1 (30)
where µ > 0 is a stepsize, and Zj is the network logit before softmax corresponding to label j. Finally, we can set âi,j(w) = aKi,j in the above minimax problem (29).
Next, we can replace the above problem (29) with the following nonconvex nonsmooth problem:
min w n∑ i=1 max u∈U { 9∑ j=0 uj L ( f(aKi,j ;w), bi ) + ν1‖w‖1 − ν2‖u‖22 } , (31)
s.t. U = { u ∈ R10 | uj ≥ 0, 9∑ j=0 uj = 1 } ,
where ν1 > 0 and ν2 > 0. Clearly, the inner maximization problem in (31) is strongly-concave, and its outer minimization problem is nonconvex and nonsmooth.
In the experiment, we set ν1 = 0.0001 and ν2 = 0.1 in the above problem (31). In the above problem (30), we set K = 5. For fair comparison, we use the same step size for all methods. Specifically, step-size for w is 0.0005 and step-size for u is 0.00001. We set η = ηt = 1 in our algorithms. For our algorithms, we choose the mirror functions ψt(w) = 12w THtw and φt(u) = 12u TGtu for all t ≥ 1, where Ht and Gt are generated from (12) and (13) respectively, given α = 0.1 and ρ = 0.0005. Here we only conduct experiments with stochastic methods, and batch-sizes of PASGDA and SMDA are 600. For our VR-SMDA, we set b = 1200 and b1 = q = 600. Following [38], we set ε = 0.4 in the above problem (28). Figure 3 shows the loss vs epoch of different stochastic methods. From these results, we can find that our algorithms outperform the other algorithms, and the VR-SMDA consistently outperforms the SMDA.

heading: 7 Conclusions
text: In the paper, we proposed a class of novel adaptive mirror descent ascent methods to solve the nonconvex-strongly-concave minimax optimization problems with nonsmooth regularization terms. Moreover, we provided a useful convergence analysis framework for our methods. Some experimental results on fair classifier and robust neural network training tasks verify that our new algorithms consistently outperform the related algorithms.
Acknowledgments and Disclosure of Funding
This work was partially supported by NSF IIS 1845666, 1852606, 1838627, 1837956, 1956002, OIA 2040588.

Review summaries:
This paper proposes efficient mirror descent ascent (MDA) methods to solve the nonsmooth nonconvex-strongly-concave minimax problems. The SOTA convergence rates are established both for deterministic and stochastic settings. In practice, some experimetal results are provided to demonstrate the efficiencies of the proposed MDA methods. Overall, this is a very good paper.

This paper proposes a class of mirror descent ascent (MDA) methods for solving nonsmooth and nonconvex-strongly-concave minimax optimization problems by using dynamic mirror functions. It also studies the convergence properties of the proposed algorithms. In particular, the MDA method achieves a lower sample complexity by using the strongly-convex mirror function. The paper also provides some numerical experiments on fair classifiers and robust neural network training tasks to demonstrate the efficiency of the proposed algorithms. This paper first applies the mirror descent algorithm to nonsmooth minimax optimization. It provides a rigorous convergence analysis of the proposed algorithms. Overall, this paper is interesting and has some novelties. Thus I recommend accepting this paper.