  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, Hazan et al. (2016)
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.
