Timezone: »
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 stepsize 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-{\L}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.
Author Information
Junchi Yang (University of Illinois)
Negar Kiyavash (École Polytechnique Fédérale de Lausanne)
Niao He (ETH Zurich)
More from the Same Authors
-
2022 Poster: Sharp Analysis of Stochastic Optimization under Global Kurdyka-Lojasiewicz Inequality »
Jalal Etesami · Ilyas Fatkhullin · Niao He · Negar Kiyavash -
2022 Poster: Causal Discovery in Linear Latent Variable Models Subject to Measurement Error »
Yuqin Yang · AmirEmad Ghassami · Mohamed Nafea · Negar Kiyavash · Kun Zhang · Ilya Shpitser -
2022 Poster: Stochastic Second-Order Methods Provably Beat SGD For Gradient-Dominated Functions »
Mohammadsaeed Masiha · Saber Salehkaleybar · Niao He · Negar Kiyavash · Patrick Thiran -
2021 Poster: Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias »
Sina Akbari · Ehsan Mokhtarian · AmirEmad Ghassami · Negar Kiyavash -
2021 Poster: On the Bias-Variance-Cost Tradeoff of Stochastic Optimization »
Yifan Hu · Xin Chen · Niao He -
2020 Poster: Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning »
Yifan Hu · Siqi Zhang · Xin Chen · Niao He -
2020 Poster: A Catalyst Framework for Minimax Optimization »
Junchi Yang · Siqi Zhang · Negar Kiyavash · Niao He -
2020 Poster: A Unified Switching System Perspective and Convergence Analysis of Q-Learning Algorithms »
Donghwan Lee · Niao He -
2020 Poster: The Devil is in the Detail: A Framework for Macroscopic Prediction via Microscopic Models »
Yingxiang Yang · Negar Kiyavash · Le Song · Niao He -
2020 Poster: The Mean-Squared Error of Double Q-Learning »
Wentao Weng · Harsh Gupta · Niao He · Lei Ying · R. Srikant -
2020 Spotlight: The Devil is in the Detail: A Framework for Macroscopic Prediction via Microscopic Models »
Yingxiang Yang · Negar Kiyavash · Le Song · Niao He