Near-Optimal Higher-Order Oracle Complexity for Convex--Concave Minimax Optimization

Abstract

For smooth convex--concave minimax optimization, the higher-order lower bound of Chen et al. (2026) applies to a restricted tensor-algorithm class with prescribed regularized Taylor-model updates. We establish the same bound for arbitrary adaptive deterministic and randomized algorithms, matching, up to logarithmic factors, the upper bound of Zhang et al. (2026). Fix an integer $p\ge 2$ and let $L_p>0$ bound the Lipschitz constant of the objective's $p$-th derivative on a compact convex product domain of diameter at most $D_Z>0$. Each feasible query returns the objective value and all derivatives through order $p$. For accuracy $\epsilon >0$, set $Q_{\tan }=L_p{D}_Z^p/\epsilon$ for tangent residual and $Q_{\mathrm{gap}}=L_p{D}_Z^{p+1}/\epsilon$ for saddle gap. Let $T_E^{\det }(\epsilon )$ and $T_E^{\mathrm{rand}}(\epsilon )$ denote the high-dimensional minimax query complexities for criterion $E\in \{\tan ,\mathrm{gap}\}$, with randomized success probability at least $2/3$ on every instance. Our lower bounds and the existing upper bound give $c_p{Q}_E^{2/(3p-1)}\le T_E^{\mathrm{rand}}(\epsilon )\le T_E^{\det }(\epsilon )\le C_p{Q}_E^{2/(3p-1)}[1+\log (3+Q_E){]}^{6(p-1)}$ for sufficiently large $Q_E$, where $c_p,C_p>0$ depend only on $p$. Thus the same accuracy exponent holds beyond tensor update rules, even for randomized queries and arbitrary feasible outputs. The proof constructs a scalar convex--concave chain with exactly flat gates that hide complete derivative information. Direct product-domain error witnesses and adaptive transcript arguments establish the lower bounds for both criteria.