PaperlayerView exact revision on arXiv

Source-linked AI summary

GTG-Shapley: Efficient and Accurate Participant Contribution Evaluation in Federated Learning

Zelei Liu, Yuanyuan Chen, Han Yu, Yang Liu, Lizhen Cui

arXiv:2109.02053v1cs.AI

TL;DR

FL contribution evaluation must be fair and privacy-preserving, but existing Shapley Value methods are costly and can suffer from ordering-related limitations. GTG-Shapley reconstructs models from gradient updates and applies guided sampling with truncation. Experiments show close approximation to actual Shapley values with significantly improved computational efficiency, especially under non-i.i.d. settings.

  • Problem

    Fairly evaluating FL participants’ contributions without exposing local data is important for incentive schemes, but existing Shapley Value approaches require substantial computation and may incur training overhead.

  • Method

    GTG-Shapley reconstructs FL sub-models from previous gradient updates and uses guided Monte Carlo sampling with within-round and between-round truncation.

  • Results

    GTG-Shapley closely approximates actual Shapley values while significantly improving computation efficiency compared with state-of-the-art approaches across i.i.d. and non-i.i.d. settings.

  • Takeaways & Limitations

    GTG-Shapley supports fair assessment of FL participant contributions at scale without extra model training or exposing sensitive local data.

  • Takeaways & Limitations

    Similarity-based contribution assumptions may be unreliable in non-i.i.d. settings, where complementary participant knowledge can be more valuable than similarity.

Abstract

from arXiv · show

Federated Learning (FL) bridges the gap between collaborative machine learning and preserving data privacy. To sustain the long-term operation of an FL ecosystem, it is important to attract high quality data owners with appropriate incentive schemes. As an important building block of such incentive schemes, it is essential to fairly evaluate participants' contribution to the performance of the final FL model without exposing their private data. Shapley Value (SV)-based techniques have been widely adopted to provide fair evaluation of FL participant contributions. However, existing approaches incur significant computation costs, making them difficult to apply in practice. In this paper, we propose the Guided Truncation Gradient Shapley (GTG-Shapley) approach to address this challenge. It reconstructs FL models from gradient updates for SV calculation instead of repeatedly training with different combinations of FL participants. In addition, we design a guided Monte Carlo sampling approach combined with within-round and between-round truncation to further reduce the number of model reconstructions and evaluations required, through extensive experiments under diverse realistic data distribution settings. The results demonstrate that GTG-Shapley can closely approximate actual Shapley values, while significantly increasing computational efficiency compared to the state of the art, especially under non-i.i.d. settings.

1 INTRODUCTION

Federated learning needs fair, privacy-preserving participant contribution evaluation to support incentives, but Shapley Value estimation is computationally expensive and can be distorted by permutation ordering. GTG-Shapley addresses these challenges by reconstructing models from gradient updates and using guided truncation and sampling, achieving efficient and accurate approximation.

  • Motivation: Federated learning incentive mechanisms require fair evaluation of participants’ contributions without direct access to their private data.Contribution evaluation is the first step before designing and distributing rewards.
  • Motivation: Shapley Value evaluates individual contributions from utilities across participant subsets while preserving privacy, but direct calculation has exponential computational cost.Its fairness and reliance on coalition utility make it suitable for FL, whereas exhaustive evaluation is expensive.
  • Challenges: Permutation-based SV estimates can unfairly undervalue late-joining participants because sampled ordering may systematically place them after others.This ordering effect can prevent estimates from converging fairly to the theoretical Shapley values.
  • Approach: GTG-Shapley reconstructs FL sub-models from stored gradient updates and uses guided Monte Carlo sampling with within-round and between-round truncation.These mechanisms reduce model reconstruction and evaluation operations without requiring extra learning tasks from participants.
  • Results: Extensive experiments across i.i.d. and non-i.i.d. data settings show that GTG-Shapley improves efficiency and accuracy relative to existing approaches.The method closely approximates actual Shapley values while reducing computational costs.

2 RELATED WORK

Related work evaluates FL contributions through self-reporting, individual performance, utility games, and Shapley Value-based methods. Existing approaches face truthfulness assumptions, limited suitability for non-i.i.d. data, ordering effects, or substantial training and evaluation costs; GTG-Shapley combines gradient reconstruction with guided truncation to address these gaps.

  • 2.1 FL Participant Contribution Evaluation via Self-Reporting: Self-reporting methods use participants’ claims about sensitive data and resources, but their validity depends on truthful reporting.Their evaluation is straightforward, yet truthfulness is a strong assumption.
  • 2.2 Individual FL Participant Contribution Evaluation: Individual-performance methods assess participants using local performance, update similarity, or ratings rather than the FL model’s overall performance.They generally assume similarity to an aggregated or other local model indicates greater value.
  • 2.2 Individual FL Participant Contribution Evaluation: Similarity-based individual evaluation may fail in non-i.i.d. settings, where complementary knowledge can be more valuable than similarity.This is identified as a limitation of the underlying assumption.
  • 2.3 Utility Game-Based Evaluation: Utility-game approaches allocate value through marginal gains, marginal losses, or related profit-sharing principles when participants join or leave coalitions.Gradient Shapley applies marginal-loss reasoning to data points but remains affected by evaluation order.
  • 2.4 FL Participant Contribution Evaluation via Shapley Value: Monte Carlo Shapley methods reduce sampled permutations, but conventional approaches still require training each permutation-specific FL model from scratch.This creates substantial computation and communication overhead for participants.
  • 2.5 FL Participant Contribution Evaluation via Gradient Shapley Techniques: Gradient-based Shapley methods reconstruct sub-models from stored participant updates, with one-round and multi-round variants differing in when SVs are calculated.Truncated multi-round methods further eliminate selected evaluations.
  • 2.6 Summary: GTG-Shapley targets utility-evaluation speed, training-round importance, and unnecessary evaluations simultaneously to improve efficiency and accuracy.The paper identifies these three aspects as uncovered together by prior approaches.

3 PRELIMINARIES

This section describes horizontal federated learning, canonical Shapley-value contribution evaluation, and gradient-based model reconstruction. It also identifies evaluation cost and ordering effects as key challenges motivating more efficient estimation.

  • Federated Learning Framework: In horizontal federated learning, participants share a feature space but hold different samples, and the server aggregates their model updates each global round.Participants train locally after downloading the global model, then send updates for server-side aggregation such as FedAvg.
  • Shapley Value Evaluation: Data Shapley values evaluate each participant’s contribution by averaging marginal utility gains across counterfactual participant permutations.The utility function can evaluate the joint utility of any participant subset, commonly through model prediction performance on a separate test set.
  • Computational Challenge: Canonical SV evaluation requires retraining the FL model for each participant combination, making computation prohibitive for large enterprise data silos.Gradient-based reconstruction replaces repeated sub-model retraining by using participants’ gradient updates.
  • Empirical Insights: In an empirical MNIST analysis with 10 non-i.i.d. participants, approximately 98.5% of SV-computation time was consumed by sub-model performance evaluation.The analysis also found significant marginal utility differences between global training rounds and lower perceived significance for late-joining participants.
  • Empirical Insights: Early positions in sampled participant permutations can receive larger perceived marginal utility, while late positions can appear less significant and bias SV estimation.A participant may repeatedly appear late or behind particular participants, undermining the intended removal of ordering effects.

4 THE PROPOSED APPROACH

GTG-Shapley evaluates participant contributions by reconstructing sub-models from stored gradient updates, then reduces evaluations through guided sampling and truncation. Its complexity can range from O(Tlog N) to O(TNlog N), reaching O(Tlog N) when truncation is highly effective.

  • 4.1 Elimination of Sub-Model Retraining: GTG-Shapley reconstructs FL sub-models from participants’ gradient updates instead of retraining them from scratch.This allows Shapley calculation to run entirely on the FL server without additional participant computation.
  • 4.2 Guided Truncation of Model Evaluation: The method uses guided Monte Carlo sampling to distribute participants across permutation positions and improve convergence.The first m participants are circulated in fixed order, while the remaining n−m positions use random permutations.
  • 4.2 Guided Truncation of Model Evaluation: Between-round truncation discards entire SV-calculation rounds when their remaining marginal utility gain is small.A round is ignored when |v_N−v_0| is not larger than the threshold ε_b.
  • 4.2 Guided Truncation of Model Evaluation: Within-round truncation terminates permutation evaluations when the remaining marginal gain falls below the threshold ε_i.This avoids unnecessary successive sub-model evaluations within a sampled participant sequence.
  • 4.4 Complexity Analysis: GTG-Shapley requires O(Tlog N) to O(TNlog N) complexity, depending on the data distribution and truncation behavior.For some i.i.d. settings, L_i≈1 and the complexity is O(Tlog N).

5 EXPERIMENTAL EVALUATION

This section compares GTG-Shapley with six state-of-the-art approaches and evaluates different GTG-Shapley variants. The evaluation covers varied data distributions and performance ablations.

  • The evaluation compares GTG-Shapley with six state-of-the-art approaches.
  • The experiments cover various data distributions.
  • The study includes performance ablation experiments on different GTG-Shapley variants.

5.1 Experiment Setings

The evaluation uses MNIST with ten participants across five federated learning data settings and compares GTG-Shapley with six baselines using four metrics. Lower metric values indicate better performance.

  • Experiment Settings: The experiments use MNIST with 54,210 training samples and 8,920 test samples distributed among 10 participants.The dataset contains handwritten digit images, with 5,421 training samples and 892 test samples selected per digit.
  • Experiment Settings: The five FL settings vary distribution similarity, dataset size, label noise, and feature noise.They include same or different distributions and sizes, noisy labels, and noisy features.
  • Comparison Approaches: GTG-Shapley is compared against Original Shapley, TMC Shapley, Group Testing, MR, Fed-SV, and TMR.The baselines use exhaustive evaluation, Monte Carlo sampling, group testing, gradient-based reconstruction, or truncation variants.
  • Performance Evaluation Metrics: The evaluation metrics are Time, Cosine Distance, Euclidean Distance, and Maximum Difference.Time is shown after applying log10(·), while the distance metrics compare estimated values with Original Shapley results.
  • Performance Evaluation Metrics: Smaller values across all four metrics indicate better approach performance.

5.2 Results and Discussions

GTG-Shapley provides the strongest combined efficiency and accuracy across i.i.d. and non-i.i.d. settings. It remains consistently faster than the best baseline while matching or slightly exceeding its accuracy.

  • Same Distribution and Same Size: GTG-Shapley achieves the highest efficiency in the same-distribution, same-size setting, running 7.4 times faster than TMR.MR, TMR, and Fed-SV are faster than GroupTesting and Original Shapley, while GTG-Shapley is fastest overall.
  • Same Distribution and Same Size: GTG-Shapley slightly outperforms MR and TMR in accuracy across all three distance metrics under the same-distribution, same-size setting.
  • Different Distributions and Same Size: GTG-Shapley is fastest and achieves the best accuracy under different distributions and same size across all three distance metrics.The accuracy gap is larger than under the same-distribution setting, with TMC the second most accurate approach.
  • Noisy Labels and Noisy Features: GTG-Shapley achieves the best accuracy and significantly higher efficiency than other approaches under noisy labels and noisy features.TMR and MR follow closely in accuracy, while other truncation methods can slow under noisy settings.
  • Overall Results: Across i.i.d. and non-i.i.d. settings, GTG-Shapley is consistently faster than the best baseline and matches or slightly outperforms it in accuracy.Its partial permutation sampling improves SV estimation convergence, while truncation benefits vary across non-i.i.d. conditions.

5.3 Ablation Study

The ablation study examines SV computation frequency, between-round truncation, and guided sampling. Guided sampling provides the largest accuracy benefit, while truncation improves efficiency without reducing accuracy in the tested settings.

  • SV Computing Frequency: GTG-OTi is 2–3 times more efficient than GTG-Ti across all five settings by computing SVs only once instead of every round.GTG-OTi has the lowest SV computing frequency, whereas GTG-Ti computes SVs in every round.
  • SV Computing Frequency: GTG-OTi has the lowest accuracy because its low SV computing frequency makes reconstructed sub-model utilities deviate from current values.Reducing SV computing frequency improves efficiency but negatively affects estimated SV accuracy.
  • Between-Round Truncation: Between-round truncation makes GTG-Tid 17% more efficient than GTG-Ti and up to 3 times faster, depending on FL model convergence.It can further improve efficiency under i.i.d. settings.
  • Between-Round Truncation: Between-round truncation increases or maintains SV estimation accuracy across the tested data-distribution settings.GTG-Tid is more accurate in Figures 11–13 and similar to GTG-Ti in Figures 14–15.
  • Guided Sampling: Guided sampling gives GTG-Shapley the highest accuracy in all five settings and generally improves or maintains efficiency relative to GTG-Tid.The study attributes the accuracy gain to reducing ordering bias by placing different participants in important permutation positions.

6 CONCLUSIONS AND FUTURE WORK

The paper concludes that GTG-Shapley estimates participant contributions without extra model training or exposing sensitive local data. Its experiments show close approximation to actual SVs with improved computational efficiency, and future work targets participant auditing tools.

  • Conclusions: GTG-Shapley evaluates FL participants’ Shapley-based contributions without extra model training or exposing sensitive local data.
  • Conclusions: GTG-Shapley closely approximates actual Shapley values while significantly improving computation efficiency over state-of-the-art approaches.Previously evaluated model utilities guide the skipping of unnecessary sub-model reconstruction and evaluation operations.
  • Future Work: Future research will build FL participant auditing tools based on GTG-Shapley to support regulatory oversight of federated-learning data exchange.
Loading 2109.02053v1…