Distributed Gradient Descent Algorithm Robust to an Arbitrary Number of Byzantine Attackers
Distributed Gradient Descent Algorithm Robust to an Arbitrary Number of Byzantine Attackers
复制标题
DOI：
10.1109/tsp.2019.2946020
复制
发表时间：
2019-10
影响因子：
5.4
通讯作者：
Xinyang Cao;L. Lai
中科院分区：
文献类型：
--
作者：
Xinyang Cao;L. Lai
由于现代数据集规模的增长以及利用多台机器的计算能力的愿望，最近人们对分布式机器学习算法的设计兴趣激增。然而，分布式算法对拜占庭攻击者很敏感，他们可以发送伪造的数据来阻止算法收敛或导致算法收敛到攻击者选择的值。最近的一些工作提出了有趣的算法，可以处理多达一半的工作人员受到威胁的情况。在本文中，我们提出了一种可以处理任意数量的拜占庭攻击者的新颖算法。主要思想是要求参数服务器随机选择一个小的干净数据集并使用这个小数据集计算噪声梯度。然后，这个噪声梯度将被用作基本事实，以过滤掉受感染的工作人员发送的信息。我们表明，无论拜占庭攻击者的数量有多少，所提出的算法都会收敛到人口最小化器的邻域。我们进一步提供数值示例来表明所提出的算法可以受益于优秀工人的存在，并获得比现有算法更好的性能。
Due to the growth of modern dataset size and the desire to harness computing power of multiple machines, there is a recent surge of interest in the design of distributed machine learning algorithms. However, distributed algorithms are sensitive to Byzantine attackers who can send falsified data to prevent the convergence of algorithms or lead the algorithms to converge to value of the attackers’ choice. Some recent work proposed interesting algorithms that can deal with the scenario when up to half of the workers are compromised. In this paper, we propose a novel algorithm that can deal with an arbitrary number of Byzantine attackers. The main idea is to ask the parameter server to randomly select a small clean dataset and compute noisy gradient using this small dataset. This noisy gradient will then be used as a ground truth to filter out information sent by compromised workers. We show that the proposed algorithm converges to the neighborhood of the population minimizer regardless the number of Byzantine attackers. We further provide numerical examples to show that the proposed algorithm can benefit from the presence of good workers and achieve better performance than existing algorithms.