Competitive Gradient Optimization
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 $\alpha$-coherent function for which we provide
convergence analysis. We show that for strictly $\alpha$-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 $\alpha$-coherent class of functions.