One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently
Authors: Weida Li
Yaoliang Yu
Venue: NeurIPS 2024 poster (2024)
Keywords: Beta Shapley values
weighted Banzhaf values
approximation
datamodels
Primary area: interpretability_and_explainability
TL;DR: We explore the possibilities of approximating all probabilistic values simultaneously and efficiently, examples of probabilistic values include Beta Shapley values and weighted Banzhaf values.

Abstract: The concept of probabilistic values, such as Beta Shapley values and weighted Banzhaf values, has gained recent attention in applications like feature attribution and data valuation. However, exact computation of these values is often exponentially expensive, necessitating approximation techniques. Prior research has shown that the choice of probabilistic values significantly impacts downstream performance, with no universally superior option. Consequently, one may have to approximate multiple candidates and select the best-performing one. Although there have been many efforts to develop efficient estimators, none  are intended to approximate all probabilistic values both simultaneously and efficiently. In this work, we embark on the first exploration of achieving this goal. Adhering to the principle of maximum sample reuse and avoiding amplifying factors, we propose a one-sample-fits-all framework parameterized by a sampling vector to approximate  intermediate terms that can be converted to any probabilistic value. Leveraging the concept of $ (\epsilon, \delta) $-approximation, we theoretically identify a key formula that effectively determines the convergence rate of our framework. By optimizing the sampling vector using this formula, we obtain i) a one-for-all estimator that achieves the currently best time complexity for all probabilistic values on average, and ii) a faster generic estimator with the sampling vector optimally tuned for each probabilistic value. Particularly, our one-for-all estimator achieves the fastest convergence rate on Beta Shapley values, including the well-known Shapley value, both theoretically and empirically. Finally, we establish a connection between probabilistic values and the least square regression used in (regularized) datamodels, showing that our one-for-all estimator can solve a family of datamodels simultaneously. Our code is available at https://github.com/watml/one-for-all.

One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently
Weida Li School of Computing National University of Singapore vi vidaslee@gmait 1. com
Yaoliang Yu School of Computer Science University of Waterloo Vector Institute yaoliang. yuglianngyuu@uaterlloo ca
Abstract
The concept of probabilistic values, such as Beta Shapley values and weighted Banzhaf values, has gained recent attention in applications like feature attribution and data valuation. However, exact computation these values is often expo- nentially expensive, necessitating approximation techniques. Prior research has shown that the choice of probabilistic values significantly impacts downstream performance, with universally superior option. Consequently, one may have to approximate multiple candidates and select the best-performing one. Although there have been many efforts develop efficient estimators, none intended approximate all probabilistic values both simultaneously and efficiently. In this work, embark the first exploration of achieving this goal. Adhering the principle of maximum sample reuse and avoiding amplifying factors, we propose a one-sample-fin fits-all framework parameterized by a sampling vector to approximate intermediate terms that can be converted to any probabilistic value. Leveraging the concept of (c, approxxxxiao,,,, we theoretically identify key formula that effectively determines the convergence rate of our framework. By optimizing the sampling vector using this formula, we obtain a one-for-all estimator that achieves the currently best time complexity for all probabilistic values on average, and ii) faster generic estimator with the sampling vector optimally tuned for each probabilistic value. Particularly, our one-for-all estimator achieves the fastest convergence rate on Beta Shapley values, including the well-known Shapley value, both theoretically and empirically. Finally, we establish connection between prob- abilistic values and the least square regression used in (regularized) datamodels, showing that our one-for-all estimator can solve family of datamodels simultane- ously. Our code available at https: //gi thub. com/ wa tm// /ww/oooe-ooooo for-all.
1 Introduction
The problem of attribution is central in many aspects of machine learning (Rozemberczki et al. 2022). Examples include data valuation (Ghorbani and Zou 2019), feature attribution (Lundberg and Lee 2017), multi-agent reinforcement learning (Wang et al. 2022), data attribution (Ilyas et al. 2022), and the list goes One popular methodology is leverage the concept of probabilistic values, which is uniquely characterized by the axioms of linearity, null, monotonicity and symmetry in cooperative game theory (Weber 1988). Recent studies demonstrate that downstream performance employing this concept relies on the choice of probabilistic values, and the best one varies (Kwon and Zou 2022b; Li and Yu 2023). Therefore, practitioners may resort to approximating multiple candidates of probabilistic values and then select the best best-performing one (Kwon and Zou 2022b).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In general, probabilistic values can only be approximated as they require exponentially many utility evaluations to compute exactly. Thus far, there has been line of works devoted to designing efficient estimators for the Shapley value (e.g., Covert and Lee 2021; Jia et al. 2019; Kolpaczki et al. 2024; Zhang et al. 2023), while Li and Yu (2023) and Wang and Jía (2023b) proposed efficient estimators specific to weighted Banzhaf values. Despite recent progress in research on generic estimators for approximating any probabilistic value (Li and Yu 2024; Lin et al. 2022), none of them can approximate all probabilistic values simultaneossly and efficiently. Overall, there is a strong demand for efficient one-for-all estimators, the possibilities of which will be explored in this work.
To sum up, we propose a Aie-sammle-FFie Fits-All (OFA) framework parameterized by sampling vector to approximate intermediate terms that can be converted to any probabilistic value. Particularly, our framework i) adheres to the principle of maximum sample reuse and ii) does not include amplifying factors in the conversion. These two properties are considered indispensable as we observe that i) the empirical fastest estimators designed for the Shapley value or weighted Banzhaf values all follow she principle of maximum sample reuse and ii) amplifying factors could deteriorate the convergence rates of estimators. Then, using the concept of (c, -apppooximation, i.e., P(lo 212 2 c) S
where & refers to some probabilistic value and & is its estimate, we theoretically identify formula from our framework that effectively determines the corresponding convergence rate, through which the sampling vector can be optimized. Specifically, we deduce i) an efficient one-for-all estimator (OFA-A) while optimizing the formula for all probabilistic values on Average and ii) a faster generic estimator (OFA-S) while the optimization is done for each Specific probabilistic value. The results of our convergence analysis are summarized as follows:
log (i) Our OFA-A achieves the convergence rate (n logn) n) for all probabilistic values on average. Notably, (n log n) is the currently-knwwn best time complexity for some probabilistic values. (ii) For Beta Shapley values parameterized by a, B 2 1 (Kwon and Zou 2022a), our OFA-A estimator requires On log n) utility evaluations to achieve an (c, 6) approxxiiatoo simulta- neously. Note that a B corresponds to the commonly-used Shapley value (Shapley 1953). For the Shapley value, the previous best convergence rate is O(n(log n)?).' achieved by the group testing estimator (Wang and Jia 2023a, Theorem 6); however, we note that in our experiments the previous best-performing estimator is the complement estimator (Zhang et al. 2023), whose convergence rate unknown. For Beta Shapley values with (a = 1,3 > 1) or (a >>>>> 1, = 1), the previous best estimator requires OOn(log n)²) utility evaluations instead (Li and Yu 2024, Proposition and Remark 3).
(iii) For weighted Banzhaf values parameterized by 0 < w < 1, the time complexity of our OFA-A is Ön logn), not rivaling the previous best convergence rate O(n n) achieved by the estimator exclusive to weighted Banzhaf values (Li and Yu 2023, Proposition 2). Nevertheless, our OFA-S achieves the convergence rate of O(n n) for both Beta Shapley values (with a, 3 2 1) and weighted Banzhaf values.
In our experiments, the empirical convergence rates align well with the theoretical ones derived using the concept of (c, (ap))apppooiiatiinn. Additionally, we establish a connection between probabilistic values and the least square regressions employed in datamodels (Ilyas et al. 2022), demonstrating that OFA-A estimator can solve family of datamodels simultaneously if it is the distances between feature coordinates that matter. This condition is met while using datamodels to detect similar training examples given target. Furthermore, we also identify a group of regularized datamodels that our OFA-A estimator can solve simultaneously without this condition.
Preliminaries
Let n be the number of players and [n] := (1, be the set of all players. In data valuation (feature attribution, respectively), n refers to the number of training data (features, respectively). For simplicity, we write S\ and S instead of (1) and SUU fi), respectively. Meanwhile, (lowercase) s denotes the cardinality of the set (uppercase) S. Then, each probabilistic value can be written as U(S)
Φ: = (U)) = Σ Po+ PU
SEiM]
Ussing another definition, Musco and Witter (2024) claimed have estimator with convergence rate (n log n) for the Shapley value after this work was accepted.

---

where U 2(n] + R is utility function and E I" is a non-negative vector such that Ex (5-1)p= = 1. Take data valuation as an example, U(S) may measure the performance of models trained on 5 C [n], with which oi (U) can be interpreted as the contribution of the i-th data point to the performance of models trained on [n].
there exists a (Borel) probability measure y on the closed interval [0, 1] such that ps = So w² '(1 w))=sdp(wt w) then the resulting probabilistic value is referred to as semi- value (Dubey et al. 1981). If represents Dirac delta distribution dæ, the corresponding probabilistic value is referred as the weighted Banzhaf value parameterized by a, or WB-a. For Beta Shapley values, denoted by w1-1(1 dm. In practice, the considered range of a is [1, 20) (Kwon and Zou 2022a,b). Particularly, Beta(1, 1), whose is the uniform distribution (over [0, 1)), corresponds to the Shapley value.
Beta(a, (3), ((A)
We will use the standard notion of (c, appproxiaati to analyze a (randomized) estimate & of some probabilistic value Φb
Definition 1. We say a (randomized) estimate & achieves an (c, capproxitatiiionn of Φ if P(I 2112 2 e) <
For instance, Wang and Jia (2023b, Theorem 4.9) proved that their proposed estimator requires 0 log n) utility evaluations to achieve an (e, apprrxxxmitiiooonn for WB-0.5, provided that | 00 S 1. When and 8 are considered fixed constants, then simply say the estimator converges at On log n) rate.
Motivations
One-For-All Estimators In this paper, an estimator is referred to as one-for-all all it is capable of sampling subsets Once to approximate All probabilistic values.
Though existing estimators are not designed approximate all probabilistic values simultaneously. some of them can be easily modified for this end by using the weighted sampling technique. Take the sampling lift (SL.) estimator (Moehle et 2022) as an example, approximation based on
Φ = EsggH/
U(S) where P(S) = Ps+1-
If we fix the probability sampling S to be the one, denoted by q E R" for the Shapley value, there is
Φ =
sc
Shap
Ps+1 (U(SU)) (U(SU))))
(1)
4s+1
which is the weighted sampling lift (WSL) estimator employed by Kwon and Zou (2022a). Therefore, we can store the accumulated results (U(S Ui) - U(S)} separately for each subset size of S that they can be reweighted to be any probabilistic value.
( potentially introduce a non- The Effect of Amplifying Factors However, the scalars 1ut1 negligible factor into the theoretical convergence rate. To demonstrate, we take the WSL estimator as an example. this case, di = + E X, where [X,)T are i.i.d. random variable such that P(X;
Pa-1 (U(S i) U(S)) = 4s+1 and thus E[X.] di. Assume that [0]| S 1, by the
d+41
Hoeffding's inequality, P(l ø.1 2 <) $ 2 exp
Tea 802
where C maxigAán ax By solving
2 exp
Tea SC
80 S we eventually obtain T > 2
log 2 and therefore the convergence rate of à
log 2). Consequently, if asymptotically. For the Banzhaf value, Ps = - since ql = (k-1)](n-k)! l: = 2
is O e
oo, this theoretical convergence rate deteriorates n+1 there
n!
Pt E En2)) by the Stirling's approximation d! vá (1)² Therefore, 2 introduces a factor
qu of (()) into the theoretical convergence rate, though the derived formula may not be tight. If we switch the roles of p and q, the introduced factor Cº is as worst as (22"). To generalize this idea,
formula is said to contain amplifying factor if it involves 7 US) such that - +

---

Regarding this, we notice that Kwon and Zou (2022b) resort to a one-for-all estimator based on
m, (UC
(2)
where m, = (;-i)Pb and each expectation is taken over the corresponding uniform distribution. We refer to this estimator as weightedSHAP in this work. As can be verified, Eq. (2) does not contain any amplifying factors, i.e., each m, does not grow as n + oc.
The Principle of Maximum Sample Reuse However, estimators designed according to Eqs. (I) and (2) are not expected to be efficient as it does not obey the principle of maximum sample reuse. Precisely, an estimator adheres to the principle of maximum sample reuse if each sampled subset is used to update all estimates { (et)) As analyzed by Zhang et al. (2023, Section 4.2), estimators based on sampled marginal contributions {U(S - {S}} are impossible to meet the principle of maximum sample reuse. By contrast, we observe that the SHAP-IQ estimator proposed by Fumagalli et al. (2024) can also be adopted for this end, which employs the formula
&i (m(((())) (0)) + 2H [((12 s)m,lles 1
(())] (3)
where m, = (-=)) Ps. H = Σj= and P(S) x (-=1)= In particular, SHAP-IQ is equal to the unbiased KernelSHAP estimator (Covert and Lee 2021) for the Shapley value; see (Fumagalli et al. 2024, Theorem 4.5). Although SHAP-IQ follows the principle of maximum sample reuse, is apparent that Eq. (3) contains an amplifying factor H E B(logn). Meanwhile, there is another line of research in quest of efficient estimators for the Shapley value by reducing the variance via the stratified sampling technique (Burgess and Chapman 2021; Castro et al. 2017; Maleki et al. 2013; Wu et al. 2023). However, such a technique also does not verify the principle of maximum sample reuse.
Empirical Evidence For convenience, we formally define the two aforementioned desirable prop- erties for estimators to possess as Pl: The underlying formula contains no amplifying factors and P2: Each sampled subset is used to update all the estimates { In Figure 1, we provide some experiment results while setting n 24 to support aforementioned informal analysis. Precisely, we implement six one-for-all estimators by combining the weighted sampling technique and the previous estimators. Some of our observations are:
(i) On WB-0.5, weightedSHAP, which satisfies P1 but not P2, is empirically not comparable to MSR-Banzhaf that possesses both P1 and P2. This observation supports the necessity of P2.
(ii) On WB-0.5, SHAP-IQ sticks to P2 but not Pl. It is clear that SHAP-IQ also performs significantly worse than MSR-Banzhaf, which highlights the role of P1.
(iii The sudden rises of relative differences stem from the existence of significantly large amplifying factors. For WSL-Banzhaf on Beta(1, 1), the scalar for (i) (() is as large 2"
In Table 1, we summarize the previous estimators terms of P1 and P2, and defer the technical details to Appendix D. Notably, the complement estimator is empirically the best for the Shapley value, while it MSR for weighted Banzhaf values; both of them follow P1 and P2.
Table I: A scope "all" indicates that the estimator can approximate any probabilistic value, whereas "weighted Banzhaf" suggests that the estimator can only approximate weighted Banzhaf values. P1 refers to the property that the underlying formula does not contain any amplifying factors for all probabilistic values in scope, while P2 means whether each sampled subset is used to update
all the estimates {6. / For AME, the range of y in y US) could be (0, oc), independent of n. Originally, AME only applies to subfamily of semi-values, but extend it for all semi-values in
Appendix D.
WSL. (Kwos and 2022.3
Si (Modlle al 2002) Shopky
GFIS (Li and Yo 2024)
ABM (Kolpoakii st 2004) all
MSR
SHAP BQ (Paresuli et 20243
weigHedSHEA
(Wasg and 2013b) weighted Bonthaf /
(Koon and Zou 20026)
P1
P2
(Castro 2003)
keredSSHAPP (Landiegg 2017)
unbioual lemdSSAAP 1021) Stapley
200ug
2013a) Stapley
completest Stopley
AME (Lis semi-oliux
OFA all
Stapley
shopley
P1

---

OFA-A (ours)
WSL-Banzhaf
ARM-Banzhaf ARM-Shapley
MSR-Banzhef
weightedSHAP
OFA-S (ours)
WSL-Shapley
SHAP-10
permutation-Shapley
107
207
ditferonce
10a
relative differrncee
relative difference
30²
201
105
20*
209
10-1
10-1
10
10-²
13000 #Puiiiity per player
10000
5000
15000 20000
5000
15000 20000
#utiiity evailuations per player
*utility evaluaaions player
Beta 1)
Beta(1, 1)
Beta (1, 4)
10a
relatve ditfaronce
differrncce
relative difference
107
10-1
L0-3
19"4
13005 #utility evalustions per player
5000 #utiiity evalustions per player
20000
5000
15000 20000
*utility evallaaions player
WB-0.2
WB-0.5
WB-0.8
Figure 1: Comparison of ten one-for-all estimators. Beta(a, 3) denotes Beta Shapley values, whereas WB-a refers to weighted Banzhaf values. Our OFA-S estimator is equal to the OFA-A estimator for the Shapley value. The suffix "Shapley" indicates that there is reweighting for the Shapley value, while "Banzhaf" stands for the Banzhaf value. The permutation estimator is originally proposed for the Shapley value. The utility function U is the cross-entropy loss of LeNet trained 24 data from FMNIST. All the results are averaged using 30 random seeds.
Main Results
The framework we propose is built upon
6:
my
E [UR
E [U()
(4)
ER
SR
==1
where m, = (C=1)p, and each expectation taken over the corresponding uniform distribution. For simplicity, we write Φ
- [U (R)). Clearly, there is no amplifying factors in Eq. (4). Meanwhile, the structure of Eq. (4) suits the principle of maximum sample reuse. Since {Ø, / I, and (0,,, 10,,11==0,1 can be calculated exactly using 2n + 2
(U(R) and - Eight
utility evaluations of U, our focus is efficiently approximate ( 12,12esn The proposed framework is presented in Algorithm I; qj the probability of drawing subset of [r]] with size j + 1. To facilitate the choice of the sampling vector q E == appearing Algorithm our first step is to theoretically ascertain a key formula that effectively determines the convergence rate of Algorithm 1.
Theorem 1. Assume i) [|]| S and ii) 0 < 22 q)r(4) For & in Algorithm it 4nu D(m.g) log o
requires
8n²
evaluations of U to achieve P(] Φ112 2 E) < 8 where q--1 Q (n
2
n-2 T
m
m
D(m, ②)
and (()) min 25e5n-2
min
9--1 8
n
n
n
We remark that D(m, q) jointly convex in m and q. The second assumption Theorem can be removed subsets in a predetermined order; see the proof in Appendix A for details. Precisely, let T be the number of subsets for estimating o and define Ti,, similarly; then the pre-allocated numbers T -9 and T,, (n-e)u.-1 which are the expected values of T and T while using Algorithm 1; T refers to the total number of sampled subsets. By Theorem 1, the convergence rate of Algorithm is (DD(m, q) n log n), and thus achieving the currently best convergence rate On logn) requires D(m, q) O(1).
pre-allocate the number of sampled subsets for each o.., or oi,, and draw
5

---

Algorithm 1: The One-Sample-Fits-All (OFA) Framework
Input: A utility function U : 2 + R, a positive probability vector q E R"-3, and a total number T of samples
Output: Estimates to @ 1,k+ and Lik with i, k+ E [n|] and 0 S k- S n -
iitt - 0 and L.k- t -i,-- for i E [m]. kt {1,n - 1, and & E {0, -
2 i.k + 0, 0 1,k + 0, 1. + 0 and T + 0 with i E [m] and 2 S k < n- 2
for t = ........ T do
4 Sample s; from f2.3. n - 2] according to q Sample S, uniformly from {R S [n] r
v x (S, for i = 1,2,..... do i Sz then
Th,, +1 1i + Ti,, +1 1 and T,t., +- T +1
10
else
11
1,80
Tr.., +1 Pion + Pi +1 and I Tims + T Ti +
Aggregation Phase:
&i E.= my (o - 2
4.1 A One-For-All Estimator
To obtain our one-for-all estimator, our goal is to find a q such that D(m, q - E (11 for as many m as possible. To this end, we define q Q be the uniquely optimal solution
/ MEA
argmin D(g) q
D(m, ()d)(m)
where A = {m E R" m, 2 0 and En= m7, 1} and v is the uniform distribution on A. In our work, our OFA-A estimator refers to the use of OFFA-A in Algorithm 1.
Proposition 1. OPA-A
(()) and OFA-)) e O(1). In other words, our OFA-A estimator
achieves the convergence rate of (n logn) simultaneously for all probabilistic values on average.
Our next proposition provides condition on μ for semi-values such that our OFA-A estimator achieves the convergence rate of O( log n). In other words, we explicitly identify a subfamily of semi-values for which our OFA-A estimator achieves the currently best time complexity simultane- ously.
Proposition 2. Our OFA-A estimator achieves the convergence rate of O n) simultaneously for all semi-values whose probability density functions exist and are bounded. Particularty, Beta Shapley values with a, 3 2 1 all satisfy this condition.
To our knowledge. the previous caroreticalllyffstess estimator for the Shapley value is demonstrated by Wang and Jia (2023a, Theorem 6) as (noloo 2) By contrast, our OFA-A A estimator achieves the convergence rate of O log nt). Meanwhile. also surpasses the previous best time complexity for Beta Shapley values with (a = 1,3 1) or (a > 1, B = 1), which is (nn(log )) (Li and Yu 2024, Proposition and Remark 3). Remarkably, our OFA-A estimator enjoys this fastest convergence rate simultaneously for a broad subfamily of probabilistic values
Proposition 3. Ifps = a0 a)n with 0 < a < 1, which corresponds to the weighted Banzhaf value parameterized by then D(m, ( E O(t)) In other words, the OFA estimator achieves the convergence rate of O( à log n) simultaneously for all WB-a with
< 1.
The previous best convergence rate for weighted Banzhaf values is O(n log n) (Li and Yu 2023, Proposition 2), ours is slower by factor of n². Nevertheless, we will demonstrate that our generic estimator, which is expected be faster than our OFA-A estimator, achieves the best convergence rate for all weighted Banzhaf values.

---

4.2 A Faster Generic Estimator
Our faster generie estimator (OFA-S) obtained via optimizing q for each Specific m. Precisely, for each m, we have
OBA-S
O m
m
where q q argmin (mm, q) s.t. Σ 9J - qER--3
(5)
which can be obtained using the Cauchy-Setie Schwarz inequality. For the Shapley value, q Q q ORA.A
Our next proposition specifies a sufficient condition for semi-values such that D(m, q OFA.S) E O(1).
Proposition 4. For semi-values, (m,, QP..s) E O(1) if μ has a bounded probability density function ii) f(..1) w(--w) du(w) ()) < cc. Particularly, this condition covers all weighted Banzhaf values and Beta Shapley values with a, 2 1.
All in all, demonstrate that by sticking to the principle of maximum sample reuse and avoiding any amplifying factors, we are able to establish a generic estimator that achieves the currently best convergence rate for any previously-studiee semi-value.
4.3 A Connection between Probabilistic Values and Datamodels
A datamodel, proposed by Ilyas et al. (2022), is learn easy-to easy-to-interpret surrogate to represent model output distribution related to a specific test example. In this circumstance, the set of players [n] identified with all the available training data. Precisely, the feature coordinates 0" E R imputed to every data point in [n] is defined to be the uniquely optimal solution (together with a bias b* E R) to the optimization problem
argmin Σ 7 U(S) - OER BEB
(6)
SCIm
where 17 E R==1 non non-negative and Σ.= 7s+1 > 0. The weight vector v can be scaled such that the objective in the problem (6) can be treated as expectation, and thus the objective can be approximated through sampling a sufficient number of subsets, upon which an estimate of (0*, b*) can be obtained. We show below that O to a family of such least square regressions can be cast as some probabilistic values if it is the pairwise differences 07 0% (for every j, E [n.) that matter.
Theorem 2. Let (b", 0*) be the uniquely optimal solution the problem (6) where n)s Ps-1 Ps for 2 E s S n. Then, there is
87 - = Φの Φx for every j. E [m].
In other words, 0" = Φ + for some constant cl; 1 E Rn is the all-one vector. When using datamodels detect similar training examples given target, what matters is the relative order of components in 0* Meanwhile, Ilyas et al. (2022) showed that the corresponding performance depends on the choice of the weight vector 77. Therefore. our OFA-A estimator serves as a sufficient proxy for a range of } and would facilitate the fine-tuning of 7) when using datamodels to detect similar training examples.
When 0" Can Be Recovered From Interestingly, for specific choices of p I and v) Rn+11 it holds that 0 = Φ. Theorem 2 can be seen as an extension to the previous result stated in the below.
Proposition (Marichal and Mathonet 2011, Proposition 4). Suppose 0 < a < 1 is given, if 1, which leady to
P, a² 1 (1 a)n-3 for 1 S i and Mik
a (1 a)n for
P. + for 2 < s E n, there is
0" Φ
It is worth pointing out that Φ in Proposition 5 is exactly the weighted Banzhaf value parameterized by a, i.e., WB-a. Even more, under the same setting, we can even solve a group of datamodels with l or &g regularization simultaneously.
7

---

Corollary 1. Under the setting of Proposition 5, let 0 be the uniquely optimal solution to
argmin OER .,EE
Σ
Mot1
U(()) - Σ
81
+
X
R(0)
a(1 - a)
SCinl
iES
where À > O, the following are true about the relation between O" and Φ:
1. Rf()) = 11012 then
0- 1 A ) a(1 - a) )² Φ
2. (f)) -1011, then
0- sign( max 00100 2a(1 a)
All operations are element-wise.
This corollary is immediate by combining Proposition 5, and Theorem 2.2 by Saunshi et al. (2022). We comment that replacing z; by 2x; - 1, i.e., mapping 0 and 1 into -1 and 1, respectively, in 6 (z) used by Saunshi al. (2022) yields v41 (z)) used by Marichal and Mathonet (2011). A remarkable implication of the combination of Corollary and our proposed OFA-A estimator is that solve group of regularized datamodels covered by the problem (7) simultaneously! For example, the coefficient À can be finetuned by running Algorithm just once.
Experiments
In this section, we are verify i) the simultaneous efficiency of our OFA-A estimator and ii) the faster convergence rate of our OFA-S estimator compared with the considered baselines and our OFA-A estimator. Particularly, if (mm, q) is effective in determining the convergence rate of Algorithm our OFA-S estimator is expected to be faster than our OFA-A estimator. All the experiments are conducted using CPUs.
We use two types of utility functions for this end: i) following the experiment settings of (Li and Yu 2024), (S) is set be the cross-entropy of LeNets trained S the classification datasets FMNIST, MNIST and iris; to obtain the exact values, the number training data n is set to be 24; ii) U is defined to be the sum of unanimity (SOU) games, i.e., U(S) = Σ 03 ss where each 0 Sy ç [n]] is randomly sampled, for which each semi-value can be computed by d; ンÿ 0j [o.1] w -ww((w);;; specifically, we set n {64, 128, 256} with d n², which implies that the implemented SOU games require n² utility evaluations to compute semi-values exactly. The random seed inside each utility function is fixed as 2024, and thus each U is deterministic.
For the simplicity of presenting our empirical results, we use the area under the convergence curve (AUCC) to assess the convergence quality estimators, and thus the smaller the better. For 24, the value of each player is approximated using 20, 0000 utility evaluations, and we compute the 100 (2002) all where & (2005) refers to the estimate using 200ý utility evaluations AUCCs as TOO 2j=1 for each player. For E (64, 128, 256), the value of each player is approximated using 000 utility [ (20g) +ll2
|
evaluations, and the corresponding AUCCs are calculated as 100 >)
All the AUCCs +012
are reported with standard deviation using 30 different random seeds from {0. 1, 2,,,,,.,,,99
Verification of Our OFA-A Estimator For our OFA-A estimator where we substitute q OPA-A which is defined in Proposition 1, into Algorithm 1, we choose the baselines according to Figure The selected baselines include WSL-Shapley (Kwon and Zou 2022a), SHAP-IQ (Fumagalli et al. 2024), weightedSHAP (Kwon and Zou 2022b) and permutation-Shan Shapley (Castro et al. 2009). The corresponding results are reported in Figure 2. Overall, our OFA-A estimator performs the best on all the employed 18 probabilistic values, which verify the simultaneous efficiency of our OFA-A estimator.
8

---

OFA-A (ours)
SHAP-QQ
weightedSHAP
permutationShaaple Shapley
AUCC
AUCC
12
11
91
T1
91
100
30
Beta Shapley values
Beta Shapley
Beta Shapley values
104
AUCC
AUCC
AUCC
10--
022 2.3 5.4 0.S 0.6 0.7 0.5 0.9
0.1 02 8.3 0.4. 0.5 U.S. 0.7 0.5 0.2
0.1
0.2 03 24 0.5 0.7
weighted values
weighted
weighted
iris (n 24)
MNIST (n 24)
FMNIST (n = 24)
10
AUCC
AUCC
AUCC
911
11 93
11
10
191 50
310
191
11
191
Beta Shapley values
Beta Shapley values
Beta
Shapley values
AUCC
AUCC
AUCC
0.3 02 3.1 54 6.5 0.5 6.7 0.8 0.5 weighted Banzhaf values
3.1 02 8.3 64 6.5 0.6. 077 B. weighted Banzhar values
0.1 0.2 6. 64 8x 0.6 8.7
Wei Weighted Banzhar
SOU (n 64)
SOU 128)
SOU (n 256)
Figure Comparison of one-for-all estimators using six utility functions. the AUCCs are reported with standard deviation using 30 random seeds. Smaller AUCC indicates faster convergence rate.
Verification of Our OFA-S Estimator Next, we verify the faster convergence rate of our OFA- estimator, using q OFA-S as defined in Eq. (5). The baselines we employ include: (unbiased) kernelSHAP (Covert and Lee 2021; Lundberg and Lee 2017), GELS and BEES--Shapley (Li and Yu 2024). ARM (Kolpaczki et 2024: Li and Yu 2024), complement (Zhang al. 2023), group testing (Jia et al. 2019; Wang and Jia 2023a), AME (Lin et al. 2022), MSR (Wang and Jia 2023b) and sampling lift (Moehle et al. 2022). Note that not the baselines are designed for the probabilistic values we employ. For example, the complement estimator only works for Beta(1 (1 1), i.e., the Shapley value. According to (Li and Yu 2024, Remark 9), we implement the paired sampling technique for (unbiased) kernelSHAP and group testing. The corresponding results are presented in Figure 3.
First, our OFA-S estimator indeed faster than our OFA-A estimator, which aligns exactly with our theory: in other words, it implies that our proposed D p) indeed determines the convergence rate our Algorithm 1. Second, our OFA-S estimator always performs the best except on the SOU games which require only n² utility evaluation to get the exact values; by contrast, the utility function defined using the classification datasets require utility evaluations instead. Third, our proposed estimator is consistently the fastest the commonly-used Beta(1, 1), i.e., the Shapley value; note that q - q OFA-S for the Shapley value; therefore, our proposed estimator achieves the currently best convergence rate both empirically and theoretically.

---

OFA-A (ours)
GELS GELS-Shapley
sampling
unbiased kernelSHAP
ARM
AME
OFA-S (ours)
kernet SerneeSHAPP
group testing
complement
MSR
10k
105
10
107
AUCIC
AUCC
AUCC
10"4
10"11
10
1914
1'
11
11
91
91
Beta Shapley valuess
Beta Shapley values
Beta Shapley values
107
10
AUCC
10
AUCC
AUCC
10"4
0/6 weighted Banzhaf values
077 weighted Banzhal
05 weighted Banzhaf values
iris (n 24)
MNIST (n 24)
FMNIST (n 24)
AUICC
10
AUCC
10-11
AUCC
10--1
Beta Shapley
Beta values
Beta volues
10
AUCC
AUCC
AUCC
0z a1 6.5 6. 0.9
0.3 0.6 0.7 weighttd Banshat
02 03 DE weighted Banzhaf
weighted Banzhaf
SOU (n 64)
SOU (n 128)
SOU (n 256)
Figure 3: Comparison of twelve estimators using six utility functions. The dashed lines correspond to the improved AME estimator developed in Appendix D. All the AUCCs reported with standard deviation using 30 random seeds. Smaller AUCC indicates faster convergence rate.
Conclusion
In this work, we propose a framework, termed OFA, that i) adheres to the principle of maximum sample reuse and ii) contains amplifying factors for the goal of optimizing all probabilistic values simultaneously and efficiently. Particularly, our OFA framework is parameterized by sampling vector R=-3 To gain insights, theoretically develop key formula D(m, q) concerning this framework that effectively determines the corresponding convergence rate. By optimizing in D(m, q) for all probabilistic values average, obtain one-for-all estimator that can theoretically approximate all probabilistic values simultancously with the currently best convergence rate Onn log n)) average. Meanwhile,
propose faster generic estimator by optimizing q for each specific probabilistic value, and we demonstrate that our generic estimate enjoys the best convergence rate for all previously-studied probabilistic values. All of theoretical findings verified in our experiments. Finally, we establish a connection between probabilistic values and the least square regressions used in datamodels, showing that our OFA-A estimator is capable of solving a family of (regularized) datamodels simultaneously.
10

---

Acknowledgements
We thank the reviewers and the area chair for thoughtful comments that have improved our final presentation. YY gratefully acknowledges NSERC and CIFAR for funding support.
References
Burgess, M. A. and A. C. Chapman (2021). "Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling". In: IJCAI, pp. 73-81.
Castro, J. D. Gómez, E. Molina, and Tejada (2017). "Improving Polynomial Estimation of the Shapley Value by Stratified Random Sampling with Optimum Allocation". Computers & Operations Research, vol. 82, pp. 180-188.
Castro, J., D. Gómez, and Tejada (2009). "Polynomial Calculation of the Shapley Value Based on Sampling". Computers & Operations Research, vol. 36, no. pp. 1726-1730.
Covert, I. and S.-I. Lee (2021). "Improving KemneISHAP: Practical Shapley Value Estimation Using Linear Regression", " In: International Conference on Artificial Intelligence and Statistics, pp. 3457-3465.
Dubey, P., A. Neyman, R. Weher (1981). "Value Theory without Efficiency". Mathematics of Operations Research, vol. 6, no. I, pp. 122-128.
Fumagalli, F, M. Muschalik, P. Kolpaczki, E. Hüllermeier, and B. Hammer (2024). "SHAP-IQ: Unified Approximation of Any-Order Shapley Interactions", In: Advances in Neural Information Processing Systems. Vol. 36.
Ghorbani, and J. Y. Zou (2019). "Data Shapley: Equitable Valuation of Data for Machine Learning.. In: International Conference on Machine Learning pp. 2242-2251.
Hammer, P. L. and R. Holzman (1992). "Approximations Pseudo-Boolcan Functions; Applications to Game Theory". Zeitschrift für Operations Research, vol. 36, no. I, pp. 3-21.
Ilyas, A., M. Park, L. Engstrom, G. Leclere, and A. Madry (2022). "Datamodels: Predicting Predictions from Training Data". In: Proceedings of the 39th International Conference on Machine Learning.
Jia, R. al. (2019), "Towards Efficient Data Valuation Based the Shapley Value". In: The 22nd International Conference on Artificial Intelligence and Statisticx, pp. 1167-1176.
Kolpaczki, P. V. Bengs, M. Muschalik, and E. Hüllermeier (2024). "Approximating the Shapley Value without Marginal Contributions". In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. 12, pp. 13246-13255.
Kwon, Y. and J. Y. Zou (2022a). "Beta Shapley: Unified and Noisc-reduced Data Valuation Framework for Machine Learning". In: International Conference on Artificial Intelligence and Statistics, pp. 8780-8802.
(2022b). "WeightedSHAP: Analyzing and Improving Shapley Based Feature Attributions". In: Advances in Neural Information Processing Systems. Vol. 35, pp. 34363-34376.
Li, W. and Y. Yu (2023). "Robust Data Valuation with Weighted Banzhaf Values". In: Advances in Neural Information Processing Systems. Vol. 36.
(2024). "Faster Approximation of Prohabilistic and Distributional Values via Least Squares". The Twelfth International Conference on Learning Representations.
Lin, J., A. Zhang, M. Lécuyer, J. Li, A. Panda, and S. Sen (2022). "Measuring the Effect of Training Data on Deep Learning Predictions via Randomized Experiments", : In: International Conference on Machine Learning, pp. 13468-13504 13504.
Lundberg, S. M. and S.-I. Lee (2017). "A Unified Approach to Interpreting Model Predictions". In: Advances in Neural Information Processing Systems. Vol. 30.
Maleki, S., Tran- Thanh, Hines, Rahwan, and A. Rogers (2013). "Bounding the Estimation Error of Sampling-Basse Based Shapley Value Approximation". arXiv preprint arXiv: arXiv:1306.42666 1306.4265.

---

Marichal, J.-L. and P. Mathonet (2011). "Weighted Banzhaf Power and Interaction Indexes Through Weighted Approxinations of Games". European Journal of Operational Research, vol. 211, no. 2. pp. 352-358.
Moehle, N., S. Boyd, and Ang (2022). "Portfolio Performance Attribution via Shapley Value" Journal Of Investment Management, 20, no. 3, pp. 33-52.
Musco, C. and R. T. Witter (2024), "Provably Accurate Shapley Value Estimation Leverage Score Sampling". arXiv preprint a1X1v22410.01117.
Rozemberczki, B., L.. Watson, P. Bayer, H.-T. Yang, O. Kiss, S. Nilsson, and R. Sarkar (2022). "The Shapley Value in Machine Learning". In: The 3 International Joint Conference Artificial Intelligence and the 25th European Conference Artificial Intelligence, pp.
Ruiz, L. M., F. Valenciano, and J. M. Zarzuelo (1998). "The Family of Least Square Values for Transferable Utility Games". Games and Economic Behavior, vol. 24, no. 1-2, pp. 109-130.
Saunshi, N., A. Gupta, M. Braverman,
Arora (2022). "Understanding Influence Functions and Datamodels via Harmonic Analysis". In: The Eleventh International Conference on Learning Representations.
Shapley, L. S. (1953). "A Value for N-Person .nnalssAnnas of Mathematics Studies, vol. 28, pp. 307-317.
Wang, J. T. and R. Jia (2023a). "A Note on 'Towards Efficient Data Valuation Based on the Shapley V"lue"'. arXiv preprint arXiv:2302. 1431.
(2023b). "Data Banzhaf: A Robust Data Valuation Framework for Machine Learning.. In: International Conference on Artificial Intelligence and Statistics, pp. 6388-6421.
Wang. Y. Zhang, Y. Gu, and T.-K. Kim (2022). "SHAQQ Incorporating Shapley Value Theory into Multi-Agent Q-Learning" Advances in Neural Information Processing Systems. Vol. 35, pp. 5941-5954.
Weber, R. J. (1988). "Prohabilistic Values for Games". The Shapley Value. Essays in Honor of Lloyd Shopley, pp. 101-119.
Wu, M., R. Jia, C. Lin, W. Huang, and X. Chang (2023). "Variance Reduced Shapley Value Estimation for Trustworthy Data Valuation". Computers & Operations Reveurch, vol. 159, 10630S.
Zhang, J. Q Sun, J. Liu, L. Xiong, J. Pei, and K. Ren (2023). "Efficient Sampling Approaches to Shapley Value Approximation" Proceedings of the ACM Management of Data, vol. 1, 1, pp. 1-24.
12

---

A Proof of Theorem 1
Theorem 1. Assume i) ||U||oo S u and ii) 0 < E (2D(m, ()>(q) =u² For & in Algorithm
requires e²
4na" ((m.q)
evaluations of U achieve P(lo Φb12 2 c) S 8 where log 5
8u²
m m
4-- -- (n 8)
D(m,9 9
Σ 2=2
and 7(q) min 25o5n-2
min
n n-s)
9--1
8
n
n
Proof. Following Algorithm let {S be T independent random subsets. Define
T
T
T
= li E S,, [S,] = s] and T.
Σ 1=1
li St.
S
s]
where s = 2.3,....
2. Then, we have
T
T
3. Eii lie E S. | sI U(S)) and क7.-
1
E ll & Sc, |Sc s] US.)).
T:T
T
Define r. + and r.,4 +.. In particular, both [i E St. |St| = s] and [ E St |S.| s] are Bernoulli random variables with
B[rt.l q--1 (m=
1. and E(ri,J] q--1 n2 (M=11
9--1 (n
n
n
Additionally, R and are defined to be vectors in 1R2n-6 such that R26-1 rik+1 Ras 1
72k-1 (=(k++1 and 72k (m- for & E In 3). Note that R is random vector. By Hoeffding's s inequality,
P([R, Ty 2 w) S 2exp (-2Tw²)
where w > 0, and thus
P( - w S P(
U jE[2n-6]
R3 Jj 2 w) S (4n 12) exp (-2Tw²).
Denote the event (E ( (T.)) m (T_, - 2 e) by E2 where 0. Let C be the set that contains all possible configurations C E {0, (2 6)x such that Clr R and IC I i.e., Cj.-- 0 indicates that the k-th subset is sampled from {R C [n] |
T
(j + 3)/2 and i E R] if is odd and {R S
[m] r (j 2)/2 and & R] otherwise. Then,
P(E.) = Σ P(E Σ P(E. P(C).
CEC
Cec
Observe that C can be divided into two separate groups Ceu and C2. such that
Σ P(Ccw)= = R- oooo < w) and Σ
P(C2w) P( - T/100 w).
CewECen
CZuElzu
Therefore,
P(E,) = Σ P(E, Cew) P(CCw) +
Σ P(E, Czw) P(Czu)
CzuECeu
CzuECzu
(8)
< Σ CzuECzu
P(Fg Cew) P(Ccw) + (4n 12) exp (-2Tw²))
For simplicity, we write Po (E₂) instead of P(E, Cew). Additionally, we assume w < 7(q) so that neither T nor TV is zero when conditioned any Ckw. By the Chernoff bound, for any
13

---

>> O, there is
Pc
(Ei)
S
exp
m - - + mo+1 - - c
==2
n2-
=E-M
II
E
exp
(AmoloTs ota)) II Ecc. (exp (Amo+1 (07,, die))
where the equality is due to the independence that stems from the independence of random subsets and that the configuration is fixed. Moreover,
T (U(St o.t.))
BC
exp (Amolot, - 0%.1)]
EC
exp
Xm
Σ
T
Tit
E
EC
exp
Am,
(U(S).
oi.r)
T
j=1
where (St hessstt is obtained by ordering (St
| and i St}. In a similar fashion, we
have
T
Bc
exp (Amotal0Te--a -3
II
Bd
exp
Ama+1 Ti,
(0 U(ST,o))))
By Hoeffding's lemma,
Ams (U (5.)))) -otie)
X2 X²m2zu
Ecaw
exp
exp
T
2T T
Ams+1 (07,5 - U(5
X 112
Ec
exp
S exp
Tír
27 Tú,o
which leads to
Xm (U(St - vite) -cste)
X² X2m2u
II
Bccw
exp
exp
T
21 i,a
T
Ams+1 T
X² X u
Ec
exp
(1i US(tina))
S exxp
2T:
/=1
Therefore,
2222
Po (Ei) S exp
D Ae
27
where = Dm-
T
m
+
T
m
Next, we aim to show that 1 D(m, q)l S D(m, q).
Tia
Tr,
Observe that
1 D(m, g)l 5
1
1
m1g
2
1
1
m
r20-3
T2
r2a-2
T2a 2
2=2
and since |ry - Ty| < w,
1
w
1
Tj
(T)
w)Th
Tj
Tj
Since 7(q) S T, and w <
7(q)
2
T
1
T
Tj
T5
T
14

---

As result, we have ((m, q)l S (m,, q), and thus
u22u²
cc (Ei) S exp
D q) Xe)
T
Combining Eqs. (8) and (9) yields
u2 Dmm, q) Xe + (4n (4n- 12) exp(-2TW
P(E:) < exp
Choosing that minimizes the upper bound yields
Te²
P(E:) < exp
4u2 (m2 q)
+ (4n 12) exp(- -2T
Solving the equation
T² 1u ((m.))
-2Tw yields w = &D(m.q)u² which gives
Te²
2T 4D m, q)u?"
Particularly, to meet the assumption w S 2/a) conclude, provided that I 2m 9)>(g)2u² we have
2 we have have e S (2D(m, q)r(q)uu² To
Te
P
m - (.te) + mm+1107, 37,)) 2 26) 4n enexp(--
(m, quu
Similarly, there is
Te² 40 q)u
P m - -1tt motil07, - oite)) 2 4n exp(
and thus
Te
P( dil 2 8nexpl
4D(m. m. quu
Eventually, we have
Te²
P(IØ 0 2 P
U 16: 0 <E(n]
< 8n expl 4nD(m quu
V
Solving 2 8n² exp( (m..)m yields T >
inD'mmg)'u log Sn Note the assumption e
(2, 2u² can be removed the configuration is fixed with T s7, 1T and T, (n (n-s)g, 17.
B Proofs of Propositions
Proposition 1.
OP 9
()) and DFAA) E O(1). In other words, our OFA-A estimator
achieves the convergence rate of (n logn) simultaneously for all probabilistic values average.
Proof. Let A = {x 1n-1 10 プØ
Tj S Lnf where Ln Ā.-1y, and smooth homeomor-
phism ʃ : + A defined by letting
1
f(x)
- (x1,
In-1 Ln Σ TT
Ln
15

---

n
In other words, both f and f-1 are C
Since the volume of A (n-1))-
there is
(n (n-1) 1)!
SXEA D(f(x), y (Dtf())))))))))))))))))))))) Df(x))dxx = J
Dmm, qidr(m).
n12
Note that det (DS(x)TD[(X)) = for every E A. With A { TVER-- 1}. we have
S Ej= S
(n (n D(f(x), qxx (n-
1)1 yEA
D(f(Ln)).qddy
n² XEE
For simplicity, assume that n = 4, notice that
/ yEA
Vn dd = ! dy !.
1-11-
dy/
Vadys
3 3.4.5
k= (2 1:)
Therefore,
[ ())
N2 2
Vz
22+1
dy
48
yEA
n
n-2
(2 +
9s-1
n1
which leads to
((g) (n-1) 1)!
(2 ==2
9--1
Since D(q) is convex in q. q OFA-A can be directly obtained using the KKT conditions, which is
OFA-A
11-2
Therefore, we have
(n
1)!
n
D(q OFA-A)
T= (2 k)
8
71
Since lim
(n- 1))2
(3), when n is sufficiently large, there is
11m= (2+*)
OFAA) 1
n 2
n1
2
n-2
2 (1- 2) 2 [1
))
< <(6² x(1 - x))
dx
m²
n
8
11
71
Proposition 2. Our OFA-A estimator achieves the convergence rate of (n log n) simultaneously for all semi-values whose probability density functions exist and are bounded. Particularly, Beta Shapley values with a, 3 2 1 all satisfy this condition.
Proof. Let & be a vali-value such that Ps So " w0 ud(=>d((w) So w- w)" "pppppp (w dw such that Pa (w) S for every w [0, 1]. Particularly, we have
n ( ps 5 B
1) 8 -=1)
[ w-1 ww B 8 1-11)
n 1)
(s 1)!(n 8)
B
m,
n.
Therefore,
B2
D Dmm, q OFA-A)
<
+
B2
Σ
< B2T
UFA-A
n1
v vo(n 8)
2=2
2
16

---

Proposition 3. If = 10)==a((((1aa" a)" with 0 < a < 1, which corresponds to the weighted Banzhaf value parameterized by w, then (/ E O(t)) In other words, the OFA estimator achieves the convergence rate of On log n) simultaneously for all WB-a with 1.
Proof.
With A
we have
vs(n-s)
n-2
n-2 1 < a
D(m, q ( = n
n
8
m
5
+
n
8
m
where C' =
Σ
ol( - 8)
==
Then,
D(m.q q OFA-A)
n-2 =C
13 2=2
n 8 n1-
-
1)²
2
(1 - a) a)
8
11 - 1) 2
(1 - a) 1))
11
+ V
1
8
Specifically,
1 2 1
(n - 1)!
s
8
n
(s 1)ls((n - )]((n
2
(n - 1)!2
8
71
n
and
(8 1)ls!(n
8 1).(n 8)!
and thus
-(V
n2 s n 1 2
(a-~1(1 - a) a)m= 2
s
n 1 2
(a' (1 - a)n---1)²
n
8 8 0-1 1
V n - s
3
(n 1)12
= n
(1 - (a-1((1
a)n-a-1) 1)2
(s 1)1s!(11 (n
1)1(1= -ss 8)s
n1 8
(1 a)
n 2
8
Since
s
(1 a)² 2 +
n 8 2 S
s
+
n 8
n
11
Vs(n - s)
there is
n
n 1)
2
(a- - a) m²
+ /
n2 10-1 1 2
(a'(1 a) a))=
n V 8
8 3--1
V n 8
8
S Vvs(n- s(n s) ac)a a) 0)
Sn. (C)a((1 a) a)n= 2
a²(1 - a)²
a²(1 - -a)
Using the identity En 0 (7)) (x + y))
y) (
Σ5 (?)) (2(m-/))
() )z22 (mmm))) there is
n-2 2
12
(2(n= - s)
2aa - 2(n-s)
a (1 - a)m=
= Σ
2
2
2=2
==0
12n
2a -
1
28
2n 8)
1
2aa 1
2(n-s)
(nn 1
+
n
2
220
2
n
22n
For every $21, 1,
(2k)
~
g VI
using the Stirling's 's approximation, and thus
2n
2a
1
2n
n
2n 1
~
n
2
n
n2
22n
Vn
2s
2n 8)
2a
2(n s)
カ- 1
nn
Σ --
j=1
8
n2
8
22
2
v
s(n
8)
v
1
s=1
17

---

where (2a -1)2 1. Therefore, obtain Σx= eventually leads to
S O((=)), which
n-2
D(m, D
q ) S a² 0) 2=2
11 a (")''
-)m= 50(nt).
Proposition 4. For semi-values, (mm, q a E 0(1 if (a has a bounded probability density function ii 1( w(I-wr) dp(w) < cc. Particularly, this condition covers all weighted Banzhaf values and Beta Shapley values with a, 1.
Proof. If ({{))) # 0 (p((T)) # O, respectively), its induced marginal contributions all reside in 92,1 and 05.0 ( and 11 respectively), which is computed exactly using Algorithm 1. Therefore, W.I.OOGG., we assume that p((0, 1)) 1. 1 Suffice it to show that if So w01 w du(w) < co, there is
11
n m E
Specifically,
n-2
11
D(m, q OFA.S)
Σ
m
+
TE
m
++1 S
71
ms +
1 n2
11
m
n1
2
11
w
(1
n
8
n1
wd (1 - du(ww).
n2
8
72
6=2
Since V - w) + v
س=س w
< 2. we have
n
w 2 w (-)--a
w (1 w)n---1 du((w)
8
n- 2 (()) e0 1 w/ n
du(w)= 52 2 S('
w(1 w) dp(w)= E 0(1).
w(1 w)
C Proof of Theorem 2
To prove this theorem, we first state useful definitions and lemmas.
Definition 2 (Semi Inner Product). Let is a real linear space. A semi inner product (::-) on V satisfies, for every x, y, z V and every R, i) (x. y) = (y, x). ii) {ax, y) aix, 1). ii)) (ar + v, (x, z) + (y, 2), and iv) (x, x) O. In addition, we write ||]|| V (x,xx) for every E.
Lemma 1. Let semi inner product on a linear space V be given, and A C V is some affine space. For the following optimization problem
argmin ÆEA
||x - 2
where V, x² is optimal if and only if
(x"
P. x²) =0, Vy A.
(10)
18

---

Proof. Suppose x" verifies Eq. (10), for every A,
ll - pl = || - pll 11 x 212 + 2(x" - P.y - x²) 2 x= -pl..
Next, suppose x² is optimal, and for the sake of contradiction, assume that there is some E A such that (x* p. x² + Write
x for E IR
|| + tz pl ||0 pll + -|==||= + 20(a" - p: z).
Since (x. - 2) * O, there exists some l, E such that 1||==|1 21 - p2 < 0, and thus |10* 10 p|1 || pl1 contradiction.
Definition 3 (Projection Induced by Semi Inner Product). Given semi inner product on a linear spuce V, the set of all optimal solutions to the problem
argmin ZEA
where A C is an affine space and p V, is denoted by (roj To account for the possibility that there are multiple optimal solutions, we extend the definition by letting ( UPES (
Lemma 2. Let V a linear space with a semi inner product. Suppose there are two affine spaces B S A. for every p E V. there is
Proig(Prois((pp))) S Proig((p)).
Proof. We rephrase Lemma ease the proof. For each affine space C V, define Lu A A- for some q E A. Note that the resulting La is independent of the choice of E A and it is subspace in V. Therefore, Eq. (10) equivalent
(x"
2) 0. V2 E L.A.
Suppose x E Proin(Proia by Lemma I, there exists y E ProjA((p)) such that
(y p.a) 0, Va E LA and (x y, x) = 0, vb e B.
Therefore.
(x p. b a) (s y, x) (u p,b x) +
(y p,b x) 0 is due to that x E LB C C..
Lemma 3 (Ruiz et al. 1998, Theorem 12). Let v* be the uniquely optimal solution to
(U()) - U(0)
argmin VER"
Σ
16+1
Σ
Σ 4, U[]]) (())
(11)
SC(x)
iES
/E|m]
where W)s P + Po for 2 < < n.. Then, there is
0r oi Φi dj for every i,j [m].
Recall that the problem (6) is
argminn Σ M6+1 U(S) - Σ 0,
BERE,DER SC(m)
and our goal is to prove that
0: 0 u o5 for every i,j E [n],
which together with Lemma 3 is sufficient to complete proof.
Theorem 2. Let (b", 0*) be the uniquely optimal solution to the problem (6) where T) = Pa-1 + for 2 < s n. Then, there is
87 -% 0% = Φ, Φb for every j. k E [n].
19

---

Proof. The first part of our proof was inspired by (Hammer and Holzman 1992, Lemma 2.9). Let G {U 2 + R), Ag = {U E 9 U(S) = do + Eies a for every S S [n]] and Au = =g E Ag U(ml]) = ((vl)) and U(0) - ( Note that 9 is a linear space and the other two affine spaces with Au S AG. For clarity, each game in Ag is written (ag, al where a E R"
A semi inner product on 9 can be defined by letting (g),92) -Sc(m 16+ 9n (S) for every
gl: 92 E G. Then, [b", 0*] is the projection of U onto AG, whereas (U), v*) is the projection of U onto Ar where v* is the uniquely optimal solution to the problem (11).
By Lemma 2, there is Projar (Proj (LU)) S Pr problem (11) implies that ProjAu ((U)) = {(U()), v'].. and thus
Moreover, the uniqueness in
ProjAr ag (alagg((UU)) ((T)) = ProjAc ({U)) = {[U(0), v']]-
Since [b*, 0*] E pg ({U), the equality Projar (1(6",011}) = {(U(0), v*I] means that (Vo, v*]
is the uniquely optimal solution the problem
argmin (o) SC|nl
Σ
1s+1 (LU(0), v]( - ,,,, 0'']))²²
(12)
Pick j.j E [n] such that i + j, and define an additive game c² E Ag by letting -5) - and otherwise, e is defined similarly. Consider the problem
argmin E AER
((())
(13)
SCIm]
Note that (U),), v*] + l(ee - e²) E Au for every / E R. and the uniqueness the problem (12) suggests that 1" = is the uniquely optimal solution to the problem (13). Removing all constant terms in the problem (13) yields an equivalent problem
argmin tER
Σ
7 (UU(0), v v=1(5) - 07,0)((S) + +t²²
SC(M]: iESjES
Σ
Mo+1 (000)),'((53 - [b*, (S) - =)²
SC(n]: iESjES
Write g [U()). v- 0+) since this problem is convex, letting the derivative equal leads to t
Escin): iES.Jes 70+1 g(S) Esgim) (ES Mo+1 g(S) 0.
Es, iES.jes 7s41
Write g = [900- g] where go = U(()) b' and g = v 0r, there is
Σ
7s+1 g(S) algo 9i) + B
Σ
g
SCIn]: iESjees
Isksn: Ket
n-1
11 - 2)
n-1
3
where a Σ
8 75 and 3 Σ
1s+1-
2
2=2
Similarly, we have E Escho) vESJes M941 g(S) algo + 93) + 3 E
Iskkn kiii lk. and therefore
alg, 9i) =0 0.
Since a > O, we eventually get 9: gy- In other words, wr - 0: = 0z 07. Because i and j are chosen arbitrarily, proof completed.
To be self-contained, we also prove that the problem (6) has only one optimal solution provided that 7) P--1 + P. for 2 < n. W.L.O.G., assume Es Mot1 1. By letting the derivative of the
20

---

problem (6) equal 0, we have = Ax=b b
K
R
A
K
T
K
n1
11
Σ
b1 = Σ 1s+1U(S), Sclm]
7s+1:
==
1s+1
2
s=1
==2
b++1=
Σ
Ms+1U(S) for every j E [n],
21 b and Ji+11 0g for every E [n].
sgin]: jes
Left multiplying A with some row operation matrix gives
K
K
0 K x
2
x²
RA
0
R²
0 5
K R
It is sufficient to prove that the bottom-right x n submatrix of R.A is invertible. Suffice it to show
T + 0 and K. + (n 1)T nk²
+ O. Using (:) ((--)) + we have
2 17+1 > 0.
Using n (²=1)) s()), have
11 - 8
11
K + (n 1)r
7
s²
Ms+11
s=1
s=1
2
2
n 2 n2
Σ
71
7s+1
8
7
8
Let
?/1 and 6. 1/ //y for every E [n]] there is
2 n1
n x²
So
ES
E[
7(1 + (n 1)7) < (n 1)T.
n
71
If 1 > 0, the last inequality is strict as < 1. Otherwise, the first inequality is strict as Var(s]
E s [[s]
D Overview of Estimators
Recall that each probabilistic value is defined to be, for every E [n].
Φ (1)
Σ ps+ (U(S
(14)
SCInj
where p E R nen-negative vector with Σ a for some probability measure l on the closed interval [0, 1]. the induced & referred as semi-value.
(--1) Ps If = Io (1-w)=-sppp
21

---

The Sampling Lift Estimator (Moehle et al. 2022) The sampling lift estimator is based on Φi Bsscii Ui) U(S] where P(S) Ps+1-
The sampling procedure is: sample a subset size & E [n] with P(s) - (--1) and then ii sample a subset uniformly from {R S [n]]i r 1}. For semi-values such that P, Jo w= =))=>d)(w)) where is probability measure on the closed interval [0, 1]. there
is an alternative: i) sample a w [0, 1] according to and then sample subset S = [n] V by incorporating each player in [n]] (i with probability w. With sequence of sampled subsets {S, {5
the i-th estimate is Φ; + Σj= Ui) U(S))).
The Weighted Sampling Lift Estimator (Kwon and Zou 2022a) The formula it is built upon is
Ps+1 (U(SUi) - U())))))((S)))))))))) where P(S) = 9s+1 s!(n - 8)!
Shap Sc(
Φ =
4s+1
n!!
Note that setting p in Eq. (14) leads the Shapley value. The sampling procedure is: i) sample a w uniformly from [0, 1], and then ii) sample a subset S C [n]]i by incorporating each player in Poy
[n]]/ with probability w. Then, the i-th estimate is & 1 1,=1 4., 11 (U(S, U(())
The KernelSHAP Estimator (Lundberg and Lee 2017) This estimator is specific to the Shapley value. It employs the fact that the Shapley value Φ; Shop is the uniquely optimal solution to
argmin $ER"
Σ
8 (
2
U(S) (U(S) ((())-U()) (())
Σ
Pi
Σ ( - U()). (15) iE
[CSC(a]
Note that the weights can be scaled so that the objective is an expectation. sequence of subsets {5,) where 0 S2 & [n]] is sampled according to P(S) (-=?) Then, we have approximate problem as
2
argmin OER"
1 T
Σ
U(S)) - U(1)
Σ
Φi
Φ U(m)) - U(W),
iES,
(E[M]
the uniquely optimal solution which is treated as the estimates, i.c..
A 16
U(m)) + U(0)
B Shap
À
6 In
A '1, T
where A
1 T
Σ 1s, 15 and b (U(())) U(D)): 1s,
5=1
Specifically, 1s, E 1f0,13" such that its i-th entry is 1 if and only if E Sy-
The Unbiased KernelSHAP Estimator (Covert and Lee 2021) Shap to the problem (15) is
The uniquely optimal solution
A -1 b 1n AA 11--1p -b U(m) UU()
Shap
1 1,,,
where A = =[(1ss]] and = E(U((S) - U())) 1n]-
E. otherwise. In other
This estimator employs the fact that Ai, if j and a(n-1) E al words, the estimates of this estimator is
of Shap = A-1 1, I.A - U(m))) UU()
T Σ
where b (U(S)) - U(O) 1sy-
ATA-11,
T j=1
(16)
22

---

Particularly (5,) where 0 & Sj & [ni] are sampled using P(S) (2-1)
Recently, Fumagalli et al. (2024) proved that Eq. (16) can be simplified as
(((a)) - (0) 2 2E T EU(s)) (LiES, %
Shap
The ARM Estimator (Kolpaczki et al. 2024) This estimator is designed according to Φi = Es-P [es[U(()] - Eg-P [KssU((S)]
where (S) ps for every 0 ş S [ni and P (S) Ps+1 for every S S [ni] (Li and Yu 2024, Proposition 8). A sequence subsets {5,) are sampled using and P alternatively,
i... {1 are sampled independently according to Pt, whereas {52x) are sampled independently using PT Then, the i-th estimate is
Φ 1=1
U1Sax11)
LigSa
T,
k=1
where T =E 1 and T.
The AME Estimator (Lin al. 2022) This estimator is restricted to sub-family of semi-values that satisfy So w(1-w) du(w) < co. For such a semi-value Φ. it can be cast as uniquely optimal solution to
argmin B[(Y vER"
X TxTv? v)
where E R and Y are random variables. The sampling procedure is: sample a E (0. 1) using ii) sample a subset S by incorporating each player with probability and then iii) Y = (S) and
X (S) such that X; w'c if E and -m--we otherwise where C So w(1-w) du(w).
With a sequence of subsets (ww), S,) the uniquely optimal solution to the approximate problem
Σ (U(S)) - -
argmin T
j=l
taken as the induced estimates, which is 2 = A) T where the j-th row of A is (S,) and by = U(})).
One Way Improve the AME Estimator The limitation of the AME estimator is that it only applies to semi-values that satisfy fo ((l--dd((w) < sc. Meanwhile, another potential drawback is its need compute the inverse of A T A, though can be circumvented by solving the approximate problem using gradients. In this work, we make a small improvement to the AME estimator by extending applicability to all semi-values, removing (A T A)- the approximate formula and providing more direct analysis of its convergence rate in terms of (e, -)paprooximmtinnn.
Our improvement begins with the observation that X I, suggesting that (+ATA) +I by the law of large numbers and thus (A T A) redundant. Its removal leads simplified formula:
i E S,I U(S))
T
Wi
1 1-w;
We comment that the following proposition is complementary (Lin al. 2022, Proposition 3.3) that claims a similar result.
Propusition 6. Assume that i) ||U| u and ii) p[A, 1 for some 0 < A B 1, the improved AME estimator requires 2m log 2n utility evaluations of U to achieve P([ -0112 >
<) < à where C = min(A,1-Bj
23

---

Proof. Notice that Ø; - - 7 Z, where 125 are ii.d. random variables with E|Zy] = Φ:.
By the Hoeffding's inequality, there is
Te²
P(Iá: 2.1 E) S 2 exp
2
where C' min[A,11BB)) Then,
P(]Lo 2112 2 S S U
Jdi - 0il
- Vn
6
S 2n exp
2nn22
Te²
15iSa
Solving 2n exp
(-2m3
Tea 2
2 leads to T 2n log 2n 6
Remark Notice that the improved AME estimator requires that pl( {0, 13)= Nevertheless, semi-values are additively decomposable on and the part related to pl 1]) can be computed exactly linear time. Therefore, fair to conclude that the improved AME estimator applies to all
semi-values.
The MSR Estimator (Wang and Jia 2023b) The methodology of this estimator is limited to weighted Banzhaf values parameterized with 0 a 1 (Wang and Jia 2023b, Appendix C.2). Precisely, Ps (1 -a a)=- Each subset is sampled by incorporating each player with probability a, and then the i-th estimate is
T Σ T, Uss
Σ (U(S))LESS a. T j=1
where T = E lees, and T = E/=1 liss,
The GELS Estimator (Li and Yu 2024) This estimator is established using the fact that Φi #1 where v E I=++ is the uniquely optimal solution to
Σ Ps (U(Sn(m)
2
Σ BES
argmin VER*+1
1i
0C DCS[[++1]
The subsets {5,} where @ ç S) & In + 1] are sampled using P(S) x Ps. and then the i-th estimate is
$. = Σ
n
1 Ps (0, - in+1)
where 0g = 1 ΣT T% j=1 U(S n [n]) Il kes, and Tą = Σ/ j= REES
The Complement Estimator (Zhang et al. 2023) The complement estimator is specific to the Shapley value using the fact that
Shap
1 Σ
n (²=1)² (U(S U(HN))))(((((UU)))
SCIn
The sequence of subsets {5 is sampled using i) sample a subset size E [m] uniformly, and then sample subset S uniformly from {R C [n] = s}. Then, the i-th estimate is
n Gr. where Φi
Shap 3
( Sy, s] e $ Sy, n 8, =s]
n
Th,
2 U(S)) ((n](S,) and Ti, Σ
([i E Sy, 3] + Li $ S -3 =])
24

---

The Group Testing Estimator (Jia et al. 2019) We introduce the improved version presented by Wang and Jia (2023a). Note that this estimator is specific the Shapley value. A sequence of subsets {5,} are independently sampled according to: i) sample subset size E {n] using P(s) & s(x+1-.. and then ii) sample a subset uniformly from {R [n i-th estimate
s). Then, the
2 1= T
1 Σ LU(S ([i S g 5,1 - [i E 5 E S,
Shap
The Permutation Estimator (Castro et al. 2009) using the formula
This estimator is specific to the Shapley value,
Shap Σ
TENI
where IT contains all permutations of [n) and ((r) is the subset that contains all players preceding
in Thus, it samples sequence of permutations (Mz = from II uniformly with replacement, and
25hap then the i-th estimate 0, 1 エ (U(P) Ui) (PP())))))
The WeightedSHAP Estimator (Kwon and Zou 2022b) As mentioned in the main paper, it is based on
6 my (RgiaN, - (R)
where m, (2=1) Ps- For each player [n]. samples a sequence of permutations { of [n]]i. Then, the corresponding estimate is Φ Σ m,di, where Φi.k
+ E (1))
and (mr,) is the subset that contains the first h players
in T.
The SHAP-IQ Estimator (Fumagalli al. 2024) Recall that its underlying formula is
Φ = Pm. -U[(m)) - (()) + 2H Eøçsg[n| [[(n s)m, sm,+1 ligs) (U(S) - U())]
where m, = (==1) Ps. H Σラ J. and P(S) x (s=1) -1 Therefore, a sequence of subsets
{5 where 0 C Sj S [n] is sampled using P(S) x ("=?) -1 and the i-th estimate is
T
6, = Pm (U(ml) - U()) + 2H
Σ
(U(S)) U()) ((n s)m,lies; - sm lggs))
T j=1
25

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our claimed theories are presented Section and are empirically verified in Section 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Proposition 3 demonstrates that our OFA-A estimator does not rival the previously best estimator for weighted Banzhaf values in terms of convergence rate, which is price to pay for using fixed sampling scheme for all probabilistie values.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
26

---

Answer: [Yes]
Justification:
We have provided detailed proofs in the Appendices A, B and C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Our experiment settings are stated in Section 5, and our method is presented in Algorithm
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
27

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The datasets we used are from open resources, and our code will released github repo
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurIPS code and data submission guidelines (https://nips.co
public/guide http//uudees////eee weweee/eeooeSuummmeceeeeeee as aasssnooliccyy for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips.com wttpccccpppcccccccc.. gui des/ CodeSubmi ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Our experiment settings are stated in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Our experiment results in Section are all reported with standard deviation using 30 random seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
28

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: is stated in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't I make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: wttpeurrps.ccppullllepee cewuideeilllllnnimi ines?
Answer: [Yes]
Justification:
We have complied with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work focuses on the convergence rate of estimators for probabilistic values that do not appear to have any significant societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
29

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work focuses the convergence rate of estimators for probabilistic values that do not appear to pose any risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer:
[Yes]
Justification:
It is stated in Section 5.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
30

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi th codee.. . com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not introduce any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our work does involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
31

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "mYt3yIBCTK", "reviewer": "Reviewer_2hZa", "summary": "The paper studies efficient estimators for probabilistic values, with applications in data valuation and feature attribution. Since the computation of probabilistic values requires an exponential number of utility function evaluations, efficient estimation of probabilistic values is necessary. Existing approaches for this either contain amplifying scalers that degrade the convergence rate or fail to perform maximum sample re-use (i.e. utility evaluations are not used to update the probabilistic value estimates for all players). The paper proposes an algorithm that solves both the above challenges at once, thus providing a one-for-all estimator that achieves superior time complexity on average. The theoretical results are supported by several experimental results that validate improvements in speed of convergence as compared to the previous methods.", "questions": "Please see the weaknesses", "limitations": "Although broader societal impacts may not apply to this paper, this work should have a section on the limitations of the proposed algorithm in a separate section in addition to the brief discussion in Proposition 3.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides a simple algorithm that updates the probabilistic values of all n players at once, thus improving our ability to compute multiple probabilistic values and allowing us to evaluate the best one for downstream applications. Since the exponential number of utility evaluations hinders the ability to perform this evaluation, this paper could be an important step towards understanding how to improve the time complexity of such methods. The paper carefully compares existing methods under the axes of amplifying scalers and maximum sample reuse, providing an intuitive goal for improved estimation algorithms. The experimental assessment supports the theory developed in the paper regarding (\\epsilon, \\delta) convergence rates.", "weaknesses": "The proposed algorithm depends on obtaining a good sampling vector q. Although the paper addresses this in sections 4.1 and 4.2, it would be helpful to discuss this further (e.g., challenges in solving the minimization problem in 4.1, alternatives to the faster generic estimator in 4.2, etc). \n\nThe experimental results vary the size of the dataset up to 256. In real-world data valuation tasks with larger sample sizes, would it be harder to scale this method despite beating all the baselines? \n\nIt would be helpful to discuss the limitations of the proposed approach both in terms of theoretical analysis and applicability to tasks like data valuation (It does talk about the limitations under proposition 3, but it would be helpful to have a separate discussion on limitations)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful comments. We address your concerns below.\n\t\n**Q: Discuss further the sampling vector q.**\n\t\nA: Thank you for this suggestion. The optimization problems in Section 4.1 and 4.2 are solved in closed-form, see Proposition 1 and Eq. (4). These closed-form solutions can be computed in O(n) time. \n\t\nThe two sampling vectors are complementary to each other: using $\\mathbf{q}^{\\mathrm{OFA-A}}$ we can collect samples and (re)use them for any probabilistic value, while $\\mathbf{q}^{\\mathrm{OFA-S}}$ achieves better performance but depends on the underlying probabilistic value. \n\t\nWe have added the above discussion and limitation to our revision.\n\t\n**Q: The experimental results vary the size of the dataset up to 256. In real-world data valuation tasks with larger sample sizes, would it be harder to scale this method despite beating all the baselines?**\n\t\nA: In our experiments, we restricted the size of datasets for the sake of computing the **exact** groundtruth values, to which we compare each baseline. In practice, the limiting factor (for any valuation method) is on computing the utility $U(S)$, which often involves training a (large) deep neural network on the subset $S$ of training data. To scale up, one can simply train the network with few active layers (from a pre-trained model). This heuristic is used in many existing valuation methods and applies equally well to our method.", "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": "aH71HvPEdf", "reviewer": "Reviewer_DfL8", "summary": "This paper presents a novel framework called One-Sample-Fits-All (OFA) for efficiently approximating probabilistic values used in feature attribution and data valuation, such as Beta Shapley values and weighted Banzhaf values. The framework maximizes sample reuse and avoids variance amplification, making it capable of approximating all probabilistic values simultaneously. The authors leverage the concept of \n(ϵ,δ)-approximation to derive a formula that determines the convergence rate, which they use to optimize the sampling vector. The proposed framework includes two estimators: OFA-A, which is optimized for all probabilistic values on average, and OFA-S, which is fine-tuned for each specific probabilistic value. Empirical results demonstrate that OFA-A achieves the fastest known convergence rate for Beta Shapley values and competitive rates for weighted Banzhaf values.", "questions": "The paper does provide an extensive theoretical proof regarding scalability of the pipeline, but there is limited explorations in terms of  emperical results for scalable real life datasets and problems. It would be nice to see some comments on that. While the scalability is theoretically supported, further empirical validation on larger datasets would strengthen the claim.", "limitations": "Yes the authors have indicated the weakness of their proposed method", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a novel one-sample-fits-all framework that can approximate a wide range of probabilistic values efficiently, addressing a significant gap in the literature. The use of (ϵ,δ)-approximation to derive convergence rates and optimize the sampling vector adds strong theoretical backing to the proposed method.\n\n2. The OFA-A estimator achieves the best known time complexity for certain probabilistic values, indicating its computational efficiency.", "weaknesses": "1. The empirical results are demonstrated on a classification task using LeNet and small datasets like MNIST. \n\n2. The paper does not discuss much about the implementation details - the theoretical concepts and optimization processes might be complex for practitioners without a strong background in cooperative game theory and advanced statistical methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your review and address your concerns below.\n\t\n**Q: The paper does not discuss much about the implementation details.**\n\t\nA: We agree that implementation details are important. We included the pseudocode in the submission and we will release our pytorch code after this work is made public.\n\t\n**Q: The paper does provide an extensive theoretical proof regarding scalability of the pipeline, but there is limited explorations in terms of empirical results for scalable real life datasets and problems.**\n\t\nA: In our experiments, we restricted the size of datasets for the sake of computing the **exact** groundtruth values, to which we can compare each baseline. Without the ground-truth values, we wouldn't be able to plot the curves in Figure 1.\nIn practice where $ n $ is large, different baselines will return different approximations and it would be impossible to claim which is better **in terms of convergence**, but these approximations can always be used for some downstream applications, such as noisy label detection.", "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": "t2YXYphQIf", "reviewer": "Reviewer_k6r4", "summary": "The paper discusses a novel framework for efficiently approximating probabilistic values, such as Beta Shapley values and weighted Banzhaf values. These values are computationally expensive to calculate exactly, calling for approximation techniques.\n\nSpecifically, they propose the One-sample-Fits-All Framework (OFA), which adheres to the principle of maximum sample reuse and not increasing variance. Besides, two variants, OFA-A (and OFA-S) optimize for all probabilistic values on average (and specific probabilistic values), respectively.\n\nOverall, they provide an efficient solution for approximating multiple probabilistic values simultaneously, with theoretical and practical implications.", "questions": "See the weaknesses part.", "limitations": "The limitations are not discussed explicitly in the main text.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The quick approximation of probabilistic values is important.\n\n2. The writing flow is clear and easy to follow (especially Sec. 3).\n\n3. The theoretical part seems reasonable.", "weaknesses": "1. The variances (and/or biases) of the estimations are not thoroughly examined; instead, they only consider whether the variances will increase based on the range/value of $m_s$.\n\n2. The authors emphasize \"the principle of maximum sample reuse\" all the time, and treat it as a key principle. However, they do not provide a formal definition of this principle.\n\n3. Similarly, a formal definition of \"one-for-all estimators\" is missing.\n\n4. Line 95 mentions that an existing work already achieves $O(n/\\epsilon^2 \\log (n/\\sigma))$, while the proposed OFA-A is $O(n \\log (n))$. The significance of the contribution is unclear.\n\n5. What does $q_s$ in line 159 mean?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments! This response is to address your concerns. \n\t\n**Q: The variances (and/or biases) of the estimations are not thoroughly examined; instead, they only consider whether the variances will increase based on the range/value of $ m_{s} $.**\n\t\nA: Please let us know if our understanding of your question is not correct, and we'd be happy to respond to any further questions.  \n\t\nOur argument starts from the proof of the convergence rates of the mentioned estimators, where Hoeffding's inequality is always a key step. As a simple demonstration that applies to Eq. (1), let $ \\\\{ X_i \\\\}\\_{i=1}\\^{T} $ be $ T $ i.i.d. random variables such that $ X_{i} \\in [a,b] $. (The non-identical case may be more complicated but the intuition remains the same.) Then, by Hoeffding's inequality, $ P(|c\\cdot\\overline{X} - c\\cdot\\mathbb{E}[X_{i}] |\\geq \\epsilon) \\leq 2\\exp\\left( -\\frac{2T\\epsilon^{2}}{c^{2}(b-a)^{2}} \\right) $ where $ \\overline{X} = \\frac{1}{T}\\sum_{i=1}^{T}X_{i} $. Solving $ 2\\exp\\left( -\\frac{2T\\epsilon^{2}}{c^{2}(b-a)^{2}}\\right) \\leq \\delta $, we have $ T \\geq \\frac{2c^{2}(b-a)^{2}}{\\epsilon^{2}}\\log\\frac{2}{\\delta} $, from which we observe that to improve the convergence rate (equivalently, to minimize $ T $) it is necessary to make $ c^{2} $ as small as possible. Meanwhile, $ \\mathrm{Var}[c\\cdot X_{i}] \\leq \\frac{c^{2}(b-a)^{2}}{4} $ and the equality could hold, indicating that $ c> 1 $ amplifies the worst variance. Intuitively, the above argument illustrates that for $ m_{s} > 1 $, the theoretical convergence rate may deteriorate due to amplified variance.\nMoreover, we have empirically verified that this indeed leads to slower empirical convergence in Figure 1. We'll make this part clearer in the revision.\n\t\n\t\n**Q: The authors emphasize \"the principle of maximum sample reuse\" all the time, and treat it as a key principle. However, they do not provide a formal definition of this principle.**\n\t\nA: We would like to elaborate on what is mentioned in lines 117-118 regarding the principle of maximum sample reuse. Precisely, any of the considered estimators iteratively samples a subset $ S \\subseteq [n] $ and then uses $ U(S) $ to update **some** of the current estimates $ \\\\{ \\hat{\\phi}_i \\\\}\\_{i\\in [n]} $. An estimator is said to meet the principle of maximum sample reuse if every $ U(S) $ is employed in updating **all** the current estimates. We will formally define this principle in our revision.\n\t\n\n**Q: Similarly, a formal definition of \"one-for-all estimators\" is missing.**\n\t\nA: We'd like to add more details to our definition of one-for-all estimators. Previous works only considered the scenario of approximating **one** specific probabilistic value. As a result, the designed procedure may not be able to reuse the sampled subsets for any other probabilistic values (without amplifying variance). By contrast, a one-for-all estimator is able to sample subsets **once** and then obtain approximations for **all** probabilistic value. We will formally define one-for-all estimators in our revision. Thank you.\n\t\n**Q: Line 95 mentions that an existing work already achieves $ O(\\frac{n}{\\epsilon^{2}}\\log\\frac{n}{\\delta}) $, while the proposed OFA-A is $ O(n\\log n) $. The significance of the contribution is unclear.**\n\t\nA: Thank you for pointing out the misleading information contained in line 95. Precisely, Wang and Jia (2023) proposed an efficient estimator **only** for the Banzhaf value, and their convergence rate analysis is exclusive to the Banzhaf value. In contrast, OFA-A only needs to collect samples once which can then be used to approximate all probabilistic values (including Banzhaf). We have corrected this misprint. \n\t\nThe significance of our theoretical results, e.g., includes:\n\t\n- As indicated by Proposition 2, the proposed OFA-A estimator achieves the convergence rate $ O(n\\log n) $ **simultaneously** (i.e., sample subsets once to obtain all approximations) for all Beta Shapley values of interest. In contrast, the previous convergence analyses are limited to only **one** specific probabilistic value;\n\t\n- The well-known Shapley value belongs to the family of Beta Shapley values of interest and the previous best convergence rate $ O(n(\\log n)^{2}) $ is achieved by the group testing estimator. By contrast, our proposed OFA-A achieves a slightly better rate $ O(n\\log n) $.\n\t\n**Q: What does $ q_{s} $ in line 159 mean?**\n\t\nA: $ q_{s} $ used in Algorithm 1 is the probability of sampling a subset from $ \\\\{ T \\subseteq [n] \\mid |T| = s+1 \\\\} $. We have made it clearer in the revision.", "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": "QvasDtxDQY", "reviewer": "Reviewer_YTCS", "summary": "This paper studies efficient estimation of probabilistic values. It proposes an algorithm which can approximate any probabilistic value with average convergence $O(n \\log n)$. It also proposes an improved algorithm for specific cases.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper provides a solid contribution over previous work.\n\nThe paper is well written and explains the main ideas clearly.", "weaknesses": "If I’m understanding correctly, the algorithm approximates “any” instead of “all” probabilistic values, I.e. it’s a generic algorithm which can approximate any probabilistic value, but it can’t approximate all values simultaneously (one needs to rerun the algorithm for different values). \n\nHow valuable is the average convergence rate? It’s likely that the easy ones contribute more, and the average rate for the cases of interest is worse.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your review! Here is our response to your concerns.\n\t\n**Q: If I’m understanding correctly, the algorithm approximates “any” instead of “all” probabilistic values, i.e. it’s a generic algorithm which can approximate any probabilistic value, but it can’t approximate all values simultaneously (one needs to rerun the algorithm for different values).**\n\t\nA: We'll make it clearer on this part in the revision. As presented in line 12 of Algorithm 1, the coefficients $ \\{ m_{s} \\} $ (which vary for different probabilistic values) do not appear in the approximation procedure, i.e., Lines 1-11, meaning that the estimates $ \\\\{ \\hat{\\phi}\\_{i,k^+}\\^{+}, \\hat{\\phi}\\_{i,k^-}\\^{-} \\\\} $ can be translated to any probabilistic value. Therefore, the proposed algorithm is capable of sampling subsets **once** and then obtain the approximations of **all** probabilistic values. There is no need to rerun the algorithm (line 1-11) for different values; only the last aggregation step (which is trivial) needs to be rerun (line 12).\n\t\n**Q: How valuable is the average convergence rate? It’s likely that the easy ones contribute more, and the average rate for the cases of interest is worse.**\n\t\nA: We agree that not all probabilistic values may be of interest. Nevertheless, as proved in Proposition 2, our OFA-A estimator still achieves the convergence rate $ O(n\\log n) $ **simultaneously** for all Beta Shapley values of interest. To our knowledge, the Beta Shapley values are not easy to estimate and they have important applications in practice. For example, the previous best theoretical convergence rate $ O(n(\\log n)^{2}) $ for Beta$ (1,1) $ (i.e., the well-known Shapley value) is achieved by the group testing estimator, while the rate $ O(n(\\log n)^{3}) $ for Beta$ (\\alpha,\\beta) $ with $ (\\alpha=1, \\beta>1) $ or $ (\\alpha>1, \\beta=1) $ is instead achieved by the GELS estimator. Therefore, the significance of OFA-A is twofold: i) it improves the theoretical convergence rate for some Beta Shapley values and ii) it achieves the convergence rate $ O(n \\log n) $ **simultaneously** for all Beta Shapley values of interest. These results indicate that the average rate in Proposition 1 is not merely contributed by ''easy'' probabilistic values.", "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:

Meta-review: **Summary:** This paper proposes an estimation framework for all probabilistic values (such as Shapley values), where the approximation guarantees are given simultaneously across all values.

**Novelty and Clarity:** The perspective of simultaneously approximating all probabilistic values is novel and the topic of values is itself very timely. The paper is written and organized well, although certain expressions used (such as "maximum sample reuse" and “one-for-all estimators") are idiosyncratic and need to be defined and discussed, and certain connections to prior work need to be done more carefully, as corrected in the discussions.

**Significance:** One thing that is uncertain is whether simultaneous estimation is indeed important in downstream tasks. This is used as part of the motivation of the proposed perspective but is not elaborated on eventually, which diminished from the significance of the results. Another issue raised by reviewers is that the requisites for making the method work may not always be available (e.g., a good sampling vector). Also, empirical evaluation is hard to judge because, due to intractability, the experiments can’t quite scale to show that the method works in larger problems.

***

Not connecting the importance of estimating all values simultaneously to downstream tasks somewhat weakens the significance of the work. However, with a few pointers in this direction and ironing out some of the terminology and connections to prior work, this can become a solid paper on a timely and potentially impactful topic.
Decision: Accept (poster)