Distributed Newton Can Communicate Less and Resist Byzantine Workers

Avishek Ghosh, Raj Kumar Maity, Arya Mazumdar

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 and DINGO, 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 data-sets and demonstrate convergence guarantees.

The Challenge: Communication and Security in Distributed Learning

Modern machine learning often relies on distributed training across clusters of worker machines. However, this approach faces two primary hurdles. First, the communication bottleneck: while second-order (Newton-type) methods converge in fewer iterations than gradient descent, they typically require workers to send both gradients and Hessians, necessitating multiple rounds of communication per step. Second, the Byzantine threat: in large-scale or Federated Learning environments, faulty or malicious workers can send strategically harmful data to the central server, potentially derailing the entire training process.

Existing research has largely addressed these issues in isolation. COMRADE is introduced as the first second-order optimization framework that is simultaneously communication-efficient and robust against Byzantine attacks.

The COMRADE Framework

COMRADE (COMunication-efficient and Robust Approximate Distributed nEwton) introduces several core innovations to optimize distributed training:

  • One-Round Communication: Unlike state-of-the-art algorithms like GIANT, which communicate twice per iteration, COMRADE workers compute a local Newton update (the product of the inverse local Hessian and the local gradient) and send only that $d$-dimensional vector to the center. This effectively cuts communication overhead in half.
  • Norm-based Thresholding: To mitigate Byzantine workers, the central machine employs a simple trimming strategy. It calculates the $L_2$ norm of all received updates, sorts them, and discards the fraction of updates with the largest norms. This is based on the observation that malicious actors often must send high-magnitude updates to successfully steer the model away from the optimum.
  • Information Compression: The algorithm supports $ ho$-approximate compressors, allowing workers to further reduce data size via quantization (e.g., QSGD) or sparsification before transmission.
  • Theoretical Grounding: Using matrix sketching and concentration inequalities, the authors prove that the average of these local updates remains a reliable proxy for the true global Newton step, maintaining a linear-quadratic convergence rate.

Empirical Evaluation and Key Results

The authors validated COMRADE using standard LIBSVM benchmark datasets, including w5a, a9a, Epsilon, and covtype.binary.

Convergence and Stability

In clean environments, COMRADE matches the accuracy of the GIANT algorithm while using 50% less bandwidth. Furthermore, COMRADE often exhibits superior stability. On the a9a dataset, for instance, standard distributed Newton methods can experience significant instability or oscillations, whereas COMRADE maintains a smooth convergence path.

Figure 1: Accuracy vs. Iterations on the a9a dataset, showing COMRADE's superior stability compared to the oscillations of the GIANT algorithm.

Robustness Against Byzantine Attacks

COMRADE's resilience was tested against "flipped label" attacks and "negative update" attacks (where workers send the opposite of the correct direction). While non-robust algorithms like GIANT fail completely under these conditions—often failing to improve accuracy beyond a baseline level—COMRADE remains stable and accurate.

Figure 2: The failure of the standard GIANT algorithm under a 'negative' Byzantine attack, where accuracy remains near baseline levels regardless of the percentage of malicious workers.

Conclusion

COMRADE demonstrates that distributed second-order methods can be both faster and more secure. By reducing communication to a single round and implementing a computationally inexpensive norm-based filter, it provides a robust solution for large-scale distributed optimization. While the current framework assumes strong convexity, it sets a new precedent for Byzantine resilience in high-order optimization methods.

Summary updated

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.
BibTeX
@inproceedings{ghosh2020distributed,
  author = {Avishek Ghosh and Raj Kumar Maity and Arya Mazumdar},
  title = {{Distributed Newton Can Communicate Less and Resist Byzantine Workers}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=_mLyE8NH_f},
}
Figure