Provably Adaptive Linear Approximation for the Shapley Value and Beyond
2026-04-09 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study how to efficiently approximate the Shapley value, a way to fairly assign credit among contributors, which usually requires a huge number of calculations. They develop a new mathematical framework that helps improve existing methods while using only linear memory space relative to the number of contributors. Their framework unifies several prior approaches and shows when certain sampling strategies work best. Based on this, they create Adalina, the first adaptive algorithm that works quickly and uses little memory, while producing more accurate estimates. The authors also verify their theoretical results with experiments.
Shapley valuesemi-valuesutility queriesvector concentration inequalitylinear-space algorithmrandomized algorithmpaired samplingmean square erroradaptive algorithmkernelSHAP
Authors
Weida Li, Yaoliang Yu, Bryan Kian Hsiang Low
Abstract
The Shapley value, and its broader family of semi-values, has received much attention in various attribution problems. A fundamental and long-standing challenge is their efficient approximation, since exact computation generally requires an exponential number of utility queries in the number of players $n$. To meet the challenges of large-scale applications, we explore the limits of efficiently approximating semi-values under a $Θ(n)$ space constraint. Building upon a vector concentration inequality, we establish a theoretical framework that enables sharper query complexities for existing unbiased randomized algorithms. Within this framework, we systematically develop a linear-space algorithm that requires $O(\frac{n}{ε^{2}}\log\frac{1}δ)$ utility queries to ensure $P(\|\hat{\boldsymbolφ}-\boldsymbolφ\|_{2}\geqε)\leq δ$ for all commonly used semi-values. In particular, our framework naturally bridges OFA, unbiased kernelSHAP, SHAP-IQ and the regression-adjusted approach, and definitively characterizes when paired sampling is beneficial. Moreover, our algorithm allows explicit minimization of the mean square error for each specific utility function. Accordingly, we introduce the first adaptive, linear-time, linear-space randomized algorithm, Adalina, that theoretically achieves improved mean square error. All of our theoretical findings are experimentally validated.