Pith. sign in

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

Editorial analysis

A structured set of objections, weighed in public.

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

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)
  1. [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.
  2. [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.
  3. [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)
  1. [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.
  2. [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.
  3. [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.
  4. [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
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
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 De￾coupled GDA. For all experiments described in this… view at source ↗
Figure 3
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. 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. 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. 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. 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. 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. 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. [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

Show all 66 references
  1. [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

  2. [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

  3. [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

  4. [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

  5. [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

  6. [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

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

  8. [16]

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

    1976

  9. [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

  10. [18]

    Learning Multiple Layers of Features from Tiny Images

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

    2009

  11. [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

  12. [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

  13. [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

  14. [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

  15. [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

  16. [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

  17. [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

  18. [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

  19. [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

  20. [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

  21. [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

  22. [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

  23. [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

  24. [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

  25. [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

  26. [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

  27. [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

  28. [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

  29. [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

  30. [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

  31. [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

  32. [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

  33. [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

  34. [42]

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

    2019

  35. [43]

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

    1907 arXiv

  36. [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

  37. [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

  38. [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

  39. [47]

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

    1984

  40. [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

  41. [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

  42. [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

  43. [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

  44. [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

  45. [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

  46. [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

  47. [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

  48. [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

  49. [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

  50. [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

  51. [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

  52. [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

  53. [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

  54. [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

  55. [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

  56. [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

  57. [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

  58. [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.