Decoupled SGDA for Games with Intermittent Strategy Communication

Thanks a lot for your time reviewing our paper and for your feedback.

The analysis is restricted to strongly convex and strongly monotone games, is it possible to extend to a more general setting?

It is possible to use regularization technique in order to derive a rate for convex-concave games from the current results for strongly-convex-strongly-concave games. However, we leave the direct proof for convex-concave games for the future works.

It seems the theoretical proof is standard and the technical contribution is weak.

While the approach on a high level is standard, the difficulty is in identifying regimes and quantifying the acceleration—both of which are novel aspects of this work. Particularly, prior works rely on the assumption $\||\nabla f(x_1,y_1) - \nabla f(x_2,y_2) \||^2 \leq L^2[\||x_1-x_2\||^2 + \||y_1-y_2\||^2]$. We do not rely solely on this assumption, as it can be pessimistic when the interaction between players is low. This necessitates a novel proof approach, particularly leveraging Equation 3 from the paper. Thus, we consider identifying this weakly coupled regime as the novelty of our work.

In line 287, the function r(u,v) is not clear. Is this the same as r(u,v) in Eq. (5)?

Yes, it is the same $r(u, v)$ as in Eq. 5, thanks for your helpful comment. We added a reference to Eq. 5 in the revised version.

Regarding the 'Ghost sequence' proposed in Appendix G, could you explain the update of the ghost sequence in Algorithm 4?

In Algorithm 1, each player assumes that the other player’s strategy remains fixed during their local steps. Specifically, in round $r$, player $u$ uses the gradient $\nabla f(u_t^r, v_0^r)$, where $v_0^r$ is kept constant throughout all local steps. Between communication rounds, player $u$ does not receive updates about player $v$’s strategy, relying only on the information available from the last communication round. Algorithm 4 differs from Algorithm 1 in how it approximates the other player’s strategy during local steps. In Algorithm 4, player $u$ uses a ghost sequence $\hat{v}$ to dynamically approximate player$v$’s strategy. The ghost sequence is updated during each local step by adding $\Delta\_{v}^r := \frac{1}{K} (v^r_0 - v^{r-1}\_0),$ where $\Delta_{v}^r$represents an estimated average change in player $v$’s strategy between communication rounds.

In this approach, Algorithm 4 adjusts dynamically to the other player’s strategy changes, rather than treating it as fixed. While this is a simple way to build the ghost sequence, exploring more advanced methods is an interesting future research direction. Algorithm 4 sets a basis framework for the development of other advanced methods. Although this is a heuristic, our experiments showed that it works well in practice. We leave the theoretical analysis of this method to future work.

We would like to thank the reviewer again for their comment and time. Please consider increasing your score if you believe your concerns have been resolved. Otherwise, please let us know so that we can provide more explanations.

Thanks a lot for your time reviewing our paper and for your feedback.

Many notations (i.e., the Lipschitzness constant and the strong convexity constants) make the theorems less intuitive and hard to interpret. It would be helpful if the algorithm's complexity and comparison with other methods were discussed in more detail.

Thanks for your improvement suggestions. We applied several changes to the revised version, which include:

• In Equation 3, we replaced $L_{uv}$ and $L_{vu}$ with a single parameter $L_c$. Note that variables $L_{uv}$ and $L_{vu}$ are usually the same (in twice continuously differentiable functions). So we do not loose anything by using one variable $L_c$ instead.
• We introduced a new parameter $\mu_0$, representing the strong monotonicity parameter for the operator $F_0$, instead of using $\mu_u$ and $\mu_v$. Our analysis only needs $\mu_0$ and we no longer need to keep two separate variables $\mu_u$ and $\mu_v$ (although we show that $\mu_0$ is indeed related to $\mu_u$ and $\mu_v$).
• The definition of $\theta$ has been simplified to $\theta = \frac{L_c}{\mu_0}$.
• We also made some minor corrections to fix typos.

Table 1 presents certain conditions under which the proposed algorithm is faster than existing methods, but the condition is less intuitive. It would be helpful to give concrete examples that satisfy these conditions.

Consider the following quadratic function:

$$f(u, v) = g(u) - h(v) + \langle Cu, v \rangle,$$

where $C$ is a fixed matrix, and $g(u)$ and $h(v)$ are both $\mu$-strongly convex and $L$-smooth.

To achieve communication acceleration compared to GDA, our method needs $L_c := \||C\||$ to be sufficiently small compared to $\mu$:

$$L_c \le \frac{\mu}{4}.$$

Furthermore, for communication acceleration compared to the other algorithms in Table 1, a stronger assumption on the matrix $C$ is required:

$$L_c \leq 2\mu\sqrt{1 - \frac{1}{\kappa}}.$$

Here, $\kappa := \frac{L}{\mu}$ is the ``classical'' condition number. With this assumption, $f$ satisfies the conditions specified in the Speed Up column of Table 1.

The right-hand side of the above inequality increases with $\kappa$. This implies that the more ill-conditioned the functions $g(u)$ and $h(v)$ in $f$ are, the greater the communication efficiency of our algorithm compared to others.

Minor Comments:

Thanks for your comment. We fixed them in the revised version.

We would like to thank the reviewer again for their comment and time. Please consider increasing your score if you believe your concerns have been resolved. Otherwise, please let us know so that we can provide more explanations.

Thanks a lot for your time reviewing our paper and for your feedback.

There seems to be a discussion which is missing comparing the convergence rates of the proposed algorithm with standard methods in the literature. Table 1 compares the communication complexity of decoupled SGDA in comparison with existing methods, but it would also be interesting to have a table with the convergence rates to the minmax equilibrium, which would depend on R,K .

We believe Table 1 addresses the point you raised. In Table 1, we compare the communication complexity of our method with that of other methods. Note that for other methods, the communication complexity is the same as the iteration complexity (i.e., the total number of steps required to reach $\epsilon$ accuracy) because they do not utilize local steps. To make this clearer,

• we changed the caption of Table 1
• we added citations for the remaining methods in the table

Thanks for raising this.

The related work section on Federated Learning feels slightly misplaced given that only the experiments in Sec 5.3 are related to Federated Learning. Would it make sense to move the related work for FL to the appendix and expand more on the gradient descent/minmax optimization specific related work in the main text?

Thanks a lot for your improvement suggestions. In the uploaded revised version, we moved the Federated Learning discussion to the appendix and expanded the discussion of the min-max related work.

The notation for condition numbers $\kappa_u$, $\kappa_v$ are used before their definition (e.g. in the related work section, in the paragraph before Corollary 3). Meanwhile they are only defined at the bottom of page 6.

The revised version resolves this; thanks for noticing.

There are also several typos I've found, listed below

Thanks for pointing out the typos. We fixed them in the revised version.

How does Decoupled SGDA behave if the stepsizes are decreasing? Many of the existing results in the literature crucially depend on carefully chosen decreasing stepsize, so having a method which uses constant stepsize might be preferable. But regardless, I am curious how the convergence results change if (for instance) the local updates are performed with a decreasing stepsize.

Thank you for your insightful question. In this paper, we focus on analyzing SGD with a constant step size. However, we believe it is possible to extend our analysis to variations of SGD that employ a decreasing step size (the consensus error Lemma 17 would need to be adapted accordingly). That said, we are uncertain whether this would further reduce communication complexity. We leave this exploration for future work.

The fact that only the noise on the self-gradients needs to be bounded for the Decoupled SGDA update seems unintuitive to me, can you comment on what the trade-off is? For instance, does this come at a cost of slower convergence rate if the gradients are too noisy, even if it does not affect the communication complexity?

In our proposed method (Algorithm 1) there are two local update rules,

f(u_t^r, v_0^r)$$ $$v_{t+1}^r = v_t^r + \gamma\nabla_{v} f(u_0^r, v_t^r)$$ Note that each of the above update rules uses a different oracle for computing gradients, as they are computed on different players (compute nodes) in parallel. We call the gradient oracle queried by player $u$, $G_u$, and the one queried by player $v$, $G_v$. Without loss of generality, let’s only consider the update rule for player $u$'s parameters. We can see that player $u$ only uses its self-gradient for performing local steps. In another word, player $u$ only uses $[G_{u}(x,\xi)]\_u$, although oracle $G_{u}(x,\xi)$ also returns the gradient with respect to parameter $v$ as well ($[G_{u}(x,\xi)]\_v$). Therefore, we can argue that the only necessary assumption on the boundedness of oracle $G_u$'s noise variance is $$E[\||[G_{u}(x,\xi)]\_u -[F(x)]\_u\||^2] \le \sigma^2_{u u}$$ In another word, $E[\||[G_{u}(x,\xi)]\_v -[F(x)]\_v\||^2]$ can be arbitrarily large because $[G_{u}(x,\xi)]\_v$ is not used in Algorithm 1. Similarly, we can argue $E[\||[G_{v}(x,\xi)]\_u -[F(x)]\_u\||^2]$ can be arbitrarily large. This is, in fact, an advantage of our algorithm in comparison to other distributed minimax methods, as they require an upper bound on both $E[\||[G_{u}(x,\xi)]\_v -[F(x)]\_v\||^2]$ and $E[\||[G_{v}(x,\xi)]\_u -[F(x)]\_u\||^2]$. It means that a large value of $E[\||[G_{u}(x,\xi)]\_v -[F(x)]\_v\||^2]$ and $E[\||[G_{v}(x,\xi)]\_u -[F(x)]\_u\||^2]$ slows down the convergence of other methods while our method is not affected by that. We would like to thank the reviewer again for their comment and time.

Thanks a lot for your time reviewing our paper and for your feedback.

The idea of the algorithm (Decoupled SGDA) is natural, and the analysis seems to be standard.

While the approach on a high level is standard, the difficulty is in identifying regimes and quantifying the acceleration—both of which are novel aspects of this work. Particularly, prior works rely on the assumption $\||\nabla f(x_1,y_1) - \nabla f(x_2,y_2) \||^2 \leq L^2[\||x_1-x_2\||^2 + \||y_1-y_2\||^2]$. We do not rely solely on this assumption, as it can be pessimistic when the interaction between players is low. This necessitates a novel proof approach, particularly leveraging Equation 3 from the paper. Thus, we consider identifying this weakly coupled regime as the novelty of our work.

I think the focus on the paper is on minmax optimization, instead of games (in particular, two-player zero-sum games are really really special case of games), so I suggest the author to properly changes the title to reflect this fact.

Note that this work also studies the more general case of $N$-player games, detailed in Appendix C. The main part focuses only on two-player games to simplify the notation. Therefore, we believe the title is adequate, as the broader class of $N$-player games is addressed. This point is highlighted under the contributions in Section 1. Thank you for bringing up this concern.

We would like to thank the reviewer again for their comment and time. Please consider increasing your score if you believe your concerns have been resolved. Otherwise, please let us know so that we can provide more explanations.