Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
复制标题
DOI：
10.1145/3219617.3219655
复制
发表时间：
2017-12
期刊：
影响因子：
--
通讯作者：
Yudong Chen;Lili Su;Jiaming Xu
中科院分区：
文献类型：
--
作者：
Yudong Chen;Lili Su;Jiaming Xu
我们考虑容易受到对抗性攻击的去中心化系统的分布式统计学习问题。这种设置出现在许多实际应用中，包括Google的Federated Learning。形式上，我们关注的是一个分散的系统，它由一个参数服务器和m台工作机器组成;每台工作机器保存N/m个数据样本，其中N是样本的总数。在每次迭代中，m台工作机器中最多有q台遭受拜占庭故障-给定迭代中的故障机器对系统的行为任意恶劣，并且具有系统的完整知识。此外，故障机器的集合在迭代中可能不同。我们的目标是设计强大的算法，使系统可以学习的基本真参数，这是D维，尽管中断的拜占庭攻击。在本文中，基于几何中值的平均梯度，我们提出了一个简单的变种的经典梯度下降法。我们表明，我们的方法可以容忍q拜占庭故障高达2（1+ε）q e m的一个任意小，但固定常数ε>0。参数估计收敛于O（N）轮，估计误差的数量级为max dq/N，~ d/N，这是大于最小最大最优错误率d/N在集中式和无故障设置的最多一个因素q。该算法的总计算复杂度为O（（Nd/m）log N），总通信开销为O（m d log N）.我们进一步提供了我们的一般结果的线性回归问题的应用。上述问题中出现的关键挑战是拜占庭故障在迭代和聚合梯度之间创建任意和未指定的依赖性。为了处理这个问题的分析，我们证明了聚合梯度，作为模型参数的函数，一致收敛到真正的梯度函数。
We consider the distributed statistical learning problem over decentralized systems that are prone to adversarial attacks. This setup arises in many practical applications, including Google's Federated Learning. Formally, we focus on a decentralized system that consists of a parameter server and m working machines; each working machine keeps N/m data samples, where N is the total number of samples. In each iteration, up to q of the m working machines suffer Byzantine faults -- a faulty machine in the given iteration behaves arbitrarily badly against the system and has complete knowledge of the system. Additionally, the sets of faulty machines may be different across iterations. Our goal is to design robust algorithms such that the system can learn the underlying true parameter, which is of dimension d, despite the interruption of the Byzantine attacks. In this paper, based on the geometric median of means of the gradients, we propose a simple variant of the classical gradient descent method. We show that our method can tolerate q Byzantine failures up to 2(1+ε)q łe m for an arbitrarily small but fixed constant ε>0. The parameter estimate converges in O(łog N) rounds with an estimation error on the order of max √dq/N, ~√d/N , which is larger than the minimax-optimal error rate √d/N in the centralized and failure-free setting by at most a factor of √q . The total computational complexity of our algorithm is of O((Nd/m) log N) at each working machine and O(md + kd log 3 N) at the central server, and the total communication cost is of O(m d log N). We further provide an application of our general results to the linear regression problem. A key challenge arises in the above problem is that Byzantine failures create arbitrary and unspecified dependency among the iterations and the aggregated gradients. To handle this issue in the analysis, we prove that the aggregated gradient, as a function of model parameter, converges uniformly to the true gradient function.