Timezone: »

 
Poster
Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
Haochuan Li · Yi Tian · Jingzhao Zhang · Ali Jadbabaie

Wed Dec 08 04:30 PM -- 06:00 PM (PST) @
in Poster Session 4 »
We provide a first-order oracle complexity lower bound for finding stationary points of min-max optimization problems where the objective function is smooth, nonconvex in the minimization variable, and strongly concave in the maximization variable. We establish a lower bound of $\Omega\left(\sqrt{\kappa}\epsilon^{-2}\right)$ for deterministic oracles, where $\epsilon$ defines the level of approximate stationarity and $\kappa$ is the condition number. Our lower bound matches the best existing upper bound in the $\epsilon$ and $\kappa$ dependence up to logarithmic factors. For stochastic oracles, we provide a lower bound of $\Omega\left(\sqrt{\kappa}\epsilon^{-2} + \kappa^{1/3}\epsilon^{-4}\right)$. It suggests that there is a gap between the best existing upper bound $\mathcal{O}(\kappa^3 \epsilon^{-4})$ and our lower bound in the condition number dependence.
Keywords: Optimization

Author Information

Haochuan Li (MIT)
Yi Tian (MIT)
Jingzhao Zhang (MIT)
Ali Jadbabaie (MIT)

More from the Same Authors