5
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Learning in Non-convex Games with an Optimization Oracle

      Preprint
      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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 unstructured setting of prediction with expert advice, Hazan and Koren (2015) established an exponential gap demonstrating that online learning can be significantly harder. Interestingly, this gap is eliminated once we assume a convex structure. A natural question which arises is whether the convexity assumption can be dropped. In this work we answer this question in the affirmative. Namely, we show that online learning is computationally equivalent to statistical learning in the Lipschitz-bounded setting. Notably, most deep neural networks satisfy these assumptions. We prove this result by adapting the ubiquitous Follow-The-Perturbed-Leader paradigm of Kalai and Vempala (2004). 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.

          Related collections

          Most cited references3

          • Record: found
          • Abstract: not found
          • Article: not found

          Online Learning and Online Convex Optimization

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Introduction to Online Convex Optimization

            Elad Hazan (2015)
              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Oracle-Efficient Online Learning and Auction Design

                Bookmark

                Author and article information

                Journal
                16 October 2018
                Article
                1810.07362
                235f68e2-754c-4715-8454-28aefdcca915

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                cs.LG stat.ML

                Machine learning,Artificial intelligence
                Machine learning, Artificial intelligence

                Comments

                Comment on this article