Conceptio › Archive › arXiv CS

arXiv CSopen access

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Weida Li 1 Yaoliang Yu 2 3 Bryan Kian Hsiang Low 1

arXiv:2604.08438v1 [cs.LG] 9 Apr 2026

Abstract

learning applications, the axiom of efficiency is unarguably unnecessary (Kwon & Zou, 2022a;b), and the removal of it leads to a broader family of semi-values (Dubey et al., 1981). Specially, each semi-value ϕ(U ) ∈ Rn can be expressed as, for every i ∈ [n] := {1, 2, . . . , n}, X ϕi (U ) := p|S|+1 [U (S ∪ {i}) − U (S)]

The Shapley value, and its broader family of semivalues, has received much attention in various attribution problems. A fundamental and longstanding challenge is their efficient approximation, since exact computation generally requires an exponential number of utility queries in the number of players n. To meet the challenges of large-scale applications, we explore the limits of efficiently approximating semi-values under a Θ(n) space constraint. Building upon a vector concentration inequality, we establish a theoretical framework that enables sharper query complexities for existing unbiased randomized algorithms. Within this framework, we systematically develop a linear-space algorithm that requires O( ϵn2 log 1δ ) utility queries to ensure P (∥ϕ̂ − ϕ∥2 ≥ ϵ) ≤ δ for all commonly used semi-values. In particular, our framework naturally bridges OFA, unbiased kernelSHAP, SHAPIQ and the regression-adjusted approach, and definitively characterizes when paired sampling is beneficial. Moreover, our algorithm allows explicit minimization of the mean square error for each specific utility function. Accordingly, we introduce the first adaptive, linear-time, linear-space randomized algorithm, Adalina, that theoretically achieves improved mean square error. All of our theoretical findings are experimentally validated.

S⊆[n]\{i}

(1)

Z 1 with ps =

s−1

(1 − t)

n−s

dµ(t),

where µ is any Borel probability measure on the closed interval [0, 1]. For the Shapley value, µ corresponds to the −1 uniform distribution, resulting in ps = n1 n−1 . Here, s−1 [n] U : 2 → R is the so-called utility function that depends on the contexts. For example, in attributing the model performance to each data point, U (S) is usually defined as the performance of models trained on S (Ghorbani & Zou, 2019; Ilyas et al., 2022). In explaining the contribution of each feature to a specific model prediction, U (S) is usually defined as the expected prediction when features not in S are treated as missing (Lundberg & Lee, 2017; Lundberg et al., 2020). From Eq. (1), it is clear that computing ϕ exactly in general requires an exponential number of utility queries of U , which constitutes the major hurdle that limits the applicability of semi-values. Therefore, a great number of efforts have been devoted to designing efficient approximation algorithms (Jia et al., 2019; Covert & Lee, 2021; Zhang et al., 2023; Wang & Jia, 2023; Li & Yu, 2023; Kolpaczki et al., 2024; Li & Yu, 2024a; Fumagalli et al., 2024; Li & Yu, 2024b; Musco & Witter, 2025; Chen et al., 2025; Witter et al., 2025). The existing approximation algorithms can be divided into two categories. The first category improves the approximation quality by minimizing the mean square error (MSE)

1. Introduction In recent years, the Shapley value and its broader family of semi-values have found various potential applications in machine learning (Rozemberczki et al., 2022; Cohen-Wang et al., 2024; Deng et al., 2025). The popularity of the Shapley value mainly comes from its uniqueness in satisfying a certain set of axioms (Shapley, 1953). In certain machine

E[∥ϕ̂ − ϕ∥22 ], where ϕ̂ denotes an estimate of ϕ produced by a randomized algorithm. All stratified algorithms (Castro et al., 2017; Zhang et al., 2023; Wu et al., 2023) follow this pattern. The second category tries to provide sharp query complexities, defined as the minimum number of queries to ensure

1 Department of Computer Science, National University of Singapore, Republic of Singapore 2 School of Computer Science, University of Waterloo, Canada 3 Vector Institute, Canada. Correspondence to: Weida Li <[email protected]>.

P(∥ϕ̂ − ϕ∥2 ≥ ϵ) ≤ δ

Preprint. Jan 28, 2026.

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

for every utility function that satisfies ∥U ∥∞ ≤ C, where C is constant as n → ∞ (Wang & Jia, 2023). Very often, the query complexity is determined by corner-case utility functions satisfying U (S) ∈ {C, −C} for every S. These two objective can be connected via Chebyshev’s inequality, P (∥ϕ̂ − ϕ∥2 ≥ ϵ) ≤

a Θ(n) space constraint. In this work, we will give an affirmative answer to both questions. Our theoretical contributions. As will be demonstrated later, the modified unbiased kernelSHAP turns out to be the linear-space version of OFA, and the clue is evident, as both share the same sampling distribution. Therefore, the comparison between O( ϵn2 log nδ ) and O( ϵn2 δ ) suggests that the log n factor may arise from the limitations of the perspective used. Specifically, this log n factor comes from the union bound:

E[∥ϕ̂ − ϕ∥22 ] . ϵ2

PT Suppose ϕ̂ = T1 t=1 ϕ̂t where {ϕ̂t }Tt=1 are identical (possibly not independent) unbiased estimate of ϕ. By E[∥ϕ̂−ϕ∥22 ] ≤ δ, the query complexity is given requiring ϵ2 E[∥ϕ̂ −ϕ∥2 ]

P(∥ϕ̂ − ϕ∥2 ≥ ϵ) ≤ P(

t 2 by T ≥ . To our knowledge, this is the only ϵ2 δ known regime where MSE and query complexity can be simultaneously optimized.

[ i∈[n]

ϵ |ϕ̂i − ϕi | ≥ √ ) n

ϵ ≤ n · P(|ϕ̂1 − ϕ1 | ≥ √ ), n

To obtain a log 1δ dependence rather than 1δ in the query complexity, Hoeffding-type concentration techniques are typically applied, which in turn rely on independence among {ϕ̂t }Tt=1 . In this regime, we observe that minimizing the MSE does not translate into improved query complexity, as it often introduces dependence among {ϕ̂t }Tt=1 . Surprisingly, to our knowledge, approximation algorithms designed by minimizing the MSE are not even theoretically equipped with clearly improved MSE, the difficulty of which may stem from the introduced convoluted dependence. Moreover, these algorithms come at the expense of using Θ(n2 ) space instead. As such, it remains an open question:

which leads to bounding each individual estimate ϕ̂i as a first step. This observation motivates us to consider bounding ϕ̂ as a whole, where a vector concentration inequality comes into play. Indeed, this perspective enables sharper query complexities for existing unbiased approximation algorithms. For example, the query complexity of the modified unbiased kernelSHAP will be improved to O( ϵn2 log 1δ ). Building upon this holistic perspective, we will establish a framework for approximating semi-values. As will be shown later, our framework naturally bridges several recent approaches (Li & Yu, 2024b; Fumagalli et al., 2024; Witter et al., 2025; Chen et al., 2025). Not only does our framework provide sharper query complexities for these approaches, but it also offers that:

Is it possible to provably minimize the MSE while maintaining a Θ(n) space constraint? In the last two years, the query complexities for approximating semi-values have seen significant advances. Recently, Li & Yu (2024b) introduced the one-for-all (OFA) algorithm for approximating all semi-values and proved that it achieves a query complexity of O( ϵn2 log nδ ) for all commonly used semi-values, such as Beta Shapley values (Kwon & Zou, 2022a), which include the Shapley value, and weighted Banzhaf values (Li & Yu, 2023), which include the Banzhaf value (Banzhaf III, 1965). Then, Chen et al. (2025) established a provable framework for all the kernelSHAP variants (Lundberg & Lee, 2017; Covert & Lee, 2021; Musco & Witter, 2025) and demonstrated that, by modifying the sampling distribution, the query complexity of unbiased kernelSHAP in approximating the Shapley value becomes O( ϵn2 δ ). In particular, OFA consumes Θ(n2 ) space, while the other algorithm uses Θ(n) space. Then, a natural question arises:

• For the use of paired sampling (Covert & Lee, 2021), it is theoretically established in Theorem 3.2 that the MSE is improved if E[U (S) · U ([n] \ S)] > 0; • For approximating the Shapley value, the sampling distribution used by OFA and the modified unbiased kernelSHAP is the unique optimal solution that minimizes the query complexity; • For approximating semi-values, the sampling distribution used by SHAP-IQ does not minimize the query complexity, in contrast to the one used by Witter et al. (2025) and OFA.

Can semi-values be approximated with a query complexity of O( ϵn2 log 1δ ) using only Θ(n) space?

We note that, except for OFA, these approaches only heuristically select the sampling distribution, without demonstrating whether their choices correspond to the unique optimal solution in terms of query complexity.

To meet the challenges of large-scale applications (CohenWang et al., 2024; He et al., 2024), we limit ourselves to

For the randomized algorithm established in our framework, the query complexity and the MSE are fully decoupled. 2

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

Specifically, to ensure P(∥ϕ̂ − ϕ∥ ≥ ϵ) ≤ δ, it requires ∗

Theorem 2.1 (Vector concentration inequality). Suppose {Xi }M i=1 are i.i.d. zero-mean random vectors such that E[∥Xi ∥22 ] ≤ σ 2 and ∥Xi ∥2 ≤ C almost surely. Then, for 2 every 0 < ϵ ≤ 3σ C , there is

2 4nD C log utility queries, 2 ϵ δ nD∗ E[U (S)2 ] 2 and E[∥ϕ̂ − ϕ∥2 ] = + constant. T

∗

In particular, D ∈ O(1) for Beta Shapley values and weighted Banzhaf values. Consequently, minimizing the MSE reduces to minimizing E[U (S)2 ], which is upper bounded by ∥U ∥2∞ .

1 X Xi M i=1

≥ϵ 2

M ϵ2 ≤ 2 exp − 2 . 4σ

As will be shown below, 3σ C → ∞ as n → ∞ in our context; hence, this constraint can be ignored when deriving query complexities.

Our algorithmic contributions. Another appealing property is that the distribution under E[U (S)2 ] is the same as the one used to approximate ϕ. It implies that, while approximating ϕ, we can simultaneously solve the problem

Next, we demonstrate how Theorem 2.1 enables sharper query complexities for unbiased estimates. Take AME (average marginal effect, Lin et al., 2022) as an example, whose established query complexity is O( ϵn2 log nδ ) for its unbiased variant approximating weighted Banzhaf values (Li & Yu, 2024b, Proposition 6). Note that the unbiased variant is also the unbiased counterpart for analyzing the maximum sample reuse (MSR) approach in Li & Yu (2023); Wang & Jia (2023).

minimize E[(U (S) − V (S))2 ], V ∈V

where V ∈ V satisfies ϕ(V ) = 0. This forms the foundation for the design of our adaptive, linear-time, linear-space approximation algorithm, namely Adalina in Algorithm 1, which automatically minimizes the MSE for each specific utility function U . In particular, we theoretically prove that Adalina improves the MSE while maintaining O( ϵn2 log 1δ ) query complexity, as shown in Theorem 4.1. Our theoretical findings align well with empirical results, and our adaptive randomized algorithm consistently performs well across different utility functions and semi-values.

The unbiased AME estimator for w-weighted Banzhaf value works as follows: First, we randomly sample a subset S ⊆ [n] by including each player independently with probability w (recall 0 < w < 1). Then, the random vector X ∈ Rn defined as 1 Xi = w1 U (S) · Ji ∈ SK − 1−w U (S) · Ji ̸∈ SK

2. Vector Concentration Inequality and Sharper Query Complexities

is an unbiased estimate of the w-weighted Banzhaf value ϕ. Indeed, let s = |S| be the cardinality, we verify X Ji̸∈SK − E[Xi ] = U (S)ws (1 − w)n−s · Ji∈SK w 1−w

In this section, we recall a vector concentration inequality and demonstrate its usefulness in providing sharper query complexities for unbiased estimates. For a biased estimate ϕ̂biased , such as OFA, establishing its query complexity typically involves constructing an unbiased counterpart ϕ̂unbiased , after which the analysis (implicitly) bounds ∥ϕ̂biased − ϕ̂unbiased ∥2 as an additional term. We note that all existing query complexity analyses for biased estimates proceed in this manner (Wang & Jia, 2023; Li & Yu, 2023; 2024a;b; Chen et al., 2025). As a result, the established query complexities for biased estimates are worse than those of their unbiased counterparts. Empirically, however, biased estimates can perform significantly better than its unbiased counterparts, a phenomenon that so far lacked theoretical explanation.

S⊆[n]

ws (1 − w)n−s−1 [U (S ∪ i)−U (S)] =: ϕ.

S̸∋i

To reduce variance, we average over T i.i.d. copies P AME := T1 Tt=1 Xt . Since ∥ϕ∥2 = {Xt }Tt=1 and obtain ϕ̂ nC 2 ∥E[Xt ]∥2 ≤ E[∥Xt ∥2 ] and ∥Xt ∥22 ≤ c2 := w2 ∧(1−w) 2, (assuming that U (S) ≤ C), we have ∥Xt − ϕ∥2 ≤ 2c and E[∥Xt − ϕ∥22 ] ≤ c2 . Applying Theorem 2.1, for every ϵ ≤ 23 c, we have

The following vector concentration inequality is based on Yurinsky (1995, Theorem 3.3.4); see Appendix A for a selfcontained proof. The significance of this result is that the dimension of the vectors does not appear at all, which is not the case had we applied the union bound to each coordinate (as in many previous works) or the matrix concentration bound (e.g., Tropp et al., 2015, Theorem 6.1.1).

AME

P(∥ϕ̂

T ϵ2 − ϕ∥2 ≥ ϵ) ≤ 2 exp − 2 =: δ, 4c 2

2 leading to T ≥ ϵ2 [w24nC ∧(1−w)2 ] log δ . Therefore, we have improved the query complexity of unbiased AME from O( ϵn2 log nδ ) to O( ϵn2 log 1δ ), amounting to removing a log

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

Throughout we assume ∥u∥∞ ≤ C for some constant C (that does not depend on n).

factor but more importantly revealing that unbiased AME is already a linear-time, linear-space algorithm for approximating weighted Banzhaf values.

Although developed differently, the term D(q) also appeared in the OFA (one-for-all) framework, where it is employed to optimize the associated query complexity (Li & Yu, 2024b, Theorem 1). This is not a coincidence, as our framework can be derived from OFA by reducing its space complexity to Θ(n). We refer the reader to Appendix B for more details.

Below, we will repeatedly apply Theorem 2.1 to derive complexity bounds in the same way as illustrated above.

3. Our Framework for Approximating Semi-Values We begin by rewriting the formula of semi-values in Eq. (1): X ϕ = φ + (pn u[n] − p1 u∅ )1n with φ := u S wS ,

According to Theorem 2.1, when ϵ is sufficiently small, the unbiased estimator in Eq. (3) requires at most 4nD(q)Eq̃ [u2S ] 2 2 4nC 2 D(q) log log ≤ 2 2 ϵ δ ϵ δ

∅⊊S⊊[n]

where uS := U (S) and

utility queries to ensure P(∥ϕ̂ − ϕ∥2 ≥ ϵ) ≤ δ. Clearly, D(q) is the dominant factor governing the query complexity, whereas Eq̃ [u2S ] determines the MSE. Remarkably, our framework achieves linear query complexity if D(q) ∈ O(1). Using the Cauchy-Schwartz inequality,

(wS )i := ps Ji ∈ SK − ps+1 Ji ̸∈ SK . Throughout, for a set S we use the corresponding lowercase s to denote its cardinality and the Iverson bracket JAK equals 1 if A holds and 0 otherwise. Since calculating pn u[n] − p1 u∅ costs only 2 utility evaluations, we will focus on the approximation of φ.

 D(q) ≥ 

To sample a (nonempty and proper) subset S ⊆ [n], we first sample its size s ∈ [n − 1] according to a probability vector q ∈ Rn−1 . Then, we sample S uniformly from all subsets with size s. Given a sequence of such sampled subsets {St }Tt=1 , we form an unbiased estimate of ϕ: ϕ̂ =

T 1X

T t=1 qs

uSt wSt + (pn u[n] − p1 u∅ )1n . n −1

n·

s=1

 2 m2s+1  =: D∗ , + s n−s

m2s

(4)

where the equality is achieved if and only if s qs = qs∗ ∝

(2)

Pn Let ms = n−1 s=1 ms = 1 according to s−1 ps so that Eq. (1). Then, we have n n ms ms+1 s (zS )i := (wS )i = Ji ∈ SK − Ji ̸∈ SK . qs qs s n−s Consequently, T

1X ϕ̂ = uS zS + (mn u[n] − m1 u∅ )1n , T t=1 t t

n−1 X

(3)

n·

m2 m2s + s+1 . s n−s

(5)

In particular, D∗ ∈ O(1) for all Beta Shapley values and weighted Banzhaf values, which was already proved by Li & Yu (2024b, Proposition 4). √

∗

Theorem 3.1. Setting q = q∗ , for every ϵ ≤ 3C 2nD , there is T ϵ2 P(∥ϕ̂ − ϕ∥2 ≥ ϵ) ≤ 2 exp − 4nD∗ C 2 ∗ 2 nD E[uS ] − ∥φ∥22 , and E[∥ϕ̂ − ϕ∥22 ] = T −1 X n where E[u2S ] = qs∗ u2S . s ∅⊊S⊊[n]

whence Theorem 2.1 applies. To analyze its query complexity, we note that

In particular, ∥zS ∥22 = nD∗ for every ∅ ⊊ S ⊊ [n].

−1 2 2 m2s+1 n n ms qs + u2S qs2 s n−s s

It is worth pointing out that, in Theorem 3.1, the optimal distribution q∗ defined in Eq. (5) uniquely satisfies two ∅⊊S⊊[n] properties, namely that the expectation E[u2S ] is taken with = n · D(q) · Eq̃ [u2S ] ≤ n · D(q) · C 2 , where respect to the same distribution used to approximate ϕ. and that ∥z ∥2 = nD∗ for every S. These properties form n−1 X n m2 S 2 m2s+1 m2s+1 n m2s s q̃s ∝ + , D(q) := + . the foundation for designing our adaptive randomized algoqs s n−s q s n−s s=1 s rithms with provably improved MSE. E[∥uS zS ∥22 ] =

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

102

#utility queries per player

101

102

#utility queries per player

103

spambase (n = 57)

101

kernel leverage modified

10 1

103

kernel leverage modified

101

102

#utility queries per player

103

kernel leverage modified

103

102

#utility queries per player

103

101

FOTP (n = 51)

101

102

#utility queries per player

103

kernel leverage modified

10 1

10 1 101

kernel leverage modified

10 1

102

#utility queries per player

kernel leverage modified

10 1

101

10 1

100

kernel leverage modified

10 1

100

2 2/

kernel leverage modified

100

102

#utility queries per player

103

MinibooNE (n = 50)

101

102

#utility queries per player

103

philippine (n = 308)

Figure 1. The relative approximation error of unbiased kernelSHAP in approximating the Shapley value with different sampling u −u distributions. Here, λ = [n]n ∅ . The dashed lines correspond to those with paired sampling, whereas the solid lines are without paired sampling. For the first row, the utility function there is positive, whereas for the second row, U (S) can be either positive or negative.

Paired sampling. Paired sampling has become a common tool in improving the approximation quality of kernelSHAP (Covert & Lee, 2021). Empirically, however, it does not always yield performance gains (Li & Yu, 2024a), making its effectiveness somewhat mysterious. Nevertheless, our framework offers a definitive characterization. Paired sampling is specific to symmetric semi-values satisfying pn−s+1 = ps for every s ∈ [n], which include the Shapley value and the Banzhaf value (Banzhaf III, 1965). Instead of sampling subsets independently, paired sampling inserts the complement of each sampled subset immediately after it.

q 1 framework is qs ∝ s(n−s) , as defined in Eq. (5). Very recently, Chen et al. (2025) established a provable framework that unifies all kernelSHAP variants to approximate the Shapley value. In particular, their unified formula for unbiased kernelSHAP can be simplified as

Theorem 3.2. Let T be the total number of utility queries, accounting for the fact that each sampled subset incurs 2 utility queries under paired sampling. Then, when qs = qn−s for every s ∈ [n − 1], The use of paired sampling c c := technique reduces to approximating U −U 2 , where U (S) U ([n] \ S). In particular,

Lemma 3.3. For the Shapley value, let V be any utility function such that V (S) = f (s) for every S. Then E[vS zS ] = 0n , where vS = V (S).

ϕ̂

kernel

U ([n]) − U (∅) 1X (uSt − λ · st )zSt + 1n . T t=1 n

Here, λ ∈ R is arbitrary. Within our framework, the arbitrariness of λ can be directly generalized.

As a result, λ · st in unbiased kernelSHAP can be replaced by f (st ). For the vanilla unbiased KernelSHAP (Covert & Lee, 2021), 1 the sampling distribution satisfies qs ∝ s(n−s) with λ = 0, 1 whereas the leverage score sampling uses qs = n−1 and

nD(q)σq̃2 − 2∥φ∥22 , T where σq̃2 := Eq̃ [u2S ] − Eq̃ [uS · u[n]\S ] E[∥ϕ̂ − ϕ∥22 ] =

(∅) λ = U ([n])−U (Musco & Witter, 2025). Subsequently, n Chen et al. (2025) propose a modified variant by setting q to the geometric mean of these two distributions, which coincides with q∗ . Therefore, by Theorem 2.1, the query complexity of the modified unbiased kernelSHAP is already O( ϵn2 log 1δ ). By contrast, the other two methods incur an additional multiplicative factor of log n.

∗ Note that for q∗ in Eq. (5), indeed qs∗ = qn−s for all s. We conclude that paired sampling improves the approximation variance if Eq̃ [uS · u[n]\S ] > 0, which holds whenever U does not change sign. As shown in Figure 1, Theorem 3.2 exactly predicts when paired sampling boosts the approximation. In particular, when Eq̃ [uS · u[n]\S ] > 0 is not satisfied, paired sampling can even degrade performance.

Corollary 3.4. To ensure P(∥ϕ̂ − ϕ∥2 ≥ ϵ) ≤ δ, the unbiased kernelSHAP using leverage score sampling re2 quires at most 72C ϵn2 log n log 2δ utility queries for ϵ ≤ 4C log n, whereas the vanilla unbiased kernelSHAP re2 1 quires 8C nϵ2log n log 2δ for ϵ ≤ Cn 2 . In other words, their n query complexities are both O( n log log 1δ ). ϵ2

Next, we demonstrate how our framework bridges the existing approaches. More details can be found in Appendix B. Unbiased KernelSHAP. For the Shapley value, ms = n1 for every s and the optimal sampling distribution of our 5

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

0.15

u[n] u

0.10 2

spambase (n = 57)

2 2/

0.20

u[n] u 1

FOTP (n = 51)

0.33 0.30 0.28 0.25 0.23 0.20 0.17 0.15

0.55 0.50 0.45 0.40 0.35 0.30 0.25

0.50 0.45 0.40 0.35 0.30 0.25 0.20 0.15

0.25

u[n] u 2

MinibooNE (n = 50)

u[n] u 2

philippine (n = 308)

Figure 2. The relative approximation error of ϕ̂ in approximating the Shapley value as γ varies.

Algorithm 1 Adalina (Adaptive Linear Approximation) Input: Weight vector m ∈ Rn for semi-value ϕ, total number of samples T

This suggests that the modified unbiased KernelSHAP is superior in terms of query complexity. Remark. We notice that Chen et al. (2025, Proposition E.1) constructed a specific utility function to show that the modified unbiased kernelSHAP could behave worse √ by a multiplicative factor of n compared to the variant using leverage score sampling. This does not contradict our Corollary 3.4, since their constructed U satisfies ∥U ∥∞ ∈ Θ(n) while we assume ∥U ∥∞ ≤ C.

Adalina

Output: Estimate ϕ̂ n−1 1 Compute the sampling distribution q ∈ R such that q 2 2 ms+1 ms qs ∝ s + n−s 2 Initialize φ̂, v̂ ← 0n , γ̂ ← 0 3 for t = 1, 2, . . . , T do 4 Sample a subset size s with probability qs 5 Sample a subset S of size s uniformly from 2[n] SHAP-IQ. As a weighted extension of kernelSHAP for φ̂ ← (1 − 1t ) · φ̂ + 1t · uS zS approximating semi-values (Fumagalli et al., 2024), the 6 7 v̂ ← (1 − 1t ) · v̂ + 1t · zS estimate of SHAP-IQ can be rewritten as: 8 γ̂ ← (1 − 1t ) · γ̂ + 1t · uS T Adalina IQ 1X 9 ϕ̂ ← φ̂ − γ̂ v̂ + mn (u[n] − γ̂) − m1 (u∅ − γ̂) (uSt − u∅ )zSt + mn · (u[n] − u∅ ) ϕ̂ := T t=1

1 . It also fits into with the sampling distribution qs ∝ s(n−s) our framework, by simply translating {uS }S to {uS − u∅ }S . Therefore, as indicated by Eq. (4), the choice of q in SHAPIQ does not minimize the query complexity.

where the convention here is x0 := 0. The difference is that they include [n] and ∅ in the sampling pool, whereas we exclude them. In particular, Theorem 3.1 continues to hold when using qMSR (see Appendix B), indicating that a linear-time, linear-space randomized algorithm already exists for approximating semi-values.

Regression-adjusted approach. Recently, Witter et al. (2025) propose learning a utility function V , whose semivalues can be computed in polynomial time, by minimizing

4. Our Adaptive Randomized Algorithms for Approximating Semi-Values

MSR

E[∥ϕ̂ (U − V )∥22 ]. The regression-adjusted estimate is then computed as adjusted

ϕ̂

(U ) := ϕ̂

MSR

In this section, by applying the well-known control variates technique, we show that there is still room for improving the existing linear-time, linear-space randomized algorithms through minimizing the MSE. From now on, we assume q∗ is employed, as it optimizes the query complexity.

(U − V ) + ϕ(V ).

Clearly, this approach aims to minimize the MSE. Adopting the maximum-sample-reuse (MSR) perspective with q ∈ Rn+1 unspecified, Witter et al. (2025) derive an exact expression for E[∥ϕ̂(U − V )∥22 ]. They then heuristically choose q so that no reweighting scheme is required to approximate this quantity. Notably, this choice coincides with the optimal solution for minimizing the query complexity. Specifically, the choice of their qM SR ∈ Rn+1 can be simplified as s m2s+1 m2s q MSR ∝ + for every 0 ≤ s ≤ n, s s n−s

Since ϕ(U ) = 0n if U is constant, we immediately have the following unbiased estimate for ϕ, γ

ϕ̂ :=

1X (uSt − γ)zSt + b T t=1

where b := [mn (u[n] − γ) − m1 (u∅ − γ)]1n . Observe that this reduces to SHAP-IQ when qs ∝ 1/s(n − s) and γ = u∅ . If m1 = mn , which is satisfied by symmetric semi-values, 6

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

2 2 2/

2 2/

2 2 2/

(4, 16)

Beta Shapley values

(8, 8)

(2, 2)

(16, 4)

(1, 16)

(1, 4)

(1, 1)

10 1

(4, 1)

=u = u[n] 2+ u adaptive SHAP-IQ

(16, 1)

(4, 16)

Beta Shapley values

(8, 8)

(2, 2)

(16, 4)

=u = u[n] 2+ u adaptive SHAP-IQ

10 1

(1, 16)

(1, 4)

(1, 1)

10 1

(4, 1)

(16, 1)

=u = u[n] 2+ u adaptive SHAP-IQ

10 1

=u = u[n] 2+ u adaptive SHAP-IQ

10 1

(4, 16)

Beta Shapley values

(8, 8)

(2, 2)

(16, 4)

(1, 16)

(1, 4)

(1, 1)

(4, 1)

=u = u[n] 2+ u adaptive SHAP-IQ

(16, 1)

(4, 16)

(8, 8)

(2, 2)

(16, 4)

(1, 16)

(1, 4)

(1, 1)

(4, 1)

(16, 1) 10 1

Beta Shapley values

10 1

=u = u[n] 2+ u adaptive SHAP-IQ

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

spambase (n = 57)

FOTP (n = 51)

MinibooNE (n = 50)

philippine (n = 308)

Weighted Banzhaf values

Figure 3. The relative approximation error of SHAP-IQ, ϕ̂ and its adaptive variant. The adaptive method corresponds to Adalina, presented in Algorithm 1, which adaptively estimates the optimal γ. Weighted Banzhaf values are parameterized by w ∈ (0, 1), whereas Beta Shapley values are parameterized by (α, β), with (1, 1) corresponding to the Shapley value.

As the baseline, E[∥ϕ̂ − ϕ∥22 ] = T1 nD∗ E[u2S ] − ∥φ∥22 , which is stated in Theorem 3.1. It follows that the MSE of Adalina γ∗ is fast approaching that of ϕ̂ as T → ∞; see ϕ̂ Figure 3 for its performance.

then by Theorem 3.1, γ

E[∥ϕ̂ − ϕ∥22 ] =

nD∗ E[(uS − γ)2 ] − ∥φ∥22 . T

This indicates that γ adjusts the MSE. Empirically, this is confirmed in Figure 2. In particular, the shapes of the curves align well with E[(uS − γ)2 ], indicating that there exists a unique optimal γ ∗ that minimizes it. Theoretically, γ ∗ = E[uS ]. By Theorem 3.1, the distribution underlying E[u2S ] is the same as that used to approximate ϕ, which means we can approximate γ ∗ and ϕ simultaneously. This leads to our adaptive randomized algorithm, Adalina, for approximating semi-values: ϕ̂

Adalina

We note that our proof relies on the condition E[zS ] = 0n , which clearly holds when m1 = mn according to Eq. (6). This assumption can be immediately removed if q MSR is used instead, since ϕ(U ) = 0n whenever U is constant. In this case, Theorems 3.1 and 4.1 remain valid with ∥φ∥22 and D∗ replaced by ∥ϕ∥22 and DMSR , respectively. Further details are provided in Appendix B, with the corresponding procedure summarized in Algorithm 2 (Adalina-All).

5. Empirical Results

1X (uSt − γ̂)zSt + b̂, T t=1

In this section, we examine the performance of our adaptive randomized algorithm, Adalina and its variant Adalina-All.

where b̂ := [mn (u[n] − γ̂) − m1 (u∅ − γ̂)]1n and γ̂ := PT 1 t=1 uSt . Its procedure is summarized in Algorithm 1. T Note that Adalina consumes Θ(n) space. In particular, it comes with the following improved MSE.

Baselines. Since our focus is on the approximation quality of Θ(n)-space randomized algorithms, the baselines we consider include: MSR-Banzhaf (Wang & Jia, 2023), MSR

MSR-Prob (see ϕ̂ in Appendix B.4), SHAP-IQ (Fumagalli et al., 2024), unbiased kernelSHAP (Chen et al., 2025), AME (Lin et al., 2022), ARM (Kolpaczki et al., 2024), and GELS and GELS-Shapley (Li & Yu, 2024a). In particular, while the original AME requires Θ(n2 ) space and an additional O(n3 ) time for matrix inversion, we instead use its linear-space variant provided in Li & Yu (2024b). Among these baselines, MSR-Banzhaf can only approximate weighted Banzhaf values, whereas unbiased kernelSHAP and GELS-Shapley are designed specifically for approximating the Shapley value. All the others can approximate a wide range of semi-values.

Theorem 4.1. For semi-values satisfying m1 = mn , which include the Shapley value and the Banzhaf value, we have Adalina

E[∥ϕ̂

− ϕ∥22 ]

6nD∗ ∥U ∥2∞ 1 nD∗ E[(uS − γ ∗ )2 ] − ∥φ∥22 + T T (T − 1) ∗ 2 ∗ γ 6nD ∥U ∥∞ = E[∥ϕ̂ − ϕ∥22 ] + . T (T − 1) ≤

Meanwhile, the query complexity of ϕ̂ for semi-values with D∗ ∈ O(1).

Adalina

is O( ϵn2 log 1δ )

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

Adalina (ours) Adalina-All (ours)

0.04 0.02 0.00 0.02 0.04

SHAP-IQ kernelSHAP

AME ARM

GELS GELS-Shapley

MSR-Banzhaf MSR-Prob

0.04

0.02

0.00

0.02

0.04

10 1

2 2/

(4, 16)

Beta Shapley values

(8, 8)

(2, 2)

(16, 4)

(1, 16)

(1, 4)

(1, 1)

10 1

(4, 1)

(16, 1)

(4, 16)

Beta Shapley values

(8, 8)

(2, 2)

(16, 4)

(1, 16)

(1, 4)

(1, 1)

(4, 1)

10 1

(16, 1)

(4, 16)

(8, 8)

(2, 2)

(16, 4)

(1, 16)

(1, 4)

(1, 1)

(4, 1)

(16, 1)

Beta Shapley values

10 1

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

spambase (n = 57)

FOTP (n = 51)

MinibooNE (n = 50)

Weighted Banzhaf values

Figure 4. The relative approximation error of different randomized algorithms. Weighted Banzhaf values are parameterized by w ∈ (0, 1), whereas Beta Shapley values are parameterized by (α, β), with (1, 1) corresponding to the Shapley value.

the Beta Shapley value with parameter (1, 1), our Adalina performs consistently well. Although Adalina does not improve the MSE for non-symmetric semi-values, its estimates closely match those of Adalina-All, which theoretically achieves improved MSE for all semi-values. For the Shapley value, unbiased kernelSHAP can be significantly better, suggesting the possibility that inf λ∈R E[(uS − λ · s)2 ] < inf γ∈R E[(uS − γ)2 ] and indicating that there is still more room to better approximate the Shapley value. In particular, Lemma 3.3 suggests a path for future work.

Utility functions. Each utility function is defined using a trained (gradient boosting) decision tree f and an instance x ∈ Rn . Specifically, Ufx (S) := EX[n]\S [f (xS , X[n]\S )]. Therefore, the number of players is equal to the number of features. We follow the path-dependent definition given in Lundberg et al. (2020, Algorithm 1). In particular, while the semi-values of Ufx can be computed in polynomial time (Muschalik et al., 2024), providing ground-truths for evaluating the performance of different randomized algorithms. We employ six datasets from OpenML for training (gradient boosting) decision trees, which are (1) spambase (n = 57), (2) FOTP (n = 51) (Bridge et al., 2014), (3) MinibooNE (n = 50) (Roe et al., 2005), (4) philippine (n = 308), (5) GPSP (n = 32) (Madeo et al., 2013), and (6) supperconduct (n = 81). All gradient boosting decision trees are trained using GradientBoostingClassifier and GradientBoostingRegressor from the scikit-learn library (Pedregosa et al., 2011) with the number of trees set to 5. An exception is that we use DecisionTreeClassifier to produce positive utility functions to verify Theorem 3.2 in Figure 1.

6. Conclusion In this work, we adopt a holistic perspective to systematically establish a theoretical framework for designing linear-time, linear-space randomized algorithms that approximate semi-values. Our framework bridges the recent works, including OFA, unbiased kernelSHAP, SHAP-IQ and the regression-adjust approach, and provides sharper query complexities. It also characterizes when paired sampling boosts performance, which is empirically verified in Figure 1. In particular, our work enables the explicit minimization of the MSE for each utility function, through which we propose the first adaptive randomized algorithm, Adalina, with provably improved MSE. Empirically, Adalina consistently performs well against baselines. We view our framework as the first concrete step towards designing more efficient adaptive randomized algorithms for semi-value estimation.

Each estimate is computed using 1, 000 queries per player. For example, if n = 10, each estimate is computed using 10, 000 queries. All results are averaged over 10 random seeds, with the standard deviation reported. For reproducibility, all other sources of randomness are fixed to 2026. More details and experimental results are in Appendix C. As presented in Figure 4, except for the Shapley value, i.e., 8

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

References

Conference on Machine Learning, pp. 2242–2251, 2019. URL https://proceedings.mlr.press/v97/ ghorbani19c.

Banzhaf III, J. F. Weighted voting doesn’t work: A mathematical analysis. Rutgers Law Review, 19(2):317–343, 1965. Bridge, J. P., Holden, S. B., and Paulson, L. C. Machine learning for first-order theorem proving: learning to select a good heuristic. Journal of automated reasoning, 53: 141–172, 2014.

He, Y., Wang, Z., Shen, Z., Sun, G., Dai, Y., Wu, Y., Wang, H., and Li, A. SHED: Shapley-based automated dataset refinement for instruction fine-tuning. In The Thirtyeighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview. net/forum?id=Gqou8PRgWq.

Castro, J., Gómez, D., Molina, E., and Tejada, J. Improving polynomial estimation of the Shapley value by stratified random sampling with optimum allocation. Computers & Operations Research, 82:180–188, 2017. URL https: //doi.org/10.1016/j.cor.2017.01.019.

Ilyas, A., Park, S. M., Engstrom, L., Leclerc, G., and Madry, A. Datamodels: Predicting predictions from training data. In Proceedings of the 39th International Conference on Machine Learning, 2022. URL https: //proceedings.mlr.press/v162/ilyas22a.

Chen, T., Seshadri, A., Villani, M. J., Niroula, P., Chakrabarti, S., Ray, A., Deshpande, P., Yalovetzky, R., Pistoia, M., and Kumar, N. A unified framework for provably efficient algorithms to estimate Shapley values. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. URL https: //openreview.net/forum?id=KQLCim1NhT.

Jia, R., Dao, D., Wang, B., Hubis, F. A., Hynes, N., Gürel, N. M., Li, B., Zhang, C., Song, D., and Spanos, C. J. Towards efficient data valuation based on the Shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1167–1176, 2019. URL https://proceedings.mlr.press/v89/ jia19a.html.

Cohen-Wang, B., Shah, H., Georgiev, K., and Madry, A. Contextcite: Attributing model generation to context. Advances in Neural Information Processing Systems, 37: 95764–95807, 2024. URL https://dl.acm.org/ doi/10.5555/3737916.3740951.

Kolpaczki, P., Bengs, V., Muschalik, M., and Hüllermeier, E. Approximating the Shapley value without marginal contributions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 13246–13255, 2024. URL https://doi.org/10.1609/aaai. v38i12.29225.

Covert, I. and Lee, S.-I. Improving KernelSHAP: Practical Shapley value estimation using linear regression. In International Conference on Artificial Intelligence and Statistics, pp. 3457–3465, 2021. URL https:// proceedings.mlr.press/v130/covert21a.

Kwon, Y. and Zou, J. Y. Beta Shapley: a unified and noisereduced data valuation framework for machine learning. In International Conference on Artificial Intelligence and Statistics, pp. 8780–8802, 2022a. URL https: //proceedings.mlr.press/v151/kwon22a.

Deng, J., Hu, Y., Hu, P., Li, T.-W., Liu, S., Wang, J. T., Ley, D., Dai, Q., Huang, B., Huang, J., et al. A survey of data attribution: Methods, applications, and evaluation in the era of generative AI. HAL Id: hal05230469, 2025. URL https://dx.doi.org/10. 2139/ssrn.5451054.

Kwon, Y. and Zou, J. Y. WeightedSHAP: Analyzing and improving Shapley based feature attributions. In Advances in Neural Information Processing Systems, volume 35, pp. 34363–34376, 2022b. URL https: //openreview.net/forum?id=u359tNBpxF.

Dubey, P., Neyman, A., and Weber, R. J. Value theory without efficiency. Mathematics of Operations Research, 6(1): 122–128, 1981. URL https://www.jstor.org/ stable/3689271.

Li, W. and Yu, Y. Robust data valuation with weighted Banzhaf values. In Advances in Neural Information Processing Systems, volume 36, 2023. URL https: //openreview.net/forum?id=u359tNBpxF.

Fumagalli, F., Muschalik, M., Kolpaczki, P., Hüllermeier, E., and Hammer, B. SHAP-IQ: Unified approximation of any-order Shapley interactions. In Advances in Neural Information Processing Systems, volume 36, 2024. URL https://openreview.net/forum? id=IEMLNF4gK4&noteId=pL6cYtCk7N.

Li, W. and Yu, Y. Faster approximation of probabilistic and distributional values via least squares. In The Twelfth International Conference on Learning Representations, 2024a. URL https://openreview.net/forum? id=lvSMIsztka. Li, W. and Yu, Y. One sample fits all: Approximating all probabilistic values simultaneously and efficiently. Advances in Neural Information Processing Systems, 37:

Ghorbani, A. and Zou, J. Y. Data Shapley: Equitable valuation of data for machine learning. In International 9

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

58309–58340, 2024b. URL https://openreview. net/forum?id=AUg9D2VjcF. Lin, J., Zhang, A., Lécuyer, M., Li, J., Panda, A., and Sen, S. Measuring the effect of training data on deep learning predictions via randomized experiments. In International Conference on Machine Learning, pp. 13468– 13504, 2022. URL https://proceedings.mlr. press/v162/lin22h.html.

in machine learning. In The 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence, pp. 5572– 5579, 2022. URL https://doi.org/10.24963/ ijcai.2022/778. Shapley, L. S. A value for n-person games. Annals of Mathematics Studies, 28:307–317, 1953. URL https: //doi.org/10.1515/9781400881970-018. Tropp, J. A. et al. An introduction to matrix concentration inequalities. Foundations and Trends® in Machine Learning, 8(1-2):1–230, 2015. URL https: //doi.org/10.1561/2200000048.

Lundberg, S. M. and Lee, S.-I. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems, volume 30, 2017. URL https://dl.acm.org/doi/ 10.5555/3295222.3295230.

Wang, J. T. and Jia, R. Data Banzhaf: A robust data valuation framework for machine learning. In International Conference on Artificial Intelligence and Statistics, pp. 6388–6421, 2023. URL https://proceedings. mlr.press/v206/wang23e.

Lundberg, S. M., Erion, G., Chen, H., DeGrave, A., Prutkin, J. M., Nair, B., Katz, R., Himmelfarb, J., Bansal, N., and Lee, S.-I. From local explanations to global understanding with explainable AI for trees. Nature machine intelligence, 2(1):56–67, 2020. URL https: //doi.org/10.1038/s42256-019-0138-9.

Witter, R. T., Liu, Y., and Musco, C. Regression-adjusted monte carlo estimators for Shapley values and probabilistic values. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. URL https: //openreview.net/forum?id=Qabko39AS5.

Madeo, R. C., Lima, C. A., and Peres, S. M. Gesture unit segmentation using support vector machines: segmenting gestures from rest positions. In Proceedings of the 28th Annual ACM Symposium on Applied Computing, pp. 46– 52, 2013.

Wu, M., Jia, R., Lin, C., Huang, W., and Chang, X. Variance reduced Shapley value estimation for trustworthy data valuation. Computers & Operations Research, 159: 106305, 2023. URL https://doi.org/10.1016/ j.cor.2023.106305.

Muschalik, M., Fumagalli, F., Hammer, B., and Hüllermeier, E. Beyond treeshap: Efficient computation of any-order shapley interactions for tree ensembles. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 14388–14396, 2024. URL https: //doi.org/10.1609/aaai.v38i13.29352.

Yurinsky, V. Sums and Gaussian vectors. Springer, 1995. URL https://link.springer.com/book/10. 1007/BFb0092599.

Musco, C. and Witter, R. T. Provably accurate Shapley value estimation via leverage score sampling. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum? id=wg3rBImn3O.

Zhang, J., Sun, Q., Liu, J., Xiong, L., Pei, J., and Ren, K. Efficient sampling approaches to Shapley value approximation. Proceedings of the ACM on Management of Data, 1(1):1–24, 2023. URL https://doi.org/10. 1145/3588728.

Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al. Scikit-learn: Machine learning in python. Journal of machine learning research, 12(Oct):2825–2830, 2011. Roe, B. P., Yang, H.-J., Zhu, J., Liu, Y., Stancu, I., and McGregor, G. Boosted decision trees as an alternative to artificial neural networks for particle identification. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, 543(2-3):577–584, 2005. Rozemberczki, B., Watson, L., Bayer, P., Yang, H.-T., Kiss, O., Nilsson, S., and Sarkar, R. The Shapley value 10

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

A. Proofs Theorem A.1 (Yurinsky, 1995, Theorem 3.3.4). Let S = vectors. Then, for every λ > 0, M Y

E[cosh(λ∥S∥2 )] ≤

M i=1 Xi where {Xi }i=1 are independent zero-mean random

E[exp(λ∥Xi ∥2 ) − λ∥Xi ∥2 ].

i=1

Proof. By Taylor expansion (and the monotone convergence theorem), E[cosh(λ∥S∥2 )] =

∞ X λ2ℓ ℓ=0

(2ℓ)!

E[∥S∥2ℓ 2 ].

We begin by bounding each moment E[∥S∥2ℓ 2 ]. Expanding the square Euclidean norm we have X

ℓ

∥S∥2ℓ 2 = ⟨S, S⟩ =

ℓ Y

⟨XI(k) , XJ(k) ⟩,

I∈[M ][ℓ] J∈[M ][ℓ] k=1

where [M ] := {1, 2, . . . , M }. For every (I, J) and i ∈ [M ], define κi (I, J) :=

ℓ X k=1

(JI(k) = iK + JJ(k) = iK) .

Then, since {Xi }M i=1 are zero-mean, we have " ℓ # Y E ⟨XI(k) , XJ(k) ⟩ = 0 if κi (I, J) = 1 for some i ∈ [M ]. k=1

For the other cases, E

" ℓ Y

# ⟨XI(k) , XJ(k) ⟩ ≤ E

k=1

" ℓ Y

# ∥XI(k) ∥2 · ∥XJ(k) ∥2

"M Y

Kℓ := {κ = (κi ) ∈ ZM + |

M X

i=1

k=1

Let

# κ (I,J) ∥Xi ∥2 i

κi = 2ℓ and κi ̸= 1 for every i ∈ [M ]}.

i=1

Then, rearranging the sum and applying the above inequality, we have X ≤ E ∥S∥2ℓ 2

κ∈Kℓ (I,J) : κ(I,J)=κ

"M Y

# ∥Xi ∥κ2 i

i=1

For each κ ∈ Kℓ , there are 2ℓ entries in (I, J) to be determined, with the constraint that κi entries are chosen to be i ∈ [M ]. It follows that (2ℓ)! |{(I, J) : κ(I, J) = κ}| = QM . i=1 κi ! Consequently, "M # M X Y ∥Xi ∥κi X Y E[∥Xi ∥κ2 i ] 2ℓ 2 E ∥S∥2 ≤ (2ℓ)!E = (2ℓ)! , κi ! κi ! i=1 i=1 κ∈Kℓ

κ∈Kℓ

where the equality comes from the independence among {Xi }M i=1 . As a result, E[cosh(λ∥S∥2 )] ≤

∞ X Y M X λκi E[∥Xi ∥κi ] 2

ℓ=0 κ∈Kℓ i=1

κi !

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

Since

∞ [

Kℓ ⊆ (Z+ \ {1})M ,

ℓ=0

we eventually have X

E[cosh(λ∥S∥2 )] ≤

κ1 ̸=1

···

M X Y λκi E[∥Xi ∥κi ] 2

κM ̸=1 i=1

κi !

M X κi Y λ E[∥Xi ∥κi ] 2

i=1 κi ̸=1

κi !

M Y

E[exp(λ∥Xi ∥2 ) − λ∥Xi ∥2 ],

i=1

which completes the proof. 2 Theorem 2.1 (Vector concentration inequality). Suppose {Xi }M i=1 are i.i.d. zero-mean random vectors such that E[∥Xi ∥2 ] ≤ 3σ 2 2 σ and ∥Xi ∥2 ≤ C almost surely. Then, for every 0 < ϵ ≤ C , there is ! M 1 X M ϵ2 P Xi ≥ ϵ ≤ 2 exp − 2 . M i=1 4σ 2

Proof. The proof presented here is routine in establishing Bernstein’s inequality. Let S := begin by applying Markov’s inequality to obtain P (∥S∥2 ≥ ϵ) = P (cosh(λ∥S∥2 ) ≥ cosh(λϵ)) ≤

i=1 Xi and λ > 0, and we

E[cosh(λ∥S∥2 )] . cosh(λϵ)

Then, by Theorem A.1, M

E[cosh(λ∥S∥2 )] ≤ (E [exp (λ∥Xi ∥2 − λ∥Xi ∥2 )])

x Introducing the non-decreasing and non-negative function h(x) := e −1−x , x2

E[exp(λ∥Xi ∥2 ) − λ∥Xi ∥2 ] = 1 + E[λ2 ∥Xi ∥22 · h(λ∥Xi ∥2 )] ≤ 1 + λ2 σ 2 · h(λC). We continue to bound h by Taylor expansion (and the simple fact that k! ≥ 1 · 2 · 3k−2 ): k ∞ ∞ ∞ X (λC)k−2 1 X (λC)k−2 1 X λC ≤ = . h(λC) = k! 2 3k−2 2 3 k=2

k=2

k=0

If λ < C3 , by combining the previous two inequalities, we have λ2 σ 2 ≤ exp E[exp(λ∥Xi ∥2 ) − λ∥Xi ∥2 ] ≤ 1 + 2(1 − C3 λ)

λ2 σ 2 2(1 − C3 λ)

! ,

where the last inequality comes from 1 + x ≤ ex . As a result, E[cosh(λ∥S∥2 )] ≤ exp

M λ2 σ 2 2(1 − C3 λ)

! .

Since cosh(x) ≥ e2 , P(∥S∥2 ≥ ϵ) ≤ 2 exp

! M λ2 σ 2 − λϵ . 2(1 − C3 λ)

Putting λ = M σ2ϵ+ C ϵ , which meets the constraint λ < C3 , we have 3

! ϵ2 P(∥S∥2 ≥ ϵ) ≤ 2 exp − , 2(M σ 2 + C3 ϵ) PM 1 M ϵ2 C 3σ 2 2 which is equivalent to P(∥ M i=1 Xi ∥2 ≥ ϵ) ≤ 2 exp − 2(σ 2 + C ϵ) . If 3 ϵ ≤ σ , which is equivalent to ϵ ≤ C , the 3 result follows. 12

Provably Adaptive Linear Approximation for the Shapley Value and Beyond √

∗

Theorem 3.1. Setting q = q∗ , for every ϵ ≤ 3C 2nD , there is T ϵ2 P(∥ϕ̂ − ϕ∥2 ≥ ϵ) ≤ 2 exp − 4nD∗ C 2 ∗ 2 nD E[uS ] − ∥φ∥22 and E[∥ϕ̂ − ϕ∥22 ] = , T −1 X n where E[u2S ] = qs∗ u2S . s

∅⊊S⊊[n]

In particular, ∥zS ∥22 = nD∗ for every ∅ ⊊ S ⊊ [n]. Proof. Recall that D(q) =

Pn−1 n m2s s=1 qs

m2s+1 + n−s

. Let A :=

r m2s+1 m2s n + s=1 s n−s . Then, the unique optimal choice

Pn−1

of q can be written as qs = qs∗ :=

1 A

s m2 m2s n + s+1 . s n−s

In particular, s m2 m2s n + s+1 = A2 . D∗ = A · s n−s s=1 n−1 X

For any zS , n2 ∥zS ∥22 = 2 qs

m2 m2s + s+1 s n−s

= n · A2 = n · D ∗ .

Therefore, we have X

E[∥uS zS − φ∥22 ] = E[∥uS zS ∥22 ] − ∥φ∥22 ≤ E[∥uS zS ∥22 ] = n · D∗ ·

∅⊊S⊊[n]

−1 n u2S s

√

and ∥uS zS − φ∥2 ≤ ∥uS zS ∥2 + E[∥uS zS ∥2 ] ≤ 2C nD∗ . Invoking Theorem 2.1 yields the desired result. Theorem 3.2. Let T be the total number of utility queries, accounting for the fact that each sampled subset incurs 2 utility queries under paired sampling. Then, when qs = qn−s for every s ∈ [n − 1], The use of paired sampling technique reduces c c := U ([n] \ S). In particular, to approximating U −U 2 , where U (S) E[∥ϕ̂ − ϕ∥22 ] =

nD(q)σq̃2 − 2∥φ∥22 , T

where σq̃2 := Eq̃ [u2S ] − Eq̃ [uS · u[n]\S ] Proof. Recall that ps = pn+1−s for every s ∈ [n] if ϕ corresponds to a symmetric semi-value. As a result, we have ms = mn+1−s for every s ∈ [n]. Let T be the total number of utility queries. Then, after sampling T2 subsets R1 , R2 , . . . , R T , the sequence of subsets used 2

to compute ϕ̂ is S1 = R1 , S2 = [n] \ R1 , S3 = R2 , S4 = [n] \ S3 , . . . , ST −1 = R T , ST = [n] \ R T . 2

Recall that the estimate is computed as φ̂ =

t=1 uSt zSt , which can be rewritten as T

2 2X 1 φ̂ = uRt zRt + u[n]\Rt z[n]\Rt . T t=1 2

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

Specifically,

uRt − u[n]\Rt 1 uRt zRt + u[n]\Rt z[n]\Rt = · z Rt . 2 2 For symmetric semi-values, we have uS − u[n]\S φ+φ E · zS = = φ. 2 2 Then, u −u (u −u )2 2 E[∥ S 2[n]\S · zS ∥22 ] − ∥φ∥22 n · D(q) · Eq̃ [ S 2[n]\S ] − 2∥φ∥22 2 = . E[∥ϕ̂ − ϕ∥2 ] = T T Since Eq̃ [u2S ] = Eq̃ [u2[n]\S ], (uS − u[n]\S )2 Eq̃ = Eq̃ [u2S ] − Eq̃ [uS · u[n]\S ]. 2 Lemma 3.3. For the Shapley value, let V be any utility function such that V (S) = f (s) for every S. Then E[vS zS ] = 0n , where vS = V (S). Proof. Observe that E[vS zS ] = WT v. where wS is the S-th column of WT . For the Shapley value, ( 1 n−1 −1 , s−1 n WS,i = 1 n−1 −1 −n s ,

i ∈ S, otherwise.

Specifically, (WT v)i =

1 X n−1 1 X n−1 f (s) f (s) − n n s s−1 i̸∈S

i∈S

n−1 X

−1

−1 n−1 n−1 1 X n−1 n−1 f (s) − f (s) s−1 n s=1 s s

n−1 1 n s=1 s − 1

1X [f (s) − f (s)] = 0. n s=1

n−1

Corollary 3.4. To ensure P(∥ϕ̂ − ϕ∥2 ≥ ϵ) ≤ δ, the unbiased kernelSHAP using leverage score sampling requires at most 2 72C 2 n log n log 2δ utility queries for ϵ ≤ 4C log n, whereas the vanilla unbiased kernelSHAP requires 8C nϵ2log n log 2δ for ϵ2 1 n ϵ ≤ Cn 2 . In other words, their query complexities are both O( n log log 1δ ). ϵ2 Proof. Given a sequence of sampled subsets {St }Tt=1 , T [u[n] − u∅ ]st u[n] − u∅ leverage 1X := ϕ̂ uSt − · zSt + 1n . T t=1 n n Specifically, (zS )i = Then, for n > 1, " E

n n Ji ∈ SK − Ji ̸∈ SK . s n−s

# n−1 2 X (u[n] − u∅ ) · |S| n2 uS − zS <= 9C 2 E[∥zS ∥22 ] = 9C 2 ≤ 18C 2 n log n, n s(n − s) 2 s=1 r (u[n] − u∅ ) · s n uS − zS ≤ 3C∥zS ∥2 = 3nC ≤ 6nC. n s(n − s) 2 14

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

The results follow by applying Theorem 2.1. For the vanilla kernelSHAP, vanilla

ϕ̂ Here, Hn−1 =

u[n] − u∅ 1X := uSt zSt + 1n where zS = T t=1 n

(

2Hn−1 (n − s), n 2Hn−1 − n s,

i ∈ S, otherwise.

Pn−1 1

k=1 k ≤ log n. Then,

E[∥uS zS ∥22 ] ≤ C 2 E[∥zS ∥22 ] = C 2 · 2Hn−1 (n − 1) ≤ 2C 2 n log n, 1 2CHn−1 p ∥uS zS ∥2 ≤ C∥zS ∥2 = n(n − s)n ≤ 2Cn 2 log n. n

Lemma A.2. For zS defined in §3, we always have E[zS ] = WT 12n −2 = (m1 − mn ) · 1n ,

(6)

where wS is the S-th column of WT . Proof. If U (S) is constant for all S, it is straightforward to see from Eq. (1) that ϕ(U ) = 0n . This implies that WT 12n −2 = (m1 − mn ) · 1n . Theorem 4.1. For semi-values satisfying m1 = mn , which include the Shapley value and the Banzhaf value, we have Adalina

E[∥ϕ̂

− ϕ∥22 ]

6nD∗ ∥U ∥2∞ 1 nD∗ E[(uS − γ ∗ )2 ] − ∥φ∥22 + T T (T − 1) ∗ 2 γ∗ 6nD ∥U ∥ ∞ = E[∥ϕ̂ − ϕ∥22 ] + . T (T − 1)

≤

Adalina

Meanwhile, the query complexity of ϕ̂

is O( ϵn2 log 1δ ) for semi-values with D∗ ∈ O(1).

Proof. For symmetric semi-values, mn (u[n] − γ̂) − m1 (u∅ − γ̂) = mn u[n] − m1 u∅ . Let

φ̂ :=

Ψ :=

T X

1X (uSt − γ̂) · zSt , T t=1 T

ψ t where ψ t := uSt zSt −

t=1

and Ψ :=

T X

ψ t where ψ t = uSt zSt −

t=1

1X uS · zSt , T t=1 t 1 X uSr · zSt . T −1 r̸=t

Then, we have

1 1 Ψ = φ̂ and E[Ψ] = φ. T T

Besides, ψt − ψt =

X 1 1 1 uSr · zSt − uSt zt = − ψ t . T (T − 1) T T r̸=t

Observe that Adalina

E[∥ϕ̂

− ϕ∥22 ] = E[∥φ̂ − φ∥22 ] =

1 1 E[∥Ψ − Ψ + Ψ − T · φ∥22 ] = 2 E T2 T 15

# 2 1 − Ψ+Ψ−T ·φ . T 2

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

Specifically, " E

# 2 1 1 2 = 2 E[∥Ψ∥22 ] + E[∥Ψ − T · φ∥22 ] − E[⟨Ψ, Ψ − T · φ⟩]. − Ψ+Ψ−T ·φ T T T 2

Since E[Ψ] = T · φ, there is E[⟨Ψ, Ψ − T · φ⟩] = E[∥Ψ − T · φ∥22 ]. Consequently, Adalina

E[∥ϕ̂

− ϕ∥22 ] =

1 T −2 1 1 E[∥Ψ∥22 ] + E[∥Ψ − T · φ∥22 ] ≤ 4 E[∥Ψ∥22 ] + 2 E[∥Ψ − T · φ∥22 ]. T3 T T T4

Recall that ∥zS ∥22 = nD∗ for every S. For the first term, 1 1 1p 1 4nD∗ ∥U ∥2∞ 2 ∗ ∥U ∥2 , and thus ∥Ψ∥ ≤ ∥ ≤ 4nD E[∥Ψ∥ ] ≤ . ∥ψ t ∞ 2 T2 T T T4 T2 For the other term E[∥Ψ − T · φ∥22 ] = T · E[∥ψ t − φ∥22 ] + T (T − 1) · E[⟨ψ t1 − φ, ψ t2 − φ⟩] where t1 ̸= t2 . Since ψ t − φ = (uSt − γ ∗ )zSt + (γ ∗ −

1X uSr ) · zSt − φ and E[ψ t ] = φ, T r̸=t

we have nD∗ nD∗ Var[uS ] − ∥φ∥22 ≤ nD∗ E[(uS − γ ∗ )2 ] + ∥U ∥2∞ − ∥φ∥22 . T T

E[∥ψ t − φ∥22 ] = nD∗ E[(uS − γ ∗ )2 ] + By Eq. 6, for symmetric semi-values, there is

E[zS ] = 0n . As a result, E[⟨ψ t1 − φ, ψ t2 − φ⟩] =

1 nD∗ ∥U ∥2∞ 2 ∥φ∥ ≤ . 2 (T − 1)2 (T − 1)2

Combining all the results yields Adalina

E[∥ϕ̂

− ϕ∥22 ] ≤

6nD∗ ∥U ∥2∞ γ∗ 1 6nD∗ ∥U ∥2∞ nD∗ E[(uS − γ ∗ )2 ] − ∥φ∥22 + = E[∥ϕ̂ − ϕ∥22 ] + . T T (T − 1) T (T − 1) Adalina

Next, we prove the asymptotic complexity of ϕ̂

. Using Hoeffding’s inequality, with probability at least 1 − 2δ , there is r 2C 2 4 ∗ |γ̂ − γ | < log . T δ

Meanwhile, according to Theorem 3.1, with probability at least 1 − 2δ , r r γ∗ 4nD∗ E[(uS − γ ∗ )2 ] 4nD∗ C 2 4 4 ∥ϕ̂ − ϕ∥ < log ≤ log . T δ T δ Therefore, with probability at least 1 − δ, we have both inequalities. Then, r r r Adalina Adalina γ∗ γ∗ 2nD∗ C 2 4 4nD∗ C 2 4 16nD∗ C 2 4 ∥ϕ̂ − ϕ∥ ≤ ∥ϕ̂ − ϕ̂ ∥ + ∥ϕ̂ − ϕ∥ < log + log ≤ log . T δ T δ T δ As a result, P ∥ϕ̂ Putting

Adalina

r − ϕ∥ ≥

∗ 2 16nD ∗ C 2 C log 4δ ≤ ϵ yields T ≥ 16nD log 4δ . T ϵ2

16nD∗ C 2 4 log T δ

! ≤ δ.

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

B. Bridges In this appendix, we discuss how our framework bridges the recent approaches (Li & Yu, 2024b; Chen et al., 2025; Fumagalli et al., 2024; Witter et al., 2025). B.1. OFA (Li & Yu, 2024b) The OFA framework makes use of ϕi =

n X

− ms · ϕ+ i,s − ϕi,s−1

− where ϕ+ i,s = E [U (S)] and ϕi,s−1 = i∈S |S|=s

s=1

[U (S)].

i̸∈S |S|=s−1

Here, each expectations is taken w.r.t. the corresponding uniform distribution. In light of this formula, OFA is proposed − n−1 n−1 to approximate {ϕ+ , where qs denotes i,s , ϕi,s }s=1 for every i ∈ [n]. It also employs a sampling distribution q ∈ R [n] the probability of sampling a subset of size s from 2 . Given a sequence of independent sampled subsets {St }Tt=1 , OFA proceeds as follows: ϕ̂+ i,s := ϕ̂− i,s :=

t=1 U (St ) · Ji ∈ St , st = sK + Ti,s

+ := with Ti,s

t=1

t=1 U (St ) · Ji ̸∈ St , st = sK − Ti,s

T X

with

− := Ti,s

T X t=1

Ji ∈ St , st = sK , Ji ̸∈ St , st = sK .

Then, := ϕ̂OFA i

n−1 X

ms · ϕ̂+ i,s −

s=1

n−1 X

ms+1 · ϕ̂− i,s + (mn · u[n] − m1 · u∅ ).

s=1

In particular, "

+ Ti,s E T

" −# Ti,s s · qs (n − s) · qs = and E = . n T n

To reduce OFA to a Θ(n)-space version, we first set ϕ̂+ i,s = ϕ̂− i,s =

+ − Ti,s Ti,s (n−s)·qs s·qs . Then, T = n and T = n

T T 1 X n 1 T X · + · U (St ) · Ji ∈ St , st = sK = · U (St ) · Ji ∈ St , st = sK , T Ti,s T t=1 s · qs t=1

T T 1 X n 1 T X U (St ) · Ji ̸∈ St , st = sK = · · − · U (St ) · Ji ̸∈ St , st = sK . T Ti,s t=1 T t=1 (n − s) · qs

Next, we have ϕ̂OFA = i

T 1 X n · m st n · mst +1 · U (St ) · Ji ∈ St K − Ji ̸∈ St K + (mn · u[n] − m1 · u∅ ). T t=1 st · qst (n − st ) · qst

This exactly recovers our ϕ̂ in Eq. (3) when Eq. (2) is taken into account. B.2. KernelSHAP (Chen et al., 2025) We demonstrate how their unified formula for unbiased KernelSHAP can be simplified to fit into our framework. Let n n n A ∈ R(2 −2)×n be a binary matrix such that AS,i = 1 if and only if i ∈ S. Let M ∈ R(2 −2)×(2 −2) be a diagonal matrix n−1 T such that MS,S = (n−s)s n . Additionally, let Q be any n × (n − 1) matrix such that Q Q = I and QT 1n = 0n . Given a (s) r (snt ) T T ×(2n −2) sequence of sampled subsets {St }t=1 , let S ∈ R be a sketching matrix such that St,St = T ·q and 0 otherwise. s t

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

The unified formula of unbiased kernelSHAP is given as ϕ̂ r where U :=

kernel

= QUT ST Sbλ + α1n

u[n] − u∅ n √ , and bλ := MAQ, α := n−1 n

√ n √ ( Mu − λ MA1n ). n−1

Here, λ ∈ R is arbitrary. Observe that QUT ST Sbλ =

√ √ n QQT AT MST S M(u − λA1n ). n−1

For convenience, write v = u − λA1n . Specifically, T

QQ A

√

n T √ n−1 1 X st · vS · QQT aSt , · MS S Mv = T t=1 qst (n − st )st snt T

where aS denotes the S-column of AT . Since QQT = I − n1 J, where J denotes the all-one matrix, we have

QQT aS

s n−s Ji ∈ SK − Ji ̸∈ SK . n n

Therefore, QUT ST Sbλ =

T T 1X 1X vSt zSt = (uSt − λst )zSt . T t=1 T t=1

B.3. SHAP-IQ (Fumagalli et al., 2024) Given a sequence of sampled subsets {St }Tt=1 , the estimate produced by SHAP-IQ is ϕ̂IQ i := where H =

T 2Hn−1 X (uSt − u∅ ) · ((n − st )mst Ji ∈ St K − st mst +1 Ji ̸∈ St K) + mn · (u[n] − u∅ ), T t=1

Pn−1 1

k=1 k . For SHAP-IQ,

qs =

1 n . · 2Hn−1 s(n − s)

Then, T

ϕ̂IQ i =

1X (uSt − u∅ ) · T t=1

n mst n mst +1 · Ji ∈ St K − · Ji ̸∈ St K + mn · (u[n] − u∅ ). qst st qst n − st

Consequently, IQ

ϕ̂

1X (uSt − u∅ )zSt + mn · (u[n] − u∅ ). T t=1

B.4. Regression-Adjusted Approach (Witter et al., 2025) The sampling distribution qMSR ∈ Rn+1 used in this approach can be expressed as −1 r s s MSR n qs ∝ p2s+1 1 − + p2s for every 0 ≤ s ≤ n. s n n where p0 and pn+1 are arbitrary. Observe that −1 −1 −1 −1 s s n−1 n n−1 n p2s+1 · 1 − + p2s · = m2s+1 · + m2s · . n n s s s−1 s 18

Provably Adaptive Linear Approximation for the Shapley Value and Beyond

Algorithm 2 Adalina-All Input: Weight vector m ∈ Rn for semi-value ϕ, total number of samples T Adalina−All

Output: Estimate ϕ̂ 10

Compute the sampling distribution q ∈ Rn+1 for 0 ≤ s ≤ n such that qs ∝

ms+1 m2s s + n−s

x := 0 0

Initialize ϕ̂, v̂ ← 0n , γ̂ ← 0 for t = 1, 2, . . . , T do 13 Sample a subset size s with probability qs 14 Sample a subset S of size s uniformly from 2[n] 1 MSR 15 ϕ̂ ← t−1 t · ϕ̂ + t · uS zS 1 t−1 MSR 16 v̂ ← t · v̂ + t · zS 1 17 γ̂ ← t−1 t · γ̂ + t · uS

11 12

ϕ̂

Adalina−All

← ϕ̂ − γ̂ v̂

Then, s r m2s+1 s n m2s s 2 2 ps+1 · 1 − + ps · = n · + . n n s n−s s Here, the convention is x0 := 0. Eventually, we have s m2s+1 m2s + for every 0 ≤ s ≤ n. q MSR ∝ s s n−s It is clear that qMSR coincides with q∗ , except that qMSR includes [n] and ∅ in the sampling pool. Let D

MSR

n X

s=0

q MSR s

m2 m2s + s+1 s n−s

Then, D

1 MSR 2

n X

n·

s=0 ∗

1 2

m2 m2s + s+1 s n−s

= m1 + (D∗ ) 2 + mn ,

which leads to (D ) ≤ (D ) ≤ 2 + (D∗ ) 2 . It indicates that DMSR ∈ O(1) if and only if D∗ ∈ O(1). Therefore, according to Li & Yu (2024b, Proposition 4), DMSR ∈ O(1) for Beta Shapley values and weighted Banzhaf values. MSR

m1 n Under the use of qMSR , zMSR = zS with qs = q MSR for all ∅ ⊊ S ⊊ [n], while zMSR = − qMSR 1n and zMSR = qm MSR 1n . s S ∅ [n]

In this case, one can verify that ∥zS ∥22 = nDMSR for every S ⊆ [n]. Moreover,

E[zMSR ] = 0n S for every semi-value, which is one of the keys to prove Theorem 4.1. As a result, Theorems 3.1 and 4.1 continue to hold when using qMSR , where D∗ and ∥φ∥22 are replaced by DMSR and ∥ϕ∥22 , respectively, and the constraint on symmetric semi-values is removed. After all, the corresponding estimate is MSR

ϕ̂

1X uS zMSR . T t=1 t St

Its adaptive version is given by MSR−adaptive

ϕ̂

T T 1X 1X := (uSt − γ̂) · zMSR where γ̂ uS . St T t=1 T t=1 t

The corresponding procedure is presented in Algorithm 2. 19

Provably Adaptive Linear Approximation for the Shapley Value and Beyond Table 1. Summary of the datasets used.

Dataset

#Instances

#Features

6, 118 9, 873 130, 064 5, 832 4, 601 21, 263

51 32 50 308 57 81

FOTP GPSP MinibooNE philippine spambase superconduct

Adalina (ours) Adalina-All (ours)

0.04 0.02 0.00 0.02 0.04 0.04

0.02

0.00

0.02

0.04

Source

Task

https://openml.org/d/1475 https://openml.org/d/4538 https://openml.org/d/41150 https://openml.org/d/41145 https://openml.org/d/44 https://openml.org/d/43174

classification classification classification classification classification regression

MSR-Banzhaf MSR-Prob

SHAP-IQ kernelSHAP

AME ARM

6 5 2 2 2 -

20 10 20 15 15 10

100

10 1

(4, 16)

Beta Shapley values

(8, 8)

(2, 2)

(16, 4)

(1, 16)

(1, 4)

(1, 1)

(4, 1)

(16, 1)

(4, 16)

Beta Shapley values

(8, 8)

(2, 2)

(16, 4)

(1, 16)

(1, 4)

(1, 1)

(4, 1)

(16, 1)

(4, 16)

(8, 8)

(2, 2)

(16, 4)

(1, 16)

(1, 4)

(1, 1)

(4, 1)

(16, 1)

Beta Shapley values

Depth

GELS GELS-Shapley

100

10 1

#Classes

100

10 1

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

philippine (n = 308)

GPSP (n = 32)

superconduct (n = 81)

Weighted Banzhaf values

Figure 5. The relative approximation error of different randomized algorithms. Weighted Banzhaf values are parameterized by w ∈ (0, 1), whereas Beta Shapley values are parameterized by (α, β), with (1, 1) corresponding to the Shapley value.

C. Experiments u

−u

For kernelSHAP, we set q = q∗ and λ = [n]n ∅ , a combination that is empirically the best according to Chen et al. (2025), as confirmed in Figure 1. The details of the employed datasets are summarized in Table 1, which includes the depth of trees used to construct utility functions. Additional results on the comparison of randomized algorithms for approximating semi-values are shown in Figure 5.

Record · ID 2592 · SHA-256 a17d07a5b275d1ef
Conceptio Open Knowledge Archive — every document is proof-bundled with source, license, and retrieval metadata.