BestSHAP: Best-of-Many Adaptive Approximations for the Shapley Value

The Shapley value has become a popular concept in attribution problems because it is uniquely characterized by a specified set of axioms. However, computing the Shapley value for a general characteristic function requires exponentially many queries, motivating extensive research into randomized approximation algorithms. Although several randomized algorithms achieve the best-known query complexity for a specified approximation guarantee, none consistently outperforms the others in practice. In other words, without access to the ground-truth Shapley values, it remains unclear which estimate is the most accurate. In this work, we show that identifying the potentially best estimate can come for free, without requiring access to the ground-truth Shapley values. As a first step, we introduce a class of provably adaptive randomized algorithms that retain the best-known query complexity while requiring only linear memory. These algorithms differ in their choice of control variates, and the effectiveness of the adaptivity associated with each variate depends on the characteristic function used. In particular, this class naturally generalizes the linear-memory KernelSHAP framework. The estimates produced by these algorithms can be obtained simultaneously using the same sequence of sampled subsets. Moreover, the mean squared errors of these estimates, which measure their expected approximation quality, can be approximated in parallel without increasing the time or memory complexity. These estimates of the approximation error thus enable us to select the potentially best candidate. Theoretically, the accuracy of this selection improves as the number of sampled subsets increases. Our theoretical results are supported by empirical evaluations. Furthermore, our proposed algorithm, BestSHAP, consistently outperforms existing linear-memory baselines.