K-Beam Minimax: Efficient Optimization for Deep Adversarial Learning

Jihun Hamm, Yung-Kyun Noh
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1881-1889, 2018.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-hamm18a, title = {K-Beam Minimax: Efficient Optimization for Deep Adversarial Learning}, author = {Hamm, Jihun and Noh, Yung-Kyun}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {1881--1889}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/hamm18a/hamm18a.pdf}, url = {https://proceedings.mlr.press/v80/hamm18a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T K-Beam Minimax: Efficient Optimization for Deep Adversarial Learning %A Jihun Hamm %A Yung-Kyun Noh %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-hamm18a %I PMLR %P 1881--1889 %U https://proceedings.mlr.press/v80/hamm18a.html %V 80 %X 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.
APA
Hamm, J. & Noh, Y.. (2018). K-Beam Minimax: Efficient Optimization for Deep Adversarial Learning. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:1881-1889 Available from https://proceedings.mlr.press/v80/hamm18a.html.

Related Material