Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent

Many recent AI architectures are inspired by zero-sum games, however, the\nbehavior of their dynamics is still not well understood. Inspired by this, we\nstudy standard gradient descent ascent (GDA) dynamics in a specific class of\nnon-convex non-concave zero-sum games, that we call hidden zero-sum games. In\nthis class, players control the inputs of smooth but possibly non-linear\nfunctions whose outputs are being applied as inputs to a convex-concave game.\nUnlike general zero-sum games, these games have a well-defined notion of\nsolution; outcomes that implement the von-Neumann equilibrium of the "hidden"\nconvex-concave game. We prove that if the hidden game is strictly\nconvex-concave then vanilla GDA converges not merely to local Nash, but\ntypically to the von-Neumann solution. If the game lacks strict convexity\nproperties, GDA may fail to converge to any equilibrium, however, by applying\nstandard regularization techniques we can prove convergence to a von-Neumann\nsolution of a slightly perturbed zero-sum game. Our convergence guarantees are\nnon-local, which as far as we know is a first-of-its-kind type of result in\nnon-convex non-concave games. Finally, we discuss connections of our framework\nwith generative adversarial networks.\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC