Siqi Zhang

Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization

We study the stochastic first-order oracle complexity of finding $\epsilon$-stationary points of the primal function in smooth nonconvex-strongly-concave minimax optimization. For sufficiently small $\epsilon$, we establish lower bounds of $\Omega(\kappa L\Delta\sigma^2\epsilon^{-4})$ under the bounded-variance assumpt...