aiqbench analysis
This paper introduces Leverage SHAP, a method that provides provably accurate Shapley value estimates with significantly improved computational complexity compared to standard Kernel SHAP. By integrating leverage score sampling from active learning, the approach reduces model evaluation costs and lowers estimation error in explainable machine learning workflows. This advancement strengthens the theoretical foundations of feature attribution while offering practical efficiency gains for deploying interpretable models at scale.
Provably Accurate Shapley Value Estimation via Leverage Score Sampling
arXiv:2410.01917v3 Announce Type: replace Abstract: Originally introduced in game theory, Shapley values have emerged as a central tool in explainable machine learning, where they are used to attribute model predictions to specific input features. However, computing Shapley values exactly is expensive: for a general model with $n$ features, $O(2^n)$ model evaluations are necessary. To address this issue, approximation algorithms are widely used. One of the most popular is the Kernel SHAP algorithm, which is model agnostic and remarkably effective in practice. At the time of our original submission, no strong non-asymptotic complexity guarantees were known for Kernel SHAP. We address this issue by introducing Leverage SHAP, a lightweight modification of Kernel SHAP that provides provably accurate Shapley value estimates with just $O(n\log n)$ model evaluations. Our approach takes advantage of a connection between Shapley value estimation and agnostic active learning by employing leverage score sampling, a powerful regression tool. Beyond theoretical guarantees, we find that Leverage SHAP achieves an approximately $50\%$ reduction in error compared to the highly optimized implementation of Kernel SHAP in the widely used SHAP library [Lundberg & Lee, 2017].
Abstract:Originally introduced in game theory, Shapley values have emerged as a central tool in explainable machine learning, where they are used to attribute model predictions to specific input features. However, computing Shapley values exactly is expensive: for a general model with $n$ features, $O(2^n)$ model evaluations are necessary. To address this issue, approximation algorithms are widely used. One of the most popular is the Kernel SHAP algorithm, which is model agnostic and remarkably effective in practice. At the time of our original submission, no strong non-asymptotic complexity guarantees were known for Kernel SHAP. We address this issue by introducing Leverage SHAP, a lightweight modification of Kernel SHAP that provides provably accurate Shapley value estimates with just $O(n\log n)$ model evaluations. Our approach takes advantage of a connection between Shapley value estimation and agnostic active learning by employing leverage score sampling, a powerful regression tool. Beyond theoretical guarantees, we find that Leverage SHAP achieves an approximately $50\%$ reduction in error compared to the highly optimized implementation of Kernel SHAP in the widely used SHAP library [Lundberg & Lee, 2017].
Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2410.01917 [cs.LG]
(or arXiv:2410.01917v3 [cs.LG] for this version)
From: R. Teal Witter [view email] [v1] Wed, 2 Oct 2024 18:15:48 UTC (272 KB) [v2] Mon, 10 Mar 2025 15:52:54 UTC (3,360 KB) [v3] Thu, 8 Oct 2026 23:10:08 UTC (820 KB)
Full text under the publisher's open licence · 225 words
Related coverage
A Mike's-Eye View of ARC's Research
AI Alignment Forum · Jun 9, 2026
Amortized mean-shift interacting particles
arXiv · Jun 16, 2026
Hamiltonian-Guided Leverage Embedding: Robust Subspace Compression for Efficient QAOA Parameter Estimation
arXiv · Jun 9, 2026
The Machines that Make the Machines
NVIDIA · Oct 7, 2026