mlsanityData to 14 Oct 2026

Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise

arXiv 2206.01095 ↗First posted 2 Jun 2022math.OC cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

Stochastic first-order methods such as Stochastic Extragradient (SEG) or Stochastic Gradient Descent-Ascent (SGDA) for solving smooth minimax problems and, more generally, variational inequality problems (VIP) have been gaining a lot of attention in recent years due to the growing popularity of adversarial formulations in machine learning. However, while high-probability convergence bounds are known to reflect the actual behavior of stochastic methods more accurately, most convergence results are provided in expectation. Moreover, the only known high-probability complexity results have been derived under restrictive sub-Gaussian (light-tailed) noise and bounded domain assumption [Juditsky et al., 2011]. In this work, we prove the first high-probability complexity results with logarithmic dependence on the confidence level for stochastic methods for solving monotone and structured non-monotone VIPs with non-sub-Gaussian (heavy-tailed) noise and unbounded domains. In the monotone case, our results match the best-known ones in the light-tails case [Juditsky et al., 2011], and are novel for structured non-monotone problems such as negative comonotone, quasi-strongly monotone, and/or star-cocoercive ones. We achieve these results by studying SEG and SGDA with clipping. In addition, we numerically validate that the gradient noise of many practical GAN formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). Builds on 37 of its 66 references that are in the map. First posted on arXiv 2 Jun 2022.

Builds on

37 of 66 references.

References · 37

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2018A Style-Based Generator Architecture for Generative Adversarial Networkscited by 6,013
  3. 2019Analyzing and Improving the Image Quality of StyleGANcited by 3,588
  4. 2018Large Scale GAN Training for High Fidelity Natural Image Synthesiscited by 2,626
  5. 2017Improved Training of Wasserstein GANscited by 2,235
  6. 2018Spectral Normalization for Generative Adversarial Networkscited by 1,636
  7. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  8. 2022StyleGAN-XL: Scaling StyleGAN to Large Diverse Datasetscited by 492
  9. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 341
  10. 2017FeUdal Networks for Hierarchical Reinforcement Learningcited by 337
  11. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  12. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
25 more
  1. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 96
  2. 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
  3. 2020The Complexity of Constrained Min-Max Optimizationcited by 82
  4. 2016Learning in games with continuous action sets and unknown payoff functionscited by 81
  5. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  6. 2015Beyond Convexity: Stochastic Quasi-Convex Optimizationcited by 76
  7. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 62
  8. 2018Negative Momentum for Improved Game Dynamicscited by 60
  9. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  10. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  11. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  12. 2021Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothnesscited by 37
  13. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  14. 2019Revisiting Stochastic Extragradientcited by 35
  15. 2020Adversarial Example Gamescited by 34
  16. 2019Algorithms of Robust Stochastic Optimization Based on Mirror Descent Methodcited by 32
  17. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  18. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  19. 2021Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalitiescited by 29
  20. 2019Generalized monotone operators and their averaged resolventscited by 27
  21. 2022Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutionscited by 27
  22. 2019Last-iterate convergence rates for min-max optimizationcited by 25
  23. 2019Self-supervised GAN: Analysis and Improvement with Multi-class Minimax Gamecited by 25
  24. 2021High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noisecited by 19
  25. 2017Measuring heavy-tailedness of distributionscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 3; 2024: 2; 2025: 3; 2026: 4.

14 papers.

Sort:

  1. 2025Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noisecited by 41
  2. 2023Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewardscited by 11
  3. 2024Adaptive Gradient Clipping for Robust Federated Learningcited by 11
  4. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  5. 2023High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noisecited by 7
  6. 2025Efficient Distributed Optimization under Heavy-Tailed Noisecited by 7
  7. 2024Analysis of Kernel Mirror Prox for Measure Optimizationcited by 4
  8. 2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 4
  9. 2022Dissecting adaptive methods in GANscited by 3
  10. 2026Solving Stochastic Fixed-Point Equations with High Probabilitycited by 3
  11. 2023Cyclic and Randomized Stepsizes Invoke Heavier Tails in SGD than Constant Stepsizecited by 2
  12. 2026Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noisecited by 2
2 more
  1. 2026Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noisecited by 1
  2. 2026Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problemscited by 0