Decoupled SGDA for Games with Intermittent Strategy Communication
Authors: Ali Zindari
Parham Yazdkhasti
Anton Rodomanov
Tatjana Chavdarova
Sebastian U Stich
Venue: ICML 2025 poster (2025)
Keywords: minimax games
Distributed Optimization
Primary area: optimization

Abstract: We introduce *Decoupled SGDA*, a novel adaptation of Stochastic Gradient Descent Ascent (SGDA) tailored for multiplayer games with intermittent strategy communication. Unlike prior methods, Decoupled SGDA enables players to update strategies locally using outdated opponent strategies, significantly reducing communication overhead. For Strongly-Convex-Strongly-Concave (SCSC) games, it achieves near-optimal communication complexity comparable to the best-known GDA rates. For *weakly coupled* games where the interaction between players is lower relative to the non-interactive part of the game, Decoupled SGDA significantly reduces communication costs compared to standard SGDA. Additionally, *Decoupled SGDA* outperforms federated minimax approaches in noisy, imbalanced settings. These results establish *Decoupled SGDA* as a transformative approach for distributed optimization in resource-constrained environments.

Decoupled SGDA for Games with Intermittent Strategy Communication
Ali Zindari"
Parham Yazdkhasti 1
Anton Rodomanov'
Tatjana Chavdarova Sebastian U. Stich
Abstract
2019; Robey et al., 2023) and multi-agent reinforcement learning (e.g.. Lowe et al., 2017; Li al., 2019).
We introduce Decoupled SGDA, novel adap- tation of Stochastic Gradient Descent Ascent (SGDA) tailored for multiplayer games with in- termittent strategy communication. Unlike prior methods, Decoupled SGDA enables players to update strategies locally using outdated oppo- nent strategies, significantly reducing communi- cation overhead. For Proongly-Convex Stroonlly- Concave (SCSC) games, it achieves near-optimal communication complexity comparable to the best-known GDA rates. For weakly coupled games where the interaction between players is lower relative to the non-interactive part of the game, Decoupled SGDA significantly re- duces communication costs compared to standard SGDA. Additionally, Decoupled SGDA outper- forms federated minimax approaches in noisy, imbalanced settings. These results establish De- coupled SGDA as transformative approach for distributed optimization in resource-constrainne environments.
Several gradient-based methods have been proposed for solving minimax problems (Korpelevich, 1976; Popov, 1980; Balduzzi et al., 2018; Nouiched et al., 2019; Chav- darova et al., 2020; Kovalev & Gasnikov, 2022). One of the most widely used is the gradient descent method. In the context of 2-player zero-sum minimax games, this approach is referred to as Gradient Descent Ascent (GDA), where the minimizing player (u-player) takes descent steps and the maximizing player (v-player) takes ascent steps.
In some situations, however, players may not have direct access to their opponents' exact strategies. The u-player might only have noisy estimate of when updating its parameters, and vice versa. In extreme cases, players might operate with outdated strategies from their opponents, with limited opportunities to synchronize. We refer to this sce- nario as games with intermittent strategy communication (ISC- gamee). Here are a few illustrative examples:
Corporate competitors. Companies frequently adjust their strategies based on individual objectives and the strategies of their competitors. For instance, Netflix may need to lower its prices if competitor like Max reduces its subscription rates (Jagadeesan et al., 2022). Corporations may occasionally release (noisy) general information about their strategies, giving each com- pany an imperfect understanding of its competitor's actions. Alternatively, companies might hire experts to estimate competitor strategies using publicly available data, although this process is expensive and infrequent.
1. Introduction
Several real-world problems in diverse areas, such eco- nomics and computer science, can frequently be described as N-player differentiable games (Von Neumann & Mor- genstern, 2007). While players may have competing ob- jectives, the aim to identify an equilibrium, a strategy where no player benefits from deviating unilaterally. Exam- ples of such games in machine learning include Generative Adversarial Networks (GANs, Goodfellow al., 2014), 4), adversarial robustness (Madry et al., 2017; Shafahi et al.,
N --agents with restricted communication. In con- trol theory, applications involving drones or robots are modeled with N --player games (see Spica et al., 2020; Laine et al., 2021; Zhou et al., 2021, and references therein). However, due factors like long distances or limited battery life caused by weight constraints, com- munication between agents regarding learned strategies is costly and can only occur intermittently
"Equal contrihution 'CISPA Helmholtz Center for Informa- tion Security, Suarbrücken, Germany "Politecnico Milano, Italy. Correspondence to: Ali Zindari cali.zindariee cenudari@cispadde. cispades. Parham Yazukhasti <parbam. <parbam.yazdkhast yazdkhasti @ ces, Anton Rodomanov cantonnrodomanov @ cispa.de>, Tatjana Chav- darova caajian..havvdarvv@@eee polimi.. Sebastian U. Stich < ciipp.des.
In summary, this paper focuses on the following questions.
Can players effectively learn and adapt locally in ISC- games when relying on noisy or outdated opponent strategies?
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Decoupled SGDA for Games with Intermittent Strategy Communication
How do the convergence rale and communication costs of the proposed optimization method compare to the baseline, and can communication costs be significantly reduced?
To simplify the exposition, the main body of the paper fo- cuses on the minimax setting, while the extension N- player games is presented in Appendix C.
1.1. Related Works
To address the first question, we propose an extension of the gradient descent method where agents perform local up- dates while using outdated strategies from their opponents. In minimax problems, we term this approach Decoupled SGDA, and in N-player games, it is Decoupled SGD. The second question is examined by analyzing the convergence rate of Decoupled SGD(A) and identifying specific class of problems, called Weakdy Coupled Games, where commu- nication speed-up (acceleration) can be achieved.
Our work' draws from multiple lines of work, and herein, we review these and discuss the difference with federated learning. Appendix E gives additional discussion and lists works on decentralized optimization. The latter are further from our work in that there is no centralized communication, and nodes communicate with neighbors.
Game optimization. Nemirovski (2004); Nesterov (2007) achieve a rate of 0(+) for convex-concave minimax problems. For seeell--oooee---sooggyy-ooomm (i) Thekumparampil et al. (2019) combine Nestrov's Ac- celerated Gradient and mirror-prox and achieve Ö(7)) rate of convergence, (ii) Wang & Li (2020) explore ideas from accelerated proximal point and achieve a linear rate, and (iii) Kovalev & Gasnikov (2022) propose a method with OV log 2) rate of convergence which matches the lower bounds (Zhang et al., 2022b; Ibrahim et al., 2020), Several works focus on accelerating the convergence of GDA (Lee al., 2024; Zhang et al., 2022a). Quadratic games with bilinear coupling 2021). Nouiehed et al. (2019) propose method that per- forms multiple first-order steps on only one of the param- eters to solve minimax problems. Tsaknakis et al. (2021) study a generalized minimax problem with linear constraints coupling the decision variables. Tseng & Yun (2009) study coordinate gradient descent method for minimizing the sum of a smooth and separable convex function. Jain et al. (2018) and Yoon & Ryu (2021) present algorithms with accelerated (1/k²) rates for smooth minimax optimization and estab- lish the optimality of this rate through a matching lower bound. In the context of multi-player games, several works have explored multi-agent reinforcement learning in a dis- tributed setting, where agents update their policies without access to the policies of others (Lu et al., 2021; Sayin et al., 2021; Jiang & Lu, 2022). Independent and concurrent work by Yoon et al. (2025) also considers decoupled updates for cquilibrium computation in N --player games. While we both address this setting (see Appendix C), their method does not achieve the same communication efficiency as ours. See Remark 4.6 for a detailed comparison.
Contributions. Our contributions include:
games,
We introduce Decoupled SGD(A), the first method de- signed for ISC-games, where each player performs local updates using outdated opponent strategies.
We analyze its convergence in both the strongly-conver strongly-concave (SCSC) setting and in N-player games where each player's 's utiliiyy is strongly convex.
We introduce a non-standard set of assumptions to mea- sure the coupling of the players' objectives. This allows us to identify a specific regime, termed Weakly Coupled Games, where Decoupled SGD(A) demonstrates commu- nication acceleration compared to the baseline GD(A), by removing the dependency on player conditioning. We show that Decoupled SGDA can even outperform the optimal first-order method for solving SCSC games in terms of communication rounds under a slightly stronger assumption than weakly coupled games. Our method achieves robustness to noise imbalance, a significant limitation of existing federated minimax methods.
studied in (Zhang et al.,
We study the convergence of Decoupled SGDA for quadratic minimax games with bilinear coupling between the players, providing additional in-depth insights into the algorithm's 's convergence behavior.
Through numerical experiments, we validate the practical benefits of Decoupled SGDA in non-convex GAN train- ing, federated learning with imbalanced noise, and in weakly coupled quadratic minimax games, showcasing its versatility.
We propose a novel heuristic (Ghost-SGDA). detailed Appendix G. to further accelerate the convergence of Decoupled SGDA by leveraging predictive updates for opponent strategies. Our numerical results demonstrate its practical effectiveness, showing that Ghost-SGDA can achieve faster communication efficiency and conver- gence even in highly interactive games. This heuristic opens a promising new direction for distributed optimiza- tion, potentially going beyond the theoretical guarantees proven in this work.
Federated learning. Building on the foundational work of McMahan et al. (2017), numerous works have explored distributed minimization, or federated learning, across var- ious settings (e.g., Stich, 2019a; Koloskova et al., 2020; Karimireddy et al., 2020; Woodworth et al., 2020a;b). In
'An early version of this work was presented at an 2024 workshop (Zindari et al., 2024).
2

---

Decoupled SGDA for Games with Intermittent Strategy Communication
the context of minimax optimization, Deng & Mahdavi (2021); Sharma al. (2022); Zhang et al. (2024) extended the so-called Local SGD (Stich, 2019a) to the minimax set- ting, achieving convergence rates for different classes of functions in both heterogeneous and homogeneous regimes. Although both Federated Minimax and Decoupled SGDA are designed to solve minimax optimization problems a distributed fashion. their approaches achieving this are fundamentally different. Refer to Section F.1 for more de- tails.
||x|| (Px, x)2/2, where P is the block-diagonal matrix with blocks ot, Pu and o,P,, v (P diag(o., P u. P.). The parameters Cuyy Oty can be seen as scaling factors for players that can be optimized separately. One can easily assume P. = Pr. I, P I and Oz = Og recover the common euclidean norm ||x|| = V(x x). The corresponding dual norms are defined in the standard way: gu Ilu. := max gg. u) (gu: P. guu 1/2 (gu X,), || == | v) = (g. P. g.> 1/2
and
(g. E X,), and ||gll := max x (g. x) = (2. gg u,* +
g. 1 3 0, 1/2 11/2
p 1/2 (g = (gu: g.) E 2).
o.
2. Setting and preliminaries
Now we outline the necessary assumptions for establishing the convergence of our method.
In the main body of the paper, we focus on the two-player setting, as this allows us to clearly present the key ideas and insights of our approach. The extension to the more general N 1-player games is detailed in Appendix C. Specifically, we consider the following saddle-point problem over X' Rdy:
Assumption 2.1 (Strong monotonicity). Operators Fx and F from (1) are strongly monotone with parameters ju, 2 > 0, i.e., for all x, x, x' E X, the following inequalities hold:
N₂ x Xe with X₂ Rd., X.
(F&(x) - Fx(x)),x x) 3 x|| - x x'12,
(F(x) F(x', [ xxxx μب | x'112.
min max f(u, v), X vex.
(SP)
We can show that ن = min(pa/as aanaaaaaaaaaa ap)a (Proof in Lemma B.5) where fru is the strong convexity parameter of f in u and M. is the strong concavity parameter of f in v. Assumption 2.2 (Lipschitz smoothness). Operators F& and F from (1) are Lipschitz with parameters L and L, i.c., for all x, x', x E X, the following inequalities hold:
where /: X' - R is differentiable function. Its solution is defined as point x' (u'vv)) E X' satisfying the following variational principle: f(u", v) & f(u',v') v²) < f(u, v") for all (u, é X. In ISC-games, players often have access only to the outdated strategies of their oppo- nents. To address this in our analysis, it is useful to define the following operator (x): X - X. which incorpo- rates a reference point x = (ū, v) E X X-typically the most recent synchronization point account for this delay:
(x) Fx & Σ||x - -x11,
(3)
[[(x)) - Fxx'Il++ & L||x - x'Il
Fx(x) == (V.f(u, VV. v)), F(x) = (V.f - vv,(u, (V.((u
X, (1)
While we assume both operators are smooth, Lemma B.2 shows that L < L.
X X.
In the special case of x = x, we recover the definition of the commonly used operator F(x)= = xx-x(x)= = (V.f(u,vv, ([llu,),,Vvvjp. -V.((u,v))
Assumption 2.3. The norm of the difference between oper- ators F& from (1) is upper bounded with parameter Le for for all x, X X as follows:
Notation. Bold lower and upper case denote vectors and matrices, respectively. We often denote the two players as E (K,, Rdd) and E (X₂ Rd.). The product space X = X, x X, = Rd (with d = d, + d,) con- sists of vectors x = v) E Rd. where u E Xx and v E X.. For a differentiable function f: X - IR we denote partial gradients at a point x = (u, v) E X w.r.t. the corresponding variables by Vuf(x) and (x). re- spectively, so that fx(x) = (x),(x) (x)(.)). <..> de- notes inner product. We assume that the spaces X, and Xr are equipped with certain Euclidean norms, ||u|| := (P, u, 1/2 and ||v|le := (P.v, 1/2 respectively, where P. and P. are given symmetric positive definite ma-
[ - F(x)]++ & Lallx-x11 - x||.
(4)
It is possible to show Le = 1/vandy max Luvn Lout (Proof in Lemma B.6) where [VVffu, Vuf(u, v') & Tuvllv - v'lle and [IV.f(u, Here, we take the Vuf(u', v)ll & Eoullu-u'' -
derivative with respect to one variable while varying the other. We will demonstrate in Section that this constant plays an important role in communication acceleration it quantifies the interaction level of the game. In fact, Le can be much smaller than J. and can be even zero. We show it always holds that L. < L (Proof in Lemma B.2).
trices. The norm in the space X is then defined by |x|| (a.. ||ll + 1[)) where Ou, Op > 0: thus,
For the reader's 's convenience, we also present Tables 2 and 3 in the appendix, summarizing our notations.
3

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Assumption 2.4. There exists finite constants x² succ that for all x, X X:
K updates on local copy of the parameters. After every communication round, local variables are initialized as x = x Xt, and updated as:
E [ o²
(5)
where Gx(x, <) is an unbiased stochastic gradient acle that each player has access to with the property (x,x(x, ()] (x).
x x3 (. Σ
(8)
K-1
x++x = x - (aap..)
Σ
As we assumed that the above inequality holds for all x E X, we also cover the common operator F and we denote G(x, <) = 5x)
t-0
The local variables are then synchronized in a communica- tion round, Xx+ :- 2 (x*+ + x*+x)- This is a standard approach in distributed optimization. However, this method does not apply to our setting, as we would need to assume that the stochastic noise of the oracles o and o bounded.
3. Decoupled SGDA for two-player games
In this section we introduce Decoupled SGDA and explain its motivation.
Common Approach: Stochastic Gradient Descent As- cent (SGDA). A standard way for solving (SP) is as fol- lows:
Decoupled SGDA: Communication Efficient with Reli- able Information. We are considering setting where the two players may not have access to their opponent's 's strate- gies or gradients, and only assume that the private compo- nents of the gradients have bounded variance, see Assump- tion 2.4. This reflects real-worke challenges where it is hard to share reliable (with bounded noise) information between the communication rounds. For this setting, we therefore propose that each player should only use the reliable infor- mation, that is [G,[xx {) for player u, and [G,(x, E) for player v, and wait for the communication round to get reliable information about the other players. We introduce the oracle Go E) Gx-xç(x, (x for = fu, e) where Xe -uo, Vo) refers to the parameters of each player at the beginning of the round. Now of our method as:
X++1 = xx - - GP
G) = V.f(u, viE) (V.f(u,v: v)
(6)
for a given positive definite matrix P.? However, in a dis- tributed setting, the players need one round of communi- cation to exchange their parameters (u,, Vz) in every step of the method. This is because SGDA requires the most recent parameters from each player to take an step. In many real-world scenarios, however, communicating at every step may not be feasible due to the high cost.
write the update rule
Communication Efficient Strategy Exchange. To alle- viate this communication issue, earlier works proposed so- called local update methods that reduce the amount of com- munication by performing local parameter updates for each player separately. For these methods, it is common to as- sume that both players- the minimization player and the maximization player v- hahave access unbiased stochastic oracles Gx, E). (x, X - X. with the property (x, {)] = F(x) and follow-
K- Xx -P
Go(xf,
(9)
([G,,u,, vollu) [GG.(u). vf)]./ = (-v..(u,, (.).))))))
[u, vi)
Go(x²) =
Here, the index denotes the local update step in the current local update phase, and the superscript r indexes the local phases. One communication round is needed for exchanging the updated parameters (u vik when passing to the next round. Here we allow the variances o" and o2 to be arbitrarily large and we only need ø² & o + o to be finite which is an advantage of our method compared to local update methods.
Eg[G,, (x,{)] F(x). [x
ing bound on the variance of the noise:
[x]l[[G,(xx - (xx 1 < ouu
[x]] [F(x]]
[1, < 02 u
[x] - [F(x)] (x. [F(x)] & 22
Method. We formalize our method in Algorithm 1. De- coupled SGDA has round-wise update scheme allowing each player to share his parameters only once in a while. At the beginning of each round r, each player receives the most recent parameters of the other player. Then all players start taking K local steps and updating only their own parameters
Here, we use the operator [.] to denote the coordinates cor- responding to player i E {u, v3. Both players could perform
II optimization literature, the matrix P is known as the pre- conditioning matrix. For simplicity, we can assume P I without disrupting the flow of the paper.
4

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Algorithm 1 Decoupled SGDA for two-player" games
instance, our method allows for any first-order update rule to be applied for the local steps like GDA, Extra Gradient (EG), and Optimistic Gradient Descent Ascent (OGDA), Note that in this work, we focused on GDA updates, leaving the analysis of other methods for future work. Moreover, in Section G, we present Ghost-SGDA, where each player aims to estimate the other player's parameters using the so- called Ghost Sequence, which leads further acceleration in terms of the number of rounds.
1: Input: step size y, initialization X, = (uo, vo), number of rounds R. number of local GD steps K, Ous Ou. P
2: for r {I,..., RR] do
3: for L (I,...,K] K] do
4: u - u/ 7
v) V..(u. 5)
5: V/-1 - V2 + (a, P.)
6: end for
7: Communicate (uk vic) to each player
8: end for
9: Output: x (u v
4. Convergence Guarantees
"The extension to N N-player games is displayed in Appendix C
We could analyze our method under the common smooth- ness assumptions in the literature (see Appendix B.2 for the details). However, these assumptions are often overly pessimistic in distributed settings, as they fail to account for the interaction level between players. Specifically, they treat games with high and low interaction identically, yield- ing the same convergence rates in both cases. In contrast, we introduce an important parameter Le (see Assumption 2.3) that quantifies the interaction level of the game. This allows us to achieve communication acceleration in games with low interaction through a novel proof technique (see Section B. To formalize this, we first introduce the notion of Weakly Coupled Games Regime and then provide the convergence guarantee for our method.
in Alg. 2.
'The constants dz ct., are determined by the vector norm that we specify. For simplicity, the reader can assume that aa = a. and P. P. I. These terms are included for the sake of completeness, though they are not essential for the main results.
using the information they received at the beginning of the round from other players. Note that our method is general framework and one can use any first-order method to take local steps and not just the GD steps as illustrated here. The extension to N- -pllayer games is displayed in Appendix C in Alg. 2.
Intuition. To provide some intuition on why Decoupled SGDA might work, consider that the objective of minimax games (SP) can be written as:
Given a strongly-convex strongly-concave (SCSC) zero- sum minimax game fuu, v), we define the coupling degree parameter Ke for this game as follows:
f(u, v) g(u) h(v) + v(u,v)
(10)
Le
Re :
(11)
where g()) and h(v) represent the independent contribu- tions of each player, and captures the interaction between them. Note that in this formulation, r(u, v) cannot be de- composed in the same way as f. as it specifically captures the interdependent aspects of u and v.
This variable measures the level of interaction in the game. A smaller value of Ke indicates less interaction. For any f(u, v), we say the game is Weakly Coupled if:
In the special case when r(u, v) 0, i.e., there no interaction, the problem does not require any communica- tion: the optimal solution can be found by minimizing g and i separately. A method like SGDA is, therefore, not a good choice in this setting, as it requires to communicate parameters (u, v) in every step of the method, although this is unnecessary. In contrast, when the coupling r(u, v) is significant, then optimizing g and h separately might not be good strategy. Decoupled SGDA aims find balance between the two extremes. In the following, we will charac- terize some settings where Decoupled SGDA provably uses significantly fewer communication rounds than SGDA or other baselines (see also Table 1).
Ke 4
(12)
We say the game is Fully Decoupled if KG = 0, which im- plies that (u, v) (see Eq. (10) and Lemma B.3). These games are an extreme case of weakly coupled games. In weakly coupled games, each player's dynamics are mostly driven by their own pay-off function, with little influence from the other player.
Theorem 4.1. For any R 3 and any K 3
1. log 7u
Ke
after running Decoupled SGDA for a total of T = KR iterations on a function f, with the stepsize Y & T3 weakly coupled regime (48. & 1), we get rate of:
B
in the
Extensions of Decoupled SGDA (Appendix G). It is clear that our method is a general framework, providing flexibility for various modifications and adaptations. For
E E||| x*113 D2 exp (-p(-11- (1-))))) + 1(1 (())
8k.072
5

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Table 1. Comparison of Communication Complexity and Acceleration Condition for Different Methods, Speed up lists the conditions under which Decoupled SGDA achieves acceleration relative to the respective method. Note that for simplicity and in order to compare our results with other works, we consider P.. = P. = I. P and at at 1.
Communication Complexity (Fuily Decopplod)
Communication Complexity (Genvul Bound)
Method
Speed Up
GDA (L.c et al., 2024)
(Kx Kew) log? 7
(Nu + Mu + xi..) log 1
J (weakly coupled)
EGOOGDA
(Nu + No) log 2
(Nu + Nu) log 2
No & 2// max (oartt
(Mokhtari al., 2020)
APPA (Lin ct al., 2020)
Va, log"
1
v VRu log"
Kio 1
FOAM (Kovalev & Gusnikov, 2022)
v Miu Mi log ?
Ree % 1 VRuNg
PEARL-SGD (Yoon et 2025)
x²a log
x² log
Kig 1 (weakly coupled)
Decoupled SGDA (ours)
0
min
dag
log 2. x2? log 23
Moreover, For any R.K: 3 I, after running Decoupled SGDA for a total Tf = KR iterations on a function f,
with K = 122 log( log(()) Moreover, with the choice of Y pp
min s2kL2 uKR log(max()))) D² KR))} if the game is not weakly coupled we get:
with the stepsize y & min { R. { P 1 in the non-weakly coupled regime, we gel rate of:
1.2
σ2
E [| - x x1 & D2 exp (-21 KR) +
20
E B[||x - x Dxcxp/ exp
2L
+
H2² 12KR
where D = - 1
Consequently, reach E perform R= 21.2 n² log( D2 with K
[[[[x
x* [|]] & e, it suffices to 20²
Corollary 4.2. Decoupled GDA with a stepsize of = fo converges the saddle point without any communication on fully decoupled games (Ng- = =0 if K + sc.
Weakly and Non- Weakly Coupled Games The main property of our rate for weakly coupled games is the ab- sence of Ku, Ky, or K, which can be very large even if the player interaction is low. We are able to capture this effect due to differentiating between different smoothness param- eters. In addition, mathematically identifying the regime in which we can benefit from low interaction and achieve communication acceleration is another important aspect of our work. This stands in contrast to most popular methods, whose communication complexity always depends on the quantities Ki: Ki or i. (see Table 1), which can be overly pessimistic, especially in the weakly coupled regime. More- over, for non-weakly coupled games, our rate recovers the standard Orx² log( 1/e)) rate for GDA from (Zhang et al., 2022a; Azizian et al., 2020).
Fully Decoupled Games. For the sake of comparison, we Lu
define the condition numbers?: Kix pa
Ki Lu and
Kun Kun Le_.. We also use x L. The most VPulte"
recent rate proposed for GDA (Lee et al., 2024) requires O ((na + k2) log 2) rounds of communication when the game fully decoupled.
major drawback of GDA and several other common methods in this setting is that poor conditioning in one of the players (large Kuy K.) signifi- cantly increases the number of communication rounds. In contrast, our method overcomes this issue by utilizing local steps, effectively eliminating the dependency on players' conditioning.
Corollary 4.3. With the choice of = RL. if the game is weakly coupled we get:
Noise Term. Our method does not depend on Twe or dour allowing them to be arbitrarily large. In contrast, existing federated minimax methods assume these quantities are bounded, which may not hold in many real-world settings. In the weakly coupled regime, ō is multiplied by K.. small quantity, reducing the effect of noise. In the non-weakly coupled regime, we can mitigate noise by taking more local steps. Herein, we state the communication complexity of our method and compare it with GDA as the baseline.
802 pue RUL2(1 - 4nc))
E R x [P3 & D2 exp (xpp(-(1AKE))))
Consequently, to reach [[[1x xx'1 111 & e, it suffices to perform R. max! --o log( 2D
16 (Aeoee) } rounds
"IV,s(u, v.f(n',v)) & Iullu u'll and [V.f(u.v) - V.f(u, T. -vll
6

---

Decoupled SGDA for Games with Intermittent Strategy Communication
rajectories for Cm10
Trajectories for 3.3.5
Irajectories for C=2.7
Irajectories for C=0
Coordinate
Coordinate
Coordisate
CCordinate
Synchronizazion Rounds
Synchrorimation Rounds
Synchronization Rounds
Synchronization Rounds
Figure 1. Trajectories (top row) and distance to equilibrium over synchronization rounds (bottom row) of GDA (K = 1) and Decoupled SGDA with K = [2. 5) on the (13) problem (d = 2). C in (13) is constant here-the larger, the stronger the interactive term. Left-to-right: decreasing the constant c E {10, 3.5, 2, 7, O). The markers denote the local steps and star the solution. See for discussion.
Corollary 4.4. For any K > log ) after running 7/4 Ke
can recover the weakly coupled condition if Max though the rate (Kr log(1 the lower bound from (Zhang et al., 2022b), large condition number of players (Ni, Ne) can increase the communication overhead significantly.
rounds. The assumption Ki. & 2V VRg
Decoupled SGDA on a weakly coupled game, we have the following communication complexity in order to achieve accuracy in the noiseless setting:
c. Al- is optimal and matches
Decoupled GDA
GDA
1 O (RR + Ky + kww) log
0
log
vs.
4ne
Remark 4.6. The recent work of Yoon et al. (2025) consid- ers similar method in the general N-player setting (we also address this case in Appendix C) and establishes a linear convergence rate of O ( T.unnn f/P
Moreover, Decoupled SGDA the weakly coupled regime always has better communication complexity compared to the baseline GDA. In other words, I-Ix; Kuu + Kip + x
log(1/c));
where & denotes the star-cocoercivity constant and Lmax max|L1..... L is the largest smoothness parameter among the players. For the class of j-strongly mono- tone and L-Lipschitz continuous operators considered in our work, it holds that Tmaxx///j ///ji < (see Yoon et al. 2025, Appendix D), which simplifies their rate to o (5 (og(ee)) In general, one has the bound < L (Facchinei & Pang, 2003), which implies a worst-case convergence rate of O1s2 log(1/c)), offering commu- nication acceleration. While acceleration is theoretically possible when É is small, the improvement is limited: since L < f, the best achievable rate is OO (og()))). In the fully decoupled setting, this matches the convergence rate of GDA (Lee et al., 2024), which, as discussed earlier, is suboptimal. By contrast, our method requires only a single round of communication in this regime (see Corollary 4.2), demonstrating significant advantage. A key distinction between the two works is in how interaction between play- ers is modeled. Our analysis introduces and leverages the coupling parameter L,, which more directly captures the interaction structure and leads to sharper communication complexity bounds.
Table 1 compares our method with other first-order methods in terms of communication complexity in both the fully decoupled and weakly coupled regimes. is clear that in the fully decoupled regime, our method outperforms all other methods. Furthermore, is expected to compare our method with GDA by considering it the baseline because our method uses GD local updates (and not updates using EG or momentum). In Corollary 4.4, we stated that we always have a better complexity compared to GDA in the weakly coupled regime. However, we can show that under slightly stronger assumption, our method achieves better communication complexity than the optimal first- order method for solving SCSC games.
Corollary 4.5. For any SCSC zero-sum minimax game with coupling degree Rie & 1 //11 " our method achieves better communication complexity than FOAM which is the optimal first-order method for solving SCSC games. In another word, if T- nificant communication acceleration compared to FOAM.
T < v Vuu our method achieves sig-
Corollary 4.5 shows that our method can even outperform the optimal first-order method in terms of communication
7

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Number of Rounds to Reach Epsilon Accuracy vs Amar(C)
Number Rounds to Reach Epsilon Accuracy vs Amax
Dacoupled
Log of Numbor of Hounds
Weakly Coupled Regime>
DCIDA
ADt-GD
Log Numberr
Decoupled GDDA Km1 (GDA)
Decoupled CIDA
Decoupled GDA K-5
Decoupied CDA K=10
Decoupled CDA K-50
(Ca
Figure 2. Number of rounds (log-seale; lower is better) to reach epsilon accuracy for varying A ) in (13). Left: Decoupled GDA with different K-values and GDA (K 1). Right: comparison between GDA, Decoupled GDA, Optimistic GDA (Popov, 1980), Alternating GDA and Extragradient (Korpelevich, 1976).
5. Experiments
follows:
In this section, we evaluate the empirical performance of De- coupled GDA. For all experiments described in this section, we provide additional implementation details (and hyperpa- rameters) in Appendix I.
min max NE0 vø]
u
(14)
E Eg-Noon v(uo) v(u An ///ll/ / Aellv|?3.
where u E Rd, v E Rd, Figure 3 shows the smallest gradient norm (lower is better) each algorithm can achieve for fixed number of communication rounds, with vary- ing values of 1/x. As decreases, the regularization terms dominate, making the game less interactive (similar the weakly coupled regime). When À increases, reducing in- teraction, Decoupled GDA achieves much lower gradient norm with the same number of communication rounds. This demonstrates that Decoupled GDA efficiently solves non- convex problems in settings analogous to the weakly cou- pled regime by leveraging local updates to reduce communi- cation. This experiment highlights the method's capabilities beyond SCSC games. The trajectory of Decoupled GDA it- erations for this non-convex minimax problem can be found in Appendix H.1. Decoupled SGDA with gradient ap- proximation. Herein, we compare Decoupled SGDA with Federated Minimax, aka (8). We study environments with gradient oracles with unbalanced noise unbalanced noise. Each player has access to a gradient oracle that provides low-variance noise for their own gradients but high-variance noise for the remaining players. In the quadratic game in- troduced earlier, each oracle adding zero-mean Gaussian noise to the gradient. The variance differs between gra- dients for a player's own parameters (diagonal variance) and those of others (off-diagonal variance). Equation for- malizes this. In both experiments, we kept the diagonal variance (o yus og constant, while varying the off-diagonal variance (o oi in the second experiment. Figure 4 com- pares Decoupled SGDA and Local SGDA, the latter being the most commonly used method for federated minimax problems (Deng & Mahdavi, 2021). depicts the small- est gradient norm each algorithm achieves within a fixed number of communication rounds across different scenarios.
5.1. Quadratic Games
Herein, we consider the following problem class:
min max 1 [u. Au) 2
1 ( Bv) + (u, Cv), (13)
u
where u, vE R$, and A, C are / positive definite matrices. We will use varying C to control the players' interaction.
Figure illustrates the performances of Decoupled SGDA on the (13) for varying numbers of local steps K and dif- ferent intensities of the interactive term of (13). The results show that as the interactive term weakens, Decoupled SGDA converges more quickly than the GDA baseline (K 1). Additionally, with stronger interactive term, increasing the number of local steps K leads to faster convergence for the same number of synchronization rounds. Figure 2 de- picts the performances over a spectrum of payoff functions controlled by the constant matrix in (13). the Weakly Coupled Game regime, highlighted by shading, Decoupled SGDA outperforms the baseline GDA. In Figure (right), compare it with other optimization methods, demon- strating that Decoupled SGDA achieves similar results with significantly fewer communication rounds in the weakly coupled regime.
5.2. Communication Efficiency For Non-convex Functions
While our theoretical focus was on SCSC games, in this section, we explore if our insights extend to broader problem instances. We focus on Toy GAN non-convex game as
8

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Lowest gradient norm reached in R rounds
Lowest gradient norm reached R rounds
Decoupted GDA K=] (SDA)
Decoupled
Deccupled 6DA K-3
Deccupled GDA K=2
-30
OGDA
(Wekkyy Coupled Regime)
Decoupted SDA K-d
Decoupted GDA K-5
1/A
1/A
Figure 3. Lowest gradient norm reached after a fixed number of communication rounds, for varying 1/2 in (14). Left: Effect of K. Right: different optimization methods, GDA, Decoupled GDA, Optimistic GDA (Popov, 1980), ALT-alternating GDA and Extragradient (Korpelevich, 1976). See 5 for discussion.
gradient rounds
Escoupted Sc0R Local 5024
Deszuphed 500A
Local SOGA
Figure 4. Lowest gradient norm reached by Decoupled SGDA and Local SGDA for a fixed number of communication rounds using unbalanced noisy gradient oracles. Left: Decoupled SGDA vs. Federated Minimax for varying values of ||C|| and fixed variance. Left: Decoupled SGDA vs. Local SGDA for varying levels of off- diagonal variance noise (Tus. Jvu). See 5.
Figure 5. y-axis: FID scores (log scale; lower is better) during GAN training, versus 7-axis communication rounds. Left: results the CIFAR-1O (Krizhevsky, 2009) dataset. Right: results on the SVHN (Netzer et al., 201 dataset.
6. Conclusion
The left plot demonstrates how both methods perform in games with varying levels of interaction. When the inter- action is weaker, Decoupled SGDA achieves significantly lower gradient norms with the same number of communi- cation rounds. The right plot highlights the effect of noise variance, showing that while high noise negatively impacts Local SGDA, it has minimal to no effect on Decoupled SGDA. In the presence of imbalanced noise, the results sug- gest that switching from local SGDA to Decoupled SGDA is beneficial, even for highly interactive games.
We proposed Decoupled SGDA, an effective optimization method for games with intermittent strategy communica- tion, particularly suited for settings with weak interaction between players imbalanced noise levels. Our theoretical and empirical results show that Decoupled SGDA outper- forms traditional methods like Local SGDA in terms of communication efficiency and robustness, and extends be- yond strongly- congvexeyvvxxxxcooeoeooo strongly- concave (SCSC) games to non-convex settings. Its adaptability to varying interaction and noise makes it valuable tool for federated and decen- tralized optimization.
5.3. Communication Efficiency in GAN Training.
Figure 5 compares Decoupled SGDA with baseline meth- ods in terms of FID score over communication rounds. The results show that Decoupled SGDA converges faster and requires fewer communication rounds than standard GDA and its variants. This advantage is particularly evident on the CIFAR-10 10 and SVHN datasets, where increasing the number of local steps (K) leads to lower FID scores. These findings highlight the efficiency of our approach in reducing communication overhead while maintaining strong perfor- mance in complex, non-convex tasks such as GAN training.
Several future directions remain. One could explore varying across players or adapting other game optimization meth- ods (e.g., Extra-Gradient) to broader settings without re- quiring strong convexity. Moreover, the decoupled updates naturally lend themselves to privacy-sensitive applications,
players do not need direct access others' parameters, reducing risks from gradient sharing (see Zhu et al., 2019; Zhao et al., 2020; Wei et al., 2020, and references therein), Future work could investigate and further develop Ghost-SGDA to enhance performance in decentralized and privacy environments.
extensions

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Impact Statement
Jain, P., Kakade, S. M., Kidambi, R., Netrapalli, P., and Sidford, A. Accelerating stochastic gradient descent for least squares regression. In Conference On Learning Theory, pp. 545-604. PMLR, 2018.
This work is purely theoretical with no direct societal im- pact. However, our findings can improve communication efficiency in decentralized systems, such as federated learn- ing and multi-agent reinforcement learning, by reducing communication complexity.
Jiang, and Lu, Z. 12: fully decentralized q-learning algorithm. Advances in Neural Information Processing Systems, 35:20469- 20441, 2022.
Acknowledgments
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T. Scaffold: Stochastic controlled averag- ing for federated learning. In International conference on machine learning, pp. 5132-5143. PMLR, 2020.
TC was supported by the FAIR (Future Artificial Intelli- gence Research) project, funded by the NexIGenerationEU program within the PNRR-PE-AI scheme (M4C2, Invest- ment 1.3, Line Artificial Intelligence).
Khaled, A., Mishchenko, K., and Richtárik, P. Tighter theory for local sgd on identical and heterogeneous data. International Conference on Artificial Intelligence and Statistics, pp. 4519-45555 4529. PMLR, 2020.
References
Azizian, W., Scieur, D.. Mitliagkas, I., Lacoste-Julien, S., and Gidel, G. Accelerating smooth games by manipulat- ing spectral shapes. In International Conference on Arti- ficial Intelligence and Statistics, pp. 1705-1715. PMLR, 2020.
Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning. pp. 5381-53999 PMLR, 2020.
Balduzzi, D., Racaniere, S., Martens, J., Foerster, J., Tuyls, K., and Graepel, T. The mechanics of n-player differen- tiable games. In ICML, 2018.
Korpelevich, G. M. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Bravo, M., Leslie, D., and Mertikopoulos, P. Bandit learning in concave n-person games. Advances in Neural Informa- tion Processing Systems, 31, 2018.
Kovalev, D. and Gasnikov, A. The first optimal algorithm for smooth and seggll-ccooveee-ttoony--ooooooe minimax optimization. Advances in Neural Information Processing Systems, 35:14691-14703, 2022.
Chavdarova, T., Pagliardini, M., Stich, S. U., Fleuret, F., and Jaggi, M. Taming gans with fookahead-minmax, minmax. arXiv preprint arXiv:2006. 100006..4555. 14567, 2020.
Krizhevsky, A. Learning Multiple Layers of Features from Tiny Images. Master's thesis, 2009.
Deng, Y. and Mahdavi, M. Local stochastic gradient de- scent ascent: Convergence analysis and communication efficiency. In International Conference on Artificial Intel- ligence and Statistics, pp. 1387-1395. PMLR, 2021.
Laine, F,, Fridovich-Keil, D., Chiu, C.-Y., and Tomlin, C. Multi-hypothesis interactions in game-theome theoreth motion planning. In 2021 IEEE International Conference on Robotics and Automation (ICRA), pp. 8016-8023, 2021. 1oi:10.1109/ICHH 1001109///A4445002202000 95661195...
Facchinei, F. and Pang, J.-S. Finite-dimensional variational inequalities and complementarity problems. Springer, 2003.
Lee, J., Cho, H., and Yun, C. Fundamental benefit of alter- nating updates in minimax optimization. arXiv preprint arXiv:2402. 10475, 2024.
Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio. Y. Generative adversarial nets. Advances in neural informa- tion processing systems, 27, 2014.
Li, S., Wu, Y., Cui, X., Dong, H., Fang, F., and Russell, S. Robust multi-agen reinforcement learning via minimax deep deterministic policy gradient. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4223-4220, 2019.
Ibrahim, A., Azizian, W. Gidel, G., and Mitliagkas, Linear lower bounds and conditioning of differentiable games. In International conference on machine learning, pp. 4583-4593. PMLR, 2020.
Lin, T., Jin, C., and Jordan, M. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pp. 2738-2779. PMLR, 2020.
Jagadeesan, M., Jordan, M. I., and Haghtalab, N. Compe- tition, aligmment, and equilibria in digital marketplaces. ArXiv:2208. /4423, 2022.
Liu, M., Zhang, W., Mrouch, Y., Cui. X., Ross. J., Yang, T., and Das, A decentralized parallel algorithm for
10

---

Decoupled SGDA for Games with Intermittent Strategy Communication
training generative adversarial nets. Advances in Neural Information Processing Systems, 33:1 1056-11070, 2020.
using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
Liu, Z., Zhang, X., Lu, S., and Liu, J. Precision: Decentral- ized constrained min-max learning with low communi- cation and sample complexities. In Proceedings of the Twenty-fourth International Symposium on Theory, Al- gorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pp. 191-200, 2023.
Patel, K. K., Glasgow, M., Zindari, A., Wang, I.,, Stich, S. U., Cheng, Z., Joshi, N., and Srebro, N. The limits and potentials of local sgd for distributed heterogeneous learning with intermittent communication. arXiv preprint arXiv:2405. //67,, 2024.
Popov, L.. D. A modification of the arrow-hurwitz method search for saddle points. Mat. Zametki, 28(5):777-784, 1980.
Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, P., and Mor- datch, I. Multi-agent actor-critic for mixed cooperative- competitive environments. Neural Information Process- ing Systems (NIPS), 2017.
Robey, A., Latorre, F., Pappas, G. J., Hassani, H., and Cevher, V. Adversarial training should be cast as non- zero-sum game. arXiv preprint arXiv:2306. 1035, 2023.
Lu, S., Zhang, K., Chen, T., Başar, T., and Horesh, L. De- centralized policy gradient descent ascent for safe multi- agent reinforcement learning. In Proceedings of the AAAI conference artificial intelligence, volume 35, pp. 8767- 8775, 2021.
Sayin, M., Zhang, K., Leslie, D., Basar, T., and Ozdaglar, A. Decentralized q-learning in zero-sum markov games. Advances in Neural Information Processing Systems, 34: 18320-18334, 2021.
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 06083, 2017.
Shafahi, A., Najibi, M., Ghiasi, M. A., Xu, Z.,, Dickerson, J., Studer, C., Davis, L. S., Taylor, G., and Goldstein, T. Adversarial training for free! Advances in neural information processing systems, 32, 2019.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-effiiee learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1pp.1275 1273-1282. PMLR, 2017.
Sharma, P., Panda, R., Joshi, G., and Varshney, P. Federated minimax optimization: Improved convergence analyses and algorithms. In International Conference on Machine Learning, pp. 19683-19730 PMLR, 2022.
Mokhtari, A., Ozdaglar.
A., and Pattathil, S. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference Artificial Intelligence and Statistics, pp. 1497-1507. PMLR, 2020.
Spica, R., Cristofalo, E., Wang, Z., Montijano, E., and Schwager, M. A real-time game theoretic plan- ner for autonomous two-player drone racing. IEEE Transactions on Robotics, 36(5):1389-1403, 2020. doi: 10. 10110/00...00009999200
Nemirovski, A. Prox-method with rate of convergence (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1): 229-251, 2004.
Stich, S. U. Local SGD converges fast and communicates little. In International Conference on Learning Represen- tations, 2019a.
Stich, S. U. Unified optimal analysis of the (stochastic) gra- dient method. arXiv preprint 1907.0420000333 2019b.
Nesterov, Y. Dual extrapolation and its applications to solv- ing variational inequalities and related problems. Mathe- matical Programming. (09(2):319-344) 2007.
Thekumparampil. K., Jain, P., Netrapalli, P., and Oh, S. Efficient algorithms for smooth minimax optimization. Advances in Neural Information Processing Systems, 32, 2019.
Nesterov, Y. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-36,, 2012.
Tsaknakis, I., Hong. M., and Zhang, S. Minimax prob- lems with coupled linear constraints: computational com- plexity, duality and solution methods. arXiv preprint 20. 2021.
Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., and Y. Ng, A. Reading digits in natural images with unsupervised feature learning. 2011. URL http://
FFilosstanfordddd///ousssna
Tseng, P. and Yun, S. A coordinate gradient descent method for nonsmooth separable minimization. Mathematical Programming, 117:387-42. -238, 2009.
Nouiched, M., Sanjabi, M., Huang, T., Lee, J. D., and Raza- viyayn, M. Solving a class of non-convex min-max games

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Tsitsiklis, J. N. Problems in decentralized decision making and computation. PhD thesis, Massachusetts Institute of Technology, 1984.
Zhang, J., Hong, M., and Zhang, S. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194(1):011933, 2022b.
Von Neumann, J. and Morgenstem, O. Theory of games and economic behavior: 60th anniversary commemorative edition. In Theory of games and economic behavior. Princeton university press, 2007.
Zhang, S., Choudhury, S., Stich, S. U., and Loizou, N. Communication-effiiennn gradient descent-accent meth- ods for distributed variational inequalities: Unified analy- sis and local updates. In The Twelfth International Con- ference on Learning Representations, 2024.
Wang, Y. and Li, J. Improved algorithms for convex-concave minimax optimization. Advances in Neural Information Processing Systems, 33:4800-48 10, 2020.
Zhao, B., Mopuri, K. R., and Bilen, H. idlg: Improved deep leakage from gradients. arXiv preprint arXiv:2001.02610, 2020.
Wei, W., Liu, L., Loper, M., Chow, K.-H., Gursoy, M. E., Truex, S., and Wu, Y. A framework for evaluating gradi- ent leakage attacks in federated learning, arXiv preprint PrXiv:2004.1039) 2020.
Zhou, M., Guan, Y., Hayajneh, M., Niu, K., and Abdal- lah, C. T. Game theory and machine learning in uavs- assisted wireless communication networks: A survey. 1rxiv:2/08.034:0 2021.
Woodworth, B., Patel, K. K., Stich, S., Dai. Z., Bullins, B., Mcmahan, B., Shamir, O., and Srebro, N. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pp. 10334-10343, PMLR, 2020a.
Zhu, L., Liu, Z., and Han, Deep leakage from gradients. Advances neural information processing systems, 32, 2019.
Woodworth, B. E., Patel, K. K., and Srebro, N. Minibatch vs local sgd for heterogeneous distributed learning. Ad- vances in Neural Information Processing Systems, 33: 6281-6292, 2020b.
Zindari, A., Luo, R., and Stich, S. U. On the convergence of local sgd under third-order smoothness and hessian simi- larity. In OPT 2023: Optimization for Machine Learning, 2023.
Xian, W., Huang, F., Zhang, Y., and Huang, H. A faster de- centralized algorithm for nonconvex minimax problems. Advances in Neural Information Processing Systems, 34: 25865-25877, 2021.
Zindari, A., Yazdkhasti, P., Chavdarova, T., and Stich, S. U.
Decoupled stochastic gradient descent for n- n-player games. In ICML 2024 Workshop: Aligning Reinforcement Learn- ing Experimentalists and Theorists, 2024.
Xiao, L. and Boyd, Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-77, 2004.
Yoon, T. and Ryu, K. Accelerated algorithms for smooth convex-concave minimax problems with (I/k" 2) rate squared gradient norm. In International Conference on Machine Learning, pp. 12098-1222 12109. PMLR, 2021.
Yoon, T., Choudhury, S., and Loizou, N. Multiplayer feder- ated learning: Reaching equilibrium with less communi- cation. arXiv preprint arXiv:2501.08263, 2025.
Yuan, H. and Ma, T. Federated accelerated stochastic gradi- ent descent. Advances in Neural Information Processing 2020.
Systems,
Zhang. G., Wang, Y., Lessard, L.,, and Grosse, R. B. Don't fix what ain't broke: Near-optimal local convergence of alternating gradient descent- for minimax optimiza- tion. 1.Xiv:/022009466 2021.
Zhang, G., Wang. Y., Lessard, L.., and Grosse, R. B. Near- optimal local convergence of alternating gradient descent- ascent for minimax optimization. In International Con- ference on Artificial Intelligence and Statistics, pp. 7659- 7679. PMLR, 2022a.
12

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Table of Contents
A. Summary of Parameters
Table 2. Summary of Symbols for Two-Player Games
Symbol
Definition
Mathematical Definition
Smoothness parameter for operator F(x)
[[ F(x)1l, & l. ||x x'1l
L
Smoothness parameter for operator (x)
[xx(()) Fx(x')1, L||x x'1
Le
Difference between Fx(x) and F(x)
[xx - -F(x)] & Le ||x -xxx x|
Lu
Smoothness parameter with respect
[V, v) Vu.f(u', vill - & Lu |/u u'll,
I.g
Smoothness parameter with respect
Vef(u, - V.f(u, v')l . & Lo ||v v
Luee
Interaction smoothness parameter
[V,,(u, v) - V V.f(u, V'll Luo 1|v v/ll.
Lygu
Interaction smoothness parameter for with respect
& Low un IV..(u, V V. 1),
Puu
Strong convexity parameter for u
f(u',v) > /(u, +V v), u) Hu ||u ull
Pe
Strong concavity parameter for
f(u,v) s f(n, (V (V.
Me 1| vll.
Strong monotonicity parameter Fx(x)
(F&(x) Fs (x)
||x x(|
Strong monotonicity parameter for F(x)
(F(x) - F(x'), x -x1I
Coupling degree of the game
Table 3. Summary of Symbols for N-Player Games
Symbol
Definition
Mathematical Definition
in
Upper bound for diagonal elements L,s
[a)a(()) Vnfx(x + U,hailln. & L.llballl
En
Upper bound off-diagonal elements Ly for st
[V,.f((x) Vnfa(x Eito U,h,)) n.* & Ln EEin U,b.
Le
Difference between F(x) and F&
[[((x) - Fx) Le ||x xx]
Smoothness parameter for operator (xx
[Fx(x) (x))l, L||x x'1l
Smoothness parameter for operator F(x)
[1((x) - F(x Il, & L ||x x'Il
Strong monotonicity parameter for (x)
(Fx F (x)),
f ||x x'
Strong monotonicity parameter F(x)
(F(x) - F(x)
|x x 2
Hh
Strong convexity parameter for fx(x)
(V.f((x) - Vx U.d,).
xm > M., | -x"
Kc
Coupling degree of game
B. Missing Proofs for Section 4
Lemma B.I. Let (re be a sequence of numbers satisfying:
T1+1 & (1 ar)rr 7b
for constants a, b 0 assuming ay < 1. After unrolling the recursion K times get:
TK & (1 - -a))
(15)
a
13

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Proof.
K-1
rk (1 (1-aa) a7)
Σ (1 ar)'yb
& (1 (11-ay)
+
Σ (1 o7) 27/'/bb>//////// & (1 -1- (1-07) +
1-0
Lemma B.2. For the parameters L, L and from Assumptions 2.2 and 2.3, we can say Le & and L & L.
Proof. Recall that:
[F(() - F(x'Il+ & L||x x'|
[ Fx(x')l& < xxxxxXi x
[x((x) F(X)]1+ & L x- x
we start with the definition of the || Fxx)lla:
1 [u, v) v.f(u, v)
1 V.s(u, v) V.,(ū, v)
|| [x(x))
12x)
au
Or
1
|V v) v.J(u, V)l
V.s(u, v) - v..((u, v)le
0N
Op
1 Vv,((u, v) - v.J(ū, v) |Va](u, V.,(ū, v)l
1
[I v) - F(u, v) |F v) F(ū, v)ll
L'av ||v v1l + Laa.,
-ll -
L3 x||
which means that we can upper bound [|F(xx) - 11x) by the constant at the worst case. However, the constant Le that we use can be much smaller. Next, for the the inequality [|(x(x) Fx(x') I| we have:
|| [x(x)) Fx(x111+
1
(u, v) Vas(u', 1)
1
V. v) V.S(ū, v¹) 1l
0a
ap
1
Vns(u, v) V..(u', v)
V.s(u, v) v.S(u', v) 11
0n
Or
VV. v) - v. v )l
V.l(ū, v) V. v.,((,,
Oh
0n
F(uu, v) - F(u', v) + F(ū, v) - F( v') 1
< LLaa I - u' ll L. Vv- v/ = L x
which means we can upper bound |F&(xx) much smaller.
Fx(x')] I| by the constant the worst case. However, the constant can be
Lemma B.3. Given SCSC game f(u, v). If the parameter Le from Assumption 2.3 is zero, the game is fully decoupled and players do not interact.
Proof. Recall that game can be expressed as:
f(u, v) g(u) h(v) + r(u,v)
We only need to show that I., implies r(u, v) This means that each player's payoff is affected only by their own strategy. Also, recall that L. you. max Loes L.n where Luv and Lva are defined as follows:
[V, Vuf(u,,v)la. Lao laallv v'lles [V.f(u, v.f(u', v)lloc & Loullu ul
14

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Since it is clear that if Le O, then Lue Lvu the right-hand side of the above inequalities must be zero. Now, rewrite the left-hand side of these inequalities in terms of the functions g. h, and r, which must also be zero:
ug ( + Var(u, - Vug(u) Vur(u, V' [v,((,, - (u,(u, ul = |V
= / Vur(u, v)),,,
For the above expression to be zero, either r(u, v)
Vur(u, Vur(u, v') must hold. However, the latter is impossible, it implies that r(u, v) depends only which contradicts our assumption (if a term depends only is already captured in g(u)). The same thing can be shown in the same way with respect to player v.
Lemma B.4. Let X, x', x" X be such that Fx(x') F(xx) = 0. Then,
|| x & Ne ||X x"
(16)
Proof. From Assumption 2.1 and the Cauchy-Schwarz Schwarz inequality, it follows that [Fx(xx) - Fx(x*)1 > A - x=1 Hence,
|X x"1 & [|xx(x))) - Fx(x*)]
1 [|F(x*) - (x <
Le 1 - x"11 = Ko ||x x"11
Lemma B.5. For any E X, the operator F& is p-strongly monotone with
Pu
Ho
p =
min
On.
Proof. Recall that function f is -tronnyy convex in and str-snyggly concave in v meaning that:
(Vu((u, Vus(u', v), u - u'> > pallu u' 1 (V.((u,v) VoJ(u, v - v) * -.llv- v'I??
Therefore,
(Fx(x) - [x(x),x->
= (V,((u, v) - V.J(u', v), u --'--'- (V.((ū, v) - V.J(ū, v²), v'
> Mu u u' 1| + Mw || - v = Ha
au
u u'll2 + He
av || v112
> min
Mu Mu
|x 12
au Or
Lemma B.6 (two-player). For any E X. parameter Le can be expressed as:
L
max/Luv- Loui.
vadae
Proof. Recall that:
Vuf(u,, v) - Vuf(u, v'lluu & Maollv-vvll
v.f(u,v) - Vos(u' v)),v, & Lou u1llu
Next have:
F(x) - Fx(x)]1 =
Vuf(u, v) Vaf(u, v) vuf(u,v)l2 + V - V.f(ū, v
au
22
L
|| v/1 +
||u ull?
au
Op
L2
12
Or ||v
v/
ag au || -il
a,aa
L2
L
[o0 villllvia - vV1?? +
-- ] 1 ||x x||
max
agar
ava
15

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Lemma B.7 (two-player). Lel X, x6:x* X be such that Fx(x
and F(x*) = O. Then Fig can be expressed as:
au
Luv
av Lou
max
(V Ov
(17)
Muu
Ou Mr
Proof. Indeed,
|| xx0
x*11²= = 0uu
ju - 1l + au |V -v'1
au
V VuJ(u', v) - Vuf(u', v)
+ ag
-Vvf(u,
au
[Vnf(u", Vuf(u', v) + a
Vef(u',v") - V v']l,
m
Oa Tie
Ogp I2
- v" 1 +
|| - 1'll
pa
ag L2
a L2
Ogp ||
+
Ouu [ 1='l="
Calli
On 1
Og 22
E max
[ ||
v + au || - u² ['] = =ke || x²1
2
B.1. Proof of Theorem 4.1 in Weakly Coupled Regime
In this section, we provide the proof of convergence for our method in the weakly coupled regime. In contrast to the common assumptions and proof techniques, we utilize our new parameter Le. which quantifies the level of interaction in the game. We demonstrate that if the fraction Lu is sufficiently small (i.e., the game is weakly coupled), we can achieve communication acceleration. This aspect is often overlooked in the analysis of games, as existing works tend to disregard the possibility that player interactions might be very low which results in a pessimistic rate. We start with the following auxiliary lemma.
Lemma B.8. For any xa E X' that satisfies Fo(xt)= O where Fo(x) Px-xo (x), after K steps of Decoupled SGDA starting from No with stepsize of & F. we have:
E 1|100 x;l1? + 70²
E
| x x6l1 (1-178))
(18)
Proof. We start by upper bounding the iterates generated by our method from xi at time step 0 +++ & K using the update rule of our method. Recall that Go(x, { = GR=xo (x, <) where X (uo, Vo).
P |x++1 xil ll 2 | - P G (x {t) x112
= ||x, x|112 + 7² (x,,, 11 - (G Ex), -x0).
By taking the conditional expectation on previous iterates we have:
E& Xx+1 x
< |x xill + 7 [[)()))) - Fx(xi)1 - (o(()) - Fo(xo), x1 xx) 720
(1 2n + 72 ||x: x;,1 2 722
With the choice of 7 & f/z and taking the unconditional expectation we have:
E x| x 2 < (1 - yp) E ||x
xill2 2220
After unrolling the recursion for K steps using Lemma B. we have:
K
| xil1 (1 yp)) K E E| x111
2202
702
(1 yp) k
E 1|x0
x112
p
16

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Now are ready to prove the main theorem.
Theorem B.9. For any R, K > log ( after running Decoupled SGDA for a total of = KB R iterations on a function f. with the stepsize y & 22
P. in weakly coupled regime (ARe < 1), we get a rate of:
8y0²
E
|| R
x1]]
x
n + & D2 (4Ko))
Re
1 1 Ane
where D= = ||x0 - x"1 ||-
Proof. We start by upper bounding the following term where x; = =(ue Vz) is the parameters of players at some round r after t local steps.
|x++1 1x1 < 2 2||xc+11 x5ll² + 2 ||x] - 1x11
(19)
where x e X satisfies (x = Recall that (xx) = (V..(upg. Vv. vo)). The point ug is the minimizer of given fixed v = meaning that un arg min f(u, v) and vo is the maximizer of given a fixed u meaning that v arg max,ex, J(ū, v). Note that know such minimizer and maximizer exists as the function is strongly convex in u and strongly concave in
For the first term we use Lemma B.8 and we get:
xil1² + 70²
E ||x411 xxll?]
<(1
E |xx
Putting this back in (19) gives us:
[|+11 - x²1
< 2(1 - yaa) K E [|300 - x611² + 2E ||x x" + 2y0²
a
2 ya) E ||x00 xill + 2kz E xo x" x²1 + 2y0²
2y0²
< 4(1 - >p)* KE ||x00 - x11 + 4(1 - >²)* K E ||x - x=1 + 2xo E 11x00-x0 - xx112+
1
< 4(1 > E ||x00 x22 + (4(1 >p kk ke + 2kee) E l|x00 xx1 + 270²
p
< (4(1 - 72)( +4(1- - (1)) K Ke 2nie) LE' 1|x00 - x1= 270²
2y0²
<
+ 4exp (->ūk) Ke + 2x. E |xo
x=1
where we used Lemma B.4 in the third line. Now we need to make sure that 4 eepp (-7ūK) & No & which is implied by
K
log 7p
n. Next we have:
E [X x 122 & E|xo - x" x11 + 270²
f
The above recursion can be re-written in terms of two consecutive rounds:
112 + 2
E X
x11 4k. E |x
After unrolling the recursion for R rounds using Lemma B.1 we have:
17

---

Decoupled SGDA for Games with Intermittent Strategy Communication
x'1 + 270²
B l|x - x' 1|² (4xx) R |1xo -x'1'
(4K))*
Note that we assumed the game is weakly coupled which implies that 4Ne & 1. Finally we have:
2
E ||x x' x²1²² & (4Hic) "B "B||xo
x²1
+
(Ame))
f
8y0²
$ D2 (Axic)#
R +
1
4ric
B.2. Proof of Theorem 4.1 in Non Weakly Coupled Regime We start with some auxiliary lemmas.
Lemma B.10. Ler (ra)ezo be non-negative sequence of numbers that satisfy
b
T1t1 & (1-a
rs + oy +g00
K²
K
K+]
for constants a >> 0, b, e b and integer K3 > and a parameter 7 > 0, such that ar & F. 1fb < 9. then it holds
2c
rt.
2)-
+
(20)
Proof. By assumption on ry:
(1-2)
47
b
T++1 &
2
Ft
2
+
K
+
i=max K+1}
and by unrolling the recursion:
Tt+1 (1-a2) ro +
Σ
1
a7 b-i
ay
+
K 7
b
Tj
+
Σ
1
a7
2
2
2
1-0
j=max (0,i K+1]
1=0
& (1 2
)
+
Σ
1
a7)
a7
2 pi
+
b
7
Σ
rj
+
2c
2
K
1=0
(1- - 22)²
ro +
Σ
[ -
ar)
2
b-
ay
2
ri
+
K
Σ
(1-
07
2
Ni
+
-
2c
a
i-0
==
where we used 0 2g
& ay
(for (77) < 1) for the second inequality.
By estimating
07 ri
+
Σ
(1-
a7 i rr x
a7
2 ri + K²
Σ
(1
a7
1-K
ri
2
K"
2
2
K-1)
j j_max(0,i-KK-
a7
2 ri byr, (1 09)
<
ri
a7
2 ri 2byr $ $0,
18

---

Decoupled SGDA for Games with Intermittent Strategy Communication
with and (1 - & 2 for a7 R. and the assumption b < 4 (and rg > 0).
The validity of the inequality, (1 - ---)) - & 2 for ar के can be shown in the following way:
(1- an 1-K
2 & [1 - (2 K
2nk
For the last inequality above we used the approximation (1 - x) -n & t: for x i and n > 0:
Given that a7 & t we have:
2 e
Thus, we have
(1-
ay 2
1-K
$ 2
Going back to the main proof, we conclude
T++1 (1
a
2c ro
7.
2
as claimed.
Lemma B.11 (Consensus error). After running Decoupled SGDA for K local steps at some round r with a step-size of y & 32bhek for any constant a < I., the consensus error can be upper bounded as follows:
x++1 - xol12
E B|[x; - x²1 + 4K-202
(21)
64KI2
Proof. Recall that Gu(x, x) = Gx=xo (x. {) and Eg[Gu(xx c)] = (x)) where X = (uo. vo) refers to the parameters of each player at the beginning of some round r. Using the update rule of our method we have:
E X
xoo
-Go(xx,)) Xo |
E
X
7P
E
X
7P Fo(x)) - xxol2 + 7200
1 1
E -xol2 # 22 ( +
K
1+ K
E E|x, xx01 2 - F(x,) + FIx;) +220²
1+ K
E E| x-1 + 2 (x:) - F(Xx)) 4K 11 72202
1 K
E E x + 4KT E || xol1 44K2 E| x11 + 7202
With the choice of 7 &
32KLL.
we get:
E
[||x++1 - xoll2
a²
+ K
E.
| Xpl
E ||
2
+
E B||x: - -x11 + 222
256K L
256K
1
a
+
E
||X
xul1
E ||x:
x
E |||x x-12 x"1 7220
K
256K
256K
1
1
d²
1
+
E
[[x
xo112
E
El|x:
x1
2202
K
256K
256KL2
19

---

Decoupled SGDA for Games with Intermittent Strategy Communication
where in the third line we used the fact that a² steps and considering the fact that (1 + 256K
due the assumption L. By unrolling the recursion for the last K
4 get:
a²
xx41 xoll2
Σ
E ||,
x²12²
64K
i=t+1-K
Now are ready to prove the following theorem.
Theorem B.12 (Decoupled SGDA for two-player Games). For any R. K, after running Decoupled SGDA for total of the non weakly coupled regime, we
T= iterations on a function f, with the stepsize y & min { 2 KLL. Riz
xtz
get a rate of:
200g
x # x²1
D2 exp (-2 KR)
where D l1x0 - x-1
Proof. We start by upper bounding the iterate x at time step t + 1 from the equilibrium. Recall that Fo(x) = Fx-xo (x) where refers to the parameters of players at the beginning of some round r.
X - x'
Xx P Go(xx: 5) - xx x-1 + 220²
X PP Fo(xe) x' 72202
E X P -P1F((x)) F((x)) x + +p 7p-1111 =F(x)) --P-1 + 72202
< 1 + 7/
EB ||x - F(X)) xx ||| + (1+
2 2) E B(|F(x)) Fo(x))ll + 7220
2
/
(1+ 2
7/0
[||x x3 1 + 722 F(x:)) F(x*))l -x(F(xx) x(x'),xi-xx
7 ( 2
[xx)(x (x( 1/ + 72202
(1+ 2 )
7H)
(1 7 27/44 E ||x: - x²1 + (7+ 2 [|(((x - Fo + 7720
1 7/0)
[1] 7/14) E [|x, - -xx-x=11" ||]
37
E Fxx,) Fo((,)) 11= 72202
+
2
7/4 E 1|xe
x21
37
E
1|x+
xul1 11+ 77202
2
/
Where we assumed that y v 8.2 Now by using the upper bound on consensus error from Lemma B.11 and setting a = we get:
E | - x12
= -(1- (1-24)
EE |Ix:
x²1 +
7/ 16K
Σ
E l|x
x11 + -1+ 12KYL2
7202
m-max (0.t-
K}
20

---

Decoupled SGDA for Games with Intermittent Strategy Communication
With the choice of y
12K have:
E X 1=1
(1 (1-27 2
7/ E I|x -x"1' 1 +
7
Σ
E E| x-112 + 2
16K
max (J
By unrolling the recursion using Lemma B.10 we get:
(-22
122 R
_ o2 p
E B
x" & D2 exp
D2xxp
C. Decoupled SGD for N-player games
In this section, we generalize all previous results on two-player games to N-player games. We first introduce the notation that is needed to define N-player games and will be used to establish our convergence guarantees.
C.1. Setting and Preliminaries
Notation. We consider unconstrained N-player games where each player x belongs to the space X; = R24. The vector X = xx² E IRd is defined in the space = 21 x ... x AN = Rd with = Ei= d,. The space X, for all i E [N] equipped with a certain Euclidean norm, ||x == (Pix x22 where P, a positive definite matrix. The norm in the space X' is then defined by ||*|| = (Ei-1 ai||x ( 112) where > 0; thus, ||x|| (Px, x)1/2 where P is the block- diagonaa matrix with blocks o; P, (P diag(a)P1..... a........... pN)). The dual norms are defined as: |g: kill := Pg gi) 1/2 )/2 (gi Xa,) and |g -
1/2
max g. x²)
(E lg P 1/2 (g, P P..P)g)) -g)g g/2
(g gg. gN) X).
Similar to the work (Nesterov, 2012), we define the following partitioning of the identity matrix:
N
I = (U,, U2,... UN) E Rddd d =
Σ
de U, Rdxd
Now we can represent the vector x as follows:
N
X = Σ U EX
We can extract the parameters of one player as follows:
UJJxx E Xx
Problem Formulation. An N-player games is defined as:
(x), minfa (x)) x
(N (N-player)
Where fn: X
The goal is find the Nash Equilibrium in x* property that if one player changes their strategy, their payoff function will increase. In other words, there is incentive change one strategy alone: for all h, Xn, it holds that
N) like in the work (Bravo et al., 2018), which has the
fn(x') fn(x" U,
(22)
21

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Moreover, we define the operator (x) X' X' with respect the fixed point x X which denotes the stack of gradients with respect to each player's parameters as follows:
(x) = (Vif( + U,h), VNfN(X+ Uxh))
Where h = x &. We can recover the commonly used operator as F(x) = Fx=x(x)= = (Vi](x)) VNff(x)). Note that for the equilibrium, it holds that F(x*) while general Fx(x*) * O. We can extract the partial gradient with respect one player as follows:
V vnnn(x) = (x))
We now present the assumptions required for the convergence of our method. Assumption C.1 (Strong monotonicity). Operators Fx and F are strongly monotone with parameters j4, H. > 0, i.e., for all x, x, E X, the following inequalitics hold:
(F&(x) Fx(xx)) x jil pa|i x'12.
(23)
(F(x) - F(x'), x u x - x' x11
We can show that |a|lx"" - x" ll..
) (Proof in Lemma C.8) where (VnIn(x) Vnfa(x + Undr),, x"
Assumption C.2 (Lipschitz gradients). Operators Fx, X + X' are Lipschitz with parameters L and L if for all x, x,x's x, X, the following inequality holds:
[[x(x)) Fx(x'))lx I1 & L||x x'I [[((x) - F(x') I < L||x - x'|l
(24)
Assumption C.3. The norm of the difference between operators Fx Fx(x) and F(x) is upper bounded with parameter Lg for all x, X 6 X as follows:
Fx(x)) F(x)ll+ < Lellx- x||
(25)
It's possible show L (max Ej ; 1/22 where I.,, is defined as VV]f(xx) VnJn(x Eienn U.h,))l x
EnllEsen U,h;|| || for any E X' and any h, Xn (Proof in Lemma C.9). The parameter L,, corresponds to smoothness parameter of fn when we take gradient with respect player while varying all other parameters (and fixing the parameters of player n.). If Ln 0 for all n, it means for any two players i, [N], i # j, they have no interaction.
Assumption C.4. There exists finite constants /² such that for all x, x X::
Eg [x] (x 2 < 0².
(26)
Where [[)x(x, (x)..
As we assumed that the above inequality holds for all x e X, we also cover the common operator F and denote
G(xx, { (x.
C.2. Method
Local update methods. As discussed in the two-player section, Local update methods proposed reduce the communi- cation overhead in distributed optimization. In this context, it's reasonable assume each player has access to their own stochastic oracle (x, for all i e [N] with the property [[G,(x,()] F(x) and following bound on the variance of the noise:
[x 4) [F(x) < o
(x] E)1, [F(x) [| < of for i +
However, as we discussed we are considering a setting where the players may not have access to other players' strategies or gradients, and only assume that the private components of the gradients have bounded variance (σ² N o On
22

---

9: end for Decoupled SGDA for Games with Intermittent Strategy Communication
the other hand, local update methods require the variance oi be bounded as well while we allow that be arbitrarily large. We introduce the oracle Go xx <) Gx-x; (x, for i {u, e) where Xo (uo, vo) refers the parameters of
each player at the beginning of the round. Our operator only uses the reliable information which is [G,(x, E)]s for player i. Now we can write the update rule of our method as:
x x pP Go(x,
(27)
where
G) = (Vif((x- + U,U, (x x))):
Here, the index t denotes the local update step in the current local update phase on player i, and the superscript indexes the local phases. One communication round is needed for exchanging the updated parameters x when passing to the next round. Note that x E X; and x X.
Algorithm 2 Decoupled SGD for N N-player games
1: Input: step size initialization (x).... (x. x)) R, K
2: for F (1,..., R) do
3: for E KI, do
4: for n (1...., ]] parallel do Update local model x 6: end for
5:
x, yan
" Vnfn(xo Un(x} xx):
7: end for
8: Communicate
K
1rr .....
N.r XK
to all players
Output: x
(x
1.
N.R.
C.3. Convergence Guarantee
Now we out to a change in the definition of weakly coupled games in --llayer setting. Definition C.5 (Weakly Coupled and Fully Decoupled Games). Given an N-player game in the form of N N-player, We define the coupling degree parameter Kg for this game follows:
L
(28)
f
This variable measures the level of interaction in the game. A smaller value of Ne indicates less interaction. We say the game is Weakly Coupled if the following inequality holds:
(29)
We say the game is Fully Decoupled if we have 0 which implies each player is minimizing their own pay-off function independently.
Theorem C.6. For any R 3 and any K log (..). after running Decoupled SGDA for total of KRR iterations on a function f. with the stepsize r & La in the weakly coupled regime (Are & 1), we get a rate of:
7p
J2y 8kc +
E||| - x D2 Dxp (xxpp1(11 (x)
r 1 - 4Kс
Moreover, For any R, K 2 1, after running Decoupled SGDA for total T K.R iterations on function f, with the p_ stepsize y & min { to R.I. } in the non-weakly coupled regime, we get a rate of:
E E[xx -x1
D exp
(- 74 KR
20
23

---

Decoupled SGDA for Games with Intermittent Strategy Communication
where D x 1- Corollary C.7. With the choice of
P RI if the game is weakly coupled we get:
B[1x [7] & D2 exp
exxp(1(( (-(11 (xx) + 0² Ru - 4xi.)
Consequently, to reach x - x & it suffices to perform R max
4-Me log( 2D
1 4xc)e) rounds with
K 12 l.)( Moreover, with the choice o min a coupled we get:
pKR log(max(2, -2 K R))} if the game is not weakly x²
32K
112 +
E ||x R
x*1 & D2 exp
212
R
H²KR
Consequently, to reach B[||* - xx11 & it suffices to perform R
2L log(
D2 with K
28²
n²²
C.4. Missing Proofs for Section C.3
Before establishing the convergence results, first need couple of auxiliary lemmas for N-player games. Lemma C.8. for all x, &, x e X, the operator Fx ji-ttrongly monotone where ji can expressed as: we have
n
(30)
Proof. First recall that that each fn is u4, -tronngy convex in x" Xr meaning that:
(Vnf((x) (xfx(x+ x,d,),x" - -x"> Mm 1| x²11
where dn = x" x". Next we have:
(Fx()) xx(x)),-xx)
N Σ (x)(x) v.f(x+ + U. di), x² xt)
Σ m x -
H4 - Σ
ai
1-1
min
[4 ||x
x112.
0;
where d, = x x
Lemma C.9 (N-player). For all e X, parameter Le be expressed as:
1 L = max Σ
2
(31)
J4i C3
Proof. Recall that for each n e [N], there exist constants L,,, In 3 0 such that, for any x X, any h E Ci.... by e XN and any n E [N], holds that:
[V)ff(x) Vnfx(x + Unbn)llnn & En
(x)x((x) Vnfn(x Eien U,h;)llnx In Eilli U,hill-
24

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Next define h, X² - x² and V Exti , and we have:
[|xx(x) - F
Σ
N
1
[V,f((x)
Vifi(x v)l
N
||vl
03
aj
N
L
N
Σ
Σ
Σ 3 ||: 1:
0
Li where 3, = -Eiti ay"
Defining now L = maxi SS we get -i=1 3,ay ||h:l < L3 hl]?
Lemma C.10 (N-player). Let X, x', x" E X be such that Fx 0 and F(x*) 0. Then Rig can be expressed as:
Ki
max N
)12
(32)
jti
Proof. Let's define h, := x3 x', di == x
r = x i
x
Si ==
x
x" We first introduce the point x' Rd as
follows:
x' (x" ,.... x x"
arg min fi(x + U,,,
j
|x
x=1
a4 x - x
2
Vifi x + U,d. + LU, Vif.
x+ U.U++ Σ UUn,,
jzi
N
v.I((x*) - Vifi
x+ Ur., + E,,h,
Σ
U
jfi
i-1
j+i
N
Σ
ag |s,s|, <
Σ
3,0 |s:11 < 1s1
f+1
where 3, = 2
1 M
and Ke == maxNN VB..
More details on smoothness parameters for N-player games. for the better understanding of the smoothness parameters:
For N-player games, we can define the following matrix
in
L
Ln
L
(33)
Tm
ix
In the above matrix, the row number corresponds to the player with respect to whom we are taking the derivative, while the column number corresponds to the player that is fixed, with all other parameters changing. All the elements I on the main diagonal of the matrix measure the strength of each individual player, while the off-diagonal elements Lip for i * j measure the interaction between players i and j. We assume that all the diagonal elements are upper bounded by f., and all off-diagonal elements are upper bounded by Ln. Here n is the player which is being fixed. The parameter Ln, measures the interaction of the nth player with all other players.
With the use of these Lemmas, one can easily extend the proof of two player game to the general N-player games.
25

---

Decoupled SGDA for Games with Intermittent Strategy Communication
D. Decoupled GDA for Quadratic Games
To provide an extra insight for the results we showed so far in Section 4 and support them with a separate analysis, we additionally consider analysing our method for quadratic games with bi-linear coupling between the players which are sub-class of SCSC functions.
Problem formulation and Notation. Recall that we consider unconstrained two-player games denoted by u and the spaces X, dd and X. Rd,, respectively. The corresponding product space X' Xr x X, Ie (with d = d, + dy) consists of vectors (u, v) R4, where Xn and X.,. We assume that the spaces X., and Nr are equipped with Euclidean norms, denoted by | |/v The norm in the space X is then defined by ||||| = (a ||| + 12) where a,3 3 > 0.
We aim to find the saddle point of the following function:
1 (v, Bv) + (u, cv) (u, = / (u, Au) 2
min max ueX, VER,
(QG)
where A E $4, and B E 84, and C E Rd. Recall that we defined a general two player game as f(u, v) g(u) - h(v) + r(u, v). For the class of quadratic games, we can be more specific as functions g()) and h(.) are quadratic functions and r(-) is just a linear term. Moreover, we can be more precise about the smoothness and strong convexity parameters as they are correspond the maximum and minimum singular values of the matrices A, B and C. The matrix players it's the only term which involves both u and It's also easy to
C' can be seen the interaction between verify that for quadratic games in the form of (QG), the saddle point is at x* 0), For clarity and ease of comparison other related works, in this section we assume = B 1.
Definition D.1. Consider function f: X' R in the form of (QG) for some Kn, N.. The Lipschitzness and strong convexity/ / concavity parameters can be defined as:
Hu A Lu and My B L
Moreover, we use the norm of matrix to measure the strength of the interactive part of the game.
Lue Leu == ||C||
Note that we assume Teuv Teva which always holds for twice differentiable functions. Now give explicit formula for the iterates generated by our method on quadratic games.
Lemma D.2. Given a two-player quadratic game in the form of (QG), At some round after K local steps with a stepsize y & max L L. ), the exact iterate generated by Decoupled GDA is given as follows:
x = -
E X
-I-
A)
0
0
E,,
Q
E =
(34)
0
(I-rB)
Ep 0
I-
Eg == [ (I (I-7B)* B B
After taking the norm of both sides we have:
|x /I & max {(1 (1-110 -Vpp) ),, [,, [1 ||||| max (ō 8 (B)) 1/2
(35)
8(A): = (1 - (1 (1-7Lu) R22
8(B) = (1- - (1 - -., )3
22
22
26

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Remark D.3. For quadratic game in the form of (QG), the saddle point is x* (0,0). We expect method to shrink the norm of x in each round by factor less than that converge the saddle point.
Lemma D.2 shows the dynamics of Decoupled GDA for quadratic functions. We can decompose the exact iterates and write the sum of two matrices Q and E. As Q is diagonal matrix to the power of K and we have that y & max 2. L. ) know that when K oc then Q O. The second matrix E can be seen an error matrix which caused by the interactive part of the game. It is clear that if the game is fully decoupled which implies C converge only with local steps without the need for communicating. However, for the case that have this interactive term and the game is weakly coupled, we have to upper bound the norm of this error matrix to derive the convergence rate. We first re-state the notion of weakly coupled games for quadratic games and then provide the convergence rate of Decoupled GDA for quadratic games.
get the trivial result that
Definition D.4 (Weakly Coupled and Fully Decoupled Games). Given quadratic game in the form of (QG). We define the coupling degree parameter Re for this game as follows:
1 Nuu
==
||||
max
(36)
This variable measures the level of interaction in the game. A smaller value of indicates less interaction. For any quadratic game, we say the game is Weakly Coupled if the following inequality holds:
Ne
(37)
We say the game is Fully Decoupled if we have Kg which implies r(u, v- -.
Theorem D.5. For any R and K B 1 with a stepsize of & maxt t.m, T..) which ensures 8(A) & 1 and 8(B) & 1. after running Decoupled GDA for a total Tf = R iterations on a quadratic game in the form of (QG) assuming the game weakly coupled, we get a rate of:
||"
x"1
& D
exp
(- Mmin K
+
Liw Mmin
R
(38)
Where T.max: : max Tuu ]oo) and Muni
min(fuu: Hor)
Theorem D.5 clearly shows the effect of local steps and communication rounds which gives more insights about our method compared to the SCSC case. We can see that the first term in the rate goes to zero with taking more local steps while there is another term that is not affected by local steps. It's indeed intuitive as we don't 't expect our method to converge with only local steps in general. The remaining error is do to the interactive part. All the previous results discussed for SCSC case can be applied to the quadratic setting as well.
D.1. Missing Proofs from Section
We first introduce some auxiliary lemmas that are needed for proofs.
Lemma D.6. Let A be a positive definite matrix and > O. Then matrices A and (I 7A) are commutative meaning that:
A A-' - 7A) = -1-7A)A-
(39)
Proof.
A A - AA
A -1
(I AAA
27

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Lemma D.7. Let A be positive definite matrix and ? Then matrices A and (I 7A) are commutative meaning that:
A AI (II-AA)* =I--A)A
(40)
Proof. By induction we assume that this statement holds for K which means A AII(I-AA)* - -(I- -II- (I-7A)KA-! Now we show that this statement holds for K + 1.
A -I- -I
AA AA AA)
A
(I 1---AAAA-- AA)
= =(I -I- (I-ZA)(T A)) A-1
(I (I- [I-7A]K+IA* A-1
For the case of K = 1 we use the previous Lemma.
Lemma D.8. Let A be a positive definite matrix and 7 e 0. Then we have that:
A A- A(I-(AA)) 1) (II-7A) 1) --
(41)
Proof.
A- A (I- -1)
-A- 7A) A
= =(--7)* A-1 -1- -1
-(I-~A)K - A
D.2. Explicit Iterates Generated by Decoupled GDA
Lemma D.9. Given general quadratic game in the form of (QG). After l steps of Decoupled GDA at some round r we can compute the explicit form of iterates as follows:
u - - (I- (Au, Cv²)
B- up + B
(I -I-73-1 (I-78-''B) (Bvī C CTu)))
28

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Proof. We use induction for the proof of this lemma. By using the update rule of Decoupled GDA we have:
u = U2 7 Vul(ug, vo)
= un 7 (Auj + Cv-)
-AA''CV + A- AI----A)* (Aug + Cv))
-7 (Al -A- + A (I- (Aug + +Cro) + Cv²)
A CV + A-' (I->A)* +Auj+
-7 (-Cr + +1 (Au. + Cv-) + Cv6)
A CCv + A- (I- (I- (Au Cv,) - 71 - -7A)* (Auj Cv.)
-C'' + (A-1-11) (I- (Aub + +vvi)
A 'CV + A A- A[( (I -A) (Aug+ + cv
- A CV, + A A- "(I-AA) k+1 (Auō + Cv.)
Now we only need to show that our claim also works for ht = 0,
U A 'Cv + A- (I-18 7A) "I->A))
+ (Aū)+Cv))
= - 'Cv + up + A 1-AA-CC 'Cv
ub
Also, we do the computation with respect to
C u5+ (I- (I (Bvó - -C c'u))
By using the update rule of Decoupled GDA we get:
v = Vk - Vvv(uu uf()
=v*+7 7- + C
CT)) ug)
=Vx-7(BV - -C ug)
= -B-'C.u + B -
BB)
8 (Bvg - CTub)
-7 B B c up + B (I (I- (Bvg - -C- cTui)] - cT cTub)
= CB up + B (I [1-11) B)* 8 (Bvj - C un)
- CC ug + (I BB (Bvj C cTuu)) - C CTu))
= -B-'C + BB 1
(Bvg - C uw) - - - BB)* (Bvū - c²ub)
= =B-'c u/ + 1
(I (I-7B)* k (Bv; - C. [u]]
= B BB u + B - (I- BB)
(I->B)* x (Bv) - cTuu))
=B-'c up B- [I (I-B)** ++1 (Bvg C CTuu)
29

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Now only need show this our claim also works for k O,
V B C up + B (I (I->B)" (Bv; CTuu) C up + v -B C
B
D.3. Proof Lemma D.2
Given a two-player quadratic game in the form of (QG). some round after K local steps with a stepsize of y <
max Ti t.g ). the exact iterate generated by Decoupled GDA is given as follows:
x 1Q X
(I-
0
0
E.,
Q
E
(42)
0
(I->B)
Ep
0
E, = -- (I-
A ([---)AAAA'CC
E. [ (I (I- [ CC
After taking the norm of both sides we have:
| || & max {(1 mpa) K (1Hb) } + ||]|| max (o(A), 8(B) 1/2
(43)
8(A) == (1 - (1 (1-776 (1- )22
8(B) = (1 (1 - (1-7L,)*) )22
Proof. From Lemma D.9 we can write the explicit iterates for the variable x:
k
I A
0
0
E,,
|
+
||x0|||
(I
B
E
O
II AA
0
E,
+
||>
(I-rB)
E,
E,,
< max {11 - ) /,, (1
)
||x]|||
+
||x6||
E
O
For computing the norm of the error matrix we need to compute v Amax
E).
We first form E E;
E.
E E
E. E.,
So we have:
Amax (E'
E) (E
max (mmax En),,
Eu), Amax (E. E.))
30

---

Decoupled SGDA for Games with Intermittent Strategy Communication
For computing the Amax E Eu) have:
Amax
En)
Amax
CC A I- (I [I I- (I- [-
[ max
A [ (I- [-- I- (I-[-AA)]A-]
|C|| Amax
(A-T) Xmax
(1- Amax (1I (I (1-~44 ()-))))] Amax (A-1)
|C|2 (1 (1 - >maxx (A))8}2
X (A)
|
We have the same computation with respect to player v as well which gives us:
(1
7 max )2))
Amax ( E.)
||a||
min (B)
||C||
Note that using the assumption y < max( 1 L. b.) we make sure that 6(A) < 1 and 6(B) & 1.
D.4. Proof of Theorem D.5
For any R and K > with a stepsize of y & max L. L. which ensures 5(A) & and 5(B) & 1, after running Decoupled GDA for total of KR iterations on quadratic game in the form of (QG) assuming the game weakly coupled with 1, we get a rate of:
(- Mmmin K
Leae Mmin
R
|
x"1
& D
exp
(-Lmax Lmaxx
+
(44)
Where Liax = max Ieny [ and Pmin = min(fhus Mor3.
Proof. Using previous Lemmas we have:
|
Eu
< max - ((1-))4m) K (1 (1-
=) -1|x5|l +
||x,||
E O
1
& max {(1 (11-))44) (1
mm4) "} -|xx5| + ||C|| max
||x6||
"Amin (A)' Amiu (B)
<(1-7Ppmnn))
|C||
||x||
Pmin
After unrolling the above recursion for R rounds get:
||]|| R
x B (1
(1-7//min)
Pmun
E. Additional Related Works & Discussion
E. Decentralized optimization
The key difference between decentralized and distributed minimax approaches the presence of a central server. In the former, there no central server, and nodes communicate directly with their neighbors, whereas the latter, a central server
31

---

Decoupled SGDA for Games with Intermittent Strategy Communication
aggregates the parameters. Our method belongs the category of distributed methods. However, we will discuss later on that our approach is completely different from the general idea of distributed federated optimization.
Decentralized optimization is widely studied for the case of minimization (Xiao & Boyd, 2004; Tsitsiklis, 1984) with the goal of not relying on a central node or server. This idea is also applied to the case of minimax optimization problems. decentralized minimax. They also used the idea of optimistic gradient descent and achieved a rate (E 12). In (Xian et al., 2021), authors proposed an algorithm called DM-HSGD for non-convex decentralized minimax by utilizing variance reduction and achieved rate of O ?) Recently authors in (Liu et al., 2023) proposed an algorithm named Precision for the non-convex- wwwneeee-ssroggly-onneee objectives which has two-stage local updates and gives a rate of ((+).
The paper (Liu et al., 2020) is the first who studied wew--ooveenoo--cneeeee
E.2. Comparison Between Decoupled SGDA and Federated Minimax (Local SGDA)
In this section, aim to highlight the key differences between our method and existing distributed decentralized methods in the literature. As mentioned earlier, method can be classified as distributed, though it has major difference from others. In fact, this difference lies in the problem formulation.
Decentralized Distributed minimax formulation. In these settings, we aim to solve the following finite-sum optimiza- tion problem over M clients:
M Σ fm( v) M
1
v(u.v)
(45)
In the above formulation, it is assumed that each client has a different data distribution D, and tries to solve the game based on this data. It means that each client keeps updating both u and v at the same time for several steps. Then the server aggregates the parameters and sends them back to clients. The ultimate goal is to find the saddle point x = (u", v*) of the global function f, as if the entire dataset setting, each client is allowed update both players meaning that it has access to the gradient of fm with respect to u and v. However in our approach, instead of splitting the data over clients, is responsible for only updating u and another for v. Our method also allows to have several machines for u and several machines for v. An important point to consider is that the notions of client and player should not be intermixed. When the number of players is fixed, the distributed minimax approach essentially runs several instances (fm) of the main game (f) in parallel to ultimately find the saddle point of f. In contrast, our method directly finds the saddle point of f by splitting the parameter space across different machines. Figure illustrates the difference between these two methods.
D, u... U DM were on a single machine running GDA on it. this
split the parameter space. It means one machine
Decoupled GDA
u = uf - 7 V V.f(uff vo) v v = v 7 V fuj vf)
GDA
Federated Minimax
U
Us- 7 V.. Va)
k+1
r.m
uk
pim
Wuffm ( (u nim V vim)
V = V4 V.. V&.)
rim
m.
+ +VV. m mm)
R+1
Figure 6. Comparison of different gradient descent ascent (GDA) approaches: Decoupled GDA, standard GDA, and Federated Minimax. The top box represents Decoupled GDA, where u and v gradients are separated, while the bottom left and right boxes represent the standard GDA and Federated Minimax approaches, respectively.
32

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Decoupled SGD
Distributed Decentralized Minimax
Processor 1
Processor 1
Processor 2
Processor 2
Processor
Plyer Punanii
Figure 7. Comparison our method with federated minimax formulation: Our method splits the parameter space, while the federated formulation splits the data. Moreover, method only allows each player access the gradient with respect their own parameters, whereas in federated minimax, each player can compute the gradient with respect to both their own parameters and the other player's parameters.
F. Federated Decoupled SGDA
F.1. Comparing Decoupled SGDA with Federated Learning for Minimax Optimization
Federated learning (FL) builds on the foundational work in distributed minimization, exploring various settings, In the context of minimax optimization, methods like Local SGD have been extended to achieve convergence rates for different classes of functions in both heterogeneous and homogeneous regimes. FL methods for games differ from the setting considered in this work. In FI., multiple copies of all strategies (parameters) are trained locally different machines and datasets and periodically aggregated. FL is suited for scenarios where a single local machine runs a multi-player algorithm and has access to all players' loss functions, with "collaboration" built into the design. In contrast, our method suits competitive distributed players (local machines) where each player has noisy or outdated strategies of the remaining players. For further discussion, see Appendix E. Additionally, federated learning assumes balanced noise across players, which required in our setting; revisited faster convergence, even if fully centralized training possible, which class similarly arises in non-convex settings-$ 5.In the rest of this section, study Federated Decoupled SGDA, which is combination of Federated Minimax and Decoupled SGDA algorithms, and can benefit from the advantages of both approaches. In the next section we propose this method with details.
3 and $ 5. Finally, in $ identify class of games where our approach leads
F.2 Federated Decoupled SGDA method
In this section, we study an extension of our method in the context of federated minimax optimization aligned with the works (Deng & Mahdavi, 2021; Sharma et al., 2022). This line work is closely related to finite-sum minimization, well-studied topic. Local SGD (Stich, 2019a) is the most popular method used to solve finite-sum minimization problems in distributed fashion. an extension of this method to finite-sum minimax problems, researchers have studied Local SGDA, which is
33

---

Decoupled SGDA for Games with Intermittent Strategy Communication
straightforward extension of Local SGD, incorporating gradient ascent steps in addition gradient descent. We extend method to this setting for the sake of completeness and provide convergence rate that matches the state-of-the-an results for Local SGD while also improving the conditioning of the existing rates for Local SGDA.
Notation. We consider unconstrained two-player games denoted by and v in the spaces A. = Ed and X Rd respectively. The corresponding product space X' = X₂ x X, = _ (with d = du + d,) consists of vectors x = (u, v) IR4 where u E X. and v Xg. For this section, we consider the common le norm | = (x.x).
Problem formulation In distributed minimax optimization, we aim to solve the following problem:
M Σ m=1
M Σ
[(u,v) - M
min max uaA, VEA.
(u
Be Jm (u, v, Em)
(46)
M
m==
In this setting, we assume that each player's data is distributed across M clients / processors. So each processor has access to function fm X - R on which it can perform stochastic gradient steps. We denote ug nh." and V& mh. as the parameters of players and client m in some round r after local steps. We also use the notation u M - u = and v% M Em= th to denote the average of parameters over clients at some round r after k local steps. Data distribution across processors can be either homogeneous or heterogeneous. the heterogeneous regime, which is the case of study in this paper, each processor holds a different payoff function. To measure the heterogeneity of the problem, it's common to use the following assumption:
1 MM
Assumption F.1. There exists constant Ç. 0 satisfying the following inequality in distributed minimax games:
max
sup /Vaam(x'') (x")] sup "v.mm((''''' C
(47)
Assumption F.1 very common in federated learning and has been used in many works (Koloskova et al., 2020; Deng Mahdavi, 2021; Khaled et al., 2020). Another common assumption in the literature (Woodworth et al., 2020b; Patel et al., 2024; Zindari al., 2023) is gradient similarity Ç for every point X' which is a stronger assumption and cannot be satisfied for quadratic functions. In this work, use Assumption F.1 to provide convergence guarantee for our method. Assumption F22. We assume that each local function fm is L-smooth meaning that for all u, u' Xx and v E X, it holds that:
V v) Vu v & T. u
(48)
(u, V.fm(u', v'Il < L [[[ ullu-ut u'] --v-v]]]
Assumption F.3. We assume that the global function f is μ strongly convex u and μ strongly concave if for all u, u' E Xr and v, v' X, it holds that:
(u- u', V.f(u, V.f(u', v)) P u' (v- v' v.f(u, v') V.f(u, > / | v
(49)
Assumption F.4. The variance of the noise of stochastic gradients on each client is uniformly upper bounded by d²
Eg pm
Vufm u, v: - V Vafm(u, v) 2
(50)
Ee... V (u, vm) (u, 2
Method Note that in this section drop the superscript for convenience. It's expected first define operators F(x), Fm as follows:
V Vufmlu v:
ΣM (u.
Gm (x:
G(x;
(51)
- -Vammu viEm)
1 EM Vulm(u,
17
Where we assume Re.., (x; {mm] Fon (x) and Eg,,, (m)) F(x).
34

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Algorithm 3 Decoupled SGDA for two-player federated minimax games
1: Input: step size y, initialization ug.
Vo Uo. Yo
2: Initialize: Vm [M]] Ug
7.0
r.
3: for r {1...., ....,R) R] do
4: Vm E [M] 40 m..
Vo 6: for m E (I...., M) in parallel do
- 0g.
Yo
m.r
5: for E {O....,
1 do
Update local model gg+1
Un ? V Vufm(ut (u -o {m)) VE
8:
Update local model *++
V.Vmm vV 5m)
9: end for
10: end for
MM 12. 11: Uh+ M m== K
_., M mm=1 K
M
12: Communicate ig to all processors with v player and Vi to all processors with u player
13:
end for
Output: u K
Remark F.5. Note that (x*) * and F(x*) 0.
The conventional method for solving (46) is Local SGDA which performs K gradient descent and ascent local steps on each client followed by an averaging on parameters u and v over all clients which is done by a central server.
K-1
K
Vulm(u v Em),
VK
Volm(u vi Em)
(52)
Then the server computes the average of parameters üg M Em=1 u and VK all clients to start from these points. On the other hand, method different operator which contains the outdated gradients.
M Em=1 Vi and sends them back
V Vufm(u, Em)
1
ΣM Vo.
Go (x) ==
(x: :=
M
(53)
Vufm(us vi Em)
M ΣM Vufm(uo, v; Em)
Where assume E... [G (x: Em)l = F (x) and E.,. Em)l = (x). The update rule of our in some round be written as:
u up
W. vk = v
Vefm(u"" Em)
(54)
Assuming that all clients started with the parameters un u and Vo v at the beginning of the round.
In Algorithm 3, we discuss our method, where two players u and v have their data distributed across M processors each. At every round, each set of processors update their local models while having access to an outdated version of the other opponent parameters which was received at the beginning of round. By the end the round, both set u and processors send the their parameters to central server which will compute the average of the parameters and send them back all processors.
F33. Convergence Guarantees
Theorem F.6. For any K, R, 0.p after running Decoupled SGDA for a total of K iterations on the problems in the form of (46) in a distributed setting with 2M clients using a slepsize of 7 प. assuming that
Ixxo x" & D2, we have the the following convergence rate:
x
x*111
D2exp
D2 exp
YHKR
+
2 6KL
270²
(55)
2
112
422
M
35

---

Decoupled SGDA for Games with Intermittent Strategy Communication
In(max (2, (R/R211)))
Corollary F.7. After choosing stepsize of y = min
P L2
{: we get a rate of:
HKH
(-
112 12
C +
1²002
d²
| - x x11
= =
D2
cxp exp
R
+
+
(56)
μet R² R
HAKR
Method
Heterogeneous
Homogeneous
Local SGDA
O
6 R
HAMKR
12 DOKR
+
L2 MAMKR
Ô K-R μMNK H +
o²
L'O²
MAMKAR
L²O²
(Deng Mahdavi, 2021)
Local SGD
O LD' exp
o²
u.
La² p²k
O OLD'
cLD exp (-#KR)
da
Q'o' H
(Koloskowa al., 2020)
uMKR
pana
uRMR
(Yuan & Ma, 2020)
Ours
δ Ö(D2xx exp (- +
o² HeMKR R
L. +
L²o0² K
Fod. Decoupled SGDA
Table 4. Comparison of Methods in Heterogeneous and Homogeneous Settings
Table 4 compares state-of-the-arr rates for Local SGD, Local SGDA with Federated Decoupled SGDA. The first term in our rate enjoys an exponential decrease which matches the rate of Local SGD. However, the rate for Local SGDA has rate of O 1.6
which is worse. In addition, in this term we have better conditioning of x² compared to α² in Local R
SGDA. Note that the condition number x² in the first term of our rate matches the baseline SGDA which considering the fact that SGD has conditioning of и which also appears in Local SGD due to the fact that the problem is minimization (not minimax). Our method also matches the rate of Local SGD for the noise terms and the term with heterogeneity. However, it seems that for this term the rate in (Deng & Mahdavi, 2021) contracts the existing lower bound proposed for Local SGD in (Patel et al., 2024) which is:
- LD²
(1 K1/3R2/3
oD
(LC2D4)
(57)
R
VMKR
R2/3
As it's clear from the lower bound, the term with heterogeneity cannot improved using local steps (there no K in the denominator) while in the rate of (Deng & Mahdavi, 2021) this term can be decreased if K - Øc, which contracts the lower bound.
E.4. Missing Proofs for Section F
Lemma F.8. For set of M vectors a1, a2, a.
Rdd have:
M
M amml
Σ
am
(58)
Lemma F99. For set of M vectors ai, ......, aM
Rd
have:
M
M
Σ
am
M
am
(59)
Lemma F.10. For two arbitrary vectors b e IRd and Vy > O we have:
||a b112 < (1 + 7) ||a]| (1+x-1)|bb]] 1b12
(60)
Lemma F.11. Let Assumption 2.4 holds. Then have:
M Vafm(u,
12 o2
E.g..
Σ
Σ Vulm(u, M m=
1
(61)
M m=1
M
The same argument holds for gradient with respect to v.
36

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Lemma F.12 (Consensus Error). After running Decoupled Local SGDA for & local steps at some round with step-size of Y 32 the error V (xx+ (xx) ((%) can be upper bounded follows:
K
1i² 8KL2
2Kg002
B[V(x**)) + (xxx)]
Σ
|
M 2K
(62)
:=1
In this setting, have two different errors related the use of outdated gradients and deviation from the average iterates. Total error is the sum of both errors. We define the consensus error in this setting follows:
M
(u m.r = 1
Σ
uu
mar - u
w(v == M
Σ
ma
v
M
m
m-1
(()))) = | uill
((v)) 1 - 2
((xx")) = v( + V(v ((x)) = ((u)) + +(v))
The total consensus error can computed by summing both errors with respect to u and
(uu) + V (v+)
p + + (vv)
Consensus error
caused deviation from average
eπror caused outdated gradients
In the following, the upper bound for consensus error different settings will be discussed. Note that in the case multi client, we get different upper bounds based on the assumption on data heterogeneity.
37

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Proof.
E (1
+ (1++1)
Σ
E
uk
V fuffmuu (ul"", No0 (m) oj
Y
Σ
V Vufm(u) (u
"o0 : :mm)
+
M m=1
M
E
u1
u +
V JuJm(ul (ux th No ;o=";Em Em)
M m=1
M
M
1
E
Ux
? V n. famfmmm
(uk m,r vo (. uj
M Σ
7
Vafm
(ug m.r v0 (1
+
M
720²
E
unj u +
V Vufm( (u un vo )))
M + 7000
M m=1
1+ 1
+ 2K 2
M
M
K
B8 ( + (
M
Σ EE
V Vufm (uk mir viD
(ux
M m=1
V
fm uu m.r
vo
+
2 M
0²02
M Σ
E Vo m. 012
+
+ 220
M
4K 2
M
(u m.r _v )1 + 2²0²
1+ K
E BL +0,00
E
V
M + 7202
M
+
EE E[V(Lu mi + (+
K
4K7² M
V fmmmmm (ug m.r v - (uk. v/) + (uf, v2 2202
Σ
+ +2202
M m=1
M
8K2² M
++ K
E ([V( [ū]]]+
M Σ
ElVuuf (u m.r vor Vafm v0)12
8K9 M
0202 M
M Σ
E
| V (u. v0)
+ 22
1+ K
E[ (U ( + (ux) + 8 (
m. + SKL22 E
M 8K22 2
2²02
M Σ V (6% 2
(1]121) +
M + 202
= -(1+ K
B (LV m.r) + +( + + + +(vD)}
8K2 2
M
2²0²
Σ
vi) Vafm v²) + Vufm(u' v=)]2 E
M + 222
M
1 1+ K
E ( " + +(+ + SKL ELV ++V+))+
16K 2
M
2222
M Σ
EIV..L vD) Vnfm +
M + 720
38

---

Decoupled SGDA for Games with Intermittent Strategy Communication
continue:
B[V(DD + ((1 & (1 F[V(ug")) +(()) + 8KT, " + +(v[)+ K
1
7²0²
16KI3
-
16 +
M + +720²
After doing the same computation with respect to get:
B v (v m.r k+1 + ((v++t))
1 + K
7-02
16K -
12 16K
+ 7200 M
Now we sum up both inequalities and we get:
V (xx+1) + [[{++1]]
1 + K
+ (()]))))))++++++++++) " +xxx))
2720²
- 32K 2 +
+ 27
M
With the choice of 3212R we simplify the above inequality as:
m.r (xx1)) R+1
+
((xx++1) 1)
1 1
112
2-20²
1+ K
E[[(xT")) T. +(8+) +
E E
x*1| + 32K
+ 27200
128K
32KT2
M
After unrolling the recursion for the last K steps and considering the fact that (1+ k + 128K
< 4 we have:
2K-202
E[ + (x ) <
E - x²11 32K
+ +2K2002
8KL2
M
F.5. Proof of Theorem F.6
For any K, R, > 0, > after running Decoupled SGDA for total of K R iterations on the problems in the form of (46) in a distributed setting with 2M clients using a stepsize of y & अां. assuming that ||xo the following convergence rate:
x=1 < B², we have
E E
x-1
&
B²exx exp
Y0KR
96K2L??2C2
+
6KL2n202
270²
(63)
2
42
122
Mp
39

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Proof. We start by upper bounding the distance between the average iterate - and the saddle point.
E
1 ++ u²ll
M
E
7
Σ
V Vumml
u vVO "00": (00":5mm :m) u
m.r
M m-1
M
X²0²
<
E
U
Σ
V Vufm
m.y .v0 u
M
M
M
M
2
8²0²
E
1 M
Y
Σ
V
Vulm (
Σ
V
VuSm(uu k
vo :
?
Σ
V Vulm (1)) vD) -n"
+
M m=1
M
M
m==
M
&
(1+ +
7p 2
E
1
Σ
V mm 0g. vD)
- u1'
+
M
m=1
1
2
22 M M
Σ
ElIVum (0 v/)
vufm m.r Vo )1 +
(uk
y002
7p
M
m==
For the first term in the above inequality we have:
M Σ
(1 E
7M
Y
Vafm [uk, v/) u²
2
M
m=1
(1 +
7/
E |lu VV.ffuuf vg - u" 121
=
2
= [1 + 7/4
E
||0| - 1'' + | V f v/]1 - (n -u", V.f m
2
<
1 +
7/
E
[1+ 1|ا6 u' 1| - (T - -u', v..((bE. v
2
For the second term we also have:
1 +
2
MM Σ
2 M
E
V
fm (u,, vD) - Vufm(u, m.r vv. )²
7/
1 +
2
2 M
Σ KE
u 1 + 1 7p/
2
L222 M
Σ m=1
E V - vo
M
M
1
2
L277 E
[M
+ (1+
2
L2n? [[((vV)
7/11
7/1
40

---

Decoupled SGDA for Games with Intermittent Strategy Communication
Where in the last line, we used the fact that Vo virr Vo- We then repeat the same computation with respect v.
E 1+1 v-1l²=
=
M
E
1/ M
7
Σ
V. Fofm(ul R.r .Vk :Em) v²
M
E
1/
2 M
Σ
, .K ("0
myr
v²
+
M
m=1
M
M
+ 7 M
12
702
E
1/ M
7
Σ
VoSm(ug myr vvk
Y
Σ
Vesm
Σ
Volm (1 v/) - v.
+
M
M
M
m=
m=
m=1
M
1+
7H
E
V + 7
Σ
vufm 0% v%) v*
M
2
72
M
Vefm(uj .va') vefm(u""".v""") 70²2
1+
Σ
V
E
vi-
7p
M
M
For the first term in the above inequality we have:
M
1+ +
7p
E
V/
+
7
V. V/)
M
11 + 7/
V1 + 7 v. (ig v/) - v=1
2
1 + 7/
E
1 v11
V V. vi]l - -2 - -vi Ve v()
2
< [ +
7H4
E
(1+
18 - -- 2x -v6 v.f(ūj. mi)>
2
For the second term we also have:
2
2
M Σ
1
+
E of EV
(ū6, vp) - V Vefm (u, m.r vxx )1
7/
M
m-1
2
L2n²
M
B|a - ub1l + (1+ 2 L2 M
1
+
Σ
Σ m=1
E 10 - vx v
7/11
M
M
m=1
2
2
1 +
[( + I+
12n² ([
7Hpl
7p
Summing up the results from the inequalities with respect to u and v gives us:
E x k+1 -
1²
+ 7/11
E
(1 + (2) 118 - x11 2x - -x", x", F(XE)) +7 (222+ +
21.
E [[ + v(xT
+ 2002
2
11
M
1 + 7/4)
E
(1+ + 22,) 1|8 -x112= 20/4 1| x" x1]] +7 71.2 2L²
E (x( V(
7202
2
/
M
=
(1+ 7/1)
E
(1 27/4 + (3) | x1| + (2L3+ +
21,2
EE [x(()) + M((XX"))
+ 7002
2
4
M
41

---

Decoupled SGDA for Games with Intermittent Strategy Communication
With the choice of y
16r
We have:
E x x+1
x²1
23
33
320²
I8 || x+112=
[
(X
)]+
16p
M
23
y3
96K2
6KL
720²
1
I ||
x+1
128K
1
μM
M
We change the current notation for simplicity proof by substituting r and k with t. varies from 0 to KR, iterating over all rounds and local steps:
E
X
x"1
&
1
237yu
E ||x
x²11
337
Σ
| -
xx11
16
128K
maxx(0,f K+1]
96
7KI2
0²
6K +
7202
1
PM
M
Here use the Lemma B.10 with the following parameters,
23p
33μ
96
7KI2
6KL2g02
70²
X
x11
c=
16
128
J.M
M
The final inequality is:
237
32
96K L
TKLin02
6KL2n02 700
B E| - x-11²
E E|xxo x²11
7
32
23μz
P.
M
9,
7KI2
6KT2-002
702
7/1
E [X0 1
122
p2M
12
MH
Recall that we assumed
so we have:
32K
- x212 (1- 7/4
KR
E
||x0 - x²1 +
96K2
6KL2220"
+
2700²
2
12
112
M
By setting t = T = -RK, we get:
E - < (1- 7/ KR
6KL29002
27002
2
1|xxo - x11
422
122
Mμ
7/ $ exp (-24
R
E
Xn
11
96K
22
6KL222002 2
112
112
Mp
We can see that with this inequality we can only guarantee convergence to neighborhood x*. To obtain a convergence the In(max(2,,u xxo || (p??"//?))
final, as discussed in (Stich, 2019b), we need choose the step size carefully. If 32K
then
we choose In(max(22,4' No fo-x*11"r" (e²"))) otherwise if 32KL In(max
(2 xo 1| (02))
then we choose
pf
32 L
we can see that with these choices, we would have:
E XT = (exp/
" |x0
122
x11
K3L2C2 1472
KL202
202
1A72
M
42

---

Decoupled SGDA for Games with Intermittent Strategy Communication
G. Decoupled SGDA with Ghost Sequence
In this section, we introduce a new extension to the Decoupled SGDA algorithm called Ghost Sequence. The base Decoupled SGDA algorithm, explained earlier, is designed take advantage problems with a dominant separable component. minimizes communication complexity by reusing outdated strategies, which has already been analyzed theoretically in the prevous sections.
However, we can push this idea further by not just reusing old strategies but also predicting the opponent's ss next move. This smarter approach opens up new line of research, where more advanced methods can be explored for estimating the opponent's 's strategy, offering directions for future work.
To demonstrate the potential of this approach, we propose Decoupled SGDA with Ghost Sequence. The main idea is for each player to predict (or approximate) the next move of the opponent based on their previous actions and behaviour. This is achieved by computing the difference between successive strategies during synchronization. Using this information, each player update both their own and their opponent's parameters, leading to improved performance. As shown in Figure 8, Decoupled SGDA with Ghost Sequence can greatly improve the algorithm's 's performance. It also achieves faster communication, even in highly interactive games, and does not require the problem to be weakly coupled.
For more details, refer to Algorithm
Algorithm 4 Decoupled SGDA with Ghost Sequence
1: Input: Step size y, initial strategies xo (uo, vo), total rounds R, local updates K
2: for E {1...., R} do
3: Calculate guess A < (1n 11-1)
4: Calculate guess A K (vū 1
5: fo (O...., K 1) do
6:
Update ghost sequence 1/4 < Vi41 + A
7:
Update local strategy u - u, 7 V..(( V))
8:
Update ghost sequence i/41 - 0/411 + A
9: Update local strategy v[+1 vf V
10: end for
11: Communicate (u'x. vix) to other players
12: end for
13: Output: Final strategies x = (u v
H. Additional Experiments
H.1. Finding the stationary point Decoupled SGDA for non-convex functions
Here, we add one more figure for the toy GAN problem to provide further insight into the behavior of Decoupled SGDA.
43

---

Decoupled SGDA for Games with Intermittent Strategy Communication
for
Trlectories
Trajettores
Talectories
Shost Doc susted SODA Decoupted
Decsusted S0. Dacoupted SCAA
Syechonaaion Reunes
Sprchronzatinn Pourdds
Syschesoos Rouni3
Sydditetee Rounes
Figure 8. Trajectories and convergence comparison of GDA,Decoupled SGDA and Decoupled SGDA with Ghost Sequence with different values of C C1 (intcraction strength). The top row shows the trajectories of the different algorithms for K = {1, values of C {25, 13, 5, 0.13. As C' decreases, trajectories become more stable, with the Decoupled SGDA with Ghost Sequence (blue) showing more efficient convergence compared to GDA (black) and Decoupled SGDA (red). The bottom row presents the synchronization rounds versus distance equilibrium for each configuration, highlighting faster convergence of Decoupled SGDA with Ghost Sequence under larger C values, while Decoupled SGDA with Ghost Sequence and Decoupled SGDA converge similarly for small C.
over varying
Trgecooniorteea 1
Thaldenn for A 0S
Thgedbetts bea 24
K-1 (GDA)
K=2
Conndasn
Coanddrade
RCcortlaae
Spechmsstrtin Roands
Syccrenbatiee Aoands
Systhrelat kound
Synthookraton
Figure 9. Trajectories (top row) and distance to equilibrium over synchronization rounds (bottom row) of GDA (K = 1) and Decoupled SGDA with K (2, 5) the (14) problem (d 2). C in (13) is constant here-thh larger, the stronger the interactive term, Left-to-right: decreasing the constant e (10,3.5, 3, 7,
H.2. More Figures Decoupled SGDA With Gradient Approximation
In this experiment (Figure 10), Decoupled SGDA achieves lower gradient norms in fewer communication rounds compared to Local SGDA, especially as interaction noise increases (larger c). Decoupled SGDA shows much more stability in high-noise environments, highlighting its effectiveness in dealing with noisy gradients when compared to federated minimax settings.
44

---

Decoupled SGDA for Games with Intermittent Strategy Communication
c: 0,000
c:10 De
2:2., du t bp 6x
Lea 505A
Loca 506A
01
20
303
26
06
300
20
66
66
300
c-0.000
c+10. 05
Co2 Su fp
Loca CODA
Loca 220A
25
2.
-15
-0.
393
c: 000033 Byy
c:110
$10
15003
5003
00
-13
06 300 -05
20
30 26 05
20
06
00
300
Figure 10. Comparison of Decoupled SGDA and Local SGDA under different noise settings, Each plot shows the smallest gradient norm achieved by both algorithms over 100 communication rounds, with varying interaction levels and noise variances. Top Row: Different settings of noise variances in off-diagonal entries (interaction noise). Left to Right: Increasing values of the constant controlling the interactive term's strength in the game. Decoupled SGDA consistently outperforms Local SGDA in scenarios where off-diagonal noise is sigmificant, achieving lower gradient norms with fewer communication rounds.
I. Experimental Setup
L.I. Finding the saddle point of quadratic games
In the first experiment, we conducted tests with a dimensionality of D = 2 over R 31 synchronization rounds. The values of K tested were 2, and 5, alongside parameter combinations (a, b, c) set as (1, 10, 10), (1, 3.5), (1, 10, 2.7), and explored gamma values uniformly spaced in the interval (0.0001,0.1], The algorithm
(1, 0). For each combination, initializes and at 1 and -1 respectively and updates these variables based on the gradients Ja and gy computed using the defined parameters.
For the second experiment, in the left figure, eigenvalues were sampled logarithmically between 10-1.5 and 101.5, with random symmetric positive definite matrices generated for each. We tested agent counts K as [1, 5, 10, 50] and learning rates y from 10-10 to 1. The algorithm ran for 10s rounds, adjusted based on eigenvalue size, to measure the average distance from equilibrium until it fell below e 10-6 Results were plotted illustrate the relationship between Amaz (C)) and the number of rounds required for convergence.
For the left figure, we generated random symmetric positive definite matrices oracles, varying the maximum eigenvalue of the matrix C' using logarithmic spacing between 1.5 and 101.5, The accuracy threshold is set to = 10-4, We evaluated five algorithms: GDA, Decoupled GDA, Optimistic, Alternating Gradient Descent, and Extragradient, with K fixed at 50. Each algorithm was executed for R 10y rounds, determined based on the maximum eigenvalue, and their performance was assessed by the number of rounds required to achieve accuracy.
45

---

Decoupled SGDA for Games with Intermittent Strategy Communication
1.2. Decoupled SGDA with Gradient Approximation
In this experiment, analyze the performance of Decoupled and Local Stochastic Gradient Descent (SGDA) algorithms under varying conditions. We define oracles based random symmetric positive definite matrices, with fixed number of rounds A = 100 and K 40. In the first experiment (left figure) The maximum cigenvalues of matrices C' are sampled _ FFor each maximum eigenvalue, we generate corresponding matrices and evaluate the algorithms across five trials to determine the lowest gradient norm achieved. We reported the mean of these five experiments. In the second experiment (right figure), off-diagonal variances (o and duv) range linearly from to 10. In this experiment they are assumed to be equal. Results are aggregated and visualized in two plots: one depicting the relationship between the maximum eigenvalue of C and the minimum gradient norm, and the other illustrating the effect of varying off-diagonal variance algorithm performance.
logarithmically between 10 10-0.25 0.25 and 10
1.3. Communication Efficiency Decoupled SGDA for Non-Convex Functions
In this experiment, we investigate the performance of Decoupled Single Oracle GDA under various settings of À and K. We evaluate the gradient between 10 -.5 and 103, while K values range from to 5. For each combination of À and K, we compute the lowest gradient norm over 5 independent trials. The gradient norms are averaged and plotted, with vertical lines marking the transition to the weakly coupled regime at À = 50. The final results show the relationship between and the minimum gradient norm for different values of K, highlighting the weakly coupled regime.
achieved over I 100 communication rounds. The values sampled logarithmically
1.4. Communication Efficiency of Decoupled SGDA in GAN Training
In this experiment, Generative Adversarial Network (GAN) was trained using the CIFAR-I0 and SVHN datasets, both resized to 32 x 32 pixels. The GAN was trained with a learning rate x 10 a batch size of 256, and 50,000 rounds of updates. The hidden dimension size for the generator was 128. For evaluation, 256 samples were used to compute the Fréchet Inception Distance (FID) every 200 iterations. Both the generator and discriminator were optimized using the Adam optimizer, with learning rate scheduler that decayed by factor of 0.95 every 1000 steps. Additionally, gradient penalty term was applied to stabilize training. The generator's latent space dimension was set to 100, and its Exponential Moving Average (EMA) was maintained with decay factor of 0.999 for evaluation purposes. Training was conducted using CUDA on an NVIDIA L4 GPU.
The Generator uses series of transposed convolutions, starting from a 100-dimensional latent vector, to generate a 32 x 32 x image, with BatchNorm and ReLU, ending with a Tanh activation. The Discriminator applies four convolutional layers to downsample the input, using LeakyReLU and BatchNorm, and outputs a real/fake probability through a Sigmoid activation.
46


Reviews:
[{"review_id": "Pm5q9pKC3q", "reviewer": "Reviewer_HvTn", "summary": "This paper introduces Decoupled SGDA, a novel stochastic gradient-based method designed for multi-player (or two-player) games with intermittent strategy communication. The key idea is that each player updates their parameter (e.g., minimizer or maximizer) locally using potentially outdated (yet periodically synchronized) opponent strategies. The authors analyze the approach under strongly-convex strongly-concave (SCSC) assumptions and show that in a regime they call Weakly Coupled Games, Decoupled SGDA achieves accelerated communication complexity compared to traditional methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s time and effort in reviewing our work.\n\n> It might be interesting to see if adapting the number of local steps $K$ dynamically  can further reduce communication, especially during early or late phases of training.\n\nThis is an interesting idea which can be a new line for future works. Basically, in each round, we can take as many local steps as it gives some improvement , as soon as the improvement (gradient norm) is less than some threshold, we can stop taking local steps and do one communication. This could reduce the overhead of taking so many local steps.\n\n>  If a player partially observes the other’s parameters between rounds, can the approach be adapted to incorporate partial synchronization?\n\nThank you for your suggestion. This idea can be very useful in practice. This situation would be like mixing 'Distributed minimax' with 'coordinate descent' for each player. We could imagine each player periodically gets updates on some parts of their opponent's parameters, maybe based on a certain probability $D$. So, instead of assuming the opponent's parameters stay completely fixed between rounds, it could be seen as we are performing coordinate descent steps on specific coordinates (parameter parts) sampled from a distribution $D$, using the partial information received.\n\n>How sensitive is performance to the choice of $K$ in real applications? For instance, in the experiments, do you see a clear sweet spot for $K$ depending on $\\kappa_c$?\n\nThe sensitivity of performance to the choice of $K$ depends on $\\kappa_c$. As seen in Figure 2 of the paper, for smaller values of $\\kappa_c$, the algorithm quickly saturates as $K$ increases. In other words, there isn’t a significant difference in performance between larger and smaller $K$ values. However, as $\\kappa_c$ increases, using larger $K$ values actually improves performance significantly. So, for larger $\\kappa_c$, different choices of $K$ can lead to more noticeable differences in performance. \nIf we ignore local computation costs (i.e., the local steps performed by the players), there is no theoretical sweet spot for our algorithm (increasing $K$ never leads to worse performance compared to smaller $K$ values). However, when considering local step costs, the optimal $K$ depends on the relative cost of computation versus communication. Roughly speaking, The best K is usually where performance plateaus; increasing it further offers little gain.\n\n>Have you considered weaker assumptions like Minty variational inequalities or quasi-strong convexity? If not, do you anticipate major challenges?\n\nYes, it is possible to relax the strong convexity assumption. Specifically, we can derive Lemma B.4 and Lemma B.8 under a weaker assumption instead of strong convexity:\n\n**Assumption**: For operators $ F_{\\bar{\\mathbf{x}}} $, we assume that for all $ \\mathbf{x}, \\mathbf{x}' \\in \\mathcal{X} $ and $ \\bar{\\mathbf{x}} \\in \\mathcal{X} $ such that  $ F_{\\bar{\\mathbf{x}}} (\\mathbf{x}) = \\mathbf{0} $, the following inequality holds:\n\n$\\langle F_{\\bar{\\mathbf{x}}}(\\mathbf{x}) - F_{\\bar{\\mathbf{x}}}(\\mathbf{x}'), \\mathbf{x} - \\mathbf{x}' \\rangle \\geq \\mu'  ||\\mathbf{x} - \\mathbf{x}'||^2$\n\nThis assumption implies that functions $ f(\\cdot,\\mathbf{v}) and f(\\mathbf{u},\\cdot)$ are strong-quasi-convex and strong-quasi-concave, respectively, in the case of two-player games.\n\nWe can relax the strong monotonicity assumption of the operator $ F $ and we still can drive the results in Theorem B.12 as follows:\n\n**Assumption:** For operators $F$, we assume that for all $ \\mathbf{x} \\in \\mathcal{X} $ and $ \\mathbf{x}^{\\star} \\in \\mathcal{X} $ such that $ F(\\mathbf{x}^{\\star}) = \\mathbf{0} $, the following inequality holds:\n\n$\\langle F(\\mathbf{x}) - F(\\mathbf{x}^{\\star}), \\mathbf{x} - \\mathbf{x}^{\\star} \\rangle \\geq \\mu''||\\mathbf{x} - \\mathbf{x}^{\\star}||^2$\n\n\nTherefore, Assumption 2.2 can be replaced with these two new assumption.\n\n>Could you comment more on the empirical overhead or potential instability of “ghost updates”?\n\nDecoupled SGDA with Ghost Sequence has minor overhead (vector ops) vs. standard SGDA, insignificant for simple games (bilinear, quadratic), negligible for complex tasks like GAN training (vs. gradient costs).\nGhost Sequence is stable and improves performance in simple (quadratic) games. Its effectiveness in complex scenarios (e.g., GAN training) needs more study.\n\n>Are there conditions under which Ghost-SGDA might fail to converge or require additional assumptions?\n\nFor payoff functions that have Hessians with large norms, Ghost-SGDA may encounter difficulties. This is because the underlying assumption for the approximation strategy in the Ghost sequences is that the gradient of the other player remains relatively constant between communication rounds. \nWe want to thank the reviewer again for their constructive feedback. If we managed to address your concerns, we appreciate if you consider increasing your score.", "claims_and_evidence": "**Reduced communication in weakly coupled games**  \n   - *Claim*: Decoupled SGDA requires fewer communication rounds than standard GDA/SGDA, especially when the interaction between players is weak.  \n   - *Evidence*: The authors introduce a coupling parameter $\\kappa_c$ and prove that if $\\kappa_c \\le 1/4$, the method’s communication complexity *no longer depends* on the potentially large condition numbers $\\kappa_u, \\kappa_v$. Experimental plots on quadratic games confirm substantially fewer communication rounds for small $\\kappa_c$.\n\n**Near-optimal communication complexity**  \n   - *Claim*: Decoupled SGDA can match or even outperform, in terms of *communication rounds*, the best-known first-order methods (like FOAM) under certain stronger assumptions on the coupling.  \n   - *Evidence*: Corollary 4.5 states that if $\\kappa_c \\le \\tfrac{1}{2}\\sqrt{1 - \\frac{1}{\\sqrt{\\kappa_u \\kappa_v}}}$, Decoupled SGDA beats FOAM (which has optimal iteration complexity for classical SCSC). The proofs (in the main text and appendices) and carefully derived bounds support this.", "methods_and_evaluation_criteria": "- Decoupled SGDA performs local gradient updates with respect to *one’s own parameter* only, using *outdated* opponent strategies that are synchronized less frequently. In practice:\n  1. Each round begins with a synchronization step where $(\\mathbf{u}, \\mathbf{v})$ are exchanged among players.\n  2. Each player runs $K$ local steps using only the gradient w.r.t. their own variable and a *fixed* (outdated) opponent parameter from the start of the round.\n  3. After $K$ local steps, parameters are synchronized again.\n\n\n- *Theoretical metrics*: The standard measure is the *distance to the equilibrium* $\\|\\mathbf{x}_t - \\mathbf{x}^\\star\\|$ for strongly-convex strongly-concave games, and *gradient norm* for more general (non-convex) settings.  \n\n- *Empirical metrics*:  \n    - Quadratic toy games: distance to equilibrium or gradient norm.  \n    - Non-convex toy game (GAN-like): smallest gradient norm vs. number of communication rounds.", "theoretical_claims": "Under strong monotonicity, if $\\kappa_c \\le 1/4$, Decoupled SGDA achieves a *linear rate* $\\exp(- (1-4 \\kappa_c) R)$ in terms of *rounds* $R$.", "experimental_designs_or_analyses": "Overall, the experimental methodology is sound: they fix the total number of communication rounds and observe the final performance. This directly speaks to the main claim of *communication efficiency*.", "relation_to_broader_scientific_literature": "The work builds on foundational methods (GDA, EG, OGDA) and references advanced algorithms such as FOAM, APPA, etc. The authors also connect to known lower bounds in strongly-convex strongly-concave optimization, ensuring theoretical completeness.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The requirement of unbiased gradient oracles *for each player’s own parameters* might be challenging in certain practical contexts (though standard in many theoretical studies).", "other_comments_or_suggestions": "1. It might be interesting to see if adapting the number of local steps $K$ dynamically (e.g., using line search or variance monitoring) can further reduce communication, especially during early or late phases of training.  \n\n2. If a player partially observes the other’s parameters between rounds, can the approach be adapted to incorporate partial synchronization?", "questions_for_authors": "1. **Choice of Local Steps $K$ in Practice**  \n   - *How sensitive is performance to the choice of $K$ in real applications?* For instance, in the experiments, do you see a clear sweet spot for $K$ depending on $\\kappa_c$?  \n   - *Would an adaptive schedule for $K$ be simpler or more robust?*\n\n2. **Beyond Strong Monotonicity**  \n   - Have you considered *weaker* assumptions like *Minty* variational inequalities or *quasi-strong convexity*? If not, do you anticipate major challenges?\n\n3. **Ghost-SGDA**  \n   - Could you comment more on the empirical overhead or potential instability of “ghost updates”? \n   - Are there conditions under which Ghost-SGDA might fail to converge or require additional assumptions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "o79EmuCfhw", "reviewer": "Reviewer_fzab", "summary": "This paper studies the communication complexity of first-order methods for solving strongly convex games (two-player games in the main body and an extension to $n$-player games in the appendix). Motivated by the fact that the communication complexity of recent (near-)optimal methods (Lin et al., 2020; Kovalev & Gasnikov, 2022) is independent of the coupling in the minimax objective—resulting in no speed-up even in fully decoupled objectives—the authors introduce a measure of coupling, $\\kappa$. This measure is defined as the ratio between the Lipschitz continuity of the lagged operators of the corresponding VI and its monotonicity.  \n\nThe authors propose a new algorithm, a direct extension of first-order methods for minimax optimization, which updates locally using outdated information from other players and only communicates periodically. They analyze the algorithm in a noisy lagged setting. The new algorithm, termed **Decoupled SGDA**, demonstrates some relative speed-up compared to existing methods in weakly coupled settings, in terms of the condition numbers of the players, $\\kappa_u$, $\\kappa_v$, and the coupling degree $\\kappa$. In general settings, the communication complexity of the algorithm is comparable to optimal methods (Zhang et al., 2022; Kovalev & Gasnikov, 2022), though it may be off by a factor that depends on $\\kappa_u$, $\\kappa_v$, and $\\kappa$.  \n\nThe authors conduct experiments to demonstrate the effectiveness of their algorithm in weakly coupled settings on classical quadratic convex games. Additionally, they illustrate that similar ideas as Decoupled SGDA can be applied to nonconvex optimization problems by showing practical results in a toy GAN setting.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's time and effort in reviewing our work. Although some parts of the analysis follow the previous works, we have novelties in our proof, especially in the weakly coupled regime. Firstly, one novelty of our work is identifying the regime in which we can achieve communication acceleration. We mathematically identified under which condition the coupling between players is low, and it can give us communication acceleration. To the best of our knowledge, previously, there was no proof in the literature in which the low interaction of players has been identified based on players' related parameters. Secondly, in section B.1 in the Appendix, we provide a novel proof for the convergence of our method in the weakly coupled regime in which we remove the dependency on the players' conditioning and our rate depends only on the coupling parameters of the players ($L_c$), which can be very small and even zero. So far, this type of proof has not existed in the literature, and previous works always use some pessimistic assumption for all regimes (even when there is no interaction between players). As an example, the very recent work [1], which considers the same setting as our work in which $N$ players (we discuss the extension to $N$ players in Section C) collaboratively find the equilibrium while taking local steps and synchronize periodically, gives a rate that always depends on the quantity $L_{\\max} = \\max ( L_1, \\dots, L_N )$, where $L_i$ is the smoothness parameter of the $i$th player (Theorem 3.3). This rate is pessimistic in low interaction games. One can verify that when there is no interaction, players can independently optimize their own objective without the need for communication. While this work cannot recover this scenario, our rate does because of introducing the parameters $L_c$ and our novel proof. We also cover the case that the interaction exists but is somewhat small, and we still can get communication acceleration.\n\n>How are $\\kappa_u$ and $\\kappa_v$ related to $\\kappa$? Is it possible to provide crude upper and lower bounds on the relationship between these parameters to make the speed-up of Decoupled SGDA in Table 1 more meaningful compared to other algorithms? \n\nIt always holds that $\\kappa \\ge \\max(\\kappa_u, \\kappa_v,\\kappa_c)$ (note that without the loss of generality, $\\kappa_c = \\kappa_{uv} = \\kappa_{vu}$ if we use regular $l_2$ norm or equally if the parameters $\\alpha_u = \\alpha_v = 1$. See Section \"Notation\" from the paper for the definition of $\\alpha_u, \\alpha_v$). If $\\kappa_{c}$ is large compared to $\\kappa_u,\\kappa_v$, meaning that we have a strong interaction between players, our method achieves nearly GDA complexity as $\\kappa_c$ dominates the condition numbers of players (worst-case analysis of our method). However, when $\\kappa_{c}$ is small, which we refer to as the weakly coupled regime, our method achieves significant acceleration as there is no dependency on the players' conditioning or $\\kappa$ and only $\\kappa_c$ appears as opposed to all other methods which are still affected by $\\kappa_u,\\kappa_v$, even if there is no interaction (meaning that $\\kappa_{uv} = \\kappa_{vu} = \\kappa_c = 0$). So, our method performs very well when the interaction is low and players suffer from poor conditioning, but also it does not get much worse than baseline GDA in the case of high interaction between players.\n\n> Can you design concrete examples where the speed-up criteria are satisfied for illustration purposes?\n\nTo show this speedup on some examples, one can consider quadratic games with linear coupling in the form of $f(u, v) = \\frac{1}{2} u^\\top A u - \\frac{1}{2} v^\\top B v + u^\\top C v$ where $A, B$ are positive definite matrices and $C$ is a general possibly rectangular matrix. Let $\\mu_u, \\mu_v$ be the minimum eigenvalues of $A, B$. The condition for which we get communication acceleration on this class of functions is $\\frac{\\|\\|C\\|\\|}{\\min(\\mu_u, \\mu_v)} \\leq \\frac{1}{2}$, where $\\|\\|. \\|\\|$ is the $l_2$ norm of the matrix $C$. The norm of matrix $C$ defines the level of interaction, and the larger it is, the more interactive the game is. So, it is expected to get more acceleration as this norm gets smaller, and in the extreme case, when $C = 0$, there is no interaction, and players can independently optimize and find the equilibrium without any communication.\n\nWe want to thank the reviewer again for their constructive feedback and we will consider adding some details about the novelty of proof in the main body of the revision. If we managed to address your concerns, we appreciate if you consider increasing your score. \n\nreferences:\n[1] Yoon, T., Choudhury, S. and Loizou, N., 2025. Multiplayer federated learning: Reaching equilibrium with less communication. arXiv preprint arXiv:2501.08263.", "claims_and_evidence": "Yes, the theoretical claims and experiments are well supported. Additionally, it is important to note that there is no magic in the theory, and claims such as speed-ups in weakly coupled settings, given the design of the new algorithm, are expected.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No, I have not checked the proof in the appendix.", "experimental_designs_or_analyses": "Yes, I checked the ones in the main body.", "relation_to_broader_scientific_literature": "This research focuses on the communication complexity of minimax optimization, which may have some impact on training GANs and adversarial machine learning, particularly in scenarios where some form of limitations on synchronization exist.", "essential_references_not_discussed": "Not that I know of. However, I would like to note that I am not an expert in this line of work.", "other_strengths_and_weaknesses": "Strengths:\n- The observation and formalism on the effect of the coupling level of the objective function on communication complexity are interesting, e.g., the definition of $\\kappa$, weakly coupled settings, etc.\n- While the proposed algorithm is quite natural (which I do not consider a drawback), the paper theoretically demonstrates considerable speed-ups in certain regimes depending on the condition numbers of the players' objectives.\n- Well-designed experiments support the main claims of the paper.\n- The paper is well-written and easy to follow.\n\nWeaknesses:\n- I highly doubt that the theoretical novelties in this work provide sufficient merit for a top-tier publication, as the analysis appears to be relatively straightforward and closely follows previous work. Additional discussion on these aspects, especially on how the analysis differs from prior works, seems necessary.\n\nGiven these points, I am leaning toward rejection, but I am open to reconsideration based on the opinions of the other reviewers and the forthcoming discussion.", "other_comments_or_suggestions": "I suggest that the authors discuss the mathematical novelties of their proofs in the main body, as this will significantly strengthen the paper.\n\nIn Algorithm 1, it appears that two lines are missing, which update the initial belief of the other player at the start of each round based on the previous completed round. Specifically, after Line 2, the following should be added:\nset $v_0^{r} = v_K^{r - 1}$ and $u_0^{r} = u_K^{r - 1}$.", "questions_for_authors": "How are $\\kappa_u$ and $\\kappa_v$ related to $\\kappa$? Is it possible to provide crude upper and lower bounds on the relationship between these parameters to make the speed-up of Decoupled SGDA in Table 1 more meaningful compared to other algorithms?\n\nAdditionally, can you design concrete examples where the speed-up criteria are satisfied for illustration purposes?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eOEOXJUXDY", "reviewer": "Reviewer_17WE", "summary": "The authors introduce a variant of SGDA to compute solutions to decentralized min-max problems with limited communication. Players update locally with outdated strategies and synchronize intermittently, improving efficiency. Theoretical results establish near-optimal communication complexity in strongly convex–strongly concave settings, with extensions to weakly coupled games. Experiments on quadratic minimax problems and GANs to empirically validate the proposed method.\n\nPost-rebuttal\nThe authors response was helpful, but given that I am not well versed in communication complexity, I am not in a good position to evaluate the contribution of this work. I will defer to the other reviewers and maintain my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's time and effort in reviewing our work. As the first work to consider solving minimax games in a distributed setting while players are on different machines, we decided to focus on SCSC games in this study. Extending this method to other types of games, such as convex-concave or non-convex-non-concave games, is a promising direction for future work. \n\nHowever, our work introduces the following novelties: Firstly, it is not clear whether the worst-case analysis of our method could be as good as the baseline GDA. We provide a proof demonstrating that this is indeed the case (see Appendix B.2). We refer to this as the non-weakly coupled regime, in which players have high interaction with each other. On the other hand, we present a novel proof for the weakly coupled regime, where players have low interaction (see Appendix B.1). To the best of our knowledge, this is the first proof that removes the dependency on players' conditioning and instead relies solely on the degree of interaction between players, which is low in the weakly coupled regime. \n\n>Can you provide further interpretation on the conditions for speedup relative to algorithms in the literature?\n \nOther works in the literature typically consider the worst-case scenario, where no communication acceleration can be achieved when player interaction is low. For instance, the recent work [1] considers a scenario where $N$ players collaboratively find the equilibrium while taking local steps and communicating intermittently. This framework is the same as ours (we provide the $N$-player extension in Section C), yet they do not demonstrate any communication acceleration, as their convergence rate always depends on $L_{\\max}$, the maximum smoothness parameter among all players (Theorem 3.3). This assumption is overly pessimistic when player interaction is low. However, in our work we demonstrate the level of interaction using the parameter $L_c$ which is zero when there is no interaction between players and is small when interaction is low. This allows us to have a rate depending on $L_c$ (and not $L_{\\max}$) in the weakly coupled regime. As far as we know, our work is the only one that explicitly accounts for this fact in the distributed minimax problems.\nWe hope we could address your concerns about our work and would be happy to clarify if you have further questions. If we managed to address all your concerns, we appreciate if you consider increasing your score. \n\nreferences: \n[1] Yoon, T., Choudhury, S. and Loizou, N., 2025. Multiplayer federated learning: Reaching equilibrium with less communication. arXiv preprint arXiv:2501.08263.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, I checked the correctness of the convergence guarantees.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The authors do a good job of contextualizing their work in the broader literature on GDA methods for SC-SC minimax games.", "essential_references_not_discussed": "Not as far as I am aware.", "other_strengths_and_weaknesses": "While the idea presented is an interesting one, and I understand the motivation behind studying a limited communication algorithm for equilibrium computation, the novelty of the work in the paper appears to be limited, since the theoretical analysis is standard and the approach focuses on the restrictive SC-SC setting. The speedups compared to other algorithms mentioned in Table 1 is not really interpretable. A comparison of convergence rates in addition to communication complexities would help provide additional context for the proposed algorithm.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Can you provide further interpretation on the conditions for speedup relative to algorithms in the literature?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cEaw6MoCpz", "reviewer": "Reviewer_7iUK", "summary": "This paper presents a novel adaptation of Stochastic Gradient Descent Ascent (SGDA) tailored for multiplayer games where strategy updates occur intermittently. The authors introduce **Decoupled SGDA**, a method that allows players to update strategies locally using outdated opponent strategies, significantly reducing communication overhead. \nThe paper establishes theoretical guarantees for convergence in strongly-convex-strongly-concave (SCSC) games and weakly coupled games. Moreover, the proposed method outperforms existing federated minimax approaches in noisy, imbalanced settings. Numerical experiments validate its effectiveness in quadratic minimax games, federated learning, and non-convex GAN training. A further extension, **Ghost-SGDA**, is introduced as a heuristic to enhance communication efficiency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's time and effort in reviewing our work and highlighting its strengths. We would be happy to further discuss any concerns and address the reviewer’s questions. If the reviewer finds our clarifications satisfactory, we appreciate if you consider increasing your score.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "The proofs appear sound, but I did not verify all derivations.", "experimental_designs_or_analyses": "Experiments cover key settings and demonstrate benefits.", "relation_to_broader_scientific_literature": "The work extends prior research in minimax optimization, federated learning, and game theory, introducing a novel approach for communication-efficient optimization.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "#### Strengths\n- Well-motivated problem and clear contributions.\n- Theoretical guarantees and strong empirical results.\n- Addresses real-world constraints in **distributed learning and federated settings**.", "other_comments_or_suggestions": "Nothing", "questions_for_authors": "See weaknesses", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewed work investigates the effects of deferring the update of the opposing player's strategy in simultaneous gradient descent-ascent. For a class of problems the authors call "weakly coupled", they show that the resulting communication complexity is smaller than that of standard SGDA.
The reviewers found that while this insight might not be overly surprising and the contribution limited, the author's idea is novel and natural. I concur and therefore recommend acceptance.
Decision: Accept (poster)