2022/05/27 by Abhijeet Vyas, Vyas, Abhijeet, Kamyar Azizzadenesheli +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2205.14232
openalex publication_date 2022/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.