גבולות תחתונים לאלגוריתמים ראשוניים-אקראיים עם צמצום סטטיסטי באופטימיזציה מינימקס-קונבקס

תקציר מקורי באנגליתarXiv:2610.01662v1 Announce Type: cross Abstract: 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 suboptimality at most $\Delta$. The target accuracy $\varepsilon$ is measured by the gradient norm of the Moreau envelope of the constrained primal val