论文标题
具有耦合线性约束的迭代最小游戏
Iterative Minimax Games with Coupled Linear Constraints
论文作者
论文摘要
由于与对抗性培训方案的基本联系，对非凸界最小游戏的研究已经在机器学习和决策科学社区中获得了巨大的动力。这项工作开发了一种原始的双偶近端梯度（PDAPG）算法框架，用于解决迭代的minimax游戏，其特征是非光滑的nonconvex目标，但要受到耦合线性约束的目标。我们建立了严格的融合保证，可确保非convex巧妙的凹和concave游戏配置，这表明PDAPG在$ \ varepsilon $ stational $ stational of $ \ mathcal {o \ mathcal {o} \ left（\ varepsilon ^varepsilon ^{ - 2} \ right）中，$ \ VAREPSILON $ - 固定解决方案$ \ MATHCAL {O} \ left（\ Varepsilon ^{ - 4} \ right）$ tererations $ tererations for凹面方案。我们的分析为这类受约束的最小游戏提供了第一个已知的迭代复杂性界限，尤其是解决了耦合线性约束的关键挑战，这些约束诱导策略变量之间固有的相互依赖性。提出的游戏理论框架通过同时处理非平滑组件和协调约束结构来通过交替的二线更新来推进现有的解决方案方法。
The study of nonconvex minimax games has gained significant momentum in machine learning and decision science communities due to their fundamental connections to adversarial training scenarios. This work develops a primal-dual alternating proximal gradient (PDAPG) algorithm framework for resolving iterative minimax games featuring nonsmooth nonconvex objectives subject to coupled linear constraints. We establish rigorous convergence guarantees for both nonconvex-strongly concave and nonconvex-concave game configurations, demonstrating that PDAPG achieves an $\varepsilon$-stationary solution within $\mathcal{O}\left( \varepsilon ^{-2} \right)$ iterations for strongly concave settings and $\mathcal{O}\left( \varepsilon ^{-4} \right)$ iterations for concave scenarios. Our analysis provides the first known iteration complexity bounds for this class of constrained minimax games, particularly addressing the critical challenge of coupled linear constraints that induce inherent interdependencies among strategy variables. The proposed game-theoretic framework advances existing solution methodologies by simultaneously handling nonsmooth components and coordinated constraint structures through alternating primal-dual updates.
