# Distributed Training with Heterogeneous Data: Bridging Median- and Mean-Based Algorithms

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2019.

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

- [SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification](https://mlsanity.com/paper/2112.06274/) (2021)
- [Recent Advances on Federated Learning: A Systematic Survey](https://mlsanity.com/paper/2301.01299/) (2023)
- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective](https://mlsanity.com/paper/2111.03741/) (2021)
- [Auto-FedAvg: Learnable Federated Averaging for Multi-Institutional Medical Image Segmentation](https://mlsanity.com/paper/2104.10195/) (2021)
- [Robust Federated Learning with Attack-Adaptive Aggregation](https://mlsanity.com/paper/2102.05257/) (2021)
- [z-SignFedAvg: A Unified Stochastic Sign-based Compression for Federated Learning](https://mlsanity.com/paper/2302.02589/) (2023)
- [Auto-FedRL: Federated Hyperparameter Optimization for Multi-institutional Medical Image Segmentation](https://mlsanity.com/paper/2203.06338/) (2022)
- [Maximizing Communication Efficiency for Large-scale Training via 0/1 Adam](https://mlsanity.com/paper/2202.06009/) (2022)
- [Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction](https://mlsanity.com/paper/2406.00489/) (2024)
- [FedBAT: Communication-Efficient Federated Learning via Learnable Binarization](https://mlsanity.com/paper/2408.03215/) (2024)
- [Stability Based Generalization Bounds for Exponential Family Langevin Dynamics](https://mlsanity.com/paper/2201.03064/) (2022)
- [Dim-Krum: Backdoor-Resistant Federated Learning for NLP with Dimension-wise Krum-Based Aggregation](https://mlsanity.com/paper/2210.06894/) (2022)
- [A Secure Federated Learning Framework for Residential Short Term Load Forecasting](https://mlsanity.com/paper/2209.14547/) (2022)
- [SignSVRG: fixing SignSGD via variance reduction](https://mlsanity.com/paper/2305.13187/) (2023)
- [Federated Learning via Plurality Vote](https://mlsanity.com/paper/2110.02998/) (2021)
- [Distributed Non-Convex Optimization with One-Bit Compressors on Heterogeneous Data: Efficient and Resilient Algorithms](https://mlsanity.com/paper/2210.00665/) (2022)
- [Personalised Federated Learning: A Combinational Approach](https://mlsanity.com/paper/2108.09618/) (2021)
- [Breaking the Communication-Privacy-Accuracy Tradeoff with f-Differential Privacy](https://mlsanity.com/paper/2302.09624/) (2023)
- [Magnitude Matters: Fixing SIGNSGD Through Magnitude-Aware Sparsification in the Presence of Data Heterogeneity](https://mlsanity.com/paper/2302.09634/) (2023)
- [Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/2310.15976/) (2023)
- [TernaryVote: Differentially Private, Communication Efficient, and Byzantine Resilient Distributed Optimization on Heterogeneous Data](https://mlsanity.com/paper/2402.10816/) (2024)
- [Byzantine-Robust Federated Learning via Credibility Assessment on Non-IID Data](https://mlsanity.com/paper/2109.02396/) (2021)
- [Attacking Byzantine Robust Aggregation in High Dimensions](https://mlsanity.com/paper/2312.14461/) (2023)
- [SignSGD with Federated Defense: Harnessing Adversarial Attacks through Gradient Sign Decoding](https://mlsanity.com/paper/2402.01340/) (2024)
- [Collaborative Compressors in Distributed Mean Estimation with Limited Communication Budget](https://mlsanity.com/paper/2601.18950/) (2026)
- [FedGraph: an Aggregation Method from Graph Perspective](https://mlsanity.com/paper/2210.02733/) (2022)
- [Aggressive or Imperceptible, or Both: Network Pruning Assisted Hybrid Byzantines in Federated Learning](https://mlsanity.com/paper/2404.06230/) (2024)
- [Sign compression for Muon: SignMuon, MuonSign, and the Limits of Error Feedback](https://mlsanity.com/paper/2607.29674/) (2026)

## Abstract (arXiv)

Recently, there is a growing interest in the study of median-based algorithms for distributed non-convex optimization. Two prominent such algorithms include signSGD with majority vote, an effective approach for communication reduction via 1-bit compression on the local gradients, and medianSGD, an algorithm recently proposed to ensure robustness against Byzantine workers. The convergence analyses for these algorithms critically rely on the assumption that all the distributed data are drawn iid from the same distribution. However, in applications such as Federated Learning, the data across different nodes or machines can be inherently heterogeneous, which violates such an iid assumption. This work analyzes signSGD and medianSGD in distributed settings with heterogeneous data. We show that these algorithms are non-convergent whenever there is some disparity between the expected median and mean over the local gradients. To overcome this gap, we provide a novel gradient correction mechanism that perturbs the local gradients with noise, together with a series results that provable close the gap between mean and median of the gradients. The proposed methods largely preserve nice properties of these methods, such as the low per-iteration communication complexity of signSGD, and further enjoy global convergence to stationary solutions. Our perturbation technique can be of independent interest when one wishes to estimate mean through a median estimator.