RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation

Zhankun Luo, M. Berk Sahin, Antesh Upadhyay, Behzad Sharif, Abolfazl HashemiarXiv 2026 · arXiv

TL;DR

The classic Extragradient (EG) method is a staple for solving min-max optimization problems, but it suffers from a hidden "discretization bias" in non-linear settings that can cause algorithms to diverge. This paper introduces RAMPAGE and RAMPAGE+, novel algorithms that use randomized path integration and antithetic sampling to eliminate this bias. The result is a highly stable optimization framework that tolerates larger stepsizes and guarantees robust convergence where standard methods fail.

What Problem Does This Paper Address?

From training Generative Adversarial Networks (GANs) to optimizing for adversarial robustness and distributionally robust optimization (DRO), machine learning is increasingly reliant on min-max optimization and Variational Inequalities (VIs). To keep these inherently unstable rotational dynamics from spiraling out of control, researchers overwhelmingly rely on the Extragradient (EG) method.

EG works by taking a temporary step forward, evaluating the gradient field at that intermediate point, and then using that information to make a real update from the original position. However, the authors of this paper point out a fundamental flaw: EG acts as a rigid, discrete-time numerical integrator. When applied to highly non-linear vector fields, EG introduces a local truncation error—a discretization bias—that scales with the Hessian of the system. When stepsizes are pushed to the edge of stability, this bias causes the algorithm to overshoot, plateau, or completely diverge.

Methods

To eliminate this systematic bias, the authors propose replacing the fixed midpoint evaluation of EG with a stochastic path-integral approach:

  1. RAMPAGE (RAndomized Mid-Point for debiAsed Gradient Extrapolation): Instead of evaluating the gradient field at a fixed midpoint, RAMPAGE randomly samples a point $u_t$ uniformly from the exploration interval $[0, 1]$. Because the expectation of this random selection perfectly mirrors the continuous line integral of the vector field, the discretization bias is completely neutralized.
  2. RAMPAGE+: While random sampling removes bias, it introduces variance. To fix this, RAMPAGE+ leverages antithetic sampling. At each step, it evaluates the gradient at a random point $u_t$ and its deterministic complement $\tilde{u}_t = 1 - u_t$. This perfectly correlated pairing cancels out the first-order Taylor fluctuations along the exploration path, drastically reducing variance.
  3. Symmetrically Scaled (SS) Variants: When moving from unconstrained to constrained optimization, standard randomized scaling can break down at the boundaries. The authors introduce SS-RAMPAGE and SS-RAMPAGE+, which symmetrically couple the randomized step to both the intermediate exploration projection and the final update projection to maintain feasibility.

Datasets

The authors validated their approach on both synthetic benchmarks and real-world datasets:

  • Synthetic Fields: A 4th-order conservative polynomial field and high-frequency rotational min-max games designed to mimic the complex dynamics of infinite-width GANs.
  • Real-World Benchmark: The Breast Cancer Wisconsin dataset (569 samples, 30 features) was utilized to evaluate the algorithms on practical, non-bilinear min-max tasks: KL-regularized Distributionally Robust Optimization (DRO) and adversarial training formulations.

Key Insights and Ideas

  • De-biasing via Randomization: Instead of computing expensive higher-order derivatives to correct numerical integration errors, simply randomizing the evaluation point along the path yields a mathematically unbiased estimator.
  • Deterministic Bounds from a Randomized Algorithm: Remarkably, because the antithetic sampling in RAMPAGE+ is so effective at neutralizing path variance, the algorithm yields purely deterministic $\mathcal{O}(1/k)$ convergence bounds for several settings, rather than just bounds in expectation.
  • Path-Averaging as a Low-Pass Filter: By integrating over an exploration segment rather than evaluating a single point, RAMPAGE+ acts as a geometric low-pass filter, smoothing out high-frequency non-linear perturbations that typically destabilize EG.

Key Results

The empirical results highlight a massive stability upgrade over standard Extragradient methods.

Comparison of EG and RAMPAGE+ across various optimization landscapes.

As shown in Figure 1, when stepsizes are tuned to the edge of stability, a slight increase causes EG to become unstable or plateau (blue curves). In contrast, RAMPAGE+ (red and green curves) converges smoothly.

Key quantitative takeaways include:

  • Larger Stepsizes: RAMPAGE+ successfully converges using stepsizes that are 6% to 26% larger than the maximum allowable stepsize for EG.
  • Robustness in Adversarial Settings: On the Breast Cancer Wisconsin dataset, RAMPAGE+ continued to minimize the residual norm under aggressive step regimes where EG completely stalled or diverged.

Limitations and Future Work

While RAMPAGE+ provides superior stability, it requires two operator evaluations per iteration (at $u_t$ and $1-u_t$). While this matches the per-iteration computational cost of standard EG, it does not reduce it.

Additionally, the theoretical guarantees in this work primarily focus on smooth or generalized Lipschitz continuous operators. Extending this randomized path-integration framework to non-smooth regimes or settings with highly stochastic, heavy-tailed oracle noise represents an exciting frontier for future research.

Summary updated

Abstract

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 $\mathcal{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.
BibTeX
@misc{luo2026rampage,
  author = {Zhankun Luo and M. Berk Sahin and Antesh Upadhyay and Behzad Sharif and Abolfazl Hashemi},
  title = {{RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation}},
  year = {2026},
  eprint = {2603.22155},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.22155},
}
Figure