Stability and Generalization of Stochastic Gradient Methods for Minimax Problems

Yunwen Lei, Zhenhuan Yang, Tianbao Yang, Yiming Ying
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:6175-6186, 2021.

Abstract

Many machine learning problems can be formulated as minimax problems such as Generative Adversarial Networks (GANs), AUC maximization and robust estimation, to mention but a few. A substantial amount of studies are devoted to studying the convergence behavior of their stochastic gradient-type algorithms. In contrast, there is relatively little work on understanding their generalization, i.e., how the learning models built from training examples would behave on test examples. In this paper, we provide a comprehensive generalization analysis of stochastic gradient methods for minimax problems under both convex-concave and nonconvex-nonconcave cases through the lens of algorithmic stability. We establish a quantitative connection between stability and several generalization measures both in expectation and with high probability. For the convex-concave setting, our stability analysis shows that stochastic gradient descent ascent attains optimal generalization bounds for both smooth and nonsmooth minimax problems. We also establish generalization bounds for both weakly-convex-weakly-concave and gradient-dominated problems. We report preliminary experimental results to verify our theory.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-lei21b, title = {Stability and Generalization of Stochastic Gradient Methods for Minimax Problems}, author = {Lei, Yunwen and Yang, Zhenhuan and Yang, Tianbao and Ying, Yiming}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {6175--6186}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/lei21b/lei21b.pdf}, url = {https://proceedings.mlr.press/v139/lei21b.html}, abstract = {Many machine learning problems can be formulated as minimax problems such as Generative Adversarial Networks (GANs), AUC maximization and robust estimation, to mention but a few. A substantial amount of studies are devoted to studying the convergence behavior of their stochastic gradient-type algorithms. In contrast, there is relatively little work on understanding their generalization, i.e., how the learning models built from training examples would behave on test examples. In this paper, we provide a comprehensive generalization analysis of stochastic gradient methods for minimax problems under both convex-concave and nonconvex-nonconcave cases through the lens of algorithmic stability. We establish a quantitative connection between stability and several generalization measures both in expectation and with high probability. For the convex-concave setting, our stability analysis shows that stochastic gradient descent ascent attains optimal generalization bounds for both smooth and nonsmooth minimax problems. We also establish generalization bounds for both weakly-convex-weakly-concave and gradient-dominated problems. We report preliminary experimental results to verify our theory.} }
Endnote
%0 Conference Paper %T Stability and Generalization of Stochastic Gradient Methods for Minimax Problems %A Yunwen Lei %A Zhenhuan Yang %A Tianbao Yang %A Yiming Ying %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-lei21b %I PMLR %P 6175--6186 %U https://proceedings.mlr.press/v139/lei21b.html %V 139 %X Many machine learning problems can be formulated as minimax problems such as Generative Adversarial Networks (GANs), AUC maximization and robust estimation, to mention but a few. A substantial amount of studies are devoted to studying the convergence behavior of their stochastic gradient-type algorithms. In contrast, there is relatively little work on understanding their generalization, i.e., how the learning models built from training examples would behave on test examples. In this paper, we provide a comprehensive generalization analysis of stochastic gradient methods for minimax problems under both convex-concave and nonconvex-nonconcave cases through the lens of algorithmic stability. We establish a quantitative connection between stability and several generalization measures both in expectation and with high probability. For the convex-concave setting, our stability analysis shows that stochastic gradient descent ascent attains optimal generalization bounds for both smooth and nonsmooth minimax problems. We also establish generalization bounds for both weakly-convex-weakly-concave and gradient-dominated problems. We report preliminary experimental results to verify our theory.
APA
Lei, Y., Yang, Z., Yang, T. & Ying, Y.. (2021). Stability and Generalization of Stochastic Gradient Methods for Minimax Problems. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:6175-6186 Available from https://proceedings.mlr.press/v139/lei21b.html.

Related Material