Source-linked AI summary
The Non-IID Data Quagmire of Decentralized Machine Learning
Kevin Hsieh, Amar Phanishayee, Onur Mutlu, Phillip B. Gibbons
TL;DR
Decentralized learning must train over distributed data whose contexts create non-IID label distributions, but the resulting challenge has been understudied. The paper conducts a broad empirical study, presents SkewScout to adapt communication to skew-induced accuracy loss, and evaluates group normalization as an alternative to batch normalization. It finds that label skew broadly reduces accuracy, especially for batch-normalized DNNs, with difficulty determined by skew degree.
Problem
Distributed data commonly has skewed label distributions across devices and locations, creating an important but understudied challenge for decentralized learning.
Method
The paper performs a detailed study across applications, DNNs, datasets, algorithms, and skew levels, and presents SkewScout plus GroupNorm as approaches addressing the challenge.
Results
Skewed label partitions cause major accuracy loss across the studied settings, batch-normalized DNNs are particularly vulnerable, and difficulty increases with skew degree.
Takeaways & Limitations
Communication frequency can be adapted to skew-induced accuracy loss, while GroupNorm can recover much of BatchNorm’s accuracy loss under the studied non-IID setting.
Takeaways & Limitations
More study is needed to determine whether GroupNorm can replace BatchNorm across different applications and DNN models.
Abstract
from arXiv · showhide
Many large-scale machine learning (ML) applications need to perform decentralized learning over datasets generated at different devices and locations. Such datasets pose a significant challenge to decentralized learning because their different contexts result in significant data distribution skew across devices/locations. In this paper, we take a step toward better understanding this challenge by presenting a detailed experimental study of decentralized DNN training on a common type of data skew: skewed distribution of data labels across devices/locations. Our study shows that: (i) skewed data labels are a fundamental and pervasive problem for decentralized learning, causing significant accuracy loss across many ML applications, DNN models, training datasets, and decentralized learning algorithms; (ii) the problem is particularly challenging for DNN models with batch normalization; and (iii) the degree of data skew is a key determinant of the difficulty of the problem. Based on these findings, we present SkewScout, a system-level approach that adapts the communication frequency of decentralized learning algorithms to the (skew-induced) accuracy loss between data partitions. We also show that group normalization can recover much of the accuracy loss of batch normalization.
1. Introduction
Decentralized learning addresses privacy, communication, and data-locality constraints, but skewed labels across partitions create a pervasive accuracy challenge. The study evaluates this challenge broadly and introduces dataset and system-level contributions.
- Centralizing data from devices worldwide can be impractical because of communication, privacy, and data-sovereignty constraints.
- Decentralized learning trains models over distributed data, but traditional centralized-data approaches require massive communication and can be slowed by limited network bandwidth.
- The study examines skewed label distributions across devices and locations across diverse applications, DNNs, datasets, algorithms, and skew degrees.
- Skewed label partitions cause major model-quality loss across the decentralized learning algorithms, applications, models, and datasets studied.
- DNNs with batch normalization remain particularly vulnerable under BSP, while the difficulty increases with the degree of label skew.
- The paper releases a real-world geo-tagged Flickr mammal dataset and introduces SkewScout, which adapts communication frequency to skew-induced accuracy loss.
2. Background and Motivation
The paper motivates label skew with geographically and contextually heterogeneous data, then frames decentralized learning algorithms and BSP around the communication–model-quality trade-off. Its Flickr-Mammal dataset provides a real-world example of strongly differing regional label distributions.
- Decentralized learning is motivated by distributed data that is impractical to centralize, while non-IID partitions arise because devices and locations generate data in different contexts.
- The study evaluates Gaia, FederatedAveraging, and DeepGradientCompression, which reduce communication through different update-sharing or local-training strategies.
- BSP shares every partition’s updates after each training step and serves as a quality target despite being significantly slower.
- This work focuses on label-distribution skew, one form of non-IID data that can result from heterogeneous users or locations.
- The Flickr-Mammal dataset contains 41 mammal classes and 736,005 pictures after cleaning Flickr search results with a PNAS model pretrained on ImageNet.
- Across continents, the top five mammals account for 32%–92% of normalized worldwide samples, versus 20% under an IID distribution, with no top-five class overlap.
3. Experimental Setup
The experiments span applications, models, datasets, decentralized algorithms, and controlled label-skew levels. Training settings are calibrated against IID BSP baselines, while algorithm-specific hyperparameters represent communication controls.
- The study varies ML applications and models, decentralized learning algorithms, and the degree of data skew using rigorous experimental methodologies.
- Applications: Image-classification experiments use AlexNet, GoogLeNet, LeNet, and ResNet with CIFAR-10 and ImageNet, measuring validation accuracy.
- Experimental controls: Training parameters are tuned so IID BSP matches the corresponding original-paper accuracy, then reused across other settings until accuracy stops improving.
- Data partitions: Non-IID partitions are created by partitioning data according to labels, with skewness controlled by the fraction assigned non-IID.
- Communication controls: Gaia, FederatedAveraging, and DeepGradientCompression expose hyperparameters that control communication through thresholds, local SGD steps, or update sparsity.
- Hyperparameter selection: Hyperparameters are selected to match IID BSP quality and provide similar communication savings across the decentralized algorithms.
4. Non-IID Study: Results Overview
Across image classification and face recognition, decentralized learning suffers substantial accuracy loss under non-IID label partitions, including settings where communication-heavy or longer training does not resolve the problem.
- Image Classification: 3% to 74% validation accuracy loss occurs for all three decentralized algorithms across four DNNs in CIFAR-10's Non-IID setting.In the IID setting, the algorithms retain BSP accuracy with 15×–20× communication savings; some Non-IID runs diverge.
- Image Classification: 39% lower validation accuracy for ResNet20 in the Non-IID setting shows that BSP cannot retain model quality for some DNNs.Increasing communication between partitions may not solve the challenge for these models.
- Image Classification: 8.1% to 61.7% accuracy loss also appears for ResNet10 on ImageNet, whose 1,000 classes greatly exceed CIFAR-10's ten classes.The same problem therefore appears in a larger, more class-diverse dataset.
- Image Classification: 5.2% and 5.5% accuracy losses occur when Flickr-Mammal is partitioned at the subcontinent level.The experiment uses real-world continent-based partitions versus randomly assigned IID partitions.
- Face Recognition: 50% verification accuracy for Gaia and FederatedAveraging in Non-IID face recognition is no better than random guessing.This occurs even though validation labels differ from training labels and verification uses feature-vector distances rather than the classification layer.
- Overall Findings: The Non-IID problem is not specific to hyper-parameter choices: conservative settings still lose major accuracy, unlike in the IID setting.The conservative settings incur high communication costs, while training and validation accuracy have already stopped improving in the reported CIFAR-10 experiments.
5. Batch Normalization: Problem and Solution
BatchNorm is vulnerable to skewed partitions because local minibatch statistics diverge, undermining synchronized models even under BSP. GroupNorm avoids minibatch dependence and recovers much of the resulting accuracy loss, though broader replacement remains unresolved.
- BatchNorm Problem: BatchNorm validation can be inaccurate when training minibatch statistics differ from estimated global statistics, a mismatch exacerbated by non-IID partitions.Each partition may observe different means and variances, and larger minibatches or improved sampling cannot make a local partition represent the global dataset.
- BatchNorm Problem: 6% to 61% minibatch-mean divergence under Non-IID partitions exceeds the 1% to 5% divergence under IID partitions.The same trend occurs for minibatch variances, explaining why BSP cannot retain BatchNorm accuracy in the Non-IID setting.
- GroupNorm Solution: GroupNorm computes per-group statistics for each input sample, so its normalization does not depend on minibatches.It divides adjacent channels into groups of a prespecified size.
- GroupNorm Solution: 79.2% validation accuracy is achieved by GroupNorm with BSP in the Non-IID setting, matching its IID accuracy for BN-LeNet on CIFAR-10.The experiment uses five partitions and selects Gsize = 2 for this DNN.
- GroupNorm Solution: GroupNorm improves Non-IID decentralized algorithms over BatchNorm by additive 10.7%, 19.8% and 60.2%, respectively.Accuracy losses remain significant for those algorithms despite the improvement.
- Limitations: More study is needed to determine whether GroupNorm can replace BatchNorm across different applications and DNN models.For recurrent and generative models, the paper identifies LayerNorm as a possible option because it is effective there and minibatch-independent.
6. Degree of Data Skew
Partial non-IID label partitions remain problematic, and increasing skew generally makes decentralized training harder. Even 40% non-IID data causes measurable accuracy loss, while the 80%-versus-20% gap can reach 7.4%.
- Degree of skew: Figure 6 plots GN-LeNet’s top-1 CIFAR-10 validation accuracy across skew levels against BSP in the IID setting.The “-x%” labels denote accuracy loss relative to that baseline, and the y-axis begins at 60%.
- Partial non-IID data: 1.5%–3.0% accuracy loss occurs even when only 40% of the data is non-IID.The problem therefore extends beyond exclusive label partitioning.
- Degree of skew: Accuracy generally worsens as the degree of skew increases.The accuracy gap between 80% and 20% non-IID data reaches 7.4% for DeepGradientCompression.
7. Our Approach: SkewScout
SkewScout estimates accuracy divergence across data partitions and adapts communication to preserve model quality efficiently. It achieves substantial savings over BSP while matching BSP accuracy, and approaches the ideal Oracle baseline.
- Overview: SkewScout estimates skew-induced accuracy loss by traveling the model between partitions and evaluating it on remote training data.Comparing remote and original-partition training accuracy provides the loss estimate.
- Adaptive communication control: SkewScout tunes decentralized-learning hyperparameters to minimize communication while keeping accuracy loss within a threshold.The system is designed as a general module that integrates with learning algorithms, training frameworks, and applications.
- Design scope: SkewScout assumes increased communication improves accuracy for the relevant data skew, regardless of whether skewed labels or another non-IID source causes the loss.Its effectiveness depends on this relationship between communication and accuracy.
- Evaluation results: 9.6–34.1× communication savings over BSP are achieved in various non-IID settings without sacrificing model accuracy.Savings are larger with less skew because communication can be loosened safely.
- Evaluation results: SkewScout requires only 1.1–1.5× more communication than Oracle to achieve the same model accuracy.Periodic model traveling and inability to foresee some favorable early accuracy losses explain the remaining gap.
8. Related Work
Related work spans centralized communication-efficient training, decentralized-learning algorithms, non-IID federated learning, and non-IID datasets. The paper distinguishes its study by examining skewed label partitions and releasing a larger real-world dataset.
- Contribution: The paper presents its study as the first to show that skewed label partitions across devices or locations are a fundamental and pervasive decentralized-learning problem.Its investigation covers real-world data, algorithms, batch normalization, and data skew.
- Large-scale systems for centralized learning: Centralized large-scale ML systems generally assume training data can be centralized and partitioned among machines.Their communication-efficient designs relax synchronization or reduce updates to parameter servers.
- Decentralized learning: Prior decentralized-learning algorithms improve communication efficiency but lose significant model accuracy under non-IID data.Other approaches may sidestep global-model challenges when local models are unavailable or ineffective.
- Non-IID dataset: Existing non-IID datasets support federated-learning research, while the Flickr-Mammal dataset studies geographic label skew at a much larger scale.The paper also broadens the dataset scope to geo-distributed mammal data.
9. Conclusion
The paper concludes that skewed label partitions are a pervasive decentralized-learning problem whose difficulty depends on skew and is especially severe for batch-normalized DNNs. It studies this empirically, releases a real-world dataset, and presents SkewScout to retain quality while reducing communication.
- Conclusion: All decentralized-learning algorithms studied suffer major accuracy loss on skewed label partitions.The conclusion identifies skewed labels as a fundamental and pervasive challenge.
- Conclusion: DNNs with batch normalization are particularly vulnerable under non-IID data, even with the most communication-heavy approach.The paper also discusses the cause and a potential solution.
- Conclusion: The difficulty of skewed-label training varies greatly with the degree of skew.This finding extends the problem beyond a single partitioning severity.
- Conclusion: SkewScout is presented as a general approach to minimize communication while retaining model quality for non-IID partitions.Its implementation and evaluation use Gaia, FederatedAveraging, and DeepGradientCompression, with training inputs including local datasets, minibatches, momentum, and learning rates.
- Dataset: The released Flickr-Mammal dataset contains substantial class imbalance, with cats having 23× more images than skunks.Most classes have at least 10,000 images, while the least popular class has 1,531 images.
B.2. First-Level Geographical Region Analysis
The Flickr-Mammal dataset exhibits substantial geographical variation in both image counts and mammal-label distributions across continents and subcontinents. Normalizing regional sample counts isolates label-distribution skew from differences in the number of images collected.
- Continental image counts: Americas and Europe contain significantly more Flickr-Mammal images than other continents.The analysis omits 53 images not assigned to one of the five continents.
- Continental label shares: Geographical distributions create highly uneven mammal-label shares across continents, with some classes concentrated in particular regions.For example, Oceania contains more than 70% of Kangaroo and Koala images despite representing 6% of total images.
- Normalized continental shares: Normalizing each continent to the same total image count preserves substantial differences in mammal-label distributions.This normalization focuses the analysis on P(y) across continents rather than on unequal regional sample sizes.
- Subcontinental image counts: At the subcontinent level, Northern America and Northern Europe have significantly more images than other analyzed subcontinents.The analysis retains 13 subcontinents and 735,071 images after excluding regions with fewer than 1,000 images.
- Subcontinental label shares: Mammal labels are highly skewed across the 13 subcontinents, with most classes concentrated in only 3–5 subcontinents.Concentration patterns differ by class, including Kangaroo and Koala in Australia and New Zealand and Antelope and Zebra in Sub-Saharan Africa.
D. Training Convergence Curves
Training on non-IID partitions generally converges along trends similar to IID training but reaches substantially lower model accuracy. Longer training does not resolve the observed non-IID accuracy problem, and BatchNorm contributes to the loss even under BSP.
- Convergence behavior: Non-IID training processes stop improving long before the experiments end, indicating that longer training does not solve the problem.This observation is reported for AlexNet and ResNet20 on CIFAR-10.
- Convergence behavior: Non-IID convergence curves generally follow IID trends but achieve significantly lower model accuracy.The pattern appears in the reported CIFAR-10 convergence curves for AlexNet and ResNet20.
- Normalization effects: BatchNorm causes BSP to lose significant accuracy in non-IID settings for DNN models such as ResNet20.The paper connects this loss to the convergence behavior shown for ResNet20.
- Cross-dataset consistency: The ImageNet experiments reproduce the non-IID problem across Gaia, FederatedAveraging, DeepGradientCompression, and BSP.Gaia and FederatedAveraging lose 8.1% to 27.2% validation accuracy, while some configurations fail to produce useful models.
F. Effect of Larger Numbers of Data Partitions
Increasing the number of data partitions makes highly skewed training harder: with ten CIFAR-10 partitions, fully label-separated training does not converge even under BSP. A milder 80%/20% skew is therefore used for comparison.
- Experimental scope: The study examines larger partition counts after earlier experiments used only K = 2 or K = 5 partitions.The stated purpose is to study the effect of having a larger number of data partitions.
- CIFAR-10: With ten CIFAR-10 partitions, 100% non-IID ResNet20 training does not converge under BSP.Each partition contains only one object class, causing gradients from different partitions to diverge too much.
- CIFAR-10: The ten-partition experiment instead assigns each partition 80% of one object class and 20% of another.This creates a less extreme non-IID setting after fully label-separated training fails to converge.
- Experimental scope: The partition-count comparison reports Top-1 validation accuracy for ResNet20 on CIFAR-10 with five and ten partitions.The five-partition results are repeated from Figure 1.
G. Reasons for Model Quality Loss
Model-quality loss under non-IID training reflects partition-specific specialization and delayed or sparse synchronization, while more frequent communication often improves accuracy. GroupNorm avoids BatchNorm’s minibatch dependence, but the study’s normalization conclusions remain bounded by model and task scope.
- Gaia: Gaia can produce specialized partition models despite average weight differences of only 0.5%.The corresponding average neuron-value difference is 173%, allowing small weight differences to yield substantially different model behavior.
- Gaia: Gaia’s communication savings allow models to specialize for local image classes at the expense of other classes.The paper attributes this to eliminating insignificant communication updates.
- DeepGradientCompression: DeepGradientCompression has an average residual update delta of 283% in Non-IID training versus 27% in IID training.Fixed-rate gradient sparsification leaves large, partition-specific gradients unsynchronized.
- FederatedAveraging: FederatedAveraging can lose accuracy or diverge when delayed local updates cause weights across partitions to diverge too much.The analysis evaluates average local weight-update deltas at global synchronization points.
- Communication frequency: More frequent communication often reduces non-IID accuracy loss, supporting SkewScout’s adaptive-communication approach.A Gaia setting with T0 = 2% achieves significantly higher validation accuracy than T0 = 30%.