Timezone: »

Competitive Gradient Optimization
Abhijeet Vyas · Brian Bullins · Kamyar Azizzadenesheli

Tue Jul 25 05:00 PM -- 06:30 PM (PDT) @ Exhibit Hall 1 #808
Event URL: https://github.com/AbhijeetiitmVyas/CompetitiveGradientOptim »
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 two players in zero-sum games for its iterative updates. We provide a continuous-time analysis of CGO and its convergence properties while showing that in the continuous limit, previous methods degenerate to their gradient descent ascent (GDA) variants. We further provide a rate of convergence to stationary points in the discrete-time setting. We propose a generalized class of $\alpha$-coherent functions and show that for strictly $\alpha$-coherent functions, CGO ensures convergence to a saddle point. Moreover, we propose optimistic CGO (oCGO), an optimistic variant, for which we show a convergence rate of $O(\frac{1}{n})$ to saddle points for $\alpha$-coherent functions.

Author Information

Abhijeet Vyas (Purdue University)
Abhijeet Vyas

Abhijeet Vyas is a 2nd year Ph.D. student at Purdue University. Before this he was an analog systems engineer at Texas Instruments. He finished his Bachelors in Electrical Engineering and Masters in Data Science from the Indian Institute of Technology Madras during which he won the Caltech SURF award and spent 4 months at Caltech working on Active Vision and Reinforcement Learning.

Brian Bullins (Purdue University)
Kamyar Azizzadenesheli (NVIDIA)

More from the Same Authors