Source-linked AI summary
A Principled Approach to Data Valuation for Federated Learning
Tianhao Wang, Johannes Rausch, Ce Zhang, Ruoxi Jia, Dawn Song
TL;DR
Federated learning needs fair valuation of decentralized data, but canonical Shapley values are costly to compute and ignore participation order. The paper introduces the federated Shapley value, which uses ordered, round-level updates while preserving key Shapley properties. Across noisy-label detection, adversarial-participant detection, and data summarization, it reflects data-source utility for federated learning, while its assumptions remain less valid than in centralized learning.
Problem
Canonical Shapley valuation requires evaluating every participant subset and ignores training order, making its assumptions invalid for federated learning.
Method
The federated Shapley value assigns same-round aggregate value using ordered model-performance changes, sums values across rounds, and is approximated with efficient algorithms.
Results
Across noisy-label detection, adversarial-participant detection, and data summarization, the federated Shapley value reflects the actual utility of federated data sources while preserving group rationality, fairness, and additivity.
Takeaways & Limitations
The federated Shapley value provides a communication-efficient data-valuation notion that captures participation order and can support analysis of data utility in federated learning.
Takeaways & Limitations
The canonical Shapley formulation relies on combinatorially evaluable and order-independent utility, assumptions the paper states are no longer valid in federated learning.
Abstract
from arXiv · showhide
Federated learning (FL) is a popular technique to train machine learning (ML) models on decentralized data sources. In order to sustain long-term participation of data owners, it is important to fairly appraise each data source and compensate data owners for their contribution to the training process. The Shapley value (SV) defines a unique payoff scheme that satisfies many desiderata for a data value notion. It has been increasingly used for valuing training data in centralized learning. However, computing the SV requires exhaustively evaluating the model performance on every subset of data sources, which incurs prohibitive communication cost in the federated setting. Besides, the canonical SV ignores the order of data sources during training, which conflicts with the sequential nature of FL. This paper proposes a variant of the SV amenable to FL, which we call the federated Shapley value. The federated SV preserves the desirable properties of the canonical SV while it can be calculated without incurring extra communication cost and is also able to capture the effect of participation order on data value. We conduct a thorough empirical study of the federated SV on a range of tasks, including noisy label detection, adversarial participant detection, and data summarization on different benchmark datasets, and demonstrate that it can reflect the real utility of data sources for FL and has the potential to enhance system robustness, security, and efficiency. We also report and analyze "failure cases" and hope to stimulate future research.
1 Introduction
Federated learning enables training across siloed data without centralizing it, but participation requires fair data valuation. The canonical Shapley value is principled yet costly for decentralized, sequential training, motivating the federated SV.
- Federated learning trains local models on sequestered data and distills them into a global model without requiring centralized data.
- Fairly appraising each data source is crucial for incentivizing participation and dividing earnings from the federated model.
- The canonical Shapley value distributes model gains according to contributions and has properties including group rationality, fairness, and additivity.
- Computing the canonical Shapley value requires evaluating every subset of decentralized data sources, while its order-insensitivity conflicts with sequential federated training.
- The federated Shapley value uses local updates, captures participation order, preserves canonical properties, and is evaluated empirically across several FL tasks.
2 Related Work
Related work categorizes data pricing into query-based, attribute-based, and auction-based strategies, while Shapley-based valuation remains computationally expensive. Federated pricing also studies incentive mechanisms under participant heterogeneity.
- Existing data-pricing schemes include query-based pricing, data attribute-based pricing, and auction-based pricing.
- The Shapley value uniquely satisfies desired valuation properties but can be #P-complete to compute and requires repeated model retraining for ML data valuation.
- One federated-pricing research thread designs contracts to incentivize participation despite differences in data quality, bandwidth, and computational capability.
3 Data Valuation based on SV
The canonical Shapley value models data contributors as cooperative-game players and assigns average marginal contributions. Its valuation guarantees rely on combinatorial evaluability and order-independent utility.
- A cooperative game maps each coalition of players to its collective utility, and the Shapley value distributes the coalition’s total gains among players.
- The Shapley value averages each player’s marginal contribution over all possible joining orders.
- In data valuation, players represent contributors, coalition utility represents model performance, and each Shapley value measures a contributor’s importance to learning.
- Group rationality distributes the model’s full value, fairness equalizes equivalent contributors and pays zero for universally zero marginal contribution, and additivity combines values across utilities.
- The Shapley value assumes that utility can be evaluated for every player combination and does not depend on player order.
- These assumptions are plausible in centralized learning but become invalid in federated learning because data are decentralized and training order matters.
4 Valuing Data for FL
Federated learning makes canonical Shapley valuation impractical because only ordered, round-specific updates are observed. The federated SV assigns round-level aggregate value to participants while preserving key Shapley properties.
- A typical federated-learning round samples participants, downloads the global model, computes local updates, aggregates them, and updates the global model.
- Federated participants contribute at different times, while confidentiality and partial selection prevent evaluating every possible participant subset.
- The federated SV characterizes same-round participants’ aggregate value through model-performance change and distributes that value among them using the Shapley value.
- Unlike the canonical formulation, the federated utility takes an ordered sequence, so U(A + B) represents training on A’s data before B’s data.
- The federated SV sums participant values across rounds and assigns zero at a round to participants who were not selected.
- Theorem 1 establishes that the federated SV preserves group rationality, fairness, and additivity.
1. Instantaneous group rationality: P
The federated Shapley value distributes each round’s performance improvement among participating players while retaining principled fairness properties. Because exact computation remains expensive, the paper develops approximation methods whose relative efficiency depends on the number of participants per round.
- Instantaneous group rationality: Each round’s participant values sum to the global model utility improvement over the preceding round.This instantaneous group rationality property underlies the federated SV’s allocation of round-level performance gains.
- Long-term group rationality: Aggregating instantaneous group rationality over time yields long-term group rationality, dividing a coalition’s final yield among its participants.The long-term statement applies to players participating throughout a T-round FL process.
- Exact computation: Exact federated SV computation has complexity O(T2m), because it evaluates every participant’s marginal utility across every within-round subset.Each utility evaluation updates the global model with selected participant updates and measures the resulting performance.
- Approximation methods: Permutation sampling approximates each participant’s expected contribution under random orderings, extending canonical SV estimation to each FL round.The method uses sample averages of contributions to preceding participants in random permutations.
- Approximation methods: When each round selects many participants, group testing is significantly faster; with few participants, permutation sampling is preferred because its utility evaluations have a smaller constant.For constant ϵ and δ, group testing scales as O((log m)^2), compared with O(m log m) for permutation sampling.
5 Empirical Study
The empirical study evaluates federated data valuation on noisy-label detection, backdoor detection, and data summarization, comparing federated SV with federated LOO and random selection. Federated SV generally reflects participant utility, while normalization improves detection but can introduce trade-offs and setting-dependent weaknesses.
- Experimental Setup: The study evaluates data valuation for noisy-data detection, adversarial participant removal, and data summarization across MNIST and CIFAR10.The experiments compare federated SV with federated LOO and random baselines.
- Noisy Label Detection: In IID noisy-label detection, federated LOO and federated SV perform similarly, whereas federated SV outperforms federated LOO in the Non-IID setting.The authors attribute this difference to the way federated SV evaluates contributions across participant subsets.
- Noisy Label Detection: Normalized federated SV and LOO make noisy participants much easier to separate from benign participants.Normalization compensates for decreasing total participant contribution across later training rounds, but normalized values no longer preserve group rationality and additivity.
- Backdoor Attack Detection: Federated SV is more effective than federated LOO for detecting compromised participants, while normalized federated SV and LOO improve substantially over their original definitions.The backdoor experiments use adversarial control of 30% of participants and backdoor images mixed into compromised participants’ batches.
- Data Summarization: For data summarization, federated SV outperforms both baselines on MNIST IID and beats the random baseline in MNIST Non-IID, but federated LOO performs better at lower dismissal fractions in Non-IID.Both federated SV and LOO perform worse on CIFAR10; the authors hypothesize that MNIST’s redundant samples make participant dismissal less harmful.
6 Conclusion
The paper concludes that federated SV provides a principled, communication-efficient way to value data in federated learning while accounting for participation order. Experiments across detection and summarization tasks indicate that it can reflect data-source utility, with the figures summarizing backdoor-detection and data-summarization evaluations.
- 6 Conclusion: Federated SV preserves group rationality, fairness, and additivity while enabling communication-efficient calculation that captures participant participation order.The paper also presents approximation algorithms that are more efficient than the exact algorithm when the participant count is large.
- 6 Conclusion: Across noisy-label detection, adversarial participant detection, and data summarization, federated SV reflects the actual utility of data sources.The conclusion identifies these tasks as the main empirical evidence for the proposed data-value notion.
- 6 Conclusion: Figure 3 summarizes backdoor-detection results for original and normalized LOO/SV approaches.The corresponding experiments report federated SV as more effective than federated LOO and improved performance for normalized variants.