Distributed Approximate Newton's Method Robust to Byzantine Attackers
Distributed Approximate Newton's Method Robust to Byzantine Attackers
复制标题
DOI：
10.1109/tsp.2020.3029461
复制
发表时间：
2020
影响因子：
5.4
通讯作者：
Xinyang Cao;L. Lai
中科院分区：
文献类型：
--
作者：
Xinyang Cao;L. Lai
最近人们对一阶和二阶分布式机器学习算法的设计产生了浓厚的兴趣。然而，分布式算法对拜占庭攻击者很敏感，拜占庭攻击者可以发送伪造信息来阻止算法收敛或导致算法收敛到攻击者选择的值。最近的一些工作已经提出了一阶方法可以防御拜占庭攻击者的算法。本文针对二阶方法设计了两种处理拜占庭攻击的算法。第一种算法称为基于中位数的近似牛顿法（MNM），其主要思想是要求参数服务器聚合梯度信息，并通过几何中位数从所有工人中近似牛顿方向。我们证明，当多达一半的工人是拜占庭攻击者时，MNM可以收敛。为了处理任意数量攻击者的情况，我们提出了一种基于比较的近似牛顿方法（CNM）。CNM的主要思想是要求服务器随机选择一个小的干净数据集，并使用这个小数据集计算噪声梯度和牛顿方向。然后，这些噪声信息将被用作地面真实值的近似值，以过滤掉来自拜占庭攻击者的不良信息。我们证明，即使超过一半的工人是拜占庭工人，CNM也可以收敛到人口最小值的邻域。我们还提供了数值例子来说明所提出算法的性能。
There is a recent surge of interest in the design of the first-order and the second-order distributed machine learning algorithms. However, distributed algorithms are sensitive to Byzantine attackers who can send falsified information to prevent the convergence of algorithms or lead the algorithms to converge to value of the attackers’ choice. Some recent works have proposed algorithms that can defend against Byzantine attackers for the first-order methods. In this paper, we design two algorithms that can deal with Byzantine attackers for the second-order methods. The main idea of the first algorithm, named median-based approximate Newton's method (MNM), is to ask the parameter server to aggregate gradient information and approximate Newton's direction from all workers by geometric median. We show that MNM can converge when up to half of the workers are Byzantine attackers. To deal with the case with an arbitrary number of attackers, we then propose a comparison-based approximate Newton's method (CNM). The main idea of CNM is to ask the server to randomly select a small clean dataset and compute noisy gradient and Newton's direction using this small dataset. These noisy information will then be used as an approximation of the ground truth to filter out bad information from Byzantine attackers. We show that CNM can converge to the neighborhood of the population minimizer even when more than half of the workers are Byzantine workers. We further provide numerical examples to illustrate the performance of the proposed algorithms.