Distributed Newton Can Communicate Less and Resist Byzantine Workers

Abstract

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.

References in corpus (15)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• The Hidden Vulnerability of Distributed Learning in Byzantium
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Sparsified SGD with Memory
• ATOMO: Communication-efficient Learning via Atomic Sparsification
• Robust Federated Learning in a Heterogeneous Environment
• Distributed Mean Estimation with Limited Communication
• AIDE: Fast and Communication Efficient Distributed Optimization
• DINGO: Distributed Newton-Type Method for Gradient-Norm Optimization
• Distributed Robust Learning
• Byzantine-Tolerant Machine Learning
• Distributed estimation of the inverse Hessian by determinantal averaging

Cited by in corpus (2)

• LocalNewton: Reducing Communication Bottleneck for Distributed Learning
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification