# Competitive Gradient Descent

arXiv: https://arxiv.org/abs/1905.12103 · HTML: https://mlsanity.com/paper/1905.12103/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2019.

## Built on by (most cited first, 30 of 32)

- [COLA: Consistent Learning with Opponent-Learning Awareness](https://mlsanity.com/paper/2203.04098/) (2022)
- [Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization](https://mlsanity.com/paper/2102.09468/) (2021)
- [Competitive Physics Informed Networks](https://mlsanity.com/paper/2204.11144/) (2022)
- [A Ranking Game for Imitation Learning](https://mlsanity.com/paper/2202.03481/) (2022)
- [Minimax Model Learning](https://mlsanity.com/paper/2103.02084/) (2021)
- [Discretization Drift in Two-Player Games](https://mlsanity.com/paper/2105.13922/) (2021)
- [Riemannian Hamiltonian methods for min-max optimization on manifolds](https://mlsanity.com/paper/2204.11418/) (2022)
- [Complex Momentum for Optimization in Games](https://mlsanity.com/paper/2102.08431/) (2021)
- [Minimax and Neyman-Pearson Meta-Learning for Outlier Languages](https://mlsanity.com/paper/2106.01051/) (2021)
- [Learning with Logical Constraints but without Shortcut Satisfaction](https://mlsanity.com/paper/2403.00329/) (2024)
- [Equivariance Allows Handling Multiple Nuisance Variables When Analyzing Pooled Neuroimaging Datasets](https://mlsanity.com/paper/2203.15234/) (2022)
- [In-Trajectory Inverse Reinforcement Learning: Learn Incrementally Before An Ongoing Trajectory Terminates](https://mlsanity.com/paper/2410.15612/) (2024)
- [Effects of Spectral Normalization in Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2212.05331/) (2022)
- [Adaptive Consensus Optimization Method for GANs](https://mlsanity.com/paper/2304.10317/) (2023)
- [Recursive Reasoning in Minimax Games: A Level k Gradient Play Method](https://mlsanity.com/paper/2210.16482/) (2022)
- [Analysing the Sample Complexity of Opponent Shaping](https://mlsanity.com/paper/2402.05782/) (2024)
- [Automatic debiasing of neural networks via moment-constrained learning](https://mlsanity.com/paper/2409.19777/) (2024)
- [Equilibrium Learning in Combinatorial Auctions: Computing Approximate Bayesian Nash Equilibria via Pseudogradient Dynamics](https://mlsanity.com/paper/2101.11946/) (2021)
- [Scalable Balanced Training of Conditional Generative Adversarial Neural Networks on Image Data](https://mlsanity.com/paper/2102.10485/) (2021)
- [Polymatrix Competitive Gradient Descent](https://mlsanity.com/paper/2111.08565/) (2021)
- [Competitive Gradient Optimization](https://mlsanity.com/paper/2205.14232/) (2022)
- [ApproxED: Approximate exploitability descent via learned best responses](https://mlsanity.com/paper/2301.08830/) (2023)
- [Beyond first-order methods for non-convex non-concave min-max optimization](https://mlsanity.com/paper/2304.08389/) (2023)
- [Kolmogorov n-Widths for Multitask Physics-Informed Machine Learning (PIML) Methods: Towards Robust Metrics](https://mlsanity.com/paper/2402.11126/) (2024)
- [A Gauss-Newton Approach for Min-Max Optimization in Generative Adversarial Networks](https://mlsanity.com/paper/2404.07172/) (2024)
- [Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularization](https://mlsanity.com/paper/2405.02769/) (2024)
- [GDA-AM: On the effectiveness of solving minimax optimization via Anderson Acceleration](https://mlsanity.com/paper/2110.02457/) (2021)
- [Uncoupled Learning of Differential Stackelberg Equilibria with Commitments](https://mlsanity.com/paper/2302.03438/) (2023)
- [Number Theoretic Accelerated Learning of Physics-Informed Neural Networks](https://mlsanity.com/paper/2307.13869/) (2023)
- [Preference-based opponent shaping in differentiable games](https://mlsanity.com/paper/2412.03072/) (2024)

## Abstract (arXiv)

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 optimism and 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.