论文标题
分布式牛顿可以更少的交流并抵抗拜占庭工人
Distributed Newton Can Communicate Less and Resist Byzantine Workers
论文作者
论文摘要
我们开发了一种分布式的二阶优化算法，该算法是沟通有效的，并且对工具机器的拜占庭故障进行了鲁棒性。我们提出了同志（迭代二阶算法的共同效率且健壮的近似分布式牛顿），在该算法中，工具机器仅通过迭代一次与中心机器进行一次通信。这与最先进的分布式二阶算法（如Giant [34]和Dingo [7]）形成鲜明对比，该算法是工具机依次发送（功能）局部梯度和Hessian。因此，根据迭代，最终与中央机器进行了两次通信。此外，我们表明，工具机器可以在将其发送到中心之前进一步压缩本地信息。此外，我们采用一个简单的基于规范的阈值规则来过滤拜占庭工人的机器。我们建立了同志收敛的线性季度次数，并确定通信节省和拜占庭的弹性仅导致任意凸损失函数的统计错误率很小。据我们所知，这是第一项解决次要分布优化的拜占庭弹性问题的工作。此外，我们通过对合成和基准LIBSVM的广泛实验来验证我们的理论结果[5]数据集，并证明了收敛的保证。
We develop a distributed second order optimization algorithm that is communication-efficient as well as robust against Byzantine failures of the worker machines. We propose COMRADE (COMunication-efficient and Robust Approximate Distributed nEwton), an iterative second order algorithm, where the worker machines communicate only once per iteration with the center machine. This is in sharp contrast with the state-of-the-art distributed second order algorithms like GIANT [34] and DINGO[7], where the worker machines send (functions of) local gradient and Hessian sequentially; thus ending up communicating twice with the center machine per iteration. Moreover, we show that the worker machines can further compress the local information before sending it to the center. In addition, we employ a simple norm based thresholding rule to filter-out the Byzantine worker machines. We establish the linear-quadratic rate of convergence of COMRADE and establish that the communication savings and Byzantine resilience result in only a small statistical error rate for arbitrary convex loss functions. To the best of our knowledge, this is the first work that addresses the issue of Byzantine resilience in second order distributed optimization. Furthermore, we validate our theoretical results with extensive experiments on synthetic and benchmark LIBSVM [5] data-sets and demonstrate convergence guarantees.
