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

• URL: http://arxiv.org/abs/2002.09621v1
• Date: Sat, 22 Feb 2020 04:20:37 GMT
• Title: Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Authors: Junchi Yang, Negar Kiyavash, Niao He
• Abstract summary: Non minimaxewicz problems appear frequently in emerging machine learning applications generative adversarial networks and adversarial learning. GDA algorithms with constant size can potentially diverge even in the convex setting. AGDA algorithm converges globally at a rate that attains a sub rate.
• Score: 39.13924898972611
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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-{\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.

Related papers

• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  Decentralized minimax optimization has been actively studied in the past few years due to its application in a wide range machine learning. This paper develops two novel decentralized minimax optimization algorithms for the non-strongly-nonconcave problem.
  arXiv  Detail & Related papers  (2023-04-24T02:19:39Z)
• A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization [27.07082875330508]
  Non constrained inequality problems can be used to model a number machine learning problems, such as multi-class Neyman oracle. Under such a mild condition of regularity it is difficult to balance reduction alternating value loss and reduction constraint violation. In this paper, we propose a novel primal-dual inequality constrained problems algorithm.
  arXiv  Detail & Related papers  (2022-07-12T16:30:34Z)
• Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learning [12.069630105460766]
  An Alternating Table-descentascent (AltGDA) is an computation optimization algorithm that has been widely used for training in various machine learning applications. In this paper, we develop a single-loop fast computation-of-the-loop gradient-of-the-loop algorithm to solve non minimax optimization problems.
  arXiv  Detail & Related papers  (2021-12-22T04:33:27Z)
• Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Minimax Problems [80.46370778277186]
  Large scale convex-concave minimax problems arise in numerous applications, including game theory, robust training, and training of generative adversarial networks. We develop a communication-efficient distributed extragrad algorithm, LocalAdaSient, with an adaptive learning rate suitable for solving convex-concave minimax problem in the. Server model. We demonstrate its efficacy through several experiments in both the homogeneous and heterogeneous settings.
  arXiv  Detail & Related papers  (2021-06-18T09:42:05Z)
• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems [71.60601421935844]
  Many machine learning problems can be formulated as minimax problems such as Generative Adversarial Networks (GANs) We provide a comprehensive generalization analysis of examples from training gradient methods for minimax problems.
  arXiv  Detail & Related papers  (2021-05-08T22:38:00Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• Train simultaneously, generalize better: Stability of gradient-based minimax learners [12.691047660244331]
  We show a key role in the performance of the trained minimax model under both convex concave and non-concave minimax settings. We discuss several numerical results indicating the role of optimization algorithms in the generalization of learned minimax models.
  arXiv  Detail & Related papers  (2020-10-23T17:44:43Z)
• Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems [10.112779201155005]
  We study the limiting behaviors of three classic minimax algorithms: gradient descent (AGDA), ascentGDA, and the extragradient method (EGM) Numerically, we observe that all limiting behaviors can arise in Generative Adrial Networks (GAN) and are easily demonstrated for a range of GAN problems.
  arXiv  Detail & Related papers  (2020-10-20T21:14:51Z)
• Accelerated Gradient Methods for Sparse Statistical Learning with Nonconvex Penalties [10.913266721195916]
  Nesterov's accelerated simulation (AG) is a popular technique to optimize objective functions two: a convex loss and a penalty function. A recent Nesterov's AG proposal generalizes but has never been applied to statistical learning problems. In this article, we consider the application non AG algorithm to high-dimensional and sparse statistical learning problems.
  arXiv  Detail & Related papers  (2020-09-22T15:37:09Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.