Optimizing Shapley Value for Client Valuation in Federated Learning through Enhanced GTG-Shapley

In the ever-evolving realm of federated learning
(FL), the question of data worth resonates with newfound urgency across organizations and individuals. In the dynamic FL ecosystem, where data resides across distributed nodes, evaluating the value of each client’s data is paramount. The evaluation mechanism helps to understand individual contributions to the overall process and incentivizes the best contributors, thereby ensuring the sustainability of federated training. Drawing inspiration from cooperative game theory approaches, we harness the Shapley Value (SV)—a well established measure of value—to address this challenge. Despite offering valuable insights, the computation of
the Shapley Value often entails exponential time complexity. In
our study, we propose an Enhanced Guided Truncation Gradient
Shapley algorithm, precisely tailored for efficient SV approximation in FL settings. Specifically, our approach comprises two pivotal enhancements for the GTG-Shapley method. First, we optimize the client sampling policy to generate representative permutations. Second, we employ an order-reversed marginal utility function based on the Monte-Carlo estimation for SV calculation. Through empirical experiments, we demonstrate the superior performance of EGTG-Shapley compared to the conventional GTG-Shapley method, showcasing significant efficiency gains in FL contexts.