A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
Authors: Tyler Chen
Akshay Seshadri
Mattia Jacopo Villani
Pradeep Niroula
Shouvanik Chakrabarti
Archan Ray
Pranav Deshpande
Romina Yalovetzky
Marco Pistoia
Niraj Kumar
Venue: NeurIPS 2025 poster ()
Keywords: Explainability
Interpretability
Machine Learning
Randomized Algorithms
Provable Algorithms
Sample Complexity
Sketching
Quantum-Inspired
Primary area: general_machine_learning
TL;DR: We present a unified framework of provably efficient randomized estimators for Shapley values. We also provide, for the first time to our knowledge, provable guarantees for KernelSHAP, the most popular Shapley value method.

Abstract: Shapley values have emerged as a critical tool for explaining which features impact the decisions made by machine learning models.
However, computing exact Shapley values is difficult, generally requiring an exponential (in the feature dimension) number of model evaluations. To address this, many model-agnostic randomized estimators have been developed, the most influential and widely used being the KernelSHAP method (Lundberg & Lee, 2017). While related estimators such as unbiased KernelSHAP (Covert & Lee, 2021) and LeverageSHAP (Musco & Witter, 2025) are known to satisfy theoretical guarantees, bounds for KernelSHAP have remained elusive. We describe a broad and unified framework that encompasses KernelSHAP and related estimators constructed using both with and without replacement sampling strategies. We then prove strong non-asymptotic theoretical guarantees that apply to all estimators from our framework. This provides, to the best of our knowledge, the first theoretical guarantees for KernelSHAP and sheds further light on tradeoffs between existing estimators. Through comprehensive benchmarking on small and medium dimensional datasets for Decision-Tree models, we validate our approach against exact Shapley values, consistently achieving low mean squared error with modest sample sizes. Furthermore, we make specific implementation improvements to enable scalability of our methods to high-dimensional datasets. 
Our methods, tested on datasets such MNIST and CIFAR10, provide consistently better results compared to the KernelSHAP library.

A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
Tyler Chen" Akshay Seshadri'
Mattia J. Villani"
Pradeep Niroula
Shouvanik Chakrabarti
Archan Ray
Pranav Deshpande
Romina Yalovetzky
Marco Pistoia
Niraj Kumari
Global Technology Applied Research, JPMorganChase, New York, NY 10001, USA
Abstract
Shapley values have emerged as a critical tool for explaining which features impact the decisions made by machine learning models. However, computing exact Shap- Iey values is difficult, generally requiring an exponential (in the feature dimension) number of model evaluations. To address this, many model-agnostic randomized estimators have been developed, the most influential and widely used being the KernelSHAP method (Lundberg Lee, 2017). While related estimators such as unbiased KernelSHAP (Covert & Lee, 2021) and LeverageSHAP (Musco & Witter, 2025) are known to satisfy theoretical guarantees, bounds for KernelSHAP have remained elusive. We describe broad and unified framework that encompasses KernelSHAP and related estimators constructed using both with and without re- placement sampling strategies. We then prove strong non-asymptotic theoretical guarantees that apply to all estimators from our framework. This provides, the best of our knowledge, the first theoretical guarantees for KernelSHAP and sheds further light on tradeoffs between existing estimators. Through comprehen- small and medium dimensional datasets for Decision- Tree
sive benchmarking models, we validate our approach against exact Shapley values, consistently achiev- ing low mean squared error with modest sample sizes. Furthermore, specific implementation improvements to enable scalability of our methods to high- dimensional datasets. Our methods, tested datasets such MNIST and CIFARIO, provide consistently better results compared to the KernelSHAP library.
make
Introduction
Explaining the prediction of machine learning model is as important as building the model itself, since it helps determine whether the model can be trusted to give meaningful predictions when deployed in real world [RSG16]. Such explanations of black-box decisions are all the more important in sensitive applications, such as medicine, finance, and law [Bur+16].
In the quest of explaining models, recent line of research has focused on developing local explanation methods with the objective identify the degree of influence of each feature that specific data point has on the model prediction. These include Explanation vectors [Bae+10]. LIME [RSG16], and Shapley values [$K14]. When local methods are expressed as additive feature attribution methods, ie.. the feature influence lincarly adds up to provide the model prediction, [LL17] provided game theoretic results guaranteeing that Shapley values provide a unique solution to additive feature attribution. For these reasons, has emerged as front-runner model agnostic explanation tool.
"Equal contribution. Email: (akehay.seshaadri, tyler. chen, mattia. vatria.villani)@jpmccees I Principal Investigator. Email: niraj xx7 www.arrjjcchaaeecoommm
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Shapley values have found relevance in other machine learning applications too. They have been used in measuring the global sensitivity analysis where for instance they have been used partition the coefficient of determination quantity in linear regression [SNS16]. More concretely, Shapley values offer a general approach of answering the following question: given model I trained on data-points with d features, and evaluated on test sample q E Rd, how does each feature of q locally influence the final model decision f())
Consider the value function 2 + R. where v(S) depends on the output of the model on a test sample q using only the subset of features corresponding to the elements of the subset S of [d] = (1.....)) .d). For instance, given a baseline q quase, we may define v(S) = f(q(() where 9; contribution is defined as
(5) 9, if j S and g)me otherwise. The Shapley value 0f corresponding to the j-th feature
|S|!(d - |S| 1}! (w(SU())) - -
Σ SCINM
(1.1)
d!
which is the aggregate of the marginal contribution of feature j to the model prediction achievable by the modified mean of all the subsets S that do not contain the feature j. As d increases, an exact solution quickly cannot be computed and estimation techniques are required. However, as Shapley values are increasingly used to interpret the model behavior, the quality of the estimator is of the utmost importance: unfaithful explanation may lead to incorrect model interventions, business decisions or court judgments whenever model assessment is involved.
1.1 Fast Approximate Estimators
In general, computing (1.1) requires evaluating v(S) on each of the exponentially many subsets of [d]. Each evaluation of vSS) is costly, with the exact cost depending on the way wSS) is defined. While this cost can be reduced for certain types of simple models [LEL18], appealing aspect of Shapley values is the potential for model- model-aggostic explanations.
To make Shapley values computationally tractable for arbitrary models, multiple randomized es- timators have been proposed. Such methods aim to approximate the Shapley values, while using a sub-exponential number of value-function evaluations; see [CGT09; WF20; OL21; MCFH22; Zha+24]. Perhaps the most popular is a method called KernelSHAP, which is implemented in the widely used SHAP library [LL17]. KernelSHAP and related estimators are the focus of this paper.
Approximate Shapley Value Estimation. In what follows, the all ones vector and zero vector are and 0 respectively, and the j-th standard basis vector is ej. Given a vector a, ||a]] denotes its Euclidean norm, while for a matrix A. ||A|| denotes its spectral norm. The key observation [CGKR88] used by KernelSHAP and related estimators is that the Shapley values are the solution to a certain constrained least squares problem
argmin EER" (())-
IZ' b1]
(1.2)
where Z' = VWW.bb VWe, and
Z is a (2d 2) x d binary matrix: Zs.; = j E S and Zs.; = 0if E
. W is (2d - 2) x (2 22) 2) diagonal matrix: Ws.s = k(S) = (d- 1)/(((()) (s((d (SD)
. is 2d - 2 length vector: Ug = v(S) - (0).
As with the definition of the Shapley values (1.1), the regression formulation (1.2) requires the knowledge of u(S) for each 2d subsets of [d]. To get around this cost, KerneISHAP (randomly) subsamples and reweights the rows of (1.2), and then outputs the solution to the (much smaller) constrained regression problem. The sampling of the 5-th row Zs is done proportional to the kernel
'There are other established ways to do this including replacing a fixed haseline with expectation over suitable inputs even training the model with only the features in S present [CSWJ18: LL17]. The precise choice is not important for us. as the methods discussed in this paper work for any value function. 'The matrices are indexed by S C 2 {[d]. 0).
2

---

weight k(S), choice made based on the observation that the objective function | Z' -bll can be with respect to this sampling distribution, as explained in Appendix B.I. Other practical improvements such as paired-sampling and sampling without replacement are also included in the implementation of KemnelSHAP in the SHAP library.
written as an expectation Z -5)) v
A large number of subsequent works have built on KemelSHHA [CL20; LL17; AJL21; Zha+24; MW25; Jet+21; KZ22; Fum+24; KTLM24]. Of particular relevance the present work are unbiased Kerme[SIAP [CL20] and LeverageSTIAP [MW25] which, to the best of our knowledge, are the only extensions of KemelSHAP with theoretical convergence guarantees. The method of [CL20] is an unbiased variant of KemelSHAP for which an asymptotic variance analysis is given. It was however observed that this method tends to underperform compared the original KerelSSHAP in practice. The method of [MW25] is regression based estimator and satisfies strong -symmmoti theoretical guarantees. Numerical experiments suggest that it may outperform KernelSHAP in most settings.
High--Dimensionl Estimators. Additionally, several works have specifically focused on the chal- lenges of computing Shapley values for high-dimensional data [AJL21; CSWJ18; Jet+21; Fry+20;; HZFS24; Zha+24]. These use parametric approaches to the computation of Shapley values; however, they require overhead model pretraining. Building on [Fry++0]], [HZFS24] develop a method for high-dimensional SHAP estimation using latent features. [CSWJ18] propose a specific approach for data structured on graphs; such approaches avoid computing SHAP for large dimensions leveraging inductive biases. Recently, [Zha+24] propose SimSHAP, an unbiased alternative to [Jet+21]. Methods for large language models, such as [Kok+21] have recently been develop; however, no algorithm at present is tailored for high dimensional settings while providing provable guarantees on sample efficiency.
1.2 Our Contribution
In this work, we present novel and unified framework to analyze Shapley value estimators. Using tools from randomized linear algebra, we prove non-asymptotic sample complexity guarantees on the efficient behavior of the estimators, including KernelSHAP [LL17] and LeverageSHAP [MW25]. Specifically, we identify three main contributions of the present work:
Unified Framework: We present a unified framework which encompasses many existing randomized estimators for Shapley values, including the widely used KemelSHAP method. Our framework is derived by rewriting the standard constrained regression formulation of the Shapley values either an ordinary linear regression problem matrix-vector multiplication.
bounds for estimators within our framework constructed via both with and without replacement sampling strategies. This immediately gives, for the first time our knowledge, theoretical guarantees for Ker- nelSHAP. Our theory also provides insight into the relative performance of estimators such as LeverageSHAP and KernelSHAP, as well novel estimator built with kernel re-weighted fz distribution.
Provable Guarantees: We prove non-as -on-asympootic
We make specific implementation improvements to Shapley value computation that allow our methods to scale beyond all other theoretically grounded methods. We test these on image datasets (MNIST and CIFARIO) with consistently better results compared to KernelSHAP library.
Shapley Value Estimation for High Dimensional Inputs:
These advancements promote trust in the estimation of Shapley values, enabling their usage in safety-critical applications. In Section 2, we develop the unified framework: defining the estimators and distributions in Section 2.1 and Section 2.2 respectively, and providing our main result on sample complexity guarantees in Section 2.3. In Section 3, we perform an extensive experimental evaluation of the described estimators, comparing their performance in Section 3.1, and showcasing their effectiveness in higher dimensional settings Section 3.2.
2 A Unified Framework for Provable Shapley Value Estimation
The main theoretical contribution of our paper is a unified framework through which many existing estimators for Shapley value estimation can be understood. We provide non-asymptoti theoretical
3

---

guarantees for all methods within our framework, including that of the widely used KemelSHAP method.
Towards this end, it is useful to reformulate (1.2) in terms of an ordinary linear regression or a matrix- vector multiplication problem involving matrix with orthonormal columns. The key observation herein is that any vector & E R satisfying the constraint 1't & =([d)- e(0) can be decomposed as the sum of vector proportional to 1 (with proportionality constant (v[[d] - v(1))/d) and a vector orthogonal to 1. By converting (1.2) to an unconstrained problem, we will be able to more easily understand how popular Shapley value estimators can be studied through the lens of randomized numerical linear algebra.
Theorem 2.1. Let Q be any fixed d x (d-1) matrix whose columns form an orthonormal basis for the space of vectors orthogonal to the all-ones vector (i.e. Q'Q I, Q 0). Given À E I. define
U= = d-1 Z'Q:
a:
bx = V d (b AZ'1).
d
Then, UT = I and
Φ" Q argmin
Ux bxll + QU b^ al.
#ER
similar formulation of the Shapley values in terms of unconstrained regression appears in [MW25]. Theorem 2.1, which is proved in Appendix A.3, goes beyond that of [MW25] in two key ways. First, we observe that by solving the unconstrained problem explicitly, we obtain the solution as the product of matrix QUT T and vector bx- Second, we make the observation that there is complete freedom in the choice of E IR. Together, these advancements allow us to develop a unifying framework for providing provable guarantees for broad class of randomized estimators which encompasses many existing estimators [CL20; LL17; AJL21; Zha+24; MW25, etc.].
2.1 Randomized Estimators Within our Framework
We frame our exposition in the context of randomized sketching, a powerful technique which has been studied for decades in randomized numerical linear algebra [Woo+14; MT20].
In the context of Shapley value estimation, a sketching matrix is an m x (2d 2) matrix S where each row has exactly one nonzero entry and E E[STST = We leave the exact choice of the distribution of S general, but discuss several natural choices in Section 2.2. Regardless of the distribution, since each of the m rows of S has exactly one nonzero entry, computing Sb requires at most m evaluations of vS)). Thus, estimators which make use of Sb can be substantially more efficient to compute when m < 2d.
Using the sketch Sbx (which can easily be computed from Sb) in the formulations in Theorem 2.1 yields estimators based on sketched regression or on approximate matrix-vector multiplication.
1. Sketched Regression: Methods such as KernelSHAP and LeverageSHAP can be viewed as sketched versions of the regression formulation of the Shapley values:
Q argmin| S(Ux b + wERd-1
Given the sketching matrix S, this regression (or least squares) estimator be computed in O(md² + mT.) time, where T, is the time to evaluate an entry of b.
2. Approximate Matrix-Vector Vector Multiplication: Instead of approximating the regression prob- lem, methods such as unbiased KemneSSHAP approximate the closed-form solution U bx directly:
X ST +al.
This estimator is unbiased (provided E|ST S] I) and, given the sketching matrix S, can be computed in O(md + mT,,) time, where T, is the time to compute v(S).
'At first glance it is not obvious that KemeISHAP, which solves an approximation to the constrained problem (1.2), can be expressed this way. However, a careful computation (see Appendix B.1) reveals that the KemeISHAA estimator is indeed special case of the general regression estimator (with À a).

---

We provide proofs that the estimators from [LL17; CL20; MW25] fit into our framework in Ap- pendix B. Past works, especially [CL20], have used a Lagrangian framework obtained closed-form solutions to their randomized estimators. While this is mathematically equivalent to our change of variable approach, as described Appendix C, the expressions, which involve ratios of correlated random variables, are seemingly harder to analyze directly in the Lagrangian framework leading to previous difficulties in providing proofs of KerneISHAP [CL20].
2.2 Sampling Schemes for Sketching Matrix
The choice of S plays a critical role in both the regression and matrix-vector multiplication estimators- which m entries of b are observed impacts what we lear about the Shapley values. However, model- agnostic estimators cannot make strong assumptions about the structure of b. The relative importance of the i-entry of can be encoded in probability distribution P over subsets S C 2 \ {[d], 0}. This distribution is subsequently used generate S and hence sample the entries of b. In the context of Shapley value estimation, it is common to use further optimizations such as paired sampling and sampling without replacement, which we explore empirically in Section 3.
Since the values of are costly to observe and are highly dependent on the given model, it is natural to choose the P based on U. Two popular choices sampling based the kernel weights (as done in KeAP) and sampling based on the leverage scores of U (as done in LeverageSHAP) We therefore analyze these distributions in our study, along with another distribution that interpolates between these two.
1. Kernel Weight Sampling: The KernelSHAP and unbiased KernelSHAP methods use ps o k(S). This is heuristic choice based on the fact that expressions like TZ') can be naturally written the expectation of certain random variables with respect to this sampling distribution.
Z' and (Z')Tb
2. Leverage Score / fz-squared Sampling: The LeverageSHAP method chooses sampling probabilities proportional to the statistical leverage scores of U. Since U has orthonormal columns, the leverage score of the Sth row of U coincides with the squared row-norm || which is widely used the quantum -onnture-nsppeed algorithms framework [Tan19]. Leverage score sampling for sketched regression satisfies strong theoretical guarantees, which [MW25] use to prove guarantees about the LeverageSHAP estimator.
3. Modified & Sampling: The modified row-norm sampling scheme is obtained by taking the usual geometric mean of kernel weights and leverage scores. The theoretical bounds we derive for these weights are never worse than the bounds for fz-squared sampling in the worst-case (up to constant factors), but can be up to a factor of /d better in some cases.
All the above distributions can be thought of special cases of family of distributions that interpolate between kernel weights and leverage scores. Specifically, given a parameter т E [0, 1]. we can consider the distribution
Dig (11ss))1)
(2.1)
which is the weighted geometric mean of the kernel weights and the leverage scores (see (A.66) for the full expression). 1 gives kernel weight distribution, T 0 gives leverage score sampling, while r = 1/2 gives modified lg sampling.
'The approaches we consider only take into account relative importance individual rows. Other approaches (e.g. based on Determinantal Point Processes/volume sampling) take into account the relative importance of entire sets of rows. This results in stronger theoretical guarantees for general regression problems, but such distributions are harder sample from [DM21].
5

---

= 10
d = 100
d = 1000
Rel. Probability
5
10
50
100
0
500
1000
Subset Size
Figure 1: Comparison of the sampling probabilities described in Section 2.2. Kernel Weights (dashed), Leverage scores (dash-dot), and our proposed modified fz-weights (solid), which are the geometric mean of the Kernel Weights and Leverage scores.
Note: In the remainder of the study, we interchangeably use the term (modified) row-nonn sampling with (modified) fo-nrrm sampling, and leverage sampling with fz-squared sampling.
2.3 Theoretical Guarantees of Shapley Value Approximation
now provide bounds on the sketching dimension m required to ensure a Shapley value estimator Φ E {ΦR M) satisfies a guarantee
pll0- - < > 1-6,
(2.2)
for some accuracy parameter E > O and failure probability parameter 8 E (0,
While there are number of ways to construct a m 2d sketching matrix S from sampling probabilities p = (es))ctt(((((410) We analyze two common choices:
1. With Replacement:
Each the m rows of S are sampled independently. For given row, single entry is selected be nonzero according to P. The value of this nonzero entry is 1/ /mps. where is the index of the nonzero row; see Appendix A.2.
2. Without Replacement: For each subset S, we flip coin that returns heads with probability qs. If the coin is heads, we add row to S, where the S-th entry of the row is nonzero and takes value 1/ /Ts. The probabilities qs are chosen based on the P so that, the dimension of the sketching matrix is equal, on average, to some target value see Appendix A.5.
To reduce the notational burden, we parameterize our bounds in terms
|usl 2
|usl1 (zs)?
max Mid),)
7(=)
Σ
Z ZER 2ER22-2
(2.3)
PS
Ps
SE2 ((4.0)
Our main theoretical result, which we prove in Appendix A.3 using techniques from randomized numerical linear algebra [Woo+14; Tro15; MT20], the following:
Theorem 2.2. Define Pu == (I - UUT,, and fix À E l.. Let m denote the sample complexity in the sampling with replacement scenario and the average sample complexity in the sampling without replacement scenario. Then, for the regression estimator,
m=
m m= (Pobx) SE2
(d) ))
+ 1o
guarantees
P[[ - ΦR1l < > 1-
and for the matrix-vector multiplication estimator;
m = 0 (bx)
guarantees
-1 < >
8G2
A direct computation reveals that > (Pbbb)) < v/ Pubxl S n/llba13 where the first inequality is by the definition of y) and second inequality is due fact that Pt the orthogonal projector onto the column-span of U. However, for particular bx each of these incqualities may not be sharp.

---

In Table 1, we provide more refined bounds for the kernel weight, leverage score, and modified row-norm sampling probabilities from Section 2.2. More precise bounds are stated and derived in Appendix A.4, and we also give bounds for the family of distributions defined in (2.1) in Remark 11 Importantly, the bounds for modified row-norm sampling are no worse than leverage scores, but can be up to a factor of vd better in some cases. Furthermore, up to log factors, the bounds for kernel weights are no worse than both leverage scores and modified row-norm sampling, but can be factor of d/ log(d) d) or vd/ log(d) better than leverage scores and modified row-norm sampling in some cases, respectively. These observations are formalized in Corollary A.9, and we construct an adversarial model demonstrating such an advantage in the sample complexity bounds in Appendix E. Intuitively, kernel weights and modified row-norm sampling place a larger importance on subsets of small/large size, seen from Fig. 1. As result, for models where the entries of the vector bx or by are concentrated around subsets of small/large size, kernel weights or modified row-norm sampling would perform better than leverage score sampling, which is the key observation constructing the adversarial model in Appendix E. It remains to be seen whether kernel weights or modified row-norm sampling scheme provides a sample complexity advantage over leverage scores for models used in practice (such as neural networks), and we leave this as an open question for future research.
use for
<(Pbs))
7(xx)
"
Kernel Weights Leverage Scores
d loo((d)
H P 1? d Pub d bull
dlog(d)
||
dlog(d)
d | 1
d
Modified row-norms
d dII Hbbl?
d
Table 1: Bounds (big-O) parameters in Theorem 2.2 for the sampling weights from Section 2.2,
derived in Corollary 10. H is diagonal matrix defined in Corollary A.10 satisfying Amin (H) =
@(1/Vd) and Amax (H) = (1), so that |>||/|<>||| E [@(1/vd), @(1)] Hence, the bounds for kernel sampling are within log(d) (f) factor of leverage score sampling in the worst case, but can be
better by factor d/ (d) in some cases. On the other hand, the bounds for modified & sampling
are never worse than leverage score sampling, but can be better by factor of vd in some cases (see Corollary A.9).
3 Experiments
Based on our framework, Appendix F describes the pseudo-code of the randomized estimators based on sampling with-replacement Algorithm and nethout-replacement Algorithm 2. We evaluate these estimators across range of synthetic and real world settings. Of primary interest is the mean squared error distance from the true Shapley value (normalized: mse EEll Φ- 1 ( we explore the convergence of these estimators to the true Shapley Values. We set out to find the best strategy, but our findings reveal that each method has its own merits across different scenarios. A summary of the experiments is provided here, with details deferred to the following sections.
In the experiments that follow, [MW25] has been re- immlememteedd to (a) allow the methods to be computed in high dimensions efficiently, and (b) to ensure a fair comparison between regression and matrix-vector multiplication method by fixing a single SZ for both estimators. We include results from our implementation of KernelSHAP (regression + kernel weights) as well as the implementation of KernelSHAP from the shap library. This particular implementation includes several additional heuristic optmizations.
We run experiments eight popular tabular datasets from the shap library (up to d 101) and two image datasets (MNIST d 784, and CIFAR-10 d = 3072), details on each dataset are in Appendix G.2. In each dataset, we train XG-Boost model [CG16] to compute the exact Shapley values using TreeExplainer class in shap [Lun+20]. We report a summary of the experimental findings while leaving detailed experiments Appendix G.
Following [CI.20; MW25], we run our experiments using paired sampling, simple modification of the estimation procedure, which has been observed to improve empirical performance. In paired
7

---

(1)
Independent (dim m 60)
Correlated (dim m 60)
NHANES (dim 79)
Communities (dim = 1011
16
10a
14
16a
10-7
18a4
10a4
10
101
10a
1.0
10a
10'
10
10'
10
(2)
medifled
HV
KornelSHAP
Mean Squared Error
Independent
Communities
10a
10
101
101
10a
10
207
10
2014
10"1
10-4
10
16a
30'
30
30
102
3
30a
20'
18
10a
30'
201
NV modifted
NV 1 squared
MV kernel
KerneiSHAP
LS modifted
L5 aquared
LS kernel
(3)
Independent (dim
Correlated (dim
NHANES
Communittes (dim 103)
10a
30-
10a
10a
10a
18-1
10
10"
MV (bo La squared)
MV (Be. la modifled)
IV (ba,, squared)
NV (bo modifled)
Number Samples
Figure 2: Comparison of performance across different estimators. In (I, top row) estimators use with replacement sampling strategies. In (2,3, central and bottom row) SZ is sampled without replacement. legends, MV refers to matrix-vector multiplication estimator and LS to regression (least squares) estimator. Dimensions of each datasets reported with the titles.
sampling, when index S c 2/4| \ {[d]00 0} is selected, the compliment S = [d] \ S is also selected. Paired sampling is also used by default in implementation of KemneISHAP from the shap library.
We run our experiments on an AMD EPYC 7R13 processor with 48 cores per socket, 96 CPUs, and 183GB RAM.
3.1 Comparisons of Estimators
For each dataset, choose the first data points of the train and the test sets, according to an 80/20 split, as baseline, and query points for our Shapley estimators respectively. We choose 103, 10 /2, 10 ..... 10 /2 for larger datasets (d 12) and pick specific values of m for smaller datasets. We run the experiments on random seeds O, 99 (numpy and Python's random) for replicability of results. Exact Shapley values computed with TreeExplaine lainer the same baseline; Kernel Expl ainer is run without é regularization. XG-boost regressors and classifiers fit with 100 estimators and maximum tree depth of 10. We highlight key observations in Fig. where we plot median normalized mean squared errors for 100 random seeds, alongside interquantile ranges, Except when specified otherwise, we use À a. Detailed results, variations and tables are in Appendix H.l. Our findings are as follows.
Matrix- Vector Multiplication vs. Regression Estimator. We showcase the effectiveness of each Shapley value estimator practice, reporting a comparison between the best performing distribution in Fig. 2 (1, with replacement; 2 without replacement). The clearest separations across methods appears in the comparison between matrix vector multiplication and regression estimators. We find that regression estimator tends to perform better than matrix-vector multiplication estimator. KernelSHAP generally positioned between these methods in the ranking, This is highlighted in Fig. 2.
8

---

MNIST
Natrix Vector
3/0
Least Squares
KernelSHAP
Kenee
Mat/Wcc
AUC Daletion (%)
Rank Correlation
Mean Squared
Kemelbiaa
Higher Piduity
CIFAR10 Us
3001
200
14
KomeSHAPP
Seai nee
Rank Correlation
AUC Deletion (%)
Mat
Mean Squared
Cernetivee tonge
Higher Fidelity
Time
AUC Insertion (%)
Number Samples
Figure 3: Comparison of estimators in image datasets: MNIST (top row) and CIFAR (bottom row). In the first column, (1, left column) performance of estimators is measured with mean squared error (normalized) from true Shapley value and time (in seconds). (2, center column) Area under the curve (AUC) calculation for insertion (x-axis) and deletion curves (y-axis) have been provided, computed on the top 100 features; reported as percentage under the curve. (3, right column) Spearman rank correlation for increasing number of samples.
Comparison Across Distributions. Among the three sampling schemes evaluated, our results in Fig. 2 (1,2) indicate that the fz-squared method outperforms modified & marginally, while outperforming kernel distribution more significantly in both regression and matrix- vector multiplication approximations. As discussed in Section 2.2, the choice of sampling distribution affects the performance of the estimator; with the best choice being problem dependent. In Appendix E, we design synthetic experiment where estimators based on modified & and kernel distributions significantly outperform lz-squared distribution based estimator.
With and Without Replacement Sampling Strategies. Sampling strategies (with and without replacement) perform similarly for the vector multiplication estimator. For the regression estimator, sampling with replacement outperforms sampling without replacement some datasets. However, sampling with replacement strategy is poorly suited for settings where m 2d, since will perform worse than brute force computation of Shapley values.
Comparing λ=0 versus λ=o for the Matrix-Vert the performance of matrix- vector multiplication estimator using À = 0 and X = a (i.e., by vs b..) in Fig. 2 (3). As noted in Appendix B, the unbiased KemeelSHA method of [CL20) uses X = O, while the other methods we have explored use a. We find that using À a the estimator leads to better performance.
Multiplication Estimator. We compare
3.2 Provably Efficient Methods in High- Biggh-Dmensions
For high dimensional datasets, aim to compare the estimators across f'itthfulness measures, as well as mean squared error. We compute Shapley values on the first 10 data points from the test sets, using the first data point of the training set, using 80/20 splits. As before, we train a decision tree in order to be able to compare with exact Shapley value computed from the TreeExplainex class. For each method, we compare average normalized mean squared error across test points, computational costs and faithfulness of the explanations. Mean squared error is juxtaposed with time (in seconds) in Fig. 3 ((a,b) to emphasize computational tradeoff's between methods. Faithfulness via both area under the curve (AUC) of insertion and deletion curves in Fig. 3 2(a.b), and Spearman rank correlation between exact and estimated Shapley values (as reported in Fig. 3, 3(a.)). Detailed experimental results with errors can be found in Appendix H.2.

---

Algorithmic Innovations. Approximating Shapley values in high dimensional problems is a chal- lenge. There are two computational bottlenecks [MW25]: (a) for distributions beyond f2-squreed, combinatorial terms (o) will cause overflow/nderffow for sufficiently large d and middle & (i.e.. k ~ d/2), and (b) even if we are able compute the binomial term, [MW25] bucket sampling proce- dure requires binomial sampling from a distribution with support of size (i) which can be large. In our Algorithm 2, we overcome both issues for all distributions by (a) avoiding the computation of the combinatorial terms in the probability distributions and weights, and (b) using Poisson approximation of large binomials to avoid the large support problem. This allows an analysis of our estimators on CIFAR10.
Estimator Performance. In Fig. part (aa-,), experiments confirm that regression estimators generally requires less time and lead to better approximations for fixed number of samples compared to matrix-vector multiplication estimator. Indeed, this discrepancy is accentuated as the dimension size increases. The regression estimator produces accurate estimates even when the number of samples is small, improving on all other estimators.
Faithfulness. In Fig. 3 part 2(a-b) and 3(a-b); after 100k samples, we find that for MNIST, all estimators have similar fidelity, but KernelSHAP has very high rank correlation. This may be due to the fact that KernelSHAP first samples from buckets of size and d, difference which may be beneficial in this setting. For CIFAR-10, there have been significant increases in rank correlation, showcasing the effectiveness of the estimators. In all settings, we find increased fidelity especially as the dimensionality of the problem increases. We note this could be problem dependent. We report AUC curves in Appendix H.3.
Discussion
We have provided a theoretical grounding for the use of randomized estimators in the context of Shapley value computation. We have achieved this by means of sample-efficient convergence guarantees for broad family of estimators, including the popular estimator KerneISHAP and the recently introduced LeverageSHAP. Responsible use of explainable-AI methods involves an understanding of how estimators scale as sample complexity is increased, especially when computing the exact ground truth Shapley values are not computationally feasible. This work on unified framework provides definitive step in this direction.
Limitations. Computing accurate Shapley values remains a challenge. As with past work, the theoretical bounds we derive for Shapley value estimators depend on quantities involving bx (e.g. (ibal)) which cannot be computed efficiently. As such, they cannot be instantiated by the user. Below, we give prescription on how this limitation can be mitigated in practice, but leave a thorough study for future research. Also note that there are several approaches to sampling without replacement and the present work does not provide prescriptions on which to use; this is left to future work.
Practical Prescription. As our analysis reveals, the estimators converge in predictable way with the number of samples (m) to the true Shapley value, at the rate of ~ 1/ m. Therefore, we can use the estimate from larger value of to approximate the error at some mg < m. As long as m >> ma. the estimate using m samples is good proxy for the true Shapley values, relative to the error of the estimate using mg samples. We find that this method, while heuristic, gives a good estimate of the error in practice.
Future Work. This work promotes trust in the estimation of Shapley values, promoting responsible use of the estimators in the explainable-AI community. Our theoretical contributions of a unified framework pave the way for development of tailored estimators depending on the observed entries of by. which can be used to adapt the sampling distribution accordingly. Developing such adaptive estimators, as well as their theoretical analysis, is left as an interesting direction for future research.
Acknowledgements
The authors thank Rob Otter and Shaohan Hu for their support and valuable feedback on this project. We also acknowledge our colleagues the Global Technology Applied Research Center of JPMorganChase, especially Sriram Yechan Gunja and Rajagopal Ganesan, for helpful discussions.
10

---

We would also like to thank R. Teal Witter and Christopher Musco for providing us the code for LeverageSHAP [MW25].
Disclaimer
This paper prepared for informational purposes by the Global Technology Applied Research center of JPMorgan Chase & Co. This paper is not a merchandissbllesellabee product of the Research Department of JPMorgan Chase & Co. its affiliates. Neither JPMorgan Chase & Co. any of its affiliates makes any explicit or implied representation or warranty and none of them accept any liability in connection with this paper, including, without limitation, with respect the completeness, accuracy, or reliability of the information contained herein and the potential legal, compliance, tax, accounting effects thereof. This document is not intended investment research or investment advice, or as recommendation. offer, or solicitation for the purchase or sale of any security, financial instrument, financial product service, or to be used in any way for evaluating the merits of participating in any transaction.
References
[AJL21]
K. Aas, M. Jullum, and Løland. "Explaining individual predictions when features are dependent: More accurate approximations Shapley values". In: Artificial Intelligence 298 (2021), p. 103502 (cit. on pp. 4).
[Bae+10]
D. Baehrens, T. Schroeter, S. Harmeling, M. Kawanabe, K. Hansen, and K.-R. Müller. "How to explain individual classification decisions", In: The Journal of Machine Learn- ing Research (2010) (cit. on p. 1).
[Bur+16]
C. Burton, L. De Boel, C. Kuner, A. Pateraki, S. Cadiot, and S. G. Hoffman. "The final curopean union general data protection regulation", BNA Privacy & Security Law Report (2016) (cit. p. 1).
[CG16]
T. Chen and C. Guestrin. "Xgboost: A scalable tree boosting system". In: Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. 2016, pp. 785-794 (cit. on p. 7).
[CGKR88]
A. Charnes, B. Golany, M. Keane, and J. Rousseau. "Extremal Principle Solutions of Games in Characteristic Function Form: Core, Chebychev and Shapley Value General- izations". In: Econometrics of Planning and Efficiency. Springer Netherlands, 1988, pp. 123-133 URL: http: // /xxx doi org 10 1007 978 94 009 3677-3677--0 - 5_7 (cit. on p. 2).
[CGTO9]
J. Castro, D. Gómez, and J. Tejada. "Polynomial calculation of the Shapley value based on sampling". In: Computers Operations Research 36.5 (2009), pp. 1726-1730
(cit. p. 2).
[CL20]
I. Covert and S.-I. Lee. "Improving kernelSHAP: Practical Shapley value estimation via linear regression". In: http: // arziv. org/ abs/ 2012. 01536 (2020) (cit. on
pp. 3-5, 7, 9, 36).
(CSWJ18)
J. Chen, I.. Song, M. Wainwright, and M. Jordan. "I.-Shapley and C-Shapley: Efficient model interpretation for structured data". In: arXiv preprint arrXiv:188..020 (2018) (cit. pp. 2,
[DM21]
M. Dereziński and M. W. Mahoney. "Determinantal Point Processes in Randomized Numerical Linear Algebra", In: Notices of the American Mathematical Society 68.01
(2021), p. URL: http:://ds doi. org/10....... 20090/noti2000 (cit. on p. 5).
[Fry+20]
C. Frye, D. de Mijolla, T. Begley, L. Cowton, M. Stanley, and I. Feige. "Shapley explainability the data manifold". In: arXiv preprint arXiv:2006.01777 (2020) (cit.
on p. 3).
[Fum+24]
F. Fumagalli, M. Muschalik, P. Kolpaczki, E. Hüllermeier, and B. Hammer. "KemelSHAP-IO" Weighted least-square optimization for Shapley interactions". In: arXiv preprint ar05v:2405. 10852 (2024) (cit. on p. 3).
[HZFS24]
X. Hu, M. Zhu, Z. Feng, and L. Stanković. "Manifold- Shapley explanations for high dimensional correlated features".. In: Neural Networks 180 (2024), p. 106634 (cit. p. 3).

---

[Jet+21]
N. Jethani, M. Sudarshan, I. C. Covert, S.-L. Lee, and R. Ranganath. "Fastshap: Real- time Shapley value estimation", In: Proceedings of the 38th International Conference on Machine Learning. 2021 (cit. on p. p)
[Kok+21]
Kokalj, B. Skrlj, N. Lavrač, Pollak, and M. Robnik Robnik-Sikonja. "BERT meets Shapley: Extending SHAP explanations to transformer-basee classifiers". In: Proceedingg of the EACL hackashop on news media content analysis and automated report generation. 2021, pp. 16-21 (cit. on p. 3).
[KTLM24] S. Kariyappa, L. Tsepenekas, F. Lécué, and D. Magazzeni. "SHAP@ k: efficient and probably approximately correct (PAC) identification of top-k features". In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. 12. 2024, pp. 13068-13075 (cit. on p. 3).
[KZ22]
Y. Kwon and J. Y. Zou. "Weightedshap: analyzing and improving shapley based fea- ture attributions". In: Advances in Neural Information Processing Systems 35 (2022), pp. 34363-34376 (cit. on p. 3).
[LELL18]
S. M. Lundberg, G. G. Erion, and S.-I. Lee. "Consistent individualized feature attri- bution for tree ensembles". In: http: // arziv. org/ abs 1802. 03888 (2018) (cit. p. 2).
[LL17]
S. M. Lundberg and S.-I. Lee. "A unified approach to interpreting model predictions". In: Proceedings of the 30th Conference on Neural Information Processing Systems (NeurIPS) (2017) (cit. on pp. 1-5, 36, 40).
[Lun+20]
S. M. Lundberg, G. Erion, H. Chen, A. DeGrave, J. M. Prutkin, B. Nair, R. Katz, J. Himmelfarb, N. Bansal, and S.-L. Lee. "From local explanations to global understanding with explainable AI for trees". In: Nature Machine Intelligence 2.1 (2020), pp. 2522- 5839 (cit. on p. 7).
[MCFH22]
Mitchell, Cooper, Frank, and G. Holmes. "Sampling permutations for Shapley value estimation". In: Journal of Machine Learning Research 23.43 (2022), pp. 1-46 (cit. on p. 2).
[MT20]
P.-G. Martinsson and J. A. Tropp. "Randomized numerical linear algebra: Foundations and algorithms". In: Acta Numerica 29 (2020), pp. 403-572. URL: http:://aatt doi. org/10. /0t...00//0229999200000000
(cit. on pp. 4, 6, 22).
[MW25]
Musco and R. T. Witter "Provably Accurate Shapley Value Estimation via Leverage Score Sampling". In: Proceedings of the 13th International Conference on Learning Representations (ICLR). 2025. URL: atttps://arxa www. abs/a/as//aa 2410..4000000 01917 (cit. on pp. 3-5, 7, 10, 11, 26, 32, 36, 37, 40, 44, 45).
[OL21]
R. Okhrati and A. Lipani. "A multilinear sampling algorithm to estimate Shapley values". In: 2020 25th International Conference on Pattern Recognition (ICPR). IEEE. 2021, pp. 7992-7999 (cit. on p. 2).
[RSG16]
M. T. Ribeiro, S. Singh, and C. Guestrin. ""Why should I trust you?": Explaining the predictions of any classifier" In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016 (cit. on p. 1).
[ŠK14]
Strumbelj and I. Kononenko. "Explaining prediction models and individual pre- dictions with feature contributions". In: Knowledge and information systems (2014) (cit. on p. 1).
[SNS16]
E. Song, B. L. Nelson, and J. Staum. "Shapley effects for global sensitivity analysis: Theory and computation". In: SIAM/ASA Journal on Uncertainty Quantification (2016)
(cit. on p. 2).
[Tan19]
E. Tang. "A quantum-inspired classical algorithm for recommendation systems". In: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing. 2019, pp. 217-228 (cit. on p. 5).
[Tro15]
J. A. Tropp. "An Introduction to Matrix Concentration Inequalities", In: Foundations and Trends@ in Machine Learning 8. 1-12 (2015), pp. 1-230. URL: http:://a
org/10. 15511220000004 (cit. on pp. 6, 23).
[WF20]
B. Williamson and J. Feng. "Efficient nonparametric statistical inference population feature importance using Shapley values".. In: International conference on machine learning. PMLR. 2020, pp. 10282-10291 (cit. on p. 2).
12

---

[Wo++14]
D. P. Woodruff et al. "Sketching as tool for numerical linear algebra". In: Foundations and Trends@ in Theoretical Computer Science (2014) (cit. on pp. 4, 6, 22). B. Zhang, B. Tian, W. Zheng, J. Zhou, and J. Lu, "Fast Shapley Value Estimation:
[Zha+24]
A Unified Approach". In: (2024). URL: https: / arrxiv. org/ abs / 2311 01010 (cit. on pp. 2-4).
13

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA]. .
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction clearly state the claims made and match theoreti- cal and experimental results, reflecting how much said results can be expected to generalize to other settings.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
14

---

Justification: The paper has a distinct section where limitations of the works are discussed. This was an opportunity for the authors to reflect on scope of the claims and the factors that influence the performance of the approach.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification; All proofs are provided and are core to the paper. Main theoretical discussions are present in the paper with details in the Supplementary Material.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer:[Yes
15

---

While all information regarding the experiments, including hyperparameters, experimental seeds, and experimental ranges are provided: mostly in the main body. with details in the Supplementary Material.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g.. a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: While code to replicate the experiments will not be shared, thorough im- plementation details are provided to convey the soundness of results, including model hyperparameters, details on query and baseline selection, and experimental seeds.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
public/ cublic/guides. /ttggeee/ooeeeumiiiieeeeee/ (oodeSubmissioni CamPolicy iiy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //ni http://bbl/ggggdided/ddeeebbbbee
for more details.
16

---

The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
reproducible, they
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental details are included to provide context for the results and ensure replicability.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Each experiment reports the quantiles across runs, median and mean for the discrepancy between true Shapley value and expected Shapley value. Full results present in the Supplementary Material.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
17

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Detailed description of experiments are present in the main body and in the Supplementary Material. Information on the compute resources are included in the main body. Details of the time of execution are reported.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't I make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /tte::///eeuiss/eeeeeee cc wwtppbccc//cceecccccccccc ctwiiceuiellnnees
Answer: [Yes]
Justification: Having reviewed the NeurIPS Code of Ethics, attest that the research conducted and the paper conduct with the policies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: reflections the impact has have been included in the main body of the text, highlighting the improvements Al safety that are achieved through our theoretical and practical advancements.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinfornation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
18

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not pose risks for misuse or dual use. The paper promotes AI safety and deeper understanding of XAI topics: specifically, caapley-based explainations.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All assets used (code and data) are properly credited to the original developers.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- e-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
19

---

Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/coddemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of L.MMs if is an important, original, or non-standard component of the core methods in this research? Note that if the L.M is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [No]
Justification: The paper does not use LLMS important, original or non-standard compo- nents of the core methods.
20

---

Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https / http//eeurip...ee http///riss.cc/oofeeeeeeeeeeeeee /cw.c///ooeeeencse//2/////// for what should or should not be described.
21

---

Supplementary Material for
"A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values"
A Proofs of the Main Theoretical Results
A.1 Notation
will be convenient switch from indexing rows by sets S 2 {[d].0) and instead index by integers i [2d 2). Given d E N, we fix ordering of the subsets of [dl] according to the size of the subset. Subsets of the same size are ordered in any fixed way (since the sampling probabilities of all distributions we consider only depends on the subset size). We then identify [2 2] to
integers (h, satisfying E [d - 1], E [()] by
h-1
+1
(A.1)
Unless mentioned otherwise, e1,..., En are the standard basis vectors for IRS and are the vectors of all zeros and ones, respectively, while I is the identity matrix. ||-|| denotes the Euclidean norm for vectors, while the spectral norm for matrices. ||-]|F denotes the Frobenius norm. Given matrix A, A denotes its Moore-Penrose pseudoinverse. Finally, given a matrix U with orthonormal columns. we write Pu = UUT.
A.2 Proofs from Randomized Numerical Linear Algebra
In this section, provide bounds for approximate matrix multiplication and sketched regres- sion (least squares) as defined in Section 2.1. Our proofs follow standard techniques in randomized numerical linear algebra [Woo+14 14; MT20; Tro15], and are included illustrate core concepts which may provide a useful starting point for proving theoretical guarantees for more complicated sketching distributions for Shapley value estimation. For simplicity, analyze the simpler that S has independent rows; i.e. that
m
S
eT,,),
(A.2)
PI,
where Jı,..., Im are iid copies of random variable 7 for which P(7 = k) = Pkc. h: E [r] for some fixed N. Note that E S| =.
Proof Sketch: Prior to diving into the technical details, we present a high-level overview of the strategy used in deriving sample complexity bounds for matrix-vector multiplication and regression estimators.
Given a matrix U RRyxy satisfying UT = I, fixed vectors b E RT, our goal is to estimate UTa and y" argmin, |Uy b11².
1. Approximate Matrix- Matrix-Vector Multiplication: Observe that U S Sz is an unbiased esti- mator of U²Z z. By computing the variance of this estimator and using Markov's 's inequality, the sample complexity estimating UT to a given error (in & norm)
we obtain bounds and confidence level (see Theorem A. Note. in particular, that the term y(x) (see (2.3)) appearing in the sample complexity is related the variance of the estimator.
2. Sketched Regression: The sketched regression estimator is given by ②
b)ll² To derive sample complexity bounds for estimating y" using T. we use two main observations. (I) Since ST SU is an unbiased estimator of I, we can compute the number of samples (using matrix Bernstein' 's incquality, Imported Theorem A.3)
argmin,,l|
22

---

to ensure that | SU - I| S 1/2 holds with sufficiently high probability (see The- orem A.4). Straightforward algebra then gives 1 y'1l 2|| S SU y'''l with high probability. (II) Since S(Uğ b) lies in the orthogonal complement of SU, we have S'ST (SUY Sb) = 0. For a similar reason, we also have U (Uy" b) = O. It follows that U SU - 7) U S - b), which is just sketched matrix-vector multiplication estimator for U (U'' b) = O. Consequently, we can use Theorem A.1 to compute the sample complexity for bounding the error SUTSTUU probability. In particular, since U (Uy" b) (I D = Pub, this explains why we have (P)b) instead of (b) in the sample complexity for the sketched regression estimator in Theorem A.5.
y²)|| with high
Proofs for sampling without replacement, which follow a similar strategy, are described in Ap- pendix A.5.
A.2.1 Approximate Matrix- Multiplication
We begin with a simple bound on approximate matrix- -ectoo multiplication. This bound immediately gives provable guarantees for the Shapley estimator eb defined in Section 2.1.
Theorem A.1 -Matrix-Vector multiplication). Let U E IRx and z E R Let S be a m r sketching matrix with iid rows drawn according to probability P. Then,
m 2 (7(=)-|U0)
2)
8e2
it holds that
P P||IUS U S 1-8.
Proof. Let I.... Im denote m iid random variables that sample indices from [r] according to probability P. Let ... u, be the columns of UT, and define X, = u1, /P1, for j E [m] Then, X, are iid d-dimensional random vectors. It can be verified that E X,I = U z for all j E [m]] Next, we calculate the variance of the random vector X, for [ml] Using (2.3), observe that
U. 1
E |X
12
2 7(2),
(A.3)
P
1=1
so that var(X,) independent and (1/m) m)) Σm X, = UTSTSZ we have
R X, B[X =
UT 2|| for all j E [m]. Since Xi,..., Xm
U
E S - U -== =
X, - E[X,)
var (X)
(A.4)
m
Then, using the bound on m, the result follows by Markov's inequality.
Remark A.2. When using Theorem A.I to compute the sample complexity bound the subsequent proofs in Appendix A, we use
(7(2) 5
m = O
(A.S)
samples. This is, in general, an upper bound on the sample complexity required for approximating the matrix-vector product, and can be tightened by including the term |UT ==]
A.2.2 Subspace Embedding
Before we prove a bound for the sketched regression &º from Section 2.1, we prove a subspace embedding guarantee.
We begin by recalling the following well-known matrix concentration inequality; see e.g., [Tro15, Theorem 6.6.1].
23

---

Imported Theorem A.3 (Matrix Bernstein's 's inequality). Ler X1, X....., Xm be zero-mean. indepen- dent. 9 X q Hermitian random matrices. Then, if X S for all [m], we have
P
Σ 1=1
x 2
S qexp
(A.6)
2
1 i=
E
X
(2L/3)e)
In particular, denoting X = m
m 2i=1 i=1
X; and
E
E
x
=
mo? if
20²
2h
m 2
log
2
3c
8
holds that X|||X|
2-
By subsampling sufficiently many rows/columns of a matrix, we can obtain an appropriate subspace embedding guarantee.
Theorem A.4 (Subspace embedding). Given d matrix U, let ui...., Ur E I denote the columns of U.. Let S m x sketching matrix with iid rows drawn according to probability P.
Then, if
m
2
2 8
Σ
r
Uil
u.u. - (UTU)
log
d
+
4
max
|
log
d σ
Pi
30
xE(r]
Pi
i=1
it holds that
P'l'''s'U S 2 8
Proof. First, we write U = (un (u....u,) u, where u, E RR is the ith column of T for i E [r]. Then, UT = Ei u.u.. Similarly, can be verified that U ST SU >x= ur, "r,,,,/(mppp /m/r,, where Im....,Im are the random variables defining the sketching matrix. It follows that E(U ST SU = U.. For convenience, define X; = U1, un / U for i E [m]] and X = - x/m. Then, for all i E [m], we have
,, u. /p..
max kE(r] Pk
=: L.
(A.7)
follows from triangle inequality and Jensen's inequality that || |X,|| S 2T. for all E [m]] Further- more, using the fact that X 1....., Xm are iid with zero mean, and symmetric, we have
x = mE = m
uu
u1 !
(UTU)2)
(A.8)
ps
Writing
|E
= 2 we have
us T
(UTUO()
0²
(A.9)
Ps
The result then follows from Imported Theorem A.3.
A.2.3 Sketched Regression
Together, Theorems A.1 and A.4 give bound on sketched regression.
Theorem A.5 (Sketched Regression). Suppose U has orthonormal columns and let y"
argmin,, |Uy b11a. Let S be sketching matrix with iid rows drawn according probability
P. Define
ÿ argmin SUy Sb
(A.10)
Then, if
m o 1(1 -U log (1)
)
852
holds that
Plly" 1 < > - 8.
(A.11)
24

---

Proof. Since y² is the solution of miny Jy - bl.. Uy - b lies in the orthogonal complement of the range of U, and therefore, (U""" b) = O. Then, taking = U'y -b Theorem 1. we can infer that using
-1 U0 b in
m ( 1(2) 852
uu 2
8
(A.12)
852
Pi
we have with probability exceeding 8/2.
| SUSSSSUU S(Uy' - b)]l 5
(A.13)
Next, note that 7) max; |u:1? (//l///0 /11ppppp2pp
Σ
[u:
U, Mi
3n
u n
(A.14)
Pi
X is positive semi-definite. If ps > || for all i E [r]. then 1 2i=1 |u,l² = | = d (since UU = I), which is a contradiction. Thus, we must have p: S [u:] for some [r]. or equivalently, 77 2 1. Then, because U has orthonormal columns, we have
where X 3 Y indicates
|uul
u.u - -UUT))
- (n - (1--))|0'01|1 15 n
(A.15)
Therefore, by Theorem A.4,
m o 19og (
(A.16)
8 uull
d
||
|uil
d
u.u
-UTU)}
log
+
max TE|r
log
(A.17)
Pi
8
ps
8
then, with probability exceeding - 88/2.
S SU 1|| 1/2
(A.18)
For the remainder of the proof, we condition on (A.13) and (A.18), which, by a union bound, simultaneously occur with probability exceeding 1 5.
Using the triangle inequality, submultiplciitivt, and (A.18),
V ō ( SU)("' 0) + (I - (U SU)) - D
(A.19)
< ST SU) T) + (I- SU
-IT SU)) 9)
(A.20)
$ sT SU) - M)1l + I SU) lyy - -11
(A.21)
s sTuTTTTS)( .) + 1
+1l+- Øll
(A.22)
and hence,
1y" - s (
ST SU) 1
(A.23)
Next, by the optimality of ÿ have that (SU) Sb) and hence that (U SU)ğ
UT TT Sb. Therefore, by (A.13),
[| ST SU) - - =
b)ll 5 =
(A.24)
Combining the above equations gives the result.
25

---

A.3 Proofs for Shapley Value Estimators
As noted in [MW25, Lemma 3.3], the matrix Z' nearly has orthonormal columns.
Lemma A.6. Let ca - 1 ([))/) where Ha 11/0 is the 4th harmonic number. Then,
(Z') z' = d-1 d + call"
(A.25)
Proof. First, we note that (Z') Z WW a matrix of size d. Let (1,..., d). Then it follows from definition that,
Z T W2 Σ k(S)
(A.26)
SA.ES
We separately consider the case where = j. From the above,
zz W Z} = Σ
A(S)
(A.27)
SWESS
d-1
(d-
( (-1
Σ
(A.28)
(d]
S||=
d
Σ
1
(d 1)
(A.29)
d-
18|=1
Similarly for + j.
z W2 = Σ k(S)
(A.30)
SAyeSS
d-1
(d- (d-1)((573 d-2)
(A.31)
(1S)
(s(d (S))
2
Σ
d-1
|S|
(A.32)
d - S
19
d-1
d d-1
-1)
(A.33)
d
d |
|8 2
(d
1)
(d (d-2) 2)
(A.34)
d
Define 1 the all vector in Rdd and I the identity matrix of size d x d. The matrix Z W ZTWZ Z can then be written as
zwZ= d-1, I+ (d 1)Ha- (d 2) 11
(A.35)
d
d
which is the desired result.
Next, we describe the conversion from the constrained problem (1.2) to an unconstrained problem. Our approach is closely related [MW25, Lemma 3.1]. However, as noted in Section 2, our approach allows arbitrary À (where as [MW25] only allows X = a).. In addition, on more technical note, we state our results terms of the argmin of a regression problem involving a full-rank matrix U. The result of [MW25] is stated in terms of the argmin of regression problem involving rank-deficient matrix, which is not uniquely defined. As such, their result implicitly assumes that the argmin returns one particular solution (the minimum norm solution); see Appendix B.3.
26

---

Proof of Theorem 2.1. Using Q - 0,
- I, and (A.25),
U = d Q (Z)' 1 Q'
d
d dd-1 1
+ ca call Q==1. I.
(A.36)
Therefore, (U U = U and so Q ar |Ux - ball + al = QUT
by + al.
remains to show these formulations are equivalent to (1.2). Since Q 1 = and 1 = d, observe that
( Φ E R 1' = v([[)) - - e(0) = {Qu + a1 x E R
(A.37)
with the natural bijection Φ + Qx + a1 between Φ and æ. Thus, using the definitions of U and ba.
argmin
Z - bll
(A.38)
&ER"
1 1'd=v((4)-<(00)
Q argmin|
argmin|Z'(Qrr
Z x + a1) - bll +al
(A.39)
zER*
Q argmin =cRd-i
CaaninnUxx>00 Uv 1a +al
(A.40)
Now, since =1
U U'Z''= z'1 21 Q + 1=0. 0.
(A.41)
Therefore, for any X, argmin||Uz bxll = argmin =ER
Ux (b xZ'1)]l= argmin Ux - b11 =ER
(A.42)
mgRd-1
This gives the desired result.
Finally, we use Theorem 2.1 and the bounds from Appendix A.2 prove our main approximation guarantee.
Proof of Theorem 2.2. We analyze the estimators individually. Recall from Theorem 2.1 that
Q arrmmnn| Ux bxll a1 QU bN +al. =ER
(A.43)
We will use both of these formulations.
Regression: Observe,
Φ Q argmin S(Ux -b)ll + = Sb,, +al.
-ER--1
Now, since Q =
||Ø
&R11 LQU by - Q(SU))+++ Sbill |IUT - (SU) Sball
(A.44)
By Theorem A.5, if
m o ( (2(Pbbb) + log 1 )
(A.45)
0E2
then
Pl||Tb - (SU)* Sbal1 S 2 1-8.
Matrix- Vector Multiplication: By definition.
Φ QUT ST Sb, all
(A.46)
Then, since QTQ =
|1 I1
QQU by QU ST Sb
T 1 -U
(A.47)
By Theorem if
m m= 0 (bb))
r |u;l1
((bx):)² -IIUTba1
(A.48)
dE2
Pi
552
then
Pll|Ubb
UT Sbx || < > 1-8.
(A.49)
This establishes the result.
27

---

A.4 Fine-grained bounds for specific probability distributions
Theorem A.7. Map the index i E [2d - 2] to integers (h,, 1) satisfying E [d (d, E [())] as
i プド + I. Then, we have
|u: ||um in
(A.50)
for all E 1(21 and all h E [d 1]. Moreover,
1. (l2-squared) For E [d - 1] and 1 E [[h]]. we have
|un.11 1| Ph,
1
|
(d (1)
722) (d 1)
and
11 1
2. (Kernel) For [d- - 1] and E [(1)], denoting k:(h) (d - 1)/((1) (hidd ((]d-)))) we have
Ph.1 k(h)) 1 hdd
(H) d-
jldー
2 (x)
d h hld - h)
and
1 S
h
h=1
3. (Modified Eg) For h E ld (d--1) 1] and I [(H],, we have
k(h) unlll
v Vh(d-A)
Ph.t
(3)
(1) j== Vi(d-j)
ΣØ Σi 1=1
d-1
and 1) S d d-1
7()) = Σ
Vhild 100--hj -))
V hldd h)
2 h=1 v /hl - h)
Proof. Denote r = 2d 2, and let el...., er E Rdd be the standard basis vectors. Since u,,..., the columns of UT, we can write u, U e; for all i [r]. follows that
= e = d e WWWPZT
(A.51)
Now, we map i to (h, for appropriate integers h E [d- 1] and I E I(e).. so that the subset St C [d] is of size h (according to the chosen ordering of subsets). Then, writing k(h) k(S.). we have zT /We, en, <k(h) TT en.1 / <k(h)z), 21,, where 2h,1 d-dimensional vector with 1 entry j if j Sn,1 and 0 otherwise. Substituting this in (A.51), using P I (1/d)11" and
|Sh.ll = ||, = || = h, we obtain
d | 2 = - k(hh) || - -11mmnll?
d
d d-1 11166
( h22
(A.52)
d-1
(g) - d)
d
1
(
24-1 It can verified that Σi=1
|uu,'
| 2
The result follow from the definition of
Ph.ts and 7 17 in (2.3).
28

---

2. Noting that k(S) depends only on the size of the subset S S [d], Ph. in Item 2 is obtained by direct calculation. Observe that
(A.53)
hld - h)
h
and therefore,
uunil 112
d-
h(d - h),
(A.54)
Ph.l
h
for h E ld - 1] and E [[.]. Since h(d- - h) S & /4 E [d 1J. Item 2 follows from (2.3) by
direct substitution.
We obtain Ph, Item 3 by direct substitution. Since
11
d-1 Σ
1
Vh(d- h)
(A.55)
Ph.l
Vhld h))
for h E [d - 1] and E [()), we obtain Item 3.
Remark A.8. The sum over 1/h in Item and over 1/ 1/Vh(d - h) in Item 3 only mildly depend on Indeed,
d-1 Σ h=1
(log(d))
and
9(1).
(A.56)
h
v /hld (ld--h)
This can be seen from the (well-known) bound
d 1
J
log(d)
do
Σ h=1
Σ
-dx + log(d - 1),
(A.57)
where the approximation with the integral uses the fact that h + 1/h is a decreasing function. Similarly, since [dd 1)/2} < d/2, we have
d-1
((d-1)/21
Σ Vh(c h)
2
Σ
Vhdd-h
h=
h=1
2/2
(A.58)
2
Var(d - x) dx
Vd
2
arctan Vd-1)
T
Vd
2
d
and since - 11/2] d/2 1, we have
[(d 1)/21
2
Σ
Vh(ld 11)
hid - h)
M=1
dd/2
(A.59)
2
dr Vx(d - x)
2
2arctan (oitaan(d=-aa -dd-) 2
77
n
d
Theorem A.7 allows us to directly compare the values of 7 for the different sampling strategies we consider.
29

---

Corollary A.9. Denote "ieg New Ta-l, to be the expressions for for by by-squared Item 1, kernel Item 2, and modified &g Item 3 sampling schemes respectively. Then, for all 2 E R²--3 we have
log d)
Ther (z)
θ
I (llog(d))
(A.60)
71 (2)
em (z)
θ
+)(1,
(A.61)
(2)
and
log(d)
nker (z)
θ
I (log(dd))
(A.62)
Vd
em (z)
Proof. Since d 1 h(d- - h) d / for all h E ld 11. we have
d-1
(d- 12,.11 -
h(d - h) - (d/44)|Zn_11
(A.63)
h= 1=1
and
d-1 (1)
dd Eh. $
v hid h)22. S (d/2)
(A.64)
Similarly, since (vd 1/d) / hid h) h(d h\dd (1/2) hd-h) h) for h E [d 1], we have
Vd-I V hhld - h)21.1 5 4=1 1=1
h(d h)
/hld h)2
(A.65)
h=l 1=1
1=1 1=1
Then, (A.60), (A.61), and (A.62) follow from Theorem A.7 and Remark A.8.
These bounds suggest that kernel weights perform at most a log factor worse than leverage scores, while it can perform nearly d better than leverage scores. On the other hand, the performance of modified εe weights never worse than leverage scores (up to constant factors), but can nearly do vd better than leverage scores. In Appendix E, we explicitly construct a toy model that demonstrates such advantage. While these results only upper bounds on the sample complexities, observe similar results in experiments. Using Theorem A.7, we can derive the values of 7 and 1) listed in Table for the different sampling strategies as follows.
also
Corollary A.10. Define H to be (2d 2) x (2 2) dimensional diagonal matrix with diagonal entries
HODD /kld h)
d
for h E [d - and E [(A]. so that
Amin (H) 2 ((a) and
Amax (H) O
Then, we have the following expressions for 7(2) and n for all -2
1. (lz-squared)
7(2) = O(d|=]]] and
= ((d).
2. (Kernel)
((x) @(dlog(d)) and
17 = (dgo)))
3. (Modified 22)
(x)) (dl) / Hz2
and
7 O(d).
30

---

Proof. This follows from Theorem A.7, Remark A.8 and the definition of H.
Remark A.11. The distributions considered in Theorem are actually special case of a family of distributions, obtained by interpolating between kernel weights and leverage scores. Specifically, given r E [0, I., we can consider the weighted geometric mean (k(h))) (1 (11111)))))) of ((h)))) and | for h E [d 1] and E [(,)]. This gives rise to the distribution
h(d-h)
Ph.
(A.66)
dd-1 2j=1 o(d-j)
Fort = = 0, we get the leverage scores (or bz-squared distribution), T 1 gives the kernel weight distribution, and 1/2 gives the modified Eg distribution.
Denoting
d-1
N
(A.67)
j(d -dd-ji
Ø=1
be the normalization factor, we have
Un 112
(h(d- h1)" T Nr
(A.68)
Pha
for h E [d- and / (()) It follows that
N
if is even
77
(A.69)
N
if d is odd,
and
7+ (=) Nrr Σ (m(d - h))² =h.1
(A.70)
h.1
for z E 222-2
Using similar arguments as in Remark A.8, we can show that
((()-22)
Nr
+
loR(d)
-
(A.71)
d
Here, we used the fact that
8/2 1 dx d' d''-2T(Bi/dl T, 7) -BI/a(1 T, - 27) (A.72)
(old=x))"
for 0 0 1, where B2(a,b) b) 1== (1- t)² b dt is the incomplete beta function.
Therefore, we have
(+(2)= = e H 2 =1 and 17+ = (d)
(A.73)
for 0 S < 1, and
=((lo=(((o 21|3) and 17, ((dlog(d)
(A.74)
1. For < 1, do worse than leverage score sumpling. We remark that because the notation hides constants, for a given dimension, one can choose an appropriate T that minimizes these constants. It remains to see how such strategy performs in practice.
31

---

A.5 Theoretical guarantees for sampling without replacement
In this section, we prove guarantees for matrix vector multiplication estimator and the regression esti- mator when the rows/columns are sampled without replacement. We follow the strategy of [MW25] for sampling indices without replacement.
Let U be an r x dimensional matrix, with rows u...... u,, E R To sample the rows of U without replacement, suppose that we have independent Bernoulli random variables Y,.-... Yr, where Y, has mean C; > 0 for E [r]. We interpret Y; = 1 as having picked the ith row, and Y = 0 as not having picked the ith row. The expected number of samples (or rows) mo = -i=1 qi. Thus, on an average, we will sample ma rows, none of which are the same. Observe that while we can control the expected number of samples by choosing the probabilities qı,... 9r. the actual number of samples m we draw is random. If f1,.... Im are the (distinct) indices we pick, then the sketching matrix S is m r dimensional, with jth row having the element 1/ /9, at location ij and zero elsewhere for j E [m]. Note that an important feature of such sampling without replacement scheme is that the probabilities ç1...., fr need not sum to 1 because they independently determine whether or not given row is picked.
A.5.1 Approximate Matrix- Matrix-Vector Multiplication
We derive the following guarantee for the matrix-vector multiplication estimator for sampling without replacement. Since the number of samples are not fixed, we instead calculate the estimation error for a fixed expected number of samples (which is determined by the probabilities QI...., Qr).
Theorem A.12 (Matrix-Vectee Vector multiplication, sampling without replacement). Given a matrix R", let S be an X r dimensional sketching matrix constructed by sampling rows of U without replacement according to probabilities q,.... Then, using an expected number of samples Ei=1 Qo we have
U E R2' and a vector
P P[ S Sz U² S =
21-
2
for
Ui -1)
1|2.
(A.75)
Proof. Let YI,..., Y, be independent Bernoulli random variables with means - respectively. Then, the random variable
Y an unbiased estimator of U z. Denote var X = E X
X U- =
4
(A.76)
qi
1=1
E X
to be variance of X. Then,
since all Y Y,,...; Yr are independent, have
Uizi
var x
var
Yi
(A.77)
1
12
(A.78)
0i
Since var X
E[|
E[X |1,
by Markov's inequality, we have
p
P
- E
var
2
Σ
1u:122
(A.79)
Setting the right-hand-side of the above inequality equal to 5 and solving for gives us (A.75). [
We can use the above result to derive the error bounds in terms of the function (xx) defined in (2.3).
"We note that the term "sampling without replacement" is perhaps a bit of a misnomer for this type of sampling scheme. Nevertheless, we it order maintain consistency with [MW25].
32

---

Corollary A.13. Let P = (pi..... .P) be probability distribution on [r] with ps > 0 for all i E [r].
Given a mumber my E (0, let с 0 be constant for which qi (i,c(1 for E [r] and Ei= 4 mg. Then, given enror >> 0 and confidence level 1 - - E (0, 1), if
(()
8g2
by sampling the rows of U without replacement according to probabilities q1,...: yrs we have S E 8
Proof. First, note that by the continuity of + min cp:} for all [r], given real number my E r0, there is always some с > O for which Σ min 11 cp:} = my by the intermediate
value theorem. Furthermore, mg = Ei= m cp: S c, since Ei=1 = Therefore, we have
14 ||: 1|22
- 1)
qi
1=1
|2: x?
Pi
(A.80)
||
Pi
1=1
(z)
E²
mg0
where the fact that q cp; when di < in the second line, the fact that the terms non-negative the third line, and the definition of y (see (2.3)) and c 2 mg in the third line. The result then follows from Theorem A.12.
Remark A.14. We can derive a lighter bound the expected sample complexity for sampling without replacement as
1
u 12
mo
822
P
Intuitively, when 1, we (deterministically) choose the ith row U, U, and therefore, it should not add the estimation error, which is then reflected the average sample complexity. Thus, in practice, we may observe a somewhat smaller enror for sampling without replacement on an average, compared to sampling with replacement.
A.5.2 Subspace Embedding
In this section, we derive a subspace embedding guarantee for sampling without replacement.
Theorem A.15 (Subspace embedding). Let be an r x d matrix with rows U1..... u, and let P (p1. .P...... .P) be a probability distribution on [r] with > 0 for all i [r]. Given number ma E r). let c > 0 be a constant for which min cp.} for i E [r] and Ei= mg- Then,
ma Z
Σ
|uill inu
Pt
log
d )++
8
35
max sE[r]
Pi
log d
by sampling the rows of U without replacement according to probabilities qı, yrs holds that
P|l|uTsT STU S 21
Proof. Let ..,..... Y, be independent Bernoulli random variables with means ......, respectively. For [r], define the random variable
Y, u:u uuu
X;
(A.81)
33

---

If = 1, then Y; = 1, so that X, = 0. Therefore, we have
y;
X
I max
1/22l11
(A.82)
/E|r]
96
4; <1
uu,
max
(A.83)
9,
[u:]]
max
(A.84)
C ie(r
P
9:51
1
||u:li
I18X
(A.85)
C kE(r)
Pi
1
||u=ll 2
I
max
(A.86)
mg
sE|r]
P
m0
for all E [r]. Here, the third line follows from the fact that gi
ops when qi 1, while the last line follows from the fact that mo = -'i= min(1, cpc} S since Ei= P
Next, note that [| and Σ.= X; = ST U.. Furthermore, we have
X
1
+ (1 - 9/)
|lu:l/ (1 q:) 1 uu uuu!
(A.87)
q
for all i E [r]. Therefore, we have
[1: ||
i=1 E
Uz u
(A.88)
9i
9: <1
| 1|
(A.89)
81 <<1
|uul1"
(A.90)
Pi
||
u
(A.91)
m7
follows that
x
2
Σ
r
u
2
u
0²
(A.92)
mo
pi
mg
i=1
The result then follows from Imported Theorem A.3.
A.5.3 Sketched Regression
We now combine approximate matrix-vecte vector multiplication guarantee (Corollary A.13) and subspace embedding guarantee (Theorem A.1 to obtain guarantee for the sketched regression estimator constructed by sampling without replacement.
Theorem A.16 (Sketched Regression). Suppose has orthonormal columns and let y" argmin, y | JUy - bll². Let (pı,...,PP be a probability distribution on [r] with p; > 0 for all E []] Given number mo E (0, rl, let > be a constant for which q: min(11cpp) for i E [r] and Ei= mg. Let S be x q sketching matrix obtained by sampling rows of U without replacement according probabilities qi...., qr- Define
ÿ argmin SUy Sb|
34

---

Then, if
mo (2((80 log
((P(bb) 06
d )
it holds that
PI y
y S 5) 8
Proof. We closely follow the proof of Theorem A.5. Since y² is the solution ming Uyy bll Uy" lies in the orthogonal complement the range of U, and therefore, UT b) Then, taking Uy" b (I UU in Corollary A.13, we can infer that using
mu = 0 7(2)
(A.93)
óc2
we have with probability exceeding 1 - 8/2,
SUTSTS(U'' b)]l 5 E
(A.94)
Next, note that 17 max; |u:l? pss that
uu
U
1)
Σ u U.
(A.95)
Ps
Then, because U has orthonormal columns, we have
[u
s <n = u. u
(A.96)
pi
Therefore, by Theorem A.15, if
mo
=
17 log
(A.97)
uu 11
uu 12
8
u.u.
log
+
max
log
(A.98)
Pi
3 kE
Pi
then, with probability exceeding 1 8//2,
| SU - 1|| 1/2.
(A.99)
The remainder of the proof is the same as that of Theorem A.5.
B Description of past estimators
In this section we provide more details on how several existing estimators fit into the unified framework described Section
B.1 KernelSHAP
KemeelSHAP makes use of subsampled and reweighted version of the constrained regression formulation (1.2) of the Shapley values. Specifically, denoting Zs to be the S-th row of Z, observe that
IZ ω b11
Σ
k(S)(Zso 23)
(B.1)
Σ
K(S)
E I Φ Ug Ug
35

---

where in the last equation S' is a random variable for which P[S" S] x k(S) for S S [d].
# 0, [d]. Note that
argmin &CR"
2 - b1j² argmin
Z -
- )
DE
1 ((4)-()))
1 (())(()
because the minima of a function f coincide with the minima of (f for > 0.
The KernelSHAP estimator [LL17] is then defined
argmin $ER" m
1
Σ Zz. vg
(B.2)
1 =()=
where S; are iid copies of S
As noted by [MW25], this can be viewed constrained sketched regression problem
Ks
argmin
|S(Z' bb)l
(B.3)
$E
Performing the same change of variables as the proof of Theorem 2.1 we find that
KS
Q argmin
(aammiinnS(((((/ (Qx + al) b)ll + al
(B.4)
=ER4-1
Q argmin S(Z'Qz (b ao='a'1))11' a1
(B.5)
=ER
Q argmin S(Un - ba)l aal
(B.6)
B.2 Unbiased KernelSHAP
In [CL20], the authors observe that the Shapley values can be expressed as
A f - v((d) v(0)
A-1
(B.7)
1TA-11
where
= Z ZWZ.
f=z
(B.8)
They then introduce the unbiased KernelSHAP estimator
duks AA-1 f - A 1
v([d) + v00)
f z VWST
(B.9)
A --11
Expanding, that
111
v(d) + x00
gukS_
A-
f A
(B.10)
ATA-11
1TA-11
Since [Q, 12,d-1/21 form an orthonormal basis for Rdd
A ( d -
QQ + (d - 1 dea) 11
d
11T
d-1 -
QQ + (d - 1 doa)
(B.11)
d
d
Using this, we see that
A-1 = (d - + -1,
AA- = d(d - + dea)
(B.
We now compute
A- f d-1 QQ T f + (d - + dcg) 1 11
d f.
(B.13)
A-'11TA-1 A-1 (d + dea) 2 $11 (d- - 1 + dca)-111 111
(B.14)
1TA-11
d(d 1 dc -1
d
and
1 v ((d) + v(0)
(d - 1 + dcg) -11 1
(B.15)
1'A-11 d(d + dea) -I d'
Combining these equations we have
d d-1
10Q0Q0 zJ V www.swssww v(d) v(0)
GuKS
QQQQ
d 1.
(B.16)
36

---

B.3 LeverageSHAP
In [MW25], the authors show the typical formulation of the Shapley values (1.2) can be rewritten as an unconstrained problem
argmin AΦ ball al. 6ER
(B.17)
where
A= P= 1 QQ
(B.18)
They then describe randomized estimator LeverageSHAP of the form
Φ
argmin
S
b.)ll -
al.
(B.19)
Theoretical guarantees are given for the case where S is drawn according to the leverage scores of A.
C Equivalence between Lagrangian and Change of Variable Framework
We consider,
Φº argmin|
C$ - -ll
(C.1)
dER" 1 d=
where (u([d) =(0))/d, and C Z' and y = b for solving the constrained least squares exactly, while C 5Z' and y Sb for approximately methods such that EiST I. Define M CCC and C' y. Next, we write the unconstrained solution of the above least squares as,
Φ
argmin CΦ - y/ M ΦER
(C.2)
Lagrangian method:
In order to solve (C.1), the Lagrangian method writes,
[( A) _ Φ M g x
(C.3)
with the following KKT conditions,
1. Mό g + & ( X1)
2. T = 9-a
M
This results in the final solution to be,
- 1T 0² ad 1 M
(C.4)
Change of Variable Method: discussed in Appendix A.3, an alternative method to solve the constrained least squares is using the change of variable to explicitly enforce the constraint. Specifically, we re-parameterize & as,
Φ = a1 + Qæ
(C.5)
where Q E (d-(1)) is a matrix with columns forming an orthonormal basis for the null space of 1 i.e., i and QQQ==1
Plugging & into the objective results in,
argmin MaiimllCC C(al + Qx) - u argmin||CQQ (qapnnlCCx((gaCCi)))
(C.6)
æ
x
Solving this results in,
x (Q' " M
(C.7)
This the final solution is.
= =
o1)
(C.8)
*Since 1 in the null-space of A, all of (6 + cl E K) produce the same objective value (and hence the argmin is an infinite set), it should be understood as the minimum norm solution; i.c. for which & + cl is orthogonal to 1.
37

---

Equivalence of the methods: The second term in (C.8) can be seen projection of the vector Φ² al into the span of Q (or alternatively on the null space of 1) with the projection matrix,
P Q=QQQM"Q) Q" M
(C.9)
Next, can rewrite (C.8) as,
s² = al + P(Ø" -a1) 8² P) -a1)
(C.10)
From the geometric intuition, I - can be seen as metric-projeetiee projeccoooooonnn in the M-norm' into the orthogonal complement Q, or alternatively in the span of M 1. Such a projection in the M- -onom for any vector z is
l
- P))== M
(C.11)
1TM-1
Thus, plugging in this (C.11) results in
x" M 1 1' al)
(C.12)
M
thus recovering (C.4) by noting that 1 1 = d.
D Ratio of mean squared errors
In Appendix A.2, we saw that 7(2) and (see (2.3)) give upper bounds on the sample complexity of matrix-vector multiplication and regression estimators for sampling with replacement. In this section, we study the ratio of mean squared errors for different sampling strategies these estimators in the unite-ssamlleasymppoooo regime. We find that this ratio is determined by y for both these estimators, as summarized below.
Theorem D.1 (Ratio of mean squared errors), Given an r q matrix U with orthonormal columns, and an r-dimensional vector b, suppose that want estimate U using matrix-vector multiplication estimator (see Theorem A. and argmin, |Uy - bl(² using regression estimator (see Theorem A.5). Given sampling distribution over (r) and a fixed number of samples m, denote XM X xR(P) be the matrix-vector multiplication estimator and regression estimator for U.b respectively.
Given two sampling distributions Pi and P2, denote 7/1 and 72 to be the values of y as defined in (2.3) with respect to distributions P1 and P2, respectively. Fix the number of samples m N. Then, we have the following results.
1. (Matrix- Vector Multiplication)
E
X
M
(Pt) b11 (b)
b
(D.1)
E
X
(P2) - U 6|
(2(
|
Tr
2. (Regression) iffor = 1,2,
X (P:) U U + and
m
[ (P:) UTb O(1),
(D.2)
B||l R (P:)
U 611
we have
B X (P U b1
1 vm
(Pob) (Pub)))
1 1
o
(D.3)
(P2) UTb
where (a + b) means x E [a b, a b].
Proof. Let S be an x sketch matrix (for sampling with replacement) as defined in (A.2)
with respect the distribution P. Then, the matrix multiplication estimator is XM (P)
ST while the regression estimator X (P) argmin, SU Sb1l2.
where M norm is defined as || M MM for all gd
38

---

1. Matrix- Vector Multiplication: Since E| X b is the variance of X using m samples, from (A.4), we have
B X (P:) - b11] (ni(b) [1Tb
(D.4)
for i = 1,2, from which we obtain (D.1).
Regression: Observe that argmin,, Uy b12 U. Furthermore, since
x (P:) U | s SU
-U (D.5)
we have from triangle and reverse-triangle inequalities,
- - I S SU (P:) DTbIll S 11T- ST (U)(((((P)))))) - bill
(D.6)
For simplicity. denote A, = | (P:) - UTI B: = |U SU (P.) U) and C. =
[| - S STSTSU)) (X m (P;) bbb)
b)ll Then, we have |4 - B - (A; + B.)C₁. from which
follows that
|B[ - || - [[AA, + B.)C.J.
(D.7)
Now, observe that B; s || SU || A, and C; < I - S SU Moreover, we have ||US S SUIl S 7h, where is defined in (2.3) (and depends on the distribution P.). Therefore,
E EB = (1 + n E U SU S (1 (1+ m)) BlIl UTSTSU [E[A]]
IP
E [[
(D.8)
where we used Cauchy-Schward incquality in the last step. Now, note that v E[A|]
> E[A by
Jensen's 's inequality, and thus, /E[44]/B[A? = O(1) implies /B[4/)/E[4]] = (11). It follows from (A.9) and (A.15) that
E
?
Th E[A
- (1 17.)
θ
(D.9)
E
[AA
m E[A
Thus, for large enough m (using (1 - x)) + (zx) for < 1), have
E [{A1]
1 o
(D.10)
E [
v m
and
E [3
= -10
(D.11)
E [4]]
m
which implies
E[
1
E E[B
1 1
(D.12)
[E[
Vml
EE B[
Then, denoting y = argmin,, [Uy
b112 from (A.24) and (A.4), we obtain
E B[B]]
STU 1
(D.13)
B[B
EiJUTSTS((U> - =]
7Uy'" - b) -IUT(U 2
(D.14)
'2(Un" b) b) - IUT(Uy" - 2
(Pub)
(D.15)
(P)))))
where in the last step, we use the fact that Uy -b
b = Pub and UT Pub = 0.
Informally, (D.2) says that (the square-root of) the fourth "central moment" comparable to the mean squared error of the estimator. This requirement actually holds for the simple statistical task of
39

---

estimating the mean of scalar random variable. Indeed, if X Xm are iid copies of a random variable X with [=[ < oc, then X i= X./m is unbiased estimator of [[[] satisfying
m
v EI(X - E[X])* B[(x [[ = ((1)
(D.16)
for all m. Motivated by this observation, we expect (D.2) hold in practice, though this may be difficult to verify rigorously. Also note that while (D.3) gives an expression for ratio of mean squared errors for the regression estimator in the finite-sample regime, the number of samples needs to be large enough so that we can ignore the correction term.
Now, we specialize Theorem D.I Shapley value estimation.
Corollary D.2. Let o' denote the true Shapley value vector and a as in Theorem 2.1. Given X E I. define by as in Theorem 2.2. For = 1,2, given m. E N samples from the sampling distribution Pi. denote & (P:) and (P:) .) to be the malrix-vecte multiplication estimator and regression estimator, respectively. Then, for all X E R. we have the following results.
1. (Matrix- Vector Multiplication)
Bll (Pt) 1-1 (bx)x) - 11 a1 ||
(D.17)
Bll 2-11 (2x)x) - 1100- a1
2. (Regression) if = 1,2, E [IlldR(()) - 60 [12] # and
/
/Ell 1-
[ 11 O(1)
(D.18)
we huve
E [PI - 11
1
71 (Pbbx)
(D.19)
E (T
72 (Pub)
Proof. Denote S to be m 24 - 2 sketching matrix obtained by sampling with replacement according to appropriate sampling probability. Let U and Q be defined as in Theorem 2.1.
1. From (A.47), we know that |Ø - x0 = ||U S Sb, - - bxll- Furthermore, from Theorem 2.1, we have |bU = |QQUU = || - -a1ll. Then, the result follows from Theorem D.I.
From (A.44), we have | 601l = (((UU) Sbb UTb = miny SUy Sbxll- Then, the result follows from Theorem D.I.
The results of this section shows that while the theoretical guarantees derived in Theorem 2.2 only give upper bounds on the sample complexity, the quantity y appearing in this theorem in fact determines the fnite-sample/asmmpotii behavior of the mean squared errors, as shown in Corollary D.2. Therefore, as long as our metric of performance is the mean squared error, we can directly compare the performance of different sampling schemes by comparing the corresponding values of
E Adversarial example
In this section, we develop an adversarial example that help us separate the performance (in terms of the mean squared error) of fq-squared sampling, kernel weight sampling, and modified & sampling. The main intuition for construction such adversarial examples comes from Corollary A.9 and Corol- lary D.2, where we compare the value of (z) (see (2.3)) for different sampling strategies. The vector z is either equal to bx or (I (I- UUT) )b, as in Theorem 2.2. For ease of comparison, in our adver- sarial example,
will construct model for which b = (I UUT )b,, and the lower bounds in Corollary A.9 are saturated up to constant factors. For simplicity, we fix À = (v([d) v()) = a, as done in previous studies [LL.17; MW25].
We now construct an example for which we can provably show better theoretical guarantees for modified &2 sampling and kernel weight sampling compared to fz-squared sampling. To that end,
40

---

define the function f: R - R, which is our model acting on d-dimensional input data, f(z)
g(Ei h(z;)), where 9 and h are real-valued functions to be chosen below. While there is reasonable freedom in defining the functions h and 9. we choose these judiciously in order to theoretically compute the Shapley values. Given parameter eo (0, 1), we define
h(x) - {
i > co otherwise.
(E.1)
Furthermore, given parameters E N (independent of d) and ć, E R, we define y: IR + as
$
+ x
= ~ sd=dd-
g(x)
(F.2)
X
otherwise.
Then, we have the following result.
Proposition E.1. For the model f(x) 9(Ei= h(x;)), where h is given in (E.1) and is given in (E.2), baseline y = 0, and explicand a = 1, we have 6- x1 and
7eg ((1 - )b)) = =brg(b>) = (
Tha (II Ubx) (bx) (log(d))
(E.3)
I'm (U- = e2 @(vd).
Proof. First, compute by and show that (I - -UUTTb, = b,. For given subset S of [d]. define
S E I as x Iz if S and 2. = y4 if y & S. Then, from the definition of f. it follows that for all S C [d]. we have v(S) [(x ===[(S])) By construction, we have v([d] xd and
v(0) = O. Since vSS) depends only on the size of the subset S, by (1.1), we have that Φ= Φn 1 for
some constant कū E IR. Then, the constraint 1 x² = =v([d) - v00 gives de (v(d] =v0))/d X- Thus, for this example, we have = a X- Since o² x1 a.1, from Theorem 2.1, we have b2 b O. and therefore, b
)b, = O. It follows that (I (I-UT*) )b> bx-
Next, we compute ||bx| 2 Hbbx| and || HHbxll (see Corollary A.10). Since depends only on the size the subset and X, we obtain
d d-1
52 d3
13
d-1
h =
12
h(d - h) (g(h) 2b)²
Σ
+
Σ
+11 (E.4)
d
d d-
h
- h
h=1
h=d-n
since is constant independent of d. Similarly, we have
1-1 h(d h) Hb h(dd h)) d² (g(h) X6)2
2
Σ h2 θ (1)
d5
h=d-n
(E.5)
We also have
d
Σ
d-1
d d-1 1
Vhld - h)
(g(h) Xh)2
1
h(d h)
(E.6)
13.5
d-1
33.5
+
Σ
= 0
d
Vd
h
Vd
Vd
1=1
h=d-n
Therefore, by Corollary A. we have
Yig (bx) Odd O(d),
ner (bx) = (d Hbx = (log(d)),
(E.7)
mm-l, (bx) = O(dlv Hb, (1 @(vo).
41

---

We remark that the adversarial model constructed in this section is specific toy example meant to illustrate the advantage of modified & and kernel sampling. One can construct many such adversarial examples for which modified l2 and kernel gives better performance than both leverage scores. We can now translate these results into statements concerning the mean squared error for the different sampling schemes.
Corollary E.2. Denote Piz. Pker and Pm-ta to be the sampling distributions for l3-squared. kernel, and modified &2 weights, respectively. Then, for the model f(x) =(( h((+)), where h is given in (E.1) ) and g is given in (E.2), baseline y = O, and explicand æ 1, we have (using m samples, drawn with replacement)
E
Φ
(P:)
11
Yez (bx))
= 0 d
ker)
12
Yker (bx)
log(d)
E
1 (Pm-l, 6- 1-1
Ymm-l (bx)
Vd log(d)
dx (Pkor) - 60
Tker (bx)
E
mmm (bx)
0 (vd).
E
Φ (P (Pmm))) Φ- 12
Yker (bx)
(E.8)
E
(P(g)
[]]]
Veg (bx)
d
=
for large enough m,
E
(Pker)
ker) 11
Ther (bx)(bb))
log(d)
E
6- 10 ( (Pm-).)
Ymmee(by))
= =0 vd log(d)
for large enough m,
2 (Pker)
Tker (bx)
E [ (Peg) 10
Teg( (bx))
for large enough m.
E|| ( (Pm-ta)
1-
Tker(ba)
The expressions for the ratio of mean squared errors for the regression estimator hold under the technical assumption (D.18) stated Corollary D.2.
Proof. This follows by directly substituting the results of Proposition E.I in Corollary D.2.
This example shows that modified &2 gives advantage over leverage scores by a factor of Vd. On the other hand, kernel weights give a factor d/ log(d) advantage over leverage scores, while factor of vd log(d) (d) advantage over modified f2- These saturate the lower bounds in Corollary A.9. Since have the analytical expressions for y for the adversarial example studied in this section, in Fig. 4, we plot the ratio of for different the sampling distributions using these expressions.
F Methodology
In this section, we describe our estimators algorithmically. The unified theoretical framework can directly be implemented into an algorithmic framework, which we depict in Fig. 5. The general procedure to generate the Shapley values in our framework requires three choices: (1) a sampling
distributions the index-sizes, (2) strategy for sampling (with replacement, without replacement) and (3) an approximation method (least squares or vatrix-vector). Least squares and -ettix-vector estimation are reported in Section 2. The missing detail is how the sampling procedure is implemented
(this is the middle column Fig. 5). We report this Algorithm for with replacement sampling and in Algorithm 2.
F1
With Replacement Estimators
Sampling with replacement to generate the sketch is a computationally efficient procedure that performs well in practice. However, if the number of samples m >> 24. the estimator will fail to compute exact Shapley values general. We report the sampling procedure as implemented in our experimental evaluations in Algorithm I.
42

---

10a
MSE Ratio
102
10a
104
10
10c
d
d/log(d)
MSE m-7
/d/log(d)
MSE ker
vd
m-4
Figure 4: Ratio of meean-squared errors (MSE) as function of the dimension for different sampling strategies for the adversarial model in Appendix E (computed analytically from expressions for 7). The matrix- vector multiplication estimator and regression estimator have (almost) the same MSE ratio for this model (see Corollary E.2). For fz-squared v/s kernel (solid) and modified & vs kernel (dashed), kernel weights give advantage by factor of Ō(d) and Ö(vd) respectively. On the other hand, for modified f2 v/s lz-squared (long dashed), modified & outperforms Ez-squared by factor of O(vd).
Sample Efficient Shapley Value Estimators
Select Bucket Distribution
Seleet Sampling Strategy
Select Estimator
Kernel
With Replacement
Regression
f2-squared
Without Replacement
Matrix- Vector Multiplication
Modified &
Figure 5: The unified framework for estimating Shapley values with the proposed class of estimators. First, we define a distribution to apply to each bucket (i.e., to the selection of the bit vector to select p: is the probability of sampling item from bucket/coalition of size (or bit vector with Hamming weight) E [d]. Then we select sampling strategy (with or without replacement). Finally, we select the estimation strategy. If limit ourselves fz-squared and modified, and kernel distribution, this provides a total of 3 x 2 x 2 12 estimators.
43

---

Algorithm Sampling with Replacement (paired sampling)
Require: d: number of features we: number of samples expected by user, choice of distribution on d buckets, maxval maximum value before Poisson approximation is applied (our algorithm uses 10¹²).
Ensure: SZ E Rmxdd W E R Rm sub-sampled Z matrix and weights
1: Redefine + 2p, for -- = 1...., 1.
2: First sample with replacement ?? from indices i = .,.,, [ E [m]] each with probability P1.....P144411 Denote m, to be the number of times we observe the index (bucket) during sampling.
3: For each i 11...... 1, ا
construct bj E {0, 13d by sampling with replacement my bitstrings of size i, which equivalent sampling without replacement indices from [d]. uniformly; and generate, the complement big = bi.j.
4: Construct w, ((d 1)p;) and return:
sz = stack((b,, (b)be)(bb W = diag( [wy, wy wylsem).
F.2 Without Replacement Estimators
At first glance, sampling based on the without replacement sampling scheme described in Section 2.3 (see also Appendix A.5) requires flipping 2 coins. However, for the sampling distributions described in Section 2.2, given the size of subset, the probability of picking any given subset of that size is constant. This observation is used in [MW25] to avoid flipping exponentially many coins. In particular, can determine which coins are heads by first determining how many heads there will be of given subset size, and then picking the resulting subsets of this size uniformly at random. We describe variant of [MW25, Algorithm 2] in Algorithm 2.
G Experimental Details
We use publicly available datasets for reproducibility; choosing particularly those available through the shap for their popularity, ease of use and for direct comparison with [MW25].
G.1 Training Details
In this subsection, we detail the experimental design choices and hyperparameter for low Section 3.1 and Section 3.2, including implementation details, to promote reprodicibility.
G.1.1 Low Dimensional Experiments
We refer low dimensional experiments to the content of Section 3.1. For each dataset we train decision tree from the xgboost. Specifically, we use the XGBRegressor class with 100 estimators and maximum depth of 10 for each task. We replacing missing values with the mean for that feature in the dataset. Note that the goal is not to achieve competitive performance but rapidly train model where the Shapley values can be computed exactly and efficiently. The train test splits are ordered 80/20 splits for all datasets; pick query and baseline points the first data points of the test and train datasets respectively.
G.1.2 High Dimensional Experiments
We refer to high dimensional experiments to the content of Section 3.2. For the two classification tasks, train CandomForestCI. clssssiiiiiee from the sci-kit learn library. The random forest has maximum depth 15 and random state 42 for both tasks (MNIST and CIFAR-10) 10). For both datasets, we pick query and baseline points the first data points of the test and train datasets respectively.
For MNIST we use train test splits (80/20) with random state using the train, trrin_test___e test_split method sci sci-kit learn. We achieve a test accuracy of 96.3%.
44

---

Algorithm 2 Sampling without Replacement (paired sampling, modified from (MW25])
Require: d: number of features wæ number of samples expected by user, choice of distribution on d buckets, maxval maximum value before Poisson upproximation applied (our algorithm uses 10
Ensure: SZ E R mmxd W E IR sub-sampled Z matrix and weights
1: Redefine + 2p; for i = 1,................
d-1
2: Choose such that
m = Σ min (1))
2
using binary search algorithm.
3: if (c) < maxval then let
(0)
< Binomial
min(1, ap.)
4: else let
m, < Poisson (ap:))
1
and let mi
m
5: end if
6: Construct j [m,] bitstring arryys of by E 10 of size [[--']] without replacement (c.g. using Fisher Yates shuffling Algorithms 2.3 [MW25]), If there middle bucket (i.e., is odd), fix d = 1 and sample without replacement from the remaining bitstrings. Then, generate the complement b,.j = bigs- (dd 1) min ap:)) and return:
7: Construct w,
SZ stack( bjljem), W diag((m), wyljem)
For the CIFAR-10 dataset, we use standard train test split from the torchvision library. We prepro- cess the input data by normalising. We achieve low accuracy 44.98%, should be expected using basic tree-based models for CIFAR-10; however, using said models enables the exact computation of Shapley values, which consider more important aspect for the paper. We used paired, with replacement estimators with modified & and ba
G.2 Datasets
this subsection, we briefly describe the datasets used for the experiments, for completeness.
G.2.1 shap Datasets
Adult. Demographic information about individuals collected from the 1994 U.S. Census database. is used to predict whether a person earns more than $50, 000 dollars per year based on individual attributes: age, work, class, education, etc...
California. The California Housing dataset is a linear regression tasks containing information collected from the 1990 U.S. Census. This includes data on housing prices targets, and median income, housing age, and average number of rooms as the input features.
Communities. Communities and crime dataset studies the relationship between community charac- teristics and crime rates, including socio-ee socio-econome economic, law enforcement and demographic factors in the United States. This is regression task.
Diabetes. The Diabetes dataset used to predict onset diabetes as diagnostic measurements. includes factors like age, blood pressure, and body mass index.
45

---

Independent and Correlated Datasets that are used to study the behavior of the algorithm under the assumption feature independence and correlation respectively. The target linear regressor of the features.
IRIS. This classic dataset in the field consists of 150 samples of iris flowers, with three different species: Iris setosa, iris versicolor and Iris virginica. Each has four features, describing anatomical sizes of the plant. This a classification task.
NHANES The National Health and Nutrition Examination Survey (NHANES) is a program designed to assess health and nutritional status of citizens of the United States. Based on interview and physical examination data, it predicts survival times based on medical features (regression).
G.2.2 Image Datasets
MNIST The MNIST dataset is collection of handwritten digets (0-9); the classic task is to classify into their respective value. The dataset has 28 x 28(= 748) dimensions. This is an incredibly popular dataset used for training and testing image classification algorithms.
CIFAR-10 CIFAR-10 dataset classification task dataset where a collection of 60,000 images, with 32 x 32 x 3(= 3072) dimensions, are mapped to target clas; cars, airplanes, birds, cats, deer, dogs, frogs, horses, ships and trucks. The standard split for this dataset is 10,000 test images and 50,000 training images, which we use in our experiments. This is considered relatively challenging dataset for boosted trees and feedforward neural networks; good performance achieved, however, for convolutional neural networks.
G.3 Adjustments for Classification Tasks
In the computation of Shapley values for classification tasks, slight adjustment needed. While the output of the classifier is ultimately single value f(x) [c]. for E N classes, computing Shapley on value function that predicts classes would incorrect: in genreal, the classes should not be considered an ordered set. Therefore, we compute Shapley values on the probabilities for each class.
Successively, the mean squared error (normalized) computed on the vectorized output of the Shapley computation. For example, for classification task with classes and a d-dimensional input space, the Shapley values will be in â Rexd, Therefore, to compute the mean squared error (normalized), we vectorize the matrices Shapley values and compute as usual.
In high dimensional experiments, the average is taken across test points. We also provide evaluation details with the purpose of increasing transparency and promoting reproducibility of experiments.
H Extended Experimental Results
The goal of this section is to report the numerical results from our experiments. We first report the extended experiments from Section 3.1, followed by experiments Section 3.2. Importantly, we share tables and plots containing results.
H.1 Low Dimensional Experiments
In low dimensional experiments, as described in Appendix G and Section 3.1, we compute the mean squared error (normalized by norm of exact Shapley values) as the median of 100 random seeds (0-99). We also report the average and interquartile ranges for each of the experiments. These results are summarized in Table 2 (median), Table 3 (lower quantile), Table 4 (upper quantile), and Table 5 (by values). In each of those tables we report the values for selected number of samples: for IRIS report 10; Adult, California and Diabetes we show results for 64; for Communities, Correlated, Independent, and NHANES we report m 50000.
H.2 High Dimensional Experiments
For high dimensional experiments, as described in Appendix G and Section 3.2, we compute the the mean squared error (normalized by norm of exact Shapley values) as the average of 10 test points from the respective datasets. We also report quantiles and median in Table 6.
46

---

H.3 Faithfulness Experiments
For each experiment the high dimensional setting, we compute the insertion and deletion curves as reported in Table 7 (insertion and deletion AUC), Fig. 6 (insertion and deletion curves for MNIST), and Fig. (insertion and deletion curves for CIFAR-10).
Insertion and Deletion Curves for MNIST Dataset
Insertion,
1.8
Percentage Performance
0.2
100
Deletion, neamples
Deletion, nsamplas 100000
0.2
20 40
08
80
100
20
40
60
08
160
KemneSHAP
Figure 6: Insertion and Deletion Plots for MNIST Dataset, for varying number of Samples. As expected, the three methods converge to towards the same curve as the plots increase.
Insertion and Deletion Curves for CIFARIO Dataset
Insertion, no reamples
Insertion, nsamples
0.8
Parcentage Performance
0.2
0.2
20
40
63
88
160
0
20
40
60
88
160
Deletion, neamples
500
Delation, nnamplas 100000
0.4
0.4
Number of Features
Mab-Vac
L-5
KerneSHAAP
Figure 7: Insertion and Deletion Plots for MNIST Dataset, for varying number of Samples. As expected, the three methods converge to towards the same curve as the plots increase.
For any Shapley value, the insertion curve computed by adding features, in order of importance, to an empty vector and computing the prediction. The expectation is that the most important features (the first features to added) contribute most reconstructing good feature attribution method will maximise the area under this curve.
original prediction. Hence,
47

---

Conversely, the deletion curve is computed by removing features (replacing them by 0), in order of importance, the original test point, and computing the prediction. The expectation is that the most important features (the first features to be removed) will deteriorate the performance rapidly. Hence, a good feature attribution method will minimize the area under the curve.
We compute this curve for each test point and average across the curves (as reported in Fig. 6 and Fig. 7). We limit the computation the top 100 features for both datasets and report the values in percentages. Note that for MNIST, this is a complete ordering of all features (64), whereas for CIFAR-10, this only a fraction of the 3072 dimensions. These are commonly used faithfulness measures from the literature: the higher the insertion AUC / the lower the deletion AUC, the higher the faithfulness of the model.
Moreover, for each test point, we compute the Spearman correlation rank from the scipy stats library, on the Shapley values, summed (in absolute value) across classes. We report the results in Table 7. This is a measure of agreement between the true Shapley values and the estimated Shapley values. The higher the Spearman rank correlation, the better the faithfulness of the approximation. Note, however, that due to the presence of many small values (near zero Shapley values) in image classification tasks, this measure may overemphasize incongruence between features.
48

---

With Replacement
Without Replacement
Dataset
Approximation
Sampling
Kernel
kernel
0.0221
kernel
0.577
0.0904
Matrix- Vec
Ez-squared
0.208
0.0793
Adult
modified &
0.2
0.0888
kernel
0,00652
0.0016
Least Squares
fz-squared
0.00509
0.00146
modified
0.00572
0.00136
Kernel
kernel
0.0165
kernel
1.03
0.151
Matrix-Vo Vec
f2-squared
0,218
0.148
California
modified
0.254
0.136
kernel
0.00419
0.00234
Least Squares
fz-squared
0.0039
0.00222
modified &
0.00427
0.00193
Kernel
kernel
0.000810 IO
kernel
0.009871
0.007950
Matrix-Ve
f2-sque
0.009174
0.026858
Communities
modified &
0.007645
0.018672
kernel
0.000887
0.000719
Least Squares
lz-squared
0,000479
0.000301
modified l
0.000554
0,000315
Kernel
kernel
0,000620
kernel
0.007933
0.005208
Matrix Vec
fz-squared
0,009155
0.002495
Correlated
modified &
0.006804
0.002772
kernel
0.0002252
0.000169
Least Squares
fz-Squared
0.000146
0.000064
modified
0.000172
0.000072
Kernel
kernel
0.0163
kernel
1,47
0.218
Matrix-Ves
fz-squared
0,235
0.179
Diabetes
modified
0.274
0.2
kemel
0.00183
0.0106
Least Squares
l2-squared
0.00155
0.00889
modified &
0.0016
0.00983
Kernel
kernel
0.000480
kernel
0.006640
0.004847
Matrix-Vos Vec
f2-squared
0.005631
0.00418
Independent
modified &
0.005024
0.003773
kernel
0.000673
0.000502
Least Squares
fz-quared
0.000401
0.000370
modified lg
0.000487
0.000377
Kernel
kernel
0.0222
kernel
0.471
0,218
Matrix-Ve Vec
lz-squared
0.359
0.229
IRIS
modified &
0.366
0.254
kernel
3,28e-05
1.64e-05
Least Squares
f2-Squared
3.28e-05
1.45e-05
modified
3.28e-05
1.54e-05
Kernel
kernel
0.000597
kernel
0.011273
0.008429
Matrix- Vec
lz-squared 0,013369
0.009053
NHANES
Eg-modified
0.009980
0.007377
kemel
0.002637
0.002153
Least Squares
Eg-squreed
0.001505
0.00221
modified &
0.001674
0.000428
Table 2: Mean Squared Error for Different Sampling and Approximation Methods Across Various
Datasets (best relative MSE performance marked in bold).
49

---

With Replacement
Without Replacement
Dataset
Approximation
Sampling
Kernll
kernel
0.0128
kernel
0.322
0.0635
Matrix-Ve
Ez-squaeed
0.124
0.0526
Adult
modified &
0.101
0.0584
kernel
0.00414
0.000931
Least Squares
f2-Squred
0.00316
0.000895
modified &
0.00305
0.000871
Kernel
kernel
0.0118
kernel
0.595
0.0904
Matrix-Ves
f2-squared
0.15
0.0939
California
modified
0.156
0.0905
kernel
0.00271
0.0017
Least Squares
Ez-squared
0.00281
0.0015
modified &
0.00245
0.00136
Kernel
kernel
0.000735
kernel
0.009144
0.007282
Matrix-Ve Vec
fz-squared
0.008249
0.025044
Communities
modified &
0.006825
0.016340
kernel
0.000785
0.000659
Least Squares
E2-squreed
0.000436
0.000276
modified &
0.000504
0.000284
Kernel
kernel
0.000547
kernel
0.006926
0.004395
Matrix- Vec
Ey-squared
0.008373
0.002188
Correlated
modified &
0.006078
0.002340
kernel
0.000219
0.000149
Least Squares
fz-squared
0.000122 29
0.000058
modified &
0.000149
0.000062
Kernel
kernel
0.012
kernel
0.983
0.153
Matrix-VV
f2-Squared
0.148
0.124
Diabetes
modified &
0.169
0.134
kernel
0.00127
0.00742
Least Squares
E2-squared
0.000874
0.00667
modified &
0.00126
0.00799
Kernel
kernel
0.000435
kernel
0.005925
0.004309
Matrix-Ves Vec
fz-squared
0.004942
0.003723
Independent
modified &
0.004517
0.003284
kernel
0.000581
0.000431
Least Squares
Ez-sqared
0.000353
0.000322
modified &
0.000423
0.000333
Kernel
kernel
0.0108
kernel
0.241
0.123
Matrix-Ves Vec
Ez-squared
0.187
0.127
IRIS
modified &
0.192
0.101
kernel
8.21e-06
1.64e-05
Least Squares
fz-squared
1.15e-05
1.25e-05
modified
8.11e-06
1.44c-05
Kernel
kernel kernel
0.000505
0.010318
0.007504
Matrix-Ve Vec
f2-squared
0.011346
0.008037
NHANES
modified &
0.008947
0.006688
kernel
0.002385
0.001926
Least Squares
suusqud
0.001368
0.00221
modified &
0.001540
0.000375
Table 3: (Lower Quantile) Mean Squared Eiror for Different Sampling and Approximation Methods
Across Various Datasets
50

---

With Replacement
Without Replacement
Dataset
Approximation
Sampling
Kernel
kernel
0.0291
kernel
0.968
0.144
Matrix-Ve
Ez-squaedd
0.276
0.115
Adult
modified &
0.298
0.128
kernel
0.0111
0.00225
Least Squares
f2-Squred
0.00936
0.00238
modified &
0.0091
0.00211
Kernel
kernel
0.0269
kernel
1.64
0.274
Matrix-Ves
f2-squared
0.293
0.242
California
modified
0.376
0.236
kernel
0.00597
0.00313
Least Squares
Ez-squared
0.00542
0.00317
modified &
0.00586
0.00331
Kernel
kernel
0.000877
kernel
0.010869
0.008674
Matrix-Ve Vec
fz-squared
0.009949
0.029046
Communities
modified &
0.008383
0.019998
kernel
0.000968
0.000787
Least Squares
E2-squreed
0,000522
0.000335
modified &
0.000597
0.000346
Kernel
kernel
0.000721
kernel
0.009207
0.005980
Matrix- Vec
Ey-squared
0.010407
0.002896
Correlated
modified &
0.007889
0.003279
kernel
0.000294
0.000195
Least Squares
fz-squared
0.0001 59
0.000073
modified &
0.000184
0.000081
Kernel
kernel
0.023
kernel
2.08
0.358
Matrix-VV
f2-Squared
0.318
0.296
Diabetes
modified &
0.382
0.315
kernel
0.00249
0.0146
Least Squares
E2-squared
0.00237
0.0144
modified &
0.0024
0.0141
Kernel
kernel
0.000551
kernel
0.007710
0.005508
Matrix-Ver Vec
fz-squared
0.006441
0.004724
Independent
modified &
0.005656
0.004196
kernel
0.000745
0.000558
Least Squares
Ez-sqared
0.000463
0.000413
modified &
0.000529
0.000444
Kernel
kernel
0.0453
kernel
0.851
0.593
Matrix-Ves Vec
Ez-squared
0.531
0.411
IRIS
modified &
0.538
0.504
kernel
3.28e-05
2.76e-05
Least Squares
lz-sqqured
3.28e-05
0.000131
modified
3.28e-05
3.3e-05
Kernel
kernel kernel
0.000704
0.012395
0.009490
Matrix-Ve Vec
t2-squared
0.014504
0.009863
NHANES
modified &
0.010979
0.008374
kernel
0.002917
0.002366
Least Squares
su-squreed
0.001668
0.00221
modified &
0.001888
0.000471
Table 4: (Upper Quantile) Mean Squared Error for Different Sampling and Approximation Methods
Across Various Datasets
51

---

Dataset
Samples
Distribution
Q1
Median MSE
Q3
Adult
64
kernel
0.0574
0.0839
0.144
22-Squreed
0.0633
0.0977
0.143
modified &
0.0568
0.0907
0.127
California
64
kernel
0.102
0.165
0.288
22-squrred
0.095
0.129
0.241
modified &
0.098
0.15
0.233
Communities
50000
kernel
0.000765
0.000851
0.000920
22-squree
0.000555
0.000600
0.000672
modified &g kernel
0.000595
0.000637
0.000695
Correlated
50000
0.000495
0.000566
0.000644
squuqed
0.000402
0.000448
0.000528
modified &
0.000431
0.000493
0.000562
Diabetes
64
kernel
0.216
0.36
0.509
f2-squared
0.328
0.432
0.562
modified &
0.29
0.393
0.577
Independent
50000
kernel
0.000435
0.000510
0.000541
f2-squared
0.000368
0.000426
0.000487
modified &
0.000407
0.000446
0.000494
IRIS
10
kernel
0.122
0.443
0,593
22-squreed
0.0883
0.361
0.473
modified &
0.101
0.414
0.54
NHANES
50000
kemne
0.002350
0.002696
0.002915
L l2-squared modified &g
0.001704
0.001868 0.002055
0,002084
0.001845
0.002203
Table 5: Values for by in Fig. 2 (3) Comparison: Quantile Values for Different Datasets and Sampling Methods (least squares estimator without replacement, paired).
Dataset
Samples
Approximation
Time
Q1
Median MSE
Q3
MNIST
500
Matrix-Veae
7.140
10-1
2,625 x 10a
2.668 x 10*
2,681 104
Least Squares
1.850
10"
6.087
10-2
6.144 10-2
6.188 10
KernelSHAP
7.390
10-1
9.235
10"
1.309 102
2.147 102
1000
Matrix Vector
9.270 10
8.394
8.491 x 10
8.566 10/3
Least Squares
1.960 x 10"
5.879 x 10
5.914 x 10
5.949 x 10
KernelSHAP
8.920 10
1.745 10"
1.784 10"
1.816 x 10"
10000
Matrix-Vector Vector
5.540 10"
2.385 102
2.393 10
2.414 102
Least Squares
7.710 10"
4.899 10
4.999 x 1
-0
KemneISHAP
2.940 10"
7.866 X 10-2
7.979 x 10-2
8.058 10-2
100000
Matrix-Vector
5.240 10
1,048 X 10a
1.058 x 10a
L.063 10
Least Squares
6.790 10t
3.071 10
3.117 10
3.150 10
KernelSHAP
2.840 10a
7.374 x 10-3
7.472 x 10
7.393 10
CIFARIO
500
Sutrix-Vector
1.990 x 10a
1,411 X 10a
1,476 x 10a
3.191 10S
Least Squares
9.810 10a
1.440 X 10"
1,478 x 10"
1.491 10"
KernelSHAP
1.390 10a
3.112 10a
1.11X 102
6.247 10P
1000
Matrix Vector
2.180 10a
5.755 X 10a
9.362 x 102
L.314 10a
Least Squares
1.270 103
2.025 X 10"
2.047 x 10"
2.094 10
KernelSHAP
1.350
10a
2.411 X 10S
1.153 x 10S
L.033 106
10000
Matrix-Veds Vector
5.690
10a
9.168 10"
1.031 10a
L.172 102
Least Squares
1.210
103
1.000 X 10"
1.035 1
101
KernelSHAP
2.820
10
2.846 x 10"
2.870 x 10t
2.897 10a
100000
Matrix- Vector
3.190 x 102
1.014 x 10
1.068 x 10a
1.104 x 10a
Least Squares
3.030
103
4.168 10
4.252 x 10
4.295 10
KernelSHAP
1.860
10
1.050 10"
1.053 10"
1.053 10
Table 6: Performance Metrics for MNIST and CIFAR- IO Datasets Using Different Methods (Eg-
squared estimator, without replacement, paired sampling with by).
52

---

Dataset
Samples
Approximation
Deletion AUC
Insertion AUC
Rank. Corr.
MNIST
500
Matrix-Vector
0.758
0.721
0.632
Least Squares
0.758
0.718
0.737
KernelSHAP
0.601
0.589
0,959
1000
Matrix-Ver Vector
0.758
0.719
0,639
Least Squares
0.761
0.718
0.742
KernelSHAP
0.707
0.649
0.975
10000
Matrix- Vector
0.762
0.723
0.655
Least Squares
0.762
0.717
0.753
KerneISHAP
0.762
0.710
0,992
100000
Mltrix-Vector
0.756
0.715
0.674
Least Squares
0.758
0.719
0.767
KernelSHAP 0.762
0.714
0.996
CIFARTO 500
Matrix Vector
0.581
0.548
0.008
Least Squares
0.604
0,535
0.033
KerneISHAP
0.607
0.610
0.026
1000
Matrix Vector
0.560
0,523
0.020
Least Squares
0.584
0.541
0.061
KernelSHAP 0.613
0.612
0.028
10000
Matrix-Vector Vector
0.544
0.510
0.069
Least Squares
0.661
0.571
0.185
KerneISHAP
0.629
0.555
0.184
100000
Matrix-
0.521
0.485
0.239
Least Squares
0.679
0.558
0.662
KernelSHAP 0.685
0.557
0.540
Table 7: AUC and Rank Correlation for MNIST and CIFARIO Datasets Using Different Methods (e2-squared estimator, without replacement, paired sampling with bp).
53


Reviews:
[{"review_id": "cQ6Kc8BeuH", "reviewer": "Reviewer_Z2FN", "summary": "The paper presents a new, unified framework for analyzing and developing randomized algorithms to estimate Shapley values, which are crucial for explaining the outputs of machine learning models. The exact computation of Shapley values is often too computationally expensive, necessitating the use of estimation methods. The contributions include a framework that encompasses many existing randomized estimators for Shapley values, theoretical guarantees for the popular KernelSHAP method, and implementation improvements that enhance the scalability of Shapley value estimation to high-dimensional data.", "questions": "1. One question for the author concerns the implications of the proposed method for Shapley value-based data valuation.\n2. Can you provide some intuition how sampling with replacement works better than without replacement in certain settings and worse in others?\n3. Figure 3 2(a) and (b) remove the top 100 features altogether, and as a result, there are only two data points for each estimator. Can you provide results for individuals one by one?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n- The presentation is clear and flows well. \n- The related work is carefully discussed. \n- The idea of using randomized sketching to unify different Shapley estimators is novel.\n\nWeakness:\n- The improvement of the proposed estimators measured in terms of AUC deletion is marginal.", "was_revised": true, "final_justification": "The paper is a novel contribution to the space of Shapley value estimation. I am leaning toward accepting the paper.", "rebuttal": "We thank the reviewer for their time in carefully reviewing our paper. \nWe answer the reviewer's questions below:\n\n**(1) Implications.**\n\nThe KernelSHAP method is widely used to approximate Shapley values (e.g. the SHAP library has 24k stars on Github). \nHowever, until our work, there were no strong theoretical bounds guaranteeing the accuracy of KernelSHAP. While the method was observed to work well in practice, the lack of theoretical guarantees represented a major gap in the explainability pipeline. By providing theoretical guarantees for the method, our work  further justifies the use of such libraries for providing model explainability in critical fields.\n\nMoreover, by approximating values of $||b_\\lambda||$ and $||Ub_\\lambda||$, it is  possible to estimate the number of samples that will provide a specific $\\epsilon, \\delta$ error bound. In future work, these bounds could be made precise by analyzing the behavior of $||b_\\lambda||$ as the number of samples varies. This also opens up the possibility of adaptively choosing the distribution based on the samples that we have seen so far so as to improve the performance (which was also highlighted by reviewer TpwW), and can be explored in future work.\n\n**(2) Comparison Between Estimator Performance (sampling with/without replacement).**\n\nBased on our theoretical analysis for sampling with and without replacement in the unpaired case, we expect sampling without replacement to perform as well as or better than sampling with replacement. Experimentally, for the case of paired sampling (where we always sample a subset along with its complement), we find that the sampling with and without replacement perform very similarly for the least squares estimator. However, sampling with replacement outperforms sampling without replacement for matrix multiplication estimator in the paired case: we leave the problem developing bounds for the paired case for future research.\n\n**(3) Fine-Grained Results.**\n\nWe believe the information that the reviewer is looking for can be found in Appendix  H (Figures 6 and 7). Indeed, since these are Shapley estimators, we do not expect the curves to vary dramatically; we verify that indeed they converge to a single curve. In this sense, sample efficiency positively impacts faithfulness."}, {"review_id": "2MzE9wiWcA", "reviewer": "Reviewer_7LtQ", "summary": "This work provides the first theoretical guarantee for popular estimators such as KernelSHAP in the context of Shapley value estimation. In particular, the authors provide a unified framework that encompasses many existing randomized estimators for Shapley values and prove the corresponding sample-complexity guarantees.", "questions": "1. I understand that due to the space constraint, lots of the details are hidden in the Appendix. However, it'll be beneficial to have a proof sketch on the main results (Theorem 2.2) for readers to grasp the high-level idea and how the presented framework helps the final proof.\n2. In the discussion around Table 1, it states that the bounds for modified row-norm sampling are no worse than leverage scores and kernel weights in the worst case, but may be almost a factor of $\\sqrt{d}$ better in some cases. However, in the experiments, this phenomenon does not seem to show up in practice. It'll be helpful to elaborate on this (e.g., under what scenarios will one be better/worse than others) in the next iteration.\n3. Some experiments on other models can be included to go beyond tree-based models.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. The scope and the research question are clearly stated and well-motivated.\n2. The writing is rigorous and clear, with careful discussion about how the present work is different from the past literature.\n3. The contribution is sound: the first provable non-asymptotic sample complexity bounds for popular Shapley value estimators. Moreover, the general framework might be of independent interest and can provide guidance on design to other estimators.\n\n**Weaknesses**\n1. As also pointed out by the authors, the sample complexity bounds depend on instance-specific norms, which are hard to compute in practice.\n2. Experiments are mostly limited to XGBoost. Some generalization to neural networks or other black-box models is not explored, even qualitatively.\n\n**Writing**\nOnly small comments on typos:\n1. On line 119, \"In Section 3, we extensive experimental evaluation...\" is there a verb (e.g., conduct) missing?\n2. On line 129, it seems like \"whose columns *for* an\" should be \"whose columns *form* an\"\n3. On line 176, \"$k(S)$.This\" lacks a space.", "was_revised": true, "final_justification": "All my concerns are addressed by the authors' rebuttal, and I maintain my score since my concerns are all minor.", "rebuttal": "We thank the reviewer for carefully reviewing our paper and for also highlighting typos. We will fix the typos that the reviewer has pointed out in the camera-ready version. We address the questions/comments of the reviewer below.\n\n**Questions.**\n\n**(1) Proof Sketch.**\n\nWe agree with the reviewer that it would be nice to include a proof sketch in order to present a high-level picture of how our sample complexity bounds are derived. We will include such a proof sketch in the camera-ready version of our manuscript. It will be included in the main text if space permits, or if not, at the beginning of Appendix A.\n\n**(2) Leverage Scores and Modified Row-Norm Sampling Comparison.**\n\nAs the reviewer pointed out, modified row-norm sampling performs almost as good as leverage scores in the worst case, while they can perform better a factor of $\\sqrt{d}$ in some cases. Whether this advantage in the performance is seen in practice depends on the model at hand.\n\nFor the models that we tested in the experiments, we generally find that leverage scores do slightly better than modified row-norm sampling. On the other hand, to show that we can, in principle, obtain a large advantage for modified row-norm sampling, we have constructed a toy model in Appendix E, where we explicitly demonstrate a factor of $\\sqrt{d}$ advantage of modified row-norm sampling over leverage scores.\n\nThe key idea used for constructing the model in Appendix E is that modified row-norm sampling and leverage scores place different importance on subsets $S \\subset [d]$ of features, and is determined solely by the size of the subsets. Specifically, the weights on subsets of small and large size (compared to $d$) is smaller for the modified row-norm sampling distribution as compared to leverage scores (see Theorem A.6). If we have models for which the entries of the vector $b_\\lambda$ or $P_{U} b_\\lambda$ corresponding to subsets of moderate size is small, we can expect to see an advantage of modified row-norm sampling over leverage scores. As to whether there are models that are used in practice (such as neural networks) where such a condition holds, and consequently, gives an advantage for modified row-norm sampling over leverage scores, needs to be studied in more detail in the future. We note that a similar discussion holds for comparison of kernel weights with leverage scores, and can be found in Appendix E. We can elaborate on these details in the camera-ready version of the manuscript, and also highlight the open question of whether an advantage of modified row-norm sampling over leverage scores can be obtained for models used in practice.\n\n**(3) Experiments Beyond Tree Models.**\n\nIn the present version, estimates are limited to XGBoost since it is possible to compute exactly the true Shapley values for the model using TreeSHAP algorithm. \n\nIt is possible to compute results for neural networks too, but only when the true Shapley values can be computed efficiently ($d\\approx 15$ and smaller). Below, we present experimental results for a neural network trained on the Adult dataset. \nWe measure the error for both least squares and matrix-vector estimators, and samples drawn with and without replacement using the leverage score distribution.\n\n| Num Samples | With Replacement | With Replacement | Without Replacement | Without Replacement |\n|-------------|------------------|------------------|---------------------|---------------------|\n|             | Least Squares    | Matrix Vector    | Least Squares       | Matrix Vector       |\n| 410         | 0.099            | 0.57             | 0.097               | 2.8                 |\n| 1229        | 0.018            | 0.13             | 0.014               | 0.8                 |\n| 2458        | 0.0099           | 0.083            | 0.011               | 0.36                |\n| 3696        | 0.01             | 0.057            | 0.0079              | 0.14                |\n\nWe find the results to be consistent with our experiments on trees, with least squares approximation generally performing better than matrix vector estimator."}, {"review_id": "mNzZGm0Jy2", "reviewer": "Reviewer_soJB", "summary": "The paper provides a general framework for analysing Shapley value estimation algorithms, in particular for the context of explainable ML. \nThe logic of the first part is as follows: (a) the Shapley value is the solution of a linear system of equation, hence can be seen as the solution of a regression (like in SHAP), (b) this regression formulation can be transformed using a whitening/centering change of variable (c) seing the generation of rows as the multiplication by a random matrix, one get two possible reinterpretations of the initial problem:  Sketch Regression and Approximate Vector Multiplication. The second part provides  a sample complexity guarantee for those two interpretations. The  last part is dedicated to experiments on SHAP datasets and on high-dimension datasets, with several sampling schemes being tested.", "questions": "* Why does the reformulation of the regression unlocks this unifying framework? Where does it helps?\n* what do we learn  from the experimental section?\n* It seems the introduction of lambda did not bring anything interesting, why did you choose to keep it?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "# Main remarks\n+ While the analysis borrows from \"Provably Accurate Shapley Value Estimation via Leverage Score Sampling\", the results are new to me and not trivial. They unify several schemes into one theorem. \n\n+ Overall, the paper is written with care, and I could answer most of my questions by looking at the appendix. \n\n- I wish some aspects were more detailed, for example, line 127 could have been a full paragraph. Some key tricks/observations that make this work (for example Lemma A5) could be hinted in the main text. The difference between sketch regression and approximate vector multiplication could be better explained.  The value brought by the experimental section should be clarified\n\n- Table 1 is not easy to read (with H being introduced in the legend), and not really commented.  Also, having the kernel definition in the table would help\n\n+ I did not read all the appendix carefully, but what I looked at was sound. In the appendix, the authors mention a correction made to the main text.\n\n# Minor remarks\n\n- I find the formulation of theorem 2.2  too informal (mixing of O, \\implies and English)\n\n- Algorithm 1 not readable, I do not know what maxval is\n\nl 70: knowledge of knowing\n\nl 67: seems to be a typo in the combinatorial term...\n\nl 129 whose columns *form*\n\nl 221: typo in the mse formula\n\npaired sampling: explain in a few sentence what it is\n\nl 282: there is an issue with this sentence\n\nl 127: could be a full paragraph\n\nl 265: typo", "was_revised": true, "final_justification": "I will keep my positive score. The authors provided satisfying answers to my questions and suggestions.", "rebuttal": "We thank the reviewer for their careful review, highlighting typos, and giving us the opportunity to clarify. \n\nWe will fix all the typos pointed out by the reviewer in the camera-ready version of the manuscript. We will also include a more formal statement of Theorem 2.2 and improve the readability of Table 1 and Algorithm 1. We thank the reviewer for spotting the typo in Algorithm 1; maxval should have only be defined in the context of Algorithm 2 (sampling without replacement), which is the maximum number of samples before which we introduce the Poisson approximation for the sampling distribution.\n\n**(1) Proof Sketch.**\n\nIn response to the reviewer's suggestion (as well as the suggestion of reviewer 7LtQ), we will now be including a proof sketch in the camera-ready version of our paper. It will be included in the main text if space permits, or if not, at the beginning of Appendix A. We hope this would be helpful in providing an overview of the key ideas used in deriving the main theoretical results of our study.\n\n**(2) Regression Reformulation.**\n\nThe main value in the regression formulation to our paper, is that it turns Shapley value computation into a standard linear algebra problem. This is what enables the efficient implementation of KernelSHAP in the SHAP library. In the present work, it also opens a path that allows us to apply existing theory from randomized numerical linear algebra in order to analyze existing methods like KernelSHAP and unbiased KernelSHAP.\n\n**(3) Experimental Section.**\n\nThe experimental section showcases the ability to estimate Shapley values in high dimensions and it compares the different estimators used in practice. For the datasets and models that we tested, we find that the performance of different methods are comparable, with a slight advantage noticed towards the leverage scores sampling, without replacement, least squares estimator.\n\n**(4) Benefits of $\\lambda$.**\nThe main reason we have introduced $\\lambda$ is so that our framework encompasses key past estimators like KernelSHAP, LeverageSHAP, and unbiased KernelSHAP. However, it does raise some questions about the \"best choice\" of $\\lambda$, which we discuss in our response to Reviewer TpwW."}, {"review_id": "feq8nd8y6k", "reviewer": "Reviewer_TpwW", "summary": "This paper introduces a unified framework for estimating Shapley values. The authors start from the Shapley value computation as a constrained regression problem, and then reformulate it into an unconstrained linear regression problem. This reformulation, when solved with additional randomized sketching, allows them to encompass several existing estimators, including KernelSHAP, LeverageSHAP, and unbiased KernelSHAP, within a single theoretical framework. Using tools from randomized linear algebra, they derive non-asymptotic sample complexity bounds valid for all estimators in their framework.\n\nIn their experiments, they compare a large number of variants (least-squares regression versus matrix-vector operations, different sampling strategies, and tuning parameter $\\lambda$) on 8 tabular datasets. They also propose an extension of the algorithm by Musco & Witter, which is more amenable to high-dimension, and allows to perform experiments on MNIST and CIFAR-10.", "questions": "* To me, a key differentiating part of the paper lies in the freedom of choice for $\\lambda$. Could the authors give intuition about sensible choice? (I am not requesting additional numerical experiments, just hints related to e.g. data distribution or test case specificities)\n* Could the authors comment more about adaptive estimators and which type of prior information could be used to design efficient estimation strategies?\n* Related to the previous question, I was wondering if it may be possible to use prior information to optimize the proposed bounds with respect to a sampling scheme.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Even if the main and starting idea of the paper closely follows the one by Musco & Witter, I really enjoy the unification under a single formalism, with the two routes of sketched regression and approximate matrix-vector computation. The novel theoretical guarantee is interesting, in the sense that it paves the way for adaptive strategies. The new approach presented here is thus a promising point of view for improvement in Shapley values. \n\nThe paper is well-written and easy to follow (although there are some misspelling errors that should be corrected), with both novel (to the best of my knowledge) theoretical derivations, and very interesting numerical experiments. Among the strengths of the paper are these numerical findings: least-squares regression generally outperform matrix-vector-based ones, the choice of the sampling strategy is in average less influential, and the choice of the newly introduced parameter $\\lambda$ seems to be important. In addition, Algorithm 2 designed for high-dimensional problems seems to perform well, and I think it deserves more space inside the main paper.\n\nIn my opinion, the only real weakness of the paper lies in the absence of clear prescriptions in practical applications: choice of sampling scheme, and choice of $\\lambda$.", "was_revised": true, "final_justification": "The paper offers a new and very insightful new look at Shapley values estimation, with theoretical results which are promising for future work. The numerical experiments are conducted seriously, are well commented, and illustrates convincingly the author's work.", "rebuttal": "We thank the reviewer for their time in reviewing the paper and for stating their main concern clearly. \nIn the rebuttal below, we will address your questions, while highlighting prescriptions for practical applications. \n\n**Weaknesses.**\n\n**(1) Prescriptions for practical applications.**\n\nBased on our theoretical and experimental results, the following points are of relevance to practical applications:\n\na. We can use the knowledge of how the error scales with the number of samples (given by our theoretical analysis) to get a fairly good estimate of the error (as elaborated in our response to reviewer TpwW). This in turn can be used to prescribe the number of samples needed for a specified error.\n\nb. In practice, the best estimators tend to be those employing leverage score sampling without replacement and using least squares estimator; however, this remains dataset and model dependent.\n\n**Questions.**\n\n**(1) Choice of $\\lambda$.**\n\nUnfortunately, while our analysis reveals that $\\lambda$ should be chosen to try to minimize the size of $b_\\lambda$ or $P_{U} b_\\lambda$, it is currently unclear to us how $\\lambda$ should be chosen a priori, particularly in a model agnostic way. Our numerical experiment suggests that $\\lambda = \\alpha$ (what is used in KernelSHAP and LeverageSHAP) may be better than $\\lambda = 0$ (what is used in unbiased KernelSHAP), but we do not view this as a comprehensive experiment.\n\nMore broadly, variance reduction techniques, such as the one proposed in the supplementary material and concurrent work like \"Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values\" seem to be worthy of future study. We expect that the best techniques will be model dependent, but that they may substantially improve the performance of  Shapley value estimators.\n\n**(2) Adaptive Estimators /  Optimizing Bounds with Respect to a Sampling Scheme.**\n\nYes, this is a good idea, and is something we have been working on. As our analysis reveals, the algorithms converge in a predictable way with $m$ (i.e. the convergence is the Monte--Carlo rate $\\sim 1/\\sqrt{m}$). We have found it works quite well to use the estimate from a larger value of $m$ to approximate the error at some $m_0 \\ll m$. As long as $m\\gg m_0$, the estimate using $m$ samples is a good proxy for the true solution, relative to the size of the error using $m_0$ samples. We can then estimate the error at step $m$ from the estimate of the error at $m_0$ and the known rate of convergence.\n\nIn addition to improving the bounds for a specific distribution, it is possible to use prior information to obtain better/adaptive estimators. Specifically, we can use the previous samples to estimate the vector $b_\\lambda$ or $P_{U} b_\\lambda$, and adapt our sampling distribution accordingly. The algorithm and analysis for such an approach would be more involved since one would ideally like to reuse the previous samples to estimate the Shapley values. While it may not be possible to improve the worst-case performance with such a strategy, it could potentially lead to better performance in practice."}]

Author rebuttal:

Meta-review: Exploiting the fact that the Shapley value is the solution of a (large) linear regression problem, the authors applied matrix sketching techniques to unify many existing estimation algorithms for the Shapley value. In particular, the authors provided the first theoretical justification for the popular KernelSHAP method and proposed a new variant that mixes KernelSHAP and LeverageSHAP. Numerical experiments were conducted to verify the theoretical results. 

The reviewers found the unifying framework, the theoretical justifications and the numerical insights interesting and significant. The reviewers also appreciated the writing and presentation of the paper (barring some minor corrections). The authors' response helped clarify most of the reviewers' questions and resulted in a uniformly positive recommendation, which I concur. This work adds significant novel insights into the existing literature on Shapley value estimation, and should be interesting to the community and possibly inspire further developments. 

In the final version, please incorporate the reviewers' suggestions and some of the details in the rebuttal.
Decision: Accept (poster)