On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach

Yuanhao Wang, Guodong Zhang, Jimmy Ba

Many tasks in modern machine learning, such as training Generative Adversarial Networks (GANs) and reinforcement learning models, can be formulated as finding equilibria in sequential games. This two-player zero-sum setup is commonly known as minimax optimization: $\min_x \max_y f(x, y)$.

While it is tempting to apply standard gradient descent to solve these problems, naive applications often fail. To address this, researchers have proposed Follow-the-Ridge (FR), a novel algorithm that explicitly accounts for the sequential nature of these games and is provably guaranteed to converge only to local minimax points.

The Problem with Gradient Descent-Ascent (GDA)

Most practitioners use Gradient Descent-Ascent (GDA), where both players update their parameters simultaneously. However, treating a sequential game as a simultaneous one introduces two notorious pathologies:

  1. Drifting: The leader's update often pushes the system away from the optimal response of the follower (the "ridge"), causing the algorithm to miss simple local solutions.
  2. Rotation: GDA frequently exhibits circular, oscillatory behavior around fixed points rather than converging directly to them. This forces researchers to use incredibly small learning rates, which drastically slows down training.

The Follow-the-Ridge (FR) Solution

The core insight behind FR is recognizing that minimax is not a simultaneous Nash equilibrium problem, but a sequential Stackelberg equilibrium problem. For every action the leader ($x$) takes, there is an optimal "best response" for the follower ($y$). These best responses form a "ridge" in the loss landscape.

When the leader takes a standard gradient step, they naturally move off this ridge. FR fixes this by introducing a specific correction term to the follower's update:

  • Leader update: Standard gradient descent.
  • Follower update: Standard gradient ascent plus a correction term involving the Hessian inverse ($H_{yy}^{-1}H_{yx}\nabla_x f$).
Follow-the-Ridge (FR) algorithm dynamics. The correction term explicitly cancels out the off-the-ridge displacement caused by the leader's update.

This correction term explicitly cancels out the "off-the-ridge" displacement caused by the leader, effectively acting as an asymmetric preconditioner applied to the joint gradient.

Key Theoretical Properties

By staying on the ridge, FR transforms a chaotic game-like dynamic into something that behaves more like standard, stable minimization.

  • Exact Convergence: FR converges to, and only to, local minimax points.
  • No Rotation: The Jacobian of the FR dynamics has only real eigenvalues. This eliminates the "spiraling" behavior seen in GDA.
  • Momentum Compatibility: Because the eigenvalues are real, FR can safely use positive momentum (like Nesterov or Heavy Ball) to achieve a square-root speedup—something that typically makes standard GDA more unstable.

Key Results and Empirical Performance

The authors evaluated FR across low-dimensional toy problems, Mixture of Gaussians (MoG) benchmarks, and MNIST image generation.

Stability on Toy Problems: In specifically designed quadratic and polynomial functions where GDA, Extragradient (EG), and Optimistic GDA (OGDA) either diverged, converged to bad fixed points, or circled endlessly in limit cycles, FR converged directly to the local minimax.

Comparison of optimization trajectories on toy problems. FR consistently converges to the local minimax, avoiding divergence, bad fixed points, and limiting cycles.

Overcoming Mode Collapse: In the MoG experiment, GDA suffered from mode collapse, missing parts of the target distribution. FR successfully captured all modes, with its gradient norm vanishing to near-zero, indicating true mathematical convergence.

High-Dimensional Convergence: On MNIST, the gradient norms for FR decreased significantly faster (reaching $10^{-7}$) compared to GDA (which plateaued around $10^{-2}$). Furthermore, adding positive momentum to FR provided a clear empirical speedup.

Limitations and Future Work

While theoretically sound, FR does come with computational overhead. The correction term requires inverting the follower's Hessian ($H_{yy}$). Although the authors use Conjugate Gradient (CG) methods to approximate this without explicitly forming the matrix, it still adds cost per iteration compared to simple GDA.

Additionally, while FR achieved mathematical convergence (vanishing gradients) on MNIST, the visual quality of the generated samples was limited by the capacity of the small neural networks used. Testing FR on large-scale architectures like BigGAN or StyleGAN remains an exciting open challenge for future research.

Summary updated

Abstract

Many tasks in modern machine learning can be formulated as finding equilibria in sequential games. In particular, two-player zero-sum sequential games, also known as minimax optimization, have received growing interest. It is tempting to apply gradient descent to solve minimax optimization given its popularity and success in supervised learning. However, it has been noted that naive application of gradient descent fails to find some local minimax and can converge to non-local-minimax points. In this paper, we propose Follow-the-Ridge (FR), a novel algorithm that provably converges to and only converges to local minimax. We show theoretically that the algorithm addresses the notorious rotational behaviour of gradient dynamics, and is compatible with preconditioning and positive momentum. Empirically, FR solves toy minimax problems and improves the convergence of GAN training compared to the recent minimax optimization algorithms.
BibTeX
@inproceedings{wang2020solving,
  author = {Yuanhao Wang and Guodong Zhang and Jimmy Ba},
  title = {{On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=OBW_Deyxy4},
}
Figure