Single Call Extrapolation for Efficient Minimax Optimization

This direction is split into other directions: past-gradient extrapolation. Its last version stays readable and citable here.

Version 1 of 173 papers80 conceptsfrozen 2026-10-04

In traditional optimization, we usually seek a single "valley"—a minimum point where the loss is lowest. However, modern machine learning increasingly relies on minimax optimization, a mathematical tug-of-war where one player minimizes while another maximizes. This is the engine behind Generative Adversarial Networks (GANs), adversarial robustness, and multi-agent reinforcement learning.

The challenge is that minimax dynamics are inherently unstable. Standard gradient descent-ascent (GDA) often spirals outward or oscillates forever because the players react to each other's current position rather than where they are going. To fix this, researchers use extragradient methods, which take a "probing" step to see the future landscape before making a final update. The catch? This requires two gradient evaluations per iteration, doubling the computational cost.

A recurring breakthrough across recent research is the realization that we can get the stability of a look-ahead step for the price of a single gradient call by reusing the past.

The Intuition of Optimism

The core idea, often termed Optimistic Gradient Descent-Ascent (OGDA) or Single-Call Extragradient, is to use the gradient from the previous iteration as a proxy for the look-ahead step.

In a standard extragradient setup, you calculate a gradient at your current position $x_t$, move to a temporary point $x_{t+1/2}$, and then calculate a second gradient there to update $x_t$. Researchers like Gauthier Gidel and Simon Lacoste-Julien have shown in A Variational Inequality Perspective on Generative Adversarial Nets that if the optimization landscape is sufficiently smooth, the gradient doesn't change drastically between steps. Therefore, the gradient we just computed at $x_{t-1}$ is a remarkably good "forecast" of the gradient at $x_t$.

By incorporating this historical information, the algorithm "anticipates" the curvature of the landscape. This "optimism" dampens the oscillations common in competitive games, allowing the model to converge to a saddle point without the $2\times$ computational tax.

From GANs to Sharpness-Aware Minimization

While originally popularized for GANs, this "single-call" philosophy has spread to other areas where gradients are expensive:

  • Sharpness-Aware Minimization (SAM): SAM improves generalization by seeking "flat" minima, but it typically requires two forward-backward passes. Runsheng Yu and James T. Kwok introduced Lookahead-SAM, which reuses gradients from previous iterations to stabilize the perturbation step, maintaining the benefits of flatness with significantly lower overhead.
  • Deep Learning Optimizers: The Adan optimizer, developed by Xingyu Xie and Pan Zhou 0002, reformulates Nesterov acceleration to require only the current gradient. By approximating the "look-ahead" gradient as a linear combination of past states, it achieves faster convergence across Transformers and CNNs without doubling the work per step.
  • Quantum and Sampling: In QuACK, Di Luo and colleagues use learned operators to extrapolate future updates in quantum circuits, where every gradient measurement is extremely costly. Similarly, Mohammad Reza Karimi applies optimistic updates to Langevin sampling in A Dynamical System View of Langevin-Based Non-Convex Sampling, halving the per-step cost of higher-order integration schemes.

Theoretical Convergence and Gradient Sliding

A critical question is whether this shortcut sacrifices accuracy. Work by Chaobing Song and Yi Ma 0001 on Optimistic Dual Extrapolation (OptDE) (Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities) proves that single-call methods can achieve the same optimal convergence rates as two-call methods.

This is often achieved through Gradient Sliding, a mechanism explored by Yiu-ming Cheung and Jian Lou in Efficient Generalized Conditional Gradient with Gradient Sliding for Composite Optimization. The core insight is that we can "slide" over multiple inner iterations or subproblems using a single gradient evaluation. If the change in the model parameters is small, the gradient remains a valid directional guide for several micro-updates.

Why It Works: The Dynamical Systems View

The success of these methods is best understood by viewing optimization as a dynamical system. In On Symplectic Optimization, Michael Jordan and Ashia C. Wilson argue that many accelerated methods are actually discrete approximations of continuous physical systems (like a ball with momentum).

Single-call extrapolation works because it acts as a Reflected Gradient update. By looking at the difference between the current state and the previous state, the optimizer estimates the "velocity" of the gradient. As Volkan Cevher demonstrates in A Reflected Forward-Backward Splitting Method, this reflection allows the algorithm to correct its trajectory mid-flight. It transforms a reactive process into a predictive one, ensuring that even in the chaotic "tug-of-war" of minimax games, the players move toward equilibrium rather than spiraling into divergence.

Papers in this version

Showing 60 of 73 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_single_call_extrapolation_for_efficient__66633e5f,
  title = {Single Call Extrapolation for Efficient Minimax Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/single-call-extrapolation-for-efficient-minimax-optimization/rdr_66633e5f1bad4e7c886554836caf8dd3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_single_call_extrapolation_for_efficient__66633e5f_v1,
  title = {Single Call Extrapolation for Efficient Minimax Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/single-call-extrapolation-for-efficient-minimax-optimization/rdr_66633e5f1bad4e7c886554836caf8dd3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}