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≥ 2 and let Lp>0 bound the Lipschitz constant of the objective's p-th derivative on a compact convex product domain of diameter at most DZ>0. Each feasible query returns the objective value and all derivatives through order p. For accuracy ε>0, set Qtan=LpDZp/ε for tangent residual and Qgap=LpDZp+1/ε for saddle gap. Let TEdet(ε) and TErand(ε) denote the high-dimensional minimax query complexities for criterion E∈{tan,gap}, with randomized success probability at least 2/3 on every instance. Our lower bounds and the existing upper bound give cpQE2/(3p−1)≤ TErand(ε)≤ TEdet(ε)≤ CpQE2/(3p−1)[1+log(3+QE)]6(p−1) for sufficiently large QE, where cp,Cp>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.
Related
- Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
- Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization
- Sharp Fresh-Gradient Complexity of Nonconvex-Strongly-Concave Minimax Optimization
- Matching Full-Hessian Oracle Complexity for Nonconvex--Strongly-Concave Minimax Optimization
- Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization
BibTeX
@misc{li2026nearoptimal,
title = {{Near-Optimal Higher-Order Oracle Complexity for Convex--Concave Minimax Optimization}},
author = {Yanyi Li and Haihan Zhang and Chenheng Zhang and Wendao Wu and Chunyuan Zheng and Cong Fang and Haoxuan Li and Zhouchen Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.28246},
eprint = {2609.28246},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28246},
}
RIS
TY - UNPB
TI - Near-Optimal Higher-Order Oracle Complexity for Convex--Concave Minimax Optimization
AU - Yanyi Li
AU - Haihan Zhang
AU - Chenheng Zhang
AU - Wendao Wu
AU - Chunyuan Zheng
AU - Cong Fang
AU - Haoxuan Li
AU - Zhouchen Lin
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2609.28246
UR - https://arxiv.org/abs/2609.28246
AB - 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≥ 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 ε>0, set Q_tan=L_pD_Z^p/ε for tangent residual and Q_gap=L_pD_Z^p+1/ε for saddle gap. Let T_E^det(ε) and T_E^rand(ε) denote the high-dimensional minimax query complexities for criterion E∈{tan,gap}, with randomized success probability at least 2/3 on every instance. Our lower bounds and the existing upper bound give c_pQ_E^2/(3p−1)≤ T_E^rand(ε)≤ T_E^det(ε)≤ C_pQ_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.
ER -