# Solving stochastic weak Minty variational inequalities without increasing batch size

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 37 references that are in the map.
- First posted on arXiv 17 Feb 2023.

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

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2106.02326/) (2021)
- [Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization](https://mlsanity.com/paper/2008.10847/) (2020)
- [Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling](https://mlsanity.com/paper/2003.10162/) (2020)
- [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2002.09621/) (2020)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Revisiting Stochastic Extragradient](https://mlsanity.com/paper/1905.11373/) (2019)
- [Stochastic Hamiltonian Gradient Methods for Smooth Games](https://mlsanity.com/paper/2007.04202/) (2020)
- [Stochastic Extragradient: General Analysis and Improved Rates](https://mlsanity.com/paper/2111.08611/) (2021)
- [Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities](https://mlsanity.com/paper/2103.04410/) (2021)
- [Generalized monotone operators and their averaged resolvents](https://mlsanity.com/paper/1902.09827/) (2019)
- [Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutions](https://mlsanity.com/paper/2201.12247/) (2022)
- [Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants](https://mlsanity.com/paper/1410.1628/) (2014)
- [On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging](https://mlsanity.com/paper/2107.00464/) (2021)
- [Asymmetric Forward-Backward-Adjoint Splitting for Solving Monotone Inclusions Involving Three Operators](https://mlsanity.com/paper/1602.08729/) (2016)

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

- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (2023)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developments](https://mlsanity.com/paper/2303.17192/) (2023)
- [Solving Stochastic Variational Inequalities without the Bounded Variance Assumption](https://mlsanity.com/paper/2602.05531/) (2026)
- [Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates](https://mlsanity.com/paper/2306.05100/) (2023)
- [Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity](https://mlsanity.com/paper/2402.05071/) (2024)
- [Stable Nonconvex-Nonconcave Training via Linear Interpolation](https://mlsanity.com/paper/2310.13459/) (2023)
- [Primal Methods for Variational Inequality Problems with Functional Constraints](https://mlsanity.com/paper/2403.12859/) (2024)
- [Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems](https://mlsanity.com/paper/2406.02413/) (2024)
- [Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions](https://mlsanity.com/paper/2603.15576/) (2026)
- [Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation](https://mlsanity.com/paper/2306.16617/) (2023)
- [Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property](https://mlsanity.com/paper/2312.12067/) (2023)
- [Diffusion Stochastic Optimization for Min-Max Problems](https://mlsanity.com/paper/2401.14585/) (2024)
- [Revisiting Extragradient-Type Methods -- Part 1: Generalizations and Sublinear Convergence Rates](https://mlsanity.com/paper/2409.16859/) (2024)
- [How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond](https://mlsanity.com/paper/2609.08380/) (2026)
- [Convergence of the Chambolle-Pock Algorithm in the Absence of Monotonicity](https://mlsanity.com/paper/2312.06540/) (2023)
- [RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation](https://mlsanity.com/paper/2603.22155/) (2026)
- [A Deep Learning Based Resource Allocator for Communication Networks with Dynamic User Utility Demands](https://mlsanity.com/paper/2311.04600/) (2023)
- [Breaking the Stochasticity Barrier: An Adaptive Variance-Reduced Method for Variational Inequalities](https://mlsanity.com/paper/2601.23034/) (2026)
- [Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities](https://mlsanity.com/paper/2609.15257/) (2026)

## Abstract (arXiv)

This paper introduces a family of stochastic extragradient-type algorithms for a class of nonconvex-nonconcave problems characterized by the weak Minty variational inequality (MVI). Unlike existing results on extragradient methods in the monotone setting, employing diminishing stepsizes is no longer possible in the weak MVI setting. This has led to approaches such as increasing batch sizes per iteration which can however be prohibitively expensive. In contrast, our proposed methods involves two stepsizes and only requires one additional oracle evaluation per iteration. We show that it is possible to keep one fixed stepsize while it is only the second stepsize that is taken to be diminishing, making it interesting even in the monotone setting. Almost sure convergence is established and we provide a unified analysis for this family of schemes which contains a nonlinear generalization of the celebrated primal dual hybrid gradient algorithm.