Provably Accurate Shapley Value Estimation via Leverage Score Sampling
Authors: Christopher Musco
R. Teal Witter
Venue: ICLR 2025 Spotlight (2025)
Keywords: Explainable AI
Active Regression
Shapley Values
Leverage Scores
Primary area: interpretability and explainable AI
TL;DR: We propose a theoretically motivated method for estimating Shapley values that outperforms Kernel SHAP.

Abstract: Originally introduced in game theory, Shapley values have emerged as a central tool in explainable machine learning, where they are used to attribute model predictions to specific input features. However, computing Shapley values exactly is expensive: for a model with $n$ features, $O(2^n)$ model evaluations are necessary. To address this issue, approximation algorithms are widely used. One of the most popular is the Kernel SHAP algorithm, which is model agnostic and remarkably effective in practice. However, to the best of our knowledge, Kernel SHAP has no strong non-asymptotic complexity guarantees. We address this issue by introducing *Leverage SHAP*, a light-weight modification of Kernel SHAP that provides provably accurate Shapley value estimates with just $O(n\log n)$ model evaluations. Our approach takes advantage of a connection between Shapley value estimation and agnostic active learning by employing *leverage score sampling*, a powerful regression tool. Beyond theoretical guarantees, we find that Leverage SHAP achieves an approximately 50% reduction in error compared to the highly optimized implementation of Kernel SHAP in the widely used SHAP library [Lundberg & Lee, 2017].

Published as a conference paper at ICLR 2025
PROVABLY ACCURATE SHAPLEY VALUE ESTIMATION VIA LEVERAGE SCORE S SAMPLING
Christopher Musco New York University emusco@nyu. edu
R. Teal Witter New York University
rtealwi wwwllwittteeeu......
ABSTRACT
Originally introduced in game theory, Shapley values have emerged central tool in explainable machine learning, where they are used to attribute model pre- dictions specific input features. However. computing Shapley values exactly is expensive: for general model with features, O(2*) model evaluations are necessary. To address this issue, approximation algorithms are widely used. One of the most popular is the Kernel SHAP algorithm, which is model agnostic and remarkably effective in practice. However, to the best of our knowledge, Kernel SHAP has strong non-asymptotic complexity guarantees. We address this issue by introducing Leverage SHAP, a lightweight modification of Kernel SHAP that provides provably accurate Shapley value estimates with just Onn log n) model evaluations. Our approach takes advantage of connection between Shapley value estimation and agnostic active learning by employing leverage score sampling, a powerful regression tool. Beyond theoretical guarantees, we find that Lever- age SHAP achieves an approximately 50% reduction in error compared the highly optimized implementation of Kernel SHAP in the widely used SHAP li- brary [Lundberg & Lee, 2017].
INTRODUCTION
While AI is increasingly deployed in high-stakes domains like education, healthcare, finance, and law, increasingly complicated models often make predictions or decisions in an opaque and uninter- pretable way. In high-stakes domains, transparency in model is crucial for building trust. More- over, for researchers and developers, understanding model behavior is important for identifying areas of improvement and applying appropriate safeguards. To address these challenges, Shapley values have emerged as a powerful game-ther theoretic approach for interpreting even opaque models (Shapley)
1951 Strumbelj & Kononenko 2014; Datta et al. 2016 Lundberg Lee 2017). These values can be used to effectively quantity the contribution of each input feature to model's output, offering at least a partial, principled explanation for why model made a certain prediction.
method for determining fair 'payouts' for a cooperative game involving n players. The goal is to assign higher payouts to players who contributed more the cooperative effort. Shapley values quantify the contribution of player by measuring how its addition to a set of other players changes the value of the game. Formally, let the value function v: 2. + R be a function defined on sets S S [n]. The Shapley value for player i is:
Concretely, Shapley values originate from game-theory
u(SU (it) uS))
Φ
Σ SCPIO
n
[88
The denominator weights the marginal contribution of player i to set S by the number of sets of size [S], so that the marginal contribution to sets of each size are equally considered. With this weight- ing, Shapley values known be the unique values that satisfy four desirable thmorthe properties: Null Player, Symmetry, Additivity, and Efficiency (Shapley) 1951). For further details on Shapley values and their theoretical motivation, refer the reader to Molnar (2024).
popular way of using Shapley values for explainable Al to attribute predictions made by a model R R on given input E IR" compared baseline input y E IR" (Lundberg & Lee

---

Published as a conference paper at ICLR 2025
The players are the features and v(S) is the prediction of the model when using the features in i.e. v(S) = f(x*) where x," = 2, for i E S and x," = ys otherwise When v is defined in this way, Shapley values measure how each feature value in the input contributes to the prediction.
2017).
Shapley values also find other applications in machine learning, including in feature and data selee- tion. For feature selection, the value function u(S) ] is taken to be the model loss when when using the features S (Marcilio & Eler 2020 Fryer et al. 2021). For data selection, v(S) is taken to be the loss when using the data observations S' (Jia al. 2019 Ghorbani & Zou 2019
1.1 EFFICIENT SHAPLEY VALUE COMPUTATION
Naively, computing all n. Shapley values according to Equation 1 requires O(2") evaluations of
(each of which involves the evaluation of a learned model) and O (2") time. This cost can be reduced in certain special cases, e.g. when computing feature attributions for linear models or decision trees
(Lundberg et al. 2018: Campbell et al., 2022 Amoukou et al. 2022 Chen et al., 2018).
More often, when e is based on an arbitrary model, like deep neural network, the exponential cost in n is avoided by turning to approximation algorithms for estimating Shapley values, including sampling. permutation sampling, and Kernel SHAP (Strumbelj & Kononenko 2010) Lundberg & 2017; Mitchell et al.] 2022). The Kernel SHAP method is especially popular, as it performs well in practice for a variety of models, requiring just small number of black-box. boox evaluations of e to obtain accurate estimates to $1,.... Φn. The method is a corner-ston of the ubiquitous SHAP library for explainable AI based on Shapley values (Lundberg & Lee 2017).
Lee
Kernel SHAP is based on an elegant connection between Shapley values and least squares regression (Charnes et al. 1988). Specifically, let [n] denote (1, !I.....].. denote the empty set, and 1 denote an T vector of length n. The Shapley values Φ = [01,.... [n] E R are known to satisfy:
I's
arg min ||Zx yl12.
where Z E 222-2xx is a specific structured matrix whose rows correspond to sets S S [n]] with 0 < |S] < n, and y E R²" 2 is vector whose entries correspond to values of v(S). (We precisely
define Z and y in Section 2
Since solving the regression problem in Equation 2 directly would require evaluating uSS) for all 2n - 2 subsets represented in y, Kernel SHAP solves the problem approximately via subsampling. Concretely, for a given number of samples m and a discrete probability distribution E [0, 1j2"
over rows in Z, consider a sampling matrix S E mmx2"-2 -2, where each row of S is 0 except for a single entry 1/ /Pj in the jmh entry with probability Py- The Kernel SHAP estimate is given by
arg min
|SZx Sy|12.
x: =x(x)))=((())-0000
Importantly, computing this estimate only requires at most m evaluations of the value function v, since Sy can be constructed from observing most m entries in y. Value function evaluations typically dominate the computational cost of actually solving the regression problem in Equation 3 so ideally m is chosen small possible. In an effort reduce sample complexity, Kernel SHAP does not sample rows uniformly. Instead, the row corresponding to subset S is chosen with proba- bility proportional to:
w w([S]) ((1)))((m - -
(4)
The specific motivation for this distribution is discussed further in Section 2 but the choice is intu- itive: the method is more likely to sample rows corresponding subsets whose size is close to 0 or n, which aligns with the fact that these subsets more heavily impact the Shapley values (Equation] Ultimately, however, the choice of (() is heuristic.
'There are multiple ways to define the baseline y. The simplest is to consider a fixed vector (Ludbberg & Lee (017)) Other approaches define y as a random vector that is drawn from a data distribution (Lundberg et al. 2018 Janzing et al. (2020) and take e(5) = _ where the expectation is taken over the random
choice of y. The focus of our work is estimating Shapley values once the values function e is fixed, so methods and theoretical analysis are agnostic the specific approach used.
2

---

Published as a conference paper at ICLR 2025
In practice, the Kernel SHAP algorithm is implemented with further optimizations Lundberg & Lec 2017:
Covert & Lee 2021 Jethani et al. 2021).
Paired Sampling: If a row corresponding to set S is sampled, the row corresponding to its com- plement $ := [n]] \ S is also sampled. This paired sampling strategy intuitively balances samples so each player is involved in the exact same number of samples. Paired sampling substantially improves Kernel SHAP (Covert & Lee 2021).
Sampling without Replacement: When n is small, sampling with replacement can lead to in- accurate solutions even as the number of samples m approaches and surpasses 2", even though 2" evaluations of are sufficient to exactly recover the Shapley values. In the SHAP library im- plementation of Kernel SHAP, this issue is addressed with a version of sampling without replace- ment: if there is sufficient 'sample budget' for given set size, all sets of that size are sampled (Lundberg & Lee 2017). Doing so substantially improves Kernel SHAP as m approaches 2".
1.2 OUR CONTRIBUTIONS
Despite its ubiquity in practice, to the best of our knowledge, no non-asymptotic theoretical aceu- racy guarantees are known for Kernel SHAP when implemented with m < 2" - 2 row samples (which corresponds to m evaluations of the value function, v). We address this issue by proposing Leverage SHAP, a lightweight modification of Kernel SHAP that 1) enjoys strong theoretical ac- curacy guarantees and 2) consistently outperforms Kernel SHAP in experiments, achieving a 50% reduction in error average (see Table 2)
Leverage SHAP begins with the observation that a nearly optimal solution to the regression problem in Equation 2 can be obtained by sampling just ((n) rows with probability proportional to their statistical leverage scores. natural measure for the "importance" or "uniqueness" of matrix row Sar1ós 2006 Rauhut & Ward 2012 Hampton & Doostan 2015 Cohen & Migliorati 2017) 2 This fact immediately implies that, in principle, we should be able to provably approximate Φ with nearly-linear number of value function evaluations (one for each sampled row).
However, leverage scores are expensive to compute, naively requiring least O(2") time write down for a matrix like Z with O(2") rows. Our key observation is that this bottleneck can be avoided in the case of Shapley value estimation: we prove that the leverage scores of Z have simple closed form that admits efficient sampling without ever writing them all down. Concretely, we show that the leverage score of the row corresponding to any subset S [m] is proportional to (15))
This suggests a similar, but meaningfully different sampling distribution than the one used by Kernel SHAP (see Equation 4. Since all subsets of a given size have the same leverage score, we can efficiently sample proportional the leverage scores by sampling a random size s uniformly from {1. ,I }} then selecting a subset S of size uniformly at random.
Theorem 1.1. For any c O and constant 5 > O, the Leverage SHAP algorithm uses m Oonlog()) + n evaluations of v in expectation and Omm?²) additional runtime to return estimated Shapley values & satisfying (Φ, 1) = v([n)) v(0) and, with probability 1 - 6,
1Z v1l2 < (1 + Z) -
(5)
In words, Theorem I.I establishes that, with near-linear number of function evaluations, we can compute approximate Shapley values whose objective value is close to the true Shapley values. We also require O(mn?) additional runtime to solve the linearly constrained regression problem in Equation although this cost can be reduced in practice using, e.g., iterative methods.
By leveraging the fact that Z is well-conditioned matrix, the bound in Equation 5also implies bound on the average squared error, 1 Φ l|2. which is provided in Section 4 (In Appendix discuss why estimating Shapley values with multiplicative error is NP-hard.)
Beyond our theoretical results, we also show that leverage score sampling can be naturally com- bined with paired sampling, without sacrificing theoretical guarantees. Moreover, we show that
Pechhically, this fact is known for unconstrained least square regression. Some additional work is needed handle the linear constraint in Equation but doing relatively straightforward.
3

---

Published as a conference paper at ICLR 2025
Kernel SHAP
Optimized Kernel SHAP
Leverage SHAP
1.0
1.0
1.0
Precidted Shapley Valuee (6)
0.5
0.5
0.5
0.0
0.0
-0.5
-0.5
-1.0
-1.0
-1.0
0.5
True Shapley Values (6)
True Shapley Values (d)
True Shapley Valum (e)
IRIS
Diabetes (n 10)
Correlated Independeen (n 60)
NIIANES 79)
Californis 8)
Aduls 12)
Communilie (a== 101)
Figure 1: Predicted versus true Shapley values for all features in 8 datasets (we use m 5n samples for this experiment). Points near the identity line indicate that the estimated Shapley value is close to its true value. The plots suggest that our Leverage SHAP method is more accurate than the baseline Kernel SHAP algorithm, as well as the optimized Kernel SHAP implementation available in the SHAP library. We corroborate these findings with more experiments in Section 5
a natural "without replacement" version of leverage score sampling leads to additional accuracy improvements when m is large. Overall, these simple optimizations lead to an algorithm that con- sistently outperforms the optimized version of Kernel SHAP available in the SHAP Library (this 'Optimized Kernel SHAP' algorithm also uses paired sampling and sampling without replacement). We illustrate this point in Figure
More extensive experiments are included in Section 5 We find that the improvement of Leverage SHAP over Kernel SHAP is especially substantial in settings where n is large in comparison to m and when we only have access to noisy estimates of the Shapley values. This is often the case in applications to explainable AI where, as discussion earlier, v(S) is an expectation over functions involving random baselines and estimated via finite sample.
1.3 RELATED WORK
Shapley Values Estimation. As discussed, naively computing Shapley values requires an expo- nential number of evaluations of While more efficient methods exist for certain structured value functions (see references in Section I.I). for generic functions, faster algorithms involve some sort of approximation. The most direct way of obtaining an approximation to is approximate the summa- tion definition of Shapley values (Fquation] D). which involves 0(2") terms for each subset of [n). with a random subsample of subsets (Castro et al., 2009: Strumbelj & Kononenko 2010 Strumbelj & Kononenko, 2014). The first methods for doing so use a different subsample for each player i.
A natural alternative is to try selecting subsets in such a way that allows them to be reused across multiple players (Illés & Kerényil 2019. Mitchell et al. 2022). However, since each term in the summation involves both uSS and vSS {+}). it is difficult to achieve high levels of sample reuse when working with the summation definition. One option is to split the sum into two, and separately estimate EsgnMV ((SU(i)) (1ss)) and Esg()) (+) e(S)/ [is]] 1" This allows substantial subset
reuse, but tends to perform poorly in practice due to high variance in the individual sums (Wang & Jia 2023). By solving a global regression problem that determines the entire & vector, Kernel SHAP can be viewed as a more effective way of reusing subsets to obtain Shapley values for all players.
In addition to the sampling methods referenced above, Covert & Lee (2021) propose modified Kernel SHAP algorithm, prove is unbiased, and compute its asymptotic variance. However, they find that the modified version performs worse than Kernel SHAP. Additionally, recent work in the explainable AI setting takes advantage of the fact that we often wish to evaluate feature impact for large number of different input vectors E RR, which each induce their own
note that some
4

---

Published as a conference paper at ICLR 2025
set function v. In this setting, it is possible to leverage information gathered for input vector to more efficiently compute Shapley values for another, further reducing sample cost (Schwab & Karlen 2019 Jethani et al.) 202T). This setting is incomparable to ours; like Kernel SHAP, Leverage SHAP works in the setting where we have black-box access to a single value function v.
Leverage Scores. As discussed, leverage scores natural measure of importance for matrix rows. They are widely used as importance sampling probabilities in randomized matrix algorithms
for problems ranging from regression (Cohen et al. 2015 Alaoui & Mahoney, 2015), low-rank
approximation (Drineas et al. 2008 Cohen et al. 2017] Musco & Musco| 2017 Rudi et al. 2018).
to graph sparsification (Spielman & Srivastava| 201 and beyond (Agarwal al. 2020).
More recently, leverage score sampling has been applied extensively in active learning as a method for selecting data examples for training (Cohen & Migliorati [2017] Avron et al. [219 Chen & Price
2019
Erdelyi ct al. 2020 J0en Chen & Derezinski [02i]Gaajar ct 20.]]223] et al. Cardenas et al.,
2023
Shimizu al. 2024). The efficient estimation of Shapley values via the regression problem
in Equation can be viewed as an active learning problem, since our primary cost is in observing entries in the target vector y, each of which corresponds to an expensive value function evaluation.
For active learning of linear models with n features under the l2 norm, the On log n n//e) sample complexity required by leverage score sampling is known to be near-optimal. More complicated sampling methods can achieve (n/e), which is optimal in the worst-case (Batson et al. 2012 Chen & Price 2019). However, it is not clear how to apply such methods efficiently to an exponentially tall matrix, manage do for leverage score sampling.
2 BACKGROUND AND NOTATION
Notation. Lowercase letters represent scalars, bold lowercase letters vectors, and bold uppercase letters matrices. We use the set notation [n] =1..... n and (). We let 0 denote the all zeros vector, 1 the all ones vector, and I the identity matrix, with dimensions clear from context. For a
vector x, xj is the 7hh entry (non-bold to indicate a scalar). For a matrix X Rex=, [X]; E 1 is the 1th row. For a vector x, ||x||2 (Ee x²)1/2 denotes the Euclidean (f2) norm and ||x|| Σ, |a|] is the & norm. For a matrix X E iaxxi X denotes the Moore-Penrose pseudoinverse.
Preliminaries. Any subset S C [n)] can be represented by a binary indicator vector z E {0, 13" and we use use v(S) and v(z) interchangeably. We construct the matrix Z and target vector y appearing in Equation byb indexing rows by all z E {0. 13" with ||z|] < n:
Let Z IR.2" 2 -2x be a matrix with [Z], m0( | 12
Let E 2g" be the vector where [y]= = /w( [ - vO)).
Above, w(s) = ((") s(n s s))
is the same weight function defined in Equation
As discussed, the Kernel SHAP method based on an equivalence between Shapley values and the solution of constrained regression problem involving Z and y. Formally, we have:
Lemma 2.1 (Equivalence (Lundberg & Lee 2017
Charnes et al. 1988)).
arg min
Zxx
y1l
(6)
x: (1=)(())
arg min x =00)) 2:0<||><]1 <n
Σ
(ll2)))) ((2,x) (v(z)) (((2)-v(0)) x0)))
(7)
For completeness, we provide a self-contained proof of Lemma 2.1 in Appendix I The form in
Equation 7 inspires the heuristic choice sample sets with probabilities proportional to w([lz]])) in Kernel SHAP, as larger terms in the sum should intuitively be sampled with higher probability to reduce variance of the estimate. However, discussed, more principled way approximately solve least squares regression problems via subsampling is to use probabilities proportional to the statistical leverage scores. Formally, these scores are defined follows:
Definition 2.2 (Leverage Scores). Consider a matrix X E Rex" For i E [p], the leverage score of the th row X): IR 11xx is l. [X) x)+ [[]]]]
5

---

Published as a conference paper at ICLR 2025
3 LEVERAGE SHAP
Statistical leverage scores are traditionally used to approximately solve unconstrained regression problems. Since Shapley values are the solution linearly constrained problem, first re- formulate this into an unconstrained problem. Ultimately, we sample by leverage scores of the reformulated problem, which we prove have a simple closed form that admits efficient sampling.
Concretely, we have the following equivalence:
Lemma 3.1 (Constrained to Unconstrained). Lel P be the projection matrix I - 111 Define A ZP and b = y Z1 v(1)-v(0) Then
Zx y122 = arg min Ax bl2 + u(1) -0
arg min x: xx(xx1)==(1) -1)-v()
(8)
Further, we have that (inx
Zx
y1 minx ||xx -bl2-
When there are multiple x that minimize the objective ||Ax as the that also minimizes ||x|[2-
bll we define arg miny ||Ax bll
Lemma 3.1 is proven in Appendix K Using the equivalent unconstrained regressio problem, we consider methods that construct sampling matrix S and return:
arg arg min |AAx - Sbl + v -0)
x
The main question is how to build S. Our Leverage SHAP method does so by sampling with prob- abilities proportional the leverage scores of A. Since naively these scores would be intractable to compute, requiring (pm=²) time, where p 2 2 is the number of rows in A, our method rests on the derivation of a simple closed form expression for the leverage scores, which we prove below.
3.1 ANALYTICAL FORM OF LEVERAGE SCORES
Lemma 3.2. Let A be as defined in Lemma 3.1 The leverage score of the row in A with index
z E {0, 13", where 0 < ||z]|1 < n, is equal to Eg = (1el11)
The proof Lemma 3.2 depends on an explicit expression for the matrix A T A:: Lemma 3.3. Let be as defined Lemma 3.1 ATA
This fact will also be relevant later in our analysis, as it implies that A A A is well-conditioned. Perhaps surprisingly, all of its non-zero singular values are equal to 1/n.
Proof of Lemma 3.3 Recall that A = ZP, so A A p ZP. We start by deriving explicit expressions for the (1,5) entry of ZZZ, denoted by [z_ Z (1,))- for all i E [n] and j [n]. In particular, we can check that [Z] T Zl(,,) Eze(0.13- 22 w ([z]]1)) So, when $.
Z Z (i.))
w([l[|1)= 2:5t,yy=1
n-1
Σ
n
8 2 wss).
(10)
Let on denote the above quantity, which does not depend on and j. I.e., [ZTZ]
Z (1.)) = en for #
For the case = let j' be any fixed index not equal i. We have that
Z Z)
Σ w([l2]11)
Σ
(([z[|1)+ +
Σ
w (([z||1)
=
- 2)
2
w(s) + Σ
w(s)
C..
(11)

---

Published as a conference paper at ICLR 2025
100
10
Probabiitt
10
10-1
10-2
10-3
6
0
25
50
75
100
0
250
500
760
1000
Subact
Stze
Subeet
Kernel SHAP
Leveragge SHAP
Figure 2: Let S be subset sampled with the Kernel SHAP or Leverage SHAP probabilities. The plots show the distribution of the set size [S] for different n. As in the definition of Shapley values, the leverage score distribution places equal total weight on each subset size, contrasting with Kernel SHAP which over-weights small and large subsets.
The last equality can be verified via a direct calculation. By Equations 10 and Z Z I c,111 So we conclude that:
we have that 11
2
A -A=pP ZP
11 n
(H
(1-
11
-
( 11-111)
1111)
With Lemma
3.3
we are now ready analytically compute the leverage scores.
Proof of Lemma
3.2
The leverage scores are given by lz = [ZP], (A A)
[ZP]_ By
Lemma 3.3 we have that A A 1/ (I L 111 and thus (AT nI 11
Recall that
[Z], = w [|
so [ZP]x = /w([z|]1)> (I 111T). We thus have:
2 |kll 1) T
||z||1
la /u(lzll
(nI 11 )v (([2]]])
n
= [[||]|]))(||]|||
||2lf) = w(1 (|ll11) [|z|]])
n
|||/|
Notice that the leverage scores simply correspond to sampling every proportional to the number of sets of that size. retrospect, this is quite intuitive given the original definition of Shapley values in Equation [ As shown in Figure unlike the Kernel SHAP sampling distribution, leverage score sampling ensures that all subset sizes are equally represented in our sample from A.
3.2 OUR ALGORITHM
With Lemma 3.2 in place, we are ready present Leverage SHAP, which is given Algorithm I In addition to leverage score sampling, the algorithm incorporates paired sampling and sampling without replacement, both of which are used in optimized implementations of Kernel SHAP.
For paired sampling, the idea is to sample rows with probabilities proportional to the leverage scores, but in a correlated way: any time we sample index z, we also select its complement, z, where a = 1 - for i E [n]. Note that, by the symmetry of A's leverage scores, lx Ez. Similarly, ([[[l|])) = ([[[2]])) Moving forward, let Z denote set of pairs (z, 2) where ||z]|| < n.
To perform paired sampling without replacement, we select indices (z, 2) independently random with probability min(1, c(2z + +)) min 2clz), where c > is an oversampling parameter. All rows that are sampled are included in subsampled matrix Z'P and reweighted by the inverse of the probability with which they were sampled. The expected number of row samples in Z/P is equal Σ(z.,) min(1, 2clz). We choose via binary search so that this expectation equals - 2, where target number of value function evaluations (two evaluations reserved compute

---

return /- 2- u11) Published as a conference paper at ICLR 2025
Algorithm Leverage SHAP
Input: n: number of players, e: set function, m. target number of function evaluations (at least n))
Output: Φ: approximate Shapley values
1: m <- -min(m,2")
samples solve exactly
2: Find via binary search so that m 2
Ln/2. min( (()), 2c)
> Equation 12
s==
3: Z' + BeernoullSamplee
>> Sample from Z without replacement (Algorithm
4: i W (2/211) Z' 02
5: for (z.2) E z' do
Build sampled regression problem
6:
((.) + z Z (1+1) t T
7: W(i.)) < W (i+1,++1) +
Correct weights in expectation
8:
i+i+2
9: end for
10: y' v(Z)) r(01
vZ')) evaluates 2 inputs
b'+ y' -(1) Z
12: Compute
arg min W -
>> Standard least squares
n
(1) v0)). Le., we choose to solve the equation:
m Σ
n1 min
1,20
-1
8 )
n
(12)
Note that our procedure different from the with-replacement Kernel SHAP procedure described in Section 1.I Sampling without replacement requires more care to avoid iterating over the exponential number of pairs Z. Fortunately, we can exploit the fact that there are only n 1 different set sizes, and all sets of the same size have the same leverage score. This allows to determine how many sets of a different size should be sampled (by drawing a binomial random variable), and we can then sample the required number of sets of each size uniformly random. Ultimately, we can collect m samples in (mm?) time. Details are deferred to Appendix J
Because we sample independently without replacement, it possible that the number of function evaluations Z'I + 2 used by Algorithm I exceeds m. However, because this number is itself sum of independent random variables, tightly concentrates around its expectation, m. If necessary, Leverage SHAP can be implemented so that the number of evaluations is deterministically m (i.e., instead of sampling from Binomial on Line 4 in Algorithm - set m, to be the expectation of the Binomial). Since this version of Leverage SHAP no longer has independence, our theoretical analysis no longer applies. However, we still believe the guarantees hold even without independence, and leave a formal analysis to future work.
4 THEORETICAL GUARANTEES
As discussed, Leverage SHAP offers strong theoretical approximation guarantees. Our main result is Theorem I.] where we show that, with m O(n (n))) a) samples in expectation, Algorithm
returns a solution & that, with probability - 6, satisfies
A bll < (1 + c) A bll
(13)
We prove this guarantee in Appendix A The proof modifies the standard analysis of leverage scores for active least squares regression, which requires two components: antee, proven with a matrix Chernoff bound applied to a sum of rank- random matrices, and 2) an approximate matrix-mlltpllican
subspace embedding guar-
guarantee, proven with second moment analysis. We replace these steps with 1) a matrix Bernstein bound applied to a sum rank-2 2 random matrices and 2) a block-approximate matrix multiplication guarantee.
8

---

Published as a conference paper at ICLR 2025
IRIS (a 4)
California [a
Diabetes (n=
Adult = 12)
Droc in (-norm
10-1
10-1
10"4
10"
10-9
10-5
10-11
10
10P
10P
10a
10a
10a
102
10a
Correlated (ir 00)
Independent = 60)
NHANES (i 79)
Commanii (n 101)
in 6y-nom
10
10-2
10-2
10-2
10
10-1
10"3
10-2
10-3
10-4
10-1
10
10
10
10P
10"
10"
10
10"
Sample Size (m))
Sample (m)
Sample (m)
Sample
Kernel SHAP
Opsimised Kernel SHAP
Leverage SHAP
Figure 3: The 22-norm error between the estimated Shapley values and ground truth Shapley values as function of sample size. The lines report the median error while the shaded regions encompass the first third quartile over 100 runs. Besides the setting where the exact Shapley values can be recovered, Leverage SHAP reliably outperforms even Optimized Kernel SHAP: the third quartile of the Leverage SHAP error is roughly the median error of Optimized Kernel SHAP.
While well-motivated by the connection between Shapley values and línear regression, the objective function in Theorem I.]is not intuitive. Instead, we may be interested in the f2-norm error between the true Shapley values and the estimated Shapley values. Fortunately, we can use special properties of our problem to show that Theorem 1.1 implies the following corollary on the l f-rn error.
Corollary 4.1. Suppose o satisfies Then
A A
< (1++)] AΦ - bl
Let - A
|
E7 1
The proof of Corollary appears in Appendix B problem-specific parameter y which intuitively measures how well the optimal coefficients & can reach the target vector b. In Appendix(E] We find (see e.g., Figures 5 that performance does erode as 7 increases for all regression-basel algorithms, suggesting that 7 not an artifact of our analysis.
The statement of the corollary is in terms of
explore how the performance varies with in practice.
EXPERIMENTS
In the experiments, we evaluate Leverage SHAP and Kernel SHAP based on how closely they align
with the ground truth Shapley values. We primarily use the mnrn error i.e., | - 21 / 1 as the error metric. We run our experiments on eight popular datasets from the SHAP library (Lund- berg & Lee, 2017). We find that Leverage SHAP outperforms the highly optimized Kernel SHAP. achieving a 50% reduction in error on average (see Table 2 addition, we find that Leverage SHAP consistently outperforms Permutation SHAP (see the additional experiments in Section
Implementation Details. In order to compute the ground truth Shapley values for large values of n. we use tree-based model for which
compute the exact Shapley values efficiently using Tree SHAP (Lundberg & Lee 2017). All of our code is written in Python and can be found on Githut We the SHAP library for the Optimized Kernel SHAP implementation, Tree SHAP, and the datasets. We use XGBoost for training and evaluating trees, under the default parameters.
Additional experiments. So that we do not overcrowd the plots, we show performance on Kernel SHAP, the Optimized Kernel SHAP implementation, and Leverage SHAP in the main body. We also all of the experiments with the ablated estimators in Appendix G The ablation experiments (see e.g., Figure () suggest that Bernoulli sampling (sampling without replacement) improves Leverage SHAP for small n and the paired sampling improves Leverage SHAP for all settings. Because more interpretable, we report the -orm error metric to compare the estimated to the ground truth Shapley values. We also report the linear objective error for similar experiments Appendix H
writhue httthh.ccm/rreellttteee/eeeeeeee

---

Figure plots the performance for Kernel SHAP, the Optimized Kernel SHAP, and Leverage SHAP as the number of samples varies (we set m 5m, 10n, 20n..... 160m). For each estimator, the line the median error and the shaded region encompasses the first and third quartile over 100 random runs Kernel SHAP gives the highest error in all settings of and pointing to the importance of the paired sampling and sampling without replacement optimizations in both Optimized Kernel Published as a conference paper at ICLR 2025
IRIS
California
Diabeles
Adult
Correlated
Independent
NHANES
Communities
Kernel SHAP
Mean
0,026
0.0266
0.0553
0.0673
0,0465
0,0264
0.0604
0.12
Quartile
1.61e-05
0.00829
0.0116
0.0182
0.0202
2nd Quartile
0.000898
0.0236
0.0229
0.0345
0,0404
0.0217
0.0388
0.089
Quartile
Optimized Kernet SHAP
Mcan
4.84cc-09
0.00342
0,00758
1st Quartile
1.66e 13
0,000880
0.00161
0.00187
0.00499
0.00194
0.001.56
0.009962
Quartile
2.17c-13
0.00238
3rd Quartile
2.69c-10
0,00489
0.00868
0.0122
0.015
0.00695
0.00871
0.0325
Leverage SHAP
Mean
4.84g-09
0.000311
0.0023
0.00477
0.00716
0.00288
0.00532
0.0156
1st Quartile
1.66e-15
4.47e-05
0.000215
0.000477
0.00289
0.000843
0.000995
0.0062
2nd Quartile
2.17e-13
0.000133
0.000969
0.00124
0.00528
0.00257
0.00288
0.0104
3rd Quartile
2.69c.10
0,000366
0,00241
0.00354
0.00891
0.00417
0.00554
0.0225
Table 1: Summary statistics of the n-rmorm enror for every dataset. We adopt the Olympic medal convention: gold silver and bronze cells signify first, second and third best performance, re- spectively, Except for ties, Leverage SHAP gives the best performance across all settings.
SHAP and Leverage SHAP. Because both methods sample without replacement, Optimized Kernel SHAP and Leverage SHAP achieve essentially machine precision as m approaches 2". For all other settings, Leverage SHAP reliably outperforms Optimized Kernel SHAP; the third quartile of Leverage SHAP generally at the median of Optimized Kernel SHAP. The analogous experiment for the linear objective error depicted in Figure TO indicates the same findings.
Table depicts the estimator performance for m = 10n. The table shows the mean, first quartile, second quartile, and third quartile of the error for each estimator every dataset. Except for ties in the setting where m 2 2", Leverage SHAP gives the best performance followed by Optimized Kernel SHAP and then Kernel SHAP.
Beyond sample size, we evaluate how the estimators perform with noisy access to the set functions in Appendix [D As in the sample size experiments, Leverage SHAP meets or exceeds the other estimators, suggesting the utility of the algorithm as a robust estimator in explainable Al.
6 CONCLUSION
We introduce Leverage SHAP, a principled alternative to Kernel SHAP, designed to provide provable accuracy guarantees with nearly linear model evaluations. The cornerstone of our approach is lever- age score sampling, powerful subsampling technique used in regression. To adapt this method for estimating Shapley values, reformulate the standard Shapley value constrained regression prob- lem and analytically compute the leverage scores of this reformulation. Leverage SHAP efficiently uses these scores produce provably accurate estimates of Shapley values. Our method enjoys strong theoretical guarantees, which we prove by modifying the standard leverage score analysis to incorporate the empirically-mootivteed paired sampling and sampling without replacement opti- mizations. Through extensive experiments eight datasets, demonstrate that algorithm outperforms even the optimized version Kernel SHAP, establishing Leverage SHAP as a valuable tool in the explainable Al toolkit.
WWe report the median and quartiles instead of the mean and standard deviation since the mean minus standard deviation negative for the small values in our experiments.
10

---

Published as a conference paper at ICLR 2025
7 ACKNOWLEDGEMENTS
This work was supported by the National Science Foundation under Grant No. 2045590 and Grad- uate Research Fellowship Grant No. DGE-2234660. We are grateful to Yurong Liu for introducing us to the problem of estimating Shapley values.

---

Published as a conference paper at ICLR 2025
REFERENCES
Naman Agarwal, Sham Kakade, Rahul Kidambi, Yin-Tat Lee, Praneeth Netrapalli, and Aaron Sid- ford. Leverage score sampling for faster accelerated regression and erm. In Proceedings of the s1 International Conference on Algorithmic Learning Theory, 2020.
Ahmed Alaoui and Michael W Mahoney. Fast randomized kernel ridge regression with statistical guarantees. In Advances in Neural Information Processing Systems 28 (NeurIPS), 2015.
Salim Amoukou, Tangi Salaün, and Nicolas Brunel. Accurate shapley values for explaining tree- based models. In International conference on artificial intelligence and statistics, pp. 1448-2466
PMLR, 2022.
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco. Ameya Velingker, and Amir Zandieh. A universal sampling method for reconstructing signals with simple fourier transforms. In Proceedings of the 5t Anmual ACM Symposium Theory of Computing (STOC), 2019.
Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice- RacceRaamnnnjnn sparsifiers. SIAM
Journal on Computing, 4 116):1704-17 2012.
Thomas W Campbell, Heinrich Roder, Robert Georgantas III, and Joanna Roder. Exact shapley values for local and model-true explanations of decision tree ensembles. Machine Learning with Applications, 9:100345, 2022.
Juan M. Cardenas, Ben Adcock, and Nick Dexter. CS4ML: general framework for active learning with arbitrary data based on christoffel functions. In Advances in Neural Information Processing Systems 36 (NeurIPS), 2023.
Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the shapley value based on sampling. Computers & Operations Research, 3665):1226-1730) 2009.
A Charnes, B Golany, M Keane, and J Rousseau. Extremal principle solutions of games in char- acteristic function form: core, chebychev and shapley value generalizations. Econometrics of planning and efficiency, pp. 123-133, 1988.
Jianbo Chen, Le Song, Martin J Wainwright, and Michael I Jordan. L-shapley and c-shapley: Effi- cient model interpretation for structured data. In Proceedings of the 7th International Conference on Learning Representations (ICLR), 2018.
Xue Chen and Michal Derezinski. Query complexity least absolute deviation regression via robust uniform convergence. In Proceedings of the 34th Anmual Conference on Computational Learning Theory (COLT), volume 134, pp. 1144-11 1179, 2021.
Xue Chen and Eric Price. Active regression via linear-sample sparsification active regression via dinear-sample sparsification. In Proceedings of the 32nd Annual Conference on Computational Learning Theory (COLT), 2019.
Albert Cohen and Giovanni Migliorati. Optimal weighted least-squares methods. SMAI Journal of Computational Mathematics, 3:181-203, 2017.
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation. In Proceedings of the 6th Conference on Innovations in Theoretical Computer Science (ITCS), pp. 181-190, 2015.
Michael B Cohen, Cameron Musco, and Christopher Musco. Input sparsity time low-rank approx- imation via ridge leverage score sampling. In Proceedings of the Twenty-Fghtth Annual ACM- SIAM Symposium on Discrete Algorithms,, pp. 1758-1777. SIAM, 2017.
Ian Covert and Su-In Lee. Improving KemeISHHA. Practical shapley value estimation using linear regression. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, pp. 3457-3465, 2021.
Anupam Datta, Shayak Sen, and Yair Zick. Algorithmic transparency via quantitative input influ- ence: Theory and experiments with learning systems. In 2016 IEEE Symposium on Security and Privacy, pp. 598-617, 2016.
12

---

Published as a conference paper at ICLR 2025
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Relative-error CUR matrix decompo- sitions. SIAM Journal on Matrix Analysis and Applications, 30(2):4448881,
Tamás Erdélyi, Cameron Musco, and Christopher Musco. Fourier sparse leverage scores and ap- proximate kernel learning. Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
Daniel Fryer, Inga Strümke, and Hien Nguyen. Shapley values for feature selection: The good, the bad, and the axioms. leee Access, 1114432--143800 2021.
Aarshvi Gajjar, Chinmay Hegde, and Christopher Musco. Active learning for single neuron models with Lipschitz non- non-lineanee -inarineas. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS), 2023.
Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. In International conference machine learning, pp. 2242-2251, PMLR, 2019.
Jerrad Hampton and Alireza Doostan. Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression. Computer Methods in Applied Mechanics and Engineering, 290:73 97, 2015.
Ferenc Illés and Péter Kerényi. Estimation of the shapley value by ergodic sampling. arXiv preprint arXiv: 05224, 2019,
Dominik Janzing, Lenon Minorics, and Patrick Blöbaum. Feature relevance quantification in ex- plainable ai: A causal problem. In International Conference artificial intelligence and statis- tics, pp. 2907-2916. PMLR, 2020.
Neil Jethani, Mukund Sudarshan, Ian Connick Covert, Su-In Lee, and Rajesh Ranganath. Fastshap: Real-time shapley value estimation. In International conference on learning representations, 2021.
Ruoxi Jia, David Dao. Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J Spanos. Towards efficient data valuation based on the shapley value. The 22nd International Conference on Artificial Intelligence and Statistics, pp- 1167-1176. PMLR, 2019.
Scott M Lundberg and Su-In Lee. A unified approach interpreting model predictions. Advances in neural information processing systems, 30, 2017. URL prttps://githin ctt. ccm/shpp// shap
Scott M Lundberg, Gabriel G Erion, and Su-In Lee. Consistent individualized feature attribution for tree ensembles. arXiv preprint arXiv: net::000200000 2018.
Wilson Marcílio and Danilo M Eler. From explanations to feature selection: assessing shap values as feature selection mechanism. In 2020 33rd SIBGRAPI conference on Graphics, Patterns and Images (SIBGRAPI), pp. 340-347. Ieee, 2020.
Rory Mitchell, Joshua Cooper, Eibe Frank, and Geoffrey Holmes. Sampling permutations for shap- ley value estimation. Journal of Machine Learning Research, 23(43):1-46, 2022.
Christoph Molnar, Interpretable machine learning: guide for making black box models explain- able. Leanpub, 2024.
Cameron Musco and Christopher Musco. Recursive sampling for the nystrom method. In Advances in Neural Information Processing Systems 30 (NeurIPS), 2017. 2017.
Cameron Musco, Christopher Musco, David P. Woodruff, and Taisuke Yasuda. Active linear gression for Ep norms and beyond. In Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS).
Holger Rauhut and Rachel Ward. Sparse Legendre expansions via El-minimization. Journal of Approximation Theory, 164(5):517 533, 2012.
13

---

Published as a conference paper at ICLR 2025
Alessandro Rudi, Daniele Calandriello, Luigi Carratino, and Lorenzo Rosasco. On fast leverage score sampling and optimal learning. Advances Neural Information Processing Systems, 31, 2018.
Tamás Sarlós. Improved approximation algorithms for large matrices via random projections. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006.
Patrick Schwab and Walter Karlen. Cxplain: Causal explanations for model interpretation under uncertainty, Advances in neural information processing systems, 32, 2019.
Lloyd S Shapley. Notes the n-person game-il i:: The value of n-person game. 1951.
Atsushi Shimizu, Xiaoou Cheng, Christopher Musco, and Jonathan Weare. Improved active learning via dependent leverage score sampling. In Proceedings of the 12th International Conference on Learning Representations (ICLR), 2024.
Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 4066;1913-1926, 2011.
Erik Strumbelj and Igor Kononenko. An efficient explanation of individual classifications using game theory. The Journal of Machine Learning Research, 11:1-18, 2010.
Erik Štrumbelj and Igor Kononenko. Explaining prediction models and individual predictions with feature contributions. Knowledge and information systems, 41:647-665, 2014.
Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230, 2015.
Jiachen Wang and Ruoxi Jia. Data banzhaf: robust data valuation framework for machine learning. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 6321. PMLR, 25-27 Apr 2023.
Yue Wu. A note random sampling for matrix multiplication. arXiv preprint / 2018.
14

---

Published as a conference paper at ICLR 2025
Appendices
CONTENTS
Introduction
1.1
Efficient Shapley Value Computation
1.2 Our Contributions
Related Work
2
Background and Notation
3
Leverage SHAP
3.1
Analytical Form of Leverage Scores
3.2 Our Algorithm
Theoretical Guarantees
5
Experiments
6
Conclusion
10
Acknowledgements
11
Appendices
15
A Proof of Approximation Guarantee
16
Proof of Approximation Corollary
19
Computational Hardness
20
D Noisy Access to the Set Function
20
Error Relative to Optimized Kernel SHAP
21
F
Exploring 7
22
Additional Experiments with -n-no Error
23
Ablation Experiments with Objective Error
24
Constrained and Unconstrained Equivalence
25
J
Efficiently Sampling Without Replacement
26
Constrained Regression
28
15

---

Published as a conference paper at ICLR 2025
A PROOF OF APPROXIMATION GUARANTEE
In this section, we prove the following theorem.
Theorem A.1. Let m On ;) + n hc) Algorithm I produces an estimate o such that, with probability 1 - 5,
A bll - (1+ + A -b12-
Because of the connection between the constrained and unconstrained regression problems described in Lemma 3.1 the theorem implies the theoretical guarantees in Theorem 1.1 The time complexity bound Theorem 1.1 follows from Lemma
J.1
Appendix
Consider the following leverage score sampling scheme where rows are selected in blocks. (We use the word "block" instead of "pair" in the formal analysis for generality.) Let θ be a partition into blocks of equal size (size 2 in our case) where the leverage scores within a block are equal. Block O; independently sampled with probability p. := min(1, Ekee, f.) for a constant c. The constant e is chosen so that the expected number of blocks sampled is m. i... E,P," = m. Let m' be the number of blocks sampled. Let S E R |m. xp be the (random) sampling matrix. Each row of S corresponds to a row l from a sampled block i: every entry in the row 0 except for the kth entry which is 1/vP: p."
In order to amalyze the solution returned by Algorithm I we will prove that the sampling matrix S preserves the spectral norm and Frobenius norm.
Lemma A.2 (Bernoulli Spectral Approximation) Let U E RRxx be a matrix with orthonormal columns. Consider the block random sampling matrix S described above with rows sampled ac- cording to the leverage scores of U. When 12(n (og(n)/)))))
|| SU
6 5
(14)
with probability
Proof of Lemma A.2 We will use the following matrix Bernstein bound (see e.g., Theorem 6.6.1 in Tropp et al. 2015)).
Fact A.3 (Matrix Bernstein). Consider a finite sequence X, } of independent, random, Hermitian
matrices with dimension n. Assume that E xx] = O and X 11112 S L for all i. Define = -, X
and let V = ||[[**] = E, E 11... Then for any e > O.
2212
Pr ( 2 2 e) S nexp
(15)
Le/3)
Let ((k)) E Rlxn be the kth row of U. Similarly, let Ue, E R|/ be the matrix with rows U(k.)
for k E O;
We will choose X, = Uj, Ue.
UT. p.
1 UUT Ue, 1[i selected]. Then E[X,] = and X = I
SU. TU.
First, we will upper bound max; X if not selected or pt = 1, then || |X,||2 = so we only
need to consider the case where is selected and pt cc Ekee, ls < 1. Then
X S
|U_ Ual S Σ [U = -
(16)
p
P. keB:
Next, we will upper bound Σ3 E[x,11la Again, notice that E|X;| = 0 0f = so we only need consider the case where p,
< 1. Then
Σ E| = Σ pt
11
-
1
(U), Ue,)² + +1
2 (1-x)) pt) (U. Uo.)
(17)
p
Ep
16

---

Published as a conference paper at ICLR 2025
Notice that p 11--1/0 (1-1/p,)) (1 p, P
12+1/p; +1- p.- 1/p. -1 1/p Therefore
170
Σ
U Uo. U Uo.
(18)
<1 pi
upp
Observe that entry (k, of Ua, Uø, E e U. So the absolute value of each entry
U2 2 by Cauchy-Schwand Define zunx maxkee, Ex and euii minker; 4- By the Gershgorin circle theorem, Ue, Ug. 20 2 Equivalently,
| I || U
A B, x Ax x Bx for all x. Consider an arbitrary z. We have z C ACz < z T BCz
since Cz is some It follows that 6, Ue, Ug, Ua. 3 24,axx U,, Uo Then
1 20max O 2 Uo.
mmax
[18]
max 2 θ
fmin I.
(19)
EKEO, lx
Since [0:| < 2 and the leverage scores in a block all equal, || S 4/c.
Recall that e is chosen that E, min(1, Exse, (x) S c E; Eseo, la en, where the last equality follows because the leverage scores sum n. So 1/c n/m.
Plugging in to Fact A.3 we have that
-me?
Pr -T
SUI22 2 c) exxp
<
(20)
4+t/3
provided m = -[nn ())
Next, will prove that the sampling matrix preserves the Frobenius norm.
Lemma AA4 (Frobenius Approximation). Let U Rxxa be matrix with orthonormal columns. Consider the block random sampling matrix S described above with rows sampled according to the leverage scores UfU. U. Let V E RRxx'' As long as m 2 56
1. then
(21)
with probability 1 8.
Proof. We adapt Proposition 2.2 in Wu 2018 to the setting where blocks are sampled without replacement.
E|JJUT ST - U
Σ
-
UTV
(22)
h2=
(a(UUSSSSV)aan))) (V)))))))
(23)
where the last equality follows because TJUSSTSV U V. We will consider an individual
entry in terms of the blocks If p.f = 1, then the entry is so we only need to consider the case where p < Then, using independence, we have
Var((UTS] SV) (h))))) =
Σ ExpT
Var - 1li selected] (h,,..) ((e.)))))
(24)
p.
(U.,.e.) V(orna)))
(25)
Pr
Exp!
<1
17

---

Published as a conference paper at ICLR 2025
1
23 <
Σ
Σ
U (e..)
(26)
pi
EppT <1
ppp
Exeo, |
| (V,)))
11 -
IVI
- m
(27)
Ckee, lx
P <1
where the last equality follows because m and By Markov's inequality.
||
E [ sv - UTVlle]
1
- (UL
S
me²
(28)
as long as m 2 d2
With the spectral and Frobenius approximation guarantees from Lemmas A.2 and A.4 to prove Theorem A.1
we are ready
Proof of Theorem A.1 Observe that
AA
b bl = |A AΦ + AΦ - bli2 = | - A + |A - bb
(29)
where the second equality follows because AΦ b orthogonal any vector in the span of A. So to prove the theorem, it suffices to show that
|| A <
e A - bll..
(30)
Let U E RRxx' be orthonormal matrix that spans the columns of A where n' There is some y such that Uy AΦ and some ý such that Uý Aœ. Observe that || || - Uylle = |y - yl12 where the last equality follows because U
Aølle
By the reverse triangle inequality and the submultiplicavity of the spectral norm, we have
1 y1l |
y)ll2 + s - JUS - yy)ll + S Su - -1 - yll2.
y) y)lla
(31)
(32)
Because U has the same leverage scores A and the number of rows sampled in S is within constant factor of m, we can apply Lemma A.2 With m O(n log "), we have | S
Ill2 < with probability - 6/2. So, with probability 1 1 8/2,
y yll 2 S STS -2
(33)
Then
SUSTSU((E - | S (SUý Sb Sb SUy)
(34)
||U ST S (Uy -b)l1
(35)
where the second equality follows because SUý Sb is orthogonal any vector in the span of
SU. By similar reasoning, notice that U (Uy - b) = 0. Then, as long as m = O R we have
U UTSSSUUy - -b)l < Ve
| - bll2
(36)
2/n
with probability 1 5/2 by Lemma A.4
Since U has orthonormal columns, | S n. Then,
combining incqualities yields
|| | - AΦl l1 = llý - y11 < T STusy < - -blž = A b
(37)
with probability 5.
18

---

Published as a conference paper at ICLR 2025
B PROOF OF APPROXIMATION COROLLARY
We will establish several properties specific to our problem and then use these properties to prove Corollary 4.1
Lemma B.1 (Properties of A, Φ. and Φ). The Shapley values Φ, the matrix A, and the estimated
Shapley values & produced by Algorithm / satisfy
1 - 1 21
A <011
(38)
and
A = 1 (11011 (v(1) v())²²
(39)
Proof. Even though A does not have n singular values, we can exploit the special structure A, Φ, and é. Let A = UEVT T be the singular value decomposition of A. By Lemma 3.3 we know E (x--1)x is a diagonal matrix with y on the diagonal and V E (n has
orthonormal columns that are all orthogonal to 1. Let Vi,..., Vn-1 E R" be these vectors. Then
A
i= v
13
u.v. where " nn-1 E 2R2"- are the n 1 orthonormal columns in U.
By Lemma 2.1 and 3.1
write
V48 + (11 (0)
n-1 Φ
Viã v(1) (0)
and
(40)
n
n
1=1
for some 8, and &, where
[n- 1]. Then (Φ-
Φ) -i=1
v, 8,) and
A( x) Σ 1
(3)
83)
u [5 s.)
(41)
n
so A 3) = | $12
Similarly, we can write
V58j v(1) - v(0)
AΦ
?
Σ U;8;
(42)
where the second equality follows because VI...., Va-1 are orthogonal to 1. Then | ((())=r(0))² n
[
Corollary 4.1. Suppose & satisfies Then
< (1+E)] AΦ - bb Lery = | b/B//AB/
|1 - - < 2
Proof of Corollary 4.1 We have
A
b l A AØ + AΦ bll2 A
AΦ1 + || bl
(43)
where the second equality follows because AØ b is orthogonal to any vector in the span of A.
Then, by the assumption, we have
A
AØl < c A bl2
(44)
By the definition of | and Lemma B.I |
1 ey
[ (o(1) r00))²
cl A
blß e7
A
(45)
19

---

Published as a conference paper at ICLR 2025
Finally, by Lemma B.1 along with Equations 44 and 45 have
1 1 212
1 <> 1 Φ)12 -)12 < <c A bll2 - n
|
-
(46)
The corollary statement then follows after multiplying both sides by n.
C COMPUTATIONAL HARDNESS
When the Shapley value problem is viewed as an optimization problem, we provide a constant factor approximation in polynomial time (see e.g.. Theorem I.1p.
On the other hand, suppose we wanted to, e.g., ensure that to; S ă. S Co; for all We claim that obtaining this goal for any constant C' is NP-hard in many settings. In particular, to ask about computational hardness, we also need to specify the input to the algorithm: i.., is v given as a polynomial size circuit, a polynomial size formula, or as black-box, unit cost oracle? In all of these settings the problem is NP-hard to approximate. In particular, consider the case when either evaluates to O for all sets, or evaluates to () for all sets except for single set S. In the first case, the Shapley values will all equal O, whereas in the second case, the Shapley values for indices in are non-zero. As such, to obtain a multiplicative approximation, set S for which v does not evaluate to When v is a black-box, finding such a set clearly requires (2(2") time (we only enumerate all possible inputs). However, it is still hard when is given other forms. For example, if u is a given as a circuit, then determining if there is an S for which vSS) o 0 is equivalent to the NP-complete circuit SAT problem.
need to determine if there is some
This argument makes it clear why asking for a multiplicative approximation is not reasonable, and why instead we might care about approximation in objective value. This is the case for many computational problems: for example, in the class of NP-hard optimization problems like set cover, do not typically ask approximate the optimal solution itself, but instead to find another solution with nearly the same objective value as the optimal solution (whether or not it is similar to that optimal solution or not).
D NOISY ACCESS TO THE SET FUNCTION
In this section, we explore how the regression-based estimators perform given noisy access to the set function This setting is particularly relevant for Shapley values in explainable AI, since the set function may be an expectation that is approximated in practice. Figure 4 shows plots performance noise is added to the set functions: Instead of observing vSS), the estimators observe v + where ( ~ (00 o²) is normally distributed with standard deviation a (we set o = 0,5 x 10 3,12 x
10 10-2 5 x 10-2 ,...,
IRIS
California
Diabetes (n
Adult (n
Ervor in troor
20
10
10a
10
10-4
10
10
10
10
10
10
10
10
10
10
16
10
10"
10
Correlated [a 60)
Independent (i
NHANES = 79)
Commumitees [0 101)
Errer in geoor
10-1
10
10
10-2
10-3
10-1
10-2
10
10
10
10-2
10-1
100
10
10-
10-1
10
10-1
10
10
Standoni Diviiation Neion (n)
Standard Deciation of
Stanckad Trovistion Nubes (nc
Standoni Devisation
Kernel SHAP
Optimiised Kernel SHAP
Leverage SHAP
Figure 4: The fg-norm error between the estimated and ground truth Shapley values as a function of noise in the set function. Leverage SHAP gives the best performance in all settings; the third quartile of the Leverage SHAP generally matches the median of the Optimized Kernel SHAP error.
20

---

Published as a conference paper at ICLR 2025
E
ERROR RELATIVE TO OPTIMIZED KERNEL SHAP
Dataset
5n
10n
20n
40n
80n
160n
IRIS
1.00
1.00
1.00
1.00
1.00
1.00
California
0.0923
0.0909
0.0463
1.00
1.00
1.00
Diabetes
0.314
0.247
0.278
0.203
0.110
1.00
Adult
0.351
0.482
0.536
0.318
0.279
0.276
Correlated
0,484
0.614
0.613
0.658
0.682
0.685
Independent
0.540
0.608
0.614
0.637
0.658
0.651
NHANES
0.572
0.702
0.757
0.709
0.658
0.741
Communities 0.514
0.668
0.647
0.681
0.661
0.722
Table The table reports the average error ratio over 100 random runs between Leverage SHAP and Optimized Kernel SHAP. For example, on the Correlated dataset with m = 5n samples, Leverage SHAP achieved estimates with 54% the error of Optimized Kernel SHAP. A ratio of indicates that 2 2", and both algorithms recovered estimates accurate to machine precision. On average (excluding entries where the ratio is 1), Leverage SHAP estimates have 50.2% of the error of Op- timized Kernel SHAP. In other words, Leverage SHAP achieves roughly a 50% reduction in error compared to Optimized Kernel SHAP.
Table presents the average enror ratios between Leverage SHAP and Optimized Kernel SHAP across various datasets and sample sizes, computed over 100 independent random runs. Each entry reports the ratio of the mean absolute error of Leverage SHAP to that of Optimized Kernel SHAP. For example, on the Correlated dataset with m = 5n samples, Leverage SHAP achieved an error that was 54% of the eπтоr of Optimized Kernel SHAP. A reported ratio of corresponds to cases where m 2 2n, which both methods recovered estimates accurate to machine precision. Averaging over all non-unit entries, Leverage SHAP achieved 50.2% of the error of Optimized Kernel SHAP, corresponding to an approximate 50% reduction in error
21

---

Published as a conference paper at ICLR 2025
F EXPLORING y
The problem-specific term 7 = || - - b appears in the f2-norm guarantee of Corollary In this section, explore the distribution of 7, and the performance by 7. Because exactly computing 7 requires evaluating b, we focus on datasets where S 16.
Table shows summary statisties of y over 100 (the randomness comes from the different models trained on the data). On every dataset, the third quartile of y is less than 2.
Table 3: Summary statistic of over 100 runs.
Dataset
"
1st Quartile
2nd Quartile
3rd Quartile
IRIS
4
0.000234
0.266
1.03
California
8
0.158
0.298
0.449
Diabetes
10
0.174
0.321
0.513
Adult
12
0.180
0.395
0.703
In Figure 5] we explore experimentally whether y is an artifact of our analysis necessary param- eter. We perform the experiment by explicitly building the matrix (only possible for small n) and then choosing b linear combination of vector in the column span of A and vector not in the column span of A. Then, we back out the corresponding set function e using the definition of b. We induce different values of
vary how much of b is vector in the column span of A. Because all three of the algorithms we consider perform worse as y increases, the experiment suggests that y is an artifact of our analysis. The same trend appears for the ablated estimators, as shown in Figure 6 As our analysis suggests, does not appear to be relevant factor for the objective error, as shown in Figure
Synthetic (N
Syuthetic (N 12)
Syuthetic 14)
Syathetic (n 16)
Bevor in fynorm
10-1
10-1
10-1
101
10
10P
10
10
10-1
109
Kernel SHAP
Optinized Ketnel SHAP
Leverage SHAP
Figure 5: The fz-norm error as a function of y, the problem-specific parameter in Corollary 4.1 The lines indicate the median and the shaded regions encompass the first and third quartile over 100
runs. All three of the main algorithms we consider have higher l -oomm error as grows, suggesting that y is not an artifact of our analysis.
Synthetic (R 10)
Synthesie (o 12)
Syuthotic (n m 14)
Symthetic (n 16)
Brooe in fewerm
0.4
0.50
0.2
0.2
0.25
0.25
0.00
10
10"
107
10
10P
10
10
10"
10'
10
10'
Kernel SHAP
Leverage
Leverage SHAP Bermonlli
Optimized Kernel SHAP
Kernel SHAP Paired
Leverage SHAP wo Bernoull, Paired
Figure 6: The fo-m error as a function of 7, the problem-specific parameter in Corollary 4.1 The lines indicate the mean over 100 runs. All algorithms we consider have higher form error as ? grows, suggesting that y is not an artifact of our analysis.
22

---

Published as a conference paper at ICLR 2025
Syuthetic (e
Synthetic 12)
Synthotic (n
Syuthetic 16)
Erove Objective
1.00
1.02
100
1.00
1.02
1.01
10
10
10
10
10"
10
10
Kernel SHAP
Leverage SHAP
Leverage SHAP wo Bernoulli
Optimized Kernel
Kernel SHAP Paired
Leverage SHAP we Bernouli, Paized
Figure 7: The linear objective error as function of y, the problem-specific parameter in Corollary The lines indicate the mean
100 runs. All algorithms we consider have dependence on grows, suggesting that yy is not relevant parameter for the linear objective error. This finding aligns with Theorem I.I which has no dependence on ?.
G ADDITIONAL EXPERIMENTS WITH b NORM ERROR
Table evaaluates additional estimators. Leverage SHAP continues to give the best performance,
notably outperforming Permutation SHAP
IRIS
California
Diabetes
Adult
Correlated
Independent
NIAANES
Communities
Kernel SHAP
Mean
0.026
0.0266
0.0553
0.0673
0.0465
0.0264
0.0604
0.12
1st Quurtile
1.61e405
0.00829
0.0116
0.0182
0.0244
0.0134
0.0202
0.0563
2nd Quartile
0.0008988
0.0236
0.0229
0.0345
0.0404
0,0217
0.0388
0.089
Quartile
Optimized Kernel SHAP
Mean
4.84c-09
0.00342
0.0093
0.00899
0.0117
0:00474
0.00758
0.0233
1st Quurtile
1.66e:
0.000802
0.00161
0.00187
0.00499
0.00194
0.00156
0.00962
2nd Quartile
2.17c-13
0.00238
0.003566
0.00489
0.00916
0.00391
0,00425
0.0173
Quartile
0.00871
Leverage SHAP
Mean
4.84c-09
0,000311
0.0033
0.04477
0,00716
0.00288
0,00532
0.0156
1st Quurtile
1.66e-13
4.47e.05
0.000215
0.000477
0.00289
0.000843
0,000995
0.0062
2nd Quartile
2.17e-13
0.000133
0.000969
0.00144
0,06528
0.00257
0,00288
0,0104
3rd Quartile
2.69c-10
0.000366
0.00241
000354
0,00891
0.00417
0.00554
0.0225
Kernel STAP Paired
Mean
0.00343
0.00081
0.00337
000007
0.00483
0.00754
0.0249
1st Quartile
3.07e-10
9.92e-05
0.0004444
0.000676
0.00395
0.00143
0.00156
0.0108
2nd Quartile
1,28c-47
0.000361
0.00203
0,00557
0L00827
0.00344
0,00415
6016
3rd Quartile
0.000189
0.000971
0.00565
0,04822
0.0141
0.00658
0.00857
0.034
Leverage SHAP (Unnpaired)
0.0332
0,049
1st Quartile
9. 9.5e-06
0.00834
000944
0.0144
0.0171
0.00775
0.00969
0.0322
2nd Quartile
0.000951
0.0133
00184
0.0303
0.0245
0.013
0.024
0.0495
3rd Quartile
0.0277
0.0328
0,035
0.067
0.0356
0.02
0.0479
0.0774
Permutation SHAP
1st Quartile
1.29c-09
0.000174
0.000785
0'000708
0.00403
0.00109
0.00127
0.0105
2nd Quartile
2.35e-07
0.000793
0.00361
0.00222
0.0098
0.00338
0.00355
0.0188
3rd Quartile
0.000659
0.00196
0.0102
0.0079
0.0199
0.00847
0.00789
0.045
Table 4: Normalized f2-norm by dataset and estimator, reported in summary statistics from 100 random runs.
Figures g and show additional experiments where the error is measured with the fn-n enror. We find that Leverage SHAP gives the best performance.
23

---

Published as a conference paper at ICLR 2025
IRIS 4)
California
8)
Diabetes (r
Adult
Troc in Gpnorrs
10-2
10
10
10-4
10-7
10-7-
10
10.
10P
20t
10a
Correlated = 60)
Independent (f 00)
NHANES = 79)
Commanitiee (n 1013
Erver in Gytorm
10-1
10
10-3
10"
10
10
10a
10
Sample (m)
Sacpple (m)
Saceple Size
Sample
Kernel SHAP
Leverage SHAP
Leverage SHAP (Unpaized)
Optimized Kernel SHAP
Kernel SHAP Paired
Permutation SHAP
Figure 8: The -orm error between the estimated Shapley values and ground truth Shapley values function of sample size. The lines report the mean error over 100 runs. Leverage SHAP reliably gives the best performance, exceeding second- best Optimized Kernel SHAP for small n and Leverage SHAP w/o Bernoulli Sampling for large n1.
IRIS (x
California (x 8)
Diabetes in 10)
Adult (n 12)
Brove in fynorm
10a
102
10-2
10-2
10-5
10
10--3
10
10
10"
10
10
10
10'
10-2
10
10
10
Correlated (a 60)
Independent (p 60)
NILANES (n 79)
Commumities [p 101)
Erro in fymoem
10-3
10-1
10
10
Standard Deviation of Noise (e)
Standard Deviation of Noto (e)
Standard Deviation Noiso (o)
Standard Deviation of Noise (e)
Leveragg SHAP
Leverage (Unpaired)
Optimised Kornel
Kernel SHAP
Permutation SHAP
Figure 9: The f--ormm eтrоr between the estimated and ground truth Shapley values as function of noise in the set function. Leverage SHAP gives the best performance in almost all settings, with the exception of NHANES where Leverage SHAP with replacement (without Bernoulli) gives slightly better performance.
H ABLATION EXPERIMENTS WITH OBJECTIVE ERROR
Figures TO and 11 show ablation experiments where the error is measured with the objective value naturally suggested by the regression formulation. We find that Leverage SHAP, or its ablated version without Bernoulli sampling, give the best performance.
24

---

Published as a conference paper at ICLR 2025
fo
California (a
10)
Aduul 12)
Ercor Obojecive
1.1
1.2
1.2
1.1
1.0
1.0
10"
Sumple Size (m))
Sumple Sizw (m)
Sample Sizn (m)
Sample Sion (nc)
Kernel SHAP
Leverage SHAP
Leverage SHAP (Unpoirer))
Optimized Kernel SHAP
Kernel SHAP Paired
Permusaation SHAP
Figure 10: Linear objective error by sample size. The lines indicate the mean error over 100 runs. Leverage SHAP quickly achieves the lowest error in all settings. (For small n, numerical instability can lead to eπror below 1.)
IRTS (N
California
Diabetes (n 10)
Adult 12)
1270r Oljectore
50
2
1.00
Standard Deviation of Nosse (5)
Standard Devistion of Notoo (o)
Standard Deviation Noie: (o)
Standazd Devtation of Noioe (o)
Kernel SHAP
Leverage SHAP
Leverage SHAP (Unpaime))
Optimised Kernel SHAP
Kernel SHAP Paind
Permutatiin SHAP
Figure 1I:
Linear objective error by standard deviation noise. The noise grows large as a ap- proaches one for all algorithms. The plots indicate no clear winner across all four datasets.
I CONSTRAINED AND UNCONSTRAINED EQUIVALENCE
Lemma 2.1 (Equivalence Lunddberg & Lee
2017:
Charnes et al. 1988)).
arg min x: =1x))))
|Zx yll2
(6)
arg min
Σ
w((2 ((2, x) - (v(z) =())))
(7)
xx 1) ( (1)
2:0 |x
We provide a cleaner, direct proof using the unconstrained problem and the exact characterization of Z Z.
Proof of Lemma 2.1 We will show that
blb + v(1) - (0)
Φ = arg min || Ax
(47)
where = ZP and = Z1 =(0) Then Lemma 2.1 follows from Lemma 3.1
We know
arg min Ax - blß (A (AT AT
(48)
By Lemma 3.3 we have (A (A+ ( ZP) nI 11T rP. Then
(A AATA) = TPPTTT nPZT.
(49)
Let z E 13" with 0 < |z/]| < n. It follows that
A = -nP TT
- TT Vw([lz]l)) (o(z) v(0))
2
-()))((0)
72
25

---

Published as a conference paper at ICLR 2025
By symmetry, the last term is scaling of the all ones vector so it gets projected off by P. Recall w(s)
[-- -=- The weights are carefully designed so that w(s)s w(s + 1) 3 1).
m!
Then, for i E [n], we have the ith entry of (A T A)+ - A given by
E
||]]]) (v(z) (0) (([lz]])((zz
2:0x 110aa|
Σ
n - 1
0(S)
Σ (
11 n-
v(S)
(50)
+ ((nl) =(0)
v(())) v(0)
(51)
n1
1 Σ
0(S) T1
Σ
1
v(S)
(52)
n1 9:11)
9:0
((nil) - v00)
(53)
Φ; v([n]] - v())
(54)
n
where the first equality follows by converting from binary vectors to sets. Then Equation 47 follows.
J EFFICIENTLY SAMPLING WITHOUT REPLACEMENT
Since there are an exponential number of rows, the naive method of considering each row indepen- dently will not work. Our approach is follows: For each set size s E [[n/2]], we sample the number of samples that will be chosen. This is distributed as a Binomial distribution with (") trials
and probability (1, 2a(")= ") Then, because the probabilities are the same for all subsets of size
exploit this symmetry and sample random indices uniformly from [(")] without replacement. We index all subsets of size s and then construct the subsets corresponding to the randomly sampled
indices without enumerating all subsets. The Bernuuli sampling code appears in Algorithm 2 and the subset construction code appears in Algorithm 3 both deferred to Appendix
Like before, there is one special case when is and there is middle set size |n/2]. Here, the paired samples z and Z have the same size s so we need to partition the set of all subsets of size s so we do not risk sampling the same pair twice. We accomplish this by sampling from all subsets of n items with size 8 then appending 2,, = 1 and computing the complement z.
Lemma J.1 (Time Complexity). Let m' be the number of samples used in Algorithm 7 and define Tmn the time complexity of evaluating in parallel m' inputs. Algorithm 7 runs in time O(m'n' n22 + T.
For most settings, we expect Ti to dominate the time complexity. For example, consider a shallow fully connected neural network with inner dimension just n. Even evaluating the forward pass on mn inputs for a single layer of this network takes time O(m'n²).
Proof of Lemma J.7 Bernoull 1 Sample takes O(mn²) time: For each pair of samples, we call Combo at most twice which takes time at most O(n²) since there are only two loops, each over at most items. For simplicity of presentation, the algorithm calls v three times: once with input 1, once with input 0, and once with m' - 2 inputs. However, by concatenating the inputs, the algorithm can be easily modified to call e once on m' inputs for time complexity of Tm Computing the optimal subsampled solution Ø² takes Onn²) time compute a factorization of a n x n matrix and (mm' n²) time to compute the n x n matrix. Since m' 2 n, the time complexity is Omm'n²). I1
26

---

Published as a conference paper at ICLR 2025
Algorithm 2 Bernoul hwte:ouulllSmmlpllll Samplelm. c): Efficient Bernoulli Sampling
Input: number of players, probability scaling
Output: Z': random sample Z that independently contains pair (z, Z) w.p. min(1, 2c 2.)
1: 2 <-
2: for set size E (1...., m do
3: isMiddle (2) A ]
> Special handling of middle size for paired samples
4: m, Binomial( ("), min (*) (")"
5: m, + m if isMiddle
6: randomindices + m, uniform random integers drawn without replacement from [())
7: for randomIndices do
8:
K- Combo (n, 8, isMiddle then
ith combination of n items with size & (Algorithm
9:
> Partition the middle size by setting Zn ith combination of n items with size 8
10:
< Comboo nn - 1, 1,
11:
Append 0 to z
12: end if
Add (z, z) to Z' 14: end for
13:
15:
end for
16: return 2'
Algorithm Combo 8, i): Compute the ith Combination in Lexicographic Order
Input: n: total number of elements, s: subset size, i; index of subset
2: Output: z: the ith combination (lexicographically) in binary form
3: z <- O,, <- 8, start +-
4: for idx E {1...., 3 do
5: for E {start..... n do
6: count + (-x-1)
>> Combinations possible with remaining elements if j is added
7: if count then
8:
2j + b - start s break
-
Add
9:
> Decrease the number of elements left to choose Update starting index to ensure lexicographic order
10:
11:
12:
else
13:
i count
b Skip this batch of combinations
end if
15:
end for
end for
17:
return z
27

---

Published as a conference paper at ICLR 2025
K CONSTRAINED REGRESSION
Lemma 3.1 (Constrained to Unconstrained). Let P be the projection matrix
1 111
Define
A ZP and b y Z1 v(0) Then
Zx - y1 = arg min Ax bl2 v( v0
arg min x: x((x
(8)
Further, we have that mxll::(xx11
Zx y minx | bll2
Proof of Lemma 3.1 We will decompose x into one vector that is orthogonal to 1 and another vector that scaling of 1. That is, x' cl where (x', 1) 0 for some c. In order to satisfy the
constraint, follows that c o(1)-e(0) Then
arg min (10
Zx y
arg min
|Z(x' + c1) -y11
(55)
x x 1)==
arg min | (y -CZ1)]l +c1
(56)
x' =0
arg min ZPx - (y- - cZ1))l2 +1
(57)
x'
We used P to project off any component in the direction of 1 and thereby remove the constraint. Plugging in the value of with the definitions of A and b yields the first equation. The second equation follows by similar argument.
Traditional Solution Used in Kernel SHAP Consider the problem
x
arg min
Zx y11
(58)
xxxx
For Leverage SHAP, we reformulate the problem to an unconstrained regression problem with Lemma 3.1 and solve it using standard least squares.
In the standard Kernel SHAP implementation, the constrained problem solved directly using the method of Lagrange multipliers. We put the analysis in here for completeness.
The Lagrangian function with respect to x and multiplier E is
[(x, A)
Zx
y112 + X( (x, 1) - -(1= +())
(59)
At the optimal solution x* and X", the gradients with respect and O. This observation implies the following two equations:
- 11
VxL(x", x²) = 27 ZZx*
+ + = x" xz= ZTy -
(60)
2
VxC(x*,>') -x)=
(0)) 0.
(61)
Together, Equations 60 and 61 tell that
X²
-(0))= -)
Z Z
(62)
2
Plugging back into Equation 60 we have that
1 1T
- - 0(0))
x" = =2= z)-1 ZTy
(63)
1 1TZZZ)
28


Reviews:
[{"review_id": "FDqeKYLiz8", "reviewer": "Reviewer_LX1d", "summary": "This paper provides a new algorithm for approximating Shapley values with provable guarantees. Shapley values have widespread application in ML as a way of formalizing individual feature contributions to a model's final prediction, although this paper considers the fully general setting in terms of a generic value function $v : 2^{[n]} \\to \\mathbb{R}$ (where $n$ is the number of features or \"players\"). \n\nThe algorithm builds on a known way of formulating the Shapley value as the solution of a certain $2^n$-dimensional linear regression problem. The widely used \"Kernel SHAP\" algorithm approximates the solution by essentially subsampling the rows of the design matrix in a certain way. But a more principled approach is to subsample according to leverage scores, a well-studied concept in statistics. The catch is that naively, leverage score take time polynomial in the size of the design matrix (so $2^{O(n)}$) to compute. The key idea the authors exploit to get around this is that for the specific Shapley design matrix, the leverage scores can actually be written down in a simple closed form.\n\nThis allows them to efficiently solve the underlying regression problem and carry over known guarantees from the leverage score toolbox. Specifically, they show that the estimated Shapley values are close to the true Shapley values in a certain sense (both in terms of the optimum achieved and the values themselves). They show further refinements using paired sampling without replacement.\n\nFinally, they show various experiments demonstrating that the resulting algorithm indeed outperforms the previous best Kernel SHAP algorithm in practice.", "questions": "1. It would be nice to have a fuller picture of the Shapley value problem from a broader approximation algorithms standpoint. The linear regression approach is ultimately just one approach to the problem. Do we have a sense for the best possible approximation one can hope for? Are there any computational inapproximability results?\n1. Also, it's natural to ask whether additional structure makes the problem easier (e.g. for the specific setting of feature attribution). I realize this is indeed true for decision trees and such. But I am curious if the authors have an idea of a \"dream result\" under less restrictive but still reasonable structural assumptions, especially for feature attribution. For feature attribution for a general black box model, is the Leverage SHAP approach likely to be the best?\n1. One thing that was not totally clear to me from the experiments is whether Leverage SHAP strictly dominates Kernel SHAP at every point in the running time vs accuracy graph. That is, for any fixed running time budget, is it always better to run Leverage SHAP? Theoretically, one concern could be that Leverage SHAP necessarily requires sampling $m = \\Omega(n \\log n)$ rows (IIUC based on Thm 1.1), whereas I believe Kernel SHAP allows you to pick $m$ arbitrarily (albeit without a guarantee). Thus perhaps for small running time budgets, maybe Kernel SHAP can sometimes be more effective than Leverage SHAP. Or perhaps Kernel SHAP is just better optimized as a practical implementation.\nI think Figure 3 (sample size $m$ vs error) nearly answers this question, but my question is whether there is any subtlety in how $m$ translates to actual running time. And in general if there is any catch to the \"strictly dominates Kernel SHAP\" question.\n\nMinor nit: in two places (lines 132 and 266) there is a typo: \"principal\" -> \"principle\".", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Shapley values are a basic and important topic in interpretable AI and beyond, finding wide application in practice. The problem of efficiently estimating them well is a very well-motivated one. This paper makes a very nice and useful contribution to this problem. The key theoretical insight of analyzing the form of the leverage scores is simple but very clever and elegant, and allows them to make use of a very well-studied toolbox in statistics (although there is still technical work to be done). It immediately feels like the \"right\" way to solve the problem. The resulting algorithm is theoretically sound, clean, simple, as well as effective in practice. The paper is also very clearly written, with a clear description of all the relevant context as well as clear exposition in general. I did not verify all the proofs in complete detail but they seemed correct to me.", "weaknesses": "I do not see any major weaknesses. I do think would be helpful for the authors to discuss the limitations of the Leverage SHAP algorithm a bit more (e.g. does it strictly dominate all prior algorithms?), and provide some context on what still remains open in this space (see below for related questions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9pdt7DN49M", "reviewer": "Reviewer_7UDD", "summary": "The paper develops a computationally efficient method for approximating Shapely values, which are useful in interpretable machine learning. The proposed method provides a modification of the well-known Kernel SHAP method, with additional non-asymptotic theoretical convergence guarantees and better empirical performance. The authors use a modified sampling without replacement approach to optimize their method and report experiments with ablation studies for the optimizations.", "questions": "- Which algorithm in the literature does the Optimized Kernel SHAP in the experiments correspond to?\n- Do the theoretical guarantees for leverage SHAP continue to hold when optimizations like paired sampling, and sampling without replacement are not applied? Is there a difference in the guarantees with and without the optimizations?\n- In Table 2, Leverage SHAP w/o Bernoulli sampling seems to outperform in some cases. Is there a way to understand this? An analysis or discussion around this would be very useful to better understand the method's behavior.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Estimating Shapley scores accurately and efficiently is an important problem in explainable machine learning. The paper provides a theoretically principled approach for this problem.\n- The approach seems to outperform Kernel SHAP and optimized Kernel SHAP baselines in the experiments.", "weaknesses": "- The main theoretical result (Theorem 1.1) is somewhat unsatisfactory as it does not directly compare the true and estimated Shapely values. The authors address this via Corollary 4.1, but it has a non-intuitive $\\gamma$ term which is can be large and makes the approximation guarantees weaker. Are there conditions under which $\\gamma$ is guaranteed to be small? This would better help understand the limitations of current theoretical results.\n- The experiments could include more baselines like (Jethani et al., 2021), (Mitchell et al., 2022b), and (Yang & Salman, 2019) for a more comprehensive comparison with the state-of-the-art.\n- The technical novelty in proving the new theoretical results also appears to be limited. The main result seems similar to the active learning guarantee Theorem 1.1 of Shimizu et al. ICLR 2024, and it is not clear what additional technical insights are needed to develop the current result. A discussion of novel technical insights needed to develop the current result would be helpful.\n\nTypos:\n- Line 155, Line192 finte, Line 255 contrained\n- References are incorrectly bracketed", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MWFDfr5OnF", "reviewer": "Reviewer_m993", "summary": "This paper modifies the Kernel SHAP algorithm, which approximates the Shapley value and model-agnostically quantifies the role of each feature in a model prediction. The Kernel SHAP did not enjoy theoretical convergence guarantees, and the authors propose a modification of this algorithm that offers a theoretical convergence guarantee and similar numerical performance.", "questions": "N.A.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper is very well written, introduces the context of their work beautifully, and provides both a theoretical and practical contribution to the field.", "weaknesses": "A weakness is that it might feel niche, but as a non-specialist in interpretable AI, I cannot judge the importance of the Shapley values. If this information is important, then the author's contribution is quite important because it removes some level of heuristic thanks to their theoretical contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)