Efficient Data Valuation Approximation in Federated Learning: A Sampling-based Approach

• URL: http://arxiv.org/abs/2504.16668v1
• Date: Wed, 23 Apr 2025 12:36:20 GMT
• Title: Efficient Data Valuation Approximation in Federated Learning: A Sampling-based Approach
• Authors: Shuyue Wei, Yongxin Tong, Zimu Zhou, Tianran He, Yi Xu,
• Abstract summary: Cross-silo data providers often hesitate to share their high-quality dataset unless their data value can be fairly assessed.<n> Shapley value (SV) has been advocated as the standard metric for data valuation in FL due to its desirable properties.<n>We propose a practical approximation algorithm, IPSS, which strategically selects high-impact dataset combinations.
• Score: 26.75493602427444
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Federated learning paradigm to utilize datasets across multiple data providers. In FL, cross-silo data providers often hesitate to share their high-quality dataset unless their data value can be fairly assessed. Shapley value (SV) has been advocated as the standard metric for data valuation in FL due to its desirable properties. However, the computational overhead of SV is prohibitive in practice, as it inherently requires training and evaluating an FL model across an exponential number of dataset combinations. Furthermore, existing solutions fail to achieve high accuracy and efficiency, making practical use of SV still out of reach, because they ignore choosing suitable computation scheme for approximation framework and overlook the property of utility function in FL. We first propose a unified stratified-sampling framework for two widely-used schemes. Then, we analyze and choose the more promising scheme under the FL linear regression assumption. After that, we identify a phenomenon termed key combinations, where only limited dataset combinations have a high-impact on final data value. Building on these insights, we propose a practical approximation algorithm, IPSS, which strategically selects high-impact dataset combinations rather than evaluating all possible combinations, thus substantially reducing time cost with minor approximation error. Furthermore, we conduct extensive evaluations on the FL benchmark datasets to demonstrate that our proposed algorithm outperforms a series of representative baselines in terms of efficiency and effectiveness.

Related papers

• DUPRE: Data Utility Prediction for Efficient Data Valuation [49.60564885180563]
  Cooperative game theory-based data valuation, such as Data Shapley, requires evaluating the data utility and retraining the ML model for multiple data subsets.<n>Our framework, textttDUPRE, takes an alternative yet complementary approach that reduces the cost per subset evaluation by predicting data utilities instead of evaluating them by model retraining.<n>Specifically, given the evaluated data utilities of some data subsets, textttDUPRE fits a emphGaussian process (GP) regression model to predict the utility of every other data subset.
  arXiv  Detail & Related papers  (2025-02-22T08:53:39Z)
• Enhancing Generalization via Sharpness-Aware Trajectory Matching for Dataset Condensation [37.77454972709646]
  We introduce Sharpness-Aware Trajectory Matching (SATM), which enhances the generalization capability of learned synthetic datasets.<n>Our approach is mathematically well-supported and straightforward to implement along with controllable computational overhead.
  arXiv  Detail & Related papers  (2025-02-03T22:30:06Z)
• Optimizing Pretraining Data Mixtures with LLM-Estimated Utility [52.08428597962423]
  Large Language Models improve with increasing amounts of high-quality training data.<n>We find token-counts outperform manual and learned mixes, indicating that simple approaches for dataset size and diversity are surprisingly effective.<n>We propose two complementary approaches: UtiliMax, which extends token-based $200s by incorporating utility estimates from reduced-scale ablations, achieving up to a 10.6x speedup over manual baselines; and Model Estimated Data Utility (MEDU), which leverages LLMs to estimate data utility from small samples, matching ablation-based performance while reducing computational requirements by $simx.
  arXiv  Detail & Related papers  (2025-01-20T21:10:22Z)
• Over-the-Air Fair Federated Learning via Multi-Objective Optimization [52.295563400314094]
  We propose an over-the-air fair federated learning algorithm (OTA-FFL) to train fair FL models. Experiments demonstrate the superiority of OTA-FFL in achieving fairness and robust performance.
  arXiv  Detail & Related papers  (2025-01-06T21:16:51Z)
• Data Valuation and Detections in Federated Learning [4.899818550820576]
  Federated Learning (FL) enables collaborative model training while preserving the privacy of raw data. A challenge in this framework is the fair and efficient valuation of data, which is crucial for incentivizing clients to contribute high-quality data in the FL task. This paper introduces a novel privacy-preserving method for evaluating client contributions and selecting relevant datasets without a pre-specified training algorithm in an FL task.
  arXiv  Detail & Related papers  (2023-11-09T12:01:32Z)
• Analysis and Optimization of Wireless Federated Learning with Data Heterogeneity [72.85248553787538]
  This paper focuses on performance analysis and optimization for wireless FL, considering data heterogeneity, combined with wireless resource allocation. We formulate the loss function minimization problem, under constraints on long-term energy consumption and latency, and jointly optimize client scheduling, resource allocation, and the number of local training epochs (CRE) Experiments on real-world datasets demonstrate that the proposed algorithm outperforms other benchmarks in terms of the learning accuracy and energy consumption.
  arXiv  Detail & Related papers  (2023-08-04T04:18:01Z)
• A Dataset Fusion Algorithm for Generalised Anomaly Detection in Homogeneous Periodic Time Series Datasets [0.0]
  "Dataset Fusion" is an algorithm for fusing periodic signals from multiple homogeneous datasets into a single dataset. The proposed approach significantly outperforms conventional training approaches with an Average F1 score of 0.879. Results show that using only 6.25% of the training data, translating to a 93.7% reduction in computational power, results in a mere 4.04% decrease in performance.
  arXiv  Detail & Related papers  (2023-05-14T16:24:09Z)
• LAVA: Data Valuation without Pre-Specified Learning Algorithms [20.578106028270607]
  We introduce a new framework that can value training data in a way that is oblivious to the downstream learning algorithm. We develop a proxy for the validation performance associated with a training set based on a non-conventional class-wise Wasserstein distance between training and validation sets. We show that the distance characterizes the upper bound of the validation performance for any given model under certain Lipschitz conditions.
  arXiv  Detail & Related papers  (2023-04-28T19:05:16Z)
• Local Learning Matters: Rethinking Data Heterogeneity in Federated Learning [61.488646649045215]
  Federated learning (FL) is a promising strategy for performing privacy-preserving, distributed learning with a network of clients (i.e., edge devices)
  arXiv  Detail & Related papers  (2021-11-28T19:03:39Z)
• A Principled Approach to Data Valuation for Federated Learning [73.19984041333599]
  Federated learning (FL) is a popular technique to train machine learning (ML) models on decentralized data sources. The Shapley value (SV) defines a unique payoff scheme that satisfies many desiderata for a data value notion. This paper proposes a variant of the SV amenable to FL, which we call the federated Shapley value.
  arXiv  Detail & Related papers  (2020-09-14T04:37:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.