Adalina: Adaptive Linear Approximation for the Shapley Value and Beyond

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 $\Theta(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}{\epsilon^{2}}\log\frac{1}{\delta})$ utility queries to ensure $P(\\|\hat{\boldsymbol\phi}-\boldsymbol\phi\\|\geq\epsilon)\leq \delta$ 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 squared error $\mathbb{E}[\\|\hat{\boldsymbol\phi}-\boldsymbol\phi\\|^{2}]$ for each specific utility function. Accordingly, we introduce the first adaptive, linear-time, linear-space randomized algorithm, Adalina, that theoretically achieves improved mean squared error. All of our theoretical findings are experimentally validated. Our code is available at https://github.com/watml/adalina.

This work studies how to efficiently approximate the Shapley value and its extensions, which are popular tools for measuring the contributions of individual features, data points, or participants in cooperative systems. Computing these values exactly is usually extremely expensive because the required computation grows exponentially with the number of players. To address this challenge, we develop a new theoretical framework for efficient approximation while using only memory that scales linearly with the number of players. Our analysis further provides improved guarantees on the number of utility evaluations required to obtain sufficiently accurate estimates. Based on this framework, we design a new algorithm called Adalina, which adaptively reduces the expected approximation error for each specific problem instance. Adalina is the first randomized algorithm that is simultaneously adaptive, linear-time, and linear-space. Our framework also unifies several existing approximation methods, including OFA, unbiased kernelSHAP, SHAP-IQ, and regression-adjusted approaches, and clarifies when paired sampling techniques are helpful.