Optimizing Shapley Value for Client Valuation in Federated Learning through Enhanced GTG-Shapley
Meriem Arbaoui, Mohamed‐el‐Amine Brahmia, Abdellatif Rahmoun, Mourad Zghal · 2024
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.