Research map / Learning theory and algorithms / Prediction and decision losses
Provably Accurate Shapley Value Estimation via Leverage Score Sampling
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 Leverage SHAP, a leverage-score-sampling variant of Kernel SHAP with closed-form leverage scores that yields provable accuracy guarantees using O(n log n) value-function evaluations.
Problem
Estimating Shapley values for black-box models needs exponentially many evaluations exactly; Kernel SHAP is popular but lacked non-asymptotic accuracy guarantees when subsampled.
Approach
Reformulate Shapley regression as unconstrained least squares via a projection, show leverage scores of the projected matrix have closed form proportional to inverse binomial coefficient of subset size, and sample subsets by leverage score with paired and without-replacement sampling.
Key results
- Leverage SHAP achieves on average 50.0% of the error of Optimized Kernel SHAP across non-trivial settings (error ratio table over m=5n to 160n).
- At m=10n, Leverage SHAP has best mean relative squared error on all 8 datasets, e.g., Independent mean 0.00257 vs 0.00507 for Optimized Kernel SHAP and 0.0269 for Kernel SHAP.
- Theorem gives O(n log(n/delta) + n/(epsilon delta)) evaluations in expectation for a (1+epsilon) objective-value guarantee.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace optimized Kernel SHAP sampling probabilities with leverage-score sampling | Shapley value estimation · Eight SHAP library datasets; non-unit error-ratio settings | relative squared ℓ2 error: 50.0% of the error | Helped |
| Use leverage-score sampling instead of Kernel SHAP sampling | Shapley value estimation · California | relative squared ℓ2 error (mean): 0.00301 -> 0.000249 | Helped |
| Use leverage-score sampling instead of Kernel SHAP sampling | Shapley value estimation · Diabetes | relative squared ℓ2 error (mean): 0.00791 -> 0.00227 | Helped |
| Use leverage-score sampling instead of Kernel SHAP sampling | Shapley value estimation · Adult | relative squared ℓ2 error (mean): 0.0104 -> 0.00416 | Helped |
| Use leverage-score sampling instead of Kernel SHAP sampling | Shapley value estimation · Correlated | relative squared ℓ2 error (mean): 0.0117 -> 0.00662 | Helped |
| Use leverage-score sampling instead of Kernel SHAP sampling | Shapley value estimation · Independent | relative squared ℓ2 error (mean): 0.00507 -> 0.00257 | Helped |
| Use leverage-score sampling instead of Kernel SHAP sampling | Shapley value estimation · NHANES | relative squared ℓ2 error (mean): 0.00713 -> 0.00505 | Helped |
| Use leverage-score sampling instead of Kernel SHAP sampling | Shapley value estimation · Communities | relative squared ℓ2 error (mean): 0.0231 -> 0.0139 | Helped |
| Add paired sampling (ablation) | Leverage SHAP · Sample-size experiments across settings | relative squared ℓ2 error: roughly four or more | Helped |
| Add Bernoulli sampling (sampling without replacement) (ablation) | Leverage SHAP · Small-n datasets | relative squared ℓ2 error: between 1.1 and 10 (about 2 in the typical setting) | Helped |
| Add Bernoulli sampling (sampling without replacement) (ablation) | Leverage SHAP · Large-n datasets | relative squared ℓ2 error | No clear effect |
| Use leverage-score sampling rather than optimized Kernel SHAP sampling | Shapley value estimation with noisy set-function access · Low and moderate noise (σ ≤ 0.1) | relative squared ℓ2 error | Helped |
Surprising findings
- Leverage scores of the projected matrix are exactly inversely proportional to the number of subsets of each size, so each subset size gets equal total weight.
- Multiplicative approximation of Shapley values is NP-hard in general black-box/circuit settings, motivating objective-value guarantees.
Limitations
- Theoretical guarantee applies to the independent sampling version; the released deterministic stratified implementation lacks formal analysis.
- Guarantee is in objective value; multiplicative per-feature approximation is NP-hard in general.
- Gains depend on gamma; performance erodes as gamma grows.
Experimental setup
Datasets: IRIS California housing Diabetes Adult Correlated Independent NHANES Communities
Benchmarks: IRIS California Diabetes Adult Correlated Independent NHANES Communities
Metrics: relative squared l2 error of Shapley values linear objective error
Baselines: Kernel SHAP Optimized Kernel SHAP (SHAP library) Permutation SHAP
Builds on: Kernel SHAP statistical leverage score sampling Tree SHAP stratified SVARM
Closest papers by meaning
- A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values (NeurIPS 2025 · similarity 0.92)
- Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values (NeurIPS 2025 · similarity 0.90)
- shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.89)
- KernelSHAP-IQ: Weighted Least Square Optimization for Shapley Interactions (ICML 2024 · similarity 0.89)
- Amortized Linear-time Exact Shapley Value for Product-Kernel Methods (NeurIPS 2026 · similarity 0.88)
- SHAP values via sparse Fourier representation (NeurIPS 2025 · similarity 0.87)
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.