Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 

Quality: the paper is technically sound. All results are supported with solid proof.

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

Significance: 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. 
limitations_and_societal_impact: There are no foreseeable negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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})$.
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. 

The reviewer has the following comments on the current paper in terms of the novelty and the writing quality:

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

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

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

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

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

**----Post-rebuttal----**

Thanks 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). 

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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 

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

I find this definition to be limited because as far as I understand:
1) This class of min-max problems does not include nonconvex-linear min-max problems which are quite important in practice. 
2) The examples from policy evaluation and adversarial training are generally not in this class. 

I believe these restrictions, if indeed necessary, should be discussed more clearly in the paper. 

Nevertheless, 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.  

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

T. Lin, C. Jin and M. I. Jordan, "Near-optimal algorithms for minimax optimization", COLT 2020. 

Also, 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. 

D. M. Ostrovskii, A. Lowy, M. Razaviyayn. "Efficient search of first-order Nash equilibria in nonconvex-concave smooth min-max problems". SIOPT 2021. 

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

Overall 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.
limitations_and_societal_impact: See above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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. 

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

Clarity: The submission is clear and well organized. 

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

Advice and questions:
(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.

(2) Does $\xi_t^{(i)}$ denote only one sample in Algorithm 1? You could explain that. 

(3) About section 3.3: 

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

(3b) In “SPIDER will probably not converge to a stationary point”, should “SPIDER” be “SREDA”? 

(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? 

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

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

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

(5) In Corollary 2, “linear speedup of our algorithm” is compared with what? 

(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)||$?

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

(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? 

(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$? 

(10) Is $\Phi(\cdot)$ in experiment 1 computed from the analytical solution? 

(11) You might describe the weights $w_{ij}$ in the ring-based network, such as their values or the distribution that generates them? 

(12) You might add the plots of $||\nabla \Phi(x_t)||$ for experiments, possibly in appendix, if convenient. 

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

Beznosikov, Aleksandr, et al. "Decentralized Local Stochastic Extra-Gradient for Variational Inequalities." arXiv preprint arXiv:2106.08315 (2021).

limitations_and_societal_impact: Limitations are not mentioned. 
Both the authors and I do not think this theoretical work could have any immediate societal impact.
review_title: null

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)