Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning
This work addresses a key bottleneck in machine learning applications like robust learning, but it is incremental as it builds on existing convex-concave frameworks.
The authors tackled the challenge of designing provably efficient algorithms for non-convex min-max problems by focusing on weakly-convex concave objectives, proposing proximally guided stochastic methods for both non-smooth and smooth instances, and analyzing their time complexities for finding nearly stationary points.
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 analyze the time complexities of the proposed methods for finding a nearly stationary point of the outer minimization problem corresponding to the min-max problem.