The Oracle Complexity of Samplewise-Concave Finite-Sum Minimax Optimization

We study finite-sum nonconvex–concave minimax optimization when every component, rather than only their average, is concave in the dual variable. Components have jointly Lipschitz gradients, the primal domain is Euclidean space, and the known dual domain is compact and convex. An exact oracle returns the value and full gradient of an adaptively selected component. With A = LΔ/ε², B = LD/ε, and B̄ = max{1, B}, we prove that the fixed-budget randomized complexity of finding an ε-stationary point of the original Moreau envelope is Θ̃(n + A√n B̄) above a universal nontrivial-accuracy threshold. The upper bound uses a projected recursive estimator carrying an explicit normal-cone state; its coupled residual and martingale energy persists across changing primal proximal centers. The lower bound combines a new translated-convex-potential cone with a positive-semidefinite branch construction. The cone preserves individual dual concavity at every partial gate, has uniformly bounded component Hessians, and hides future information from exact values and all first derivatives. Its global KKT certificate remains valid outside the quadratic region of the radial potential. The lower bound permits arbitrary randomized component queries and unqueried outputs. The result distinguishes samplewise concavity from average-only concavity across all dual-diameter regimes, up to logarithmic factors.