Decoupled SGDA for Games with Intermittent Strategy Communication

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.

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.

However, 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.

Can you provide further interpretation on the conditions for speedup relative to algorithms in the literature?

Other 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. We 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.

references: [1] Yoon, T., Choudhury, S. and Loizou, N., 2025. Multiplayer federated learning: Reaching equilibrium with less communication. arXiv preprint arXiv:2501.08263.

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.

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?

It 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.

Can you design concrete examples where the speed-up criteria are satisfied for illustration purposes?

To 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.

We 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.

references: [1] Yoon, T., Choudhury, S. and Loizou, N., 2025. Multiplayer federated learning: Reaching equilibrium with less communication. arXiv preprint arXiv:2501.08263.

We appreciate the reviewer’s time and effort in reviewing our work.

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.

This 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.

If a player partially observes the other’s parameters between rounds, can the approach be adapted to incorporate partial synchronization?

Thank 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.

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$?

The 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. If 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.

Have you considered weaker assumptions like Minty variational inequalities or quasi-strong convexity? If not, do you anticipate major challenges?

Yes, 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:

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:

$\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$

This 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.

We can relax the strong monotonicity assumption of the operator $F$ and we still can drive the results in Theorem B.12 as follows:

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:

$\langle F(\mathbf{x}) - F(\mathbf{x}^{\star}), \mathbf{x} - \mathbf{x}^{\star} \rangle \geq \mu''||\mathbf{x} - \mathbf{x}^{\star}||^2$

Therefore, Assumption 2.2 can be replaced with these two new assumption.

Could you comment more on the empirical overhead or potential instability of “ghost updates”?

Decoupled 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). Ghost Sequence is stable and improves performance in simple (quadratic) games. Its effectiveness in complex scenarios (e.g., GAN training) needs more study.

Are there conditions under which Ghost-SGDA might fail to converge or require additional assumptions?

For 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. We 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.