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:
- 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.
- 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$).
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.
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