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

arXiv: https://arxiv.org/abs/2609.08380 · HTML: https://mlsanity.com/paper/2609.08380/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 39 references that are in the map.
- First posted on arXiv 8 Sep 2026.

## Builds on (most cited first, 21 of 21)

- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2106.02326/) (2021)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity](https://mlsanity.com/paper/1808.04162/) (2018)
- [Revisiting Stochastic Extragradient](https://mlsanity.com/paper/1905.11373/) (2019)
- [Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation](https://mlsanity.com/paper/2011.02987/) (2020)
- [Extragradient method with variance reduction for stochastic variational inequalities](https://mlsanity.com/paper/1703.00260/) (2017)
- [Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutions](https://mlsanity.com/paper/2201.12247/) (2022)
- [Solving stochastic weak Minty variational inequalities without increasing batch size](https://mlsanity.com/paper/2302.09029/) (2023)
- [The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2205.05653/) (2022)
- [Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization](https://mlsanity.com/paper/2208.05925/) (2022)
- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalities](https://mlsanity.com/paper/2204.09228/) (2022)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [Dealing with unbounded gradients in stochastic saddle-point optimization](https://mlsanity.com/paper/2402.13903/) (2024)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions](https://mlsanity.com/paper/2603.15576/) (2026)
- [A Novel Catalyst Scheme for Stochastic Minimax Optimization](https://mlsanity.com/paper/2311.02814/) (2023)
- [New Accelerated Past-Extragradient Methods with Variance Reduction for Generalized Equations](https://mlsanity.com/paper/2508.16791/) (2025)

## Built on by (most cited first, 2 of 2)

- [Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities](https://mlsanity.com/paper/2609.15257/) (2026)
- [Optimal Oracle Complexity for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2610.05038/) (2026)

## Abstract (arXiv)

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 widetildeO(varepsilon-4), compared to the near-optimal widetildeO(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 widetildeO(varepsilon-2). We then extend to prove the same complexity for problems without the bounded variance, by using the Blum-Gladyshev assumption.