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

arXiv: https://arxiv.org/abs/2604.19462 · HTML: https://mlsanity.com/paper/2604.19462/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Apr 2026.

## Built on by (most cited first, 1 of 1)

- [Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems](https://mlsanity.com/paper/2609.30212/) (2026)

## Abstract (arXiv)

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.