2021-03-18-diakonikolas21a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization	The use of min-max optimization in the adversarial training of deep neural network classifiers, and the training of generative adversarial networks has motivated the study of nonconvex-nonconcave optimization objectives, which frequently arise in these applications. Unfortunately, recent results have established that even approximate first-order stationary points of such objectives are intractable, even under smoothness conditions, motivating the study of min-max objectives with additional structure. We introduce a new class of structured nonconvex-nonconcave min-max optimization problems, proposing a generalization of the extragradient algorithm which provably converges to a stationary point. The algorithm applies not only to Euclidean spaces, but also to general $\ell_p$-normed finite-dimensional real vector spaces. We also discuss its stability under stochastic oracles and provide bounds on its sample complexity. Our iteration complexity and sample complexity bounds either match or improve the best known bounds for the same or less general nonconvex-nonconcave settings, such as those that satisfy variational coherence or in which a weak solution to the associated variational inequality problem is assumed to exist.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	diakonikolas21a	0	Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization	2746	2754	2746-2754	2746	false	Diakonikolas, Jelena and Daskalakis, Constantinos and Jordan, Michael	given family Jelena Diakonikolas given family Constantinos Daskalakis given family Michael I. Jordan	2021-03-18		Proceedings of The 24th International Conference on Artificial Intelligence and Statistics	130	inproceedings	date-parts 2021 3 18	http://proceedings.mlr.press/v130/diakonikolas21a/diakonikolas21a.pdf	label link Supplementary PDF http://proceedings.mlr.press/v130/diakonikolas21a/diakonikolas21a-supp.pdf