Multiplayer Federated Learning: Reaching Equilibrium with Less Communication
Authors: TaeHo Yoon
Sayantan Choudhury
Nicolas Loizou
Venue: NeurIPS 2025 poster ()
Keywords: Federated Learning
Game theory
Multiplayer games
Convergence guarantees
Communication-efficient Algorithms
Local SGD
Primary area: optimization
TL;DR: Proposes the novel framework of Multiplayer Federated Learning and analyzes the communication-efficient Per-Player Local SGD (PEARL-SGD).

Abstract: Traditional Federated Learning (FL) approaches assume collaborative clients with aligned objectives working towards a shared global model. However, in many real-world scenarios, clients act as rational players with individual objectives and strategic behaviors, a concept that existing FL frameworks are not equipped to adequately address. To bridge this gap, we introduce *Multiplayer Federated Learning (MpFL)*, a novel framework that models the clients in the FL environment as players in a game-theoretic context, aiming to reach an equilibrium. In this scenario, each player tries to optimize their own utility function, which may not align with the collective goal. Within MpFL, we propose *Per-Player Local Stochastic Gradient Descent (PEARL-SGD)*, an algorithm in which each player/client performs local updates independently and periodically communicates with other players. We theoretically analyze PEARL-SGD and prove that it reaches a neighborhood of equilibrium with less communication in the stochastic setup compared to its non-local counterpart. Finally, we verify our theoretical findings through numerical experiments.

Multiplayer Federated Learning: Reaching Equilibrium with Less Communication
TaeHo Yoon
Sayantan Choudhury Nicolas Loizou
Department of Applied Mathematics & Statistics
Mathematical Institute for Data Science
Johns Hopkins University mloizou] edu
{tyoon?, schoudh8, schoun7,
Abstract
Traditional Federated Learning (FL) approaches assume collaborative clients with aligned objectives working toward a shared global model. However, in many real-world scenarios, clients act as rational players with individual objectives and strategic behavior, a concept that existing FL frameworks are not equipped to ade- quately address. To bridge this gap, we introduce Multiplayer Federated Learning (MpFL), a novel framework that models the clients in the FL environment as players a game- theoretcc context, aiming reach an equilibrium. In this scenario, each player tries to optimize their own utility function, which may not align with the collective goal. Within MpFL., we propose Per-Player Local Stochastic Gradient Descent (PEARL-SGD), an algorithm in which each player/client performs local updates independently and periodically communicates with other players. We theoretically analyze PEARL-SGD and prove that it reaches neighborhood of equilibrium with less communication the stochastic setting compared to its non- local counterpart. Finally, we verify our theory through numerical experiments.
Introduction
Federated Learning (FL) has emerged as powerful collaborative learning paradigm where multiple clients jointly train a machine learning model without sharing their local data. In the classical FL setting, central server coordinates multiple clients (e.g., mobile edge devices) collaboratively learn a shared global model without exchanging their own training data [59, 66, 94, 77]. In this scenario, each client performs local computations its private data and periodically communicates model updates to the server, which aggregates them to update the global model. This collaborative approach has been successfully applied in various domains, including natural language processing [83, 52], computer vision [84, 76], and healthcare [5. 135].
Despite their success, traditional FL frameworks rely on the key assumption that all participants fully cooperative and share aligned objectives, collectively working to optimize the performance of shared global model (e.g., minimizing the average of individual loss functions). This assumption overlooks situations where participants have individual objectives or competitive interests that may not align with the collective goal. A variety of such scenarios have been extensively considered in the game theory literature, including Cournot competition in economics [2], optical networks [108], electricity markets [116), energy consumption control in smart grid [1 [141], mobile robot control [60]. These applications have yet to be associated with Fl., presenting an underexplored opportunity to bridge game theory and FL for more robust and realistic frameworks.
To address these limitations of classical FL approaches, we propose novel framework, Multiplayer Federated Learning (MpFL), which models the FL process game among rational players with individual utility functions. In MpFL, each participant considered a player who aims to optimize
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

their own objective while interacting strategically with other players in the network via a central server. This game-theoretic perspective acknowledges that participants may their conflicting goals, or be unwilling to fully cooperate. By incorporating these dynamics, MpFl. provides a more realistic and flexible foundation for FL. in competitive and heterogeneous environments.
have
In the literature, there are multiple strategies that aim to incorporate personalization into classical FL, including multi-task learning [124, 98], transfer learning [64], and mixing of the local and global models [49, 50J, to name a few. However, to the best of our knowledge, none of them can formulate the behavior of the clients/players in non-cooperative environment. This gap is precisely what Multiplayer Federated Learning (MpFL) aims to address.
1.1 Main contributions
Introducing Multiplayer Federated Learning, We develop novel framework of Multiplayer Federated Learning (MpFL), which models the FL process as a game among rational players with individual utility functions. In MpFL, each client within the FL environment is viewed as a player the game, and their local models are viewed as their actions. Each player constantly adjusts their model (action) to optimize their own objective function, and the MpFL framework aims for each player to reach to a Nash equilibrium by collaboratively training their model under the orchestration of central server (e.g., service provider), while keeping the training data decentralized. That is, MpFL extends the scope of FL to scenarios where clients are allowed to have more general, diversified, possibly competing objectives.
Design and analysis of Per-Player Local SGD. To handle the Multiplayer Federated Learning framework, we introduce Per-Player Local SGD (PEARL-SGD), a new algorithm inspired by the stochastic gradient descent ascent method in minimax optimization, that is able to handle the competitive nature of the players/clients. In PEARL-SGD, each player performs local SGD steps independently their own actions/strategies (keeping the strategies of the other players fixed), and the udpated actions/models are periodically communicated with the other players of the network via central server.
Convergence guarantees for PEARL-SGD on heterogeneous data. We provide tight convergence guarantees for PEARL-SGD, in both deterministic and stochastic regimes with heterogeneous data (see Table 1 for summary of our results).
Deterministic setting: For the full-batch (deterministic) variant of PEARL-SGD, we prove that under suitable assumptions, PEARL-SGA converges linearly to an equilibrium for any communication period T > 1, provided that the constant step-size is sufficiently small (see Theorem 3.3).
Stochastic setting: In its more general version, PEARL-SGD assumes that each player uses an unbiased estimator of its gradient in the update rule. For this setting, we provide two Theorems based on two different step-size choices:
Constant step-size: We show that under the same assumptions as in the deterministic case, PEARL-SGD converges linearly to a neighborhood of equilibrium (see Theorem 3.4). In Corollary 3.5, we show that with appropriate step-size depending the total number of local SGD iterations T, PEARL-SGD achieves O(/TT') convergence rate with improved communication complexity when is sufficienlly large.
Decreasing step-size rule: We prove that PEARL-SGD converges to an exact equilibrium (without neighborhood of convergence) with sublinear convergence (see Theorem 3.6). In this scenario, the asymptotic rate and communication complexity are essentially the same as in Corollary 3.5, but this result does not require the step-sizes depend on T.
Numerical Evaluation: We provide numerical experiments verifying our theoretical results and show the benefits in terms of communications of PEARL-SGD over its non-local counterpart in the MpFL settings.
2 Multiplayer Federated Learning: Definition and Related Work
In this section, we introduce the Multiplayer Federated Learning (MpFL. framework and explain its main differences compared to the classical FI. [59], federated minimax optimization [25, 122, 145] and personalized FL [34, 129].

---

Table 1: Summary theoretical results for PEARL-SGD. Theorem 3.3 considers the full-batch (deterministic) scenario. Theorem 3.4 and Theorem 3.6 both considers the general stochastic case. These results differ in the sizp choice; the former uses a constant step-size, while the latter uses decreasing step-sizes. In the Convergence column, "Linear" and "Sublinear" indicates the convergence rate, "Exact" refers to convergence to an equilibrium, and "Neighborhood" refers to convergence neighborhood of equilibrium.
Theorem
Setting
Step-size
Convergence
Theorem 3.3
Deterministic
Constant
Linear + Exact
Theorem 3.4
Stochastic
Constant
Linear+ Neighbbroid
Theorem 3.6
Stochastic
Decreasing
Sublinear-
2.1 Definition of MpFL.
Multiplayer Federated Learning (MpFL) is a machine learning setting that combines the benefits of a game-theoretic formulation with classical federated learning. In this setting, the problem is an n-player game in which multiple players/clients (e.g. mobile devices whole organizations) communicate with each other via a central server (e.g. service provider) to reach equilibrium. That is, reach a set of strategies where no player can unilaterally deviate from their strategy to achieve better payoff, given the strategies chosen by all other players.
In classical n-player games, communication between players was assumed to be cheap, easy, and straightforward, mainly because all players were in close proximity and had direct access to one another. This assumption made communication an insignificant concern typical game theory analysis. However, with the advent of new large-scale machine learning applications, this is no longer the case. Communication between players can be expensive and challenging, especially in distributed systems where the clients/players are geographically dispersed or operate under communication constraints. Addressing communication costs and designing communication-effee for n-player games have become increasingly important, and this is precisely the challenge that Multiplayer Federated Learning aims address.
algorithms
Equilibrium in n-player game. Let xf E Rdi denote the action of player = 1...., and Rdi+..+d, be the joint action/strategy vector of all players. Let be the function of the player i (which player prefers minimize ..... x
let (x) ,...,, .." E fi(x ,..., x"): Rd +
,T) D- be the vector containing all players' actions except that of player i. With this notation in place, the goal of an n-player game is to find an 2f) E ID, formally expressed
in r') and let x= (x),...,,'' zf+1 ......"")
equilibrium, joint action x. (0) (0.....,,"))
find
[( S ,,(x";07"), Vo E RR. Vi [n).
x. =x: 27)ER ST)ERD
where fi /i(dfx==t) fi('"....,.""
Server
MpFL. As mentioned above, in the setting of interest of this work, we focus
n-player game which multiple players communicate via central server to reach equilibrium. In this set- ting, each player of the n-player game represents client to the system (see Figure 1). Mathemat- ically, the problem is formulated as solving (1) with
[xl m..)""
Player 1 fi(x) xxx'xx"".... fa(x), xx.,,x"".
Player 2
Player xx"
f((z) = EgIND (f....))...
Figure 1: Illustration of MpFL for heterogeneous functions ft. The goal is for each player to reach the equilibrium x, (at,,.. x..) (see (1)) with as little communication as possible.
Here Dj denotes the data distribution of the i-th player, Jt.g: is the loss of the i-th player for data point ç sampled from D..
3

---

In our proposed FL environment, each client/player uses the strategies of all players to execute local updates. In particular, each player keeps the other players' strategies fixed and updates their own value, which is later shared with the master server, which concatenates all new strategies and sends them back to all players. Later, Section we introduce and analyze Algorithm 1, named Per-Player Local SGD (PEARL-SGD) which formalizes the above setting.
Similarly to classical FL, our setting allows for heterogeneous (non-iid) data as we have restrictive assumption on the data distribution D; or the similarity between the functions of the players.
Assumptions multiplayer game. Let us present the main assumptions the functions of the multiplayer game, which we later use to provide the convergence analysis for PEARL-SGD objective function fa of each player E [n]] is convex and smooth.
Throughout this work, we denote the partial derivative of fi with respect to x' as Vat fi(z" x²) fi(';; æ (). This convention allows to remove the cumbersome subscript x' from the V notation, with the understanding that we only differentiate f, with respect to x' but never with x=
Assumption 2.1 (Convex (CVX)). For e [n). for any x= R D-dd the local function ()(5x=)): Rd. -> R is convex. That is, for any x',y" y E Rd and x- E D-d,
f(y'::= f((x (Vfi(<': -x)) x¹)
Assumption 2.2 (Smoothness (SM)). For i E [n], for any x² R R-d, fi(;==)): Rd. - R is smooth. That is, for any x',y' E Rd. and x- E R-d.
d. the local function
\ Vflu:== s Lg || v'll
As in (1), in the stochastic regime of MpFl. we have fi = EgLD, [frge( =")]] To obtain convergence guarantees for PEARL-SGD in this scenario, we need the following assump- tion of bounded variance of the gradient oracle, commonly used in stochastic optimization.
Assumption 2.3 (Bounded Variance (BV)). Let 2 0, Vi E [n]. For each i 1,...,
E@ fe - v fi('" b ||| s of Va' E Rd, x E R D-d:
2.2 Comparison with closely related FL frameworks
Having presented the MpFL setting, let us now provide a concise survey of the most closely related setups: classical FL, federated minimax optimization and personalized FL. We compare each of them with MpFL, and explain in detail in Appendix why existing FL algorithmss are not applicable to MpFl. An additional list of related work, explaining the literatures on game theory, distributed Nash equilibrium search, learning in games and the usage of game theory for modeling clients' social behavior in FI., and how MpFL is distinguished from them, is provided in Appendix A.
Federated learning (FL). The basic formulation for classical FL is [59]] minimize f(x) =
zERd
1 1E Here, x Rd represents the global model parameter, fx(x) = Egt (F, E*)] denotes the local objective function at client and D, denotes the data distribution of client i. The local loss functions F, ) are often of the same form across all clients, but the data distribution D; generally varies, capturing data heterogeneity. The foundational communication-efficce for this setup is FedAvg (Local SGD), proposed and popularized by [93]. Despite its simplicity. Local SGD has shown empirical success in terms of convergence speed and communication cost. Many works provided theoretical explanation for this performance [127, 29, 128, 63].
algorithm
Note that in these works on classical FL., clients work in fully cooperative manner to find x. argmin, g (ar), unlike in our proposed MpF1., where the clients serve as players of the game and seek equilibrium among possibly competing (non-cooperative) objectives.

---

Federated minimax optimization. This is a more recent, federated extension of minimax opti-
mization appearing in many ML applications. There the problem is: minimize maximize (xx y)
xER*= yER
1 "E=,Ch y). Here n is the number of clients and L; represents the local loss function at client 2 that depends on both x and y. It is defined as L, y) Egt.D, [,._[ (z,y. <)]. where dz y, E) denotes the loss for the data point Ç. sampled from the local data distribution Dj at client i. The extension of Local SGD for solving this problem are Local Stochastic Gradient Descent-Ascen (SGDA) [25, 122] or Local Stochastic Extragradient (SEG) [8, 9] algorithms, More recently there was also an approach based on primal-dual updates [20].
While this line of work also studied federated learning in the context of minimax optimization and games, it is totally different from MpFL. The setup assumes that each FL client adjusts the actions of both players x and of the minimax game, and does not take the multiplayer aspect into account. In contrast, in MpFL, we assume that each client is player of large-scale multiplayer game who only adjusts their own action x² in the interest of optimizing their own objective /s. In our work, we design the novel PEARL-SGD algorithm suitable for MpFL, as the existing Local SGDA and Local SEG methods cannot handle the setup.
Personalized federated learning. In personalized FL [34, 129, 50, 49, 26, 130], clients aim to learn models tailored to each local data distribution, while generalizing well on all clients' data [51]. One formulation of personalized FL is minimize
- 1x(x") + o(x* x"); in [50, 51], for
x=(=* ==="""".,""))E ""E""d
example, o is taken as the model consensus regularizer 6(x² ...... x²)) 2n x= - Given that each h; and Φ are convex, its first-order optimality condition is equivalent to the equilibrium condition for the nı-player game where players' objectives fi(=";=== a: Such formulation of personalized FI., therefore, is an instance of MpFI.. On the other hand, there exist personalized FL approaches that are not modeled as direct subclass of MpFL- e.g.. [34, 129] proposed to maintain a separate global model w along with local models x'. Still, it is clear that MpFL is closely related to personalized FL. Importantly, however, the purpose of MpFL is not limited to having personalized models suitable for local data distribution, and encompasses settings where xn
hx(x)) (("))+(((>'+) ;....-""" + .").
rr, ,..., differ in dimensionality or structure.
3 PEARL-SGD: Algorithm and Convergence Guarantees
In this section, we introduce and analyze Algorithm 1, named Per-Player Local SGD (PEARL-SGD), which is suitable for the MpFL setting we described in Section 2.
3.1 Algorithm and assumptions
In PEARL-SGD, clients/players of the game run SGD independently in parallel to update their strategy (keeping the strategies x= of the other players fixed), which are communi- cated to other players only once in a while. In more detail, in every round of PEARL- SGD, each player i E [n] runs T iterations of stochastic gradient descent (SGD) with respect to f( x ") having x - fixed to be the information of the other players' actions obtained from the previous synchronization step. Once each player completes itera- tions of SGD (local updates), a synchroniza- tion occurs; the central server collects the
Algorithm 1 Per-Player Local SGD (PEARL-SGD)
Input: Step-sizes 7/4 O, Synchronization interval T 2 1, Number of rounds R 2 1
for p = 0..., R do
Master collects =r from players i E [n] Master distributes X,p back to players
for each players = 1...., n in parallel do
for k TP... ....... T 1) 1 do
Draw E ~D. Dj
g + Vhi.e (#t: xpp))
end for
end for end for Output: X, R
actions of all players, and then the concate- nation of all updated strategies/actions is dis- tributed to all clients/players.
We emphasize that PEARL-SGD and its convergence guarantees hold without any assumption on players' data distributions D. That is, functions fi can be very different between players, and the setting is fully heterogeneous.
5

---

Let us note that the synchronization step in PEARL-SGD involves transferring D = (d1 +....d,)) dimensional vector X,p from the master server to the players. This an important difference compared to the classical FL (minimization problem), where the dimension of the communication vectors is the same from client to master and from master client, and it does not scale with n. While PEARL-SGD aims to reduce this overhead compared to its distributed variant (r 1) by communicating less frequently (with T > 1), the high complexity of the synchronization step makes MpFL (and distributed n-player games in general) more suitable for cross-silo FL setups with relatively small number of organizations and more reliable communication bandwidths. We expect that the potentially expensive communication of high- nigh-dimensional vectors XTp could be addressed by incorporating additional techniques such as gradient compression [4, 10]. This an orthogonal approach to proposed local methods, and we leave it for future work.
Assumptions the joint gradient operator. We require some definitions and additional assump- tions in order to carry out the theory. Define the joint gradient operator IF: R - R as
F(x)
ffn("";
Assumption 3.1 (Quasi-strong monotonicity (QSM)). There exists x, = (x), ......... "..")..,"?.)) E R equilibrium where F(x.) and such that Vx RD,, (F(x), x.) ||x x,
(QSM) is concept extending quasi-strong convexity [46, 45] to the context of variational inequality problems (VIPs). This condition has been referred to as different names in the literature, such as strong coherent VIPs [126], VIPs with strong stability condition [95], or the strong Minty variational inequality [28]. generalizes strong monotonicity, capturing some non-monon monmoontoone problems. In [89], it proposed and utilized
assumption ensuring the convergence of SGDA dynamics in minimax games without the well-known issues of cycling or diverging [97, 22). Later, was also used in the analysis of stochastic extragradient method [42] and its single-call variants (optimistic and past stochastic etragradient) [19].
Assumption 3.2 (Star-cocoercivity (SCO)). Fis } -ssta-cccceeccvee, i.e., there l such that for any E R,, x
[
(SCO) generalizes the class of coercive operators and, interestingly, can hold for non-Lipschitz operators [89]. This has also been taken as minimal assumption for SGDA analysis in prior work [10]. Note that (QSM) and (SCO) together imply fu ||x x.I| S ||F(x)) < E |x x+I| for any IRD which implies < f. We call к ε/μ 2 the condition number of the problem. In Appendix F, we provide detailed discussion on the set of our theoretical assumptions and explain connections to other commonly assumed properties in the literature such as cocoercivity, Lipschitzness and monotonicity.
3.2 Convergence of PEARL-SGD: Deterministic setup
First, we provide the convergence result for PEARL-SGD with constant step-size 7k = in the full-batch (deterministic) scenario, where there is no noise in the gradient computation. While this directly recovered as a special case of Theorem 3.4 with o; = 0, we state separately as the deterministic case provides several points of discussion that are worth emphasizing their own.
Theorem 3.3. Assume (CVX), (SM), (QSM) and (SCO). Let Lmax = max Ly..,, ).). x= Then the Deterministie PEARL-SGD (Algorithm with full-batch) converges with the rate
= l/P
and 0 7/ = 7 S Tr+2(r- 1) Tiuax VR
||XTR - x. 1|2 < (1 " Ixo x.11
where 2 2- 7eT 2(T 1)y I-max / /k/3 (by the choice 7))

---

Theorem 3.3 shows that deterministic PEARL-SGD converges linearly to an equilibrium. This in contrast with the case of local gradient descent in FL setup with heterogeneous data, where convergence is only to a neighborhood of the optimum even in the absence of noise [63], unless further correction mechanism used [100]. This is because the classical FI. problem is modeled as finite sum minimization, whereas our MpFL. is modeled as a game, for which the existence of variationally stable equilibrium is a standard assumption for convergence analysis [14, 95, 89, 96], In particular, when = I, the step-size constraint and the convergence rate of Theorem 3.3 reduces to the analysis of gradient descent-ascent (GDA) under the (QSM) and (SCO) assumptions from [89], showing that our analysis is tight and consistent with the existing literature.
Player drift and step-size constraint. If 7 does not appropriately scale down with т, then at each round, players' actions (SGD iterates) converge to minimizers of local functions. We call this phenomenon player drift, analogous to client drift in classical FL. [61], enforcing the (1//T) step-size. our setting, note that the local minimizers x (x-p) := argmin.''Re. f((x'; xxp) depend on other players' strategies ..pp. Due to this dependence, under extreme player drift, PEARL-SGD may display undesirable dynamics such as diverging to infinity (which can be checked with simple examples such as the two-player quadratic minimax game min maX&ER 5u² + wv 5² with
< 1). As these features not typically observed in client drift in classical FL, player drift represents a distinct phenomenon despite some conceptual similaritics. Therefore, we consider understanding and mitigating player drift an intriguing direction for future work in MpFL., which may necessitate novel insights that differ from existing approaches to client drift [61, 100].
With the step-size constrained to y (1/rr, communication reduction by PEARL-SGD is not observed in the deterministic setting (Theorem 3.3) but is achieved in the stochastic setting-see Section 3.3. A concurrent work [148] proposes the Decoupled SGD algorithm, which coincides with our PEARL-SGD, and shows that can be communication-effiiie
even in the deterministic setup under an additional assumption of weakly coupled games (with slightly different main assumptions). We provide a more complete discussion of this in Appendix A.
3.3 Convergence of PEARL-SGD: Stochastic setup
We now discuss the convergence of PEARL-SGD with stochastic gradients. We first present the convergence of PEARL-SGD to neighborhood of the equilibrium x, given constant step-sizes ?'k = 7 and then discuss the communication complexity gain we achieve. Then we present the convergence result using decreasing step-size selection. showing exact sublinear convergence to x, (rather than its neighborhood). We provide the outline and details of the proofs in Appendix C.
Theorem 3.4. Assume (CVX), (SM), (BV), (QSM) and (SCO) hold. Let 0 < 7 = 7 S
2r+2(r 1)4max v and denote q = T.max// Vtp. Then PEARL-SGD exhibits the rate:
2 70²
- x.12 -|x E
1t ||x0 - x111 + (1 ( 1) ((4 v3g +
2r u
where 0² ====) >i= of and ( c- 2 7lT 2(T - 1) v Rr/ > 0 by the choice of 7.
When 7 = 1, with < 1/e, the above rate becomes E
||x - x.12] < - (1-74) Ixx x.
/0"/u, which is consistent with the classical analysis of the stochastic gradient descent-ascent (SGDA). In the result, note that ²² the sum of o?'s, the (upper bounds on) playerwise gradient variances (of 2 EgiND. [[VV (1); ( xt [|] ). Hence, r² represents the upper bound on the
variance in estimating the joint gradient operator FF.).
Remark. If we use the largest possible step-size 7 = 2++2( 11) allowed in Theorem 3.4, then the right-hand side of the bound does not scale down indefinitely with In fact, with this choice of y, one can expect the communication gain by factor of approximately ? (when Luax << E). More precisely, suppose q < 1 (equivalently Lmax I Weferrefer to Appendix F for the explanation
7

---

that this is a common parameter regime). Then we have = = ( and
E E|1x= x.11² S (TH) x.11 + x.11++0( + Immax o²
E Ep
The first linear convergence term is essentially unaffected by т, the effect of using smaller = @ (+) is canceled out by the factor r within (1 - y R In the second term (which is usually dominant), we see that the size of the convergence neighborhood reduced by the factor 0 ( + (qp) =0 =
+x) Therefore, we see that with ((V)), PEARL-SGD reaches about VK times smaller neighborhood within the same number of communication rounds R (compared to the case 1).
In Corollary 3.5, we analyze the convergence and communication gain of PEARL-SGD in the regime where the total number of iterations T = 7 is large, using step-size depending on T.
Corollary 3.5. Suppose the assumptions of Theorem 3.4 hold, and let 2 1 be fixed. Let
Lmmxx/ /ep. Then PEARL-SGD with "/k = p exhibits the rate
E -x x. 11 Ō (1 g1+ Xo x. T
(1+ o2 (1+ q) 2 Lixax22 2
where v) is selected so that T (1 + 24) rj log 4) provided that large enough so that 7) > KT. Here the O-notation hides polylogarithiic terms T and constant factors.
Reduction of communication complexity. Note that the Ô (Ix term decays fast T
in Corollary 3.5 (as T grows) and the terms proportional to o² become dominant. The order of convergence is not slower than the Ô (1/2) rate of the fully communicating case t = 1. provided that 72 Leman " 112122 O (d'/ = =
(VWT/Lmax). (
Therefore, as long as we select W Limax in PEARL-SGD the communication cost is reduced by the factor of (because the total number of communications is T/T). With the largest possible т, the resulting communication complexity 7/- = ( (Thmmas/)) ) = θ (VT)
Convergence to equilibrium via decreasing step-sizes. We conclude the section with convergence result for PEARL-SGD using decreasing step-size selection. While showing similar convergence rate terms of T as Corollary 3.5, Theorem 3.6 has the advantage of not requiring to fix in advance to determine the step-sizes.
Theorem 3.6. Under the assumptions of Theorem 3.4, let = Lmmxx/ VEpi and choose the step-
if < 2(1 + 2q) i 2 2(1 + 24)x
sizes 7
(1+2gg (1+1)
for Tp < k S T(p + 1) 1, p 0, ... R 1. Then
PEARL- converges with the rate
4(1 2272 Xo - x,
4(1 + 9)0²
[|x7 - x.1 x11
<
+
el'2
4²T
4(1 + 2q)² KTT2
27 (1+
+ 32(1 + q)T² Lmaxx 2 log T
1272
Vk
where T -R is the total number of iterations.

---

[-2
Relative Errer
Relative Erra
Relative Error
30-
10-1
1098
2039
9997
1030 4983 1999 Po1 1966 3299 1493
2036 488 189 se m9t 1209 1499 Communication Rounds
Communication Rounds
Communication Rounds
(a)
(b)
(c)
Figure 2: Performance plots for PEARL-SGD. Figures 2a (deterministic) and 2b (stochastic) show the relative error || on the n-player game defined by (2) with different values of т, using theoretical step-sizes. (We provide additional experiments for this n-player game setup in Appendix E.) Figure 2c shows the relative enror in the (stochastic) mobile robot control setup (3) for distinct values of
4 Numerical Experiments
In this section, we conduct experiments to assess the empirical performance of PEARL-SGD and verify our theory. We focus on two setups: a multiplayer game with quadratic objectives, and distributed mobile robot control problem. Details of experiments are provided in Appendix D.
4.1 Quadratic n-player game
We consider an n-player game where the local function of the i-th player is given by
[(xx;x=)) = M4 EM=1
S ax);
for i = 1,... (with d1 ... dn =d) In this setting, each fi.m (2' (x0;x=]) takes the form fimm (xt;x 1 (x², Aimxt) + Eisisminell (xt, Bijmmt) (ai,m, x²), where Ai, Big.m Raxd and ai, E Rd for 100=1,... 1,...,M. M.
Connection to game & control theory literature. The above n-player game formulation has been often considered in game and control theory literature and has been used in recent works on distributed games (Nash equilibrium search) [117, 140, 80. 132, 60). connection with this literature, in Section 4.2, we demonstrate experiment on a concrete robot control setup from [60].
(((r+t((-)))mmaae) from Theorems 3.3 and 3.4 with 21,2, 4, 5, 8, 203. We set the cocoercivity parameter to f L2/n following [33]. where I. and are explicitly computed Lipschitz constant and strong monotonicity parameter of IF. Figure 2a displays the results from Deterministic PEARL-SGD, where observe that all values of produce indistinguishable performance plots (which is predicted, as scales down with r). Figure 2b shows results from the stochastic setting (we mini-batch from the finite sum (2)), where we repeat each experiment 5 times and plot the mean relative error with standard deviation (shaded region). It demonstrates that PEARL-SGD with larger synchronization interval provides a clear benefit of achieving smaller relative error ||x=-x.1 using the same number of communication rounds. These |x
We PEARL-SGD with the theoretical step-size 7
results verify our theoretical predictions from Section 3.
In Appendix E. we provide additional simulations regarding the case where the precise theoretical parameters μ. E, Lmax not known, that has be tuned empirically. It demonstrates that in practice, (T, 7) can be effective tunable hyperparameters for gaining communication efficiency.
Performance of PEARL-SGD for different (7, pairs. Figure 3 displays the heatmap of relative errors (log-scale) after 100 communication rounds of Deterministic PEARL-SGD in the case of quadratic game with n White and yellow regions indicate divergence/poor performance; darker regions indicate lower relative errors.

---

wynchroniiation Interval
log log Relaative Error)
-0.2
43
51-
0.25
-0.30
-035
163 2633
sea de-1 se-1
Step-size
Figure 3: Heatmap of relative errors in logarithmic scale.
Figure reveals a trend for a fixed y, PEARL-SGD's performance improves as increases up to certain threshold, after which it declines and finally diverges. Another key observation is that the dark region of the heatmap (signifying the best performance) takes the shape of hyperbola. This is consistent with Theorem 3.3, showing the relationship 7/ x 1/r where "/r is the optimal step-size choice given 7 (providing fastest convergence).
4.2 Distributed mobile robot control
Here, we consider distributed control problem of mobile robots from [60]. This is multi-agent system where each robot has its own objective, depending on the positions x² RR (corresponding to action/strategy in formulation of multiplayer game) of each i-th robot. Specifically, the objective function of the robot is:
f((x) = ai | sinel
bi
N
1
x
herll
2
2
where Ju (x*) represents the cost penalizing the distance of agent from the anchor point aran E Rd and ; x ') is the cost associated with the relative displacement between the robots' positions. The control problem finds an equilibrium of the n-player game, which the concatenation of all robots' position vectors, ensuring that each robot stays close to x while maintaining designated displacement from other robots.
We implement PEARL-SGD with synchronization intervals r E 2,5,,4558 8, 2,2 and the theoretical step-size 7 Ër+ T.mas (T -r- l)vE Figure 2c shows that with larger values of PEARL-SGD achieves better accuracy (in terms of distance to x.) within a given number of communication rounds. This highlights the potential benefit of using local update steps in solving real-world problems formulated as multiplayer games.
Conclusion
In this paper, we introduce Multiplayer Federated I Learning (MpFL.,, FL. framework that models setups where clients, acting strategically in their own interests, collaborate through central server equilibrium. We propose the PEARL-SGD
to train models (actions) with the goal of reaching algorithm for handling MpFL and establish its tight convergence guarantees under heterogencous settings where each player has distinct objectives and data distributions. We show that PEARL-SGD achieves improved communication efficiency, mitigating the primary computational bottleneck in large-scale applications.
Our work offers several promising future research directions, including the incorporation ideas such Extragradient methods [68, 43), asynchronous updates [23, 127]. gradient compression [4], gradient tracking [107], and algorithmic correction for client drifts [61, 100]. We anticipate that our initiation of the study of MpFL will stimulate further research along these and related directions.
10

---

Acknowledgments
Sayantan Choudhury acknowledges support from the Chen Family Dissertation Fellowship. Nicolas Loizou acknowledges support from CISCO Research and the JHU Catalyst Award.
References
[1] J. Abernethy, K. A. Lai, and A. Wibisono. Last-iterate convergence rates for min-max optimization: Convergence of hamiltonian gradient descent and consensus optimization. international Conference on Algoritmmic Learning Theory, 2021.
[2] E. Ahmed and H. Agiza. Dynamics of a cournot game with n-competitors. Chaos, Solitons & Fractals, (19):5513-151) 1998.
[3] E. Aiyoshi and K. Shimizu. Hierarchical decentralized systems and its new solution by barrier method. IEEE Transactions on Systems, Man and Cybernetics, 00:444-449 1981.
[4] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. QSGD: Communicationn-effcccenn SGD via gradient quantization and encoding. Neural Information Processing Systems, 2017.
[5] R. S. Antunes, C. André da Costa, A. Küddrlle I. A. Yari, and B. Eskofier. Federated learning for healtheare: Systematic review and architecture proposal. ACM Transactions on Intelligent Systems and Technology (TIST), 13(4)11-23, 2022.
[6] S. Arisdakessian, O. A. Wahab, A. Mourad, and H. Otrok. Coalitional federated learning: Improving communication and training on non-iid data with selfish clients. IEEE Transactions on Services Computing, 16(4):2462-244 2023.
[7] W. Azizian, Mitliagkas, S. Lacoste- Julien, and G. Gidel. A tight and unified analysis of gradient-basee based methods for whole spectrum of differentiable games. International Conference Artificial Intelligence and Statistics, 2020.
[8] A. Beznosikov, V. Samokhin, and A. Gasnikov. Distributed saddle-point problems: Lower bounds, near-optimal and robust algorithms. arXiv preprint 2rXiv:2010..3//11 2020.
[9] A. Beznosikov, P. Dvurechenskii, A. Koloskova, V. Samokhin, S. U. Stich, and A. Gasnikov. Decentralized local stochastic eatra-gradient for variational inequalities. Neural Information Processing Systems, 2022.
[10] A. Beznosikov, E. Gorbunov, H. Berard, and N. Loizou. Stochastic gradient descent-ascent. Unified theory and new efficient methods. International Conference on Artificial Intelligence and Statistics, 2023.
[11] A. Blum, N. Haghtalab, R. L. Phillips, and H. Shao. One for one, all for all: Equilibria and optimality of collaboration federated learning. International Conference on Machine Learning, 2021.
[12] Bot, R. Csetnek, and D.-K. Nguyen. Fast Optimistic Gradient Descent Ascent (OGDA) Method in Continuous and Discrete Time. Foundations of Computational Mathematics, 2023,
[13] J. Bracken and J. T. McGill. Mathematical programs with optimization problems in the constraints. Operations research, 21(1):37-44, 1973.
[14] M. Bravo, D. Leslie, and P. Mertikopoulos. Bandit learning in concave n-person games. Neural Information Processing Systems, 2018.
[15] G. W. Brown. Some Notes on Computation of Games Solutions. Rand Corporation, 1949.
[16] Y. Cai and W. Zheng, Accelerated single-call methods for constrained min-max optimization. International conference on Learning Representations, 2023.
[17] A. Capitaine, F. Boursier, A. Scheid, E. Moulines, M. Jordan, E.-M. El-Mhamdi, and A. Dur- mus. Unravelling collaborative learning. Neural Information Processing Systems, 37: 97231-97260 2024.

---

[18] T. Chavdarova, G. Gidel, F. Fleuret, and S. Lacoste-Julien. Reducing noise in GAN training with variance reduced extragradient. Neural Information Processing Systems, 2019.
[19] S. Choudhury, E. Gorbunov, and N. Loizou. Single-call stochastic extragradient methods for structured non-monotone variational inequalities: Improved analysis under weaker conditions. Neural Information Processing Systems, 2024.
[20] L. Condat and P. Richtárik. RandProx: Primal-dual optimization algorithms with randomized proximal updates. NeurIPS OPT 2022 Workshop. 2022.
[21] C. Daskalakis and I. Panageas. The limit points of (optimistic) gradient descent in min-max optimization. Neural Information Processing Systems, 2018.
[22] C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng. Training GANs with optimism. Interna- tional Conference on Learning Representations, 2018.
[23] J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, M. Mao, M. Ranzato, A. Senior, P. Tucker, K. Yang, et Large scale distributed deep networks. Neural Information Processing Systems, 2012.
[24] V. Dem yanov and A. Pevnyi. Numerical methods for finding saddle points. USSR Computa- tional Mathematics and Mathematical Physics, 12(5):11-52, 1972.
[25] Y. Deng and M. Mahdavi. Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. International Conference on Artificial Intelligence and Statistics, 2021.
[26] Y. Deng, M. M. Kamani, and M. Mahdavi. Adaptive personalized federated learning. arXiv:2003.1 100003.13440 13461, 2020.
[27] J. Diakonikolas. Halpern iteration for near-optimal and parameter- free monotone inclusion and strong solutions to variational inequalities. Conference on Learning Theory, 2020.
[28] J. Diakonikolas, C. Daskalakis, and M. Jordan. Efficient methods for structured nonconvex- nonconcave min-max optimization. International Conference on Artificial Intelligence and Statistics, 2021.
[29] A. Dieuleveut and K. K. Patel. Communication trade-offs for Local-SGD with large step size. Neural Information Processing Systems, 2019.
[30] K. Donahue and J. Kleinberg. Model-sharing games: Analyzing federated learning under voluntary participation. AAAI Conference on Artificial Intelligence, 2021.
[31] F. E. Dorner, Konstantinov, G. Pashaliev, and M. Vechev. Incentivizing honesty among competitors in collaborative learning and optimization. Neural Information Processing Systems, 2023.
[32] K. Emmanouilidis, R. Vidal, and N. Loizou. Stochastic extragradient with random reshuffling: Improved convergence for variational inequalities. International Conference on Artificial Intelligence and Statistics, 2024.
[33] F. Facchinei and J.-S. Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, 2003.
[34] A. Fallah, A. Mokhtari, and A. Ozdaglar. Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach. Neural Information Processing Systems, 2020.
[35] S. Feng, B. Li, H. Yu, Y. Liu, and Q. Yang. Semi-supervised federated heterogeneous transfer learning. Knowledge-Basee Systems, 252:109384, 2022.
[36] T. Fiez and I.. Ratliff. Local convergence analysis of gradient descent ascent with finite timescale separation. International Conference on Learning Representations, 2021.
12

---

[37] I. Gemp, R. Patel, Y. Bachrach, M. Lanctot, V. Dasagi, L. Marris, G. Piliouras, S. Liu, and Tuyls. Steering language models with game- game-theoreetic solvers. ICML Agentic Markets Workshop, 2024.
[38] A. Giannou, E.-V. Vlatakis- Gkaragkounis, and P. Mertikopoulos. On the rate of convergence of regularized learning in games: From bandits and uncertainty to optimism and beyond. Neural Information Processing Systems, 2021.
[39] G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien. A variational inequal- ity perspective on generative adversarial networks. International conference on Learning Representations, 2019.
[40] I. Goodfellow, Pouget-Abadie. M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. Neural Information Processing Systems, 2014.
[41] E. Gorbunov, F. Hanzely, and P. Richtarik. Local SGD: methods. International Conference on Artificial Intelligence and Statistics, 2021.
Unified theory and new efficient
[42] E. Gorbunov, H. Berard, G. Gidel, and N. Loizou. Stochastic extragradient: General analysis and improved rates. International Conference on Artificial Intelligence and Statistics, 2022.
[43] E. Gorbunov, N. Loizou, and G. Gidel. Extragradient method: O (1/k) last-iterate conver- gence for monotone variational inequalities and connections with cocoercivity. International Conference on Artificial Intelligence and Statisties, 2022.
[44] E. Gorbunov, A. Taylor, and G. Gidel. Last-iterate convergence of optimistic gradient method for monotone variational inequalities. Neural Information Processing Systems, 2022.
[45] R. Gower, O. Sebbouh, and N. Loizou. SGD for structured nonconvex functions: Learning rates, minibatching and interpolation. International Conference on Arlificial Intelligence and Statistics, 2021.
[46] R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and P. Richtárik. Sgd: General analysis and improved rates. International Conference on Machine Learning, 2019.
[47] M. Grudzien, G. Malinovsky, and P. Richtarik. Can 5th generation local training methods support client sampling? Yes! International Conference on Artificial Intelligence and Statistics, 2023.
[48] F. Haddadpour and M. Mahdavi. On the convergence of local descent methods in federated learning. arXiv: 14425, 2019.
[49] F. Hanzely and Richtárik. Federated learning of mixture of global and local models. arXiv:2002.05516, 2020.
[50] F. Hanzely, S. Hanzely, S. Horváth, and P. Richtarik. Lower bounds and optimal algorithms for personalized federated learning. Neural Information Processing Systems, 2020.
[51] F. Hanzely, B. Zhao, and m. kolar. Personalized federated learning: A unified framework and universal optimization techniques. Transactions on Machine Learning Research, 2023.
[52] A. Hard, K. Rao, R. Mathews, S. Ramaswamy, F. Beaufays, S. Augenstein, H. Eichner, C. Kiddon, and D. Ramage. Federated learning for mobile keyboard prediction. arXiv preprint S.ti:18811.03004 2018.
[53] J. C. Harsanyi and R. Selten. A general theory of equilibrium selection in games. MIT Press Books, 1, 1988.
[54] Y.-P. Hsich, P. Mertikopoulos, and V. Cevher. The limits of min-max optimization algorithms: Convergence to spurious non-critical sets. International Conference on Machine Learning, 2021.
[55] Z. Hu and H. Huang. Tighter analysis for ProxSkip. International Conference on Machine Learning, 2023.
13

---

[56] M. Huang, D. Zhang, and K. Ji. Achieving linear speedup in non-llD federated bilevel learning. International Conference on Machine Learning, 2023.
[57] A. Jacob, Shen, G. Farina, and J. Andreas. The consensus game: Language model generation via equilibrium search. International Conference Learning Representations, 2024.
[58] J. Jordan. Three problems in learning mixed-strategy nash equilibria. Games and Economic Behavior, 5(3):368-386, 1993.
[59] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji. K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems in federated learning. Foundations and trends in machine learning, 14(1-2):1-210, 2021.
[60] D. Kalyva and H. E. Psillakis. Distributed control of mobile robot Nash equilibrium seeking with sampled neighbor information. Automatica, 166:1 1712, 2024.
system for
[61] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh. SCAFFOLD: Stochastie controlled averaging for federated learning. International Conference on Machine Learning, 2020.
[62] S. P. Karimireddy, W. Guo, and M. I. Jordan. Mechanisms that incentivize data sharing in federated learning. wwXiv:2207.04557 2022.
[63] A. Khaled, K. Mishchenko, and Richtarik. Tighter theory for local SGD on identical and heterogeneous data. International Conference on Artificial Intelligence and Statistics, 2020.
[64] M. Khodak, M.-F. F. Balcan, and A. S. Talwalkar. Adaptive gradient-base meta- learning methods. Neural Information Processing Systems, 2019.
[65] Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich. unified theory of decentralized SGD with changing topology and local updates. International Conference on Machine Learning, 2020.
[66] J. Konečný, H. Brendan McMahan, X. Yu, P. Richtárik, A. Theertha Suresh, and D. Bacon. Federated learning: Strategies for improving communication efficiency, arXiv e-prints, pages arXiv-1610, 2016.
[67] J. Konečný, H. B. McMahan, D. Ramage, and P. Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. arXiv:1610.02522 2016.
[68] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonomika Matematicheskie Metody, 12(4):747-756, 1976.
[69] D. M. Kreps. Game Theory and Economic Modelling. Oxford University Press, 1990.
[70] D. M. Kreps, P. Milgrom, J. Roberts, and R. Wilson. Rational cooperation in the finitely repeated prisoners' dilemma. Journal of Economic theory, 27(2):245-255 252, 1982.
[71] M. Lanetot, V. Zambaldi, A. Gruslys, A. Lazaridou, K. Tuyls, J. Pérolat, D. Silver, and T. Graepel. unified game-theoretic approach to multiagent reinforcement learning. Neural Information Processing Systems, 2017.
[72] J. Lee, H. Cho, and C. Yun. Fundamental benefit of alternating updates in minimax optimiza- tion. International Conference on Machine Learning, 2024.
[73] S. Lee and D. Kim. Fast extra gradient methods for smooth structured minimax problems. Neural Information Processing Systems, 2021.
[74] C. Li, Yu, N. Loizou, G. Gidel, Y. Ma, N. Le Roux, and M. Jordan. On the convergence of stochastic extragradient for bilinear games using restarted iteration averaging. International Conference on Artificial Intelligence and Statistics, 2022.
[75] J. Li, Huang, and H. Huang. Communication-efficiii federated bilevel optimization with global and local lower level problems. Neural Information Processing Systems, 2023.
14

---

[76] Q. Li, Z. Wen, Z. Wu, S. Hu, N. Wang, Y. Li, X. Liu, and B. He. A survey on federated learning systems: Vision. hype and reality for data privacy and protection. IEEE Transactions Knowledge and Data Engineering, 35(4):3347-3366, 2021.
[77] T. A., K. Sahu, A. Talwalkar, and V. Smith. Federated learning: Challenges, methods, and future directions. IEEE signal processing magazine, 773))50-60,, 2020.
[78] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization in heterogeneous networks. Annual Conference on Machine Learning and Systems, 2020.
[79] T. Li, K. Zhu, N. C. Luong, D. Niyato, Q. Wu, Y. Zhang, and Chen. Applications of multi-agent reinforcement learning in future Internet: A comprehensive survey. IEEE Communications Surveys Tutorials,
2022.
[80] Z. Li and Z. Ding. Distributed nash equilibrium searching via fixed-time consensus-based algorithms. In 2019 American Control Conference (ACC), pages 2765-2770, 2019.
[81] T. Lin, C. Jin, and M. Jordan. On gradient descent ascent for nonconvex-coneaw minimax problems. International Conference on Machine Learning, 2020.
[82] T. Lin, Z. Zhou, P. Mertikopoulos, and M. Jordan. Finite-time last-iterate convergence for multi-agent learning in games. International Conference on Machine Learning, 2020.
[83] M. Liu, S. Ho, M. Wang, L. Gao, Y. Jin, and H. Zhang. Federated learning meets natural language processing: A survey, arXiv:2107. 12603, 2021.
[84] Y. Liu, A. Huang, Luo, H. Huang. Y. Liu, Y. Chen, L. Feng. T. Chen, H. Yu, and Q. Yang. FedVision: An online visual object detection platform powered by federated learning. AAAI Conference on Artificial Intelligence, 2020.
[85] Y. Liu, Y. Kang, C. Xing, T. Chen, and Q. Yang. A secure federated transfer learning framework. IEEE Intelligent Systems, 35(4):70-$5) 82, 2020.
[86] Y. Liu, X. Zhang, Y. Kang, Li, T. Chen, M. Hong, and Q. Yang. FedBCD: communication- efficient collaborative learning framework for distributed features. IEEE Transactions on Signal Processing, 70:4277-422 42900, 2022.
[87] Y. Liu, Y. Kang. T. Zou, Y. Pu, Y. He, X. Ye, Y. Ouyang, Y.-Q. Zhang, and Q. Yang. Vertical federated learning: Concepts, advances, and challenges. IEEE Transactions on Knowledge and Data Engineering, 36(7):3615-36) 2024.
[88] N. Loizou. Distributionally robust games with risk-averse players. International Conference on Operations Research and Enterprise Systems, 2016.
[89] Loizou, H. Berard, G. Gidel, I. Mitliagkas, and S. Lacoste-Julien. Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Neural Information Processing Systems, 2021.
[90] R. D. Luce and H. Raiffa. Games and Decisions: Introduction and Critical Survey. Courier Corporation, 1989.
[91] Marfoq, G. Neglia, A. Bellet, L. Kameni, and Vidal. Federated multi-task learning under a mixture of distributions. Neural Information Processing Systems, 2021.
[92] E. Mazumdar, L. J. Ratiff, and S. S. Sastry. On gradient-based learning in continuous games. SIAM Journal on Mathematics of Data Science, 2(1):103-131, 2020.
[93] B. McMahan, F. Moore, D. Ramage, S. Hampson, and B. A. y Arcas Communication-effiieent learning of deep networks from decentralized data. International Conference on Artificial Intelligence and Statistics, 2017.
[94] B. McMahan, F. Moore, D. Ramage, S. Hampson, and B. A. y Arcas Communication--eficie learning of deep networks from decentralized data. International Conference on Artificial Intelligence and Statistics, 2017.
15

---

[95] P. Mertikkopoulss and Z. Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming, 173:465-507, 2019.
[96] P. Mertikopoulos, Y.-P. Hsich, and V. Cevher. A unified stochastic approximation framework for learning in games. Mathematical Programming, 203(1):559 -009,,999999 2024.
[97] L. Mescheder, Nowozin, and A. Geiger. The numerics of GANs. Neural Information Processing Systems, 2017.
[98] J. Mills, J. Hu, and G. Min. Multi-task federated learning for personalised deep neural networks in edge computing. IEEE Transactions on Parallel and Distributed Systems, 33(3):633-66)) 6411, 2021.
[99] K. Mishchenko, D. Kovalev, E. Shulgin, P. Richtárik, and Y. Malitsky. Revisiting stochastic extragradient. International Conference on Artificial Intelligence and Statistics, 2020.
[100] K. Mishchenko, G. Malinovsky, S. Stich, and P. Richtarik. ProxSkip: Yes! Local gradient steps provably lead to communication accelcration! Finally! International Conference on Machine Learning, 2022.
[101] A. Mitra, R. Jaafar, G. J. Pappas, and H. Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Neural Information Processing Systems, 2021.
[102] A. Mokhtari. A. Ozdaglar, and S. Pattathil. A unified analysis of extra-gradee attraggradient and opti- mistic gradient methods for saddle point problems: Proximal point approach. International Conference on Artificial Intelligence and Statistics, 2020.
[103] D. Monderer and L. S. Shapley. Fictitious play property for games with identical interests. Journal of economic theory, 68(1):258-265, 1996.
[104] A. Murhekar, Z. Yuan, B. Ray Chaudhury, B. Li, and R. Mehta. Incentives in federated learning: Equilibria, dynamics, and mechanisms for welfare maximization. Neural Information Processing Systems, 2023.
[105] J. Nash. Non-cooperative games. Annals of Mathematics, 54(2):286 295, 1951.
[106] J. F. Nash Jr. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1):48-44 1950.
[107] A. Nedic, A. Olshevsky, and W. Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597-2633, 2017.
[108] Y. Pan and L. Pavel. Global convergence of an iterative gradient algorithm for the nash equilibrium in an extended OSNR game. IEEE INFOCOM, 2007.
[109] L. D. Popov. A modification of the Arrow-uuwwizz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5))845-844 1980.
[110] Y. Qiu, U. Shanbhag, and F. Yousefian. Zeroth-order methods for nondifferentiable, nonconvex, and hierarchical federated optimization. Neural Information Processing Systems,
[111] A. Rakhlin and K. Sridharan. Online learning with predictable sequences. Conference on Learning Theory, 2013.
[112] S. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. Neural Information Processing Systems, 2013.
[113] J. Robinson. An iterative method of solving a game. Annals of Mathematics, 54(2):296-301, 1951.
[114] F. K. Ryu and W. Yin. Large-scale Convex Optimization: Algorithms Annalyss via Monotone Operators. Cambridge University Press, 2022.
16

---

[115] E. K. Ryu, R. Hannah, and W. Yin. Scaled relative graphs: Nonexpansive operators via 2d euclidean geometry. Mathematical Programming, 194(1):569-61) 2022.
[116] W. Saad, Z. Han, H. V. Poor, and Basar. Game-theoretic methods for the smart grid: An overview of microgrid systems, demand-side management, and smart grid communications. IEEE Signal Processing Magazine, 2965):86-105, 2012.
[117] F. Salchisadaghiani and L. Pavel. Distributed Nash equilibrium seeking: A gossip-based algorithm. Automatica, 72:209-216. 2016.
[118] т. C. Schelling. The Strategy of Conflict: With New Preface by the Author. Harvard university press, 1980.
[119] J. Shamma and G. Arslan. Dynamic fictitious play, dynamic gradient play, and distributed convergence Nash equilibria. IEEE Transactions on Automatic Control, 50(3):112-32 2005.
[120] L. S. Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
[121] L. S. Shapley al. Some topics in two-person games. Rand Corporation, 1963.
[122] P. Sharma, R. Panda, G. Joshi, and P. Varshney. Federated minimax optimization: Improved convergence analyses and algorithms. International Conference on Machine Learning, 2022.
[123] S. Sharma, C. Xing, Y. Liu, and Y. Kang. Secure and efficient federated transfer learning. IEEE International Conference on Big Data, 2019.
[124] V. Smith, C.-K. Chiang, M. Sanjabi, and A. S. Talwalkar. Federated multi-task learning. Neural Information Processing Systems, 2017.
[125] S. Sokota, R. D'Orazio, J. 7. Kolter, N. Loizou, M. Lanctot, I. Mitliagkas, N. Brown, and Kroer. unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. International Conference on Learning Representations, 2023.
[126] C. Song, Z. Zhou, Y. Zhou, Y. Jiang, and Y. Ma. Optimistic dual extrapolation for coherent non-monotone variational inequalities. Neural Information Processing Systems, 2020.
[127] S. U. Stich. Local SGD converges fast and communicates little. International Conference on Learning Representations, 2019.
[128] S. U. Stich and S. P. Karimireddy. The enror-feedback framework: SGD with delayed gradients. Journal of Machine Learning Research, 21(237):1-36, 2020.
[129] C. T. Dinh, N. Tran, and Nguyen. Personalized federated learning with moreau envelopes. Neural Information Processing Systems, 2020.
[130] A. Z. Tan, H. Yu, L. Cui, and Q Yang. Towards personalized federated learning. IEEE Transactions on Neural Networks and Learning Systems, 34(12):9587-960) 2023.
[131] D. A. Tarzanagh, M. Li, C. Thrampoulidis, and S. Oymak. Fednest: Federated bilevel, minimax, and compositional optimization. International Conference on Machine Learning, 2022.
[132] T. Tatarenko, W. Shi, and A. Nedić. Geometric convergence of gradient play algorithms for distributed nash equilibrium seeking. IEEE Transactions on Automatic Control, 66(11): 5342-5355 2021.
[133] J. Von Neumann and O. Morgenstern. Theory of games and economic behavior: 60th anniversary commemorative edition. Theory of Games and Economic Behavior. Princeton university press, 2007.
[134] S. Wang. T. Tuor, T. Salonidis, K. K. Leung, C. Makaya, T. He, and K. Chan. Adaptive federated learning in resource constrained edge computing systems. IEEE Journal on Selected Areas in Communications, 12022111 2019.
17

---

[135] J. Xu, B. S. Glicksberg, C. Su, P. Walker, J. Bian, and F. Wang. Federated learning for healthcare informatics, Journal of healthcare informaties research, 5:1-19, 2021.
[136] J. Yang, N. Kiyavash, and N. He. Global convergence and variance reduction for a class of
nonconvex-nonconcan minimax problems. Neural Information Processing Systems, 2020.
[137] Q. Yang, Y. Liu, T. Chen, and Y. Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology, 10(2), 2019.
[138] Y. Yang, P. Xiao, and K. Ji. SimFBO: Towards simple, flexible and communication--fficcnnn federated bilevel learning. Neural Information Processing Systems, 2023.
[139] Y. Yang. Xiao, Ma. and K. Ji. First-order federated bilevel learning. AAAI Conference on Artificial Intelligence, 2025.
[140] M. Ye and G. Hu. Distributed Nash equilibrium seeking by consensus based approach. IEEE Transactions on Automatic Control, (2(9):411-48115 2017.
[141] M. Ye and G. Hu. Game design and analysis for price-based demand response: An aggregate game approach. IEEE Transactions Cybernetics, 47(3):720-755 2017.
[142] T. Yoon and E. K. Ryu. Accelerated algorithms for smooth convex-coneave minimax problems with O(1/k2) rate on squared gradient norm. International Conference on Machine Learning, 2021.
[143] T. Yoon, J. Kim, J. J. Suh, and K. Ryu. Optimal acceleration for minimax and fixed -oint problems is not unique. International Conference on Machine Learning. 2024.
[144] H. Yu, S. Yang, and S. Zhu. Parallel restarted SGD with faster convergence and less commu- nication: Demystifying why model averaging works for deep learning. AAAI Conference on Artificial Intelligence, 2019.
[145] S. Zhang, S. Choudhury, S. U. Stich, and N. Loizou. Communication-efficcee gradient descent-accent methods for distributed variational inequalities: Unified analysis and local updates. International Conference on Learning Representutions, 2024.
[146] Y. Zhao, M. Li, L. Lai, N. Suda, D. Civin, and V. Chandra. Federated learning with non-iid data. arXiv: 10.Xiv:8000.00 005000082...... 2018.
[147] T. Zheng, N. Loizou, P. You, and E. Mallada. Dissipative gradient descent ascent method: A control theory inspired algorithm for min-max optimization. IEEE Control Systems Letters, 2024.
[148] A. Zindari, P. Yazdkhasti, A. Rodomanov, T. Chavdarova, and S. U. Stich. Decoupled sgda for games with intermittent strategy communication. International Conference on Machine Learning, 2025.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We explain the novel MpFL framework (Section 2), propose PEARL-SGD (Section 3), provide its convergence guarantees (Sections 3.2, 3.3) and experiments (Sec- tion 4).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: lines 192-202 and 234-244 we discuss some limitations of the current framework, identifying future research directions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
19

---

Answer: [Yes]
Justification:
See Sections 2 and 3 for the assumptions and Appendix C for proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: See Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
20

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We will include the source codes with instructions the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ //wpps.ccppbbiii wttpccccpppppcpcceeeeeeecc tttpub/ii/ggiiieeeeeeSutuuiiiiii
/Cooeeuboeeeeeeee ssionnolll mnPoicyy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We rum 5 independent runs for stochastic experiments. Our work does not require further validation statistical significance as our numerical simulations are primarily conducted for the purpose of verifying the theory.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
21

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics pettps:/nnerree
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical work and we do not anticipate any direct societal impacts that would require mentioning.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
22

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi twwoee..ooo..... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
23

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy (https: httprrppsscc//oofeeeeeeeee////// for what should or should not be described.
25

---

Supplementary Material
We organize the appendix follows: Section A provides an additional survey of related work. Section B provides a detailed explanation on how MpFL differs from prior FL frameworks. Section C presents the proofs of theoretical results. Section D provides the details of the experiments omitted from the main paper. Section E presents some additional experiments. Section provides a detailed explanation and interpretation on the theoretical assumptions made in the paper.
Contents
1
Introduction
1.1
Main contributions
Multiplayer Federated Learning: Definition and Related Work
2.1
Definition of MpFI....
2.2
Comparison with closely related FL frameworks.
3
PEARL-SGD: Algorithm and Convergence Guarantees
3.1
Algorithm and assumptions
3.2
Convergence of PEARL-SGD: Deterministic setup
3.3
Convergence of PEARL-SGD: Stochastic setup
4
Numerical Experiments
4.1
Quadratic n-player game
4.2
Distributed mobile robot control
10
Conclusion
10
Additional related work
28
Detailed distinction of MpFL from prior FL setups
30
C Omitted proofs for Per-Player Local SGD (PEARL-SGD)
31
C.I Key ideas and proof outline
31
C.2 Proof of Lemma C.1
32
C.3 General properties and bounds for SGD
................................
33
C.4 Proofs of Lemmas C.3 and C.2
37
C.5 Remaining details in proof of Theorem 3.4
38
C66 Proof of Corollary 3.5
40
C.7 Proof of Theorem 3.6
40
Details of Numerical Experiments
42
D.I Quadratic n-player game
42
D.2 Distributed mobile robot control
42
26

---

Additional Experiments
43
E,1
Quadratic n-player game with step-size tuning.
43
E.2
Distributed mobile robot control
F Discussion on Theoretical Assumptions
44
F.1 Possible simplification of assumptions: Assuming cocoercivity of .........
44
F22 Example of non-cocoercive F satisfying (CVX), (SM), (QSM) and (SCO)
45
27

---

A Additional related work
Game Theory & Equilibrium Computation. Multiplayer games, where multiple players each minimize their own cost function that is affected by the actions of the others, are a long-studied fundamental topic in mathematics and economics [106, 105, 120, 118, 70, 53, 90, 69, 88, 133]. More recently, there has been an increasing interest in the ML community in game-theoretic problems with motivating applications, including adversarial learning [40, 22]. multi-agent reinforcement learning (MARL) [71, 79, 125], and language models [37, 57]. This incoming stream of applications has led to the development of novel analyses and insights regarding classical
selllibruum-searcchin algorithms including gradient descent-ascent [24, 81, 136, 36, 147, 89, 72], extragradient [68, 18, 32, 74, 102, 99, 42, 43 optimistic gradient [109, 111, 112, 21,39, 39, 44] and consensus optimizatiio/Hamiltoon gradient method 197, 7. 1, 89], and even the discovery of new accelerated algorithms for games (27, 142, 73, 16, 12, 143].
Learning in games. Without local updates (the case T = 1), PEARL-SGD corresponds to the stochastic gradient play dynamics or the online gradient descent considered in the literature on learning in games [92. 82, 54], or more broadly, regularized Robbins- Moonoo processes or Follow- -ee-Gennralized-Leaaaae Leaderr algorithms [96, 38]. Our setup considers the pure Nash equilibrium search in games with continuous and unconstrained action spaces, similarly as in [82]. The theoretical assumptions used in our analysis are similar to the ones that has appeared in this line of works; e.g.. [82] uses strong monotonicity and cocoercivity of the joint gradient operator, while we use the weaker notion of quasi-strong monotonicity, which similar to (but stronger than) the variational stability assumed in multiple works including [14, 95, 96], to name a few. Despite the close connections, our paper is distinguished from these works as we focus on communication efficiency in distributed optimization (federated learning) setup.
Game theory for social client behavior in FL. Some prior work have also considered games with strategic clients participating in FL., focusing on designing mechanisms to prevent clients' social behaviors such as free-riding [104], coalitions [30] or dishonesty [31]. In these works, however, the meaning of the action 2; is completely different from our setup of interest: it represents the size of the dataset which each client contributes to FL [1I, 62, 104], strategy to deceive others and defend against those attacks [31], estimate of the trustworthiness of other clients [6] or willingness to participate in FL [17], all having restrictive meaning in a specific social context. On the other hand, in MpFL, F; are clients' local models to be optimized through learning, where the objectives fa follow general game-the theoretic structure, and our primary focus is to design communication-efiin algorithms for finding an equilibrium.
Heterogeneity and client drift. One fundamental challenge for theory of Local SGD (FedAvg) is heterogeneity, i.e., varying fi's due to differences in local data distributions [67, 78]. Under such setup, Local SGD is prone to client drift [146, 61] where local descent trajectories head toward distinct minima (of local objectives), and convergence theories require either additional assumptions [134, 144, 48, 78] or technical analyses [63, 65] to control this drift. Some papers, based on theoretical insights, introduced or analyzed correction mechanisms for Local SGD to mitigate client drift [61, 41, 101, 100, 55, 47]. Extension of such ideas to federated minimax optimization was explored in [145]. We note that the n-player game setup of MpFL is also fully heterogeneous each player has distinct (possibly even conflicting) objective functions, and consequently, we have the analogous concept of player drift. We refer the readers interested in this topic to the discussion the end of Section 3.2.
FL frameworks with individual models. There are several distinct contexts for FL. frameworks (other than personalized FL) where each client learns an individual model. In Vertical FL [137, 86, 87] scenarios, multiple organizations hold distinct features from the common set of samples and they collaborate to train their each local model. In Federated Transfer Learning [123, 85, 35], the participating organizations similarly keep and train local models, but their datasets have heterogeneity over both sample and feature spaces with limited overlaps. Federated Multi-Tast Learning [124, 91, 98] extends FL to cases where each client solves different, but related tasks.
Fictitious play. The Fictitious Play (FP) is a classical algorithm, originally proposed by [15] to solve minimax games where each player has finite action space and plays mixed (randomized)
28

---

strategies. In FP, each player selects an action that minimizes their expected loss (best response), assuming that the other player plays the empirical (historical) strategy, which is uniform random mixture of their previously played actions. The convergence of FP to Nash equilibrium for minimax games was established in 13], but FP fails to converge for general n-player (with > 2) or non- zero-sum games [121, 58], except for particular cases such as all players having identical objectives [103].
While it may appear that PEARL-SGD is conceptually similar to FP (as each player performing multiple local SGD steps can be interpreted as seeking local approximate best response to others' strategies) the connection is opaque due to some fundamental differences. First, in PEARL-SGD, players make their updates based on only the most recent strategies of other players (not the entire history as in FP). Second, in PEARL-SGD, local SGD steps are not run until players converge to local optima-
results in player drift as we discuss at the end of Section 3.2, and rather avoided by using step-sizes scaling down with the number of local steps. Third, in the FP setting players are assumed have finite action spaces and mixed strategies (corresponding to points on a probability simplex), while the MpFL setting deals with continuous action spaces with pure (non-random) strategies. However, despite distinctions, as FP has been previously studied in the distributed r-player game setup [119], exploring the further connection between MpFL and FP could be an interesting direction.
Federated bilevel optimization. Bilevel optimization is nested problem in which the outer optimization objective depends on the solution to an inner optimization problem [13, 3]. It can be viewed hierarchical game between a leader and a follower and generalizes minimax optimization. Recently, several works have studied bilevel formulations in federated learning (FL) settings [131, 56, 75, 110], with growing focus designing coamuumication-fffiienee single-loop algorithms for federated bilevel optimization [138, 139].
Decoupled SGD. The concurrent work [148] proposes and analyzes the Decoupled SGD algorithm whose update rule coincides with PEARL-SGD. While the exposition of this work emphasizes Decoupled SGDA
version for two-player games, the multiplayer case is considered in their (=": V=x""" v"") for y E RD,, and Appendix C. The paper defines IFy (x) = (V fi (x : ...... V
assuming that Fy is Ø-strongly monotone and (x) - F(x) | < L. - e shows that Decoupled SGD can provide communication acceleration the weakly-coupled regime where Rg = he/p is small (even in the deterministic regime). Despite the algorithmic similarity between PEARL-SGD and Decoupled SGD, our work differs from [148] not only in terms of how technical results are derived, but also in terms of the emphasis. In particular, unlike [ [148), we consider PEARL- SGD as a component of the broader framework of MpFL, which we view as our most significant conceptual contribution.
29

---

B Detailed distinction of MpFL from prior FL setups
Classical FL algorithms are incompatible with MpFL.. We first clarify that classical FL. algo- rithms including Local SGD [94], FedProx [78], SCAFFOLD [61] or Scaffnew [100] are not suitable for the MpFL setting. There the problem is formulated as
minimize ZER
f(z) Σ f(x)).
(FL)
On the other hand, recall that MpFL is formulated as
find DERD
f((1(;=7)) & f((x:;,7"), Val E Ra, vie [n].
(MpFL)
One obvious distinction is that (FL) seeks a single x, E R minimizing the finite sum, while in (MpFL.) each player finds distinct ..... x² satisfying the equilibrium condition. The player i does not update x² for j * in MpFL., so unlike in classical FI., each player only contributes to partial coordinates of the desired solution variants to the MpFL setup.
(x), (x!,...,,??) Therefore, we cannot apply Local SGD or its
Objcctvv value 1.1
2.
Dbjertove value
3.
63
Communicatin
Communication
(a) Local SGD
(b) PEARL-SGD
Figure 4: Plots of objective values f1, in (4) from running (left) Local SGD on the joint variable (u, and (right) PEARL-SGD.
Additionally, it is generally not possible to reach equilibrium by performing SGD the sum of objectives (as in Local SGD). Consider the following simple example with n = clients:
fu / TT (Au
BTv) 20 |ull f2(1; u) ||ell + 2
1 ot eT b) 20 |ul
1
where u E Rd. A > 0 and a, b Rd (we use (u, instead of (x x²) for clearer notation). Running Local SGD with respect to the joint variable (u, v) on the sum } (u, () + /2 v)) results in divergence of one of the objective values (Fig. 4a) while PEARL-SGD converges to the cquilibrium and the objective values stabilize (Fig. 4b). However, although we included this example for illustration, note that here Local SGD is not even conforming the rules of MpFL both clients are updating (u, v) simultaneously.
Federated minimax optimization (FMO) algorithms are incompatible with MpFL. In FMO, the problem is
minimize maximize C(x,y) Ti Σ (x, ZERda
(FMO)
yER"y
In algorithms designed for (FMO) including Local SGDA Local SEG, each client locally updates both the minimization and maximization variables (x* y²), and all clients work collaboratively toward finding the minimax solution (saddle point) of L(x, y), which is global objective. On the other hand, in (MpFL), each player i locally updates only their own action x" for their own individual interest reducing f((:; ")). ") Even though both (FMO) and (MpFL) aim to reach an equilibrium, they are completely different processes from a conceptual level. For example, for the n-player game setup Section 4.1 with n 5, it is not possible to apply Local SGDA Local SEG due to the conceptual mismatch.
30

---

C Omitted proofs for Per-Player Local SGD (PEARL-SGD)
C.1 Key ideas and proof outline
We first provide outline for the proof of Theorem 3.4. The key components of the proof are as follows: (i) we show that a round of local SGD in PEARL-SGD behaves like large single descent step with respect to the joint gradient operator F except for local error terms caused by running multiple SGD steps locally (Lemma C.1), and (ii) we bound these local error terms (Lemma C.2).
Lemma C.I. Assume (SM), and let Liax max L1, ..... Lnd. Let 0 S < R be a fixed round index PEARL-SGD and suppose 7/8 = 7 > for = TP. T + 1) Then for arbitrary >> 0, we have
E [ - x.1l²
X S (1+ (T 1)a7) |xTp - xx112 2 2yT (F(x,p) xrp x.)
yL max +
rpt--1
Σ
||xp
x,11 Xrp]
Xrp X+ l1? x
a
j=rp+1
Local error bound.
The right hand side of the bound in Lemma C.1 involves the quantities
T
Xrp
x,1l
Xrp
>
E |
(5)
for = = l,... T(p 1). We further bound (5) using the following result.
Lemma C.2. Suppose Assumptions (CVX), (SM) and (BV) hold. For fixed i E [n] and a fixed communication round p in PEARL-SGD, suppose 76 = 7 for h: = .p..... 7(p 0 "P.....7(PP
+ 1) - 1, where
< 7 +, min
} Then for / O,....T,
E | =lptell
+ (1 + 1)(t + 1)) of. Xrp] S 202 V 2 mlll
Here we sketch the proof Lemma C.2 and clarify role Assumption (CVX). By assuming that each f((:;2pp) is convex and L--smooth, can prove Lemma C.3, showing that the expectation of squared gradient norm is "almost" nonincreasing along the local SGD steps, except for some additional term due stochasticity. Then, rewrite each summand in (5) as
E || - 11 X
E
?
o3 jmrp
Σ
Xyp
=
2
Σ
V (z);
Xxp
(6)
and use Lemma C.3 to bound (6).
Lemma C.3. Under the assumptions of Lemma C.2, for j = Tp 1...., 7(p + 1),
E [|
x < [| + 2(j L,o?
Given (6), it is tempting to apply Jensen's inequality to the rightmost quantity and then apply Lemma C.3. However, this results in a bound that looser than our Lemma C.2. We need more careful arguments regarding the expectations, which detail throughout Appendix C.
Remark.
31

---

Proof outline for Theorem 3.4. We combine Lemmas C. and C.2, and then apply (SCO) to eliminate the ||F(x=p)]] terms to obtain
[|xx<p+1) - x.12² XTp S (1+ (T (T- 11)a)) ||-p - x,Il² (terms proportional to o²)
27 - -2 7 max 2² 1)
(F(X,p). Xrp - -x.) (7)
3a
Provided that C 2 0, we upper bound the second line of (7) by -Cp ||x,p x,1l using (QSM).
Then we choose a yr Imaax / _ which minimizes the resulting coefficient of X x, 1. and rewrite it in the form 1 - YT,U. Finally, take expectation over X in (7) and unroll the recursion. O
The proofs of Lemmas C.I, C.2 and C.3 and the detailed full proof of Theorem 3.4 are presented through the following subsections.
C.2 Proof of Lemma C.1
Note that for k = Tp+ ,,...,,( T + 1) (iterations between p-th and (p + 1)-th communications), we have
n
XR - 11
1 - x1112
1=1
1rp x¹ (x + ?
Σ
[| | - x 1| 2 2(x - x Fo xx)) + 1, ax 11²)
1=1
| x,112- 2% Σ
(1 x², .99) Σ b zill?
(8)
1=Tp
where for the last equality, we use
9} v Si.e
j = TD,..... .p....... i= I....,n
and
j+1 = 2zj ~99}, j TP......, 1, i= =1..... I....,n
rewrite wtp x1. = Σソ k-1
J/.- Note that we have
E (0+p x', gtp) xxppl (o'r I"_, fa x
while for the other indices = Tp + 1.....k 1, we have the upper bound
E [ (1to n/, Ø |af]]
(x'pp x, fi x
(oip xt, V (xtp: 2 اا
S (1 x, V f. v x ا
a
||
z1|1² +
V fi( -
V f((()
2
2a
L7
< (st + v :p: m
|
=1
|
x ||?
2
2a
where in the fourth line, we use Young's inequality with an arbitrary a > 0 that we determine later. Take expectations of the both sides in (8) (conditioned X,p), and apply the above bound with the
32

---

tower rule to obtain
E Xk x XTp
k-1
$ |rpp
x. 112
2
TTp x ((( 27
Σ
Σ
- - 111
i=1 j=7p
i=1
1=
(9)
k-1
+ +
E
-
-
Xrp
+ +
E
1 -
Xrp
2a
i= j=rp+1
i=1
Now we apply the identities
xmp) = (xxxp - -x,, F(xrp)))
Σ
Fipp
x12l1" = Xxp
x.1
==1
E
11 X
=
||x,p
X 12 XTp
and the inequality
L2 2a
I max
k-1
Σ
E
23 112
Xxp 1
Σ
Σ
||
- 2511 xxp
2a
iml j rp+1
j smpp+1 iml
I
k-1
Σ
11 x
xxp
2a
j rp+l
to (9) and plug r(p + 1), which gives the desired result.
C.3
General properties and bounds for SGD
In this section, we present some general properties of stochastic gradient descent (SGD) for an T-smooth, convex function f: R R. Suppose that have stochastic oracle f(()) for the gradient operator (.),,, satisfying
Eg Eg|V = Vf(),, Eç [[[](((( vf(a) spp Vr Rm
(10)
where Eg denotes the expectation with respect to randomness in ç. This setup and the subsequent results are the abstractions of intermediate results that we need for the proofs of Lemma C.3 and Lemma C.2. Specifically, we will later use the results of this section with
5() f((55)))
for each 1,..., n. We make this abstraction simplify notations and to more effectively convey the key intuitions underlying the analyses.
Lemma C.4. Let f: R IR be convex and L-smooth. Suppose that stochastic gradient oracle
(.)( satisfies (10). Let = x VV)(),) where < <> S Z. Then we have
Eg [IVS < [=)] 22
Proof. It well-known that if convex and L-smooth, then V is 1 -cccoerrevee, i.e., for any N, E Rm
1
xx -
33

---

By cocoercivity and the size condition S E. we have
2 [V)(x) V
$ L VV(x)) -V/(()) V
S (æ y, Vf(x)= Vf(w))
(>V)g(()), Vf(x)= Vf(w))
= 7 ((Vfe(x), vf(=)) VV)))
Vf(m)) + VV(
Taking expectation of the both sides, obtain
Es
7 [V
VS(1I
- - Vf())
(f(())))))(
=>][Vf(>)] >Eg (V)()), vf(y))] + + (V) VV(
Cancelling out the terms and dividing both sides by 3. we then have
E [V((2))
< [VVf(=]] 2E [Vf(x)
Vf(())
(II)
Now observe that
Eg V/
because Vff(2 - VVf(=) non-random quantity and (z) Vf(x))] Then
Es [[(1f))---((000))))-/-/---V-vv-
Eş [IlV [L
E [IIV f(z) - ff((=))
LEE [V] v
=
and plugging this into (11) completes the proof.
Lemma C.5. Let f: m - be convex and T-smooth and let the stochastic gradient oracle f+e()) satisfy (10). Let xo R" be any initial point, 0 I Z. and æ1, ....... be sequence generated by the stochastic gradient descent algorithm
Is+1 Is y VV. (z.)
for O,...,t 1. Then have
E [[+(2=)) s [[V)(z))] L0
for s = t-
Proof. Apply Lemma C.4 recursively and use the tower rule (law of total expectation).
Lemma C.6. Let f: R + R be L-smooth and let zo..... Iz be sequence generated by
stochastic gradient descent
Fe+1 Fs VV, (xx)
where the stochastic gradient oracle satisfies (10). Let â. f....., it be generated via deterministic gradient descent
$ S. (((..)
34

---

where Ty = zg. Then, provided that 0<7 S L(r-1) we have
1-1
||,, - xell S 37
Σ
[V)))(())) v((x,))l
sm0
Remark. This result only assumes L-smoothness of (which is L-Lipschitz continuity of f) and does not require convexity.
Proof. When t 1, we have | - 2:11 (VVf V fx(o)) zo 20.
Now assume > Observe that
Ft f = ( f2-1) - (V (x - v
(#t-1 fi2-1) (V (04-1) - Vf(x(-1) -
and therefore,
| 8.1l & 1 - 2/1 + [
+ + ( - V
- (1 + 7 | - - || + 7 (x - (f
where the last inequality the fact 100 Rol = we obtain
the I-smoothness assumption. Now unrolling the recursion and using
1-1
| - 8,11 v
711 + - Σ
[VSe, vs(2,))
==0
1
$
1 +
(z.)
t t-1
1-1
37
Vfe. (x.) vfx)))
0=0
Lemma C.7. Under the assumptions of Lemma C.6, we have
[(V (xxa), ( ((x))) s Lpp
Proof. Observe that because dt defined in Lemma C.6 is non-random quantity and fe. fzro) = 0,
we have
(x. - (zo), Vf++)) = 0.
Using this, we can proceed as in the following to obtain the desired bound:
E KV fço (za) - Vf(zx), fxx))))
[ Seo (zo) Vf(o)), Vz(x;) f(a))
< E V fea (zo) [x(2))] [V ff())l
EE S (xr) [ || -fell
< 33YEE
[V vx(20)) Σ
|V (x.) vf(ca))]
V (20) - (
[V (x.)) Vs(xx))1
< 3YYE
2
2
< Tp?
35

---

Lemma C.8. Under the assumptions of Lemma C.6, we have
27
|100 zell =
Σ ff(z))
+ + + (t 1)t(t + Lp?
Proof. In the case (= = 1, we have
E [ xn |1]] = 2 &o S (zn)) < 7 [
which is the desired statement. Now use induction t. Suppose that the result holds for any initial point and steps of SGD. Consider sequence 20...., T++1 generated via SGD with initial point za and step-size O. Observe that
E |1:00
xetall 1?]
v fe, (x.a
- EE, 2 {
Σ Ve. (z.)) (
+IV )
???
V Se. (2xx)
Zt
<E [1 22ll"]
+ T²E 2 ((r))) [vee((s)) +|[[[(0))] >
+ 0²
(12)
a=0
where the third line uses the tower rule. Now observe that for s 0, O 1,
E((Vf(x=), Ve., = ((v)) (f(x))) + ((V -V((a))
[ [ Vf(z)) x.]]
S E (VV (ax), +((-))))(((((()))))))
where the last inequality uses Lemma C.7 (with x, regarded as initial point of the stochastic gradient descent). Now we apply this inequality and the induction hypothesis to (12):
||:00 x++1ll [1]
S >>²
(x.)
1)t(t+ + (t) 1)x
Σ (2(V)(z)), vf(x.)) + 6(t + + p²
+
= =p (tp² + (t - 1)1(t + 1> + 31(1 + Lp + +
1-1
+ "
Σ vx(ss)
+2
Vf(x.) vf(mm)
+ |[
= (t + 1)p²
t(t + 1)(t+)))) Lp² + +
Σ (xx))
where for the first equality use Ex=1 6(t -s) 3tt(t 1). This completes the induction.
36

---

Lemma C.9. Let f: Imm R be convex and L-smooth, and let zo E I be any initial point. Let F Ft be generated by stochastic gradient descent
To+1
VV Se. (1a)
with 0 < S min {1, } Then
E || - zell2] s 72² [V + 2(t 1)(t + 1)
Proof. Lemma C.8 gives
1-1
17
11000
Σ
(((a))
+ + + (1 1)((4+ 1)p2
(13)
Next, by Jensen's inequality and Lemma C.5,
E
ff(x))
E
V (z.))l
==0
[Vf(2))] + +20T
$ 8 | f + -))u(t+ 1)yLp²
where the last inequality uses Σ 2s t(t 1) (t - 1) + 1). Applying the above inequality to (13) we obtain the desired result.
C.4 Proofs of Lemmas C.3 and C.2
Proof of Lemma C.3. Observe that given Xyp, the sequence o =tp...., It 7(++1) is sequence generated via stochastic gradient descent
+ = x²J - 7 VVse, (19)
for the L,-shooth convex function f1(3),7)), with di, as initial point, using the stochastic ora- cle (: ==))) satisfying (BV) (unbiased estimator of f((=z=))) with variance at most of). Therefore, we can apply Lemma C.5 with
f(-) f)(
2. 2/
L,
7p
and this immediately proves the desired statement. (Note that is replaced with Tp because ur) is obtained by j .T
-Tp steps of SGD from r
Proof of Lemma C.2. This direct consequence of Lemma C.9 with same choice of f. p², xo and as in the proof of Lemma C.3 and F, = x -pp+t
37

---

C.5 Remaining details in proof of Theorem 3.4
Note that the step-size condition of Lemma C.2 is satisfied by our step-size selection, as y <
2
[m)x(r-1) (because A 2 1). Now combine Lemmas C.1 and C.2 to obtain
tr+2(7 -=+2(r-1)lmae 1)bmaxx
[ - x. 122 Xrp
$ (1 + + 1)) x>pp x+11² - 27T (X=p - x+: F((xp))
1(p+1)-1 n 7
Σ
(706 rp)² || # - - -1p -1p---+++110 - 11t4))
rp-
a
j=rpt1
(
Vf : 2 1| || + - (1 + 2(T - -
i=1
$ (1 + an((T - 1)) || |xpp x+11² - 27T (xxp - Xx, F(xxp)) + (72,2+
1))
[+((+,))) )1
30
+ + (T - 1myxmmxx (2(++1)+
Tmmxx
+ II
(T (r+1)3)) 0²
2a
2a
(14)
where for the last incquality, we replace all occurrences of Li's by Lma max L1 L and use the identities
[[X =
to eliminate the summations Eis and use the following elementary summation results:
r(p+1)-1
(j - rp)² = (T 1)r(2r 1)
(r 1)r²
Σ
3
J=rp=1
(p+1)-1
Σ (j-rp) (r 1)T
2
j=rp+1
and
((+1)-1
- - - (T (T-2)(T
2)(T 1)T(T
(r- 1)T(T + 1)?
Σ
<
2
j=rp+1
Now in (14), we use the assumption (SCO) to bound
3.2 max
12 11)
-2 (x+p x,, F(xp(x +
2272
|1
3a
- 27T 8 {(2322 73 322 maxx
1 (2 (()- ))) (xrp xx, F(xrp))
30
x2 2T max
-T (2 2 -er
7lr
(X>p x,, F(x+p))
(15)
3x
Provided that
2 - 7eT
2TT2
max
7(T - 1)
> 0,
(16)
3a
we can again upper bound (15) using the assumption (QSM):
ELL max
T(T -1) 1)
-5 2 - 7LT
(Xpp x., F(x-p))
3a
2012 max max
(T -1)
S -77 2 2--Ee-
11
111 x.11.
3a
38

---

We plug this into (14) and rearrange the terms to obtain
[x++))+))) x-11? XTp
1 1 -1) 11-1) yT (2 2-7-7- 2 max T(T - 1) #1 | x.11
30
(17)
+ 7²r 1+ (T (1+(T-1))l 1mxx 2(T
Lmax
+
(T + 1)+
0?.
2(x
2a
Now, we optimize the coefficient of the ||xTp x.1l term (17) by taking
2 max
1)ps
Ej1
a = argmin a 1)+
= 7T Lmaxx V
3a
3
a>u
With this choice of a, the bound (17) becomes
E ||x+(++1)
-x.
Xrp
(1 7Tp
i --- 2(T 1
1x<p x,11
3/1
+ 7²r (1+(T- 11-yLmmax 2((++)+
Immuxc + 1)2
o²
27T 2YTV/4 4p/3
2T eu//3
$ (1 (I-TTp() ||xpp x1 + 2T0 ( 1)
(47TLmex +
Liax
YT L
2T 2T/33
veu/3
(18)
where for the last inequality,
1 S 27 and make the substitution
2 2-2-~l 2(T - 1)7 V
=
3p = 2 YET - 2(T
v 1c/3.
Note that with our choice a = YT LTxx V satisfied because
fu and < 7 < [r-2( - Lmme v
the condition (16) is
2T max
7(7 -1) 22- 2012 2 T(T -
2 - 7ET
3a
3a
7er (T 1 1)7 max
3/4
22 - ? (eT + (T - 1) L) VTl > 0.
Finally, unrolling the recursion (18) using the following simple lemma, with ap = ||x>p - xx11
A TPC and
Veu/3 ))
B B= [1+(r-1) (4yTLuax + I
YT T22 Tmmax
27 /2/33
gives the desired rate. (Note that 74 = YTTU- S 7T/(( 7LT) S xeT((2 - xer) S 1.)
Lemma C.10. Let y, A, B.B 0 with 7A < 1. If sequence 0o. ... ag R satisfies
0p+1 < (1 - 7A)a, + TB
for p O,..,,
.,. R then ag 5 71- R =B
39

---

Proof of Lemma C.10. As there is nothing to prove if yA = 1, suppose 7A < 1. Recursively applying the given inequality we have
ag (1-
ag + + Σ (1 YA)P.
Now apply the bound Σ (1 - 71-7A) - Ep= (1 - 7A)P = 1-
1 to the above
inequality.
C.6 Proof of Corollary 3.5
First, because 77 KT, we have
1
1
Y
$
pMr (1
2.maxx vlu
et (1
2kmaax Vep
lr + - 1) L)Lx v
Ł7 + + L)
Hence we can apply Theorem 3.4. Now observe that <> 7/ (ET + 2((T 1)x V and (1 - u)" Se Se-ut -ull for u < 1, so
1
4(log (1 22)2 = (1 q)2
(1++
(1 (I-)T S TUSTR Se ~TT =6 = -2log
1
T
T2
where we use T = 2(1 + 2g)) log 17 and remove the factor log n < log T within the Ô notation. Next, for the terms proportional to o², we have
Imuax
YT Liaxx
7a²
1+ (T 1
Lmxx +
2r
/tp/3
Ven/3
2
v3g
1 T 7
4yT +
+ V3yTLmaxq
2r
2
V39
72 (4 \/3g) +
1+
2
11
0 + /3q/2)
72 2 (4 + v3q)
1pn(1 + 29)
1311211 (1+ 29)²
δ (1 + 9)o²
(1 q) Lmmxx TT
2T
Combining these with Theorem 3.4 we arrive at the desired conclusion.
C.7 Proof of Theorem 3.6
Note that we use constant step-size ? = Trp within each communication round p, i.e. for Tp S k S
T(P + 1) - 1, so we can apply the bound (18) from the proof of Theorem 3.4, provided that
Ppp 2
& + 2(T 1)
This clearly holds true when < 2(11 + 2q) 1, and when 2 2(1 + 2q) 1 then
1 2p+1 +1 < Tup+1
Prp Tp (p +12
T/ (1 2g)x tr + 2T Lmmax V
so we see that the step-size condition is satisfied. Furthermore we have
Sop = -r - 2(T 1)7rp Imxx v k/3 > 1,
40

---

so (18), with
Lmax and taking expectation with respect to Xyp. gives vtp
[f(++11 -x. x. 12] - (1 1i-TTT/UUrppEE |1x00- - -x.11
+ 2ZpT0? (1 I [ (r-1) Irpp v3g) + v3
2Tg
1 (1 - -/rTT/) [1xTpp - xil1? + +1+ 1)= To² + 4(1 2) 1)
(19)
2p+1 For + (01++2)n: 1, plugging in 7sp ry (p+1)2 we obtain
p²
+ (2p + 11 + 9) (1 1+ 4(T 1) (2p
[|x+(p+1)- -x. 12] I (p + 1)2
1|*Tp - x111
TT² (p + 1)2
plp + 1)2
Multiplying (p + 2)² to both sides and upper-bounding
20+1 p+1
S 2, we obtain
(T(p + E))²E ||x+<p+1] - x. 111 - (Tp) |>, - 1²]
4(1 4)1+g)50² g)5o²
(1+ 8(T 1) u(p +
4²
Let po - [2(1 2g)x 11. Chaining the above inequality for p Po...., R - 1 gives
(E [|XTR -x.11²
x.11²]
+ 4(1 + q)T(R - -Pojo²
32(1 + q)T(T - Lmax 0²
R-1 1
$ (TPO))
||x/p0 - xx113]
112
1
p+1
+ 4(1 + q) po)O²
32(1 Lmax 0² log (R/Po)
S <T ||x-p00
||xrp0-Xx111 - x1|
1²
where we use Ep-p p-1 S J dp
log R Now substitute T = 7 R using the upper bounds
T(R - (p)) S 7R -= T and log( R//po) S log T, we can write
E |xx - x.11²]
s -x.1=
2 ||xTpo - x, 12]
4(1 To² 32(1 + q)r² T m log T
4²
3
(20)
As ?/ is constantly "o (-(1-2g] over rounds p= O,.., Po 1, we can directly apply Theorem 3.4
with R = Po and similar simplification of the -2tterms as in (19) to bound
Pa
(1 + 1)02
E [|xxPo x.11] <
1
x,1
(1 + 4T 1)nas)
E(1
2q)
1
1
x(1+2g)
o²
( 1+ 4(T - 11)4max
1
11x0 - x1,12+ +
xil + +24
ENT
E(1 11++29 2q)
Xx
x,11?
σ²
27
e +
1 +
VR
where the second line uses Pa > 2(1 + 2q)x
2 x(1 [1 + 24), and the third line uses the bound
(1 - 1)' < for t > 1 and 4(r- 1) maa
/gr
< 2T
2T
2r.
Now plugging this into (20)
((1+
((1+2g)
vk
and dividing both sides by 72 we obtain
||xT - 11
18 l|xo x.112
T2i02 ( ETTT2
2T
4(1 + 2)22
32(1 + 2))7Lmmxx log T
1
cT2
VR
22T
11372
< 4(1 + x2? ||x0
x. |
4(1 + 0)
4(1 + 2q) 29) 2TT2
2T
32(1 + 9) Lmax log T
(1+**))
+
cT2
12T
122
VK
which is the desired result.
41

---

D Details of Numerical Experiments
Experiments were conducted using a personal MacBook with an Apple M3 chip and 16GB RAM.
D.1 Quadratic n-player game
We set n = 5, = 10 and M = 100. The matrices A.m are generated randomly with their eigenvalues in the range juA, LA] (0 μa LA). Similarly, for 1 S i < S n,, generate the matrices B,.. randomly with their eigenvalues in [0, BB] Notably, we set Bj...m = - B j. for 1 j < E n. With this condition, we can ensure that the n-player game (2) satisfies the (QSM) assumption, regardless of the values of MA. LA and LB. We show below why this is the case.
Recall that we have
Si [((x".....,x))
1 2 (x' Axx") + xa) + Ex' (E',,igg)) Bigad) r²)
iti
for = I,..., Differentiating fi with respect to x², we get
Vfi(xt;= A,r' + az
Σ
B Baa
and thus
Vf((''==>)> -V/(((;)))) Asa² + Σ Bijad
A ai + Σ Biia!!
1+1
Ai(x" -x()) +
B Bi,s -x()
jti
and
(F(x) F(x,),x x x.)
-
),, x¹¹)
Σ d x()) +
(x" x. Bid
i=1
jzt
Now, the double summation term vanishes because for any + j.
(x* (z, =2)) (I' x B (x² xx1)) =
due to the condition B = B. Therefore, provided that each A, ž ul we see that FF satisfies (QSM) (in fact, the same argument with arbitrary y in place of x, shows that FF j-strongly monotone).
D.2 Distributed mobile robot control
We follow the same choice of parameter values at, by, anne hu within (3) from [60]: 10 + i/6, by = i/6,
(minc 2ancr znnes A
Jnnes rnn)) = (1, -4,8, 8, -9, 13)
and
5
-8
5
0
-6
-9
(hi 181555
6
-4
13155
9
2
-7
0
-2
9
We add Gaussian noise with 2² 100 to the gradients to simulate stochasticity. this setup, all our theoretical assumptions satisfied [60].
42

---

E Additional Experiments
E.1 Quadratic n-player game with step-size tuning
In this experiment, we simulate the scenario where we do not know the precise theoretical parameters in advance, For each {1, 2, 4, 5, 8, 20). we tune 7 by running PEARL-SGD with each y {10-1, 10 10-6), and plot the best relative eтror "=,,-x.1"/IIxxxx, II (g-axis) versus the communication round index p (æ-axis).. Figure 5a presents results from Deterministic PEARL-SGD, and Figure 5b presents results under stochasticity, imposed by mini-batching from the finite sum. The results demonstrate that practice, we can use (T, 7) as tunable hyperparameters to achieve the best communication complexity.
Relative Emor
Relative Error
20-1
T=1 r=2
[=1
r=2
T-4
20
r=B
T-20
T-20
1002 2020
3000
5300
5003
2000 4000 5000 8007 10350 12300 54300
Communication Rounds
Communication Rounds
(a) Deterministic setup
(b) Stochastic setup
Figure 5: Performance plots for PEARL-SGD on the n-player game (2) with different values of For each we use the empirically tuned step-size {10-1 10-2 10 6} for the best relative error xx--xx setup.
Figure 5a shows the result from deterministic setup and 5b shows the stochastic
1xo-x.11-
E.2
Distributed mobile robot control
Player
In Fig. 6, we plot the local objective values f: in the setup (3) obtained from PEARL-SGD for each robot (player) = 1,....5 5 in the case games, the objectives fi can have both cooperative and competitive components. After the cooperative components each J/ are sufficiently reduced, ft's oscillate due to the competing interests of players until an equilibrium is found, and then finally stabilize around a certain level.
Functioonal Value ue
to
Player
Player
Player
5. Generally
Communication Rounds
Figure 6: Local objective fi in mobile robot control setup.
43

---

F Discussion on Theoretical Assumptions
F.1 Possible simplification of assumptions: Assuming cocoercivity F
In fact, the convergence of PEARL-SGD can still be proved even if the three assumptions (CVX), (SM) and (SCO) are replaced with the single assumption that FF; R RD is {-cocoercive, i.c..
(F(x) F(y). x y) 2 ||x x ||l,, YXYERR
(COCO)
In the subsequent paragraphs, we explain in detail why this the case. However, we emphasize here that if we derived all convergence theory using (COCO) in place of (CVX), (SM) and (SCO) and did not distinguish the role of L,'s 's (the local Lipschitzness parameters from (SM)) from that of E, then the resulting convergence rates would have become much more pessimistic (worse) in many cases. Therefore, in our work, we choose to use the current set of assumptions. allows us to more clearly present the tight dependency of convergence rates to Lj" s. Also note that assuming (CVX), (SM) and (SCO) is strictly more general than assuming (COCO), as we illustrate in Appendix F.2.
(COCO) implies (CVX), (SM) and (SCO). Trivially, (COCO) implies (SCO). Furthermore, if F is -occoecciv,, then is monotone:
(F(x) - F(y), y) 2 0, E
(21)
and E-Lipschitz continuous:
F(x) - F(y)ll S - Vx,e
(22)
In particular, for each 1,...,,,, n, we can take
x= (x x.' x², x ++1
x²); y= = (x'...., x' , ,..,,"")
(23)
in (21), which gives
(f((('22=)) - Vf( ) -v²) 2 0
for any af, y" E RRd and x² E RD That is, the gradient of Je(:;x==); IRd, + IR is a monotone operator on &e and this implies that f=( is convex, i.e., (CVX) holds. Similarly, plugging the choice (23) into (22) we obtain
[Vfí(=";=>) fal'' 2 :>> S -e||=' -
showing that (SM) holds, with L; l. Therefore, all theorems from the main paper hold under the assumptions (QSM), (COCO), and (BV), with l in place of Lmax in step-size restrictions and convergence rates.
What do we lose by replacing Lmax with E? The previous discussion shows that we can assume (COCO) and replace all occurrences of Lmax with within the theory. In this case, however, the step-size conditions in Theorems 3.3 and 3.4 become
7 {(T + 2(T 1(T=1))x))) ()))-))))-0>) (E
(24)
and the VK factor in the denominator is undesirable as it significantly restricts the range of step-size one can use if k is large. Furthermore, in Corollary 3.5 and Theorem 3.6, the factor g becomes
Vi, causing the constant factors in the convergence bounds to potentially become large.
However, there are many cases where Lmax < f, showing why it is beneficial to keep the dependency on Lmax tight as we do. As an abstract example, when a generic μ--strongly monotone and M- M-Lipschitz continuous operator, the tight (smallest) cocoercivity parameter one can guarantee IF l = M / u [33] (tightness can be shown using, e.g., the scaled relative graph theory in [115], [114, Chapter 13]). On the other hand, we have
F(x) - F(y)l
F(x)
F(y)l
Tima < max
sup
< sup x
M,
X
yll
x
yll
44

---

ie.. .M is an upper bound on Lmax (better than E). Therefore, e is at least M
2 +
Vk times
vtz
larger than mmxx, and the largest step-size allowed in Theorems 3.3 and 3.4 is
èT 2(T T)Tmux
which in contrast with (24) where we used in place of Lmax and obtained vk times smaller step-size range. Additionally, note that this case q = Laax Limax in Corollary 3.5 and Theorem 3.6, so we can avoid the k-dependent factors appearing in the convergence results.
vip
We demonstrate another problem class for which Lmax < t. Consider two-player matrix game, regularized by adding strongly convex (resp. strongly concave) quadratic terms in x (resp. y):
minimize maximize L(u, r) 2 "ER"
|/ll² + g + u B - hTv 2 |101
(25)
vE
where B E RR .g.h R In n-player game notation, the first and second players [(xt, x²2) and f=(x;==*) = - -L(x* , In
respectively use the objective function xx² = this case, the operator IF is p-strongly monotone with μ and M M-Lischhitz continuous with parameter
M 2 V |BI|2 μ² 2 |B Note that the cocoercivity parameter É is at least M (and at most M /b). On the other hand,
V = px² + + B.², V=a(="=²')= - px= + BTx
so the Lipschitz constant for Vfi with x² fixed (resp. V/2 with x² fixed) is p. i.e., Lmax p. Therefore, we have Lmax < in this scenario, as strength of regularization is usually small
compared the smoothness parameter M. The same principle applies the n-player analogue of this setup we use in Section 4. where each player has the objective function
1 (s', A,at) + xa,, + Σ (z',B,zz²) 2
13JS
with B,, = -B. the quadratic terms are the small regularization terms introduced induce convergence, so that A, = μI with μ < |Ba then we have Lmax = μ < max:4j [Ba,illg S
F.2 Example of non-cocoercive satisfying (CVX), (SM), (QSM) and (SCO)
Consider the two-player game where two players have the objectives
2²
fi v) 2 (p))
2
f2(1; 2 p(u))
where yp: + I is defined by
(tt) (n + (e sin't).
Here 0 0 μ < f, and we use the notation x = (u, v) E R x R instead of x = (x²,2²) for better readability, Note that because ip satisfies
0 0< (t) < l, V R,
(((,)) u): R + IR is convex (quadratic) for any R, and so is fe(u,)) for any E IR. Therefore, this game satisfies (CVX). For any x = (u, v). we have
F(x) = (u: v). V.fz(e; u)) = (up()),
Therefore, the unique equilibrium of the game is x. (u., v.) (0, Additionally, observe that
fuu u) = p(v) E [n, E) Verfe(u; = p(() E in, 4..
In particular, the both second derivatives are bounded, so (SM) is satisfied. Next, we have ((x), x.) = (e)( + p ulu² + +²)
x,11 2
45

---

i.., IF satisfies (QSM). Finally, we have
[[()]]] u² x()²² v² p(()² max(p(()) (u²v(v) v(()) SE(F(x), x xx), showing that F satisfies (SCO).
On the other hand, IF is not cocoercive with respect to any parameter; in fact, is not even Lipschitz continuous nor monotone. Observe that the cross-derivatives
Vu;fi(u; = (E - p)u sin()
Voufz(u;)) = - ((-
are unbounded over R R. so cannot be Lipschitz continuous with any fixed parameter. Furthermore, we have
20(v) (DF + DFT) (u (e (innn((()) uinn(2u))
(e- (1-)(usin(2)))) + sinn(2u))
20(u))
so with vツ = (2N + 1)) n, we have
det (DF + DFT) (u, v) =4p² ((2N 2N 2) 1) -4(e- m)2
1
2N + 1 n²
1 162 - 4(l - 11) 2N + 2 x
provided that N is sufficiently large. As differentiable operator F is monotone if and only if DF DFFT 2 0 everywhere [114], this shows that IF is not monotone.
Note that while provided two- two-player example for simplicity, same ideas to construct a non-cocoercive r-player game satisfying our assumptions with any n For example, we can choose (xt;;x² (x')² p(xtt)) where we identify x=*1 xt.
easily use the essentially
46


Reviews:
[{"review_id": "eadaUKFOEH", "reviewer": "Reviewer_v3ed", "summary": "This paper introduces Multiplayer Federated Learning (MpFL), a game-theoretic framework for federated learning where clients are viewed as strategic players with possibly misaligned objectives. The authors propose a communication-efficient algorithm, PEARL-SGD, and prove convergence guarantees in both deterministic and stochastic regimes under standard game-theoretic assumptions (QSM, SCO). The algorithm is validated on synthetic and control-theoretic examples.", "questions": "1. In section 2.2, the authors mentioned the relation between MpFL and federated minimax problem, where the later seems to be a special case in the MpFL framework (2-player). Does it mean that in federated minimax problems, the players are different from the clients (computing agents)?\n\n\n2. Since bilevel optimization is essentially a two-player (leader-follower) Stackelberg game, what is the relation between MpFL and federated bilevel optimization (FBO) [1,2,3] problems? Is FBO a special case of MpFL, just like federated minimax problem?\n\n[1] Tarzanagh et al. FedNest: Federated Bilevel, Minimax, and Compositional Optimization. ICML 2022.\n\n[2] Qiu et al. Zeroth-Order Methods for Nondifferentiable, Nonconvex, and Hierarchical Federated Optimization. NeurIPS 2023.\n\n[3] Yang et al. First-Order Federated Bilevel Learning. AAAI 2025.\n\n\n3. As I mensioned in the Weaknesses 1, the lack of numerical comparison would weaken the paper. Is it possible to add some comparison under special cases (eg. 2-player minimax problem)? Can MpFL address them as well? I believe adding comparisons would strengthen the numerics significantly.", "limitations": "Yes, discussed.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "### Strengths:\n\n1. MpFL addresses a gap in the FL literature by modeling non-cooperative clients via an n-player game formulation. It generalizes classical FL and personalized FL under a rigorous game-theoretic framework.\n\n2. The paper provides linear convergence to a neighborhood under constant step-size and exact convergence under decreasing step-size, improving over classical local SGD in heterogeneity settings.\n\n3. Quantifies how larger communication intervals (τ) can lead to reduced communication without compromising performance.\n\n4. The heatmap visualization is insightful, showing the trade-off between step-size and communication frequency.\n\n### Weaknesses\n\n1. The experiments are too synthetic and not representative of typical federated learning applications. No comparison to recent FL methods that incorporate strategic or incentive-aware behavior (e.g., [10], [29]).\n\n2. Assumptions might be restrictive, some discussion or justification on when they hold in practice would help.\n\n3. The authors admit the method suits small-n, cross-silo setups, but don’t address general scalability. More discussion is needed.", "was_revised": true, "final_justification": "The framework this work proposes is novel and interesting. I will maintain my rating as accept.", "rebuttal": "We sincerely thank the reviewer for the positive evaluation, constructive feedback, and their time and effort spent reviewing. We are delighted to see that the reviewer views our work as correctly addressing a missing part in the FL literature. Below, we provide responses to each point mentioned by the reviewer.\n\n## Weaknesses\n\n> 1. The experiments are too synthetic and not representative of typical federated learning applications. No comparison to recent FL methods that incorporate strategic or incentive-aware behavior (e.g., [10], [29]).\n\nOur experiment setup has been considered very often in the multiplayer games literature [1, 2] and minimax optimization community [3, 4]. While it is synthetic, it is a standard testbed used in the literature and it successfully highlights the communication gain attained by PEARL-SGD.\n\nRegarding the methods considering strategic and incentive-aware clients, including [5, 6] (respectively cited as [10, 29] in the paper), we would like to refer the reviewer our related paragraph in Appendix A (lines 1060-1069), discussing why direct experimental comparison with them was not adequate for this paper. We believe that the connection is interesting and MpFL may potentially incorporate those prior work, but at the moment, our focus — communication-efficient equilibrium search in general games — is largely different from theirs.\n\n[1] Salehisadaghiani & Pavel. Distributed Nash equilibrium seeking: A gossip-based algorithm. Automatica, 2016.\n\n[2] Ye & Hu. Distributed Nash equilibrium seeking by a consensus based approach. IEEE Transactions on Automatic Control, 2017.\n\n[3] Mokhtari et al. A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach. AISTATS, 2020.\n\n[4] Beznosikov et al. Stochastic gradient descent-ascent: Unified theory and new efficient methods. AISTATS, 2023.\n\n[5] Blum et al. One for one, or all for all: Equilibria and optimality of collaboration in federated learning. ICML 2022.\n\n[6] Dorner et al. Incentivizing Honesty among Competitors in Collaborative Learning and Optimization. NeurIPS, 2023.\n\n> 2. Assumptions might be restrictive, some discussion or justification on when they hold in practice would help.\n\nWe do work on a specific set of assumptions, which are standard in the literature on stochastic gradient descent-ascent type methods. These assumptions are not intended to be directly applied to practical models (neural networks). Our analysis parallels how numerous theoretical works in classical FL have been done [7, 8, 9], assuming strong convexity while primary applications are ML models. Please note that our primary goal is to present a novel framework under an idealized setup (understanding the simple setting first will allow the community to build on strong foundations).\n\n[7] Stich. Local SGD converges fast and communicates little. ICLR, 2019.\n\n[8] Khaled et al. Tighter theory for local SGD … data. AISTATS, 2020.\n\n[9] Karimireddy et al. SCAFFOLD:  … federated learning. ICML, 2020.\n\n> 3. The authors admit the method suits small-n, cross-silo setups, but don’t address general scalability. More discussion is needed.\n\nAs we mentioned in lines 192-202, the communication cost will grow linearly with the number of players $n$, which limits the scalability of MpFL in its basic form. However, (as we also discuss in lines 192-202) we believe that this could be resolved using techniques such as gradient compression or random sampling of the players performing the local updates.\n\n## Questions\n\n> 1. In section 2.2, the authors mentioned the relation between MpFL and federated minimax problem, where the latter seems to be a special case in the MpFL framework (2-player). Does it mean that in federated minimax problems, the players are different from the clients (computing agents)?\n\nIn MpFL, the clients of FL act as individual players of the game, while in federated minimax optimization (FMO) each client has access to both (min and max) players’ objective functions and their actions/strategies. So **yes, in FMO, players and clients are distinct concepts, but in MpFL, clients are players, aiming to minimize their own local objectives by adjusting their actions.** \n\n> 2. Since bilevel optimization is essentially a two-player (leader-follower) Stackelberg game, what is the relation between MpFL and federated bilevel optimization (FBO) problems? Is FBO a special case of MpFL, just like federated minimax problem?\n\n\nIndeed, bilevel optimization is a two-player game with hierarchical structure. Therefore, MpFL is closely related to federated bilevel optimization (FBO) as well, similarly to FMO. In particular, taking inspiration from FBO, we believe that MpFL for hierarchical games (where the order of players is important) is an interesting future direction. We could easily add a discussion on these connections in the revision of our work. We thank the reviewer for the suggestion.\n\n> 3. As I mentioned in the Weaknesses 1, the lack of numerical comparison would weaken the paper. Is it possible to add some comparison under special cases (eg. 2-player minimax problem)? Can MpFL address them as well? I believe adding comparisons would strengthen the numerics significantly.\n\nIn Appendix B, we provide a simple simulation result on what happens if one simply ignores the conceptual mismatch and nonetheless applies FedAvg to the MpFL setup — this shows that FedAvg diverges even for a simple quadratic problem, hence highlighting that PEARL-SGD is needed. In the revision, we will add a similar demonstration for the two-player case as well. We thank the reviewer for the suggestion."}, {"review_id": "U6fvztLVZU", "reviewer": "Reviewer_1eaY", "summary": "This paper studies a new federated learning (FL) paradigm inspired by a game-theoretic context and proposes PEARL-SGD. It includes theoretical analysis to support convergence guarantees under several scenarios. The authors verify the findings through empirical experiments.", "questions": "The questions are primarily included in the weaknesses part.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* This paper is well-structured and easy to follow. \n* The theortical contribution is solid, with several scenarios. The results presented in the theorems are convincing.\n\nWeaknesses: \n* One of the major concerns with the proposed method is the communication cost. Since the master node distributes $\\mathbf{x}$ back to the players at each communication step $r$, the communication overhead for $\\mathbf{x}$ becomes $n$ times higher compared to traditional FL methods. This significantly reduces the practicality of the proposed approach when applied to large-scale models.\n* The comparison with existing methods is limited, and the experiments are conducted on relatively small-scale models. Since the goal of the proposed PEARL-SGD is still to obtain a well-performing global model, comparisons with methods like FedAvg, SGDA, and other standard FL approaches should be feasible.\n* The theoretical resulst of this paper relies on several assumptions. Some of them are quite common and widely used in FL papers, but some of them are less common in FL research such as Quasi-strong monotonicity and Star-cocoercivity. The authors should provide more discussion on the validity and applicability of these assumptions in practical FL settings.\n* I understand that the game-theoretic context may rely on convexity assumptions for theoretical analysis, but it would be helpful if the authors could explain why the non-convex setting is not considered or applicable.", "was_revised": true, "final_justification": "Based on the paper’s theoretical contribution, I raise my rating to a weak accept. Nevertheless, I still have reservations about the experimental section, as the current results make it difficult to fully convince readers of the method’s effectiveness.", "rebuttal": "We sincerely thank the reviewer for viewing our paper as interesting and well-written, for constructive feedback, and for their time and effort spent reviewing. Below we provide responses to each point.\n\n> One of the major concerns with the proposed method is the communication cost. Since the master node distributes $\\mathbf{x}$ back to the players at each communication step $r$, the communication overhead for $\\mathbf{x}$ becomes $n$ times higher compared to traditional FL methods. This significantly reduces the practicality of the proposed approach when applied to large-scale models.\n\nYes, in our proposed algorithm PEARL-SGD, as we also discussed lines 192-202 of our work, the master node distributed the vector $\\mathbf{x} = (x^1, \\dots, x^n)$ to all players. In practical scenarios, this will indeed make our method particularly suitable for cross-silo FL setups with a relatively small number of organizations/players involved. That said, let us highlight here that the need for collecting all strategies is present in virtually any prior work considering algorithms for multiplayer games, distributed or not (see references in lines 1038-1048), as each player has to know all the others’ strategies/models. **Therefore, this is not the limitation specific to the MpFL framework. Rather, MpFL partially addresses this issue by communicating less frequently, as opposed to the centralized games,** where all strategies have to be communicated at every step. Using local steps (via PEARL-SGD), we are able to reduce the communication cost.\n\nRegarding the practicality of our results, **both the PEARL-SGD algorithm and the framework of MpFL we propose could be used in any prior practical applications of multiplayer games** to reduce communication complexity (via local updates).\n\n> The comparison with existing methods is limited, and the experiments are conducted on relatively small-scale models. Since the goal of the proposed PEARL-SGD is still to obtain a well-performing global model, comparisons with methods like FedAvg, SGDA, and other standard FL approaches should be feasible.\n\nThe goal of our proposed MpFL and PEARL-SGD is to reach equilibrium while **each player is carrying their own model (action)** and objective function to minimize, which is very different from the standard FL setting where obtaining a good global model is sufficient. In the MpFL setup, the dimensionality and semantics of each player’s action may vary (e.g., if they are neural network parameters, the local models’ architectures and model sizes could be different). This prevents one from naively applying the methods such as FedAvg or (Local) SGDA, which require averaging the local models. We provide a detailed explanation on these points in lines 149-174 and in Appendix B. Additionally, in Appendix B, we provide a simulation result on what happens if one simply ignores the conceptual mismatch and nonetheless applies FedAvg to the MpFL setup, showing that FedAvg diverges even for a simple quadratic problem.\n\nWe agree with the reviewer that our experiments are relatively small-scale. **However, we believe that this should not be considered a significant weakness of our work, where we primarily claim conceptual and theoretical contributions. Not all papers should focus on large models or complex experimental settings.**  The primary goal of our work is to introduce this new theoretical framework (MpFL) and understand in depth the benefits and limitations of local methods for solving multiplayer games. \n\n> The theoretical result of this paper relies on several assumptions. Some of them are quite common and widely used in FL papers, but some of them are less common in FL research such as Quasi-strong monotonicity and Star-cocoercivity. The authors should provide more discussion on the validity and applicability of these assumptions in practical FL settings.\n\nWe thank the reviewer for the suggestion. To that end, **please let us point the reviewer to “Appendix F: Discussion on Theoretical Assumptions” in the paper, where we provide the exact details the reviewer requested.** We would be happy to move parts of this discussion to the main paper, once we are given additional space. \n\nOur assumptions are standard conditions used in many recent papers in multiplayer games (see lines 203-219). Let us also highlight here that our assumptions of *quasi*-strong monotonicity and *star*-cocoercivity include classes of structured non-monotone games, where the players’ objective functions can be nonconvex [1, Appendix A.6].\n\n[1] Loizou et al. Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity. NeurIPS, 2021.\n\n\n> I understand that the game-theoretic context may rely on convexity assumptions for theoretical analysis, but it would be helpful if the authors could explain why the non-convex setting is not considered or applicable.\n\nIndeed, convergence analysis in the game theoretic setup typically requires convexity or similar assumptions. As explained in [2], finding an equilibrium in general nonconvex-nonconcave minimax games is intractable. As such, extra structural assumptions are needed to guarantee convergence to equilibrium for minimax optimization and multiplayer games in general.  \n\nAssumptions in our work are in line with this literature — as explained above, *quasi*-strong monotonicity and *star*-cocoercivity include classes of structured non-monotone games (generalizing the more commonly used assumptions of strong monotonicity and cocoercivity). Handling even more relaxed structural assumptions is an interesting future research direction, but it will require different mechanisms, such as two-timescale step-sizes and extragradient-type updates.\n\n[2] Diakonikolas et al. Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization. AISTATS, 2021.\n\n**We hope that our response has resolved the reviewer’s concerns. We believe that all points raised as weaknesses were mostly clarifications that can easily be handled in the camera-ready version of 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.**"}, {"review_id": "DI8EBBcIsd", "reviewer": "Reviewer_3R9y", "summary": "This paper proposes MpFL, a novel federated learning framework that models clients as rational game players with individualized objectives and seeks Nash equilibrium through collaborative, decentralized training under a central server. This paper provides thorough theoretical analysis and convergence proofs, along with supporting numerical experiments.", "questions": "(a) The paper claims in line 175 that PFL is a special case of the proposed MpFL. However, this statement is rather superficial, as it merely presents an example of a regularization-based approach in PFL for comparison. In fact, the standard formulation of PFL is $\\min_{x_i} \\frac{1}{m}\\sum_i f_i(x_i) + \\phi([x_i])$. Here, $\\phi$ denotes a personalized regularization term, which does not necessarily have to be defined as a model consistency regularizer—it can take various other forms. Therefore, my question is: What are the essential differences between the proposed MpFL framework and this more general formulation of PFL where $\\phi$ can be arbitrary?\n\n(b) An important property in federated learning is the need to handle unexpected client dropouts caused by unstable connections or communication failures. As a result, most federated learning methods are designed to support partial client participation during training in order to address this practical issue. However, I did not find any discussion of this aspect in the MpFL framework.\nDoes the proposed MpFL method support partial client participation, and if so, how is it implemented?\n\n(c) What are the practical use cases of the proposed framework? How does it fundamentally differ from the setting where $n$ independent players each participate in a game until reaching equilibrium?", "limitations": "This topic has already been discussed in the main text.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "strength:\n\n(a) The paper is well-motivated and offers a novel perspective distinct from traditional federated learning.\n\n(b) The paper provides comprehensive theoretical analysis to demonstrate the effectiveness of the proposed algorithm.\n\nweakness:\n\n(a) Although the proposed approach is significantly different from traditional FL, the discussion regarding its relationship to PFL is insufficient and should be further emphasized. Essentially, the goal of the PFL framework is to train local optimal solutions with a common regularization constraint, where this regularization term is often carefully designed for different tasks. When facing multi-player game tasks, the proposed MpFL framework also appears to be a special case of the generalized PFL framework. The authors should include more discussion to clarify this connection.\n\n(b) The numerical experiments are conducted on a relatively small scale. At present, it also seems difficult to distinguish the practical applications of this framework, and the differences between this framework and independent n-player games are not clearly demonstrated.", "was_revised": true, "final_justification": "I still maintain my rating as accept. Thank the authors for the submission.", "rebuttal": "We sincerely thank the reviewer for the positive evaluation, constructive feedback and their time and effort spent reviewing. Below, we provide responses to each point mentioned by the reviewer.\n\n## Weaknesses\n\n\n> (a) Although the proposed approach is significantly different from traditional FL, the discussion regarding its relationship to PFL is insufficient and should be further emphasized…\n\n\nPlease refer to our response to the Question (a) below. We thank the reviewer for the thoughtful question and suggestion.\n\n\n> (b) The numerical experiments are conducted on a relatively small scale. At present, it also seems difficult to distinguish the practical applications of this framework, and the differences between this framework and independent n-player games are not clearly demonstrated.\n\nIn our proposed MpFL framework, all players still participate independently in the game to reach equilibrium. However, the important distinction with existing works on games is that the **proposed PEARL-SGD algorithm allows players to communicate less frequently.** In centralized training of games (which is presumably what the reviewer is referring to by “independent $n$-player games”), each player accesses other players’ actions at every iteration. This imposes a significant communication overhead, which PEARL-SGD aims to resolve by communicating only once in a while. We explain this in lines 95-103 and emphasize reduced communication as the central goal of MpFL, achieved by PEARL-SGD. Please also refer to our response to Question (c) below for the potential applications of MpFL, which further clarifies why these concepts are new and relevant.\n\nWe agree with the reviewer that our experiments are relatively small-scale. **However, we believe that this should not be considered a significant weakness of our work, where we primarily claim conceptual and theoretical contributions. Not all papers should focus on large models or complex experimental settings.**  The primary goal of our work is to introduce this new theoretical framework (MpFL) and understand in depth the benefits and limitations of local methods for solving multiplayer games. \n\n## Questions\n\n> (a) The paper claims in line 175 that PFL is a special case of the proposed MpFL. However, this statement is rather superficial, as it merely presents an example of a regularization-based approach in PFL for comparison…\n\n\nWe only discuss the model consistency regularizer in the paper for simplicity. However, any PFL problem formulated in the form $\\min\\_{(x^1,\\dots,x^n)} \\frac{1}{n} \\sum\\_{i=1}^n h\\_i (x^i) + \\phi (x^1, \\dots, x^n)$ can be reformulated as MpFL by setting $f\\_i (x^1,\\dots, x^n) = h\\_i (x^i) + n \\phi (x^1, \\dots, x^n)$.\n\nOn the other hand, there are some PFL formulations that do not follow the above structure. For instance, some influential papers [1, 2] proposed to keep a global model $w$ along with local models $x^i$, and such cases are not directly covered by the current formulation of MpFL. \n\n\nTherefore, we believe the correct viewpoint is that **PFL and MpFL are closely related setups but neither one is strictly more general than the other. However, the subclass of PFL using the formulation mentioned by the reviewer could be viewed as an instance of MpFL.** We will expand the current paragraph in lines 175-183 to include the above discussion. We thank the reviewer for pointing this out.\n\n\n[1] Fallah et al. Personalized Federated Learning with Theoretical Guarantees: A Model-Agnostic Meta-Learning Approach. NeurIPS, 2020.\n\n\n[2] Dinh et al. Personalized Federated Learning with Moreau Envelopes. NeurIPS, 2020.\n\n\n> (b) An important property in federated learning is the need to handle unexpected client dropouts caused by unstable connections or communication failures…\n\n\nIn the case of client dropout, we can perform the essentially same analysis as in Section C.1 to obtain a convergence bound, with the net effect of probabilistic dropout being a reduction of effective step-size by the dropout probability. For the purpose of our paper, we intend to provide a clean, foundational analysis under an idealized setup and leave the extensions open for the future. However, we could include the above discussion and a simple sketch of ideas in the revision. We thank the reviewer for the important and relevant suggestion.\n\n\n> (c) What are the practical use cases of the proposed framework? How does it fundamentally differ from the setting where  independent players each participate in a game until reaching equilibrium?\n\n\nWe foresee the following potential applications, although at the moment, actual implementation would need more exploration.\n\n- Autonomous Vehicle Coordination: This can be modeled as a game where vehicles’ objectives are to adjust driving strategies (speed, lane changes etc.) while adapting to the actions of others. Equilibrium is when each vehicle's strategy is optimal, given others’ strategies. FL will be needed in this scenario, as performing centralized training through real-time communication between individual players (vehicles) will be extremely challenging.\n\n\n- Multi-agent debate in language models: Given a prompt, LLMs can debate to reach agreement (equilibrium in a game) to enhance reasoning quality [3, 4]. This idea can be extended to joint training/fine-tuning of multiple language models. Here the FL setting would be the suitable theoretical description of the process, as opposed to the centralized training, which will require jointly updating every model’s parameters at every iteration (which is clearly unrealistic).\n\n\nNote that MpFL framework allows each player to perform multiple local updates based on other players’ actions given from the past (previous communication step), making it **suitable and relevant to practical scenarios where players are unlikely to have real-time access to others’ updated actions.**\n\n\n[3] Du et al. Improving … Multiagent Debate, 2023.\n\n\n[4] Jacob et al. The Consensus Game: … Equilibrium Search. ICLR, 2024.\n\n**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.**"}, {"review_id": "voMUE1cAbq", "reviewer": "Reviewer_jQKH", "summary": "This paper studies federated learning from a game-theoretic perspective, modeling the clients as rational players with individual objectives and strategic behaviors. When every player optimizes their own utility function and observes other players' actions periodically, the system should reach an equilibrium. By proposing a per-player local SGD algorithm, the authors find that by doing local updates, the system would reach a neighborhood of the equilibrium with less communication under several strong assumptions: convexity, smoothness, bounded variance, quasi-strong monotonicity and star-cocoercivity. Numerical experiments are performed to verify the theory.", "questions": "1. In classical FL, all the clients have a collaborative goal, and intuitively, by leveraging information from other clients, they would get a better result than training on their own. But in the MpFL framework, clients no longer have collaboration in mind, or even that they would be competitive with each other, what would be the incentive for them to participate in the system if the training may harm their own benefits compared to working alone?\n2. typo: line 212: etragradient -> extragradient\n3. Figure 2(c) has a weird large shaded region in the bottom left.\n4. Are all the experiments using a constant step size? Are there any numerical results to verify the sub-linear convergence to exact equilibrium in the stochastic case with decreasing step sizes?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe motivation and the modeling of this work from a game-theoretic perspective are interesting, and the paper is generally well-written and easy to follow.\n\nWeaknesses:\n1. The MpFL framework is defined without a discussion on the existence of the solution. The goal of the MpFL problem is to find a pure strategy equilibrium, which does not necessarily exist, but there is no discussion in the paper under which necessary or sufficient conditions the problem is well-defined.\n2. The assumptions in this paper are strong and restrictive. Only convex local loss functions are considered, while in the real-world applications, most cases are non-convex, but there is neither theoretical analysis nor numerical experiments on the non-convex case.", "was_revised": true, "final_justification": "This paper introduces a novel framework at the intersection of federated learning and game theory, proposing a per-player local SGD algorithm and analyzing its convergence to equilibrium under several strong assumptions. While the theoretical analysis relies on restrictive conditions and the experimental validation is limited to small-scale convex settings, the core idea and interdisciplinary framework are compelling. The rebuttal solved most of my questions, but the limitations of the work still exist. Given these strengths and limitations, I rate the paper as borderline accept.", "rebuttal": "We sincerely thank the reviewer for highlighting that our paper is interesting and well-written, for the constructive feedback, and for their time and effort spent reviewing. Below, we provide responses to each point.\n\n## Weaknesses\n\n\n> 1. The MpFL framework is defined without a discussion on the existence of the solution. The goal of the MpFL problem is to find a pure strategy equilibrium, which does not necessarily exist, but there is no discussion in the paper under which necessary or sufficient conditions the problem is well-defined.\n\n\nWe thank the reviewer for their careful reading. Under our assumptions, equilibrium always exists due to classical results (please see [1, Theorem 1] and references therein) as the minimization objectives $f\\_i$ of individual players are continuous and convex in $x\\_i$ — *equivalent to the payoff functions being concave*. We can easily add this information to the updated version of our work. \n\n[1] Daskalakis. Non-Concave Games: A Challenge for Game Theory’s Next 100 Years. 2022.\n\n\n> 2. The assumptions in this paper are strong and restrictive. Only convex local loss functions are considered, while in the real-world applications, most cases are non-convex, but there is neither theoretical analysis nor numerical experiments on the non-convex case.\n\nOur work is the first paper introducing the MpFL framework with the first algorithm (PEARL-SGD) for solving it. As such, we focus on a setting in which we can provide tight convergence guarantees, under the known most relaxed conditions for the convergence of player-wise SGD in the centralized (non-federated) multiplayer game setting. This parallels how numerous theoretical works in classical FL have been done ([2, 3, 4] to name a few), assuming strong convexity while primary applications are ML models. \n\nWe believe that not all papers should be about nonconvex settings and deep neural networks. This will be, of course, a desirable outcome, but for understanding the fundamentals in depth, one should first focus on a setting that is more tractable. \n\nAdditionally, please note that finding an equilibrium in general nonconvex-nonconcave minimax games is intractable [5]. As such, extra structural assumptions are needed to guarantee convergence to equilibrium for minimax optimization and multiplayer games in general. Our **quasi**-strong monotonicity and **star**-cocoercivity assumptions partly do that as they include classes of structured non-monotone games (see Appendix F), but handling even more relaxed structural assumptions would be an interesting future research direction. At the moment, however, it will require a distinct set of update rules and techniques, such as extragradient-type updates or multi-timescale step-sizes.\n\n[2] Stich. Local SGD converges fast and communicates little. ICLR, 2019.\n\n[3] Khaled et al. Tighter theory for local SGD … data. AISTATS, 2020.\n\n[4] Karimireddy et al. SCAFFOLD:  … federated learning. ICML, 2020.\n\n[5] Diakonikolas et al. Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization. AISTATS, 2021.\n\n\n## Questions\n\n\n> 1. In classical FL, all the clients have a collaborative goal, and intuitively, by leveraging information from other clients, they would get a better result than training on their own…\n\n\nIn the application scenarios that we have in mind, clients may have competing objectives but that does not necessarily imply that they are harming each other’s benefits. As a basic example, let us first recall the Generative Adversarial Networks (GANs), which is trained via solving the minimax game $\\min_{G} \\\\, \\max_{D} L(G,D)$ between the generator $G$ and the discriminator $D$. Here, the objective is designed to let $G$ and $D$ compete, but this lets both the generation capability of $G$ and the discriminative ability of $D$ improve. \n\n\nNow, as a similar but more timely application, consider a debate among multiple LLMs performed to reach an agreement, given a certain prompt. This can be modeled as searching for an equilibrium in a multiplayer game with not fully cooperative objectives (as different LLMs may initially output varying responses), but in the end, this leads to enhancement in the models’ reasoning quality or factual accuracy [6, 7]. This idea can be extended to joint training/fine-tuning of multiple language models, where the FL protocol (in particular, MpFL) would play an essential role, as centralized training requires jointly updating every model’s parameters at every iteration, which is unrealistic.\n\n\n[6] Du et al. Improving … Multiagent Debate, 2023.\n\n\n[7] Jacob et al. The Consensus Game: … Equilibrium Search. ICLR, 2024.\n\n\n> 2. typo: line 212: etragradient -> extragradient\n\n\nWe thank the reviewer for pointing this out. We will update it in the revision.\n\n\n> 3. Figure 2(c) has a weird large shaded region in the bottom left.\n\n\nWe thank the reviewer for taking a careful look. This is because we use the logarithmic scale for relative errors and one of the stochastic runs hit a very small loss by chance.\n\n\n> 4. Are all the experiments using a constant step size? Are there any numerical results to verify the sub-linear convergence to exact equilibrium in the stochastic case with decreasing step sizes?\n\n\nIn the current version, we only included the experiments using a constant step-size to keep the setups simple, but internally, we also verified the sublinear convergence to the equilibrium using our step-size rule from Theorem 3.6. Unfortunately, we are not allowed to include any figures (or link to them) during the rebuttal this time, but in the revision, we will include an additional plot displaying those results.\n\n**We hope that our response has resolved the reviewer’s concerns. We believe that all points raised as weaknesses were mostly clarifications that can easily be handled in the camera-ready version of 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.**"}]

Author rebuttal:

Meta-review: This paper introduces Multiplayer Federated Learning (MpFL), a framework that models clients in federated learning as self-interested players with potentially misaligned objectives, analyzed through a game-theoretic lens. The authors propose an algorithm where each client performs independent local updates and communicates periodically, and show its convergence to a neighborhood of equilibrium with reduced communication. Theoretical results are supported by numerical experiments validating the approach. Even though the scale of the experiments is small, I agree with the reviewers that the theoretical contribution of the paper is significant enough to warrant acceptance.
Decision: Accept (poster)