mlsanityData to 7 Oct 2026

Solving stochastic weak Minty variational inequalities without increasing batch size

arXiv 2302.09029 ↗First posted 17 Feb 2023math.OC cs.LGcited by 21

Not on the map. Why?

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.

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

Builds on

22 of 37 references.

References · 22

  1. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  2. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  3. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  4. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  5. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  6. 2020The Complexity of Constrained Min-Max Optimizationcited by 81
  7. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 61
  8. 2020Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimizationcited by 51
  9. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  10. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
  11. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  12. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 37
10 more
  1. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  2. 2019Revisiting Stochastic Extragradientcited by 35
  3. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  4. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  5. 2021Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalitiescited by 29
  6. 2019Generalized monotone operators and their averaged resolventscited by 27
  7. 2022Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutionscited by 27
  8. 2014Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variantscited by 19
  9. 2021On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averagingcited by 18
  10. 2016Asymmetric Forward-Backward-Adjoint Splitting for Solving Monotone Inclusions Involving Three Operatorscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 9; 2024: 5; 2025: 1; 2026: 6.

21 papers.

Sort:

  1. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  2. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 13
  3. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 10
  4. 2023Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developmentscited by 5
  5. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  6. 2024Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexitycited by 4
  7. 2023Stable Nonconvex-Nonconcave Training via Linear Interpolationcited by 3
  8. 2024Primal Methods for Variational Inequality Problems with Functional Constraintscited by 3
  9. 2026Solving Stochastic Variational Inequalities without the Bounded Variance Assumptioncited by 3
  10. 2023Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computationcited by 2
  11. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  12. 2024Diffusion Stochastic Optimization for Min-Max Problemscited by 2
9 more
  1. 2024Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problemscited by 2
  2. 2024Revisiting Extragradient-Type Methods -- Part 1: Generalizations and Sublinear Convergence Ratescited by 2
  3. 2026Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusionscited by 2
  4. 2023Convergence of the Chambolle-Pock Algorithm in the Absence of Monotonicitycited by 1
  5. 2026How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyondcited by 1
  6. 2023A Deep Learning Based Resource Allocator for Communication Networks with Dynamic User Utility Demandscited by 0
  7. 2026Breaking the Stochasticity Barrier: An Adaptive Variance-Reduced Method for Variational Inequalitiescited by 0
  8. 2026RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolationcited by 0
  9. 2026Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalitiescited by 0