First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems

Abstract

In this paper, we consider first-order convergence theory and algorithms for solving a class of non-convex non-concave min-max saddle-point problems, whose objective function is weakly convex in the variables of minimization and weakly concave in the variables of maximization. It has many important applications in machine learning including training Generative Adversarial Nets (GANs). We propose an algorithmic framework motivated by the inexact proximal point method, where the weakly monotone variational inequality (VI) corresponding to the original min-max problem is solved through approximately solving a sequence of strongly monotone VIs constructed by adding a strongly monotone mapping to the original gradient mapping. We prove first-order convergence to a nearly stationary solution of the original min-max problem of the generic algorithmic framework and establish different rates by employing different algorithms for solving each strongly monotone VI. Experiments verify the convergence theory and also demonstrate the effectiveness of the proposed methods on training GANs.

Accepted by Journal of Machine Learning Research (JMLR)

References in corpus (13)

• Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)
• On the Convergence of Adam and Beyond
• Certifying Some Distributional Robustness with Principled Adversarial Training
• A Variational Inequality Perspective on Generative Adversarial Networks
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization
• Efficient Algorithms for Smooth Minimax Optimization
• Learning with Non-Convex Truncated Losses by SGD
• Universal Stagewise Learning for Non-Convex Problems with Convergence on Averaged Solutions
• Robust Optimization over Multiple Domains

Cited by in corpus (10)

• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• A Decentralized Proximal Point-type Method for Saddle Point Problems
• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems
• A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization
• Primal-Dual Distributed Temporal Difference Learning
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods