Fast Convergence of Non-Convex Strongly-Concave Min-Max Problems with PL Condition
Zhishuai Guo, Yan Yan, Zhuoning Yuan, Tianbao Yang; 24(148):1−63, 2023.
Abstract
This paper presents a study on stochastic methods for efficiently solving smooth non-convex strongly-concave min-max problems. These problems have gained attention due to their potential applications in deep learning, such as deep AUC maximization and distributionally robust optimization. However, existing algorithms for solving these problems are often slow in practice and their convergence analysis is centered around reaching nearly stationary points. In this paper, we propose a new approach that leverages the Polyak-Lojasiewicz (PL) condition to design faster stochastic algorithms with stronger convergence guarantees. While PL condition has been used in the design of stochastic minimization algorithms, its applications for non-convex min-max optimization are limited. Our proposed framework is based on proximal stage-based methods and incorporates various well-known stochastic updates. We establish fast convergence in terms of both the primal objective gap and the duality gap. Our analysis introduces a novel Lyapunov function that consists of the primal objective gap and the duality gap of a regularized function. Additionally, our results are more comprehensive and offer improved rates with better dependence on the condition number under different assumptions. Experimental results on both deep and non-deep learning scenarios demonstrate the effectiveness of our methods.
[abs]