Coordinate-wise median in Byzantine federated learning

Federated learning enables clients to train local models on private data while exchanging model updates only. A key step in this process is gradient aggregation. We investigate the coordinate-wise median as an aggregation rule in both centralized and decentralized federated learning under Byzantine failures. In order to lower the communication cost in the decentralized setting, we allow clients to agree approximately on model parameters, which is referred to as approximate agreement problem. We propose two aggregation algorithms for centralized coordinate-wise median aggregation: the Minimum Diameter (MD) algorithm and the Hyperbox algorithm. We prove that both satisfy the box validity condition and can tolerate up to 𝑛3 and 𝑛2 Byzantine clients, respectively. We further show that only the Hyperbox algorithm can be generalized to the decentralized setting. Through empirical evaluation, we demonstrate that the MD algorithm with coordinate-wise median aggregation is more resilient to sign-flip attacks than its mean-based counterpart, highlighting the robustness of median-based aggregation in adversarial environments.