Escaping Saddle Point Efficiently in Minimax and Bilevel Optimizations

Abstract

Hierarchical optimization (including minimax optimization and bilevel optimization) is attracting significant attentions as it can be broadly applied to many machine learning tasks such as adversarial training, policy optimization, meta-learning and hyperparameter optimization. Recently, many algorithms have been studied to improve the theoretical analysis results of minimax and bilevel optimizations. Among these works, one of the most crucial issues is to escape saddle point and find local minimum, which is also of importance in conventional nonconvex optimization. In this paper, thus, we focus on investigating the methods to achieve second-order stationary point for nonconvex-strongly-concave minimax optimization and nonconvex-strongly-convex bilevel optimization. Specifically, we propose a new algorithm named PRGDA via perturbed stochastic gradient which does not require the computation of second order derivatives. In stochastic nonconvex-strongly-concave minimax optimization, we prove that our algorithm can find an $O(\epsilon, \sqrt{\rho_{\Phi} \epsilon})$ second-order stationary point within gradient complexity of $\tilde{O} (\kappa^3 \epsilon^{-3})$, which matches state-of-the-art to find first-order stationary point. To our best knowledge, our algorithm is the first stochastic algorithm that is guaranteed to obtain the second-order stationary point for nonconvex minimax problems. Besides, in stochastic nonconvex-strongly-convex bilevel optimization, our method also achieves better gradient complexity of $Gc(f, \epsilon) = \tilde{O}(\kappa^3 \epsilon^{-3})$ and $Gc(g, \epsilon) = \tilde{O}(\kappa^7 \epsilon^{-3})$ to find local minimum. Finally, we conduct a numerical experiment to validate the performance of our new method.