A Faster Decentralized Algorithm for Nonconvex Minimax Problems
Year: 2022

Abstract:
In this paper, we study the nonconvex-strongly-concave minimax optimization problem on decentralized setting. The minimax problems are attracting increasing attentions because of their popular practical applications such as policy evaluation and adversarial training. As training data become larger, distributed training has been broadly adopted in machine learning tasks. Recent research works show that the decentralized distributed data-parallel training techniques are specially promising, because they can achieve the efficient communications and avoid the bottleneck problem on the central node or the latency of low bandwidth network. However, the decentralized minimax problems were seldom studied in literature and the existing methods suffer from very high gradient complexity. To address this challenge, we propose a new faster decentralized algorithm, named as DMHSGD, for nonconvex minimax problems by using the variance reduced technique of hybrid stochastic gradient descent. We prove that our DM-HSGD algorithm achieves stochastic first-order oracle (SFO) complexity of O(κ −3) for decentralized stochastic nonconvex-strongly-concave problem to search an -stationary point, which improves the exiting best theoretical results. Moreover, we also prove that our algorithm achieves linear speedup with respect to the number of workers. Our experiments on decentralized settings show the superior performance of our new algorithm.

heading: 1 Introduction
text: Minimax optimization has enormous applications in machine learning tasks such as Generative Adversarial Net (GAN) [8], adversarial training [26] and multi-agent reinforcement learning [43]. Specifically, in minimax optimization, variable x aims to minimize a payoff loss function f(x, y) : Rd1 × Rd2 → R while variable y tries to maximize the loss, which can be formulated as
min x∈X max y∈Y f(x, y), (1)
where X ⊆ Rd1 and Y ⊆ Rd2 . In the past a few decades, there are plenty of works to study minimax optimization problem in a variety of research fields and many methods have been developed. The most intuitive solution is Gradient Descent Ascent (GDA) algorithm [6, 29] with equal stepsize ηx = ηy . Asymptotic and nonasymptotic convergence analysis has been provided when f is convex in x and concave in y. Recently, many deterministic and stochastic gradient algorithms for nonconvexstrongly-concave and nonconvex-concave problems were proposed. Some algorithms improve the performance of vanilla GDA method by adopting different stepsize on x and y, such as [10, 19], where the stepsize of y is typically larger than the stepsize of x. Some algorithms update x and y at different frequency, such as [14, 25, 32]. These kind of algorithms usually involve a nested loop structure that updates y more frequently than x to make f(x, y) close to function Φ(x), which is defined by
Φ(x) = max y∈Y f(x, y). (2)
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
As more large-scale machine learning problems are arising, distributed training becomes a popular and crucial framework because of its ability and efficiency to deal with large data. It is desired to generalize minimax optimization to distributed training to solve large-scale minimax problems. In distributed optimization, the original centralized optimization suffers from a bottleneck communication problem, i.e. the communication traffic on the busiest central node, especially when the network is large [18, 51]. To tackle this communication issue, decentralized optimization was proposed and has emerged as a promising technique. It is a kind of distributed machine learning training paradigm that does not rely on the centralized network topology. Different worker nodes collaboratively utilize their own local data to implement large-scale training tasks and at each iteration they only have to communicate with their neighbors. Decentralized algorithms have been shown to enhance the communication efficiency by avoiding the communication overhead problem. Decentralized methods are also advantageous when the network suffers from communication restriction or has low bandwidth between some nodes and the central node. Besides, it is also an essential method in some situations where data are geographically distributed and centralized data processing is not available or there are concerns to preserve data privacy [48].
Recently many works were proposed to improve the performance of decentralized training. D-PSGD [18] theoretically justifies the potential advantage of decentralized algorithm. D2 [38] improves the convergence rate to outperform D-PSGD by eliminating the influence of data variance among different workers. D-SPIDER-SFO [33] incorporates D2 and SPIDER [7, 44], which is a kind of variance reduction technique [15], to further reduce the gradient complexity. DQSFW [45] studies decentralized constrained problem with Frank-Wolfe method. GT-HSGD [46] extends hybrid stochastic gradient descent to decentralized setting, which is a variance-reduced approach that does not compute mega batch periodically. However, the decentralized minimax optimization is still very limited and existing methods suffer from very high gradient complexity [21, 41]. Thus, we are motivated to design an accelerated decentralized algorithm for minimax problems.
In this paper, thus, we propose a faster Decentralized Minimax Hybrid Stochastic Gradient Descent (DM-HSGD) algorithm to solve the following decentralized stochastic minimax optimization problem:
min x∈Rd1 max y∈Y
f(x, y) = 1
n n∑ i=1 fi(x, y), fi(x, y) := Eξ(i)∼DiFi(x, y; ξ (i)) (3)
where n is the number of worker nodes, Y is a convex set. Here the local component objective function Fi(x, y; ξ(i)) is L-smooth, nonconvex in x, and strongly-concave in y. Di is the data distribution on the i-th node. In this paper, the data distribution can be non-identical. Random variable ξ(i) is an index sampled from the local data. We summarize our contributions as follows:
(1) In this paper, we propose a new accelerated decentralized stochastic first-order algorithm, named as DM-HSGD, to solve the decentralized nonconvex-strongly-concave minimax optimization problems. Our algorithm is the first stochastic gradient algorithm to solve general decentralized minimax problem on non-identical distributed data with theoretical guarantees. Besides, our algorithm does not require large batch size or nested loop which makes it more practical and efficient to implement.
(2) We provide a completed proof to guarantee the convergence of our algorithm to solve decentralized stochastic minimax optimization. Under nonconvex-strongly-concave condition, our algorithm obtains SFO complexity of O(κ3 −3) to search an -stationary point of function Φ(x) = maxy∈Y f(x, y). This result is faster than the complexity of previous decentralized minimax algorithms [21, 41]. Moreover, we also prove that our method achieves linear speedup as the number of workers n increases, which verifies its ability to solve large-scale problems.
The rest of this paper will be organized as follows. In Section 2, we will introduce related works. In Section 3, we will introduce our new DM-HSGD algorithm. In Section 4, we will show the main theorems of convergence and complexity analysis. In Section 5, we will discuss our experimental results, and Section 6 will conclude the paper.

heading: 2 Related Works

heading: 2.1 Centralized Minimax Optimization
text: In recent years, many algorithms for solving minimax optimization were proposed, and the majority of them were studied under the nonconvex-strongly-concave condition. SGDmax [14] is a double loop algorithm that achieves SFO complexity of O(κ3 −4log(1/ )) where κ = L/µ is the condition number. Proximally Guided Stochastic Mirror Descent and Variance Reduction (PGSMD/PGSVRG) [34] are double loop algorithms that achieve SFO complexity of O(κ3 −4) for stochastic problem and O(κ2N −2) for finite-sum problem whereN is the number of samples. Multistep GDA (MGDA) [32] is a double loop algorithm and HiBSA [23] is a single loop algorithm. Both MGDA and HiBSA are deterministic hence they can only solve finite-sum problems. Both of them achieve SFO complexity of O(κ4N −2). Proximal Dual Implicit Accelerated Gradient (ProxDIAG) is a deterministic triple loop algorithm whose SFO complexity for finite-sum problem is O(κ1/2N −2).
SGDA [19], Stochastic Recursive gradiEnt Descent Ascent (SREDA) [25], and Hybrid VarianceReduced SGD [40] are more related to our work. SGDA is a single loop algorithm to solve nonconvexstrongly-concave and nonconvex-concave minimax problems. For nonconvex-strongly-concave problem, it requires O(κ3 −4) SFO complexity to find an -stationary point of Φ(x). In this paper, we will prove that our method achieves a better SFO complexity.
SREDA [25] is a double loop algorithm that achieves O(κ3 −3) SFO complexity. It accelerates SGDA by using SPIDER, which is a variance reduction technique and utilizes the newest gradient information [7, 30]. SREDA also involves a separated initialization algorithm called PiSARAH [31] to ensure the convergence. More recently, [13] proposed an efficient mirror descent ascent algorithm for nonconvex-strongly-concave minimax optimization with nonsmooth regularization based on Bregman distance and variance reduced technique of SPIDER. In our paper, we use another variance-reduced technique named STORM or hybrid stochastic gradient descent [3] to accelerate the algorithm. We will discuss the challenges of using SPIDER on decentralized settings in Section 3. Different from SREDA, our method only requires a large batch at the first iteration. Except the first iteration, we can use either a single sample or a mini-batch to calculate the stochastic gradient. However, SREDA loads a mega-batch with size O( −2) periodically (every q iterations) and needs O( −1) gradient oracles at each iteration, which is not practical for large-scale problems. Besides, the maximizer in SREDA is a nested loop to update variable y and if we count the loop of SPIDER then SREDA is actually a triple algorithm. On the contrary, there is no nested loop in our DM-HSGD, which makes our method more efficient and convenient to implement. Moreover, unlike SREDA, our method does not require a separated initialization algorithm to calculate a precise initial value for y.
Hybrid Variance-Reduced SGD algorithm also takes advantage of hybrid stochastic gradient descent to accelerate minimax optimization. For example, [40, 11] applied the Hybrid Variance-Reduced SGD to minimax problems. More recently, [9, 12] proposed some efficient adaptive gradient descent ascent methods for nonconvex-strongly-concave minimax optimization based on momentum techniques including Hybrid Variance-Reduced SGD.

heading: 2.2 Decentralized Minimax Optimization
text: At decentralized setting, most minimax algorithms were proposed for convex-concave problem [17, 28]. In [22] a nonconvex-nonconcave algorithm DPPSP was proposed. However, it is not
gradient-based and the closed-form solution to the subproblem is not ensured in our problem. Hence we will not discuss it in this paper. Decentralized Parallel Optimistic Stochastic Gradient (DPOSG) [21] is the first algorithm applicable to a general decentralized minimax problem with theoretical guarantees. It is a single loop minimax algorithm that generalizes Optimistic Stochastic Gradient (OSG) [2] to decentralized training. However, DPOSG has some obvious drawbacks. The first one is that the gradient complexity O( −12) is too high and we are motivated to design a faster algorithm. The second one is that DPOSG only works in the case where the data distribution is identical. When the data distribution is non-identical, the Lemma 3 in [21] is not satisfied. Actually the assumption of identical data distribution is not satisfied at most decentralized training tasks. Thus, in this paper, we do not use this assumption.
More recently, [41] studied decentralized nonconvex-strongly-concave minimax problems and proposed a double loop deterministic Gradient Tracking/Descent-Ascent algorithm which extends the vanilla GDA to decentralized setting and combines it with gradient tracking. It achieves a gradient complexity of O( −2). However, in large-scale machine learning tasks such as deep neural network, generally the full gradient is unavailable and the application of deterministic algorithms is very restricted. If we convert Gradient Tracking/Descent-Ascent to stochastic gradient version, the SFO complexity should be at least O( −4), which is the same result as SGD in nonconvex optimization. Under the same conditions, our new algorithm achieves a better SFO complexity of O( −3).
[24] studied decentralized reinforcement learning problem based on distributed constrained Markov decision process model and proposed a decentralized policy gradient optimization method named Safe Dec-PG, which achieves SFO complexity of O( −4). However, the problem studied in [24] has a special form that is linear in y. In this paper, we focus on general minimax problem. [1] is a simultaneous work of our work that studies a more general decentralized variational inequality problem with higher complexity. We summarize the comparison of related algorithms for general minimax optimization in Table 1. For decentralized algorithms DPOSG, GT/DA, and DM-HSGD, we also discuss whether they can converge on non-identical distributed data.

heading: 3 Proposed New Algorithm

heading: 3.1 Preliminaries
text: Before we propose our algorithms, we will introduce the notations used in this paper and some important concepts. We use lower case x(i)t and y (i) t to represent the column vector parameters on i-th worker node. We use upper case Xt and Yt to represent the n-column matrix formed by x (i) t and y (i) t respectively, which means Xt = [x (1) t , x (2) t , . . . , x (n) t ] and Yt = [y (1) t , y (2) t , . . . , y (n) t ]. Column vectors u(i)t , v (i) t , g (i) t and h (i) t are gradient estimators used in our algorithms. Upper case Ut, Vt, Gt and Ht are matrices of which the i-th column is u (i) t , v (i) t , g (i) t and h (i) t respectively. Lower case with a bar represents the mean vector. Upper case with a bar represents the matrix that each column is the mean vector. For example, x̄t = 1n ∑n i=1 x (i) t and X̄t = [x̄t, x̄t, . . . , x̄t]. We define the optimal maximum value of y as:
y∗(·) = arg max y∈Y f(·, y), ŷt = arg max y∈Y f(x̄t, y) (4)
Note that when f is strongly-concave in y, ŷt is unique. We also define:
δt = ‖ŷt − ȳt‖2 (5)
Bold number 0 and 1 are n× 1 column vectors that each entry is 0 and 1, respectively. For matrices, we use ‖·‖F to denote Frobenius norm and ‖·‖2 to denote spectral norm. We use ∇x and ∇y to denote the partial derivative with respect to x and y.
Mixing matrix W represents the weights of averaging among the communication network topology. It is doubly stochastic which satisfies:
W1 = WT1 = 1 (6)
We should notice that here matrix W is not assumed to be symmetric so that the communication network is not restricted to undirected graph.
Algorithm 1 DM-HSGD
Input: mixing matrix W , initial value x(i)0 = x0, y (i) 0 = y0, v (i) −1 = g (i) −1 = 0, u (i) −1 = h (i) −1 = 0 Parameter: stepsize ηx, ηy , weight βx, βy , batch size b0, iteration T Output: x̄ζ , where ζ is chosen randomly from {1, 2, · · · , T}
1: On i-th node: 2: for t = 0, 1, . . . , T − 1 do 3: if t = 0 then 4: g(i)t = ∇xFi(x (i) t , y (i) t ; ξ (i) x,t), |ξ (i) x,t| = b0 5: h(i)t = ∇yFi(x (i) t , y (i) t ; ξ (i) y,t), |ξ (i) y,t| = b0 6: else 7: g(i)t = ∇xFi(x (i) t , y (i) t ; ξ (i) t ) + (1− βx)(g (i) t−1 −∇xFi(x (i) t−1, y (i) t−1; ξ (i) t )) 8: h(i)t = ∇yFi(x (i) t , y (i) t ; ξ (i) t ) + (1− βy)(h (i) t−1 −∇yFi(x (i) t−1, y (i) t−1; ξ (i) t ))
9: end if 10: Communicate with neighbors and update gradient estimator as follows 11: v(i)t = ∑n j=1 wij(v (j) t−1 + g (j) t − g (j) t−1)
12: u(i)t = ∑n j=1 wij(u (j) t−1 + h (j) t − h (j) t−1) 13: Communicate with neighbors and update model parameter as follows 14: x(i)t+1 = ∑n j=1 wij(x (j) t − ηxv (j) t ) 15: y(i) t+ 12 = ∑n j=1 wij(y (j) t + ηyu (j) t ), y (i) t+1 = PY(y (i) t+ 12 ) 16: end for

heading: 3.2 Decentralized Minimax Hybrid Stochastic Gradient Descent
text: In this subsection, we introduce our new Decentralized Minimax Hybrid Stochastic Gradient Descent (DM-HSGD) algorithm. Our algorithm is a single loop minimax algorithm (summarized in Algorithm 1) which does not contain a nested loop structure.
The initial points of different nodes are the same, i.e. x(i)0 = x0 and y (i) 0 . g (i) t and h (i) t are the gradient estimators with respect to x and y on i-th node. g(i)t and h (i) t are computed in the same way as STORM [3]. When t = 0, we load a large batch with size b0 to calculate the stochastic gradient (lines 4 and 5 in Algorithm 1). When t > 0, we can use either a single sample or a mini-batch to calculate the gradient (lines 7 and 8 in Algorithm 1). g(i)t can also be written as
g (i) t =βx∇xFi(x (i) t , y (i) t ; ξ (i) t )+(1−βx)
( g
(i) t−1−∇xFi(x (i) t−1, y (i) t−1; ξ (i) t )+∇xFi(x (i) t , y (i) t ; ξ (i) t ) ) (7)
which is a linear combination of the gradient estimators of stochastic gradient descent (the first part) and SPIDER (the second part). As we have mentioned, SPIDER is a variance-reduced method that utilizes the newest gradient information. Thus, estimator Eq. (7) is also called hybrid stochastic gradient descent. It is the same with h(i)t . Then each worker communicates with their neighbors to compute gradient estimator v(i)t and u (i) t . Here we use gradient tracking [5, 47] to reduce the consensus error (lines 11 and 12 in Algorithm 1). We will discuss why gradient tracking is necessary in our method at next subsection. After we obtain u(i)t and v (i) t , each worker communicates with their neighbors again and updates the model parameters x and y. Here PY(·) represents the projection onto convex set Y . In the theoretical analysis, we define Y− 12 = Y0.

heading: 3.3 Discussions on STORM and Gradient Tracking
text: In this subsection, we will discuss the intuition of our algorithm and explain why we choose STORM and gradient tracking rather than generalizing SREDA for decentralized setting. The first reason is that SREDA requires large batch or full batch periodically, which is expensive and even unavailable. Besides, there are too many nested loops in SREDA and it is not efficient or convenient. From the view of theoretical analysis, normalization or projection are likely to cause divergence in decentralized training on non-identical data distribution, which is indicated by the following Example 1. Therefore, in the circumstance of this paper, SPIDER will probably not converge to a stationary point. Besides,
SREDA adopts smaller stepsize at the beginning and larger stepsize at the end when ‖vt‖ becomes small enough. However, when the data distribution is non-identical, ‖vt‖ may not tend to 0 and the stepsize of SREDA will probably always keep small. In contrast, STORM can avoid these issues and we use STORM to accelerate the decentralized minimax algorithm.
In the standard decentralized framework D-PSGD [18], the consensus error satisfies ‖Xt − X̄t‖F ≤ O( ) when the stepsize η is O( ) and t is large enough. The following Example 2 is a simple example to show that this bound is tight and there are cases where consensus error ‖Xt − X̄t‖F is exactly Θ(η) when the data distribution is non-identical. However, according to the analysis of STORM [3] without gradient tracking, the error term et = ḡt − ∇xf(x̄t, ȳt) between the averaged update direction and the correct direction is supposed to satisfy:
‖et‖2 ≤ (1− βx)‖et−1‖2 +O(η4x) . (8)
Nevertheless, the consensus error ‖Xt − X̄t‖2F is only O(η2x) and cannot be as small as O(η4x) if there is no gradient tracking. Therefore, to inherit the analysis framework of STORM, the gradient tracking in our algorithm is essential. Example 1. Assume f(x) = f1(x) + f2(x), where x = (a, b) ∈ R2. f1(x) = a and f2(x) = √
3b are defined on two different nodes. Let W be the uniform weighted mixing matrix. We can compute v1 = (1, 0) and v2 = (0, √ 3). The ideal averaged gradient direction is v∗ = (1/2, √ 3/2). However, if we do normalization before making consensus, the obtained gradient estimator is v = (1/2, 1/2), which is deviated from v∗.
Example 2. Suppose there are two sequences {pt} and {qt} defined on two different nodes with p0 = q0. They are updated by pt+ 12 = pt − ηa and qt+ 12 = qt − ηb at each iteration respectively where a and b are fixed gradient directions. As data distribution is non-identical, we have a 6= b. Assume the mixing matrix is
W = [ 2/3 1/3 1/3 2/3 ] Then we have
pt+1−qt+1 = 1
3 (pt−qt)−
η 3 (a−b)= 1 3t+1 (p0−q0)−η( t+1∑ s=1 1 3s )(a−b)= η 2 (1− 1 3t+1 )(b−a) (9)
Therefore, limt→∞‖pt − qt‖ = η2‖a− b‖.

heading: 4 Convergence Analysis
text: In this section, we will show the main theorems of our convergence analysis. The theoretical results show that the SFO complexity of our algorithm is O(κ3 −3), which is the same as the best result in centralized minimax problem [25]. First we will introduce the following assumptions.
Assumption 1. (Lipschitz Gradient). Each component function Fi(x, y; ξ) is L-smooth, which means there exists a constant L such that for any (x, y) and (x′, y′), we have
‖∇Fi(x, y; ξ)−∇Fi(x′, y′; ξ)‖2≤L2(‖x− x′‖2+‖y − y′‖2)
Assumption 2. (Bounded Variance). The gradient of each component function Fi(x, y; ξ) is an unbiased estimator of∇fi(x, y) and has bounded variance, i.e.,
E‖∇Fi(x, y; ξ)−∇fi(x, y)‖2 ≤ σ < +∞
Assumption 3. (Lower Bound). The function Φ(·) is lower bounded, i.e., infx Φ(x) = Φ∗ > −∞.
Assumption 4. (Spectral Gap). The doubly stochastic matrix W satisfies ‖W − 11 T
n ‖2 = λ ∈ [0, 1). Assumption 5. (Strongly Concave). The function fi(x, y) is µ-strongly-concave in y. That is, there exists a constant µ > 0, for any x, y and y′, we have
fi(x, y) ≤ f(x, y′) + 〈∇yf(x, y′), y − y′〉 − µ
2 ‖y − y′‖2
These are very common and mild assumptions that are frequently assumed in previous works. Assumptions 1, 2 and 3 are also used in minimax methods [25] and [19]. Assumption 4 is used in [46]. Typically, the spectral gap assumption is stated as W is symmetric and |λ2| < 1, |λn| < 1 where λ1 ≥ λ2 ≥ · · · ≥ λn are the eigenvalues of W [16, 18, 51]. Our Assumption 4 is automatically satisfied if the typical spectral gap assumption holds (see Lemma 16 in [16]). Assumption 5 is the definition of strong concavity.
In nonconvex-strongly-concave problem, we use -stationary point of Φ(x), i.e. ‖∇Φ(x)‖ ≤ as the convergence criterion. From Lemma 4.3 in [19], we know Φ(x) is differentiable and (L+κL)-smooth and y∗(·) is κ-Lipschitz, which means ‖y∗(x1) − y∗(x2)‖ ≤ κ‖x1 − x2‖ for any x1, x2 ∈ Rd1 . Furthermore, we have:
∇Φ(x̄t) = ∇xf(x̄t, ŷt) +∇yf(x̄t, ŷt) · ∂y∗(x̄t) = ∇xf(x̄t, ŷt) (10)
since∇yf(x̄t, ŷt) = 0. This criterion is broadly used in the analysis of nonconvex-strongly-concave minimax optimization [19, 39]. Now we will provide the main theorems of our convergence analysis. Completed proof can be found in the Supplementary Material.
Theorem 1. Let Assumptions 1 to 5 hold. When parameters βx = min{1,n }20 , βy = min{1,n } 500κ2 , ηx = (1−λ)2 min{1,n } 2000κ3L , ηy = (1−λ)2 min{1,n } 500κL , b0 = 400 min{1,n } , T = 4000κ3 −2
(1−λ)2 min{1,n } , our Algorithm 1 satisfies
1
T T−1∑ t=0 E‖∇Φ(x̄t)‖2 ≤ L(Φ(x0)− Φ∗) 2 + σ2 2 + L2δ0 2 + 2 n n∑ i=1 E‖∇xfi(x0, y0)‖2
+ 2
n n∑ i=1 E‖∇yfi(x0, y0)‖2 (11)
Corollary 1. When the parameters are defined as Theorem 1, we can see 1T ∑T−1 t=0 E‖∇Φ(x̄t)‖2 ≤ O( 2). Therefore, if n ≤ O( −1), the SFO complexity of Algorithm 1 is O(κ3 −3). If n > O( −1), the SFO complexity is O(κ3n −2). Besides, from the proof of Theorem 1 we can see error ‖ȳt − y∗(x̄t)‖2 is also bounded by the right side of Eq. (11).
Theorem 1 is the theoretical result when T is determined by . If the number of iteration T is not fixed, we have the following conclusion.
Theorem 2. Let Assumptions 1 to 5 hold. We set the parameters as T = 4000κ 3T0 (1−λ)2 , βx = n1/3
20T 2/3 0
,
βy = n1/3
500κ2T 2/3 0
, ηx = (1−λ)2n2/3
2000κ3T 1/3 0 L
, ηy = (1−λ)2n2/3
500κT 1/3 0 L
, b0 = T
1/3 0
n2/3 , where we suppose T0 ≥ 10n2.
Then our algorithm satisfies
1
T T−1∑ t=0 E‖∇Φ(x̄t)‖2 ≤ L(Φ(x0)− Φ∗) + σ2 + L2δ0 (nT0)2/3 + 1 n ∑n i=1 E‖∇xfi(x0, y0)‖2 T0
+ 1 n
∑n i=1 E‖∇yfi(x0, y0)‖2
T0 (12)
Corollary 2. From Theorem 2, we know 1T ∑T−1 t=0 E‖∇Φ(x̄t)‖2 ≤ O( 1 (nT0)2/3
) + O( 1T0 ) when parameters are defined as above. As we suppose T0 ≥ O(n2), the dominating term in the convergence rate is O( 1
(nT0)2/3 ), which indicates the linear speedup of our algorithm.

heading: 5 Experiments

heading: 5.1 Robust Logistic Regression
text: We conduct the experiment of decentralized robust logistic regression1 task as the first experiment, which was proposed in [49] and was also conducted in the related work [25]. Given dataset
1https://github.com/TrashzzZ/DM-HSGD
{(ai, bi)}ni=1, where ai ∈ Rd is the feature and bi ∈ {−1, 1} is the label, the robust logistic regression problem is formulated as follows:
min x∈Rd max y∈∆n f(x, y) = n∑ i=1 yili(x)− V (y) + g(x) (13)
where yi is the i-th component of variable y. li(x) is the logistic loss function which is defined by li(x) = log(1 + exp(−biaTi x)). V (y) is a divergence measure defined by V (y) = 12λ1‖ny − 1‖
2. ∆n represents the simplex in Rn, which means
∆n = {y ∈ Rn|0 ≤ yi ≤ 1, n∑ i=1 yi = 1} (14)
g(x) is a nonconvex regularization with form g(x) = λ2 ∑d i=1 αx2i 1+αx2i . Following the experimental settings in [25, 49], we let λ1 = 1n2 , λ2 = 0.001 and α = 10 in our experiment.
We conduct our experiment on six real-world training datasets “a9a", “covtype", “ijcnn1", “phishing",“rcv1" and “w8a", which can be downloaded from LIBSVM2 repository. The description of datasets is listed in Table 2 where N is the number of samples and d is the number of features. We implement our code on an MPI cluster where each node is equipped with 12-core Intel Xeon E5-2620 v3 2.40 GHz processor.
We compare our DM-HSGD algorithm with baseline algorithms: SGDA [19], SREDA [25], DPOSG [21], and stochastic Gradient Tracking/Descent Ascent (SGTDA) [41]. We consider the algorithms
2https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets
for solving stochastic problem. We set the number of worker nodes to n = 20 and use the ring-based topology as the communication network. For each algorithm, we grid search the learning rates ηx and ηy from {0.1, 0.01, 0.001, 0.0001}. The mini-batch size is set to 20. The number of iterations in the nested loop for double-loop algorithms is set to K = 5. For DM-HSGD, we set the batch size of the first iteration to b0 = 10000. βx and βy are set to 0.01. For SREDA, we set = 0.1 in the factor ‖vt‖ , period q = 50 and large batch size S1 = 1000. We compare the value of Φ(x) with respect to the number of gradient oracles among different algorithms, which can also be calculated by the projection onto simplex ∆n. The experimental results are shown in Figure 1. From the experimental results in Figure 1, we can see our new DM-HSGD algorithm converges faster than other baseline algorithms, which verifies the performance of our method.

heading: 5.2 Policy Evaluation
text: Our second experiment is the decentralized policy evaluation (PE) task. PE is an important task in reinforcement learning, which aims to estimate the value function of a given policy. The most intuitive and frequently used method for PE is temporal-difference (TD) method that relies on the Bellman equation [4]. However, traditional TD method, which is probably not true gradient descent method as pointed out in [20] and [37], are shown to be unstable in the case of off-policy sampling or nonlinear function approximation. [36] first proposed a method to optimize the objective function of mean-squared projected Bellman error (MSPBE) and MSPBE is proven to achieve asymptotic convergence with arbitrary nonlinear smooth function approximation in [27]. In [42], the MSPBE objective function with nonlinear approximation is converted into a nonconvex-strongly-concave minimax problem by Fenchel’s duality. The problem can be formulated as:
min θ max w
L(θ, w) = 1
nNi n∑ i=1 Ni∑ j=1 L (i) j (θ, w) ,
L (i) j (θ, w) = 〈w, [Ri(sj , aj) + γVθ(sj+1)− Vθ(sj)]gθ(sj)〉 −
1 2 (wT gθ(sj)) 2 (15)
where sj is a state and aj is an action. Ri represents the reward and γ ∈ (0, 1) is the discount factor. V is a value function that maps the state space to a real number. θ is the parameter to estimate the value function. Function gθ is the gradient of Vθ and parameter w is yield by Fenchel’s duality.
Mountaincar [35] is a preliminary task in reinforcement learning. [42] and [43] ran offline PE task of this problem with primal-dual MSPBE, where the objective function is formulated as Eq. (15). Following the experimental settings in [42], we use Sarsa [35] to generate trajectories of transitions (si, ai, si+1, ri) with d features and N = 5000 samples on each worker node. We parameterize value function Vθ as a 2-layer neural network with H hidden neurons. We use Sigmoid function as activation and set discount factor to γ = 0.95. This experiment is run on an MPI cluster where each node is equipped with 12-core Intel Xeon E5-2620 v3 2.40 GHz processor.
We compare our DM-HSGD algorithm with baseline algorithms: SGDA [19], SREDA [25], DPOSG [21], and stochastic Gradient Tracking/Descent Ascent (SGTDA) [41]. We also consider algorithms
for solving stochastic problem. We set the number of worker nodes to n = 20. We also use a ringbased topology with uniform weights as the communication network in this task. For each algorithm, we grid search the learning rates ηx and ηy from {0.1, 0.01, 0.001, 0.0001}. The mini-batch size is set to 20. The number of iterations in the nested loop for double-loop algorithms is set to K = 5. For DM-HSGD, we set the batch size of the first iteration to b0 = 2500. βx and βy are set to 0.01. For SREDA, we set = 0.1 in the factor ‖vt‖ , period q = 50 and large batch size S1 = 1000. We compare the value of Φ(θ) with respect to the number of gradient oracles among different algorithms, which can be calculated by quadratic optimization. The experimental results are shown in Figure 2.
Figure 2 (a), (b) and (c) show that our DM-HSGD algorithm achieves the fastest convergence regarding the number of gradient oracles. From the experimental result, we can also see that nested loop algorithm for minimax optimization usually consumes more gradient complexity during the training process than single-loop algorithm.

heading: 6 Conclusion
text: In this paper, we proposed a novel accelerated decentralized minimax algorithm, Decentralized Minimax Hybrid Stochastic Gradient Descent (DM-HSGD), to solve the stochastic nonconvexstrongly-concave minimax optimization problems. We prove that our new method obtains SFO complexity of O(κ3 −3) which outperforms the existing results in decentralized minimax optimization and matches state-of-the-art in centralized minimax optimization. Our method also achieves linear speedup with respect to the number workers, which shows its ability to solve large-scale problems. We also conduct experiments on two machine learning tasks, decentralized robust logistic regression and policy evaluation to validate the superior performance of our algorithm. In our future work, we will explore the decentralized nonconvex-concave minimax optimization without the strong concavity so that it can solve a broader range of problems including the loss functions that are linear in y. We will probably consider the methods that add a perturbation such as Catalyst [50].
Acknowledgments and Disclosure of Funding
This work was partially supported by NSF IIS 1845666, 1852606, 1838627, 1837956, 1956002, OIA 2040588.

Review summaries:
This paper studied the nonconvex-strongly-concave minimax optimization problem on decentralized setting. Existing literature investigateing decentralized minimax problems suffers from high gradient complexity. This paper proposed a faster decentralized algorithm, named as Decentralized Minimax Hybrid Stochastic Gradient Descent (DM-HSGD) and proved that it can achieve SFO complexity of $O( \kappa^3 \epsilon^{-3})$.

This paper considers stochastic nonconvex-strongly-concave minimax decentralized optimization problem. The authors propose a new faster decentralized algorithm for solving the considered problem. They showed that the proposed algorithm achieves SFO complexity of $\mathcal{O}(\kappa^3\epsilon^{-3})$, which is the best in the literature for the considered problem. Key to the improved rate is a variance reduction technique and a gradient tracking scheme. Numerical experiments are also presented.

The paper stuides the nonconvex-strongly-concave min-max optimizaton problem on decentralized setting. In particular, the decentalized min-max problems were seldom studied in the literature and the existing methods suffer from very high gradient complexity. To address this challenge, this paper proposes a new faster decentralized algorithm, namely DM-HSGD, for nonconvex min-max problems by using the variance reduced technique of hybrid stochastic gradient descent. The algorithm achieves SFO complexity of $O(\kappa^3 \epsilon^{-3})$ for decentalized stochastic nonconvex-strongly-concave problems, improving the best existing theoretical results. Numerical results on decentalized settings show the superior performance of DM-HSGD.