Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Algorithm Design and Convergence Analysis

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.
Date
Location
TROY 2012
Speaker: Jiajin Li from Stanford University
Back to top