Distributed Newton Can Communicate Less and Resist Byzantine Workers

Avishek Ghosh, Raj Kumar Maity, Arya Mazumdar

TL;DR

This paper introduces COMRADE, a distributed second-order optimization algorithm that cuts communication overhead in half compared to state-of-the-art methods while providing the first-ever Byzantine resilience for Newton-type methods. By sending a single combined update vector and applying a simple norm-based filter, it achieves fast, robust convergence even when a significant fraction of worker machines are malicious.

What Problem Does This Paper Address?

In large-scale distributed learning, two major bottlenecks persist:

  1. Communication Overhead: While second-order methods (like Newton’s method) converge in fewer iterations than first-order methods (like Stochastic Gradient Descent), they typically require multiple rounds of communication per iteration to synchronize gradients and Hessians.
  2. Byzantine Failures: In massive clusters or Federated Learning environments, some "worker" machines may be faulty or malicious (Byzantine). These workers can send arbitrary or adversarial data to the central server to derail the training process.

Existing research has largely addressed these issues in isolation and primarily focused on first-order methods. The authors identify a critical gap: prior to this work, there was no second-order optimization framework that was simultaneously communication-efficient and robust against adversarial workers.

Methods

The authors propose COMRADE (COMmunication-efficient and Robust Approximate Distributed nEwton). Its core innovations include:

  • One-Round Communication: Unlike previous state-of-the-art algorithms like GIANT or DINGO, which require two sequential rounds (one for the gradient and one for the Hessian), COMRADE workers compute the local Newton update—the product of the inverse local Hessian and the local gradient ($H_i^{-1}g_i$)—and send only that single vector to the center.
  • Norm-Based Thresholding: To defend against Byzantine workers, the central machine sorts the received update vectors by their $L_2$ norm. It then "trims" (discards) a fraction $\beta$ of the workers with the largest norms. This is computationally much cheaper than the coordinate-wise median filters often used in first-order robust optimization.
  • Compression Support: COMRADE is compatible with $\rho$-approximate compressors (like QSGD or top-k sparsification), allowing workers to further reduce the number of bits sent per round without sacrificing the overall "linear-quadratic" convergence rate.

Datasets

The algorithm was evaluated using standard binary classification benchmarks from the LIBSVM library, partitioned across 20 worker machines to simulate a distributed environment:

  • a9a ($d=123, n \approx 32k$)
  • w5a ($d=300, n \approx 10k$)
  • Epsilon ($d=2000, n=0.4M$)
  • covtype.binary ($d=54, n \approx 0.5M$)

Key Insights and Ideas

  • Redundancy of Sequential Communication: The authors mathematically prove that sending gradients and Hessians separately is unnecessary. A single-round update based on local data is a sufficient proxy for the global Newton step, provided the data is "incoherent" (spread out rather than concentrated in a few samples).
  • Norm as a Proxy for Malice: In second-order methods, the norm of the update vector represents the "step size." Byzantine workers attempting to steer the model away from the optimum typically send updates with unnaturally large norms. This makes a simple norm-based filter surprisingly effective at isolating malicious actors.
  • Simultaneous Estimation: A key theoretical contribution is demonstrating that one can approximate the Hessian and gradient simultaneously in the presence of adversaries, maintaining a fast convergence rate despite the "noise" introduced by trimming and approximation.

Key Results

  • Efficiency: COMRADE achieves accuracy comparable to the state-of-the-art GIANT algorithm but uses 50% fewer communication rounds.
  • Robustness: Under "flipped label" and "negative update" attacks, standard second-order methods fail to converge. COMRADE remains resilient, significantly outperforming a "Robust GIANT" baseline that simply adds thresholding to the traditional two-round approach.
  • Convergence Rate: The paper mathematically establishes a linear-quadratic convergence rate. This means the algorithm initially converges at a steady linear rate and then speeds up quadratically as it approaches the optimal solution.
Performance of COMRADE vs. GIANT across various datasets and under different Byzantine attack scenarios.

Limitations and Future Work

  • Strong Convexity: The current theoretical guarantees are limited to strongly convex loss functions (like Logistic Regression). Extending this to non-convex landscapes, such as those found in deep neural networks, remains an open challenge.
  • Byzantine Fraction vs. Condition Number: The theory currently requires the fraction of Byzantine workers ($\alpha$) to be relatively small if the problem is ill-conditioned (high $\kappa_t$). The authors suggest that more intricate (though likely more computationally heavy) Byzantine resilience schemes might improve this dependency.
  • Privacy: The paper does not address data privacy concerns, which are paramount in Federated Learning contexts. Integrating COMRADE with differential privacy or secure multi-party computation is a highly relevant future direction.

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 an iterative approximate Newton-type algorithm, where the worker machines communicate \emph{only once} per iteration with the central machine. This is in sharp contrast with the state-of-the-art distributed second order algorithms like GIANT \cite{giant}, DINGO\cite{dingo}, where the worker machines send (functions of) local gradient and Hessian sequentially; thus ending up communicating twice with the central machine per iteration. Furthermore, we employ a simple norm based thresholding rule to filter-out the Byzantine worker machines. We establish the linear-quadratic rate of convergence of our proposed algorithm and establish that the communication savings and Byzantine resilience attributes only correspond to 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 synthetically generated and benchmark LIBSVM \cite{libsvm} data-set 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