  Nonconvex-nonconcave minimax optimization has gained widespread interest over
the last decade. However, most existing works focus on variants of gradient
descent-ascent (GDA) algorithms, which are only applicable to smooth
nonconvex-concave settings. To address this limitation, we propose a novel
algorithm named smoothed proximal linear descent-ascent (smoothed PLDA), which
can effectively handle a broad range of structured nonsmooth
nonconvex-nonconcave minimax problems. Specifically, we consider the setting
where the primal function has a nonsmooth composite structure and the dual
function possesses the Kurdyka-Lojasiewicz (KL) property with exponent $\theta
\in [0,1)$. We introduce a novel convergence analysis framework for smoothed
PLDA, the key components of which are our newly developed nonsmooth primal
error bound and dual error bound. Using this framework, we show that smoothed
PLDA can find both $\epsilon$-game-stationary points and
$\epsilon$-optimization-stationary points of the problems of interest in
$\mathcal{O}(\epsilon^{-2\max\{2\theta,1\}})$ iterations. Furthermore, when
$\theta \in [0,\frac{1}{2}]$, smoothed PLDA achieves the optimal iteration
complexity of $\mathcal{O}(\epsilon^{-2})$. To further demonstrate the
effectiveness and wide applicability of our analysis framework, we show that
certain max-structured problem possesses the KL property with exponent
$\theta=0$ under mild assumptions. As a by-product, we establish
algorithm-independent quantitative relationships among various stationarity
concepts, which may be of independent interest.
