Solving Convex-Concave Problems with $\tilde{\mathcal{O}}(\hat{I}{\mu }^{-4/(3p+1)})$ $p$th-Order Oracle Complexity

Abstract

When the objective has Lipschitz continuous $p$th-order derivatives, it is known that convex-concave minimax problems can be solved with $\mathcal{O}(\hat{I}{\mu }^{-2/(p+1)})$ $p$th-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 $\tilde{\mathcal{O}}(\hat{I}{\mu }^{-4/(3p+1)})$ by applying the Monteiro-Svaiter acceleration. We also establish a lower complexity bound of $\hat{I}\text{c◯}(\hat{I}{\mu }^{-2/(3p-1)})$, suggesting a gap still exists for $p\ge 2$.

A preliminary version [arXiv:2506.08362] of this paper, with a subset of the results that are presented here, was published at COLT 2025;