K-Beam Minimax: Efficient Optimization for Deep Adversarial Learning
This addresses a key bottleneck in adversarial training for machine learning applications like GANs and domain adaptation, offering a more efficient and stable optimization method.
The paper tackles the failure of alternating gradient descent in minimax optimization due to discontinuity in inner maximization solutions, proposing a K-beam epsilon-subgradient descent algorithm that finds solutions previous methods cannot with sublinear complexity increase in K, showing significant improvements in stability and convergence speed in GAN training and domain adaptation.
Minimax optimization plays a key role in adversarial training of machine learning algorithms, such as learning generative models, domain adaptation, privacy preservation, and robust learning. In this paper, we demonstrate the failure of alternating gradient descent in minimax optimization problems due to the discontinuity of solutions of the inner maximization. To address this, we propose a new epsilon-subgradient descent algorithm that addresses this problem by simultaneously tracking K candidate solutions. Practically, the algorithm can find solutions that previous saddle-point algorithms cannot find, with only a sublinear increase of complexity in K. We analyze the conditions under which the algorithm converges to the true solution in detail. A significant improvement in stability and convergence speed of the algorithm is observed in simple representative problems, GAN training, and domain-adaptation problems.