Stability and Generalization of Stochastic Gradient Methods for Minimax Problems
Stability and Generalization of Stochastic Gradient Methods for Minimax Problems
复制标题
DOI：
--
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Yunwen Lei;Zhenhuan Yang;Tianbao Yang;Yiming Ying
中科院分区：
文献类型：
--
作者：
Yunwen Lei;Zhenhuan Yang;Tianbao Yang;Yiming Ying
许多机器学习问题都可以被公式化为极大极小问题，例如生成对抗网络（GAN），AUC最大化和鲁棒估计，仅举几例。大量的研究致力于研究其随机梯度型算法的收敛行为。相比之下，关于其推广的工作相对较少，即，从训练示例构建的学习模型如何在测试示例上表现。本文通过算法稳定性的透镜，对求解极大极小问题的随机梯度法在凸-凹和非凸-非凹两种情况下进行了全面的推广分析.我们建立了稳定性和几个推广措施的期望和高概率之间的定量联系。对于凹凸环境，我们的稳定性分析表明，随机梯度下降上升对于光滑和非光滑极大极小问题都达到了最佳推广界。我们还建立了推广的弱凸弱凹和梯度控制问题的界限。
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 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.