Minimax and Saddle-Point Optimization

Minimax training pits two players against each other, so the goal is an equilibrium where neither side can improve alone, not a single minimum.

Simultaneous updates orbit a minimax equilibrium while extragradient steps land on it

Why Does This Exist?

GANs, adversarial training, and robust optimization all minimize over one player while maximizing over another: $\min_x \max_y f(x, y)$ . The solution is not a valley but a seat-shaped equilibrium, lowest along $x$ and highest along $y$ . Standard gradient descent assumes a single downhill and walks in circles around such points instead of settling.

Training GANs made the failure famous: generator and discriminator chase each other in persistent oscillations. This page names the equilibrium, shows why naive updates cycle, and gives the fixes. Game context lives in game-theoretic optimization; OT-flavored GAN losses in OT in generative modeling.

The one idea you need first

A Nash equilibrium $(x^*, y^*)$ satisfies $f(x^*, y) \leq f(x^*, y^*) \leq f(x, y^*)$ : neither player gains by moving alone. For convex-concave $f$ such a point exists and duality holds. Details on descent mechanics in gradient descent variants.

Think of It Like This

Two players on a seesaw with a brake

Two kids share a seesaw and each wants their own side down. If both lean at once, the board rocks back and forth forever. Nobody wins and the motion never settles.

The fix is taking turns with a lookahead: lean slightly, feel where the board goes, then commit. That preview step (extragradient) drains the rocking energy instead of feeding it.

Where the analogy stops: real minimax landscapes curve in millions of directions, so the rocking hides inside high-dimensional rotations.

How It Actually Works

Simultaneous gradient descent-ascent (GDA) runs $x \gets x - \eta \nabla_x f$ , $y \gets y + \eta \nabla_y f$ . On bilinear $f(x,y) = xy$ with $\eta = 0.1$ from $(1, 0)$ :

Step 1: grads $(0, 1)$ , new point $(1, 0.1)$ . Distance from origin grows from $1$ to $\approx 1.005$ .
Each step rotates and expands: GDA diverges on exactly the problem it should solve.

Extragradient fixes it: evaluate gradients at a lookahead point $(\tilde{x}, \tilde{y})$ , then apply them at the current one. On $xy$ this converges linearly for small $\eta$ . Alternatives: optimistic GDA (reuse the past gradient as the preview) and iterate averaging, which damps cycles into convergence for convex-concave cases.

Worked example

Bilinear $f(x, y) = 2xy$ , start $(1, 1)$ , $\eta = 0.1$ :

GDA gradients: $\nabla_x = 2y = 2$ , $\nabla_y = 2x = 2$ . Update: $x \to 0.8$ , $y \to 1.2$ . Radius squared: $0.64 + 1.44 = 2.08 > 2$ . Grew.
Extragradient lookahead: $\tilde{x} = 0.8$ , $\tilde{y} = 1.2$ . Gradients there: $2.4, 1.6$ . Apply at origin point: $x \to 1 - 0.24 = 0.76$ , $y \to 1 + 0.16 = 1.16$ . Radius squared $0.578 + 1.346 = 1.924 < 2$ . Shrank. One preview flipped divergence into contraction.

Watch Out For

Tuning the generator and discriminator with one learning rate

The two players usually need different speeds. Equal rates let the faster player orbit while the slower one crawls, and loss curves look healthy while samples stay bad.

Use two time-scales (discriminator faster is the common recipe) and monitor sample quality, not just the loss values.

Reading the minimax loss as a progress bar

At equilibrium the loss value means little: both players can be strong while the number sits still. Teams stop early because the loss flattened.

Track independent metrics (FID, robust accuracy, duality gap) instead of the raw minimax objective.

The Quick Version

Minimax seeks an equilibrium, lowest in $x$ and highest in $y$ , not a single minimum.
Simultaneous gradient descent-ascent can orbit or diverge even on bilinear problems.
Extragradient previews before committing and restores convergence.
Optimistic updates and averaging are cheaper stabilizers for convex-concave cases.
Tune each player separately and judge progress by outside metrics, not the loss number.