%0 Journal Article %1 wang2019solving %A Wang, Yuanhao %A Zhang, Guodong %A Ba, Jimmy %D 2019 %K bounds optimization %T On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach %U http://arxiv.org/abs/1910.07512 %X 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.

@article{wang2019solving, abstract = {Many tasks in modern machine learning can be formulated as finding equilibria in \emph{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 \emph{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 \emph{positive} momentum. Empirically, FR solves toy minimax problems and improves the convergence of GAN training compared to the recent minimax optimization algorithms.}, added-at = {2019-10-17T18:55:15.000+0200}, author = {Wang, Yuanhao and Zhang, Guodong and Ba, Jimmy}, biburl = {https://www.bibsonomy.org/bibtex/284de586d400b883a2cfac1efacc9d81a/kirk86}, description = {[1910.07512] On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach}, interhash = {51c8df4858a70074f7b7dc09b6426fd7}, intrahash = {84de586d400b883a2cfac1efacc9d81a}, keywords = {bounds optimization}, note = {cite arxiv:1910.07512Comment: 21 pages}, timestamp = {2019-10-17T18:55:15.000+0200}, title = {On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach}, url = {http://arxiv.org/abs/1910.07512}, year = 2019 }