Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems

By Junchi Yang, Negar Kiyavash, Niao He. 2020

87 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “…for the analysis of stochastic algorithms, papers assume either bounded operators [Nemirovski et al., 2009, Abernethy et al., 2021] or bounded variance [Juditsky et al., 2011, Yang et al., 2020, Lin et al., 2020a, Luo et al., 2020, Tran Dinh et al., 2020] and growth condition [Lin et al., 2020b].”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, background): “In concurrent work, Yang et al. (2020) provide global convergence guarantees for stochastic alternate gradient descent-ascent (and its variance reduction variant) for a subclass of nonconvex-nonconcave objectives satisfying a so-called two-sided Polyak-Lojasiewicz inequality, but this does not…”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, methodology): “Compare this to the Polyak-Łojasiewicz condition (see, e.g., [41,47]), which gives the opposite inequality, namely, that f ( x , y ∗ ) − f ( x ∗ , y ∗ ) is bounded above by a multiple of k∇ f ( x , y ∗ ) 2 p ∗ .”
Hybrid Variance-Reduced SGD Algorithms For Minimax Problems with Nonconvex-Linear Function (2020, methodology): “Another subgradient-based method was recently proposed in [40] based on a two-side PL condition.”