Weakly-convex–concave min–max optimization: provable algorithms and applications in machine learning. (4th May 2022)

• Record Type: Journal Article
• Authors: Rafique, Hassan; Liu, Mingrui; Lin, Qihang; Yang, Tianbao
• Is Part Of: Optimization methods and software. Volume 37:Number 3(2022)
• Page Start: 1087
• Page End: 1121
• Publication Date: 2022-05-04
• Subjects: Min–max optimization -- non-smooth optimization -- stochastic optimization -- non-convex optimization; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2021.1895152
• Languages: English
• ISSNs: 1055-6788

Abstract

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.