Efficient Mirror Descent Ascent Methods for Nonsmooth Minimax Problems
Efficient Mirror Descent Ascent Methods for Nonsmooth Minimax Problems
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Feihu Huang;Xidong Wu;Heng Huang
中科院分区：
文献类型：
--
作者：
Feihu Huang;Xidong Wu;Heng Huang
在本文中，我们提出了一类有效的镜像下降上升方法，通过使用动态镜像函数来解决非光滑非凸强凹极小极大问题，并引入收敛分析框架来对我们的镜像下降上升方法进行严格的理论分析。对于我们的随机算法，我们首先证明小批量随机镜像下降上升 (SMDA) 方法获得 O ( κ 3 (cid:15) − 4 ) 的样本复杂度来查找 (cid:15) 驻点，其中 κ 表示条件数。此外，我们提出了一种基于方差减少技术的加速随机镜像下降上升（VR-SMDA）方法。我们证明我们的 VR-SMDA 方法实现了较低的样本复杂度 G O ( κ 3 (cid:15) − 3 ) 。对于我们的确定性算法，我们证明确定性镜像下降上升 (MDA) 在温和条件下实现了较低的 O ( κ(cid:15) − 2 ) 样本复杂度，这将已知的复杂度提高了 O ( √ κ ) 倍。我们在公平分类器和鲁棒神经网络训练任务上进行了实验，以证明我们新算法的效率。
In the paper, we propose a class of efficient mirror descent ascent methods to solve the nonsmooth nonconvex-strongly-concave minimax problems by using dynamic mirror functions, and introduce a convergence analysis framework to conduct rigorous theoretical analysis for our mirror descent ascent methods. For our stochastic algorithms, we first prove that the mini-batch stochastic mirror descent ascent (SMDA) method obtains a sample complexity of O ( κ 3 (cid:15) − 4 ) for finding an (cid:15) -stationary point, where κ denotes the condition number. Further, we propose an accelerated stochastic mirror descent ascent (VR-SMDA) method based on the variance reduced technique. We prove that our VR-SMDA method achieves a lower sample complexity G O ( κ 3 (cid:15) − 3 ) . For our deterministic algorithm, we prove that our deterministic mirror descent ascent (MDA) achieves a lower sample complexity of O ( κ(cid:15) − 2 ) under mild conditions, which improves the best known complexity by a factor of O ( √ κ ) . We conduct the experiments on fair classifier and robust neural network training tasks to demonstrate the efficiency of our new algorithms.