Efficient First Order Method for Saddle Point Problems with Higher Order Smoothness

Abstract

This paper studies the complexity of finding approximate stationary points for the smooth nonconvex-strongly-concave (NC-SC) saddle point problem: ${\min }_x{\max }_{y}f(x,y)$. Under the standard first-order smoothness conditions where $f$ is $\ell$-smooth in both arguments and $\hat{I}{¼}_y$-strongly concave in $y$, existing literature shows that the optimal complexity for first-order methods to obtain an $\hat{I}\mu$-stationary point is $\tilde{O}\left(\sqrt{\hat{I}{º}_y}\ell \hat{I}{\mu }^{-2}\right)$, where $\hat{I}{º}_y=\ell /\hat{I}{¼}_y$ is the condition number. However, when $\hat{I}¦(x):={\max }_{y}f(x,y)$ has $L_2$-Lipschitz continuous Hessian in addition, we derive a first-order algorithm with an $\tilde{O}\left(\sqrt{\hat{I}{º}_y}{\ell }^{1/2}{L}_2^{1/4}\hat{I}{\mu }^{-7/4}\right)$ complexity by designing an accelerated proximal point algorithm enhanced with the "Convex Until Proven Guilty" technique. Moreover, an improved $\hat{I}\text{c◯}\left(\sqrt{\hat{I}{º}_y}{\ell }^{3/7}{L}_2^{2/7}\hat{I}{\mu }^{-12/7}\right)$ lower bound for first-order method is also derived for sufficiently small $\hat{I}\mu$. As a result, given the second-order smoothness of the problem, the complexity of our method improves the state-of-the-art result by a factor of $\tilde{O}\left(\right(\frac{{\ell }^2}{L_2\hat{I}\mu }{)}^{1/4})$, while almost matching the lower bound except for a small $\tilde{O}\left(\right(\frac{{\ell }^2}{L_2\hat{I}\mu }{)}^{1/28})$ factor.