Search papers, labs, and topics across Lattice.
This paper analyzes the stochastic first-order oracle complexity of constrained convex-concave min-max optimization and monotone variational inequalities using the gradient mapping norm as the convergence criterion. While unconstrained stochastic min-max optimization achieves a near-optimal $\widetilde{O}(\varepsilon^{-2})$ complexity, constrained variants have historically suffered from a loose $\widetilde{O}(\varepsilon^{-4})$ upper bound. The authors bridge this foundational theoretical gap by establishing an optimal $\widetilde{O}(\varepsilon^{-2})$ rate for constrained settings and generalizing the result to unbounded variance regimes via the Blum-Gladyshev condition.
Constrained min-max optimization just caught up to its unconstrained counterpart: the long-standing $\widetilde{O}(\varepsilon^{-4})$ stochastic complexity bound for natural residuals collapses down to optimal $\widetilde{O}(\varepsilon^{-2})$.
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}(\varepsilon^{-4})$, compared to the near-optimal $\widetilde{O}(\varepsilon^{-2})$ that is established in the unconstrained case. We bridge this gap to improve the gradient mapping complexity for constrained convex-concave min-max problems to $\widetilde{O}(\varepsilon^{-2})$. We then extend to prove the same complexity for problems without the bounded variance, by using the Blum-Gladyshev assumption.
