Uniform Convergence and Generalization for Nonconvex Stochastic Minimax Problems
This paper studies the uniform convergence and generalization bounds for
nonconvex-(strongly)-concave (NC-SC/NC-C) stochastic minimax optimization. We
first establish the uniform convergence between the empirical minimax problem
and the population minimax problem and show the
$\tilde{\mathcal{O}}(d\kappa^2\epsilon^{-2})$ and
$\tilde{\mathcal{O}}(d\epsilon^{-4})$ sample complexities respectively for the
NC-SC and NC-C settings, where $d$ is the dimension number and $\kappa$ is the
condition number. To the best of our knowledge, this is the first uniform
convergence measured by the first-order stationarity in stochastic minimax
optimization. Based on the uniform convergence, we shed light on the sample and
gradient complexities required for finding an approximate stationary point for
stochastic minimax optimization in the NC-SC and NC-C settings.