Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper considers a federated minimax optimization problem with compact constraints. The contents of this paper are threefold. First, under assumptions with respect to the maximization variable, the authors upper bound the stochastic minimax objective with the empirical minimax objective. They also provide an upper bound of Rademacher complexity of the stochastic minimax model. Second, a Federated (Fed) Gradient Descent Ascent (GDA) method based on Gradient Tracking (GT) (FedGDA-GT) is proposed. Under the assumption that the minimax problem is strongly convex and strongly concave, and other assumptions, the linear convergence of the generated sequence is proved. In the last part, experiments on quadratic minimax problems and robust linear regression problems are conducted.
strengths_and_weaknesses: Strength: 
1. The upper bound of Rademacher complexity for the general federated minimax model is new. 
2. A gradient tracking skill is applied in the local updates of the proposed method. Thanks to this, in the deterministic case, the proposed method has sequential linear convergence under some assumptions.

Weakness: 
1.	From my understanding, the upper bound of the Rademacher complexity can be obtained following similar assumptions and proofs in Section 4 [13] of this paper.  
2.	In Section 4, the assumptions that the objective is strongly convex strongly concave, that the objective is twice continuously differentiable, and that the problem has at least an interior stationary point, are too strong. In centralized minimax problems, twice continuously differentiability is not usually assumed, but there are still methods that achieve linear convergence. Thus, the twice differentiability is not necessary and limits the scope of the applications of the convergence results. In addition, the assumption that there exists an interior stationary point is hard to check for many minimax models. Thanks to these ideal assumptions, the proofs for the linear convergence of the proposed method are classical and simple. In my opinion, these assumptions lack convincing application examples.
3.	The models in the experiments part are relatively simple, compared to those in [13]. No experiments are conducted on widely tested datasets such as Adult dataset, Fashion MNIST, and Language models. Since this paper claims to generalize the results in [13], I think experiments that apply the proposed method to the models in [13] should be conducted and compared.

questions: 1.	In the experimental part, are the models satisfy the assumptions in section 4? Do they have the unique interior optimal solutions? If yes, does it mean the considered quadratic problems have closed forms?
2.	What’s the complexity that counts the inner iterations for the proposed method?
3.	What is the exact form of M(y) that is used as a key element in the upper bound of the Rademacher complexity? Can it be infinity when taking the maximum over y? If yes, does the upper bound in Corollary 2 and Lemma 2 become infinity?

limitations: 1.	The proposed algorithm needs to communicate with the server twice in each iteration, which can be inefficient. 
2.	In applications of federated learning, the data size is huge and the proposed method requires computing the full gradient in each step. Thus, this method is expensive to apply. A stochastic variant of this method and its convergence analysis are not considered. 
3.	The assumptions for the linear convergence of the proposed method are too strong to satisfy or check for the learning model. See more explanation in "strength and weakness" part 2.
review_title: null

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: The paper is focused on minimax problems. First some generalization bounds are proposed via Rademacher complexity for the empirical minimax problem. Then, the paper focuses on federated learning for strongly-convex-strongly-concave minimax problems. A new algorithm  is proposed for which the convergence rate is provided.
strengths_and_weaknesses: Strengths

This paper investigates a federated learning approach for minimax problems. An interesting new algorithm is introduced, but which lacks a clear presentation. 

Weaknesses

Overall, the paper lacks a clear focus and clear interpretations of the proposed algoritm and its main results in comparison with the state of the art. 

1. The motivation behind the mathematical derivations in Section 3 are not clear. Some examples of its application could be provided. 

2. The equation (11) does not seem to be accurate as 1/T^3 would mean a very fast convergence much better than 1/T. From [25], it seems that a rate convergence of O(1/(nT)) is achieved by local SGDA, but that the number of communications is either O(n) in the homogeneous setting or sqrt(nT) communication rounds in the heterogeneous setting. 

3. Some further interpretation could be provided behind the result in Proposition 1. Especially, why this result implies that SGDA with a fixed point step-size cannot converge. 

4. The discussion regarding local vs global minimax points right before section 4.2 is not clear especially since the objective is assumed to be strongly-convex-strongly-concave as per Assumption 1. This should be clarified. 

5. The description of the novel proposed approach lacks in clarity. Some details behind the major differences between the SGDA and the proposed method FedGDA-GT should be provided after introducing the algorithm. It seems that some additional global information that is broadcasted by the server is used. 

6. A more detailed discussion about the precise convergence rate and communication rounds behind the main result in Theorem 2 and in comparison to those of [25] should be provided before the Experimental section. 

The main convergence result is not interpreted well enough and it is not clear why the proposed algorithm is superior than SGDA. Indeed, the convergence rate seems to be linear which is also the case for SGDA. 

Regarding the communication rounds required by the proposed method, there is no clear discussion in the main body of the paper. 

In the abstract the authors mention log(1/epsilon) communication rounds to reach an epsilon precision but this is nowhere to be found in the main body of the paper. In the conclusion it is mentioned log(1/epsilon) time, but this is very vague and unclear. 

Comments post-rebuttal:

The authors have answered in a satisfactory manner to most raised comments. However, the paper still requires major changes to be accepted. Thus, the initial score is raised to 5. 

questions: Qu1: How many communication rounds and what is the convergence rate of the proposed method compared with the results in [25] ? Using the same notations for clarity. Are the additional broadcasts from the server in FedGDA-GT accounted for ? 

Qu2: What is the link between Section 3 presenting the Rademacher complexity and Section 4 presenting the proposed federated learning algorithm?

limitations: The limitatios of the propsoed method do not seem to be addressed in this paper. 

Regarding negative societal impact, this work is fairly theoretical and there are no straightforward negative impact to be reported.
review_title: null

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: The paper characterizes the fixed-point properties of local SGDA with no gradient noise with multiple local steps and constant stepsize. Then FedGDA-GT, an improved Federated Gradient Descent Ascent method based on Gradient Tracking, is proposed. It is shown that FedGDA-GT converges linearly with O(\log\frac 1\epsilon) rounds of communication under smmoth strongly-convex-strongly-concave setting. Besides, the paper also analyzes the generalization of empirical minimax learning under distributed setting.
strengths_and_weaknesses: Pros: This paper characterizes the fixed-point condition for local SGDA with multiple local steps with constant stepsize. The condition is not necessarily equivalent to the optimality condition, demonstrating local SGDA under this configuration is not necessarilty convergent to saddle point. The authors also provide an example to illustrate this fact.
	Under the same setting, FedGDA-GT can be shown to exhibit linear rate, which is faster than the sublinear rate of local SGDA. The gradient tracking is used to eliminate the client drift. The numerical experiment also provides evidence on the empirical benefit of FedGDA-GT. 

Cons: The linear convergence rate of FedGDA-GT is derived under the setting without gradient noise. However, this is a distinct (and easier) scenario than the typical one in the federated learning framework where we only have access to the estimator of the gradient f_i. Whether the properties derived in this paper, i.e., linear rate with constant stepsize, still holds is unknown. Diminishing stepsize could be necessary to guarantee covergence and only sublinear rate is expected.
The paper also studies the generalization bounds on minimaxx learning problems in the distributed setting using Rademacher complexity. But its connection with other parts of the paper is unclear.

questions: 1.	Is it possible to prove the convegence guarantee of FedGDA-GT with graident noise? Does linear convergence with constant stepsize still hold?
2.	What is the connection between section 3 and other sections despite the distributed minimax setting?

limitations: NA.
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: This paper studies the problem of min-max optimization in federated settings. The paper derives a Rademacher complexity bound for this setting, and then proceeds to analyze the local SGDA method in federated contexts. The paper shows that when using fixed learning rates and multiple local optimization steps, local SGDA does not converge to minimax optimal points (and give explicit examples of this in the quadratic setting in the appendix). The paper then proposes a method, FedGDA-GT, and shows that in certain settings, FedGDA-GT converges linearly to a minimax optimal point. Finally, the paper concludes with experiments comparing local SGDA and FedGDA-GT on synthetic data that show that FedGDA-GT can converge faster and to a point with lower loss.
strengths_and_weaknesses: I will preface this section with a note that I am not an expert in minimax optimization. Thus, I have taken the paper at face value in some of its discussion of related works on distributed minimax optimization.

That being said, I think this is a generally well-written paper that occupies an important point in a vein of works on federated optimization that the authors may not be aware of (as I will discuss below). The paper has 3 primary components (generalization bounds, convergence bounds, and empirical evaluation), and I have separated this discussion accordingly.

### Section 3 - Generalization bounds

The section gives a digestible introduction to Rademacher complexity, and gives corresponding generalization bounds for distributed minimax optimization that extend those of [Mohri et al., 2019]. The proofs seem sound and are interpretable.

That being said, this section is (in my opinion) one of the weaker portions of the paper. It feels disjointed from the rest of the work, especially as I found no observations that come out of the Rademacher complexity that influence any of the subsequent sections. For example, there is no facet of Corollary 1 that seems to influence the design of FedGDA-GT. Rather, the rest of the work is quite focused on the question of whether you converge to minimax optimal points of the training loss, so I'm not certain what the reader should take away from this section.

### Section 4 - Convergence bounds

In contrast to the above, this is the strongest part of the work. The observation that Local SGDA may not converge to minimax optimal points is a valuable one, and fits in nicely with a line of prior work in federated optimization (more on that below). Similarly, the FedGDA-GT method is an intuitively useful method that has nice convergence guarantees in certain settings. The proofs all seem sound, and the entire section gives a nice picture of federated minimax optimization.

The primary weakness of this section is something that is easily remedied, which will in turn make the paper stronger. This paper gives a minimax mirror to an important line of work in risk-minimization federated optimization that should be emphasized. Prior works, including [1, 2, 3] have all explored variations on a central theme: That Federated Averaging (FedAvg) does not converge to critical points of the empirical loss when using $K > 1$ local optimization steps. In that sense, Proposition 1 of this work is effectively a minimax version of this result, and I believe should be discussed as such.

Analogously, the solution to use gradient tracking kinds of techniques to remedy this issue is one that has appeared in multiple parts of the literature. Perhaps most fittingly, I would urge the authors to consider [4]. This work proposes a kind of gradient tracking version of FedAvg that has linear convergence in deterministic settings. In fact, the method FedGDA-GT is intuitively a minimax version of FedLin from [4]. The two methods share a very common framework, and have similar convergence results. Basically, I believe this work has done a good job of translating relevant work on objective inconsistency in federated learning to minimax settings, and I would like to see more of a discussion of this.

One other weakness of this section that is worth noting: It is unclear from Theorem 2 whether setting $K > 1$ in Algorithm 2 is useful.  In [4], the authors actually construct settings where $K = 1$ is optimal (by way of a lower bound). This is potentially a useful thing to add to this work if possible. Finally, I will note that while I would also love to see extensions to non-strongly-convex-strongly-concave settings, I do not think this is strictly necessary for acceptance.

### Section 5 - Empirical results

As mentioned above, these results are all on synthetic data. As such they succeed in illustrating the relevant properties of FedGDA-GT and Local SGDA that the authors want to illustrate. Moreover, I appreciated the authors' attempts to explore how heterogeneity affects the methods (and in particular, the observation that the methods are comparable in some settings).

While explorations on less synthetic data would improve the work, I do not think this is strictly necessary given the theoretical focus of the work.

### Review Summary

All in all, I think this is a good work that opens the way for many other analyses of federated minimax optimization. The strongest parts of this work are in Section 4. I would personally recommend the authors open this section up a bit more and include more about details about how it relates to federated risk-minimization works (eg. [1, 2, 3, 4]). In particular how this work presents an extension of these works to minimax settings. This related work also gives various avenues that could improve this work, including extensions to more general loss functions and possible lower bounds. While the generalization bounds and empirical evaluation are nice, they are not the primary draw of the work.

#### References

[1] Malinovskiy et al, "From local SGD to local fixed-point methods for federated learning." ICML 2020.

[2] Pathak & Wainwright, "FedSplit: An algorithmic framework for fast federated optimization." NeurIPS 2020.

[3] Charles & Konecny, " Convergence and accuracy trade-offs in federated learning and meta-learning." AISTATS 2021

[4] Mitra et al., "Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients." NeurIPS 2021.

# Post author-feedback comments

I have read the other reviews of this work, and all the author comments. I still believe this paper should be accepted. While there are some discussions about the assumptions made regarding the minimax setting (eg. whether the strongly-convex-strongly-concave is too strong), I think that this misses the core contributions of the work:

1) A proof that Local SGDA with fixed learning rates will not converge to minimax-optimal points in federated settings when $K > 1$. Note that in particular, the linear convergence of Local SGDA only holds in non-federated settings: This work demonstrates that in federated settings it may not converge at all.

2) A new method that does converge linearly to minimax-optimal points in federated settings when $K > 1$ even with fixed learning rates.

As I mention in my review above, this mirrors a lot of theoretically interesting and provocative work on FL minimization over the last few years, but brings it to the realm of minimax optimization. I believe that this warrants publication (especially as the proofs are intuitive, easy to read, and correct). While the current organization of the work (with Rademacher complexity bounds coming first) may obscure these contributions slightly, this is eminently fixable.

Finally, I wish to note my strong belief that this is primarily a theoretical work, and should be reviewed accordingly. I think the experiments help validate the theory, and do not need to go beyond that. Similarly, I think that questions of the actual utility of this method in practical settings miss the point: This serves as a theoretical jumping off point for understanding why minimax optimization methods fail in FL settings, and how we can possibly remedy that. There is plenty of precedent in the literature for works of exactly that nature (including [1, 2, 3, 4] above).

I have increased my score to a 7 accordingly.
questions: Some of these are distillations of questions from the section above.

*   Can Assumption 1 be relaxed at all?
*   Is there any benefit theoretically to setting $K > 1$ in Theorem 2?
*   Can you shed light on the form of $\rho(\eta)$ in Theorem 2?
*   In Proposition 1, can you concretize the trade-off between model accuracy and communication-efficiency you mention at the beginning of Section 4? For example, [1, 2] show that increasing $K$ for FedAvg does exactly this in quadratic settings.

Minor comments and questions:

*   The discussion before Figure 2(a) seems to suggest that the left plot is $\alpha = 0$, but the caption says $\alpha = 1$.
*   The bound quoted in (11) is incomplete. The dominant part of the convergence rate seems to be $O(c/\mu n T)$ for some $c$.
*   In Section 5.1, you seem to use the same learning rate for different methods and different values of $K$. Why is this valid?
*   In the empirical evaluations of Section 5.2, you use the same learning rate $\eta$ for different methods "for the sake of fair comparisons." Given that the methods are different, why is this fair?


#### References

[1] Malinovskiy et al, "From local SGD to local fixed-point methods for federated learning." ICML 2020.

[2] Charles & Konecny, " Convergence and accuracy trade-offs in federated learning and meta-learning." AISTATS 2021
limitations: There are no potential negative societal impacts that I can discern.
review_title: null

Meta-review: metareview: This paper has three main contributions: (1) a generalization bound for learning in adversarial learning frameworks such as GANs based on Rademacher complexity, (2) a proof that local SGDA with constant stepsize does not converge for these problems in federated settings and therefore does not achieve linear convergence, and (3) a new method which circumvents these issues.

Overall, the consensus was that result (1) was both somewhat underwhelming and also seemed somewhat disjointed from the paper. However, results (2) and (3) are compelling, and will be of interest to the federated learning community. This is especially true after the authors removed some of the technical assumptions that they required in the first version of the paper. The updated version of the paper could still use some cleaning up and/or reorganizing, however, I think that overall the paper is above the bar for acceptance.
confidence: Less certain
Decision: Accept