Title: Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Algorithm Design and Convergence Analysis
Abstract: Nonsmooth, nonconvex-nonconcave minimax optimization has gained widespread interest in recent years in machine learning and data science. However, much of the existing work focuses on a variant of the gradient descent-ascent (GDA) algorithm, which exhibits several limitations: (1) They are only applicable to smooth problems, where gradient information is available. (2) They may not converge globally, and they may suffer from limit cycles. (3) No single algorithm can be universally applied to all minimax optimization problems, such as nonconvex-concave and convex-nonconcave minimax settings.
In this talk, we will tackle these challenges for a class of structured nonsmooth, nonconvex-nonconcave minimax optimization problems. The main difficulty in algorithmic design for minimax optimization is balancing the primal decrease and dual increase in an efficient way. To overcome this difficulty, we develop a novel primal-dual error bound that serves as the foundation for both convergence analysis and algorithmic design. This gives rise to a new algorithm design principle known as optimal primal-dual balancing. Following this principle, we develop a single algorithm, doubly smoothed (prox-linear)/ gradient descent ascent, which universally works for all minimax optimization problems. Our algorithm finds an $\epsilon$-stationary point in $O(epsilon^-4)$ iterations. If additional regularity is assumed (weaker than standard assumptions imposed in the literature), we obtain sharper, even optimal, iteration complexity results. We showcase the effectiveness of our algorithm in getting rid of limit cycles in challenging nonconvex-nonconcave minimax optimization problems.
Bio: Currently, Jiajin is a postdoctoral researcher in the Department of Management Science and Engineering (MS&E) at Stanford University, where she is working with Prof. Jose Blanchet and Prof. Yinyu Ye. Previously, Jiajin received her Ph.D. degree in the Department of Systems Engineering and Engineering Management from the Chinese University of Hong Kong (CUHK) in 2021, where she is advised by Prof. Anthony Man-Cho So. From August 2020 to March 2021, Jiajin worked as a visiting Ph.D. student in the Geometric Data Processing Group at the Massachusetts Institute of Technology (MIT) under the guidance of Prof. Justin Solomon.
