Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper focuses on decentralized local stochastic extra-gradient for variational inequalities.
This paper uses extra-gradient as the main tool to solve saddle point problems which satisfy variational inequalities.
The results of this paper are not surprise but still have their own value.
strengths_and_weaknesses: The techniques in this paper are regular and the results of this paper are not surprise.
But the results of this paper have their own value.
questions: No.
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposed a decentralized extra-gradient method with intermittent communications to solve distributed variational inequalities problem, and one important scenario is federated GAN training or federated adversarial training. They consider the setting where clients are connected with a decentralized network and clients only synchronize with its neighborhood. They provide the convergence rate for strongly monotone, monotone and non-monotone cases. The rates make sense. They also provide experiments validating their algorithms' effectiveness and efficiency.
strengths_and_weaknesses: Strengths:
As far as I know, this paper is the first to analyze the extragradient method, a celebrated algorithm in minimax/variational inequality optimization, in decentralized and intermittent communication settings. Due to the rise of federated GAN and adversarial robust training, distributed minimax problems received increasing attention from optimization and ML community. Hence, the theoretical results in this paper have its own value.

Weakness:
My main concern is that the authors assume unbounded parameter domain, but in the monotone setting, we have to assume the parameters are bounded to get a meaningful convergence bound, i.e., in equation (7), they have to assume max_{z,z'}||z-z' || is bounded. I understand that adding projection may collapse existing proof, but assuming bounded domain without projection operator looks unreasonable to me.
questions: Please refer to weakness part.
limitations: This is pure theory paper so I did not see any negative societal impact.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper studies distributed stochastic variational inequalities (VIs) problems on unbounded domains while the data on different devices might be heterogeneous (non-IID). The authors propose a new algorithm that (1) the gossip matrix is drawn from some distribution in very communication and (2) multiple updates are made on every device between two communications. The authors prove that the proposed method speedups in all strong-monotone, monotone, and non-monotone cases. Comprehensive experiments show that the proposed method have faster speeds in solving distributed stochastic saddle-point problems (SPP), e.g., to training Deep Generative Adversarial Networks (GANs).
strengths_and_weaknesses: Pros:
+ The idea makes sense. Multiple diffusions on devices between two communications can certainly speedups the training.
+ The experiments are nice for a theory-intensive paper. The results are in agreement with the theory.
+ The proofs are comprehensive and clear. I do not find any major flaws.
+ The authors provide the source code of the experiments.

Cons:
- The motivations are quite straightforward. I am concerned it is not novel. Please clarify the difference and advantages from the following papers:

A. H. Sayed, Diffusion adaptation over networks, vol. 3, pp. 323-453, 2014.

A. H. Sayed, S. Y. Tu, J. Chen, et al, Diffusion strategies for adaption and learning over networks: an examination of distributed strategies and network behavior, IEEE Signal Processing Maganize, vol. 30, no. 3, pp. 155-171, 2013.

S. Y. Xie, L. Guo, Analysis of distributed adaptive filters based on diffusion strategies over sensor networks, IEEE Transactions on Automatic Control, vol. 63, no. 11, pp. 3643-3648, 2018.

S.A. Alghunaim, K. Yuan, A unified and refined convergence analysis for non-convex decentralized learning. IEEE Transactions on Signal Processing. 2022.

A.S. Matveev, M. Almodarresi, R. Ortega, A. Pyrkin, S. Xie. Diffusion-based Distributed Parameter Estimation Through Directed Graphs with Switching Topology: Application of Dynamic Regressor Extension and Mixing. IEEE Transactions on Automatic Control. 2021.

- The paper seems written in a rush. Many typos exist.
questions: Please clarify the difference and advantages from the following papers:

A. H. Sayed, Diffusion adaptation over networks, vol. 3, pp. 323-453, 2014.

A. H. Sayed, S. Y. Tu, J. Chen, et al, Diffusion strategies for adaption and learning over networks: an examination of distributed strategies and network behavior, IEEE Signal Processing Maganize, vol. 30, no. 3, pp. 155-171, 2013.

S. Y. Xie, L. Guo, Analysis of distributed adaptive filters based on diffusion strategies over sensor networks, IEEE Transactions on Automatic Control, vol. 63, no. 11, pp. 3643-3648, 2018.

S.A. Alghunaim, K. Yuan, A unified and refined convergence analysis for non-convex decentralized learning. IEEE Transactions on Signal Processing. 2022.

A.S. Matveev, M. Almodarresi, R. Ortega, A. Pyrkin, S. Xie. Diffusion-based Distributed Parameter Estimation Through Directed Graphs with Switching Topology: Application of Dynamic Regressor Extension and Mixing. IEEE Transactions on Automatic Control. 2021.
limitations: The authors did not discuss the limitations and potential negative societal impact of their work, while no significant issues are identified.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this work, the authors address the problem of solving minty variational inequality in decentralized optimization. They extend extra-gradient to this setup and prove convergence results under different assumptions on the operator (strong monotonicity, monotonicity, existence of Minty solution) and a weak assumption on the network topology (expected multi-step contraction). These theoretical results are further complemented by experiments on a syntactic problem and GANs.
strengths_and_weaknesses: This work nicely complements the existing literature by providing an exhaustive analysis on decentralized extra-gradient for solving VI problems. On the positive side, the assumption made in this work about the network allows us to take into account various communication schemes. Moreover, their convergence rates feature explicit dependence on different constants of the problem and the network. 

On the downside, the proposed algorithm can only partially handle the case of non-monotone operators with minty solutions. In fact, both $\sigma$, the standard deviation of the noise, and $D$, the variability among nodes appear in the bounds (9) and (10) in terms that do not depend on $K$. Even if $D=0$, one still needs to increase the batch size to get better accuracy. This is probably a problem that already needs to be addressed in the centralized case.

I also feel that it is not clear what the authors want to convey through section 5.2. We can probably also get the same types of results with other decentralized algorithms that are mentioned in related work.
questions: 1. In (7) and (8) the supremum is outside the expectation while for stochastic VIs it is more common to have supremum inside the expectation and there is a standard process to achieve this in the centralized case. Actually, it is more meaningful to have the supremum inside the expectation because the gap function should be used as a measure for every realization. Therefore, I am wondering if we can get a result of this kind here or if there is any technical difficulty that makes the authors to present results like this.

2. In the experiments, the authors observe linear convergence in the bilinear case when there is no noise. I understand why this should be the case in the centralized case. However, in the decentralized case with data heterogeneity, the presence of network error should prevent the iterates from converging, as we see in the strongly monotone setup. Could you please explain why this is not observed in the bilinear case?
limitations: Fine
review_title: null

Meta-review: metareview: The paper studies decentralized local stochastic extra-gradient for variational inequalities.
An extra-gradient method is developed for this problem. Theoretical results are established and complemented by simulations. While there were some concerns about the novelty of the work in the initial review, the authors adequately addressed these comments in their response. While a number of typos were present in the paper, I believe that these can be addressed as a minor revision in the final version. I do encourage the authors to carefully proofread their camera ready submission. The work is of interest to a part of the conference audience and should be accepted. 
confidence: Certain
Decision: Accept