{"id":"arxiv/2610.01662","url":"https://arxiv.org/abs/2610.01662","tags":["math.OC","cs.LG","stat.ML"],"score":0,"title":"Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization","domain":"math.OC","source":"arxiv","authors":["Jiayi Song","Zi Xu"],"reviews":0,"subject":"math.OC","summary":"We establish complexity lower bounds for stochastic first-order algorithms in nonconvex--concave minimax optimization, allowing algorithms to use variance reduction. Our main contribution is a lower bound for a zero-respecting algorithm class that permits variance reduction, extending beyond the algorithmic restrictions imposed by some existing lower bounds. We consider objectives with an $L$-Lipschitz continuous joint gradient, a compact convex dual domain of Euclidean radius at most $D_Y$, and a primal value function, defined by maximizing the objective over the dual variable, with initial…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}