Decoupled SGDA for Games with Intermittent Strategy Communication

Ali Zindari; Anton Rodomanov; Parham Yazdkhasti; Sebastian U. Stich; Tatjana Chavdarova

REVIEW 3 major objections 4 minor 66 references

Decoupled SGDA for Games with Intermittent Strategy Communication

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Decoupled SGDA claims that weakly coupled SCSC games reach $\epsilon$-accuracy in $O(\frac{1}{1-4\kappa_c}\log\frac{1}{\epsilon})$ communication rounds, independent of player conditioning.

desk verdict Weakly-coupled noiseless rate is a genuine contribution, but Theorem 4.1's stochastic noise floor is off by a 4κ_c factor and must be fixed. read the letter →

arxiv 2501.14652 v2 pith:LP37CBXN submitted 2025-01-24 cs.LG

Ali Zindari , Parham Yazdkhasti , Anton Rodomanov , Tatjana Chavdarova , Sebastian U. Stich This is my paper · ORCID

classification cs.LG MSC 68W4090C4768W15

keywords minimaxgamesstrongly-convex-strongly-concavecommunicationcomplexitylocalupdatesweaklycoupleddistributedoptimizationfederatedintermittentstrategy

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces Decoupled SGDA, a distributed method for two-player and N-player games in which each player takes many local gradient steps using the opponent's strategy frozen at the start of the round and only synchronizes occasionally. The central claim is that in strongly-convex-strongly-concave (SCSC) games this scheme achieves near-optimal communication complexity, and that in weakly coupled games, where interaction is small relative to each player's self-interaction, the number of communication rounds to $\epsilon$-accuracy is $O\!\left(\frac{1}{1-4\kappa_c}\log\frac{1}{\epsilon}\right)$, independent of the individual condition numbers $\kappa_u$ and $\kappa_v$. This matters because standard GDA needs $O((\kappa_u+\kappa_v+\kappa_{uv}^2)\log(1/\epsilon))$ rounds, so poorly conditioned players do not force frequent synchronization when the game is weakly coupled. The paper also proves extensions to N-player games, analyzes a federated variant, and shows tolerance to imbalanced gradient noise, allowing cross-player noise variances to be arbitrarily large. A sympathetic reader would take the paper to establish that the interaction strength $L_c$, not the players' conditioning, is the right quantity governing communication in such games.

What carries the argument

The central object is the decoupled gradient operator $F_{\bar x}(x) = (\nabla_u f(u,\bar v), -\nabla_v f(\bar u, v))$, which evaluates each player's gradient with the opponent's strategy fixed at the last synchronization point $\bar x$. The paper's new constant $L_c$, defined by $\|F_{\bar x}(x)-F(x)\|_* \le L_c\|x-\bar x\|$, measures how much this frozen-operator deviates from the true gradient operator $F(x)$, and the coupling degree $\kappa_c = L_c/\bar\mu$ is the dimensionless version of that deviation. The proof machinery combines a one-round local contraction bound with step size $\gamma \le \bar\mu/\bar L^2$ (Lemma B.8) and a displacement bound (Lemma B.4) that converts the frozen-operator's error into a multiplicative factor $\kappa_c$ on the round-start distance. The per-round contraction factor is $4\kappa_c$, which is exactly why the weak-coupling condition $4\kappa_c \le 1$ is the threshold separating communication acceleration from the standard GDA rate.

What would settle it

Set up the quadratic game (13) with widely separated player conditioning, for example $\kappa_u = \kappa_v = 10^6$, and choose $C$ so that $\kappa_c = \|C\|/\min(\mu_u,\mu_v) = 0.1$, well inside the weakly coupled regime. If Decoupled GDA's required rounds to reach $\epsilon = 10^{-6}$ grow with $\kappa_u + \kappa_v$ instead of staying bounded by a constant multiple of $\log(1/\epsilon)$, the claimed independence from conditioning is false.

Watch

Extended reading notes

Core claim

The paper's discovery is a new convergence analysis for a simple decoupled update rule: at round start, players synchronize at $x_0$; during $K$ local steps, the $u$-player minimizes using $\nabla_u f(u, v_0)$ while the $v$-player maximizes using $\nabla_v f(u_0, v)$, then they synchronize again. The key comparison is against an auxiliary fixed point $x_0^*$ of the frozen-operator $F_{x_0}$, and Lemma B.4 bounds $\|x_0^*-x^*\| \le \kappa_c\|x_0-x^*\|$ with $\kappa_c = L_c/\bar\mu$. When $\kappa_c \le 1/4$, unrolling this displacement over $R$ rounds yields the contraction $D^2 e^{-(1-4\kappa_c)R}$ plus a noise term, giving the round complexity above. In the weakly coupled regime this is always no worse than GDA, and when $\kappa_c$ is small enough it even improves on the optimal first-order method for SCSC games. Outside the weakly coupled regime the same proof recovers the standard $O(\kappa^2\log(1/\epsilon))$ GDA rate.

Load-bearing premise

The advertised independence from player conditioning holds only when the game is weakly coupled, meaning the effect of freezing the opponent's strategy (quantified by $L_c$) is at most $\bar\mu/4$; if the interaction is stronger, the per-round contraction factor exceeds $1$ and the rate falls back to GDA.

Editorial extensions

If this is right

In weakly coupled SCSC games, an ill-conditioned player with very large $\kappa_u$ or $\kappa_v$ does not force more communication rounds; the needed rounds are set by the coupling constant $\kappa_c$ alone.
Fully decoupled games with $\kappa_c = 0$ can be solved without any synchronization, since enough local steps drive the iterates to equilibrium (Corollary 4.2).
In games that are not weakly coupled, the method's communication complexity degrades to the standard $O(\kappa^2\log(1/\epsilon))$ GDA rate, so the advantage is confined to the weakly coupled regime.
The method only requires bounded variance of each player's own gradient noise; cross-player noise variances may be arbitrarily large, which yields better behavior than federated minimax under imbalanced noise.
The same decoupling analysis extends to N-player games and to a federated version whose rate matches local SGD while improving the conditioning dependence of Local SGDA.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A practical implementation would need to estimate $L_c$ online and switch the synchronization schedule accordingly; the paper proves the threshold but does not provide such an estimator.
Because $L_c$ can be measured as the Lipschitz constant of $\|F_{\bar x}(x)-F(x)\|$, the framework doubles as a diagnostic: computing or approximating this constant for an application predicts in advance whether decoupled updates will reduce communication.
The Ghost-SGDA heuristic suggests that replacing the frozen opponent strategy by a short-horizon prediction could extend the savings to strongly interactive games, but this is only an empirical observation and its theory is left open.
Fewer strategy exchanges reduce the information each player exposes; the paper mentions privacy as motivation but does not analyze the privacy-communication trade-off quantitatively.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The thing to know: the weakly-coupled communication complexity result is real, but the stochastic guarantee as written is wrong. In Theorem B.9 the per-round recursion E_{r+1} ≤ 4κ_c E_r + 2γσ̄²/μ̄ unrolls to a noise floor of 2γσ̄²/(μ̄(1−4κ_c)) when the sum starts at i=0. The proof instead writes Σ_{i=1}^R (4κ_c)^i, dropping the first-round term and understating the floor by a factor 4κ_c. Theorem 4.1's stated 8κ_cσ̄²γ/(μ(1−4κ_c)) is too small, and the μ should be μ̄. For small κ_c (say 0.01) the claimed bound can be below the true one-round noise, so the theorem as stated is false in the stochastic case. The noiseless communication-acceleration claim (Corollary 4.4) survives; the fix is to correct the noise floor and propagate it to Corollary 4.3.

What is actually new: Decoupled SGDA—players update with a frozen opponent and periodic sync—is a simple and natural adaptation of SGDA, and the analysis via the coupling constant L_c and weak coupling κ_c ≤ 1/4 is new. The proof that communication rounds are O(1/(1−4κ_c) log 1/ε), independent of κ_u and κ_v, is a clean, parameter-free derivation. The comparison with FOAM is honest: they flag that it holds under a stronger assumption. The robustness to imbalanced noise (only ¯σ² bounded, not the cross-variances) is a genuine advantage over federated minimax and is shown empirically.

Soft spots, in proportion: the Theorem 4.1/B.9 indexing error is load-bearing and must be fixed. 'Near-optimal' is asserted without a lower bound. The 'first method' bullet conflicts with the concurrent work they cite (Yoon et al. 2025), so the framing needs softening. Experiments lack error bars and released code; the non-weakly-coupled and federated appendix proofs contain typos and are much harder to verify. None of these are fatal to the core idea, but the theorem error is.

Who it's for: researchers in distributed and federated minimax optimization. The weakly-coupled regime is a meaningful problem class, and the method plus L_c analysis deserve attention. A serious referee should engage; the fix is straightforward but required.

Referee Report

3 major / 4 minor

Summary. The paper proposes Decoupled SGDA for two-player zero-sum SCSC games and N-player games: each player performs K local gradient steps using the opponent's strategy from the beginning of the round, and the players synchronize strategies only every K steps. The central theoretical claim (Theorem 4.1) is that in the weakly coupled regime, defined by κ_c = L_c/μ̄ ≤ 1/4, the squared distance to equilibrium decays as D² exp(−(1−4κ_c)R) plus a noise floor, giving a communication complexity O(1/(1−4κ_c) log(1/ε)) that is independent of the player condition numbers κ_u, κ_v. A second bound in the non-weakly-coupled regime is claimed to recover the standard O(κ² log(1/ε)) GDA rate. The paper also analyzes quadratic minimax games, extends the analysis to N-player games and to a federated variant, and reports experiments on quadratic games, a toy GAN, and GAN training.

Significance. If the corrected results hold, the paper identifies a meaningful problem class—weakly coupled SCSC games—where decoupled local updates can reduce communication, and the coupling parameter L_c is a useful analytical device. The deterministic weak-coupling analysis is self-contained and parameter-free, and the claimed communication acceleration in the noiseless case survives the issues below. The paper's rates are derived from stated constants rather than fitted to experiments, and the cited workshop version is only provenance. However, the stochastic guarantee in Theorem 4.1 is not proven as stated, and one of the headline comparisons against GDA is numerically false; both issues are load-bearing for the paper's advertised claims.

major comments (3)

[Theorem B.9 / Theorem 4.1] The stochastic part of Theorem 4.1 is not proven as stated. Theorem B.9 establishes the per-round recursion E_{r+1} ≤ 4κ_c E_r + 2γσ̄²/μ̄ and then unrolls it with ∑_{i=1}^R (4κ_c)^i. The correct unrolling uses ∑_{i=0}^{R-1} (4κ_c)^i, which gives the noise floor 2γσ̄²/(μ̄(1−4κ_c)) rather than 8γσ̄²κ_c/(μ̄(1−4κ_c)). Consequently, the noise term 8κ_c σ̄²γ/(μ(1−4κ_c)) in Theorem 4.1 is too small by a factor of 4κ_c and also replaces μ̄ by μ. For κ_c=0.01 and R=1, the claimed bound is smaller than the one-round noise 2γσ̄²/μ̄, so the theorem is false as stated in the stochastic case. Corollary 4.3 and Theorem C.6 inherit the same error. The noiseless contraction claim survives, but the stochastic convergence guarantees and their corollaries need to be restated with the corrected noise floor and re-derived.
[Corollary 4.4] The assertion that Decoupled SGDA 'always has better communication complexity' than GDA in the weakly coupled regime is false. The claimed inequality 1/(1−4κ_c) ≤ κ_u+κ_v+κ_uv² does not follow from κ_c ≤ 1/4 and is contradicted by the SCSC game f(u,v) = 1/2 u² − 1/2 v² + 0.24uv. For this game μ_u = μ_v = 1, L_u = L_v = 1, L_uv = 0.24, so κ_c = 0.24, 4κ_c = 0.96, and 1/(1−4κ_c) = 25, while κ_u+κ_v+κ_uv² = 2 + 0.0576 = 2.0576. Thus the weak-coupling rate quoted in Corollary 4.4 is worse than the stated GDA rate for a valid weakly coupled game. The comparison should be restated with the min{1/(1−4κ_c), κ²} bound from Table 1 or with an additional explicit condition on κ_c, and the numerical constants should be checked against GDA's actual contraction factor.
[Theorem B.12 / Theorem 4.1 (non-weakly-coupled part)] The non-weakly-coupled part of Theorem 4.1 also needs a corrected proof. In Theorem B.12 the proof reaches the recursion E∥x_{t+1}−x*∥² ≤ (1−γµ/2)E∥x_t−x*∥² + (γµ/(16K))Σ_{i}E∥x_i−x*∥² + 2γσ̄²/µ and then states that Lemma B.10 yields exp(−γµKR/2) plus 2σ̄²γ/µ. Lemma B.10 applies to recursions with a cγ² term; with the displayed final term one obtains 2cγ/a = 4σ̄²/µ², not 2σ̄²γ/µ, and treating 2γσ̄²/µ as cγ² makes c depend on γ. The proof also displays exp(−µ²/L² R) where the theorem states exp(−γµKR/2), a further mismatch. Since this bound supports Table 1 and the second part of Corollary 4.3, the constants should be re-derived before the comparison is used.

minor comments (4)

[Theorem 4.1 and Theorem B.9] The theorem statement imposes the lower bound K ≥ (1/(γμ)) log(4/κ_c), while the proof uses K ≥ (1/(γμ̄)) log(4/κ_c). Since μ and μ̄ are distinct parameters in Assumption 2.1, the statement and proof should be aligned and the intended parameter specified.
[Proof of Theorem B.9] Lemma B.8 is a K-step bound, but the proof of Theorem B.9 appears to apply it to a generic local iterate x_{t+1}. The round-to-round recursion should be written only for the round endpoint x_K^r; please clarify the indexing so that Lemma B.8 is applied exactly where the proof needs it.
[Theorem D.5 and Lemma D.2] The stepsize condition γ ≤ max{1/L_u, 1/L_v} in Lemma D.2 and Theorem D.5 is suspicious: for the stated spectral bounds δ(A) ≤ 1 and δ(B) ≤ 1 one typically needs γ ≤ min{1/L_u, 1/L_v} or an appropriate condition per player. Please verify and correct the condition.
[Figure 1 caption and Section 5.1] The caption reads 'cPt 10, 3.5, 2, 7, 0u', which appears to be a typo for the set {10, 3.5, 2.7, 0}; the same typo appears in the text of Section 5.1.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence bounds are derived from stated problem-dependent constants and are not fitted or self-referential.

full rationale

The core claim (Theorem 4.1 and its corollaries) is a conventional derivation from Assumptions 2.1–2.4. The rate depends on the strong-monotonicity and smoothness parameters (μ̄, L̄, Lc, σ̄²) and on the user-chosen step size γ and number of local steps K; no parameter is fitted to experiments, and no quantity is defined in terms of the result it is used to prove. The weak-coupling condition κc = Lc/μ̄ ≤ 1/4 is a defined problem-class restriction, not an output of the derivation; the proof explicitly unrolls a per-round recursion with contraction factor 4κc (Theorem B.9), so the communication-complexity statement is an implication of that assumption rather than a restatement of it. Self-citations appear only as provenance (the ICML 2024 workshop version) and as background references (Stich, Zindari et al. 2023, Patel et al. 2024); none of these is load-bearing for Theorem 4.1. The reviewer-identified issue that Theorem B.9 sums the noise recursion from i=1 instead of i=0 is a potential correctness error in the stochastic noise floor, not a circularity: even if the stated 8κc σ̄²γ/(μ(1−4κc)) term is wrong, the theorem is not made equivalent to its inputs. Likewise, the comparative statement 1/(1−4κc) ≤ κu+κv+κuv² is an unproved inequality, not a circular reduction. The derivation is self-contained and externally benchmarked against GDA, EG/OGDA, and FOAM rates. Hence the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces the mathematical constants L_c and κ_c, but these are defined from problem data rather than postulated entities; no new particles, forces, or unobserved degrees of freedom are introduced. Ghost-SGDA is a heuristic variant, clearly labeled as such, not a load-bearing invented entity.

assumptions (4)

domain assumption f is μ_u-strongly convex in u and μ_v-strongly concave in v, and the full operator F is L-Lipschitz (Assumptions 2.1-2.2)
Establishes the SCSC setting and the existence of the saddle point; used in Lemmas B.4, B.5, B.8.
domain assumption The decoupled operator F̄_x is L̄-smooth and the coupling bound ∥F̄_x(x)-F(x)∥ ≤ L_c∥x-x̄∥ holds (Assumptions 2.2, 2.3)
Defines the coupling degree κ_c = L_c/μ̄, the central quantity of the weakly-coupled analysis.
domain assumption The stochastic oracle is unbiased with bounded variance σ̄² uniformly over reference points x̄ (Assumption 2.4)
Controls the additive noise term in Theorems 4.1 and B.9; the method deliberately avoids bounding the cross-player variances σ_uv, σ_vu.
domain assumption Weak coupling: κ_c = L_c/μ̄ ≤ 1/4 (Eq. (12))
Load-bearing regime condition: the per-round contraction factor is 4κ_c, so the advertised communication complexity independent of κ_u, κ_v holds only when this inequality holds.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Decoupled SGDA for Games with Intermittent Strategy Communication." pith.science (2026). https://pith.science/paper/LP37CBXN

@misc{pith2026250114652,
  author       = {Pith},
  title        = {Pith review of: Decoupled SGDA for Games with Intermittent Strategy Communication},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LP37CBXN}},
  note         = {Machine review of arXiv:2501.14652}
}

read the original abstract

We focus on reducing communication overhead in multiplayer games, where frequently exchanging strategies between players is not feasible and players have noisy or outdated strategies of the other players. We introduce Decoupled SGDA, a novel adaptation of Stochastic Gradient Descent Ascent (SGDA). In this approach, players independently update their strategies based on outdated opponent strategies, with periodic synchronization to align strategies. For Strongly-Convex-Strongly-Concave (SCSC) games, we demonstrate that Decoupled SGDA 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. Our findings extend to multi-player games. To provide insights into the effect of communication frequency and convergence, we extensively study the convergence of Decoupled SGDA for quadratic minimax problems. Lastly, in settings where the noise over the players is imbalanced, Decoupled SGDA significantly outperforms federated minimax methods.

Figures

Figures reproduced from arXiv: 2501.14652 by the authors.

**Figure 1.** Trajectories (top row) and distance to equilibrium over synchronization rounds (bottom row) of GDA (K “ 1) and Decoupled SGDA with K “ t2, 5u on the (13) problem (d “ 2). C in (13) is a constant here—the larger, the stronger the interactive term. Left-to-right: decreasing the constant c P t10, 3.5, 2, 7, 0u. The markers denote the local steps and star the solution. See § 5 for discussion. Corollary 4.4. For any K ě … view at source ↗

**Figure 2.** Number of rounds (log-scale; lower is better) to reach epsilon accuracy for varying λmaxpCq 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 In this section, we evaluate the empirical performance of Decoupled GDA. For all experiments described in this… view at source ↗

**Figure 3.** Lowest gradient norm reached after a fixed number of communication rounds, for varying 1{λ 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. 0.2 0.0 0.2 0.4 0.6 0.8 1.0 2.5 2.0 1.5 1.0 0.5 0.0 0.5 1.0 lo g(min( f )) Decoupled SGDA Local SGDA 2 4 6 8 10 1.4 1.2 1.0 0.8 … view at source ↗

Figures from the paper (6 more)

**Figure 4.** 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 SGD…

**Figure 6.** 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 Feder…

**Figure 7.** Figure 7: Comparison of our method with the federated minimax formulation: Our method splits the parameter space, while the federated formulation splits the data. Moreover, our method only allows each player to access the gradient with respect to their own parameters, whereas in…

**Figure 8.** Figure 8: Trajectories and convergence comparison of GDA,Decoupled SGDA and Decoupled SGDA with Ghost Sequence with different values of C “ CI (interaction strength). The top row shows the trajectories of the different algorithms for K “ t1, 5u over varying values of C P t25, 15…

**Figure 9.** Figure 9: Trajectories (top row) and distance to equilibrium over synchronization rounds (bottom row) of GDA (K “ 1) and Decoupled SGDA with K “ t2, 5u on the (14) problem (d “ 2). C in (13) is a constant here—the larger, the stronger the interactive term. Left-to-right: decreas…

**Figure 10.** 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 …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

66 extracted references · 40 canonical work pages

[1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...
[2]

Accelerating smooth games by manipulating spectral shapes

Azizian, W., Scieur, D., Mitliagkas, I., Lacoste-Julien, S., and Gidel, G. Accelerating smooth games by manipulating spectral shapes. In International Conference on Artificial Intelligence and Statistics, pp.\ 1705--1715. PMLR, 2020

2020
[3]

The mechanics of n-player differentiable games

Balduzzi, D., Racaniere, S., Martens, J., Foerster, J., Tuyls, K., and Graepel, T. The mechanics of n-player differentiable games. In ICML, 2018

work page 2018
[4]

Bandit learning in concave n-person games

Bravo, M., Leslie, D., and Mertikopoulos, P. Bandit learning in concave n-person games. Advances in Neural Information Processing Systems, 31, 2018

work page 2018
[5]

U., Fleuret, F., and Jaggi, M

Chavdarova, T., Pagliardini, M., Stich, S. U., Fleuret, F., and Jaggi, M. Taming gans with lookahead-minmax. arXiv preprint arXiv:2006.14567, 2020

arXiv 2006
[6]

and Mahdavi, M

Deng, Y. and Mahdavi, M. Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. In International Conference on Artificial Intelligence and Statistics, pp.\ 1387--1395. PMLR, 2021

work page 2021
[7]

and Pang, J.-S

Facchinei, F. and Pang, J.-S. Finite-dimensional variational inequalities and complementarity problems. Springer, 2003

2003
[8]

Generative adversarial nets

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 information processing systems, 27, 2014

2014

Show all 66 references

[9]

Linear lower bounds and conditioning of differentiable games

Ibrahim, A., Azizian, W., Gidel, G., and Mitliagkas, I. Linear lower bounds and conditioning of differentiable games. In International conference on machine learning, pp.\ 4583--4593. PMLR, 2020

2020
[10]

I., and Haghtalab, N

Jagadeesan, M., Jordan, M. I., and Haghtalab, N. Competition, alignment, and equilibria in digital marketplaces. ArXiv:2208.14423, 2022

2022 arXiv
[11]

M., Kidambi, R., Netrapalli, P., and Sidford, A

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

2018
[12]

and Lu, Z

Jiang, J. and Lu, Z. I2q: A fully decentralized q-learning algorithm. Advances in Neural Information Processing Systems, 35: 0 20469--20481, 2022

2022
[13]

P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A

Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T. Scaffold: Stochastic controlled averaging for federated learning. In International conference on machine learning, pp.\ 5132--5143. PMLR, 2020

2020
[14]

Tighter theory for local sgd on identical and heterogeneous data

Khaled, A., Mishchenko, K., and Richt \'a rik, P. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp.\ 4519--4529. PMLR, 2020

2020
[15]

A unified theory of decentralized sgd with changing topology and local updates

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--5393. PMLR, 2020

2020
[16]

Korpelevich, G. M. The extragradient method for finding saddle points and other problems. Matecon, 12: 0 747--756, 1976

1976
[17]

and Gasnikov, A

Kovalev, D. and Gasnikov, A. The first optimal algorithm for smooth and strongly-convex-strongly-concave minimax optimization. Advances in Neural Information Processing Systems, 35: 0 14691--14703, 2022

2022
[18]

Learning Multiple Layers of Features from Tiny Images

Krizhevsky, A. Learning Multiple Layers of Features from Tiny Images . Master's thesis, 2009

2009
[19]

Multi-hypothesis interactions in game-theoretic motion planning

Laine, F., Fridovich-Keil, D., Chiu, C.-Y., and Tomlin, C. Multi-hypothesis interactions in game-theoretic motion planning. In 2021 IEEE International Conference on Robotics and Automation (ICRA), pp.\ 8016--8023, 2021. doi:10.1109/ICRA48506.2021.9561695

2021
[20]

Fundamental benefit of alternating updates in minimax optimization

Lee, J., Cho, H., and Yun, C. Fundamental benefit of alternating updates in minimax optimization. arXiv preprint arXiv:2402.10475, 2024

2024 arXiv
[21]

Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient

Li, S., Wu, Y., Cui, X., Dong, H., Fang, F., and Russell, S. Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp.\ 4213--4220, 2019

2019
[22]

Lin, T., Jin, C., and Jordan, M. I. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pp.\ 2738--2779. PMLR, 2020

2020
[23]

A decentralized parallel algorithm for training generative adversarial nets

Liu, M., Zhang, W., Mroueh, Y., Cui, X., Ross, J., Yang, T., and Das, P. A decentralized parallel algorithm for training generative adversarial nets. Advances in Neural Information Processing Systems, 33: 0 11056--11070, 2020

2020
[24]

Precision: Decentralized constrained min-max learning with low communication and sample complexities

Liu, Z., Zhang, X., Lu, S., and Liu, J. Precision: Decentralized constrained min-max learning with low communication and sample complexities. In Proceedings of the Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks...

2023
[25]

Multi-agent actor-critic for mixed cooperative-competitive environments

Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, P., and Mordatch, I. Multi-agent actor-critic for mixed cooperative-competitive environments. Neural Information Processing Systems (NIPS), 2017

2017
[26]

Decentralized policy gradient descent ascent for safe multi-agent reinforcement learning

Lu, S., Zhang, K., Chen, T., Ba s ar, T., and Horesh, L. Decentralized policy gradient descent ascent for safe multi-agent reinforcement learning. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp.\ 8767--8775, 2021

2021
[27]

Towards deep learning models resistant to adversarial attacks

Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083, 2017

2017 arXiv
[28]

McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp.\ 1273--1282. PMLR, 2017

2017
[29]

A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach

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 on Artificial Intelligence and Statistics, pp.\ 1497--1507. PMLR, 2020

2020
[30]

Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems

Nemirovski, A. Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15 0 (1): 0 229--251, 2004

2004
[31]

Dual extrapolation and its applications to solving variational inequalities and related problems

Nesterov, Y. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109 0 (2): 0 319--344, 2007

2007
[32]

Efficiency of coordinate descent methods on huge-scale optimization problems

Nesterov, Y. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22 0 (2): 0 341--362, 2012

2012
[33]

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://ufldl.stanford.edu/housenumbers/

2011
[34]

D., and Razaviyayn, M

Nouiehed, M., Sanjabi, M., Huang, T., Lee, J. D., and Razaviyayn, M. Solving a class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019

2019
[35]

K., Glasgow, M., Zindari, A., Wang, L., Stich, S

Patel, K. K., Glasgow, M., Zindari, A., Wang, L., 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.11667, 2024

2024 arXiv
[36]

Popov, L. D. A modification of the arrow-hurwitz method of search for saddle points. Mat. Zametki, 28 0 (5): 0 777--784, 1980

1980
[37]

J., Hassani, H., and Cevher, V

Robey, A., Latorre, F., Pappas, G. J., Hassani, H., and Cevher, V. Adversarial training should be cast as a non-zero-sum game. arXiv preprint arXiv:2306.11035, 2023

2023 arXiv
[38]

Decentralized q-learning in zero-sum markov games

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: 0 18320--18334, 2021

2021
[39]

A., Xu, Z., Dickerson, J., Studer, C., Davis, L

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

2019
[40]

Federated minimax optimization: Improved convergence analyses and algorithms

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

2022
[41]

A real-time game theoretic planner for autonomous two-player drone racing

Spica, R., Cristofalo, E., Wang, Z., Montijano, E., and Schwager, M. A real-time game theoretic planner for autonomous two-player drone racing. IEEE Transactions on Robotics, 36 0 (5): 0 1389--1403, 2020. doi:10.1109/TRO.2020.2994881

2020
[42]

Stich, S. U. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019 a

2019
[43]

Stich, S. U. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint arXiv:1907.04232, 2019 b

1907 arXiv
[44]

K., Jain, P., Netrapalli, P., and Oh, S

Thekumparampil, K. K., Jain, P., Netrapalli, P., and Oh, S. Efficient algorithms for smooth minimax optimization. Advances in Neural Information Processing Systems, 32, 2019

2019
[45]

Minimax problems with coupled linear constraints: computational complexity, duality and solution methods

Tsaknakis, I., Hong, M., and Zhang, S. Minimax problems with coupled linear constraints: computational complexity, duality and solution methods. arXiv preprint arXiv:2110.11210, 2021

2021 arXiv
[46]

and Yun, S

Tseng, P. and Yun, S. A coordinate gradient descent method for nonsmooth separable minimization. Mathematical Programming, 117: 0 387--423, 2009

2009
[47]

Tsitsiklis, J. N. Problems in decentralized decision making and computation. PhD thesis, Massachusetts Institute of Technology, 1984

1984
[48]

and Morgenstern, O

Von Neumann, J. and Morgenstern, O. Theory of games and economic behavior: 60th anniversary commemorative edition. In Theory of games and economic behavior. Princeton university press, 2007

2007
[49]

and Li, J

Wang, Y. and Li, J. Improved algorithms for convex-concave minimax optimization. Advances in Neural Information Processing Systems, 33: 0 4800--4810, 2020

2020
[50]

E., Truex, S., and Wu, Y

Wei, W., Liu, L., Loper, M., Chow, K.-H., Gursoy, M. E., Truex, S., and Wu, Y. A framework for evaluating gradient leakage attacks in federated learning. arXiv preprint arXiv:2004.10397, 2020

2004 arXiv
[51]

K., Stich, S., Dai, Z., Bullins, B., Mcmahan, B., Shamir, O., and Srebro, N

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, 2020 a

2020
[52]

E., Patel, K

Woodworth, B. E., Patel, K. K., and Srebro, N. Minibatch vs local sgd for heterogeneous distributed learning. Advances in Neural Information Processing Systems, 33: 0 6281--6292, 2020 b

2020
[53]

A faster decentralized algorithm for nonconvex minimax problems

Xian, W., Huang, F., Zhang, Y., and Huang, H. A faster decentralized algorithm for nonconvex minimax problems. Advances in Neural Information Processing Systems, 34: 0 25865--25877, 2021

2021
[54]

and Boyd, S

Xiao, L. and Boyd, S. Fast linear iterations for distributed averaging. Systems & Control Letters, 53 0 (1): 0 65--78, 2004

2004
[55]

and Ryu, E

Yoon, T. and Ryu, E. K. Accelerated algorithms for smooth convex-concave minimax problems with o (1/k\^ 2) rate on squared gradient norm. In International Conference on Machine Learning, pp.\ 12098--12109. PMLR, 2021

2021
[56]

Multiplayer federated learning: Reaching equilibrium with less communication

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

2025
[57]

and Ma, T

Yuan, H. and Ma, T. Federated accelerated stochastic gradient descent. Advances in Neural Information Processing Systems, 33: 0 5332--5344, 2020

2020
[58]

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-ascent for minimax optimization. arXiv:2102.09468, 2021

2021 arXiv
[59]

Zhang, G., Wang, Y., Lessard, L., and Grosse, R. B. Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization. In International Conference on Artificial Intelligence and Statistics, pp.\ 7659--7679. PMLR, 2022 a

2022
[60]

On lower iteration complexity bounds for the convex concave saddle point problems

Zhang, J., Hong, M., and Zhang, S. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194 0 (1): 0 901--935, 2022 b

2022
[61]

U., and Loizou, N

Zhang, S., Choudhury, S., Stich, S. U., and Loizou, N. Communication-efficient gradient descent-accent methods for distributed variational inequalities: Unified analysis and local updates. In The Twelfth International Conference on Learning Representations, 2024

2024
[62]

R., and Bilen, H

Zhao, B., Mopuri, K. R., and Bilen, H. idlg: Improved deep leakage from gradients. arXiv preprint arXiv:2001.02610, 2020

2001 arXiv
[63]

Zhou, M., Guan, Y., Hayajneh, M., Niu, K., and Abdallah, C. T. Game theory and machine learning in uavs-assisted wireless communication networks: A survey. Arxiv:2108.03495, 2021

2021 arXiv
[64]

Deep leakage from gradients

Zhu, L., Liu, Z., and Han, S. Deep leakage from gradients. Advances in neural information processing systems, 32, 2019

2019
[65]

Zindari, A., Luo, R., and Stich, S. U. On the convergence of local sgd under third-order smoothness and hessian similarity. In OPT 2023: Optimization for Machine Learning, 2023

2023
[66]

Zindari, A., Yazdkhasti, P., Chavdarova, T., and Stich, S. U. Decoupled stochastic gradient descent for n-player games. In ICML 2024 Workshop: Aligning Reinforcement Learning Experimentalists and Theorists, 2024

2024

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

[2] [2]

Accelerating smooth games by manipulating spectral shapes

Azizian, W., Scieur, D., Mitliagkas, I., Lacoste-Julien, S., and Gidel, G. Accelerating smooth games by manipulating spectral shapes. In International Conference on Artificial Intelligence and Statistics, pp.\ 1705--1715. PMLR, 2020

2020

[3] [3]

The mechanics of n-player differentiable games

Balduzzi, D., Racaniere, S., Martens, J., Foerster, J., Tuyls, K., and Graepel, T. The mechanics of n-player differentiable games. In ICML, 2018

work page 2018

[4] [4]

Bandit learning in concave n-person games

Bravo, M., Leslie, D., and Mertikopoulos, P. Bandit learning in concave n-person games. Advances in Neural Information Processing Systems, 31, 2018

work page 2018

[5] [5]

U., Fleuret, F., and Jaggi, M

Chavdarova, T., Pagliardini, M., Stich, S. U., Fleuret, F., and Jaggi, M. Taming gans with lookahead-minmax. arXiv preprint arXiv:2006.14567, 2020

arXiv 2006

[6] [6]

and Mahdavi, M

Deng, Y. and Mahdavi, M. Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. In International Conference on Artificial Intelligence and Statistics, pp.\ 1387--1395. PMLR, 2021

work page 2021

[7] [7]

and Pang, J.-S

Facchinei, F. and Pang, J.-S. Finite-dimensional variational inequalities and complementarity problems. Springer, 2003

2003

[8] [8]

Generative adversarial nets

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 information processing systems, 27, 2014

2014