Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data
Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data
复制标题
DOI：
10.1109/isit45174.2021.9518248
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Deepesh Data;S. Diggavi
中科院分区：
文献类型：
--
作者：
Deepesh Data;S. Diggavi
研究了拜占庭攻击下主从式结构中的分布式随机梯度下降(SGD)问题。我们考虑了异质数据模型，其中不同的工作者可能具有不同的本地数据集，并且我们不对数据生成做出任何概率假设。在算法的核心部分，我们使用Steinhardt等人提出的多项式时间野值滤波方法进行稳健均值估计。(ITCS 2018)，以过滤掉损坏的渐变。为了能够在工作人员计算随机梯度的异类数据环境中应用他们的过滤过程，我们推导出了一个新的矩阵集中结果，这可能是独立感兴趣的。我们给出了光滑、强凸和非凸目标的收敛分析，并证明了在无拜占庭环境下，我们的收敛速度与Vanilla SGD的收敛速度相当。为了界定异质性，我们假设不同工作者的梯度彼此之间存在有界偏差，并在统计异质性数据模型中给出了这种偏差的具体界。
We study distributed stochastic gradient descent (SGD) in the master-worker architecture under Byzantine attacks. We consider the heterogeneous data model, where different workers may have different local datasets, and we do not make any probabilistic assumptions on data generation. At the core of our algorithm, we use the polynomial-time outlier-filtering procedure for robust mean estimation proposed by Steinhardt et al. (ITCS 2018) to filter-out corrupt gradients. In order to be able to apply their filtering procedure in our heterogeneous data setting where workers compute stochastic gradients, we derive a new matrix concentration result, which may be of independent interest. We provide convergence analyses for smooth strongly-convex and non-convex objectives and show that our convergence rates match that of vanilla SGD in the Byzantine-free setting. In order to bound the heterogeneity, we assume that the gradients at different workers have bounded deviation from each other, and we also provide concrete bounds on this deviation in the statistical heterogeneous data model.