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: minxmaxyf(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 tildeObig(√kappayℓε-2big), where kappay=ℓ/μy is the condition number. However, when Phi(x):=maxy f(x,y) has L2-Lipschitz continuous Hessian in addition, we derive a first-order algorithm with an tildeObig(√kappayℓ1/2L21/4ε-7/4big) complexity by designing an accelerated proximal point algorithm enhanced with the "Convex Until Proven Guilty" technique. Moreover, an improved Omegabig(√kappayℓ3/7L22/7ε-12/7big) 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 tildeObig(big(fracℓ2L2εbig)1/4big), while almost matching the lower bound except for a small tildeObig(big(fracℓ2L2εbig)1/28big) factor.