提出新方法解决非凸非凹极小极大问题，理论更贴近实际场景。
A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Lojasiewicz condition
- 基于局部KL条件设计改进的近似邻近梯度算法
- 在温和假设下实现计算近似驻点的复杂度保证
- 适用于实际中常见但传统方法难处理的复杂优化场景
我们研究一类非凸非凹极小极大问题，其中内层最大化问题满足随外层变量变化的局部Kurdyka-Lojasiewicz（KL）条件。与文献中常见的全局KL或Polyak-Lojasiewicz（PL）条件相比，该局部KL条件更具普适性且更贴近实际应用，但同时也带来新的分析挑战：随着优化过程趋近驻点，满足KL条件的区域可能缩小，导致优化景观更加复杂甚至病态。为此，我们证明了关联的最大值函数具有局部广义Hölder光滑性。利用这一关键性质，我们设计了一种求解极小极大问题的不精确邻近梯度方法，其中最大值函数的不精确梯度通过针对具KL结构的子问题应用邻近梯度法获得。在温和假设下，我们建立了计算极小极大问题近似驻点的复杂度保证。
原文摘要 · Abstract (English)
We study a class of nonconvex-nonconcave minimax problems in which the inner maximization problem satisfies a local Kurdyka-Lojasiewicz (KL) condition that may vary with the outer minimization variable. In contrast to the global KL or Polyak-Lojasiewicz (PL) conditions commonly assumed in the literature -- which are significantly stronger and often too restrictive in practice -- this local KL condition accommodates a broader range of practical scenarios. However, it also introduces new analytical challenges. In particular, as an optimization algorithm progresses toward a stationary point of the problem, the region over which the KL condition holds may shrink, resulting in a more intricate and potentially ill-conditioned landscape. To address this challenge, we show that the associated maximal function is locally generalized Hölder smooth. Leveraging this key property, we develop an inexact proximal gradient method for solving the minimax problem, where the inexact gradient of the maximal function is computed by applying a proximal gradient method to a KL-structured subproblem. Under mild assumptions, we establish complexity guarantees for computing an approximate stationary point of the minimax problem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。