Simultaneous Transport Evolution for Minimax Equilibria on Measures
This work addresses the problem of efficiently computing mixed equilibria in non-convex min-max games for machine learning practitioners, offering a novel approach with convergence guarantees, though it is incremental in building on existing measure-space methods.
The paper tackles the computational challenge of finding mixed equilibria in min-max optimization problems, such as those in adversarial learning and generative modeling, by proposing a method that achieves global convergence to the global equilibrium using simultaneous gradient ascent-descent with entropic regularization in the Wasserstein metric, with efficient particle discretization in high dimensions.
Min-max optimization problems arise in several key machine learning setups, including adversarial learning and generative modeling. In their general form, in absence of convexity/concavity assumptions, finding pure equilibria of the underlying two-player zero-sum game is computationally hard [Daskalakis et al., 2021]. In this work we focus instead in finding mixed equilibria, and consider the associated lifted problem in the space of probability measures. By adding entropic regularization, our main result establishes global convergence towards the global equilibrium by using simultaneous gradient ascent-descent with respect to the Wasserstein metric -- a dynamics that admits efficient particle discretization in high-dimensions, as opposed to entropic mirror descent. We complement this positive result with a related entropy-regularized loss which is not bilinear but still convex-concave in the Wasserstein geometry, and for which simultaneous dynamics do not converge yet timescale separation does. Taken together, these results showcase the benign geometry of bilinear games in the space of measures, enabling particle dynamics with global qualitative convergence guarantees.