A Scenario Approach to the Robustness of Nonconvex-Nonconcave Minimax Problems
It offers theoretical robustness guarantees for minimax problems, which are important for applications like adversarial training, but the results are incremental as they extend existing scenario optimization techniques.
This paper provides probabilistic robustness guarantees for nonconvex-nonconcave minimax problems using the scenario approach, establishing a bound for ε-stationary points under convex strategy sets and a relaxed bound for global minimax points under nonconvex sets.
This paper investigates probabilistic robustness of nonconvex-nonconcave minimax problems via the scenario approach. Specifically, under convex strategy sets for all players, inspired by recent advances in scenario optimization, we first establish a probabilistic robustness guarantee for an $\varepsilon$-stationary point, overcoming the dependence on the non-degeneracy assumption by proving the monotonicity of the stationary residual in the number of scenarios. Furthermore, in the presence of nonconvex strategy sets, we reveal the fundamental difficulty of obtaining a tight theoretical bound based on this recent framework. Consequently, we establish a relaxed, yet rigorously valid, probabilistic bound for a global minimax point. A numerical experiment corroborates our theoretical findings.