Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity

arXiv2112.05604MaRDI QIDQ6385327

Author name not available (Why is that?)

Publication date: 10 December 2021

Abstract: Gradient descent ascent (GDA), the simplest single-loop algorithm for nonconvex minimax optimization, is widely used in practical applications such as generative adversarial networks (GANs) and adversarial training. Albeit its desirable simplicity, recent work shows inferior convergence rates of GDA in theory even assuming strong concavity of the objective on one side. This paper establishes new convergence results for two alternative single-loop algorithms -- alternating GDA and smoothed GDA -- under the mild assumption that the objective satisfies the Polyak-Lojasiewicz (PL) condition about one variable. We prove that, to find an $epsilon$-stationary point, (i) alternating GDA and its stochastic variant (without mini batch) respectively require $O(kapp{a}^{2}epsilo{n}^{-2})$ and $O(kapp{a}^{4}epsilo{n}^{-4})$ iterations, while (ii) smoothed GDA and its stochastic variant (without mini batch) respectively require $O(kappaepsilo{n}^{-2})$ and $O(kapp{a}^{2}epsilo{n}^{-4})$ iterations. The latter greatly improves over the vanilla GDA and gives the hitherto best known complexity results among single-loop algorithms under similar settings. We further showcase the empirical efficiency of these algorithms in training GANs and robust nonlinear regression.

Has companion code repository: https://github.com/aorvieto/ncpl

This page was built for publication: Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6385327)