Journal article
Weakly-convex-concave min-max optimization: provable algorithms and applications in machine learning
Optimization methods & software, Vol.37(3), pp.1087-1121
05/04/2022
DOI: 10.1080/10556788.2021.1895152
Abstract
Min-max problems have broad applications in machine learning, including learning with non-decomposable loss and learning with robustness to data distribution. Convex-concave min-max problem is an active topic of research with efficient algorithms and sound theoretical foundations developed. However, it remains a challenge to design provably efficient algorithms for non-convex min-max problems with or without smoothness. In this paper, we study a family of non-convex min-max problems, whose objective function is weakly convex in the variables of minimization and is concave in the variables of maximization. We propose a proximally guided stochastic subgradient method and a proximally guided stochastic variance-reduced method for the non-smooth and smooth instances, respectively, in this family of problems. We analyse the time complexities of the proposed methods for finding a nearly stationary point of the outer minimization problem corresponding to the min-max problem.
Details
- Title: Subtitle
- Weakly-convex-concave min-max optimization: provable algorithms and applications in machine learning
- Creators
- Hassan Rafique - University of IndianapolisMingrui Liu - University of IowaQihang Lin - University of IowaTianbao Yang - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Optimization methods & software, Vol.37(3), pp.1087-1121
- Publisher
- Taylor & Francis
- DOI
- 10.1080/10556788.2021.1895152
- ISSN
- 1055-6788
- eISSN
- 1029-4937
- Grant note
- name: NSF, award: 1933212, 1844403
- Language
- English
- Date published
- 05/04/2022
- Academic Unit
- Business Analytics; Computer Science
- Record Identifier
- 9984380376802771
Metrics
5 Record Views