# Distributed Newton Can Communicate Less and Resist Byzantine Workers

arXiv: https://arxiv.org/abs/2006.08737 · HTML: https://mlsanity.com/paper/2006.08737/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2020.

## Built on by (most cited first, 20 of 20)

- [Exploiting Heterogeneity in Robust Federated Best-Arm Identification](https://mlsanity.com/paper/2109.05700/) (2021)
- [LocalNewton: Reducing Communication Bottleneck for Distributed Learning](https://mlsanity.com/paper/2105.07320/) (2021)
- [Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Rates](https://mlsanity.com/paper/2310.09804/) (2023)
- [Over-the-Air Federated Learning via Second-Order Optimization](https://mlsanity.com/paper/2203.15488/) (2022)
- [Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation](https://mlsanity.com/paper/2206.03588/) (2022)
- [Advancements in Federated Learning: Models, Methods, and Privacy](https://mlsanity.com/paper/2302.11466/) (2023)
- [Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds](https://mlsanity.com/paper/2206.02834/) (2022)
- [Distributed Quasi-Newton Method for Fair and Fast Federated Learning](https://mlsanity.com/paper/2501.10877/) (2025)
- [FedREP: A Byzantine-Robust, Communication-Efficient and Privacy-Preserving Framework for Federated Learning](https://mlsanity.com/paper/2303.05206/) (2023)
- [Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience](https://mlsanity.com/paper/2103.09424/) (2021)
- [Fundamental limits of over-the-air optimization: Are analog schemes optimal?](https://mlsanity.com/paper/2109.05222/) (2021)
- [FedNS: A Fast Sketching Newton-Type Algorithm for Federated Learning](https://mlsanity.com/paper/2401.02734/) (2024)
- [Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Top](https://mlsanity.com/paper/2206.00529/) (2022)
- [Stochastic Alternating Direction Method of Multipliers for Byzantine-Robust Distributed Learning](https://mlsanity.com/paper/2106.06891/) (2021)
- [Optimal Compression of Unit Norm Vectors in the High Distortion Regime](https://mlsanity.com/paper/2307.07941/) (2023)
- [GP-FL: Model-Based Hessian Estimation for Second-Order Over-the-Air Federated Learning](https://mlsanity.com/paper/2412.03867/) (2024)
- [Robust Distributed Learning Against Both Distributional Shifts and Byzantine Attacks](https://mlsanity.com/paper/2210.16682/) (2022)
- [Efficient Federated Low Rank Matrix Completion](https://mlsanity.com/paper/2405.06569/) (2024)
- [FLeNS: Federated Learning with Enhanced Nesterov-Newton Sketch](https://mlsanity.com/paper/2409.15216/) (2024)
- [From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization under Similarity](https://mlsanity.com/paper/2602.03329/) (2026)

## Abstract (arXiv)

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.