Multiplayer Federated Learning: Reaching Equilibrium with Less Communications

Secondly, given that this FL setting is now a multiplayer game where the clients are not from the same entity, expecting competitors to follow the same PEARL-SGD algorithm seems unrealistic. Any client might want to deviate from PEARL-SGD to take advantage over the competitors, or, if the collaboration does not give good results for one of the clients (since Nash equilibriums are not necessarly good for all), the client can simply sabotage the learning.

While I find the MpFL setting very intriguing, PEARL-SGD seems incomplete without considering potential adversarial behavior from clients (or perhaps I am missing real-world cases where it cannot be the case?). At present, I struggle to see how this setting or algorithm aligns with a practical problem. Could the authors comment on this?

We find the reviewer’s second question on the possibility of players’ adversarial behavior thoughtful and interesting. However, we emphasize the following two points.

First, players are unlikely to have a strong motivation to deviate from collaborative learning if the multiplayer game and its equilibrium are designed properly. One significant example of this is the well-known Personalized Federated Learning (PFL) setup [7], where each client seeks a local model that is better suited for their own local dataset; under suitable reformulation, PFL can be viewed as an instance of MpFL.

Second, the problem of defiant clients can be raised to other FL or PFL setups as well. Even in these well-established setups, there is no guarantee that every iteration of an FL algorithm (or communication round) provides monotonic performance improvement for each client, and a client may refuse to comply at any time. A proper resolution to this question will already constitute a separate paper (see, e.g., [8]). While we will be excited to see such exploration in future work, at the current stage where we are introducing the foundational concept, we believe having idealized assumptions should not be considered to be a critical flaw.

We hope that our response has resolved the reviewer’s concerns. If we have successfully addressed your concerns, please consider raising your mark. If you believe this is not the case, please let us know so that we have a chance to respond.

[1] A. P. Jacob, Y. Shen, G. Farina and J. Andreas. The Consensus Game: Language Model Generation via Equilibrium Search. ICLR, 2024.

[2] Z. Li and Zhengtao Ding. Distributed Nash Equilibrium Searching via Fixed-Time Consensus-Based Algorithms. American Control Conference, 2019.

[3] M. Ye and Guoqiang Hu. Distributed Nash Equilibrium Seeking by A Consensus Based Approach. IEEE Transactions on Automatic Control, 2017.

[4] M. Ye. Game Design and Analysis for Price-Based Demand Response: An Aggregate Game Approach. IEEE Transactions on Cybernetics, 2017.

[5] F. Salehisadaghiani and L. Pavel. Distributed Nash equilibrium seeking: A gossip-based algorithm. Automatica, 2016.

[6] D. Kalyva and H. E. Psillakis. Distributed control of a mobile robot multi-agent system for Nash equilibrium seeking with sampled neighbor information. Automatica, 2024.

[7] A. Fallah, A. Mokhtari and A. Ozdaglar. Personalized Federated Learning: A Meta-Learning Approach. NeurIPS, 2020.

[8] K. Donahue and J. Kleinberg. Model-sharing Games: Analyzing Federated Learning Under Voluntary Participation. AAAI, 2021.

We thank the reviewer for viewing our work as interesting and acknowledging the potential of MpFL. Below, we respond to each point mentioned by the reviewer.

The problem is technically interesting, but I am not convinced by the real-world motivations ... specifically, the idea that banks (or pharmaceutical companies) would collaborate and learn together as competitors while maintaining their competitive edge. If these problems are indeed real, the proposed solution may not be well-suited.

First, I find it unlikely that competing companies would be willing to share learning and potentially benefit a competitor, especially without guarantees that the collaboration would be mutually beneficial or at least better than learning alone.

Indeed, as the reviewer points out, Nash equilibrium may not always be good. However, this is a matter of how the setup is designed; if the objective functions $f_i$ are appropriately chosen, each player can be incentivized to collaborate with others to find Nash equilibrium, even if they are in competing relationships.

The reviewer’s first question asks what such situations are specifically where participating in the game will benefit all (potentially competing) players.

Let us first highlight the generality of MpFL. n-player games exist in several scenarios (please see the applications mentioned in our paper), where the goal is to reach an equilibrium. In all of these scenarios, most existing ML approaches assume that everything is centralized (they do not count how expensive communication between players is). In our work via the MpFL setting, we precisely handle this problem, providing for the first time an algorithm (PEARL - SGD) that reaches an equilibrium with less communication between players. We believe this is a more practical scenario than existing approaches for finding equilibrium n-player games, where communications occur in every iteration. As such, MpFL can be useful for any application that involves formulating the problem as an n-player game.

Having said the above, we acknowledge that our assumptions and setting are mainly theoretical (the focus of our work), and in our experiment, we have not directly formulated/implemented large-scale applications. We want our work to establish the first convergence guarantees in this setting and open the door for further evaluations (theoretical and practical).

On the application side let us share here our visions on what we think our setting and algorithm would be particularly useful in the future.

• There is a large body of literature on distributed game theory (for reaching Nash equilibrium), targeting applications in economy, energy consumption control, optical networks, robotics, etc. [2,3,4,5,6] where Nash equilibria are regarded as optimized states. While these works are relatively classical (small-scale) and communication complexity has not been considered a significant concern, we believe that with the progress of n-player games in ML scenarios, relevant large-scale applications will emerge (large number of players), and communication-efficient algorithms like our PEARL-SGD can be particularly valuable in these scenarios.
• Recent works on language models have reported that the equilibrium of a certain two-player game corresponds to more consistent, accurate output to factual questions [1]. This provides empirical evidence that output consistency can be associated with game-theoretic equilibrium. We believe this idea could be extended and utilized for the joint training of multiple language models.
• We speculate that in the future, the same idea (as we mentioned in our paper) could be incorporated into banks (or pharmaceutical companies), which would collaborate and learn together as competitors while maintaining their competitive edge. In our opinion, this is potentially the more far-fetched application for which we do not have a clear indicator at this stage. We can easily rephrase this part to better reflect our comment above.

Dear Reviewer xjkH,

We would like to provide a reminder that the pdf update deadline is approaching, and ask the reviewer whether they will have any changes to the original evaluation given our rebuttal. In our rebuttal, we provided clarifications on (1) The motivation of MpFL with the discussion on applications, and (2) The problem of defiant clients (players). We also update our pdf file to reflect the reviewer’s comment. We replace the previous discussion with far-fetched examples (banks/pharmaceutical companies) with a more general vision on game-theoretic applications. Please see the parts highlighted in red.

Please let us know if you have any other questions.

If we have properly successfully addressed your concerns, please consider raising the rating beyond the borderline scores to provide support for our work.

Thank you,

The authors.

We thank the reviewer for the time and effort spent evaluating our work. Thanks for finding our paper well-written and easy to read, understanding the importance of MpFL, the new setting we proposed in our work, and for highlighting that it has the potential to open up opportunities for future research.

Below, we provide responses to each point mentioned by the reviewer.

1. The paper states that each agent only has access to its own local objective function while in the algorithm it has been shown that the master server collects and distributed all actions to all agents … Therefore, the statement is contradicting.

Thanks for the question. However, the statements are not contradicting. Accessing the local objective function $f_i$ and accessing the local action $x^i$ are conceptually different things. We stated that the $i$-th player can only compute $f_i$ and its gradient, not that the players should have no access to other players’ actions $x^{-i}$.

Question 1. How the privacy of each agent's objective function is maintained if the master server is distributing all actions?

As we mentioned before, $f_i$ is not directly accessed by players other than $i$. This is unrelated to having (occasional) access to $x^i$.

2. The experiment part is limited. Only the relative error is shown, which is not easy for readers to tell the benefits of the proposed method in the multiplayers environment. For example, can this algorithm make all agents satisfy their learning results? This can be shown by comparing the proposed method with FL using the local losses and the overall losses. It would also be better if some real datasets can be tested.

We emphasize that in MpFL, there is generally no “overall loss”. The goal of MpFL is finding a game-theoretic equilibrium $\mathbf{x}_\star$ defined by equation (1) in the paper (lines 153-154), and this is not necessarily associated with minimizing a specific quantity. Plotting each local loss value ($f_i$) could be visually appealing, but it would not indicate convergence to $\mathbf{x}_\star$ on its own.

We have run an additional experiment on a robot control setup (presented in the general response), which has been previously considered in distributed game theory literature. If the reviewer believes that this enhances the paper, we will update the manuscript with it. ​

​Question 2. Can you include comparisons of individual agent performance using local losses to show that all agents achieve their desired learning objectives or can you provide a metric or visualization that shows how well each agent's objectives are satisfied.

Plotting each local loss value ($f_i$) would not indicate convergence to the equilibrium $\mathbf{x_\star}$, which is the goal of MpFL. The value of each $f_i$ is not necessarily globally minimized at the solution $\mathbf{x_\star}$. This is why we use the (scaled) distance to $\mathbf{x}_\star$ as our performance metric.

Additionally, running (classical) FL algorithms using local losses does not make sense in the first place. In the MpFL setup, even the dimension $d_i$ of each player’s action $x^i$ could be all different, while in most FL settings all local models $x^i$ share the same dimensionality. Majority of existing FL algorithms, which are variants of Local SGD, use averaging of local models $x^i$, but this is not possible in our setup because the players’ actions generally have different dimensions.

3. Writing needs to be polished. A thorough review of the abbreviation usage throughout the paper is needed …

We will carefully review and revise the usage of abbreviations. Thank you for pointing this out.

Question 3. Consider adding experiments with real-world datasets to demonstrate practical applicability.

Again, please refer to our additional experiment on a robot control setup (presented in the general response), which has been previously considered in distributed game theory literature.

Thanks again for the review and time invested in evaluating our work. If we have successfully addressed your concerns, please consider raising your mark. If you believe this is not the case, please let us know so that we have a chance to respond.

Dear Reviewer Bqbe,

We would like to provide a reminder that the pdf update deadline is approaching, and ask the reviewer whether our second rebuttal would change their original evaluation. In our second rebuttal, (1) we demonstrate through a numerical experiment what the plots of $f_i$ could show us, and (2) provide clarification on why Local SGD is not a valid MpFL algorithm.

We also update our pdf file to reflect the reviewer’s suggestion (please see Appendix D of the updated pdf).

If we have properly successfully addressed your concerns, please consider raising the rating beyond the borderline scores to provide support for our work.

Thank you,

The authors.

We thank the reviewer for the time and effort spent evaluating our work. Below, we provide responses to each point mentioned by the reviewer.

• Unclear definition of MpFL:
  • Despite the introduction and discussion in Section 2.1, there is no rigorous definition of what MpFL is, and how that is different from FL.
    • Provide a concise, formal definition of MpFL, perhaps in a dedicated subsection or as a numbered definition ...

We thank the reviewer for their comment on improving the presentation of our work.

However, let us highlight that in Section 2.1, we provide all the details of the problem setup and precise formulation of what we call MpFL. Precisely, in lines 123-126, we provide a high-level conceptual definition of the MpFL. To restate it here with a slight rewording: MpFL is a setup where multiple players/clients (e.g., mobile devices or whole organizations) play an n-player game with the goal of reaching equilibrium, and they communicate with each other via a central server (e.g., service provider).

The setting is simple as an idea but, to the best of our knowledge, underexplored in the literature (we are not aware of any paper focusing on this). As mentioned in Section 2.1, MpFL is the setting where we have an n-player game with the players being clients in a distributed network. In this scenario (which is more realistic than the scenario of prior works focusing on n-player games and assuming all the information is centralized), communication-efficient algorithms are required to reach an equilibrium point. Such methods currently do not exist in the literature, and this is what our paper focuses on – proposing and analyzing the PEARL-SGD method that precisely achieves that (reaching equilibrium with less communication compared to its non-local counterpart).

Also through lines 144-168 and Figure 1, we provide all the precise technical information needed for understanding the framework. Let us provide the following list of bullet points (restatement of what Section 2.1 already explains), for a clearer demonstration of the characteristics and details of the MpFL setup:

• Each player $i$ has an objective function $f_i(x^i; x^{-i})$ (depending both on their own action $x^i$ and on others’ actions $x^{-i}$), representing their interest.
• Each $f_i$ is given as the expectation of $f_{i, \xi^i}$ where $\xi^i$ represents the distribution of $i$-th player’s local data.
• The goal of the MpFL is to reach an equilibrium (defined by equation (1) in the paper).
• Players other than the $i$-th player do not have access and cannot compute $f_i$ and its gradient.
• Player $i$ can only update one’s own action $x^i$.
• The updated values of $(x^1, … ,x^n)$ are shared among players via communication steps. In a communication step, the master node (server/service provider) collects the up-to-date values of $x^1, \dots , x^n$, concatenates them into $\mathbf{x}$, and sends $\mathbf{x}$ to each player.
• Reducing the communication complexity (number of communications required to find an approximate equilibrium) is the primary concern of the setup.

The definition of FL should be in the preliminaries before introducing MpFL. Instead, it is delayed to Section 2.2.

This is a personal preference. In our viewpoint, first starting from the multiplayer game and then explaining its federated learning aspect (MpFL) should be prioritized, and the concept of MpFL can be established clearly by itself, without necessarily focusing on classical FL first. However, as we believe it is also important to clarify connections with prior works, in Section 2.2, we provide detailed definitions of FL and Federated Min-max formulations, and how they are different from our approach.

Discuss how the motivation lead to this formulation. Why communicating only once in a while? How does this falls into the federated learning framework?

Our lines 127-134 explain why we consider the problem of reducing communications important. Specifically, we are interested in scenarios of modern large-scale, collaborative machine learning among multiple players that are clients within a network with limited communication bandwidth or geographically dispersed organizations (for which the communication step is the most significant computational bottleneck).

The newly proposed MpFL setup has similarities with the classical cross-device federated learning as it shares important characteristics of FL (see also our discussion of the connections of the two literatures): 1) The clients could potentially be a very large number of mobile or IoT devices (not small size like a classical distributed setting) 2) clients/players have heterogeneous datasets (which are kept private by each player/client), and 3) communication is the primary bottleneck.

Discuss the problem formulation itself. Does the problem exists a solution? Is it unique? Does the solution depends on the order of the optimizations of different players?

The existence of a solution is a part of theoretical assumptions, and the assumption (QSM) implies its uniqueness. The notion of a solution (equilibrium) is not affected by the order of players, as we do not assume any particular hierarchical structure in the game. The solution is simply characterized as zero of the joint gradient operator $\mathbf{F}$. We will more clearly explain these points in the revision.

Grammatical errors, typos L22: less communications -> "less communication" or "fewer communications"

We remove the plural and use “less communication”. Thank you.

Why is "communicating through a central server" important in MpFL? Instead of concatenate the strategies of all players via a central server in the aggregation round, can we just assume each player can observe other players' strategies?

Having a trustable service provider (master node) taking charge of communication steps is the standard setup considered in most FL works, and we have naturally taken this as a starting point. We agree that it will be an interesting future direction to study the decentralized setup where there is no master node and the players communicate directly with each other (this is a direction we are currently exploring). This scenario is more complicated as the network topology will be an important factor in the convergence analysis. At the stage of introducing the new concept of MpFL, starting with the distributed scenario would be a strong enough first step that could open many doors for future exploration.

L167: What does the additional subscript $\xi^i$ in $f_{i,xi^i}$ mean? Please explicitly define the notation $f_{i,xi^i}$ and its relationship to $f_i$.

We have defined this in lines 165-167. It represents a dataset of the $i$-th player, following the distribution $\mathcal{D}_i$.

Thanks again for the review and time invested in evaluating our work. We believe that all weaknesses the reviewer mentioned are related to clarifying our setting and algorithm, and improving the presentation of the paper. If we have successfully addressed your concerns, please consider raising your mark. If you believe this is not the case, please let us know so that we have a chance to respond.

Dear Reviewer pJvm,

We would like to provide a reminder that the pdf update deadline is approaching, and ask the reviewer whether they will have any changes to the original evaluation given our rebuttal. In our rebuttal, we provided clarifications on (1) The problem definition of MpFL, (2) Order of presentation, (3) Motivation of MpFL and why it is considered as FL, (4) Assumption on the solution, (5) Existence of a central server and (6) Definition of $f_{i,\xi^i}$. We also update our pdf file to reflect the changes the reviewer suggested (please see the parts highlighted in red).

Please let us know if you have any other questions.

If we have properly successfully addressed your concerns, please consider raising the rating beyond the borderline scores to provide support for our work.

Thank you,

The authors.

We thank Reviewer 8Mga for the constructive and thoughtful feedback. We thank the reviewer for highlighting all the strengths of our work, mentioning that the paper is generally well-written and accessible, the theoretical results are presented in a straightforward and precise way, and the experiments show a comprehensive verification of our findings. Thanks also for pointing out that the topic of our work is timely and compelling.

Below, we address the concerns raised as weaknesses by the reviewer.

1. The extended introduction is comprehensive, yet it would benefit from including some key recent contributions…

We have a discussion on client drift, which, in our case, we name player-drift (as the clients are players in our setting) after the results of our main theorems. Even if exploring player drift in more detail is beyond the scope of our work, we can include a discussion of the above papers there.

2. While Table 1 is quite informative, it would be even more helpful if it included a direct comparison with previous approaches…

Thank you for the suggestion. This will be a nice idea, but there are no previous works and algorithms that solve the more advanced problem we propose. Introducing the new concept of MpFL is one of the main contributions of our work.

Note that in MpFL, even the dimension $d_i$ of each player’s action $x^i$ could be all different, unlike most FL settings where all local models $x^i$ share the same dimensionality. The majority of existing FL algorithms, which are variants of Local SGD, use averaging of local models $x^i$, while in our setup, averaging is absurd because the players’ actions have different dimensions and may correspond to different semantic meanings. In short, it is conceptually invalid to directly compare PEARL-SGD with existing FL algorithms, both theoretically and experimentally, as they are designed for fundamentally different setups.

3. The assumptions are clearly presented; however, the problem statement itself could be more rigorously defined. A more precise formulation would enhance the clarity and accessibility of the paper.

Thanks for the suggestion. Let us highlight that in Section 2.1, we provide all the details of the problem setup and precise formulation of what we call MpFL.

The setting is simple as an idea but, to the best of our knowledge, underexplored in the literature (we are not aware of any paper focusing on this). As mentioned in section 2.1, MpFL is the setting where we have an n-player game with the players being clients in a distributed network. In this scenario (which is more realistic than the scenario of prior works focusing on n-player games and assuming all the information is centralized), communication-efficient algorithms are required to reach an equilibrium point. Such methods currently do not exist in the literature, and this is what our paper focuses on – proposing and analyzing the PEARL-SGD method that precisely achieves this goal (reaching equilibrium with less communication compared to its non-local counterpart).

4. In Algorithm 1, the aggregation step is somewhat underexplained. Furthermore, it’s not emphasized that the server needs to send all client models to each participant…

There is no aggregation step (averaging step) in PEARL-SGD. This is the main difference between the method and MpFL compared to the standard FL setting and methods like Local SGD. We explained the exact details of the method in the first two paragraphs of Section 3 before our main pseudocode. As you can see, the task of the server in our setting is to concatenate the strategies sent to the server by all clients (every few iterations - the local aspect of our approach). Even in this scenario, communication between clients and servers is the bottleneck, and this is what PEARL-SGD handles, using local computations and communicating only occasionally.

5. In Theorems 3.3 and 3.4, with constant step size, the step size depends not only on $\ell$, $\tau$, and $L_{\mathrm{max}}$ but also on $\kappa$ … potentially weakening the practical applicability of the result.

Indeed, our theorems require the knowledge of $\mu$ to obtain the convergence guarantees. While this is a valid point, theoretical results usually have their value behind the scenes by providing a general understanding of how the algorithm behaves. We believe that even if the theoretical step-size for PEARL-SGD didn’t have $\kappa$-dependency, in practice, one would rarely select step-sizes based on the theory, e.g., by estimating Lipschitz constants. Rather, one will try out multiple values from a step-size grid and empirically choose the best-performing one. This is why we included the experiments of Figure 2(a,b), 4(a,b) — to simulate such a scenario. We speculate that in the future, using potentially different analyses one might be able to remove the dependence on $\mu$ (similar to what was done in the classical FL literature, where one of the earliest papers [1] featured $\mu$ dependence in the step-size, which was later removed).

[1] S. U. Stich. Local SGD converges fast and communicates little. ICLR, 2019.

6. In Theorem 3.3, … seems to contradict the claim in the abstract: “We theoretically analyze PEARL-SGD under different step-size selections and prove that it reaches an equilibrium with less communication compared to its non-local counterpart.” Could you provide clarification on this point?

We thank the reviewer for the very careful reading. Stating the conclusion first, the clarification is: In the deterministic case, indeed, PEARL-SGD is not more effective than its non-local version when using the tight theoretical step-sizes (as Figures 3(c), 4(c) indicate). However, in the stochastic case, PEARL-SGD does achieve the desired accuracy level (distance to equilibrium) within fewer communication rounds. The intuition is as follows. As the reviewer notices, the effect of using $\tau>1$ and $\gamma=O(1/\ell\tau)$ cancel out each other within the term $(1-\gamma\tau\mu\zeta)^R$. However, in the stochastic case, there is an additional “neighborhood term” proportional to $\gamma\sigma^2$. With $\gamma$ being $\tau$ times smaller, this neighborhood term becomes smaller as well. Hence, PEARL-SGD reaches closer to the equilibrium within the same number of communication rounds $R$. In other words, PEARL-SGD requires fewer communication rounds to achieve the same level of accuracy. Corollary 3.5 can be seen as a formalization of this idea.

7. The analysis is conducted under the assumption of quasi-strong monotonicity. Would it be feasible to relax this assumption or perhaps even the convexity assumption? An exploration of less stringent assumptions could broaden the applicability of the findings.

Yes, we agree with the reviewer that exploration beyond our current setting of assumption will be valuable, but this could be done in follow-up works. In our opinion, this should not be seen as a weakness of our work. Not all machine learning papers should primarily focus on general non-convex scenarios. With our work, we provide the setting of MpFL for the first time, and we propose PEARL-SGD as the first algorithm for solving it. Yes, indeed, our analysis focuses on convex scenarios, but this was by design. A new concept should be understood well in favorable scenarios first before moving to a more complicated (e.g., non-convex, non-smooth) setting for which it is not clear how even the non-distributed methods work yet.

Having said the above, let us emphasize the following two points:

Equilibrium search in games (which our work focuses on) is considered a much more difficult problem class compared to minimization problems (which most classical FL works deal with). Unlike in minimization problems, in game optimization, gradient descent does not even converge to the local optimum without (quasi-)strong monotonicity. Removing or weakening our quasi-strong monotonicity and playerwise convexity assumptions would indeed be an interesting and important future direction, but it will require additional non-trivial techniques (e.g., smoothed GDA [2], two-timescale extragradient [3,4]).

In addition, a number of existing theoretical works on classical FL and Local SGD have been done with the strong convexity assumption. [1,5,6] We believe providing the analysis under seemingly strong assumptions is a meaningful first step, providing intuition that could help the development of future results.

Please note that the primary purpose of this work is to provide an initial theory of MpFL and set up the conceptual foundations rather than expanding the scope of the theory to the most general level.

8. In the plots with theoretical parameter settings, the performance lines appear nearly identical. This suggests that the claim that the proposed method outperforms non-local approaches may not hold as strongly as suggested …

Our response to Question 6 (the one that questioned our claim on less communication) answers this question as well. While we demonstrated the deterministic case separately to provide a clearer picture, we believe the main application scenarios for MpFL and PEARL-SGD will be the stochastic setups. For such setups, PEARL-SGD has both theoretical/practical gains in terms of the communication cost.

9. The experiments are conducted primarily on quadratic games. It would be valuable to include additional experiments with more practical objective functions to better represent real-world applications.

We have run an additional experiment on robot control setups (presented in the general response), which has been previously considered in distributed game theory literature. If the reviewer believes that this could enhance the paper, we will update the manuscript with it.

10. I am not deeply specialized in this field, but the analysis appears to share similarities with the methods in the following papers … Could you please clarify the unique elements of the technical analysis in your proofs ...

There are some high-level similarities between these works and our work in the sense that they are all related to client/player drift or the error terms caused by local updates. However, as we explained in our response to Question 2 (on including comparison with previous approaches into Table 1), none of the previous FL works can handle the general game-theoretical setup that our MpFL addresses. In particular, the PEARL-SGD algorithm and our analysis do not use averaging, and consequently, the techniques for bounding the player drift significantly differ from prior work. For instance, Lemma 3.8 is one of the key ingredients of our analysis, and we are not aware of the case where similar arguments were used in the FL literature.

[2] J. Yang, A. Orvieto, A. Lucchi and N. He. Faster single-loop algorithms for minimax optimization without strong concavity. AISTATS, 2022.

[3] J. Diakonikolas, C. Daskalakis and M. I. Jordan. Efficient methods for structured nonconvex-nonconcave min-max optimization. AISTATS, 2021.

[4] S. Lee and D. Kim. Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems, NeurIPS, 2021.

[5] A. Khaled, K. Mishchenko and P. Richtarik. Tighter theory for local SGD on identical and heterogeneous data. AISTATS, 2020.

[6] K. Mishchenko, G. Malinovsky, S. Stich and P. Richtarik. ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally! ICML, 2022.

Thanks again for the review and time invested in evaluating our work. We believe all weaknesses the reviewer mentioned are related to clarifying our setting, algorithm and analysis, which we do above.

If you agree that we managed to address all issues, please consider raising your mark. If you believe this is not the case, please let us know so that we have a chance to respond.

Dear Reviewer 8Mga,

We would like to provide a reminder that the pdf update deadline is approaching, and ask the reviewer whether they will have any changes to the original evaluation given our rebuttal. In our rebuttal, we provided clarifications on Weakness 2 (Why existing FL techniques are inapplicable to MpFL setups), Weakness 3 (MpFL problem definition), Weakness 4 (Communication step in PEARL-SGD), Weakness 5 (Step-size dependence on $\mu$), Weaknesses 6&8 (Communication cost reduction in theory/experiments), Weakness 7 (Theoretical assumptions), Weakness 9 (Additional experiments) and Weakness 10 (Unique elements of our theoretical contributions). We also update our pdf file to reflect the suggested changes: Weakness 1 (Additional references) and Weakness 9 (please see the parts highlighted in red).

Please let us know if you have any other questions.

If we have properly successfully addressed your concerns, please consider raising the rating to provide support for our work.

Thank you,

The authors.

We thank the reviewer for viewing MpFL as a new and interesting problem. Below, we provide responses to each point mentioned by the reviewer.

Although PEAR-SGD is new, I don't see much novelty of it. It is not surprising that the individual model can converge fast by knowing all others' model unless my understanding is wrong.

PEARL-SGD is the first local method for solving multiplayer federated learning (MpFL) problems. Any prior works that have the network's clients as players of a game with the goal of finding an equilibrium do not use local steps. This highlights the importance and novelty of PEARL-SGD.

Let us also highlight that it is not the case that PEARL-SGD converges fast because it utilizes others’ models as additional information. In the MpFL setup, “knowing other’s model” (the communication step where individual models/actions are collected and distributed by the master node) is already necessary even for running the baseline algorithm (non-local method: distributed SGDA). This should not be viewed as a limitation of PEARL-SGD. Rather, it is the other way around; PEARL-SGD using local steps reduces the communication rounds for reaching an equilibrium, i.e., each player/client requires fewer communications with others’ model information (other players).

For the novelty part, the usage of local gradient steps itself is a very common and widely used concept in the FL literature. However, please note that we are introducing the new, game-theoretic FL setup (MpFL), and we are providing, for the first time, the proper way of using local gradient steps to work for this new MpFL setup. In this regard, we believe that PEARL-SGD and its analysis are indeed novel.

Below, through a sub-response, we provide a detailed explanation of why the baseline algorithm already requires communication between the players in MpFL. We would like to know whether the reviewer would maintain this evaluation, even when given the explanation.

The analysis only focused on convex and its variations. There is no analysis on general non-convex objective functions.

Yes, this is true. However we do not believe that this is a weakness of our work. In our opinion, not all machine learning papers should primarily focus on deep learning scenarios. With our work, we provide for the first time the setting of multiplayer federated learning, and proposed PEARL-SGD as an algorithm for solving it. Yes, indeed, our analysis focuses on convex scenarios, but this was by design. A new concept should be understood well in favorable scenarios first before moving to a more complicated (e.g., non-convex, non-smooth) setting for which it is not clear how even the non-distributed methods work yet.

Having said the above, let us emphasize the following two points:

1. Equilibrium search in games (which our work focuses on) is considered a much more difficult problem class compared to minimization problems (which most classical FL works deal with). Unlike in minimization problems, in game optimization, gradient descent does not even converge to the local optimum without (quasi-)strong monotonicity. Removing or weakening our quasi-strong monotonicity and playerwise convexity assumptions would indeed be an interesting and important future direction, but it will require additional non-trivial techniques (e.g., smoothed GDA [6], two-timescale extragradient [1,2]).

2. In addition, a number of existing theoretical work on classical FL and Local SGD have been done with the strong convexity assumption [3,4,5]. We believe providing the analysis under seemingly strong assumptions is a meaningful first step, providing intuition that could help the development of future results.

Please note that the primary purpose of this work is to provide an initial theory of MpFL and set up the conceptual foundations rather than expanding the scope of the theory to the most general level.

[1] J. Diakonikolas, C. Daskalakis, and M. I. Jordan. Efficient methods for structured nonconvex-nonconcave min-max optimization. AISTATS, 2021.

[2] S. Lee and D. Kim. Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems, NeurIPS, 2021.

[3] S. U. Stich. Local SGD converges fast and communicates little. ICLR, 2019.

[4] A. Khaled, K. Mishchenko, and P. Richtarik. Tighter theory for local SGD on identical and heterogeneous data. AISTATS, 2020.

[5] K. Mishchenko, G. Malinovsky, S. Stich, and P. Richtarik. ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally! ICML, 2022.

[6] J. Yang, A. Orvieto, A. Lucchi and N. He. Faster single-loop algorithms for minimax optimization without strong concavity. AISTATS, 2022.

Since the master server needs to distribute all the individual models in each round, I didn't see how this can save communication cost.

As we mentioned above, the baseline algorithm for our setup (not using local steps) requires the master node to collect and distribute all individual models in every iteration. PEARL-SGD performs this communication step more rarely (reduced by the factor of $\tau$ times), and reaches the neighborhood of equilibrium using fewer numbers of such communication steps, as shown in Corollary 3.5 and Theorem 3.6.

In our paper, we precisely explain scenarios where our method improves the complexity of communication for solving n-player games (reaching equilibrium with less communication). This is one of the main contributions of our work.

In the experiments, I suggest the authors could compare the proposed algorithm with other federated learning learning algorithm in terms of convergence rate, accuracy and communication cost.

We strongly emphasize that, to the best of our knowledge, no previous FL algorithms can handle the general game-theoretic setup that our MpFL addresses. As such there is no other algorithm to compare with that actually solves our multiplayer game setting.

Note that in MpFL, even the dimension $d_i$ of each player’s action $x^i$ could be all different, unlike the most FL settings where all local models $x^i$ share the same dimensionality. Majority of existing FL algorithms, which are variants of Local SGD, use averaging of local models $x^i$, while in our setup, averaging is absurd because the players’ actions have different dimensions and may correspond to different semantic meanings. Therefore, it is conceptually not valid to apply existing FL techniques to our experiment setups of Section 4.

Thanks again for the review and time invested in evaluating our work. Reading your comments, we believe that all pointed weaknesses could be resolved by clarifying our setting and algorithms, as we do above. If you agree that we managed to address all issues, please consider raising your mark. If you believe this is not the case, please let us know so that we have a chance to respond.

Dear Reviewer DFsy,

We would like to provide a reminder that the pdf update deadline is approaching, and ask the reviewer whether they will have any changes to the original evaluation given our rebuttal. In our rebuttal, we provided clarifications on (1) Novelty and importance of PEARL-SGD, (2) Theoretical assumptions, (3) How reduction of communication cost occurs, and (4) Why existing FL techniques are inapplicable to MpFL setups.

Please let us know if you have any other questions.

If we have properly successfully addressed your concerns, please consider raising the rating beyond the borderline scores to provide support for our work.

Thank you,

The authors.

Some reviewers raised concerns about the lack of experiments based on real-world applications. To address this, we have conducted an additional experiment on a real-world problem, and this has been added to the paper, in Appendix D (page 29).

Here, we consider a distributed formation control problem of mobile robots from [1]. Each robot in this multi-agent system has its own objective, which depends on the positions $x^i$ (corresponding to action/strategy in the formulation of our paper) of robots. Specifically, the objective (cost) function of robot $i$ is given by $J_{i1} + J_{i2}$, where $J_{i1} = \frac{c_i}{2}\| x^i - x^i_\mathrm{anc}\|^2$ represents the cost penalizing the distance of agent $i$ from some anchor point $x^i_{anc}$ and $J_{i2} = \frac{d_i}{2} \sum_{j = 1}^N \| x^i - x^j - h_{ij}\|^2$ is the cost associated with the relative distances between all the robots. The control problem finds a (Nash) equilibrium $\mathbf{x_\star} = ( x^1_\star, \dots, x^n_\star )$ of the n-player game, which is the concatenation of all robots' position vectors ensuring that each robot stays close to its desired location $x^i_\mathrm{anc}$ while maintaining appropriate relative displacement from other robots. We follow the experiment setup within [1] to choose the values of $c_i, d_i, x^i_\mathrm{anc}, h_{ij}$, with $n=5$. We add Gaussian noise to the gradients to simulate stochasticity. In this setup, all our theoretical assumptions are satisfied. Further details are provided in the updated Appendix D of the paper.

We implement PEARL-SGD for this problem, using synchronization intervals $\tau = 1, 2, 4, 5, 8, 20$ and the theoretical step-size $\gamma = \frac{1}{\ell \tau + L_{\max}(\tau -1) \sqrt{\kappa}}$. The attached plot shows that PEARL-SGD achieves better accuracy within a given number of communication rounds with larger values of $\tau$. This highlights the benefit of using local update steps in solving real-data problems formulated as multiplayer games.

We address the remaining concerns through our individual responses to each reviewer.

[1] D. Kalyva and H. E. Psillakis. Distributed control of a mobile robot multi-agent system for Nash equilibrium seeking with sampled neighbor information. Automatica, 2024.