{"id":"arxiv/2610.16991","url":"https://arxiv.org/abs/2610.16991","tags":["math.OC"],"score":0,"title":"Matching Randomized Bounds for Finite-Sum Nonconvex-Concave Optimization","domain":"math.OC","source":"arxiv","authors":["Wendao Wu","Haihan Zhang","Qian Chen","Chenheng Zhang","Chunyuan Zheng","Cong Fang","Haoxuan Li","Zhouchen Lin"],"reviews":0,"subject":"math.OC","summary":"We characterize the randomized component-oracle complexity of finite-sum nonconvex-concave optimization with a bounded dual domain. For $Φ(x)=\\max_{y\\in Y}n^{-1}\\sum_{i=1}^n f_i(x,y)$, the goal is to find an $\\varepsilon$-stationary point of the Moreau envelope $Φ_{1/(2L)}$ with probability at least $2/3$ and a fixed query budget. Let $A=LΔ/\\varepsilon^2$, $B=LD_Y/\\varepsilon$, and $\\bar B=\\max\\{1,B\\}$, where $Δ$ bounds the initial primal gap and $D_Y$ bounds the dual diameter. For $A$ above a universal constant, the worst-case complexity is \\[ \\widetildeΘ\\!\\left(n+A\\min\\left\\{ \\sqrt n\\,\\bar…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}