Source-linked AI summary
Competitive Gradient Descent
Florian Schäfer, Anima Anandkumar
TL;DR
Competitive optimization offers a flexible way to formulate problems across optimization, statistics, and machine learning, but its potential depends on efficient, reliable numerical algorithms. CGD uses a bilinear two-player approximation; in the reported experiments, it avoids divergence seen in competing methods at stronger interactions.
Problem
Competitive optimization has applications across optimization, statistics, and machine learning, but realizing its potential depends on efficient and reliable numerical algorithms.
Source: §1 · pp. 1–2Method
CGD generalizes gradient descent using a bilinear two-player approximation, the lowest-order approximation that can capture interaction between players.
Source: §2 · p. 3Results
Takeaways & Limitations
CGD handled tested stepsize choices without divergence, whereas existing methods may require small stepsizes that slow convergence and can require trial and error to select.
Source: §1 · pp. 2–3The convergence results are restricted to zero-sum games, although the authors expect they can extend to games dominated by competition.
Source: §2 · p. 4
Abstract
from arXiv · showhide
We introduce a new algorithm for the numerical computation of Nash equilibria of competitive two-player games. Our method is a natural generalization of gradient descent to the two-player setting where the update is given by the Nash equilibrium of a regularized bilinear local approximation of the underlying game. It avoids oscillatory and divergent behaviors seen in alternating gradient descent. Using numerical experiments and rigorous analysis, we provide a detailed comparison to methods based on \emph{optimism} and \emph{consensus} and show that our method avoids making any unnecessary changes to the gradient dynamics while achieving exponential (local) convergence for (locally) convex-concave zero sum games. Convergence and stability properties of our method are robust to strong interactions between the players, without adapting the stepsize, which is not the case with previous methods. In our numerical experiments on non-convex-concave problems, existing methods are prone to divergence and instability due to their sensitivity to interactions among the players, whereas we never observe divergence of our algorithm. The ability to choose larger stepsizes furthermore allows our algorithm to achieve faster convergence, as measured by the number of model evaluations.
1 Introduction
Competitive optimization provides a language for multi-agent objectives, but reliable numerical methods are needed to realize its potential in machine learning. The paper introduces competitive gradient descent (CGD) to address oscillatory or divergent gradient descent-ascent and reports stronger robustness as player interactions increase.
1 Introduction
- Competitive optimization expresses multi-agent objectives and has been used to encode robustness in optimization and statistics and to formulate machine-learning objectives.The paper cites reinforcement learning and generative models as machine-learning applications, while noting that reliable numerical algorithms are needed to realize the approach’s potential.Source: §1 · pp. 1–2
- Gradient descent-ascent can oscillate or diverge even in a bilinear game, limiting its reliability as a general competitive-optimization workhorse.The paper relates this cycling to each player responding optimally to the other’s last move.Source: §1 · p. 2
- Prior stabilization approaches include structured minimization, predictive or optimistic updates, and modifications to gradient dynamics.The paper’s central objection is that many rely on additional assumptions, modifications, and model parameters rather than a clear game-theoretic motivation.Source: §1 · p. 2
- CGD updates are the Nash equilibrium of a regularized bilinear approximation, and its convergence improves with stronger player interactions without stepsize adaptation.Existing methods may require stepsizes inversely proportional to interaction magnitude, making convergence slow and requiring trial and error.Source: §1 · p. 2
- Across experiments, CGD never diverged; on noiseless nonconvex matrix estimation it was more than twice as fast as other methods, with the speed ratio increasing on larger, harder problems.Existing methods diverged on the bimodal Gaussian mixture example across five constant RMSProp stepsizes; CGD approximated the target distribution with all five.Source: §1 · p. 3
2 Competitive gradient descent
Competitive gradient descent (CGD) generalizes gradient descent by choosing an update from the Nash equilibrium of a regularized bilinear local game. The paper develops this game-theoretic update and establishes convergence and stability results under stated conditions.
2 Competitive gradient descent
- CGD’s update is the Nash equilibrium of a regularized bilinear local game, which preserves player interactions that linear approximations cannot express.The update is defined for competitive optimization using function evaluations, gradients, and Hessian-vector products.Source: §2 · pp. 3–4
- A series interpretation makes CGD’s update successively account for what each player thinks the other player will do, with the Nash equilibrium recovered in the limit.The first partial sum corresponds to gradient descent-ascent; the second corresponds to LCGD.Source: §2 · p. 4
- The rigorous convergence results are restricted to zero-sum games, although the authors expect extension to games dominated by competition.The paper states this boundary when introducing its convergence analysis.Source: §2 · p. 4
- Under the stated assumptions, CGD converges exponentially to a critical point, and near a critical point it converges locally at an exponential rate depending only on λmin.The global result requires suitable curvature conditions; the local stability result assumes a twice differentiable function with Lipschitz continuous Hessian.Source: §2 · p. 5
- Stronger player interactions improve CGD’s convergence results, whereas existing modifications require stepsizes inversely proportional to an upper bound on interaction strength.The paper reports that experiments show existing methods prone to divergence under strong interactions.Source: §2 · p. 5
- CGD’s bilinear approximation avoids diagonal Hessian terms that can make the update matrix singular or imply players choose worst rather than best strategies outside convex-concave or bounded-curvature settings.It also uses first-order information of component functions without requiring their second derivatives, useful when those components have only first-order regularity.Source: §2 · pp. 5–6
3 Consensus, optimism, or competition?
The section compares update rules through gradient, competitive, consensus, and higher-order corrections, then tests how these ingredients affect convergence across bilinear, convex-concave, and concave-convex games. The experiments show that competition addresses bilinear cycling, while consensus can accelerate convergence or produce undesirable solutions depending on the game.
3 Consensus, optimism, or competition?
- OGDA’s update uses gradient differences as finite-difference approximations to Hessian-vector products, while LCGD skips CGD’s matrix inverse and keeps its leading-order term.LCGD also coincides with first-order LOLA.Source: §3 · p. 6
- The update-rule comparison decomposes methods into gradient, competitive, consensus, and equilibrium terms; CGD’s equilibrium term arises from solving for a Nash equilibrium.The competitive term anticipates the other player’s naive strategy or decreases their influence; the consensus term can decrease or increase each player’s gradient.Source: §3 · pp. 6–7
- In the bilinear game, only CGD converges at α = 6.0; at α = 3.0, OGDA diverges while ConOpt and SGA oscillate widely.At α = 1.0, all methods except GDA converge exponentially, with ConOpt and SGA faster than the others.Source: §3 · p. 7, Figure 2 · p. 8
- For the convex-concave game, OGDA and ConOpt fail at α = 3.0, and all methods diverge at α = 6.0.At α = 1.0, all methods converge exponentially; ConOpt is fastest and OGDA slowest.Source: §3 · p. 7, Figure 3 · p. 8
- In the concave-convex game at α = 1.0, ConOpt converges to the non-equilibrium point (0, 0), while the other algorithms diverge.As α increases to 3.0 or 6.0, ConOpt’s attraction radius shrinks and it also diverges from (0.5, 0.5).Source: §3 · p. 7, Figure 3 · p. 8
- The competitive term alone solves bilinear cycling, while the experiments do not show a systematic benefit from adding the consensus term with either sign.The authors therefore suggest using only the competitive term, as in LOLA/LCGD, CGD, or SGA.Source: §3 · pp. 7–8
4 Implementation and numerical results
The implementation computes mixed-Hessian vector products and approximates the equilibrium-term inverse with iterative solvers. In experiments, CGD remains stable on a bimodal GAN task and can outperform alternatives in covariance estimation by exploiting larger stepsizes.
4 Implementation and numerical results
- Mixed-Hessian vector products can be computed with forward- and reverse-mode automatic differentiation or approximated by finite differences.The products are described as having minimal overhead over gradient computation.Source: §4 · p. 8
- For zero-sum games, the authors recommend conjugate gradient to approximate equilibrium-term inverse products; for nonzero-sum games, they recommend GMRES or BCGSTAB.Their experiments terminate the iterative solve at relative residual tolerance 10^-6.Source: §4 · pp. 8–9
- Figure 4 encodes generator updates with arrows and discriminator logits with color; only CGD avoids eventual instability and distributes mass evenly across the two modes.All methods initially cycle between the modes.Source: Figure 4 · p. 9
- CGD produces a reasonable two-mode distribution without mode collapse across tested stepsizes, while the other methods diverge after initial cycling.Reducing their stepsize to 0.001 did not seem to help, though the authors do not rule out success with proper hyperparameter tuning.Source: §4 · p. 9, Figure 4 · p. 9
- CGD beats other methods by more than a factor of two in covariance estimation when measured by model evaluations, because it converges with larger stepsizes.At comparable stepsizes, its convergence rate is similar to the alternatives.Source: §4 · p. 9, Figure 5 · p. 9
5 Conclusion and outlook
The paper presents CGD as a game-theoretically motivated, more robust generalization of gradient descent for competitive optimization. It identifies extensions to more players and higher-order methods, while noting that a convergence proof for the nonconvex case remains out of reach.
5 Conclusion and outlook
- A convergence proof for nonconvex competitive games remains out of reach, in part because gradient norms need not decrease monotonically in nonconvex-concave games.The paper says a suitable measure of progress is still needed.Source: §5 · p. 10
- The authors identify practical implementation and evaluation of CGD, extensions beyond two players, and biquadratic models with cubic regularization as directions for future work.The multi-player extension would use multilinear quadratically regularized local models, whose implementation and evaluation remain open.Source: §5 · p. 10
- The paper characterizes CGD as a natural gradient-descent generalization with attractive game-theoretic interpretation and improved robustness relative to existing methods.Source: §5 · p. 10
A Proofs of convergence
The proof establishes exponential convergence by showing local contraction of gradient norms near a critical point. Its argument uses cancellation between players’ interactive terms, together with curvature and regularity bounds.
A Proofs of convergence
- Cancellation across players turns purely interactive terms into convergence-inducing terms in the update analysis.The proof then uses curvature and interaction estimates to control the remaining terms.Source: A Proofs of convergence · p. 13
- Near a critical point, CGD contracts the gradient norm by a factor at most 1 − λmin/4, yielding exponential convergence for sufficiently nearby starts.The proof uses continuity of the gradient and Hessian to obtain a neighborhood where the contraction holds, then a smaller invariant neighborhood.Source: A Proofs of convergence · p. 15
- The local contraction argument relies on continuous gradients and Hessians at the critical point to keep nearby iterates within the region where the bound applies.Source: A Proofs of convergence · p. 15
B.1 Experiment: Estimating a covariance matrix
In deterministic covariance estimation, CGD matches OGDA at comparable stepsizes and can converge faster by using larger stepsizes that destabilize competing methods. In the stochastic setting, noise limits its approximation advantage, but it remains the only tested method that does not diverge across stepsizes.
B.1 Experiment: Estimating a covariance matrix
- The deterministic comparison measures residual reduction against forward evaluations for d = 20, 40, and 60, with missing algorithm–stepsize combinations indicating divergence.Source: §B.1 · p. 15, Figure 6 · p. 16
- For d = 40 or 60, OGDA, SGA, and ConOpt become unstable, leaving only the smallest-stepsize OGDA convergent besides CGD, and it is much slower than larger-stepsize CGD.At matched stepsizes, CGD’s convergence rate is comparable to OGDA; larger stepsizes let CGD achieve significantly better rates.Source: §B.1 · pp. 15, 17, Figure 6 · p. 16
- In the stochastic setting, noise quickly dominates the error and prevents CGD from achieving significantly better approximations, although it is the only method that does not diverge at any tested stepsize.The trajectories of CGD are also described as less noisy and more regular than those of other algorithms.Source: §B.1 · p. 17
B.2 Experiment: Fitting a bimodal distribution
The authors test CGD on a GAN fitting a two-component Gaussian mixture. In this experiment, competing methods diverge even at a reduced stepsize, whereas CGD appears robust and distributes generated mass across both modes.
B.2 Experiment: Fitting a bimodal distribution
- The experiment uses a GAN with four-hidden-layer generator and discriminator networks, 512-dimensional Gaussian input, and batches of 256 real and 256 generated examples.The target is a mixture of two Gaussian random variables with standard deviation 0.1.Source: §B.2 · p. 17
- SGA, ConOpt, and OGDA eventually diverge in the GAN experiment, and reducing their stepsize to 0.001 does not prevent divergence.Divergence occurs as the generator either moves mass far from the mode or collapses its map to zero.Source: §B.2 · p. 17
- After initial cycling, CGD starts splitting generated mass roughly evenly between the two mixture modes, a configuration described as robust during the experiments.Source: §B.2 · p. 17