Learning in Non-convex Games with an Optimization Oracle
Learning in Non-convex Games with an Optimization Oracle
复制标题
DOI：
--
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Alon Gonen;Elad Hazan
中科院分区：
文献类型：
--
作者：
Alon Gonen;Elad Hazan
我们考虑在线学习在一个对抗的，非凸的设置下，假设学习者可以访问离线优化oracle。在专家建议预测的一般设置下，Hazan et al.（2016）建立了在优化-oracle模型中，在线学习所需的计算量比统计学习大得多。在本文中，我们证明了通过稍微加强oracle模型，在线学习模型和统计学习模型在计算上是相等的。我们的结果适用于任何Lipschitz函数和有界（但不一定是凸）函数。作为一个应用，我们展示了离线oracle如何在非凸博弈中有效地计算均衡，其中包括GAN（生成对抗网络）作为一个特例。
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.