Efficient Regret Minimization in Non-Convex Games
This work addresses computational challenges in non-convex game theory, providing an efficient solution for regret minimization, though it appears incremental as it builds on existing frameworks with a new regret definition.
The paper tackles the problem of regret minimization in repeated games with non-convex loss functions, where standard regret is computationally intractable, by defining a new regret notion that allows efficient optimization and achieves optimal regret with gradient-based methods, guaranteeing convergence to equilibrium.
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.