The Dynamics of Minimax Optimization Instability

629 concepts539 papers5 proposals

Standard machine learning relies on minimization. Optimization algorithms like Gradient Descent act like a ball rolling down a hill, reliably seeking the lowest point of a loss surface.

Minimax optimization—expressed as $\min_x \max_y f(x, y)$—is fundamentally different. Instead of a static landscape, it describes a zero-sum game between two players. As the minimization player ($x$) tries to find the bottom of a valley, the maximization player ($y$) continuously warps the landscape to turn that valley into a peak. This dynamic underpins many core paradigms in modern machine learning, including Generative Adversarial Networks (GANs), adversarial robustness, algorithmic fairness, and optimal transport.

However, optimizing these systems is notoriously unstable. Rather than converging to a stable saddle point (a Nash equilibrium), standard gradient methods frequently cycle endlessly, suffer from exploding or vanishing gradients, or diverge entirely. Understanding why this instability occurs requires looking closely at the rotational forces inherent to competitive games.

The Rotational Geometry of Simultaneous Updates

To build intuition for why minimax optimization fails, consider the simplest possible bilinear zero-sum game:

$$\min_x \max_y xy$$

The unique Nash equilibrium for this game is at the origin $(0,0)$. If we apply simultaneous Gradient Descent-Ascent (GDA)—where both players compute their gradients at the current state and step simultaneously—the update rules with a learning rate $\eta$ are:

$$x_{t+1} = x_t - \eta y_t$$ $$y_{t+1} = y_t + \eta x_t$$

Let's track the distance of the parameters from the equilibrium point from one iteration to the next by calculating the squared Euclidean norm:

$$x_{t+1}^2 + y_{t+1}^2 = (x_t - \eta y_t)^2 + (y_t + \eta x_t)^2$$ $$= x_t^2 - 2\eta x_t y_t + \eta^2 y_t^2 + y_t^2 + 2\eta x_t y_t + \eta^2 x_t^2$$ $$= (1 + \eta^2)(x_t^2 + y_t^2)$$

Because $(1 + \eta^2) > 1$ for any positive learning rate, the parameters spiral outward, moving further away from the solution with every single step. As Guojun Zhang and Yaoliang Yu demonstrate in Convergence of Gradient Methods on Bilinear Zero-Sum Games, simultaneous updates introduce a destabilizing rotational force. Instead of moving toward the saddle point, the vector field forces the optimization trajectory into persistent limit cycles or divergent paths.

To counteract this outward spiral, algorithms must incorporate mechanisms that look ahead or account for the interaction between players. For instance, Jacob Abernethy et al. show in Last-Iterate Convergence Rates for Min-Max Optimization: Convergence of Hamiltonian Gradient Descent and Consensus Optimization that modifying the objective to minimize the squared norm of the gradients (the Hamiltonian) can successfully penalize these rotational dynamics and force last-iterate convergence.

A Pervasive Challenge Across Domains

This instability is not unique to GANs; it surfaces whenever machine learning problems are framed as adversarial games.

The Non-Convex-Concave Nightmare

When deep neural networks parameterize the players, the optimization landscape shifts from a clean bilinear saddle point to a highly complex, non-convex-concave terrain. This transition introduces two primary failure modes: vanishing and exploding gradients.

Vanishing Gradients and Information Stalling

If the maximization player learns too quickly, it can perfectly counter any move the minimization player makes. In this scenario, the loss surface becomes completely flat for the minimization player, causing gradients to vanish.

Liao Peiyuan et al. document this phenomenon in Information Obfuscation of Graph Neural Networks. When training an adversary to scrub sensitive attributes from node embeddings, the non-convex-concave nature of the game frequently causes vanishing gradients, stalling the optimization process before a fair equilibrium can be reached.

Exploding Gradients and Margin Constraints

Conversely, forcing strict constraints or large margins into the adversarial objective can cause the loss surface to become excessively steep. Yuchen Zhang and Tianle Liu study this in Bridging Theory and Algorithm for Domain Adaptation, showing that enforcing large margin requirements in adversarial domain adaptation causes numerical instability and exploding gradients during stochastic gradient descent.

Algorithmic Remedies

To stabilize these systems, researchers focus on two main strategies: altering the update mechanics to break the rotational cycles, or bypassing the minimax formulation entirely.

1. Breaking Cycles via Alternating and Adaptive Updates

Instead of updating both networks simultaneously, alternating updates allow one player to move first, forcing the second player to compute its gradient relative to the updated position. Returning to our bilinear example, if $x$ updates first, the system changes to:

$$x_{t+1} = x_t - \eta y_t$$ $$y_{t+1} = y_t + \eta x_{t+1} = y_t + \eta(x_t - \eta y_t) = y_t + \eta x_t - \eta^2 y_t$$

The inclusion of the $-\eta^2 y_t$ term acts as an implicit friction or damping force, pulling the trajectory back inward toward the origin and stabilizing the system.

In deep learning, this principle is enhanced by adaptive optimizers. Samy Jelassi et al. analyze this in Dissecting adaptive methods in GANs, demonstrating that the adaptive magnitude component of optimizers like Adam is essential for preventing mode collapse. It ensures balanced updates between the generator and discriminator even when their gradient scales differ wildly.

For distributed or decentralized settings, lookahead strategies provide stability. Aleksandr Beznosikov and Pavel Dvurechensky show in Decentralized Local Stochastic Extra-Gradient for Variational Inequalities that taking a temporary "trial" step to calculate gradients before committing to the actual update effectively dampens oscillations across networks.

2. Bypassing the Adversary

Given the fundamental challenges of minimax optimization, an alternative research direction seeks to achieve the benefits of adversarial training without using an explicit adversary.

Adversarial Approach (Unstable Minimax):
[Generator] <---> [Discriminator (Reshapes Landscape)] ---> Optimization Oscillations

Direct Approach (Stable Minimization):
[Generator] ---------> [Explicit Divergence Metric (e.g., MMD)] ---> Smooth Convergence

For example, Yujia Li et al. introduce Generative Moment Matching Networks, which swap out the discriminator entirely. Instead of a zero-sum game, they optimize a direct Maximum Mean Discrepancy (MMD) loss function using the kernel trick, returning the problem to a standard, stable minimization framework.

Similarly, Piotr Bojanowski et al. demonstrate in Optimizing the Latent Space of Generative Networks that mapping data points directly to learnable latent vectors via simple reconstruction losses can replicate the target alignment properties of GANs, proving that the adversarial game is not always a strict requirement for generative modeling.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_adversarial_training_instability_minimax_db2a9dc7,
  title = {adversarial training instability (minimax optimization instability)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adversarial-training-instability-minimax-optimization-instability/rdr_db2a9dc78f974e35a7bda966180c338c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_adversarial_training_instability_minimax_db2a9dc7_v1,
  title = {adversarial training instability (minimax optimization instability)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adversarial-training-instability-minimax-optimization-instability/rdr_db2a9dc78f974e35a7bda966180c338c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake