SOURCE-LINKED INTELLIGENCE

How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond

arXiv · AI, language, vision and robotics · article · Sep 8, 2026 · UTC

We study the stochastic first-order oracle complexity for constrained or regularized convex-concave min-max optimization and stochastic monotone variational inequalities. We focus on the case when suboptimality is measured in terms of the gradient mapping, also known as, forward-backward or natural residual, an optimality notion that generalizes the gradient norm for unconstrained problems. In this setting, under standard unbiased oracle access with now-standard variance assumptions, the best-known complexity for making the norm of the gradient mapping less than $\varepsilon$ is $\widetilde{O}

Read original source ↗ Open in workspace

recordType

paper

region

Global