Journal article
First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
Journal of machine learning research, Vol.22, pp.1-34
01/01/2021
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.
Details
- Title: Subtitle
- First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
- Creators
- Mingrui Liu - Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USAHassan Rafique - Univ Iowa, Dept Math, Iowa City, IA 52242 USAQihang Lin - Univ Iowa, Business Analyt Dept, Iowa City, IA 52242 USATianbao Yang - Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USA
- Resource Type
- Journal article
- Publication Details
- Journal of machine learning research, Vol.22, pp.1-34
- Publisher
- Microtome Publ
- ISSN
- 1532-4435
- eISSN
- 1533-7928
- Number of pages
- 34
- Grant note
- 1933212; 1844403 / NSF CAREER Award; National Science Foundation (NSF); NSF - Office of the Director (OD) 1933212 / NSF; National Science Foundation (NSF)
- Language
- English
- Date published
- 01/01/2021
- Academic Unit
- Computer Science; Business Analytics
- Record Identifier
- 9984259428402771
Metrics
16 Record Views