# Competitive Gradient Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 45 references that are in the map.
- First posted on arXiv 27 May 2022.

## Builds on (most cited first, 25 of 25)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks](https://mlsanity.com/paper/1511.06434/) (2015)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Learning with Opponent-Learning Awareness](https://mlsanity.com/paper/1709.04326/) (2017)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Unrolled Generative Adversarial Networks](https://mlsanity.com/paper/1611.02163/) (2016)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [The Numerics of GANs](https://mlsanity.com/paper/1705.10461/) (2017)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [On Gradient-Based Learning in Continuous Games](https://mlsanity.com/paper/1804.05464/) (2018)
- [Competitive Gradient Descent](https://mlsanity.com/paper/1905.12103/) (2019)
- [Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent](https://mlsanity.com/paper/1907.04392/) (2019)
- [A Lyapunov Analysis of Momentum Methods in Optimization](https://mlsanity.com/paper/1611.02635/) (2016)
- [What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?](https://mlsanity.com/paper/1902.00618/) (2019)
- [On the Impossibility of Global Convergence in Multi-Loss Optimization](https://mlsanity.com/paper/2005.12649/) (2020)
- [Stabilizing Adversarial Nets With Prediction Methods](https://mlsanity.com/paper/1705.07364/) (2017)
- [An Online Learning Approach to Generative Adversarial Networks](https://mlsanity.com/paper/1706.03269/) (2017)
- [Competitive Policy Optimization](https://mlsanity.com/paper/2006.10611/) (2020)

## Built on by (most cited first, 1 of 1)

- [Beyond first-order methods for non-convex non-concave min-max optimization](https://mlsanity.com/paper/2304.08389/) (2023)

## Abstract (arXiv)

We study the problem of convergence to a stationary point in zero-sum games. We propose competitive gradient optimization (CGO ), a gradient-based method that incorporates the interactions between the two players in zero-sum games for optimization updates. We provide continuous-time analysis of CGO and its convergence properties while showing that in the continuous limit, CGO predecessors degenerate to their gradient descent ascent (GDA) variants. We provide a rate of convergence to stationary points and further propose a generalized class of α-coherent function for which we provide convergence analysis. We show that for strictly α-coherent functions, our algorithm convergences to a saddle point. Moreover, we propose optimistic CGO (OCGO), an optimistic variant, for which we show convergence rate to saddle points in α-coherent class of functions.