Iterative Minimax Games with Coupled Linear Constraints
This addresses constrained minimax optimization problems in machine learning and decision science, particularly for adversarial training scenarios with coupled constraints, representing an incremental advancement in solution methodologies.
The paper tackles iterative minimax games with nonsmooth nonconvex objectives and coupled linear constraints by developing a primal-dual alternating proximal gradient (PDAPG) algorithm, achieving convergence guarantees of O(ε⁻²) iterations for strongly concave settings and O(ε⁻⁴) for concave scenarios.
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.