A Convergent and Dimension-Independent Min-Max Optimization Algorithm
This addresses the challenge of unstable convergence in min-max optimization for machine learning practitioners, though it is incremental as it builds on a recently introduced framework.
The paper tackles the problem of min-max optimization in nonconvex-nonconcave settings, such as GAN training, by proposing an algorithm that converges to an approximate local equilibrium with a dimension-independent iteration count, and it demonstrates stable training and avoidance of mode collapse on synthetic and real-world datasets.
We study a variant of a recently introduced min-max optimization framework where the max-player is constrained to update its parameters in a greedy manner until it reaches a first-order stationary point. Our equilibrium definition for this framework depends on a proposal distribution which the min-player uses to choose directions in which to update its parameters. We show that, given a smooth and bounded nonconvex-nonconcave objective function, access to any proposal distribution for the min-player's updates, and stochastic gradient oracle for the max-player, our algorithm converges to the aforementioned approximate local equilibrium in a number of iterations that does not depend on the dimension. The equilibrium point found by our algorithm depends on the proposal distribution, and when applying our algorithm to train GANs we choose the proposal distribution to be a distribution of stochastic gradients. We empirically evaluate our algorithm on challenging nonconvex-nonconcave test-functions and loss functions arising in GAN training. Our algorithm converges on these test functions and, when used to train GANs, trains stably on synthetic and real-world datasets and avoids mode collapse