Timezone: »

 
Uniform Convergence and Generalization for Nonconvex Stochastic Minimax Problems
Siqi Zhang · Yifan Hu · Liang Zhang · Niao He

@
in OPT 2022: Optimization for Machine Learning »
Event URL: https://openreview.net/forum?id=_AHlSVY2ebg »
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 result measured by the first-order stationarity in stochastic minimax optimization literature.

Author Information

Siqi Zhang (Johns Hopkins University)
Yifan Hu (EPFL)
Liang Zhang (Department of Computer Science, ETHZ - ETH Zurich)
Niao He (ETH Zurich)

More from the Same Authors