A Faster Decentralized Algorithm for Nonconvex Minimax Problems
Authors: Wenhan Xian
Feihu Huang
Yanfu Zhang
Heng Huang
Venue: NeurIPS 2021 Poster (2021)
Keywords: minimax optimization
decentralized optimization

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 DM-HSGD, 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(\kappa^3 \epsilon^{-3})$ for decentralized stochastic nonconvex-strongly-concave problem to search an $\epsilon$-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.

A Faster Decentralized Algorithm for Nonconvex Minimax Problems
Wenhan Xian, Feihu Huang, Yanfu Zhang, Heng Huang Electrical and Computer Engincering, University of Pittsburgh, Pittsburgh, PA 15213 wex370pitt, edu,
com, paz91@pitt... edu, neng.huang@pitt.c
Abstract
In this paper, we study the sonconve--ttrongly-com problem on decentralized setting. The minimax problems attracting increasing attentions because 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 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 new faster decentralized algorithm, named as DM- HSGD, 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 problem to search e-stationary
minimax optimization
O(Ke (((x)-=) 3) for decen-
tralized stochastic sircoonveestrrongyy-coree 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.
Introduction
Minimax optimization has enormous applications in machine learning tasks such Generative
Adversarial Net (GAN) [8], adversarial training (26) and multi-agent reinforcement learning [43
Specifically, minimax optimization, variable aims minimize payoff loss function f y) Rd1 Rd + R while variable y tries to maximize the loss, which can be formulated as
min max fIr #EX yEy
(1)
where X' C Rd and ) C Rdd,, In the past few decades, there are plenty of works to study minimax optimization problem in variety of research fields and many methods have been developed. The most intuitive solution Gradient Descent Ascent (GDA) algorithm 29) with equal stepsize T TTy Asymptotic and nonasymptotic convergence analysis has been provided when f is convex in æ and concave in y. Recently, many deterministic and stochastic gradient algorithms for nonconvex- strongly-concen and nonconvex-concav problems were proposed. Some algorithms improve the performance vanilla GDA method by adopting different stepsize on æ and y, such as [00] 19], where the stepsize of y is typically larger than the stepsize of æ. Some algorithms update and at different frequency, such as [14 25 32.. These kind of algorithms usually involve a nested loop structure that updates more frequently than x to make f(x, y) close to function d(x). which is defined by
(x)) max f(, v)- yEy
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

As more large-scale machine learning problems are arising, distributed training becomes a popular and crucial framework because of its ability and efficiency deal with large data. is desired generalize minimax optimization to distributed training to solve large-scale minimax problems. In distributed optimization, the original centralized optimization suffers from bottleneck communication problem, L.e. the communication traffic on the busiest central node, especially when the network is large (8,51) To tackle this communication issue, decentralized optimization was proposed and has emerged promising technique. It is 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 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 decentralized training. D-PSGD [8] theoretically justifies the potential advantage of decentralized algorithm. D (38] improves
the convergence rate to outperform D-PSGD by eliminating the influence of data variance among
different workers. E-SPDER--SE (33 incorporates D and SPIDER 77 44]. which is kind
of variance reduction technique [5], to further reduce the gradient complexity. DQSFW (45] studies decentralized constrained problem with Frank-Wool method. GT-HSGD 46 extends hybrid stochastic gradient descent to decentralized setting, which is a variance-reducced 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 De- scent (DM-HSGD) algorithm to solve the following decentralized stochastic minimax optimization problem:
min max f(x,y) EER vEy
Σ M(l,,)) fi(a,v) = BEWL Pi,,
where n is the number of worker nodes, y is a convex set. Here the local component objective function (x y: g()) is L-smooth, nonconvex in v, and strongly-concave in y. D, is the data distribution the i-th node. In this paper, the data distribution can be non-identical. Random variable (() is an index sampled from the local data. We summarize our contributions as follows:
(1) In this paper, we propose named as DM-HSGD, to solve the decentralized sercconvee-sroongyyyooooo 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 nested loop which makes it more practical and efficient to implement.
accelerated decentralized stochastic first-order algorithm, minimax
(2)
We provide a completed proof to guarantee the convergence of our algorithm to solve decen- tralized stochastic minimax optimization. Under nonconvex-stronge cooongly-concvv condition, our algorithm obtains SFO complexity of O to search an c-stationary point of function & ((x) max,ey far y). This result is faster than the complexity of previous decentralized minimax algorithms [2] 4I). 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. 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.
2

---

Table I: Comparison of Related Algorithms for Minimax Optimization
Name
SFO
Decentralized
Stochastic
Implementation
Reference
SGDA
O
single-loop
19
SGDmax
(nge-1lo@(1
XXX
double-loop
19
SREDA
doublc-loop
25
Acc-MDA
single-loop
DPOSG
(
v (iid)
single-loop
GT/DA
logg!!!!(! O
(non-iid)
double-loop
DM-HSGD
v (non-iid)
single-loop
Ours
2
Related Works
2.1
Centralized Minimax Optimization
In recent years, many algorithms for solving minimax optimization proposed, and the majority of them were studied under the eerroonvex-stooggyy-oooo
condition. SGDmax [4] is a double loop algorithm that achieves SFO complexity of ((n3<~\oog(//// where x 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 ((x²c=t) for stochastic problem and O(&"Ne" for finite-sum problem where is the number of samples. Multistep GDA (MGDA) single loop algorithm. Both MGDA and HiBSA are deterministic hence they can only solve finite-sum problems. Both them achieve SFO complexity of O Proximal Dual Implicit Accelerated Gradient (ProxDIAG) is deterministic triple loop algorithm whose SFO complexity for finite-sum problem /(22
32
is double loop algorithm and HiBSA 23
SGDA 19,, Stochastic Recursive gna Descent Ascent (SREDA) (55,, and Hybrid Variance- Reduced SGD [40] are more related to our work. SGDA is a single loop algorithm to solve nonconvex- strongly- and canconvex-concarte minimax problems. For nonconvex-strow wereee--tooggyyooneeeee problem, it requires O SFO complexity to find an e-stationary point of ((x). In this paper, we will prove that our method achieves better SFO complexity.
SREDA 25 is double loop algorithm that achieves O(x²c-3 SFO complexity. It accelerates SGDA by using SPIDER, which variance reduction technique and utilizes the newest gradient information
SREDA also involves a separated initialization algorithm called PiSARAH 31 to ensure the convergence. More recently, [ proposed an efficient mirror descent ascent 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, first iteration, we can use either a single sample or a mini-batch to calculate the stochastic gradient. However, SREDA loads mega-batch with size ( periodically (every q iterations) and needs O(c²) gradient oracles at each iteration, which is not practical for large-scale problems. Besides, the maximizer in SREDA a nested loop 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 implement. Moreover, unlike SREDA. our method does not require a separated initialization algorithm to calculate a precise initial value for
7 30
algorithm for nonconvex-strongly-conn
method only requires large batch at the first iteration. Except the
Hybrid Variance-Reduced SGD algorithm also takes ad advantage of hybrid stochastic gradient descent to accelcrate minimax optimization. For example, [4 IT] applied the Hybrid Variance-Reduce SGD minimax problems. More recently, [2] proposed some efficient adaptive gradient descent ascent methods for conconvex-stronnly--oonee minimax optimization based on momentum techniques including Hybrid Variance-Reducel SGD.
2.2 Decentralized Minimax Optimization
At decentralized setting, most minimax algorithms were proposed for convex-concawe problem 17 28). In 22 nonconvexx-onecoccaw algorithm DPPSP was proposed. However, it is not
3

---

gradient- based and the closed-form solution to the subproblem is not ensured in our problem. Hence we will not discuss in this paper. Decentralized Parallel Optimistic Stochastic Gradient (DPOSG) 21 is the first algorithm applicable to a general decentralized minimax problem with theoretical guarantees.
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 OiE (())) 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 in [2 is not satisfied. Actually the assumption of identical data distribution is not satisfied at most decentralized training tasks. Thus, in this paper, do not use this assumption.
More recently, 41 studied decentralized nonconvex minconyex--tronglyy wtw.e-sttoooooonneeeee minimax problems and pro- posed a double loop deterministic Gradient Tracking/Descent- Ascent algorithm which extends the vanilla GDAA to decentralized setting and combines it with gradient tracking. It achieves a gradient complexity of O However, in large-scale machine learning tasks such as deep neural network, generally the full gradient unavailable and the application of deterministic algorithms very Seaiii/g/DDeeeetAsseeeee to stochastic gradient version, the SFO restricted. If we convert Gradient which the same result as SGD in nonconvex optimization. complexity should be least
Under the same conditions, our new algorithm achieves better SFO complexity of (c--))
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(e However, the problem studied in [24] has special form that is linear in In this paper, we focus on general minimax problem. [1] is 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 [ For decentralized algorithms DPOSG, GT/DA, and DM-HSGD, we also discuss whether they can converge on non-identical distributed data.
3 Proposed New Algorithm
3.1 Preliminaries
Before propose our algorithms, we will introduce the notations used in this paper and some important concepts. We use lower case z; and y," to represent the column vector parameters on i-th worker node. We use upper case X, and Y, to represent the n-column matrix formed by x!") and yi respectively, which means X, = [=, [x(") _ .....,,, ,.(1 and Y. = ( v/ ...... vh Column vectors u("), u2 .9.
(2) (i) and (() are gradient estimators used in our algorithms. Upper case U, Vo, Ge
and H, are matrices of which the i-th column is u, (0) 9i and h2 respectively. Lower case with a bar represents the mean vector. Upper case with bar represents the matrix that each column is the mean vector. For example, 34+ = Em xt and X, [Kt, "t,, F:]. We define the optimal maximum value of as:
(t)
y (+) = arg max f(: v), 0 arg max fāt nEY
(4)
wEY
Note that when f is strongly-concave in y, dt is unique. We also define:
6, = | - N. 1|
(5)
Bold number 0 and 1 are n x 1 column vectors that each entry 0 and 1, respectively. For matrices, we use I| to denote Frobenius norm and ||-|12 to denote spectral norm. We use V, and V, , 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 T =1
(6)
We should notice that here matrix W not assumed to be symmetric so that the communication network is not restricted to undirected graph.

---

Algorithm DM-HSGD
Input:
Parameter: stepsize y/,, Mly. weight 3x. Sy, batch size bn. iteration T n-1
mixing matrix W, initial value To Ho, yo yo.
(3) (8)
(6)
9-1
(8)
0,
(6)
h
0
Output: zç. where Ç chosen randomly from 21, T
On i-th node:
2: for = o.l....,T do
3:
if 0 then
4:
9: Fili (6) :..))
Isad = bo
5:
(6) sy.))
ky = bo
6:
else
(i (1) (0)
+ (1 (,) [ c(0))
7:
9:
158
8:
hr
Fi
31 14
(0) (0) (1-
VyFi(=L1
9:
end if
10:
Communicate with neighbors and update gradient estimator as follows
(1)
(i) (j)
11:
Di
9--1)
= Eドー wiy (u + h -
h
di
13:
Communicate with neighbors and update model parameter follows
2++1 = ΣE= way(z, - net )
14:
15:
144
= E== wii(Ut + u (1),
9it1 = Py(v(+4)
(
end for
3.2 Decentralized Minimax Hybrid Stochastic Gradient Descent
In this subsection, we introduce our new Decentralized Minimax Hybrid Stochastic Gradient De- scent (DM-HSGD) algorithm. Our algorithm is single loop minimax algorithm (summarized in Algorithm D which does not contain nested loop structure.
(t) The initial points of diffferent nodes are the same, i.e. x0 2o and yo Pi (3) and h are the gradient estimators with respect to x and y on i-th node.
(i)
and h,") are computed in the same way as
STORM [3]. When = O, we load large batch with size bn calculate the stochastic gradient (lines 4 and 5 in Algorithm]] [ When >> O, we can use either single sample or mini-batch to calculate
the gradient (lines 7 and 8 in Algorithm 1 Di (i)
can also be written
( =. (0) &
(44P)) (7)
which is linear combination of the gradient estimators of stochastic gradient descent (the first part) and SPIDER (the second part). As we have mentioned, SPIDER is variance-reduced method that utilizes the newest gradient information. Thus, estimator Eq. is also called hybrid stochastic gradient descent. the same with 1i()) Then each worker communicates with their neighbors
to compute gradient estimator un and u.") Here we use gradient tracking [5 47 to reduce the consensus error (lines and 12 Algorithm [ We will discuss why gradient tracking is necessary in our method at next subsection. After we obtain (+) and wi") each worker communicates with their neighbors again and updates the model parameters x and y. Here Py(-) represents the projection onto convex set V In the theoretical analysis, we define Y Yo-
3.3 Discussions on STORM and Gradient Tracking
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 not efficient or convenient. From the view of theoretical analysis, normalization projection are likely to cause divergence in decentralized training on non-identical data distribution, which indicated by the following Example Therefore, in the circumstance of this paper, SPIDER will probably not converge to stationary point. Besides,
5

---

SREDA adopts smaller stepsize at the beginning and larger stepsize at the end when ||ey|l becomes small enough. However, when the data distribution is non-identical. | may not tend 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 [8] the consensus error satisfies || - -xell= S
(ee) when the stepsize 1 is (e) and is large enough. The following Example i simple example
to show that this bound is tight and there are cases where consensus error || X F is exactly
θ (n) when the data distribution non-identical. However, according to the analysis of STORM
9t V. De) between the averaged update direction and the correct direction is supposed to satisfy:
3 without gradient tracking, the error term
||all 2 & (1 - -=)]le--11 O(
(8)
Nevertheless, the consensus error |XX, - X Ip is only Onn)) and cannot be as small as O 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 (xx = f((x) + f2(x),, where x = (a. R f(()) and f2(x) 33b
are defined on two different nodes. Let W be the uniform weighted mixing matrix. We can compute
U1 (1, 0) and U/2 (0, v3). The ideal averaged gradient direction is er = (1/2, 3/2.. However, we do normalization before making consensus, the obtained gradient estimator which is deviated from v².
1/22,
Example 2. Suppose there are two sequences {pe} and {qt 3 defined on two different nodes with Po 9o- They are updated by p = Pt na and g++ qt npb each iteration respectively where a and are fixed grudient directions. As data distribution non- aee-identiaal, we have a o b. Assume the mixing matrix is
2/3 1/3
W
1/3
2/3
Then we have
1 P141-9t+1 9t+1 / (pr 01) - (a-b) 31+1 (po 90) -1
?7
1
++
(a
b) = (1
7
1
)0 (b-a)
(9)
3
3
2
3
8=1
Therefore, ro lpt gell la b11.
4 Convergence Analysis
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 E 3), which 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 Fi(z, yi {) is L-smooth, which means there exists constant L such that for any (I., y) and (x', 1/"), we have
FV v) V Fa',', : TT 1211:==-1111+ r11
Assumption 2. (Bounded Variance). The gradient of each component function Folx,, vi is an unbiased estimator of V (((x,)) y) and has bounded variance, iee.
F
ff(xz)))l
+00
Assumption 3. (Lower Bound). The function (--) is lower bounded, i.e., inf, ((x) = tb > -0.
Assumption 4. (Spectral Gap). The doubly stochastic matrix W satisfies || - 11"" 1|2 E [o, 1).
Assumption 5. (Strongly Concave). The function fe(x, y) is pestrongly-concave in y. That is, there exists a constant 0, for any x. y and y', we have
fx v) S f(x, 1/ (2 5¹) 1/1 111 3

---

These are very common and mild assumptions that are frequently assumed in previous works. Assumptions Bnd are also used minimax methods [25 and [9]. Assumption Lis used in [46]
Typically, the spectral gap assumption is stated as W is symmetric and |22| < 1. Xr where
automatically satisfied if the typical spectral gap assumption holds (see Lemma 16 in [6]). Assumption definition of strong concavity.
A1 2 A2 2 2 An are the eigenvalues of W 16, 1& 5T]. Our Assumption
5 is the
In noncommee---trongllycoonee convergence criterion. From Lemma 4.3 in [9], we know ((x) is differentiable and (L+ (L++L)-smoool and y (.) is s-Lipschitz, which means Ily" (m) y" (22)) sillar x2ll for any 21; IRd, Furthermore, we have:
problem, we use e-stationary point of (xx), i.e. [V - as the
( = V.f(Ee 01) + V ff By (xx) = a (at. 0t)
(10)
since VT 01) = O. This criterion broadly used the analysis of nonconvex nonconvex-stroogly--o -treee-strooolyyoocaeeee
minimax optimization [9]. Now we will provide the main theorems of our convergence analysis. Completed proof can be found in the Supplementary Material.
Theorem 1.
Let Assumptions
hold.
When parameters 3n eminfl.ne
By
muin / 1,
20
500K
(1-A)² mine]
m (1,zc)
b0
400
T
4000
Algorithm
2000
500mL
min
I.ne]
(1-
n.ne
7 satisfies
T-1
n
Σ
((0)))) -b=)²² 002 L
V Vafi(zo. 80ll
n
(11)
Corollary 1. When the parameters are defined as Theorem we can see 0 Therefore, if S I), the SFO complexity of Algorithm is O 3) If n >
Et= El ( < ((33)-))
( ) the SFO complexity is n Besides, from the proof of Theorem we can see error 1i y (z+) I|2 is also bounded by the right side of Eq. 11).
Theorem
I is the theoretical result when T is determined by If the number of iteration T is not fixed, we have the following conclusion.
hold. We set the parameters as T 4000k TTo (I (1-X)²
1/3 B2
Theorem 2. Let Assumptions
207
B
1/3 TT77 The
(1-X) Ty
n/2 bo 500KTH
T w2/s,
where we suppose To 2 10n².
20
Then algorithm satisfies
E [ < L(0(20) x²) + 2 L200
1 E
E V fafi (Fo. 1oll
(nT,
To
1 El E|I p vo)l
(12)
To
Corollary 2. From Theorem
we know - E/ S ((ITT)ja7)) + O when
parameters defined above. As suppose To 2 O ), the dominating term in the convergence rate is O( (nToys7)), which indicates the linear speedup of our algorithm.
5
Experiments
5.1 Robust Logistic Regression
We conduct the experiment of decentralized robust logistic regression task the first experi- ment, which was proposed 449 and was also conducted in the related work (55 Given dataset
7

---

{(a;, b,) where E I is the feature and b; E {-1, } is the label, the robust logistic regression
problem is formulated as follows:
12
min max fzz v) Σ (dl(t) V g())
(13)
#ER* yEAr
where is the i-th component of variable (xx)) is the logistic loss function which is defined by
(x) = log(1 + exp(-b;a z)). Vly) is divergence measure defined by V A1 Iny 1
An represents the simplex in R", which means
An - vy E EVERROS 1, Σ 1}
(14)
==1
g(z) is a nonconvex regularization with form g(x) X2 2im1
oz?
Following the experimental
I
settings in 25
49 we A ., A2 0.001 and a 10 our experiment.
Table 2: Descriptions of datasets used in our experiment
Name
a9a
covtype
ijennl
phishing
rev1
w8a
32561
581012
49990
11055 68
20242
49749
d
123
54
22
47236
300
We conduct our experiment on six real-world training datasets "a9a", "ccvtyppe. "ijenn1", "Ij'nn", "phish- "rr""" and "w8a", which can be downloaded from LIBSVM" repository. The description of datasets is listed in Table 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 equipped with 12-core Intel Xeon E5-2620 v3 2.40 GHz processor.
200
801
FM TENTA
CAD EUGG
FRGH
100
0000
6000
gnolicnt crucks
(a)
(b)
(c)
600
TSSTA
500
D0000
300
ginlian sunales (K)
graliin unacko (5)
(d)
(c)
(f)
Figure 1: Results of our decentralized robust logistic regression task. Figure (a) (f) show the value of ((x) with respect to the number of gradient oracles divided by 103. Figure (a), (b), (c), (d), (e) and (f) are experimental results on "a9a". "covtype", "ijennl", "phishing", "rev1" and "w8a" respectively.
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
https://www. csie. ntu. edu. ht//://aaa//bbooooooaaaaaaaaa

---

for solving stochastic problem. We set the number of worker nodes to = 20 and use the ring-based topology as the communication network. For each algorithm, we grid search the learning rates dæ and B/y from {0.1, 0.01, 0.001, 0.0001): J. The mini-batch size is set to 20. The number of iterations in the nested loop for double- algorithms is set to K 5. For DM-HSGID we set the batch size of the first iteration to bn 10000. Bg and 8, are set to 0.01. For SREDA, we set c = 0.1 in the factor TT:] period q = 50 and large batch size S = 1000. We compare the value of (xx) with respect to the number of gradient oracles among different algorithms, which can also be calculated by the projection onto simplex A.. The experimental results are shown in Figure T From the experimental results in Figure]] we can see our new DM-HSGI algorithm converges faster than other baseline algorithms, which verifies the performance of our method.
5.2 Policy Evaluation
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 the Bellman equation [4]. However, traditional TD method, which is probably not true gradient descent method as pointed out in (00 and [77) are shown be unstable in the case of off-police 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 [2), the MSPBE objective function with nonlinear approximation converted into a nonconvex--trroggy-co minimax problem by Fenchel's 's duality. The problem can be formulated as:
min max L(O,w) w) 1 n n.
1 w),
1=
1 w) = (w, (s). + Vo(s)+1)
Vo(s))loo(s))
1 ((""90(()))
(15)
where 8y is state and aj is an action. Rd represents the reward and y E (0, 1) is the discount factor. V is a value function that maps the state space to a real number. / the parameter to estimate the value function. Function go is the gradient of Vo 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. (1))
Following the experimental settings in 42 we use Sarsa K55 generate trajectories of transitions (st Qg s))1,7)) with d features and N 5000 samples on each worker node. We parameterize value function Ve 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 equipped with 12-core Intel Xeon E5-2620 v3 2.40 GHz processor.
0.4
TERTS
SEEA
0.6
MOZIDA
STITDA
200
100 1030
60
300 100
(3)
(a)
(b)
(c)
Figure 2: Results of our policy evaluation task. Figures (a), (b) and (c) show the value of ((8) with
respect to the number of gradient oracles divided by 103. In Figures, (a) d 200, H 50: (b)
d = 300, H = 100; (c) d = 400, H = 200.
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 20. We also use a ring- based topology with uniform weights as the communication network in this task. For each algorithm. we grid search the learning rates arr and fly from {0.1, 0.01. 0.001, 0.0001]. J. The mini-batch size is the nested loop for double-loop algorithms is set to For DM-HSGD, we set the batch size of the first iteration to by 2500. 8g and 33 are set to 0.01. For SREDA, we set ε = 0.1 in the factor T period q = 50 and large batch size S = 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 F
set to 20. The number of iterations
5.
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.
Conclusion
In this paper, we proposed a novel accelerated decentralized minimax algorithm, Decentralized Minimax Hybrid Stochastic Gradient Descent (DM-HSGD), to solve the stochastic nonconvex- strongly-concave minimax optimization problems. We prove that our new method obtains SFO complexity of 0(k²==) which outperforms the existing results in decentralized minimax optimiza- tion and matches state-of-the-an 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 concceee minimax optimization without the strong concavity so that it can solve a broader range of problems including the loss functions that are linear y. We will probably consider the methods that add a perturbation such as Catalyst (50]
in centralized minimax optimization. Our method also achieves
Acknowledgments and Disclosure of Funding
This work was partially supported by NSF IIS 1845666, 1852606, 1838627, 1837956, 1956002, OIA 2040588.
References
[1] Aleksandr Beznosikov, Pavel Dvurechensky. Anastasia Koloskova, Valentin Samokhin, Se- bastian U Stich, and Alexander Gasnikov. Decentralized local stochastic extra-gradient for variational inequalities. arXiv preprint arXiv:2106.08311 2021.
[2] Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. Conference on Learning Theory, 2012.
[3] Ashok Cutkosky and Francesco Orabona. Momentum- based variance reduction in non-convex sgd. Neural Information Processing Systems (NeurIPS), 2019.
[4] Christoph Dann, Gerhard Neumann, and Jan Peters. Policy evaluation with temporal differences: A survey and comparison. Journal of Machine Learning Research, 2014.
[5] Paolo Di Lorenzo and Gesualdo Scutari. Next: In-network nonconvex optimization. JEEE Transactions Signal and Information Processing over Networks, (22::10-136, 2016.
[6] Simon S. Du and Wei Hu. Linear convergence of the primal-dual gradient method for convex- concave saddle point problems without strong convexity. International Conference Artificial Intelligence and Statistics (AISTATS), 2019.
[7] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path integrated differential estimator. Neural Information Processing Systems (NeurIPS), 2018
10

---

[8] Ian J. Goodfellow, Jean Bouget-Abadic Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Neural Information Processing Systems (NeurIPS), 2014.
[9] Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. On stochastic moving-average estimators for non-convex optimization. arXiv preprint 2xXiv:2104118400 2021.
[10] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by two time-scale update rule converge local nash equilibrium. Neural Information Processing Systems (NeurIPS), 2017.
[11] Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth-ordes and first- order momentum methods from mini minimax optimization. Journal of Machine Learning Research, 22:1-70, 2021.
[12] Feihu Huang and Heng Huang. Adagda: Faster adaptive gradient descent ascent methods for minimax optimization. arXiv preprint arXiv:2106. 16101, 2021.
[13] Feihu Huang, Xidong Wu, and Heng Huang. Efficient mirror descent ascent methods for nonsmooth minimax problems. Advances in Neural Information Processing Systems, 34, 2021.
[14] Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. What is local optimality in nonconvex- nonconcave minimax optimization? arXiv:1902.0061882,, 2019.
[15] R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Neural Information Processing Systems (NeurIPS), 2013.
[16] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference Machine Learning, pages
PMLR, 2019.
[17] Alec Koppet, Felicia Y. Jakubiec, and Alejandro Ribeiro. A saddle point algorithm for networked online convex optimization. IEEE Transactions on Signal Processing, 2015.
[18] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Neural Information Processing Systems (NeurIPS), 2017.
[19] Tianyi Lin, Chi Jin, and Michael I. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. arXiv:1906.0033:
2019.
[20] Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite-sample analysis of proximal gradient td algorithms. Conference on Uncertainty in Artificial Intelligence, 2015.
[21] Mingrui Liu, Wei Zhang, Youssef Mrouch, Xiaodong Cui, Jerret Ross, Tianbao Yang, and Payel Das. A decentralized parallel algorithm for training generative adversarial nets. Smooth Games Optimization and Machine Learning Workshop (NeurIPS). 2019.
[22] Weijie Liu, Aryan Mokhtari, Asuman Ozdaglar, Sarath Pattathil, Zebang Shen, and Neng- gan Zheng. A decentralized proximal point-type method for saddle point problems. 1910. 14380v1, 2019.
[23] Songtao Lu, loannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive approximation for one-sided non-convex min-max problems: Algorithms and applications. /xXiv: 2019.
[24] Songtao Lu, Kaiqing Zhang, Tianyi Chen, Tamer Basar, and Lior Horesh. Decentralized policy gradient descent ascent for safe multi-agent reinforcement learning, Association for the Advancement of Artificial Intelligence (AAAI), 2021.
[25] Luo Luo, Haishan Ye, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex-strongee saacooveestronnlyy-cocvvee minimax problems. Neural Information Processing Systems (NeurIPS), 2020.

---

[26] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations (ICIR)) 2018.
[27] Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, Doina Precup, David Silver, and Richard S. Sutton. Convergent lemporal-diffrrnce learning with arbitrary smooth function approximation. Neural Information Processing Systems (NeurIPS), 2010.
[28] David Mateos-Núnez and Jorge Cortés. Distributed subgradient methods for saddle-point problems. IEEE Conference on Decision and Control, 2015.
[29] Arkadi Nemirovski. Prox-method with rate of convergence ((1tt) for variational inequalities with lipschitz continuous monotone operators and smooth convex- convex-concave saddle point problems. SIAM Journal on Optimization, 2004.
[30] Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. arXIv:1703.00102V2, 2017.
[31] Lam M. Nguyen, Katya Scheinberg. and Martin Takáč. Inexact sarah algorithm for stochastic optimization. orXiv:1811.00100 2018.
[32] Maher Nouiched, Maziar Sanjabi, Tianjian Huang, and Jason D. Lee. Solving a class of non- convex min-max games using iterative first order methods. Neural Information Processing Systems (NeurIPS), 2019.
[33] Taoxing Pan, Jun Liu, and Jie Wang. D-spider-sfo: decentralized optimization algorithm with faster convergence rate for nonconvex problems. Association for the Advancement of Artificial Intelligence (AAAI), 2020.
[34] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max opti- mization: Provable algorithms and applications in machine learning. arXiv:/810.02060v3, 2018.
[35] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.
[36] Richard S. Sutton, Hamid Reza Maci, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for temporal-difference learning with linear function approximation. International Conference Machine Learning (ICML), 2009.
[37] Csaba Szepesvári. Algorithms for Reinforcement Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 2010.
[38] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. d: Decentralized training over decentralized data. International Conference on Machine Learning (ICML.,, 2018.
[39] Kiran Koshy Thekumprampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient al- gorithms for smooth minimax optimization. Neural Information Processing Systems (NeurIPS), 2019.
[40] Q. Tran-Dinh, D. Liu, and L.M. Nguyen. Hybrid variance-reduuce sgd algorithms for minimax problems with nonconvex- -inear function. Neural Information Processing Systems (NeurIPS), 2020.
[41] Ioannis Tsaknakis, Mingyi Hong, and Sijia Liu. Decentralized min-max optimization: For- mulations, algorithms and applications in network poisoning attack. In ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pages 5755-5759. IEEF, 2020.
[42] Hoi-To Wai, Mingyi Hong, Zhuoran Yang, Zhaoran Wang, and Kexin Tang. Variance reduced policy evaluation with smooth function approximation. Neural Information Processing Systems (NeurIPS), 2019.
12

---

[43] Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, and Mingyi Hong. Multi-agen, reinforcement learning via double averaging primal-dual optimization. Neural Information Processing Systems (NeurIPS), 2018.
[44] Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost: A class of faster variance-reduced algorithms for nonconvex optimization. arXiv:1810.10690022 2018.
[45] Wenhan Xian, Feihu Huang, and Heng Huang. Communication-effiieeee frank-wolfe algorithm for nonconvex decentralized distributed learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 10405-10413, 2021.
[46] Ran Xin, Usman A. Khan, and Soummya Kar. A hybrid variance-reduced method for decentral- ized stochastic non-convex optimization. arXiv:2102.06752: 2021.
[47] Jinming Xu, Shanying Zhu, Yeng Chai Soh, and Lihua Xie. Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes. In 20/5 54th IEEE Conference on Decision and Control (CDC), pages 2055-2060. IEEE, 2015.
[48] Feng Yan, Shreyas Sundaram. S. Vishwanathan, and Yuan Qi. Distributed autonomous online learning: Regrets and intrinsic privacy-preserving properties. IEEE Transactions on Knowledge and Data Engineering, 2013.
[49] Yan Yan, Yi Xu, Qihang Lin, Lijun Zhang, and Tianbao Yang. Stochastic primal-dual al- gorithms with faster convergence than O(1/VT) for problems without bilinear structure. arXiv:1904.1011 2019.
[50] Junchi Yang, Siqi Zhang, Negar Kiyavash, and Niao He. A catalyst framework for minimax optimization. In NeurIPS, 2020.
[51] Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 2016.
13


Reviews:
[{"review_id": "mdeiHyYS2OZ", "reviewer": "Reviewer_paF7", "summary": "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})$.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contributions of the paper lies on proposing the DM-HSGD algorithm which is constructed by combining two ingredients: 1. the STORM gradient estimator (from [2]), 2. the gradient tracking that is commonly employed in decentralized optimization (e.g., [4]). The resultant algorithm is a single loop algorithm which achieves a state-of-the-art SFO complexity with a linear speed up property with respect to the number of agents in the network. The study also tested the algorithm numerically on several examples. \n\nThe reviewer has the following comments on the current paper in terms of the novelty and the writing quality:\n\n- The algorithm designed merely combines a number of existing techniques to achieve the state-of-the-art complexity result. While the reviewer agrees that this is a new application of the existing techniques to a new optimization problem of interest to the ML community, the paper has failed to illustrate what are the new insights from the application. For example, what are the main challenges in the analysis which are not found in the previous applications? what are the main takeaways from the provided analysis and can the latter be extended to other settings?\n\n- While the main results appear to be accurate (given that they are the applications of existing techniques), there are a number of issues in the writing of the current paper:\n\n-- The reviewer believes that there are missing assumptions regarding the random variable $\\xi$ used in Algorithm 1. Particularly, it should consists of unbiased samples drawn such that $E[ \\nabla_x F_i( x, y, \\xi ) ] = \\nabla f_i( x,y, \\xi)$. In fact, the distribution of $\\xi$ is never defined except for in line 64 where it is mentioned \"$\\xi^{(i)}$ is an index sampled from the local data\", which does not specify the definition of the former. \n\n-- In light of Theorem 1, the statement of Theorem 2 is rather redundant as it is simply a re-cap of the theorem statement of the former. In fact, Corollary 2 suffices to make the point that the proposed algorithm achieves linear speedup.\n\n-- Example 1 and 2 may be presented before the paragraph in line 182 as the two examples are referenced in the main text of Section 3.3. \n\n**----Post-rebuttal----**\n\nThanks very much for the response. Most of my previous concerns have been addressed and I am happy to adjust my score. However, in the final version, the authors shall (i) elaborate on the challenges of their analysis, (2) fix the issues in presentation as pointed out in the above (e.g., combining Theorem 1 & 2). \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There isn't any potential negative societal impact. The limitation/suggestions for improvement have been discussed in the main review above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "hgIpHMQDsq", "reviewer": "Reviewer_85Mh", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: the authors propose a new faster algorithm for non-convex strongly concave minimax problems. The proposed algorithm is a combination of SPIDER, which aims to accelerate non-convex stochastic optimization, and gradient tracking, which aims to accelerate decentralized optimization. \n\nQuality: the paper is technically sound. All results are supported with solid proof.\n\nClarification: the presentation of the paper needs to be improved. For example, the definition of SFO complexity should be explicitly introduced. Some insights and impact of the main theorems should be discussed in Section 4.\n\nSignificance: the proposed algorithm is a natural combination of some existing algorithms and does not shed much new light on this direction. Overall, the contribution seems rather incremental. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are no foreseeable negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "LSRwRF_Kh5V", "reviewer": "Reviewer_fAEx", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper provides an interesting combination of techniques for developing arguments for min-max optimization algorithms in decentalized setting and establish the finite convergence guarantee which is new to my knowledge. \n\nAlthough the paper has a wide range of positive results, it proves these results for a rather restricted class of min-max optimization problems. Specifically, the class in question is nonconvex-strongly-concave min-max problems. \n\nI find this definition to be limited because as far as I understand:\n1) This class of min-max problems does not include nonconvex-linear min-max problems which are quite important in practice. \n2) The examples from policy evaluation and adversarial training are generally not in this class. \n\nI believe these restrictions, if indeed necessary, should be discussed more clearly in the paper. \n\nNevertheless, I still believe that this paper makes some interesting contributions to the community. The algorithm is simple and clearly implementable and the convergence analysis seems correct even though I do not check all the details very carefully. One of the technical drawbacks is that the paper leverages several existing techniques from previous papers, e.g., the two-timescale idea from [15] and the STORM framework from [2]. The authors did a great job in comparing STORM and SPIDER (cf. subsection 3.3). However, it is a bit confused why it is nontrivial to combine two-timescale GDA and STORM. Since the results are somehow unsurprising given prior works, a few more sentences on technical contribution seem necessary.  \n\nDoes this proof carry over to nonconvex-concave min-max problems? A easy approach in my mind is to add a perturbation and reduce nonconvex-concave min-max problems to nonconvex-strongly-concave min-max problems. See the following articles. \n\nT. Lin, C. Jin and M. I. Jordan, \"Near-optimal algorithms for minimax optimization\", COLT 2020. \n\nAlso, the SFO complexity bound of $\\tilde{O}(\\kappa^{1/2}N\\epsilon^{-2})$ can not be achieved by original ProxDIAG and a restarting scheme seems necessary. The above COLT paper and the following article first provide such results in the literature to my knowledge. \n\nD. M. Ostrovskii, A. Lowy, M. Razaviyayn. \"Efficient search of first-order Nash equilibria in nonconvex-concave smooth min-max problems\". SIOPT 2021. \n\nAn additional comment: Assumption 1 imposes Lipschitz gradient condition on stochastic component function and needs to be just justified. Without such condition, it seems difficult to improve $\\epsilon^{-4}$ to $\\epsilon^{-3}$ and note that the analysis for SGDA requires weaker condition than Assumption 1. \n\nOverall the paper performs a nice mathematical analysis of a new min-max optimization algorithms in decentralized setting by leveraging numerous techniques. Although the setting seems to be a bit restrictive and somewhat similar to previous papers, this paper could be a useful starting point for further follow-up work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "BXrzMZN0WXm", "reviewer": "Reviewer_ptf7", "summary": "This paper proposed the Decentralized Minimax Hybrid Stochastic Gradient Descent (DM-MHGD) algorithm for decentralized stochastic nonconvex-strongly concave minimax optimization with non-iid data. This is the first first-order algorithm with convergence guarantee under this seldom studied setting and it has the optimal SFO complexity $\\mathcal{O}(\\kappa^3\\epsilon^{-3})$ to achieve $\\epsilon$-stationary point. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The algorithm and theoretical result are both new for decentralized minimax optimization. The algorithm is a novel combination of techniques including STORM, gradient tracking, and decentralized communication. Related work is adequately cited. \n\nQuality: The submission is technically sound and complete. The claims are well demonstrated by both theoretical analysis and experimental results. The authors did not mention limitations nor future directions. \n\nClarity: The submission is clear and well organized. \n\nSignificance: The results are important as it significantly boosts the convergence decentralized minimax optimization both theoretically and empirically, and thus I think it will likely be cited. \n\nAdvice and questions:\n(1) In eq. (6), you might change the rightmost “)” into “\\big)” or “]” and correspondingly change the left one “(”, which is easier for readers to see the hierarchy of parentheses.\n\n(2) Does $\\xi_t^{(i)}$ denote only one sample in Algorithm 1? You could explain that. \n\n(3) About section 3.3: \n\n(3a) Why do the authors pick up SREDA instead of Acc-MDA, etc. to discuss? Both algorithms achieve the optimal SFO sample complexity for centralized stochastic minimax optimization. \n\n(3b) In “SPIDER will probably not converge to a stationary point”, should “SPIDER” be “SREDA”? \n\n(3c) Iterating Eq. (7) yields that $||e_t||^2\\le (1-\\beta_x)^t ||e_0||^2 + \\mathcal{O}(\\eta_x^4)/\\beta_x$. How can this imply consensus error $||X_t-\\overline{X}_t||_F^2=\\mathcal{O}(\\eta_x^2)$? In addition, both Theorems 1 & 2 use $\\eta_x=\\mathcal{O}(n\\epsilon)$. (Let $\\epsilon<<1/n$ and in Theorem 2 let $T_0=\\epsilon^{-3}/n$.). In this case, is $\\eta_x^2=\\mathcal{O}(n^2\\epsilon^2)$ not small enough? \n\n(3d) In Example 2, you may change the notations $x_t$ and $y_t$ to the ones that are never used, since I ever confused them with the $x_t$ and $y_t$ in Algorithm 1. \n\n(3e) [2] used diminishing learning rate but you used small constant learning rates in terms of $\\epsilon$. Why do you make the change? Is it possible to use larger constant learning rates? Why? You might discuss that. \n\n(4) In Theorem 2, to achieve $\\frac{1}{T}\\sum_{t=0}^{T-1}\\mathbb{E}||\\nabla \\Phi(\\overline{x}_t)||^2\\le \\epsilon^2$, we need the dominating term $\\frac{1}{(nT_0)^{2/3}}=\\mathcal{O}(\\epsilon^2) \\Rightarrow T_0=\\epsilon^{-3}/n$, which can be substituted into the hyperparameters and almost recovers Theorem 1. So I think Theorem 2 is enough and Theorem 1 can be a corollary. \n\n(5) In Corollary 2, “linear speedup of our algorithm” is compared with what? \n\n(6) The theorems guarantee the quality of $x_t$. How about that of $y_t$, e. g., $||y_t-y^*(x_t)||$ or $||\\nabla_y f(x_t, y_t)||$?\n\n(7) Why are GDmax and Acc-MDA in Table 1 excluded from the experiments? I understand that you have already done many experiments and they look sufficient. Just curious. \n\n(8) In experiment 1, you used over 10000 samples but only 20 devices, how are each $f_j(x, y); j=1, \\ldots, 20$ defined? \n\n(9) What are $g_{\\theta}$ and $w$ in eq. (14)? At least you could describe their intuitive meaning. Also, is it single-agent RL? If so, usually there is only one reward function and why does each worker node $i$ need to possess a different $R_i$? \n\n(10) Is $\\Phi(\\cdot)$ in experiment 1 computed from the analytical solution? \n\n(11) You might describe the weights $w_{ij}$ in the ring-based network, such as their values or the distribution that generates them? \n\n(12) You might add the plots of $||\\nabla \\Phi(x_t)||$ for experiments, possibly in appendix, if convenient. \n\n(13) This following paper analyzes the decentralized variational inequality problem, which generalizes decentralized minimax optimization. Using SGD, it achieves higher complexity than $\\mathcal{O}(\\epsilon^{-3})$ in non-monotone case (corresponding to non-convex non-concave minimax optimization). You might add it to related work. \n\nBeznosikov, Aleksandr, et al. \"Decentralized Local Stochastic Extra-Gradient for Variational Inequalities.\" arXiv preprint arXiv:2106.08315 (2021).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are not mentioned. \nBoth the authors and I do not think this theoretical work could have any immediate societal impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "I think this work has no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "About 4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that this paper makes an important contribution by extending recent faster convergence results for nonconvex-strongly concave minimax problems to the decentralized setting and hence I recommend the paper for acceptance. However, I ask the authors to incorporate reviewer suggestions e.g., adding discussion around non-strongly concave problems.
Decision: Accept (Poster)