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

By Xiangyi Chen, Tiancong Chen, Haoran Sun, Zhiwei Steven Wu, Mingyi Hong. 2019

89 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

Citations in the corpus

How To Backdoor Federated Learning (2018, background): “Similar performance gap is described in recent work [11].”
Salvaging Federated Learning by Local Adaptation (2020, background): “To ensure that malicious participants and other outliers cannot inﬂu-ence the joint model, robust aggregation replaces average by median (Yin et al., 2018; Chen et al., 2019): where ˜ P t is the element-wise median among the updates submitted in round t .”
Mitigating Byzantine Attacks in Federated Learning (2020, background): “In [11], the authors propose a noisy median approach that can improve the performance of the median algorithm (proposed in [9]) in heterogeneous data settings.”
Federated Machine Learning: Survey, Multi-Level Classification, Desirable Criteria and Future Directions in Communication and Networking Systems (2021, background): “In [70], the parameter subject to correction is each client’s local gradient and”