Alon Gonen (Theory Seminar)

Abstract: We consider adversarial online learning in a non-convex setting under the assumption that the learner has an access to an offline optimization oracle.  In the most general setting of prediction with expert advice, [Hazan & Koren, 2016] established an exponential gap demonstrating that online learning can be significantly harder. In this paper we show that by slightly strengthening the oracle model, the online and the batch model become computationally equivalent. In fact, our result holds for any Lipschitz and bounded (but not necessarily convex) function.  We prove our result  by adapting the powerful  Follow-The-Perturbed-Leader meta-algorithm of [Kalai & Vempala, 2004] to the non-convex setting. 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.

Joint work with Elad Hazan (Princeton university).