Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
This provides theoretical guarantees for optimization in adversarial machine learning, addressing a known divergence issue in vanilla methods, but it is incremental as it focuses on a specific subclass of problems.
The paper tackles the challenge of nonconvex-nonconcave minimax problems, common in applications like GANs, by proving that the alternating gradient descent ascent (AGDA) algorithm converges globally at a linear rate for a subclass of objectives satisfying a two-sided Polyak-Łojasiewicz inequality, with stochastic AGDA achieving a sublinear rate and a variance-reduced algorithm attaining a faster rate for finite-sum structures.
Nonconvex minimax problems appear frequently in emerging machine learning applications, such as generative adversarial networks and adversarial learning. Simple algorithms such as the gradient descent ascent (GDA) are the common practice for solving these nonconvex games and receive lots of empirical success. Yet, it is known that these vanilla GDA algorithms with constant step size can potentially diverge even in the convex setting. In this work, we show that for a subclass of nonconvex-nonconcave objectives satisfying a so-called two-sided Polyak-Łojasiewicz inequality, the alternating gradient descent ascent (AGDA) algorithm converges globally at a linear rate and the stochastic AGDA achieves a sublinear rate. We further develop a variance reduced algorithm that attains a provably faster rate than AGDA when the problem has the finite-sum structure.