2019-06-25-agarwal19a.md

abstract	section	title	layout	series	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	publisher	container-title	volume	genre	issued	pdf	extras
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 and Koren 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.	contributed	Learning in Non-convex Games with an Optimization Oracle	inproceedings	Proceedings of Machine Learning Research	agarwal19a	0	Learning in Non-convex Games with an Optimization Oracle	18	29	18-29	18	false	Agarwal, Naman and Gonen, Alon and Hazan, Elad	given family Naman Agarwal given family Alon Gonen given family Elad Hazan	2019-06-25		PMLR	Proceedings of the Thirty-Second Conference on Learning Theory	99	inproceedings	date-parts 2019 6 25	http://proceedings.mlr.press/v99/agarwal19a/agarwal19a.pdf