Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learning
Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learning
复制标题
DOI：
10.1109/isit50566.2022.9834691
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Ziyi Chen;Shaocong Ma;Yi Zhou
中科院分区：
文献类型：
--
作者：
Ziyi Chen;Shaocong Ma;Yi Zhou
交替梯度下降-上升（AltGDA）是一种优化算法，已广泛用于各种机器学习应用中的模型训练，旨在解决非凸极小极大优化问题。然而，现有的研究表明，非凸极小极大优化存在较高的计算复杂度。在本文中，我们开发了一种单循环快速 AltGDA 型算法，该算法利用近端梯度更新和动量加速来解决正则化非凸极小极大优化问题。通过利用动量加速技术，我们证明该算法收敛到非凸极小极大优化中的临界点，并实现了 $\mathcal{O}\left( {{\kappa ^{\frac{{11}}{6}}}{\varepsilon ^{ - 2}}} \right)$ 量级的计算复杂度，其中 ϵ 是所需的精度水平，κ 是问题的条件数。这种计算复杂性提高了单循环 GDA 和 AltGDA 算法的最先进复杂性（参见表 I 中的比较总结）。我们通过对抗性深度学习实验证明了我们算法的有效性。
Alternating gradient-descent-ascent (AltGDA) is an optimization algorithm that has been widely used for model training in various machine learning applications, which aims to solve a nonconvex minimax optimization problem. However, the existing studies show that it suffers from a high computation complexity in nonconvex minimax optimization. In this paper, we develop a single-loop and fast AltGDA-type algorithm that leverages proximal gradient updates and momentum acceleration to solve regularized nonconvex minimax optimization problems. By leveraging the momentum acceleration technique, we prove that the algorithm converges to a critical point in nonconvex minimax optimization and achieves a computation complexity in the order of $\mathcal{O}\left( {{\kappa ^{\frac{{11}}{6}}}{\varepsilon ^{ - 2}}} \right)$, where ϵ is the desired level of accuracy and κ is the problem’s condition number. Such a computation complexity improves the state-of-the-art complexities of single-loop GDA and AltGDA algorithms (see the summary of comparison in Table I). We demonstrate the effectiveness of our algorithm via an experiment on adversarial deep learning.