A Faster Decentralized Algorithm for Nonconvex Minimax Problems
A Faster Decentralized Algorithm for Nonconvex Minimax Problems
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Wenhan Xian;Feihu Huang;Yanfu Zhang;Heng Huang
中科院分区：
文献类型：
--
作者：
Wenhan Xian;Feihu Huang;Yanfu Zhang;Heng Huang
本文研究了分散设置下的非凸-强-凹极大极小优化问题。极大极小问题因其在策略评估、对抗训练等方面的广泛应用而受到越来越多的关注。随着训练数据变得越来越大，分布式训练已被广泛用于机器学习任务。最近的研究工作表明，分散的分布式数据并行训练技术特别有前途，因为它可以实现有效的通信，避免中心节点的瓶颈问题或低带宽网络的延迟。然而，分散minimax问题在文献中研究很少，现有的方法具有很高的梯度复杂度。为了解决这个问题，我们提出了一个新的更快的分散算法，命名为DM-HSGD，非凸极大极小问题，通过使用混合随机梯度下降的方差降低技术。我们证明了我们的DM-HSGD算法对于分散随机非凸-强凹问题搜索（cid：15）-平稳点的随机一阶预言（SFO）复杂度为O（κ 3（cid：15）− 3），改进了现有的最佳理论结果.此外，我们还证明了我们的算法相对于工人的数量实现线性加速比。我们的分散设置的实验表明，我们的新算法的上级性能。
In this paper, we study the nonconvex-strongly-concave minimax optimization problem on decentralized setting. The minimax problems are attracting increasing attentions because of their popular practical applications such as policy evaluation and adversarial training. As training data become larger, distributed training has been broadly adopted in machine learning tasks. Recent research works show that the decentralized distributed data-parallel training techniques are specially promising, because they can achieve the efficient communications and avoid the bottleneck problem on the central node or the latency of low bandwidth network. However, the decentralized minimax problems were seldom studied in literature and the existing methods suffer from very high gradient complexity. To address this challenge, we propose a new faster decentralized algorithm, named as DM-HSGD, for nonconvex minimax problems by using the variance reduced technique of hybrid stochastic gradient descent. We prove that our DM-HSGD algorithm achieves stochastic first-order oracle (SFO) complexity of O ( κ 3 (cid:15) − 3 ) for decentralized stochastic nonconvex-strongly-concave problem to search an (cid:15) -stationary point, which improves the exiting best theoretical results. Moreover, we also prove that our algorithm achieves linear speedup with respect to the number of workers. Our experiments on decentralized settings show the superior performance of our new algorithm.