Venue: NeurIPS 2022 Conference

Reviews:

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: The authors provide a variance reduction algorithm SAGDA for federated min-max optimization which covers Federated SGDA as a special case. They analyze the theoretical convergence and communication costs of these algorithms improving upon existing rates and matching that of federated convex optimization, obtaining the "linear speedup in the number of workers". Further, they compare these algorithms against existing baselines for federated min-max optimization and obtain better performance empirically.

strengths_and_weaknesses: ### Strengths
- The proposed algorithm SAGDA achieves best possible convergence and communication under standard assumptions, and can also handle arbitrary client heterogeneity 
- Using the analysis of SAGDA for Federated SGDA provides better convergence rates over existing analyses.
- The experimental results sufficiently validate the theoretical rates, and SAGDA outperforms existing methods.

### Weaknesses
- Presentation : The presentation of results and their discussion could be improved substantially. Especially for Theorems 1 and 2, most of the math could be simplified and moved to the appendix keeping only $\mathcal{O}(\cdot)$ rates in the main paper. Further, there were several typos in the equations or terms that were not defined( some of them are mentioned in minor issues) . The paper would greatly benefit by improving the presentation.
- Comparison to SCAFFOLD[1] : SAGDA seems to be the extension of SCAFFOLD to min-max optimization. Similar to SCAFFOLD, the analysis technique obtains the best possible rates for the control-variate free version, Federated SGDA. Therefore, I feel it is important to appropriately credit the SCAFFOLD paper. Further, a comparison of SCAFFOLD v/s SAGDA can help establish the difference between variance-reduced methods in convex optimization and min-max optimization.
- Effect of condition number $\kappa$: It would have been interesting to see if SAGDA achieves optimal $\kappa$-dependence in addition to improving the sample and communication complexity.
- Experiments on deep learning tasks: Since min-max optimization is a core component in training GANs, and the performance of variance reduction methods in deep learning is not easy to handle [2], conducting a few toy experiments on deep learning tasks would further improve the paper.

### Minor Issues 
- Proof Idea:  Since the theoretical results of this paper improve upon the existing rates, even for Federated SGDA, highlighting the key ideas in the convergence proof which allow this improvement would help understand what previous analyses missed.
- Extension to different classes of non-convex objectives: The authors only consider nonconvex-PL objectives, while the analysis technique might also be applied to more classes, for instance, those in  Table 1 in [3]). It would also be interesting to see if this has the same effect of mitigating heterogeneity and if it improves upon existing rates.
- Typos and issues with presentation: 
    - In Section 2 (Related Work), Lines 101-104, it is not clear what $K$ is. Later in the paper, it is defined as the number of local steps, but it would be better to mention this here as well.
    - Eq.(2) $\nabla_x f_i(z_{t,i}^j, \xi_{t,i}^k)$ -> $\nabla_x f_i(z_{t,i}^k, \xi_{t,i}^k)$
    - Unnumbered Eq after Line 171, there is an additional $\xi_{t,i}^k$.

### References 
1. Karimireddy, S.P., Kale, S., Mohri, M., Reddi, S., Stich, S. &amp; Suresh, A.T.. (2020). SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. *Proceedings of the 37th International Conference on Machine Learning*, in *Proceedings of Machine Learning Research* 119:5132-5143 Available from https://proceedings.mlr.press/v119/karimireddy20a.html.
2. Defazio, A., & Bottou, L. (2019). On the Ineffectiveness of Variance Reduced Optimization for Deep Learning. In Advances in Neural Information Processing Systems. Curran Associates, Inc..
3. 
Sharma, P., Panda, R., Joshi, G. &amp; Varshney, P.. (2022). Federated Minimax Optimization: Improved Convergence Analyses and Algorithms. *Proceedings of the 39th International Conference on Machine Learning*, in *Proceedings of Machine Learning Research* 162:19683-19730 Available from https://proceedings.mlr.press/v162/sharma22c.html.


questions: - What is the effect of $\kappa$ in the convergence rates and how does it compare to other existing federated min-max algorithms?
- How does SAGDA compare to SCAFFOLD? Is this comparison equivalent to that of comparing GDA methods to GD methods in the centralized setup or does federation change something?
- What are the key ideas in the proof technique which allow for better rates? From what I could understand in the appendix, the authors use the Error-Feedback framework with control variates for the update steps of $x$ and $y$, extending that of SCAFFOLD, but I would like to know if there were additional ideas needed for the proof to go through?

limitations: Most of the suggested improvements have been mentioned in Strengths and Weaknesses.
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: -----After rebuttal

I thank the author for answering my two questions. Given my assessment of the novelty and significance of the paper, I am keeping the score as is.

-----Original review

This paper studies the federated min-max problems which has applications to distributed robust optimization for instance. Two federated versions of the celebrated SGDA algorithm are explored by leveraging standard technique. SAGDA which uses global variance reduction by employing control variates and FSGDA which only employs client sampling and local updates (the latter is an existing method). The convergence of these methods are analyzed for nonconvex-PL min-max problems and it is shown they achieve similar iteration and communication complexity as those of FedAvg for federated minimization problem.
strengths_and_weaknesses: Strength:
1. Improving sample and communication complexity over [14]

Weakness
1. The results while theoretically appleaning does not seems surprising. The proposed algorithm and the proofs seem to be an application of the known techniques in federated and stochastic optimization.
questions: 1. It seems the CD-MAGE+ algorithm achieves a superior sample and communication complexity compared to the result of the present paper. Can you elaborate on the comparison of the two? (answered in rebuttal)

2. The title is misleading as $O(\epsilon^{-2})$ is already achieved by the prior work.  (answered in rebuttal)
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: The paper provides a new algorithm, SAGDA, for federated learning in min-max learning, and proves a theoretical communication complexity guarantee that significantly improves upon previous results (without harming sample complexity). The main idea of SAGDA is to leverage new control variates, and to update a sample of them, based on the variations of the clients’ gradients. In particular, the control variates are used by the clients to update their local models, thereby avoiding model drift. Interestingly, this also allows the authors to remove the bounded gradient dissimilarity assumption, which was needed in prior works. Empirical results also comfort the effectiveness of SAGDA.

The paper also shows the same communication complexity for the standard FSGDA algorithm, by proving that FSGDA is a special case of SAGDA where the control covariates are canceled.

strengths_and_weaknesses: Given the increasing cost of communications in federated learning, the paper provides an original and significant contribution to the design and understanding of efficient federated learning algorithms.

I have however found the paper hard to read, especially as the authors aim to present two variants of SAGDA at once. I would encourage the authors to first focus on only one flavor of SAGDA and to make it as clear as possible for the reader. The other variant may then be briefly discussed in the main paper, and described more thoroughly in the appendix. Moreover, I would have found it useful to also include Equations (2) and (3) directly in the algorithm.

I also feel that too much space is dedicated to the case of FSGDA, which seems less important to me than SAGDA. I would have found it more valuable to dedicate more space to explaining the intuition of SAGDA.

questions: It is not clear to me if the techniques of the paper apply to minimization learning in general (and not just min-max learning). Could SAGDA be easily generalized into SAGD? (in particular, the use of control variates) 

If not, it would be interesting to discuss why not.
limitations: The paper is fully dedicated to machine learning performance, under the assumption that it is desirable to generalize collected data. This clearly raises major societal concerns, if the collected data is undesirably biased, or if it is harmed by poisoning data attacks. Similarly, since it relies on averaging clients’ inputs, SAGDA is arbitrarily manipulable by malicious clients. On the Internet, such malicious clients are ubiquitous.

I believe that the authors have a responsibility to highlight this, and to warn against the use of such algorithms in environments where the quality of the data is not sufficiently guaranteed, or when the clients are not all extremely trustworthy. A discussion on the need for developing Byzantine-resilient variants of SAGDA would be ethically productive.
review_title: null

Meta-review: metareview: While the reviewers have shown some concerns regarding presentations, the paper has substantial contribution. It is suggested that the authors improve their presentation taking the suggestions from the reviewers: this paper will gain from clarifying the contributions. Overall the novelty of min-max optimization coupled with interesting results warrants acceptance. 
confidence: Certain
Decision: Accept