Solving Convex-Concave Problems with 𝒪(ϵ^-4/7) Second-Order Oracle Complexity

Abstract

Previous algorithms can solve convex-concave minimax problems min_x ∈𝒳max_y ∈𝒴 f(x,y) with (ϵ^-2/3) second-order oracle calls using Newton-type methods. This result has been speculated to be optimal because the upper bound is achieved by a natural generalization of the optimal first-order method. In this work, we show an improved upper bound of (ϵ^-4/7) by generalizing the optimal second-order method for convex optimization to solve the convex-concave minimax problem. We further apply a similar technique to lazy Hessian algorithms and show that our proposed algorithm can also be seen as a second-order “Catalyst” framework (Lin et al., JMLR 2018) that could accelerate any globally convergent algorithms for solving minimax problems.