Efficient Regret Minimization in Non-Convex Games

Abstract

We consider regret minimization in repeated games with non-convex loss functions. Minimizing the standard notion of regret is computationally intractable. Thus, we define a natural notion of regret which permits efficient optimization and generalizes offline guarantees for convergence to an approximate local optimum. We give gradient-based methods that achieve optimal regret, which in turn guarantee convergence to equilibrium in this framework.

Published as a conference paper at ICML 2017

References in corpus (2)

• Connecting Generative Adversarial Networks and Actor-Critic Methods
• Second-Order Stochastic Optimization for Machine Learning in Linear Time

Cited by in corpus (16)

• A Variational Inequality Perspective on Generative Adversarial Networks
• Stabilizing Generative Adversarial Networks: A Survey
• Online Continuous Submodular Maximization
• Convergence Problems with Generative Adversarial Networks (GANs)
• Second-order Online Nonconvex Optimization
• GANGs: Generative Adversarial Network Games
• Regret minimization in stochastic non-convex learning via a proximal-gradient approach
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Online non-convex optimization with imperfect feedback
• Learning in Non-convex Games with an Optimization Oracle
• A Local Regret in Nonconvex Online Learning
• SGLB: Stochastic Gradient Langevin Boosting
• Follow the Neurally-Perturbed Leader for Adversarial Training
• Multi-task Federated Edge Learning (MtFEEL) in Wireless Networks
• Dynamic Regret Analysis for Online Meta-Learning
• Time-Smoothed Gradients for Online Forecasting