Provably Accurate Shapley Value Estimation in High Dimensions via Sparse Leverage Sampling
NeurIPS 2026 · Main Track (Poster)Shapley values measure how much each input contributes to a model's prediction, but computing them exactly takes exponentially many evaluations. We introduce Sparse-Leverage SHAP, a sampling scheme for settings where only a few inputs matter, and prove it reaches relative-error accuracy with evaluations, depending on the number of influential inputs rather than the total number .
Read the abstract
Computing Shapley values exactly requires exponentially many evaluations of a cooperative value function, making approximation essential in high-dimensional applications. Recent leverage-score-based methods yield provably accurate estimators with sample complexity scaling linearly in the number of players, but this can still be too costly when only a small subset of players is truly influential. We study Shapley value estimation under a sparse influence model, where the Shapley vector is supported on an unknown set of size . Using the regression characterization of Shapley values, we propose a sparse leverage sampling scheme and analyze it via sparse matrix concentration. Our main result shows that the resulting estimator achieves relative-error approximation with value function evaluations, up to logarithmic and accuracy factors, thereby replacing the ambient-dimension dependence of prior guarantees with dependence on the intrinsic support size. Empirically, our method matches or improves over dense Leverage SHAP on sparse synthetic and real-data benchmarks, while exhibiting better numerical stability at small sample sizes.