EFFICIENT FIRST ORDER METHOD FOR SADDLE POINT PROBLEMS WITH HIGHER ORDER SMOOTHNESS

This paper studies the complexity of finding approximate stationary points for the smooth nonconvex-strongly-concave (NC-SC) saddle point problem: minx maxy f(x, y). Under the standard first-order smoothness conditions where f is ℓ-smooth in both arguments and μy-strongly concave in y, existing literature shows that the optimal complexity for first-order methods to obtain an ε-stationary point is (Formul Presented)where кy = ℓ/μy is the condition number. However, when Ф(x):= maxy f(x, y) has L2-Lipschitz continuous Hessian in addition, we derive a first-order algorithm with an (Formula Presented) complexity by designing an accelerated proximal point algorithm enhanced with the ``Convex Until Proven Guilty"" technique. Moreover, an improved (Formula presented) lower bound for first-order method is also derived for sufficiently small ε. 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 (Formul Presented), while almost matching the lower bound except for a small (FORMUL Presented) factor.