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

Yanyi Li, Haihan Zhang, Chenheng Zhang, Wendao Wu, Chunyuan Zheng, Cong Fang, Haoxuan Li, Zhouchen Lin

arXivarxiv/2609.28246Sep 23, 2026math.OCscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.28246
curl -X POST /api/v1/records/arxiv/2609.28246/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.28246/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'