Securing Distributed Gradient Descent in High Dimensional Statistical Learning
Securing Distributed Gradient Descent in High Dimensional Statistical Learning
复制标题
DOI：
10.1145/3309697.3331499
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Lili Su;Jiaming Xu
中科院分区：
文献类型：
--
作者：
Lili Su;Jiaming Xu
我们认为不可靠的分布式学习系统中，训练数据由外部工人保密，学习者必须与这些工人密切交互才能训练模型。特别是，我们假设存在一个系统对手，它可以自适应地危害某些工人；受危害的工人通过发送任意恶意消息来偏离其本地设计的规范。我们假设，在每一轮通信中，m名员工中有多达Q人遭遇拜占庭式的失误。每个工人保存一个大小为n的本地样本，总样本大小为$N=nm$。我们提出了一种安全的梯度下降法，它可以容忍固定比例的拜占庭工人，即$Q/m=O(1)$。此外，我们还证明了迭代的统计估计误差在$O(łog N)$轮内收敛到$O(\SQRTQ/N+\SQRTD/N)$，其中d是模型的维度。只要$q=O(D)$，我们提出的算法就可以获得最优的误码率$O(\sqrtd/N)$。我们的结果是在一些技术假设下得到的。具体地说，我们假设人口风险是强凸的。然而，经验风险(样本版本)被允许是非凸性的。该方法的核心是基于Steinhardt等人提出的滤波过程对工作人员计算的梯度进行稳健聚合。\cieSteinhardt18.在技术方面，与已有的关于稳健估计有限维均值向量的文献不同，我们建立了样本梯度协方差矩阵的一致集中，并证明了作为模型参数的函数的聚集梯度一致收敛于真梯度函数。为了得到一个接近最优的均匀浓度界，我们发展了一个新的矩阵浓度不等式，它可能是独立感兴趣的。
We consider unreliable distributed learning systems wherein the training data is kept confidential by external workers, and the learner has to interact closely with those workers to train a model. In particular, we assume that there exists a system adversary that can adaptively compromise some workers; the compromised workers deviate from their local designed specifications by sending out arbitrarily malicious messages. We assume in each communication round, up to q out of the m workers suffer Byzantine faults. Each worker keeps a local sample of size n and the total sample size is $N=nm$. We propose a secured variant of the gradient descent method that can tolerate up to a constant fraction of Byzantine workers, i.e., $q/m = O(1)$. Moreover, we show the statistical estimation error of the iterates converges in $O(łog N)$ rounds to $O(\sqrtq/N + \sqrtd/N )$, where d is the model dimension. As long as $q=O(d)$, our proposed algorithm achieves the optimal error rate $O(\sqrtd/N )$. Our results are obtained under some technical assumptions. Specifically, we assume strongly-convex population risk. Nevertheless, the empirical risk (sample version) is allowed to be non-convex. The core of our method is to robustly aggregate the gradients computed by the workers based on the filtering procedure proposed by Steinhardt et al. \citeSteinhardt18. On the technical front, deviating from the existing literature on robustly estimating a finite-dimensional mean vector, we establish a \em uniform concentration of the sample covariance matrix of gradients, and show that the aggregated gradient, as a function of model parameter, converges uniformly to the true gradient function. To get a near-optimal uniform concentration bound, we develop a new matrix concentration inequality, which might be of independent interest.