Research map / Learning theory and algorithms / Prediction and decision losses
A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a unified randomized-sketching framework for Shapley value estimators (KernelSHAP, unbiased KernelSHAP, LeverageSHAP) that gives the first non-asymptotic sample-complexity guarantees for KernelSHAP, and scales to MNIST/CIFAR10 via Poisson approximation of binomial sampling.
Problem
Exact Shapley values need exponentially many model evaluations, and existing model-agnostic estimators such as KernelSHAP lack non-asymptotic theoretical guarantees and do not scale to high-dimensional inputs.
Approach
Rewrites the constrained Shapley regression as an unconstrained regression with an orthonormal matrix U and a free shift lambda, so KernelSHAP, unbiased KernelSHAP and LeverageSHAP become sketched regression or sketched matrix-vector estimators; then proves sample-complexity bounds for kernel, leverage-score and modified row-norm sampling, with and without replacement.
Key results
- Matrix-vector and regression estimators with kernel, leverage and modified row-norm sampling achieve provable bounds; regression estimator generally outperforms matrix-vector multiplication in normalized MSE.
- On MNIST and CIFAR-10 with decision trees, the proposed estimators give consistently better results than the KernelSHAP library implementation.
- Modified l2 sampling bounds are never worse than leverage-score bounds and can be up to sqrt(d) better in some cases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the regression estimator instead of matrix-vector multiplication | Shapley value estimators · tabular and image datasets | normalized MSE | Helped |
| use leverage-score (ℓ2-squared) sampling instead of modified ℓ2 sampling | Shapley value estimators · evaluated datasets | normalized MSE | Helped |
| use leverage-score (ℓ2-squared) sampling instead of kernel-weight sampling | Shapley value estimators · evaluated datasets | normalized MSE | Helped |
| use modified ℓ2 or kernel sampling instead of leverage-score sampling | Shapley value estimators · synthetic experiment | normalized MSE | Helped |
| sample without replacement instead of with replacement (ablation) | matrix-vector multiplication estimator · evaluated datasets | normalized MSE | No clear effect |
| sample with replacement instead of without replacement (ablation) | regression estimator · some evaluated datasets | normalized MSE | Helped |
| use λ = α instead of λ = 0 (ablation) | matrix-vector multiplication estimator · evaluated datasets | normalized MSE | Helped |
| add paired sampling (ablation) | Shapley value estimators · evaluated datasets | empirical performance | Helped |
| use the high-dimensional implementation improvements | Shapley value estimators · MNIST and CIFAR-10 | normalized MSE | Helped |
| use KernelSHAP instead of other estimators | Shapley value estimators · MNIST | rank correlation | Mixed |
Surprising findings
- Sampling with replacement performs worse than brute force when m exceeds 2^d.
- The regression estimator with lambda = alpha outperforms the unbiased KernelSHAP choice lambda = 0 in matrix-vector form.
Limitations
- Theoretical bounds depend on quantities like norm of b_lambda that cannot be computed efficiently by users.
- No prescription on which without-replacement scheme to use.
- Whether kernel or modified row-norm sampling beats leverage scores on practical models such as neural networks is left open.
Experimental setup
Datasets: eight tabular datasets from the shap library (up to d=101) MNIST CIFAR-10
Benchmarks: MNIST CIFAR-10 eight shap-library tabular datasets
Metrics: normalized mean squared error time (seconds) insertion/deletion AUC Spearman rank correlation
Baselines: KernelSHAP (shap library) unbiased KernelSHAP LeverageSHAP
Builds on: KernelSHAP unbiased KernelSHAP LeverageSHAP
Closest papers by meaning
- Provably Accurate Shapley Value Estimation via Leverage Score Sampling (ICLR 2025 · similarity 0.92)
- Amortized Linear-time Exact Shapley Value for Product-Kernel Methods (NeurIPS 2026 · similarity 0.90)
- Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values (NeurIPS 2025 · similarity 0.89)
- shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.88)
- DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation (NeurIPS 2024 · similarity 0.88)
- Rethinking Data Shapley for Data Selection Tasks: Misleads and Merits (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.