Role of Interaction in Competitive Optimization

Competitive optimization is needed for many ML problems such as training GANs, robust reinforcement learning, and adversarial learning. Standard approaches to competitive optimization involve each agent independently optimizing their objective functions using SGD or other gradient-based approaches. However, they suffer from oscillations and instability, since the optimization does not account for interaction among the players. We introduce competitive gradient descent (CGD) that explicitly incorporates interaction by solving for Nash equilibrium of a local game. We extend CGD to competitive mirror descent (CMD) for solving conically constrained competitive problems by using the dual geometry induced by a Bregman divergence. We demonstrate the effectiveness of our approach for training GANs and solving constrained reinforcement learning (RL) problems. We also derive a competitive policy optimization method to train RL agents in competitive games. Finally, we provide a novel perspective on training GANs by pointing out the "GAN-dilemma" a fundamental flaw of the divergence-minimization perspective on GANs. Instead, we argue that an implicit competitive regularization due to simultaneous training methods, such as CGD, is a crucial mechanism behind GAN performance.