Solving Convex-Concave Problems with tildeO(ε-4/(3p+1)) pth-Order Oracle Complexity

When the objective has Lipschitz continuous pth-order derivatives, it is known that convex-concave minimax problems can be solved with O(ε-2/(p+1)) pth-order oracle calls. This complexity upper bound was speculated to be optimal as it is achieved by a natural generalization of the optimal first-order method. In this work, we show an improved upper bound of tildeO(ε-4/(3p+1)) by applying the Monteiro-Svaiter acceleration. We also establish a lower complexity bound of Omega(ε-2/(3p-1)), suggesting a gap still exists for p ≥ 2.