{"id":"arxiv/2610.00229","url":"https://arxiv.org/abs/2610.00229","tags":["math.OC"],"score":0,"title":"Sharp Fresh-Gradient Complexity of Nonconvex-Strongly-Concave Minimax Optimization","domain":"math.OC","source":"arxiv","authors":["Wendao Wu","Haihan Zhang","Chenheng Zhang","Yanyi Li","Chunyuan Zheng","Cong Fang","Haoxuan Li","Zhouchen Lin"],"reviews":0,"subject":"math.OC","summary":"We characterize the fresh-gradient oracle complexity of smooth nonconvex-strongly-concave minimax optimization, with matching upper and lower bounds up to logarithmic factors. Let $Φ(x)=\\max_y f(x,y)$, where $f$ is jointly $L$-smooth and $μ$-strongly concave in $y$ on unconstrained Euclidean domains, and set $κ=L/μ$. Each query returns a fresh unbiased joint gradient with conditional variance at most $σ^2$. Given initial primal gap at most $Δ$ and dual residual $\\|\\nabla_y f(x_0,y_0)\\|\\le G$, the fixed-budget complexity of finding $\\|\\nablaΦ(\\widehat x)\\|\\leε$ with probability at least $2/3$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-22","reactions":{}}