mlsanityData to 7 Oct 2026

RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation

arXiv 2603.22155 ↗First posted 23 Mar 2026cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

A celebrated method for Variational Inequalities (VIs) is Extragradient (EG), which can be viewed as a standard discrete-time integration scheme. With this view in mind, in this paper we show that EG may suffer from discretization bias when applied to non-linear vector fields, conservative or otherwise. To resolve this discretization shortcoming, we introduce RAndomized Mid-Point for debiAsed Gradient Extrapolation (RAMPAGE) and its variance-reduced counterpart, RAMPAGE+, which leverages antithetic sampling. In contrast with EG, both methods are unbiased. Furthermore, leveraging negative correlation, RAMPAGE+ acts as an unbiased, geometric path-integrator that completely removes internal first-order terms from the variance, provably improving upon RAMPAGE. We further demonstrate that both methods enjoy provable O(1/k) convergence guarantees for a range of problems including root finding under co-coercive, co-hypomonotone, and generalized Lipschitzness regimes. Furthermore, we introduce symmetrically scaled variants to extend our results to constrained VIs. Finally, we provide convergence guarantees of both methods for stochastic and deterministic smooth convex-concave games. Somewhat interestingly, despite being a randomized method, RAMPAGE+ attains purely deterministic bounds for a number of the studied settings.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 52 of its 103 references that are in the map. First posted on arXiv 23 Mar 2026.

Builds on

52 of 103 references.

References · 52

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2018Which Training Methods for GANs do actually Converge?cited by 672
  4. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  5. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 335
  6. 2015A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insightscited by 203
  7. 2018Statistical Aspects of Wasserstein Distancescited by 202
  8. 2020Large-Scale Methods for Distributionally Robust Optimizationcited by 179
  9. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  10. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  11. 2023Linear attention is (maybe) all you need (to understand transformer optimization)cited by 97
  12. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
38 more
  1. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  2. 2020Variance-Reduced Methods for Machine Learningcited by 79
  3. 2019Enhanced Convolutional Neural Tangent Kernelscited by 76
  4. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 71
  5. 2018Understanding the Acceleration Phenomenon via High-Resolution Differential Equationscited by 68
  6. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  7. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 61
  8. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 60
  9. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
  10. 2020Faster Non-Convex Federated Learning via Global and Local Momentumcited by 48
  11. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  12. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  13. 2023Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimizationcited by 35
  14. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  15. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 31
  16. 2020Adaptive extra-gradient methods for min-max optimization and gamescited by 30
  17. 2019Generalized monotone operators and their averaged resolventscited by 27
  18. 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
  19. 2024Methods for Convex (L0,L1)-Smooth Optimization: Clipping, Acceleration, and Adaptivitycited by 25
  20. 2022Exact Optimal Accelerated Complexity for Fixed-Point Iterationscited by 23
  21. 2022Neural Tangent Kernel: A Surveycited by 22
  22. 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
  23. 2023Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problemscited by 21
  24. 2021Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusionscited by 20
  25. 2021High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noisecited by 18
  26. 2022From Halpern's Fixed-Point Iterations to Nesterov's Accelerated Interpretations for Root-Finding Problemscited by 18
  27. 2024Optimizing (L0, L1)-Smooth Functions by Gradient Methodscited by 18
  28. 2022Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methodscited by 16
  29. 2018Operator Splitting Performance Estimation: Tight contraction factors and optimal parameter selectioncited by 13
  30. 2021Communication-Efficient Variance-Reduced Decentralized Stochastic Optimization over Time-Varying Directed Graphscited by 9
  31. 2023Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developmentscited by 5
  32. 2024Restarted Halpern PDHG for Linear Programmingcited by 5
  33. 2018Differentiable Antithetic Sampling for Variance Reduction in Stochastic Variational Inferencecited by 4
  34. 2025Extragradient Method for (L0, L1)-Lipschitz Root-finding Problemscited by 3
  35. 2023Moving Anchor Extragradient Methods For Smooth Structured Minimax Problemscited by 2
  36. 2024Revisiting Extragradient-Type Methods -- Part 1: Generalizations and Sublinear Convergence Ratescited by 2
  37. 2025Accelerated Extragradient-Type Methods -- Part 2: Generalization and Sublinear Convergence Rates under Co-Hypomonotonicitycited by 2
  38. 2025Glocal Smoothness: Line search and adaptive step sizes can help in theory too!cited by 2

50 most cited of 52 All 52 (JSON)

Built on by

Not cited yet.