# Variance reduced Shapley value estimation for trustworthy data valuation

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 48 references that are in the map.
- First posted on arXiv 30 Oct 2022.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [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)
- [Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms](https://mlsanity.com/paper/1908.08619/) (2019)
- [A Distributional Framework for Data Valuation](https://mlsanity.com/paper/2002.12334/) (2020)
- [Bounding the Estimation Error of Sampling-based Shapley Value Approximation](https://mlsanity.com/paper/1306.4265/) (2013)
- [A Survey on Data Pricing: from Economics to Data Science](https://mlsanity.com/paper/2009.04462/) (2020)
- [Model-based Pricing for Machine Learning in a Data Marketplace](https://mlsanity.com/paper/1805.11450/) (2018)
- [Data Valuation for Medical Imaging Using Shapley Value: Application on A Large-scale Chest X-ray Dataset](https://mlsanity.com/paper/2010.08006/) (2020)
- [SHAFF: Fast and consistent SHApley eFfect estimates via random Forests](https://mlsanity.com/paper/2105.11724/) (2021)
- [Revenue Maximization for Query Pricing](https://mlsanity.com/paper/1909.00845/) (2019)
- [A Unified Framework for Task-Driven Data Quality Management](https://mlsanity.com/paper/2106.05484/) (2021)
- [Proportional marginal effects for global sensitivity analysis](https://mlsanity.com/paper/2210.13065/) (2022)
- [DataBright: Towards a Global Exchange for Decentralized Data Ownership and Trusted Computation](https://mlsanity.com/paper/1802.04780/) (2018)

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

- [Stochastic Amortization: A Unified Approach to Accelerate Feature and Data Attribution](https://mlsanity.com/paper/2401.15866/) (2024)
- [From Points to Coalitions: Hierarchical Contrastive Shapley Values for Prioritizing Data Samples](https://mlsanity.com/paper/2512.19363/) (2025)
- [Scaling Laws for the Value of Individual Data Points in Machine Learning](https://mlsanity.com/paper/2405.20456/) (2024)
- [One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently](https://mlsanity.com/paper/2410.23808/) (2024)
- [Uncertainty Quantification of Data Shapley via Statistical Inference](https://mlsanity.com/paper/2407.19373/) (2024)
- [A Comprehensive Study of Shapley Value in Data Analytics](https://mlsanity.com/paper/2412.01460/) (2024)
- [Faithful Group Shapley Value](https://mlsanity.com/paper/2505.19013/) (2025)
- [Federated Recommender System with Data Valuation for E-commerce Platform](https://mlsanity.com/paper/2509.11196/) (2025)
- [Priority-Aware Shapley Value](https://mlsanity.com/paper/2602.09326/) (2026)
- [Towards Data Valuation via Asymmetric Data Shapley](https://mlsanity.com/paper/2411.00388/) (2024)
- [SIM-Shapley: A Stable and Computationally Efficient Approach to Shapley Value Approximation](https://mlsanity.com/paper/2505.08198/) (2025)
- [Semivalue-based data valuation is arbitrary and gameable](https://mlsanity.com/paper/2506.12619/) (2025)
- [Challenges in Enabling Private Data Valuation](https://mlsanity.com/paper/2603.00342/) (2026)
- [Adalina: Adaptive Linear Approximation for the Shapley Value and Beyond](https://mlsanity.com/paper/2604.08438/) (2026)
- [f-INE: A Hypothesis Testing Framework for Estimating Influence under Training Randomness](https://mlsanity.com/paper/2510.10510/) (2025)
- [Trading Vector Data in Vector Databases](https://mlsanity.com/paper/2511.07139/) (2025)

## Abstract (arXiv)

Data valuation, especially quantifying data value in algorithmic prediction and decision-making, is a fundamental problem in data trading scenarios. The most widely used method is to define the data Shapley and approximate it by means of the permutation sampling algorithm. To make up for the large estimation variance of the permutation sampling that hinders the development of the data marketplace, we propose a more robust data valuation method using stratified sampling, named variance reduced data Shapley (VRDS for short). We theoretically show how to stratify, how many samples are taken at each stratum, and the sample complexity analysis of VRDS. Finally, the effectiveness of VRDS is illustrated in different types of datasets and data removal applications.