Second-Order Min-Max Optimization with Lazy Hessians

This paper studies second-order methods for convex-concave minimax optimization. Monteiro and Svaiter (2012) proposed a method to solve the problem with an optimal iteration complexity of O(ε-3/2) to find an ε-saddle point. However, it is unclear whether the computational complexity, O((N+ d2) d ε-2/3), can be improved. In the above, we follow Doikov et al. (2023) and assume the complexity of obtaining a first-order oracle as N and the complexity of obtaining a second-order oracle as dN. In this paper, we show that the computation cost can be reduced by reusing Hessian across iterations. Our methods take the overall computational complexity of tildeO( (N+d2)(d+ d2/3ε-2/3)), which improves those of previous methods by a factor of d1/3. Furthermore, we generalize our method to strongly-convex-strongly-concave minimax problems and establish the complexity of tildeO((N+d2) (d + d2/3 kappa2/3) ) when the condition number of the problem is kappa, enjoying a similar speedup upon the state-of-the-art method. Numerical experiments on both real and synthetic datasets also verify the efficiency of our method.