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

arXiv: https://arxiv.org/abs/1910.07512 · HTML: https://mlsanity.com/paper/1910.07512/

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2019.

## Built on by (most cited first, 30 of 34)

- [Deep Generative Modelling: A Comparative Review of VAEs, GANs, Normalizing Flows, Energy-Based and Autoregressive Models](https://mlsanity.com/paper/2103.04922/) (2021)
- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency](https://mlsanity.com/paper/2102.13152/) (2021)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [Learning to Give Checkable Answers with Prover-Verifier Games](https://mlsanity.com/paper/2108.12099/) (2021)
- [Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization](https://mlsanity.com/paper/2102.09468/) (2021)
- [Indiscriminate Data Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/2204.09092/) (2022)
- [Meta-learning Adaptive Deep Kernel Gaussian Processes for Molecular Property Prediction](https://mlsanity.com/paper/2205.02708/) (2022)
- [Multi-Rate VAE: Train Once, Get the Full Rate-Distortion Curve](https://mlsanity.com/paper/2212.03905/) (2022)
- [Discretization Drift in Two-Player Games](https://mlsanity.com/paper/2105.13922/) (2021)
- [Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2110.04814/) (2021)
- [Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimization](https://mlsanity.com/paper/2212.12978/) (2022)
- [Complex Momentum for Optimization in Games](https://mlsanity.com/paper/2102.08431/) (2021)
- [Minimax Optimization with Smooth Algorithmic Adversaries](https://mlsanity.com/paper/2106.01488/) (2021)
- [Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain](https://mlsanity.com/paper/2110.03950/) (2021)
- [Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equations](https://mlsanity.com/paper/2112.13826/) (2021)
- [Lyapunov Exponents for Diversity in Differentiable Games](https://mlsanity.com/paper/2112.14570/) (2021)
- [A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimization](https://mlsanity.com/paper/2110.07098/) (2021)
- [Calibrated Dataset Condensation for Faster Hyperparameter Search](https://mlsanity.com/paper/2405.17535/) (2024)
- [Learning for Robust Combinatorial Optimization: Algorithm and Application](https://mlsanity.com/paper/2112.10377/) (2021)
- [Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learning](https://mlsanity.com/paper/2112.11663/) (2021)
- [STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games](https://mlsanity.com/paper/2210.09769/) (2022)
- [Two-timescale Extragradient for Finding Local Minimax Points](https://mlsanity.com/paper/2305.16242/) (2023)
- [Generative Minimization Networks: Training GANs Without Competition](https://mlsanity.com/paper/2103.12685/) (2021)
- [Stability and Generalization of Differentially Private Minimax Problems](https://mlsanity.com/paper/2204.04858/) (2022)
- [Recursive Reasoning in Minimax Games: A Level k Gradient Play Method](https://mlsanity.com/paper/2210.16482/) (2022)
- [Exploiting the Hidden Tasks of GANs: Making Implicit Subproblems Explicit](https://mlsanity.com/paper/2101.11863/) (2021)
- [HessianFR: An Efficient Hessian-based Follow-the-Ridge Algorithm for Minimax Optimization](https://mlsanity.com/paper/2205.11030/) (2022)
- [ApproxED: Approximate exploitability descent via learned best responses](https://mlsanity.com/paper/2301.08830/) (2023)
- [Distributionally Safe Reinforcement Learning under Model Uncertainty: A Single-Level Approach by Differentiable Convex Programming](https://mlsanity.com/paper/2310.02459/) (2023)

## Abstract (arXiv)

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.