# A Note on "Towards Efficient Data Valuation Based on the Shapley Value''

arXiv: https://arxiv.org/abs/2302.11431 · HTML: https://mlsanity.com/paper/2302.11431/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 13 references that are in the map.
- First posted on arXiv 22 Feb 2023.

## Builds on (most cited first, 7 of 7)

- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2110.14049/) (2021)
- [Data Banzhaf: A Robust Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2205.15466/) (2022)
- [A Principled Approach to Data Valuation for Federated Learning](https://mlsanity.com/paper/2009.06192/) (2020)
- [Improving Cooperative Game Theory-based Data Valuation via Data Utility Learning](https://mlsanity.com/paper/2107.06336/) (2021)

## Built on by (most cited first, 11 of 11)

- [Data Shapley in One Training Run](https://mlsanity.com/paper/2406.11011/) (2024)
- [LAVA: Data Valuation without Pre-Specified Learning Algorithms](https://mlsanity.com/paper/2305.00054/) (2023)
- [Capturing the Temporal Dependence of Training Data Influence](https://mlsanity.com/paper/2412.09538/) (2024)
- [Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation](https://mlsanity.com/paper/2308.15709/) (2023)
- [Efficient Data Shapley for Weighted Nearest Neighbor Algorithms](https://mlsanity.com/paper/2401.11103/) (2024)
- [An Economic Solution to Copyright Challenges of Generative AI](https://mlsanity.com/paper/2404.13964/) (2024)
- [A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms"](https://mlsanity.com/paper/2304.04258/) (2023)
- [Incentives in Private Collaborative Machine Learning](https://mlsanity.com/paper/2404.01676/) (2024)
- [One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently](https://mlsanity.com/paper/2410.23808/) (2024)
- [In-Run Data Shapley for Adam Optimizer](https://mlsanity.com/paper/2602.00329/) (2026)
- [Optimizing Product Provenance Verification using Data Valuation Methods](https://mlsanity.com/paper/2502.15177/) (2025)

## Abstract (arXiv)

The Shapley value (SV) has emerged as a promising method for data valuation. However, computing or estimating the SV is often computationally expensive. To overcome this challenge, Jia et al. (2019) propose an advanced SV estimation algorithm called ``Group Testing-based SV estimator'' which achieves favorable asymptotic sample complexity. In this technical note, we present several improvements in the analysis and design choices of this SV estimator. Moreover, we point out that the Group Testing-based SV estimator does not fully reuse the collected samples. Our analysis and insights contribute to a better understanding of the challenges in developing efficient SV estimation algorithms for data valuation.