Competitive Gradient Optimization
This addresses convergence issues in zero-sum games for machine learning and optimization researchers, but it appears incremental as it builds on gradient descent ascent variants.
The paper tackles the problem of convergence to stationary points in zero-sum games by proposing competitive gradient optimization (CGO), a gradient-based method that incorporates player interactions, and shows it converges to saddle points for strictly α-coherent functions with a provided rate of convergence.
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.