<p>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 problem possesses the Kurdyka–Łojasiewicz (KŁ) property with exponent <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\theta \in [0,1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>θ</mi> <mo>∈</mo> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation>-game-stationary points and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation>-optimization-stationary points of the problems of interest in <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\mathcal {O}(\epsilon ^{-2\max \{2\theta ,1\}})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>ϵ</mi> <mrow> <mo>-</mo> <mn>2</mn> <mo movablelimits="true">max</mo> <mo stretchy="false">{</mo> <mn>2</mn> <mi>θ</mi> <mo>,</mo> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> iterations. Furthermore, when <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\theta \in [0,\frac{1}{2}]$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>θ</mi> <mo>∈</mo> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>, smoothed PLDA achieves the optimal iteration complexity of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\mathcal {O}(\epsilon ^{-2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>ϵ</mi> <mrow> <mo>-</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. To further demonstrate the effectiveness and wide applicability of our analysis framework, we show that certain max-structured problem possesses the KŁ property with exponent <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\theta =0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>θ</mi> <mo>=</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> under mild assumptions. As a by-product, we establish algorithm-independent quantitative relationships among various stationarity concepts, which may be of independent interest.</p>

Nonsmooth nonconvex–nonconcave minimax optimization: Primal–dual balancing and iteration complexity analysis

期刊论文
发表日期：

2025年3月5日

查看全文

Jiajin Li,
Linglingzhi Zhu,
Anthony Man-Cho So

摘要

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 problem possesses the Kurdyka–Łojasiewicz (KŁ) property with exponent $\theta \in [0,1)$ $θ \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\}})$ $O (ϵ^{- 2 max {2 θ, 1}})$ iterations. Furthermore, when $\theta \in [0,\frac{1}{2}]$ $θ \in [0, \frac{1}{2}]$ , smoothed PLDA achieves the optimal iteration complexity of $\mathcal {O}(\epsilon ^{-2})$ $O (ϵ^{- 2})$ . To further demonstrate the effectiveness and wide applicability of our analysis framework, we show that certain max-structured problem possesses the KŁ property with exponent $\theta =0$ $θ = 0$ under mild assumptions. As a by-product, we establish algorithm-independent quantitative relationships among various stationarity concepts, which may be of independent interest.