mlsanityData to 14 Oct 2026

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

arXiv 2609.08380 ↗First posted 8 Sep 2026math.OC cs.LGcited by 2

Not on the map. Why?

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.

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

21 of 39 references.

References · 21

  1. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 96
  2. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 73
  3. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 62
  4. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61
  5. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 57
  6. 2018A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivitycited by 36
  7. 2019Revisiting Stochastic Extragradientcited by 35
  8. 2020Simple and optimal methods for stochastic variational inequalities, I: operator extrapolationcited by 35
  9. 2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
  10. 2022Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutionscited by 27
  11. 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
  12. 2022The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimizationcited by 20
9 more
  1. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 20
  2. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 19
  3. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 19
  4. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 17
  5. 2024Dealing with unbounded gradients in stochastic saddle-point optimizationcited by 16
  6. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 11
  7. 2026Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusionscited by 3
  8. 2023A Novel Catalyst Scheme for Stochastic Minimax Optimizationcited by 2
  9. 2025New Accelerated Past-Extragradient Methods with Variance Reduction for Generalized Equationscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalitiescited by 0
  2. 2026Optimal Oracle Complexity for Finite-Sum Monotone Inclusionscited by 0