# Differentially Private Shapley Values for Data Evaluation

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 56 references that are in the map.
- First posted on arXiv 1 Jun 2022.

## Builds on (most cited first, 30 of 31)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Revisiting Unreasonable Effectiveness of Data in Deep Learning Era](https://mlsanity.com/paper/1707.02968/) (2017)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Estimating Training Data Influence by Tracing Gradient Descent](https://mlsanity.com/paper/2002.08484/) (2020)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [A Survey on Federated Learning Systems: Vision, Hype and Reality for Data Privacy and Protection](https://mlsanity.com/paper/1907.09693/) (2019)
- [Differential Privacy Has Disparate Impact on Model Accuracy](https://mlsanity.com/paper/1905.12101/) (2019)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Problems with Shapley-value-based explanations as feature importance measures](https://mlsanity.com/paper/2002.11097/) (2020)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms](https://mlsanity.com/paper/1908.08619/) (2019)
- [Data Valuation using Reinforcement Learning](https://mlsanity.com/paper/1909.11671/) (2019)
- [Neuron Shapley: Discovering the Responsible Neurons](https://mlsanity.com/paper/2002.09815/) (2020)
- [The Shapley Value in Machine Learning](https://mlsanity.com/paper/2202.05594/) (2022)
- [A Distributional Framework for Data Valuation](https://mlsanity.com/paper/2002.12334/) (2020)
- [GTG-Shapley: Efficient and Accurate Participant Contribution Evaluation in Federated Learning](https://mlsanity.com/paper/2109.02053/) (2021)
- [Efficient nonparametric statistical inference on population feature importance using Shapley values](https://mlsanity.com/paper/2006.09481/) (2020)
- [Bounding the Estimation Error of Sampling-based Shapley Value Approximation](https://mlsanity.com/paper/1306.4265/) (2013)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [Shapley values for feature selection: The good, the bad, and the axioms](https://mlsanity.com/paper/2102.10936/) (2021)
- [Robin Hood and Matthew Effects: Differential Privacy Has Disparate Impact on Synthetic Data](https://mlsanity.com/paper/2109.11429/) (2021)
- [Efficient computation and analysis of distributional Shapley values](https://mlsanity.com/paper/2007.01357/) (2020)
- [The Shapley Value of Classifiers in Ensemble Games](https://mlsanity.com/paper/2101.02153/) (2021)
- [Finding Influential Training Samples for Gradient Boosted Decision Trees](https://mlsanity.com/paper/1802.06640/) (2018)
- [Scalability vs. Utility: Do We Have to Sacrifice One for the Other in Data Importance Quantification?](https://mlsanity.com/paper/1911.07128/) (2019)
- [Influence in Classification via Cooperative Game Theory](https://mlsanity.com/paper/1505.00036/) (2015)

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

- [Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation](https://mlsanity.com/paper/2308.15709/) (2023)
- [Incentives in Private Collaborative Machine Learning](https://mlsanity.com/paper/2404.01676/) (2024)
- [A Survey of Privacy-Preserving Model Explanations: Privacy Risks, Attacks, and Countermeasures](https://mlsanity.com/paper/2404.00673/) (2024)
- [A Comprehensive Study of Shapley Value in Data Analytics](https://mlsanity.com/paper/2412.01460/) (2024)
- [Detect & Score: Privacy-Preserving Misbehaviour Detection and Contribution Evaluation in Federated Learning](https://mlsanity.com/paper/2506.23583/) (2025)
- [On the Fragility of Contribution Score Computation in Federated Learning](https://mlsanity.com/paper/2509.19921/) (2025)
- [Private and Robust Contribution Evaluation in Federated Learning](https://mlsanity.com/paper/2602.21721/) (2026)
- [Challenges in Enabling Private Data Valuation](https://mlsanity.com/paper/2603.00342/) (2026)

## Abstract (arXiv)

The Shapley value has been proposed as a solution to many applications in machine learning, including for equitable valuation of data. Shapley values are computationally expensive and involve the entire dataset. The query for a point's Shapley value can also compromise the statistical privacy of other data points. We observe that in machine learning problems such as empirical risk minimization, and in many learning algorithms (such as those with uniform stability), a diminishing returns property holds, where marginal benefit per data point decreases rapidly with data sample size. Based on this property, we propose a new stratified approximation method called the Layered Shapley Algorithm. We prove that this method operates on small (O(polylog(n))) random samples of data and small sized (O(log n)) coalitions to achieve the results with guaranteed probabilistic accuracy, and can be modified to incorporate differential privacy. Experimental results show that the algorithm correctly identifies high-value data points that improve validation accuracy, and that the differentially private evaluations preserve approximate ranking of data.