Learning in Non-convex Games with an Optimization Oracle
Abstract
We consider online learning in an adversarial, non-convex setting under the assumption that the
learner has an access to an offline optimization oracle. In the general setting of prediction with expert
advice, [11] established that in the optimization-oracle model, online learning requires exponentially
more computation than statistical learning. In this paper we show that by slightly strengthening the
oracle model, the online and the statistical learning models become computationally equivalent. Our
result holds for any Lipschitz and bounded (but not necessarily convex) function. As an application we
demonstrate how the offline oracle enables efficient computation of an equilibrium in non-convex games, that include GAN (generative adversarial networks) as a special case.
learner has an access to an offline optimization oracle. In the general setting of prediction with expert
advice, [11] established that in the optimization-oracle model, online learning requires exponentially
more computation than statistical learning. In this paper we show that by slightly strengthening the
oracle model, the online and the statistical learning models become computationally equivalent. Our
result holds for any Lipschitz and bounded (but not necessarily convex) function. As an application we
demonstrate how the offline oracle enables efficient computation of an equilibrium in non-convex games, that include GAN (generative adversarial networks) as a special case.
Research Areas
