One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently

Authors: weida  li
yaoliang  yu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 16:18:28

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.

Main paper: 
 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 on. One popular methodology is to 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-performing one (Kwon and Zou 2022b) .In general, probabilistic values can only be approximated as they require exponentially many utility evaluations to compute exactly. Thus far, there has been a 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 Jia (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 simultaneously 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 One-sample-Fits-All (OFA) framework parameterized by a 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 (ϵ, δ)-approximation, i.e., P (∥ φ -ϕ∥ 2 ≥ ϵ) ≤ δ where ϕ refers to some probabilistic value and φ is its estimate, we theoretically identify a 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:(i) Our OFA-A achieves the convergence rate O(n log n) for all probabilistic values on average.Notably, O(n log n) is the currently-known best time complexity for some probabilistic values. (ii) For Beta Shapley values parameterized by α, β ≥ 1 (Kwon and Zou 2022a), our OFA-A estimator requires O(n log n) utility evaluations to achieve an (ϵ, δ)-approximation simultaneously. Note that α = β = 1 corresponds to the commonly-used Shapley value (Shapley 1953) . For the Shapley value, the previous best convergence rate is O(n(log n) 2 ),1 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 is unknown. For Beta Shapley values with (α = 1, β > 1) or (α > 1, β = 1), the previous best estimator requires O(n(log n) 3 ) utility evaluations instead (Li and Yu 2024 , Proposition 4 and Remark 3). (iii) For weighted Banzhaf values parameterized by 0 < w < 1, the time complexity of our OFA-A is O(n 3 2 log n), not rivaling the previous best convergence rate O(n log 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 log n) for both Beta Shapley values (with α, β ≥ 1) and weighted Banzhaf values.In our experiments, the empirical convergence rates align well with the theoretical ones derived using the concept of (ϵ, δ)-approximation. Additionally, we establish a connection between probabilistic values and the least square regressions employed in datamodels (Ilyas et al. 2022) , demonstrating that our OFA-A estimator can solve a 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 to a 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, 2, . . . , n} 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\i and S ∪ i instead of S\{i} and S ∪ {i}, respectively. Meanwhile, (lowercase) s denotes the cardinality of the set (uppercase) S. Then, each probabilistic value can be written asϕ i = ϕ i (U ) = S⊆[n]\i p s+1 [U (S ∪ i) -U (S)]where U : 2 [n] → R is a utility function and p ∈ R n is a non-negative vector such that n s=1 n-1 s-1 p s = 1. Take data valuation as an example, U (S) may measure the performance of models trained on S ⊆ [n], with which ϕ i (U ) can be interpreted as the contribution of the i-th data point to the performance of models trained on [n] .If there exists a (Borel) probability measure µ on the closed interval [0, 1] such that p s = 1 0 w s-1 (1w) n-s dµ(w), then the resulting probabilistic value is referred to as a semi-value (Dubey et al. 1981) . If µ represents a Dirac delta distribution δ a , the corresponding probabilistic value is referred to as the weighted Banzhaf value parameterized by a, or WB-a. For Beta Shapley values, denoted by Beta(α, β), µ(A) = A w β-1 (1 -w) α-1 dw. In practice, the considered range of α or β is [1, ∞) (Kwon and Zou 2022a,b) . Particularly, Beta(1, 1), whose µ is the uniform distribution (over [0, 1]), corresponds to the Shapley value.We will use the standard notion of (ϵ, δ)-approximation to analyze a (randomized) estimate φ of some probabilistic value ϕ.Definition 1. We say a (randomized) estimate φ achieves an (ϵ, δ)-approximation of ϕ if P (∥ φ -ϕ∥ 2 ≥ ϵ) ≤ δ.For instance, Wang and Jia (2023b, Theorem 4.9) proved that their proposed estimator requires O( n ϵ 2 log n δ ) utility evaluations to achieve an (ϵ, δ)-approximation for WB-0.5, provided that ∥U ∥ ∞ ≤ 1. When ϵ and δ are considered fixed constants, we then simply say the estimator converges at O(n log n) rate. 
motivations: 
 One-For-All Estimators In this paper, an estimator is referred to as one-for-all if it is capable of sampling subsets Once to approximate All probabilistic values.Though existing estimators are not designed to 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 al. 2022) as an example, its approximation is based onϕ i = E S⊆[n]\i [U (S ∪ i) -U (S)] where P (S) = p s+1 .If we fix the probability of sampling S to be the one, denoted by q ∈ R n , for the Shapley value, there isEQUATIONwhich is the weighted sampling lift (WSL) estimator employed by Kwon and Zou (2022a) . Therefore, we can store the accumulated results {U (S ∪ i) -U (S)} separately for each subset size of S so that they can be reweighted to be any probabilistic value.The Effect of Amplifying Factors However, the scalars { ps+1 qs+1 } potentially introduce a nonnegligible factor into the theoretical convergence rate. To demonstrate, we take the WSL estimator as an example. In this case, φi = 1T T t=1 X t where {X t } T t=1 are i.i.d. random variable such that P (X t = ps+1 qs+1 (U (S ∪ i) -U (S))) = q s+1 and thus E[X t ] = ϕ i . Assume that ∥U ∥ ∞ ≤ 1, by the Hoeffding's inequality, P (| φi -ϕ i | ≥ ϵ) ≤ 2 exp -T ϵ 2 8C 2 where C = max 1≤k≤n p k q k . By solving 2 exp -T ϵ 2 8C 2 ≤ δ, we eventually obtain T ≥ 8C 2 ϵ 2 log 2 δ and therefore the convergence rate of φi is O( C 2 ϵ 2 log 2 δ ). Consequently, if C → ∞ as n → ∞, this theoretical convergence rate deteriorates asymptotically. For the Banzhaf value,p k = 1 2 n-1 ; since q k = (k-1)!(n-k)! n! , if k = n+1 2 , there is p k q k ∈ Θ(n 1 2 ) by the Stirling's approximation d! ≃ √ d d e d. Therefore, C 2 introduces a factor of Θ(n) 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 2 is as worst as Θ(2 2n ). To generalize this idea, a formula is said to contain an amplifying factor if it involves γ • U (S) such that γ → ∞ as n → ∞.Regarding this, we notice that Kwon and Zou (2022b) resort to a one-for-all estimator based onEQUATIONwhere m s = n-1 s-1 p s 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 s does not grow as n → ∞.The Principle of Maximum Sample Reuse However, estimators designed according to Eqs. ( 1) 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 { φi } i∈ [n] . As analyzed by Zhang et al. (2023, Section 4.2) , estimators based on sampled marginal contributions {U (S ∪ i) -U (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 = p n (U ([n]) -U (∅)) + 2HE ∅⊊S⊊[n] [((n -s)m s 1 i∈S -sm s+1 1 i̸ ∈S )(U (S) -U (∅))] (3) where m s = n-1 s-1 p s , H = n-1 j=11 j , and P (S) ∝ n-2 s-1-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, it is apparent that Eq. ( 3) contains an amplifying factor H ∈ Θ(log n). 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 properties for estimators to possess as P1: The underlying formula contains no amplifying factors and P2: Each sampled subset is used to update all the estimates { φi } n i=1 . In Figure 1 , we provide some experiment results while setting n = 24 to support our 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 P1. 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 U (i) -U (∅) is as large as 2 n n ! In Table 1 , we summarize the previous estimators in 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 is MSR for weighted Banzhaf values; both of them follow P1 and P2.Table 1 : A scope of "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 its scope, while P2 means whether each sampled subset is used to update all the estimates { φi } n i=1 . For AME, the range of γ in γ • U (S) could be (0, ∞), independent of n. Originally, AME only applies to a subfamily of semi-values, but we extend it for all semi-values in Appendix D. 1 : Comparison of ten one-for-all estimators. Beta(α, β) 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 no 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 on 24 data from FMNIST. All the results are averaged using 30 random seeds.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?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 crossreferenced. • 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 to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
main results: 
 The framework we propose is built uponEQUATIONwhere m s = n-1 s-1 p s and each expectation is taken over the corresponding uniform distribution. For simplicity, we writeϕ + i,s = E i∈R,r=s [U (R)] and ϕ - i,s-1 = E i̸ ∈R,r=s-1 [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,k } k=1,n-1,n and {ϕ - i,k } k=0,1,n-1 can be calculated exactly using 2n + 2 utility evaluations of U , our focus is to efficiently approximate {ϕ + i,s , ϕ - i,s } 2≤s≤n-2 . The proposed framework is presented in Algorithm 1; q j is the probability of drawing a subset of [n] with size j + 1. To facilitate the choice of the sampling vector q ∈ R n-3 appearing in Algorithm 1, our first step is to theoretically ascertain a key formula that effectively determines the convergence rate of Algorithm 1.Theorem 1. Assume i) ∥U ∥ ∞ ≤ u and ii) 0 < ϵ ≤ 2D(m, q)γ(q) 2 u 2 . For φ in Algorithm 1, it requires 4nu 2 D(m,q) ϵ 2 log 8n 2 δ evaluations of U to achieve P (∥ φ -ϕ∥ 2 ≥ ϵ) ≤ δ where D(m, q) = n-2 s=2 n q s-1 m 2 s s + m 2 s+1 n -s and γ(q) = min 2≤s≤n-2 min q s-1 • s n , q s-1 • (n -s) n .We remark that D(m, q) is jointly convex in m and q. The second assumption in Theorem 1 can be removed if we pre-allocate the number of sampled subsets for each ϕ + i,s or ϕ - i,s and draw subsets in a predetermined order; see the proof in Appendix A for details. Precisely, let T + i,s be the number of subsets for estimating ϕ + i,s , and define T - i,s similarly; then the pre-allocated numbers are T + i,s ≈ s•qs-1 n T and T - i,s ≈ (n-s)qs-1 n T , which are the expected values of T + i,s and T + i,s while using Algorithm 1; T refers to the total number of sampled subsets. By Theorem 1, the convergence rate of Algorithm 1 is O(D(m, q) • n log n), and thus achieving the currently best convergence rate O(n log n) requires D(m, q) ∈ O(1).Algorithm 1: The One-Sample-Fits-All (OFA) Framework Input: A utility function U : 2 [n] → R, a positive probability vector q ∈ R n-3 , and a total number T of samples Output:Estimates to ϕ + i,k + and ϕ - i,k -with i, k + ∈ [n] and 0 ≤ k -≤ n -1 φ+ i,k + ← ϕ + i,k + and φ- i,k -← ϕ - i,k -for i ∈ [n], k + ∈ {1, n -1, n} and k -∈ {0, 1, n -1} φ+ i,k ← 0, T + i,k ← 0, φ- i,k ← 0 and T - i,k ← 0 with i ∈ [n] and 2 ≤ k ≤ n -2 for t = 1, 2, . . . , T do Sample s t from {2, 3, . . . , n -2} according to q Sample S t uniformly from {R ⊆ [n] | r = s t } v ← U (S t ) for i = 1, 2, . . . , n do if i ∈ S t then φ+ i,st ← T + i,s t T + i,s t +1 φ+ i,st + 1 T + i,s t +1 v and T + i,st ← T + i,st + 1 else φ- i,st ← T - i,s t T - i,s t +1 φ- i,st + 1 T - i,s t +1 v and T - i,st ← T - i,st + 1 Aggregation Phase: φi = n s=1 m s ( φ+ i,s -φ- i,s-1 )To obtain our one-for-all estimator, our goal is to find a q OFA-A such that D(m, q OFA-A ) ∈ O(1) for as many m as possible. To this end, we define q OFA-A to be the uniquely optimal solution to argminq∈R n-3 D(q) = m∈∆ D(m, q)dν(m)where ∆ = {m ∈ R n | m s ≥ 0 and n s=1 m s = 1} and ν is the uniform distribution on ∆. In our work, our OFA-A estimator refers to the use of q OFA-A in Algorithm 1.Proposition 1. q OFA-A s-1 ∝ 1 √ (s)(n-s)and D(q OFA-A ) ∈ O(1). In other words, our OFA-A estimator achieves the convergence rate of O(n log n) simultaneously for all probabilistic values on average.Our next proposition provides a condition on µ for semi-values such that our OFA-A estimator achieves the convergence rate of O(n 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 simultaneously.Proposition 2. Our OFA-A estimator achieves the convergence rate of O(n log n) simultaneously for all semi-values whose probability density functions exist and are bounded. Particularly, Beta Shapley values with α, β ≥ 1 all satisfy this condition.To our knowledge, the previous theoretically-fastest estimator for the Shapley value is demonstrated by Wang and Jia (2023a, Theorem 6) as O(n(log n) 2 ). By contrast, our OFA-A estimator achieves the convergence rate of O(n log n). Meanwhile, it also surpasses the previous best time complexity for Beta Shapley values with (α = 1, β > 1) or (α > 1, β = 1), which is O(n(log n) 3 ) (Li and Yu 2024, Proposition 4 and Remark 3). Remarkably, our OFA-A estimator enjoys this fastest convergence rate simultaneously for a broad subfamily of probabilistic values . Proposition 3. If p s = a s-1 (1 -a) n-s with 0 < a < 1, which corresponds to the weighted Banzhaf value parameterized by w, then D(m, q OFA-A ) ∈ O(n 1 2 ). In other words, the OFA estimator achieves the convergence rate of O(n 3 2 log n) simultaneously for all WB-a with 0 < a < 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 a factor of n 1 2 . Nevertheless, we will demonstrate that our generic estimator, which is expected to be faster than our OFA-A estimator, achieves the best convergence rate for all weighted Banzhaf values.Our faster generic estimator (OFA-S) is obtained via optimizing q for each Specific m. Precisely, for each m, we haveq OFA-S s-1 ∝ m 2 s s + m 2 s+1n -s where q OFA-S = argminEQUATIONwhich can be obtained using the Cauchy-Schwarz inequality. For the Shapley value, q OFA-S = q OFA-A .Our next proposition specifies a sufficient condition for semi-values such that D(m, q OFA-S ) ∈ O(1).Proposition 4. For semi-values, D(m, q OFA-S ) ∈ O(1) if i) µ has a bounded probability density function or ii) (0,1)1 w(1-w) dµ(w) < ∞.Particularly, this condition covers all weighted Banzhaf values and Beta Shapley values with α, β ≥ 1.All in all, we 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-studied semi-value.A datamodel, proposed by Ilyas et al. (2022) , is to learn an easy-to-interpret surrogate to represent a model output distribution related to a specific test example. In this circumstance, the set of players [n] is identified with all the available training data. Precisely, the feature coordinates θ * ∈ R n imputed to every data point in [n] is defined to be the uniquely optimal solution (together with a bias b * ∈ R) to the optimization problemargmin θ∈R n ,b∈R S⊆[n] η s+1 U (S) -b - i∈S θ i 2 (6)where η ∈ R n+1 is non-negative and n s=0 η s+1 > 0. The weight vector η can be scaled such that the objective in the problem (6) can be treated as an expectation, and thus the objective can be approximated through sampling a sufficient number of subsets, upon which an estimate of (θ * , b * ) can be obtained. We show below that θ * to a family of such least square regressions can be cast as some probabilistic values if it is the pairwise differences θ * j -θ * k (for every j, k ∈ [n]) that matter. Theorem 2. Let (b * , θ * ) be the uniquely optimal solution to the problem (6) where η s = p s-1 + p s for 2 ≤ s ≤ n. Then, there isθ * j -θ * k = ϕ j -ϕ k for every j, k ∈ [n].In other words, θ * = ϕ + c for some constant c1; 1 ∈ R n is the all-one vector. When using datamodels to detect similar training examples to a given target, what matters is the relative order of components in θ * . Meanwhile, Ilyas et al. (2022) showed that the corresponding performance depends on the choice of the weight vector η. Therefore, our OFA-A estimator serves as a sufficient proxy for a range of {θ * } and would facilitate the fine-tuning of η when using datamodels to detect similar training examples.When θ * Can Be Recovered From ϕ Interestingly, for specific choices of p ∈ R n and η ∈ R n+1 , it holds that θ = ϕ. Theorem 2 can be seen as an extension to the previous result stated in the below.Proposition 5 (Marichal and Mathonet 2011, Proposition 4) . Suppose 0 < a < 1 is given, ifp j = a j-1 (1 -a) n-j for 1 ≤ j ≤ n and η k = a k-2 (1 -a) n-k for 1 ≤ k ≤ n + 1, which leads to η s = p s-1 + p s for 2 ≤ s ≤ n, there is θ * = ϕ.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 ℓ 1 or ℓ 2 regularization simultaneously.Corollary 1. Under the setting of Proposition 5, let θ * be the uniquely optimal solution toargmin θ∈R n ,b∈R   S⊆[n] η s+1 U (S) -b - i∈S θ i 2   + λ a(1 -a) R(θ) (7)where λ > 0, the following are true about the relation between θ * and ϕ:1. If R(θ) = ∥θ∥ 2 2 , then θ * = 1 + λ a(1 -a) -1 ϕ. 2. If R(θ) = ∥θ∥ 1 , then θ * = sign(ϕ) • max 0, |ϕ| - λ 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 x i by 2x i -1, i.e., mapping 0 and 1 into -1 and 1, respectively, in ϕ {i} (x) used by Saunshi et al. (2022) yields v {i} (x) used by Marichal and Mathonet (2011) . A remarkable implication of the combination of Corollary 1 and our proposed OFA-A estimator is that we can solve a group of regularized datamodels covered by the problem (7) simultaneously! For example, the coefficient λ can be finetuned by running Algorithm 1 just once.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: Our experiment settings are stated in Section 5, and our method is presented in Algorithm 1. 
experiments: 
 In this section, we are to 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 D(m, q) is effective in determining the convergence rate of Algorithm 1, 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), U (S) is set to be the cross-entropy of LeNets trained on S on the classification datasets FMNIST, MNIST and iris; to obtain the exact values, the number of training data n is set to be 24; ii) U is defined to be the sum of unanimity (SOU) games, i.e., U (S) = d j=1 α j 1 Sj ⊆S where each ∅ ⊊ S j ⊊ [n] is randomly sampled, for which each semi-value can be computed by ϕ i = d j=1 α j [0,1] w sj -1 dµ(w); specifically, we set n ∈ {64, 128, 256} with d = n 2 , which implies that the implemented SOU games require n 2 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 of estimators, and thus the smaller the better. For n = 24, the value of each player is approximated using 20, 000 utility evaluations, and we compute the AUCCs as1 100 100 j=1 ∥ φ(200j) -ϕ∥2 ∥ϕ∥2where φ(200j) refers to the estimate using 200j utility evaluations for each player. For n ∈ {64, 128, 256}, the value of each player is approximated using 2, 000 utility evaluations, and the corresponding AUCCs are calculated as 1 100 100 j=1 ∥ φ(20j) -ϕ∥2 ∥ϕ∥2. All the AUCCs are reported with standard deviation using 30 different random seeds from {0, 1, 2, . . . , 29}.Verification of Our OFA-A Estimator For our OFA-A estimator where we substitute q OFA-A , which is defined in Proposition 1, into Algorithm 1, we choose the baselines according to Figure 1 . The selected baselines include WSL-Shapley (Kwon and Zou 2022a) , SHAP-IQ (Fumagalli et al. 2024) , weightedSHAP (Kwon and Zou 2022b) and permutation-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. Verification of Our OFA-S Estimator Next, we verify the faster convergence rate of our OFA-S 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 GELS-Shapley (Li and Yu 2024) , ARM (Kolpaczki et al. 2024; Li and Yu 2024) , complement (Zhang et 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 all the baselines are designed for all the probabilistic values we employ. For example, the complement estimator only works for Beta(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 is indeed faster than our OFA-A estimator, which aligns exactly with our theory; in other words, it implies that our proposed D(m, p) indeed determines the convergence rate of our Algorithm 1. Second, our OFA-S estimator always performs the best except on the SOU games which require only n 2 utility evaluation to get the exact values; by contrast, the utility function defined using the classification datasets require 2 n utility evaluations instead. Third, our proposed estimator is consistently the fastest on the commonly-used Beta(1, 1), i.e., the Shapley value; note that q OFA-A = q OFA-S for the Shapley value; therefore, our proposed estimator achieves the currently best convergence rate both empirically and theoretically. • 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
conclusion: 
 In this work, we propose a framework, termed OFA, that i) adheres to the principle of maximum sample reuse and ii) contains no amplifying factors for the goal of optimizing all probabilistic values simultaneously and efficiently. Particularly, our OFA framework is parameterized by a sampling vector q ∈ R n-3 . To gain insights, we theoretically develop a key formula D(m, q) concerning this framework that effectively determines the corresponding convergence rate. By optimizing q in D(m, q) for all probabilistic values on average, we obtain our one-for-all estimator that can theoretically approximate all probabilistic values simultaneously with the currently best convergence rate O(n log n) on average. Meanwhile, we propose a 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 our theoretical findings are 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.A Proof of Theorem 1 Theorem 1. Assume i) ∥U ∥ ∞ ≤ u and ii) 0 < ϵ ≤ 2D(m, q)γ(q) 2 u 2 . For φ in Algorithm 1, it requires 4nu 2 D(m,q) ϵ 2 log 8n 2 δ evaluations of U to achieve P (∥ φ -ϕ∥ 2 ≥ ϵ) ≤ δ where D(m, q) = n-2 s=2 n q s-1 m 2 s s + m 2 s+1 n -s and γ(q) = min 2≤s≤n-2 min q s-1 • s n , q s-1 • (n -s) n .Proof. Following Algorithm 1, let {S t } T t=1 be T independent random subsets. DefineT + i,s = T t=1 i ∈ S t , |S t | = s and T - i,s = T t=1 i ̸ ∈ S t , |S t | = swhere s = 2, 3, . . . , n -2. Then, we haveφ+ i,s = 1 T + i,s T i=1 i ∈ S t , |S t | = s • U (S t ) and φ- i,s = 1 T - i,s T i=1 i ̸ ∈ S t , |S t | = s • U (S t ). Define r + i,s = T + i,s T and r - i,s = T - i,s T . In particular, both i ∈ S t , |S t | = s and i ̸ ∈ S t , |S t | = s are Bernoulli random variables with E[r + i,s ] = q s-1 n -1 s -1 n s -1 = q s-1 • s n and E[r - i,s ] = q s-1 n -1 s n s -1 = q s-1 • (n -s) n .Additionally, R and τ are defined to be vectors inR 2n-6 such that R 2k-1 = r + i,k+1 , R 2k = r - i,k+1 , τ 2k-1 = q k •(k+1) n and τ 2k = q k •(n-k-1) n for k ∈ [n -3]. Note that R is a random vector. By Hoeffding's inequality, P (|R j -τ j | ≥ ω) ≤ 2 exp -2T ω 2where ω > 0, and thusP (∥R -τ ∥ ∞ ≥ ω) ≤ P ( j∈[2n-6] |R j -τ j | ≥ ω) ≤ (4n -12) exp -2T ω 2 . Denote the event { n-2 s=2 [m s ( φ+ i,s -ϕ + i,s ) + m s+1 (ϕ - i,s -φ- i,s)] ≥ ϵ} by E i where ϵ > 0. Let C be the set that contains all possible configurations C ∈ {0, 1} (2n-6)×T such that C1 T T = R and1 ⊤ T C = 1 ⊤ 2n-6 , i.e., C j,k = 0 indicates that the k-th subset is sampled from {R ⊆ [n] | r = (j + 3)/2 and i ∈ R} if j is odd and {R ⊆ [n] | r = (j + 2)/2 and i ̸ ∈ R} otherwise. Then, P (E i ) = C∈C P (E i ∩ C) = C∈C P (E i | C) • P (C).Observe that C can be divided into two separate groups C <ω and C ≥ω such thatC<ω∈C<ω P (C <ω ) = P (∥R -τ ∥ ∞ < ω) and C ≥ω ∈C ≥ω P (C ≥ω ) = P (∥R -τ ∥ ∞ ≥ ω).Therefore,P (E i ) = C<ω∈C<ω P (E i | C <ω ) • P (C <ω ) + C ≥ω ∈C ≥ω P (E i | C ≥ω ) • P (C ≥ω ) ≤ C<ω∈C<ω P (E i | C <ω ) • P (C <ω ) + (4n -12) exp -2T ω 2 . (8)For simplicity, we write P C<ω (E i ) instead of P (E i | C <ω ). Additionally, we assume ω < γ(q) 2 so that neither T + i,s nor T - i,s is zero when conditioned on any C <ω . By the Chernoff bound, for any λ > 0, there isP C<ω (E i ) ≤ E C<ω exp λ n-2 s=2 m s ( φ+ i,s -ϕ + i,s ) + m s+1 (ϕ - i,s -φ- i,s ) • e -λϵ = e -λϵ n-2 s=2 E C<ω exp λm s ( φ+ i,s -ϕ + i,s ) n-2 s=2 E C<ω exp λm s+1 (ϕ - i,s -φ- i,s )where the equality is due to the independence that stems from the independence of random subsets and that the configuration is fixed. Moreover,E C<ω exp λm s ( φ+ i,s -ϕ + i,s ) = E C<ω   exp   λm s 1 T + i,s T + i,s j=1 (U (S + i,s,j ) -ϕ + i,s )     = T + i,s j=1 E C<ω exp λm s T + i,s (U (S + i,s,j ) -ϕ + i,s )where{S + i,s,j } 1≤j≤T + i,sis obtained by ordering {S t | |S t | = s and i ∈ S t }. In a similar fashion, we haveE C<ω exp λm s+1 (ϕ - i,s -φ- i,s ) = T - i,s j=1 E C<ω exp λm s+1 T - i,s (ϕ - i,s -U (S - i,s,j ))By Hoeffding's lemma,E C<ω exp λm s T + i,s (U (S + i,s,j ) -ϕ + i,s ) ≤ exp λ 2 m 2 s u 2 2T + i,s • T + i,s , E C<ω exp λm s+1 T - i,s (ϕ - i,s -U (S - i,s,j )) ≤ exp λ 2 m 2 s+1 u 2 2T - i,s • T - i,s, which leads toT + i,s j=1 E C<ω exp λm s T + i,s (U (S + i,s,j ) -ϕ + i,s ) ≤ exp λ 2 m 2 s u 2 2T + i,s , T - i,s j=1 E C<ω exp λm s+1 T - i,s (ϕ - i,s -U (S - i,s,j )) ≤ exp λ 2 m 2 s+1 u 2 2T - i,s . Therefore, P C<ω (E i ) ≤ exp λ 2 u 2 2T D -λϵ where D = n-2 s=2 T T + i,s m 2 s + T T - i,s m 2 s+1 . Next, we aim to show that | D -D(m, q)| ≤ D(m, q). Observe that | D -D(m, q)| ≤ n-2 s=2 1 r 2s-3 - 1 τ 2s-3 m 2 s - 1 r 2s-2 - 1 τ 2s-2 m 2 s+1 ,and since |r j -τ j | < ω,1 r j - 1 τ j ≤ ω (τ j -ω)τ j = 1 τ j -ω - 1 τ j .Since γ(q) ≤ τ j and ω ≤ γ(q) 2 ,1 τ j -ω = τ j τ j -ω • 1 τ j = 1 1 -ω τj • 1 τ j ≤ 2 τ j .As a result, we have | D -D(m, q)| ≤ D(m, q), and thusEQUATIONCombining Eqs. ( 8) and (9) yieldsP (E i ) ≤ exp λ 2 u 2 T D(m, q) -λϵ + (4n -12) exp(-2T ω 2 ).Choosing λ > 0 that minimizes the upper bound yieldsP (E i ) ≤ exp - T ϵ 2 4u 2 D(m, q) + (4n -12) exp(-2T ω 2 ).Solving the equation-T ϵ 2 4u 2 D(m,q) = -2T ω 2 yields ω = ϵ 28D(m,q)u 2 , which gives-2T ω 2 = - T ϵ 2 4D(m, q)u 2 .Particularly, to meet the assumption ω ≤ γ(q) 2 , we have to have ϵ ≤ 2D(m, q)γ(q) 2 u 2 . To conclude, provided that ϵ ≤ 2D(m, q)γ(q) 2 u 2 , we haveP ( n-2 s=2 m s ( φ+ i,s -ϕ + i,s ) + m s+1 (ϕ - i,s -φ- i,s ) ≥ ϵ) ≤ 4n exp(- T ϵ 2 4D(m, q)u 2 ).Similarly, there isP ( n-2 s=2 m s (ϕ + i,s -φ+ i,s ) + m s+1 ( φ- i,s -ϕ - i,s ) ≥ ϵ) ≤ 4n exp(- T ϵ 2 4D(m, q)u 2 ),and thusP (| φi -ϕ i | ≥ ϵ) ≤ 8n exp(- T ϵ 2 4D(m, q)u 2 ).Eventually, we haveP (∥ φ -ϕ∥ 2 ≥ ϵ) ≤ P ( i∈[n] | φi -ϕ i | ≥ ϵ √ n ) ≤ 8n 2 exp(- T ϵ 2 4nD(m, q)u 2 ). Solving δ ≥ 8n 2 exp(- T ϵ 2 4nD(m,q)u 2 ) yields T ≥ 4nD(m,q)u 2 ϵ 2 log 8n 2δ . Note the assumption ϵ ≤ 2D(m, q)γ(q) 2 u 2 can be removed if the configuration is fixed withT + i,s ≈ s•qs-1 n T and T - i,s ≈ (n-s)qs-1 n T . B Proofs of Propositions Proposition 1. q OFA-A s-1 ∝ 1 √ (s)(n-s)and D(q OFA-A ) ∈ O(1). In other words, our OFA-A estimator achieves the convergence rate of O(n log n) simultaneously for all probabilistic values on average. 1) , and a smooth homeomorphism f : Λ → ∆ is defined by lettingProof. Let Λ = {x ∈ R n-1 | 0 ≤ n-1 j=1 x j ≤ L n } where L n = n 1 2(n-f (x) = 1 L n (x 1 , x 2 , • • • , x n-1 , L n - n-1 j=1 x j ) ⊤ .In other words, both f and f -1 are C ∞ . Since the volume of ∆ is n 1 2(n-1)! , there is(n -1)! n 1 2 x∈Λ D(f (x), q) det (Df (x) ⊤ Df (x))dx = m∈∆ D(m, q)dν(m). Note that det (Df (x) ⊤ Df (x)) = 1 for every x ∈ Λ. With Λ = {y ∈ R n-1 | 0 ≤ n-1 j=1 y j ≤ 1}, we have (n -1)! n 1 2 x∈Λ D(f (x), q)dx = (n -1)! y∈Λ D(f (L n y), q)dy.For simplicity, assume that n = 4, notice that y∈Λy 2 n-1 dy = 1 0 dy 1 1-y1 0 dy 2 1-y1-y2 0 y 2 3 dy 3 = 1 3 • 4 • 5 = 1 n-1 k=1 (2 + k) . Therefore, y∈Λ D(f (L n y), q)dy = n-2 s=2 n q s-1 y∈Λ y 2 s s + y 2 s+1 n -s dy = 1 n-1 k=1 (2 + k) n-2 s=2 n q s-1 1 s + 1 n -s ,which leads toD(q) = (n -1)! n-1 k=1 (2 + k) n-2 s=2 n q s-1 1 s + 1 n -s .Since D(q) is convex in q, q OFA-A can be directly obtained using the KKT conditions, which isq OFA-A s-1 = n s + n n-s n-2 s=2 n s + n n-s.Therefore, we haveD(q OFA-A ) = (n -1)! n-1 k=1 (2 + k) n-2 s=2 n s + n n -s 2 . Since lim n→∞ (n-1)!(n-1) 2 n-1 k=1 (2+k) = 2Γ(3), when n is sufficiently large, there is D(q OFA-A ) ≈ 1 n 2 n-2 s=2 n s + n n -s 2 = 1 n n-2 s=2 1 s n (1 -s n ) 2 < 1 0 1 x(1 -x) dx 2 = π 2 .Proposition 2. Our OFA-A estimator achieves the convergence rate of O(n log n) simultaneously for all semi-values whose probability density functions exist and are bounded. Particularly, Beta Shapley values with α, β ≥ 1 all satisfy this condition.Proof. Let ϕ be a semi-value such that p s =1 0 w s-1 (1 -w) n-s dµ(w) = 1 0 w s-1 (1 - w) n-s p µ (w)dw such that p µ (w) ≤ B for every w ∈ [0, 1]. Particularly, we have m s = n -1 s -1 p s ≤ B • n -1 s -1 1 0 w s-1 (1 -w) n-s dw = B • n -1 s -1 (s -1)!(n -s)! n! = B n .Therefore,D(m, q OFA-A ) ≤ B 2 n n-2 s=2 1 q OFA-A s-1 1 s + 1 n -s = B 2 n-2 s=2 1 s(n -s) 2 < B 2 π 2 .Proposition 3. If p s = a s-1 (1 -a) n-s with 0 < a < 1, which corresponds to the weighted Banzhaf value parameterized by w, then D(m, q OFA-A ) ∈ O(n 1 2 ). In other words, the OFA estimator achieves the convergence rate of O(n 3 2 log n) simultaneously for all WB-a with 0 < a < 1. 
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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 or 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our work focuses on 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 no 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 a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: 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 a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as 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 in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as 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. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?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. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: OFA-A s-1 ∝ 1 √ s(n-s), we haveD(m, q OFA-A ) = C • n • n-2 s=2 n -s s m 2 s + s n -s m 2 s+1 where C = n-2 s=2 1 s(n -s) < πThen,D(m, q OFA-A ) = C n-2 s=2 n n -s s n -1 s -1 2 a s-1 (1 -a) n-s 2 + s n -s n -1 s 2 a s (1 -a) n-s-1 2 .Specifically,n -s s n -1 s -1 2 = s n -s (n -1)! 2 (s -1)!s!(n -s -1)!(n -s)! and s n -s n -1 s 2 = n -s s (n -1)! 2 (s -1)!s!(n -s -1)!(n -s)! ,and thusn • n -s s n -1 s -1 2 a s-1 (1 -a) n-s 2 + s n -s n -1 s 2 a s (1 -a) n-s-1 2 = n • a s-1 (1 -a) n-s-1 2 (n -1)! 2 (s -1)!s!(n -s -1)!(n -s)! s n -s (1 -a) 2 + n -s s a 2 Since s n -s (1 -a) 2 + n -s s a 2 ≤ s n -s + n -s s = n s(n -s) ,there isn • n -s s n -1 s -1 2 a s-1 (1 -a) n-s 2 + s n -s n -1 s 2 a s (1 -a) n-s-1 2 ≤ s(n -s) n s a s (1 -a) n-s 2 a 2 (1 -a) 2 ≤ n • n s a s (1 -a) n-s 2 a 2 (1 -a) 2 .Using the identitym j=0 m j 2 (x + y) 2j (x -y) 2(m-j) = m j=0 2j j 2(m-j) m-j x 2j y 2(m-j) , there is n-2 s=2 n s a s (1 -a) n-s 2 = n s=0 2s s 2(n -s) n -s 1 2 2s 2a -1 2 2(n-s) = 2n n 2a -1 2 2n + n-1 s=1 2s s 2(n -s) n -s 1 2 2s 2a -1 2 2(n-s) + 2n n 1 2 2n .For every k ≥ 1, 2k k ≈ 2 2k √ k using the Stirling's approximation, and thus2n n 2a -1 2 2n ≈ z n √ n , 2n n 1 2 2n ≈ 1 √ n n-1 s=1 2s s 2(n -s) n -s 1 2 2s 2a -1 2 2(n-s) ≈ n-1 s=1 1 s(n -s) z n-s ≤ n-1 j=1 z j √ n -1 ,where z = (2a -1) 2 < 1. Therefore, we obtainn-2 s=2 n s a s (1 -a) n-s 2 ≤ O(n -1 2 ), which eventually leads to D(m, q OFA-A ) ≤ n a 2 (1 -a) 2 n-2 s=2 n s a s (1 -a) n-s 2 ≤ O(n 1 2 ).Proposition 4. For semi-values, D(m, q OFA-S ) ∈ O(1) if i) µ has a bounded probability density function or ii) (0,1) 1 w(1-w) dµ(w) < ∞. Particularly, this condition covers all weighted Banzhaf values and Beta Shapley values with α, β ≥ 1.Proof. If µ({0}) ̸ = 0 (µ({1}) ̸ = 0, respectively), its induced marginal contributions all reside in ϕ + i,1 and ϕ - i,0 (ϕ + i,n and ϕ - i,n-1 , respectively), which is computed exactly using Algorithm 1. Therefore, W.L.O.G., we assume that µ((0, 1)) = 1.1 0 1 w(1-w) dµ(w) < ∞, there is n-2 s=2 n s m 2 s + n n -s m 2 s+1 ∈ O(1).Specifically,D(m, q OFA-S ) = n-2 s=2 n s m 2 s + n n -s m 2 s+1 ≤ n-2 s=2 n s m s + n n -s m s+1 = 1 0 n-2 s=2 s n n s w s-1 (1 -w) n-s + n -s n n s w s (1 -w) n-s-1 dµ(w).Since s n (1 -w) + n-s n w ≤ 2, we have1 0 n-2 s=2 s n n s w s-1 (1 -w) n-s + n -s n n s w s (1 -w) n-s-1 dµ(w) ≤ 1 0 n-2 s=2 2 n s w s (1 -w) n-s w(1 -w) dµ(w) ≤ 2 1 0 1 w(1 -w) dµ(w) ∈ O(1).To prove this theorem, we first state useful definitions and lemmas.Definition 2 (Semi Inner Product). Let V 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) ⟨αx, y⟩ = α⟨x, y⟩, iii) ⟨x + y, z⟩ = ⟨x, z⟩ + ⟨y, z⟩, and iv) ⟨x, x⟩ ≥ 0. In addition, we write ∥x∥ = ⟨x, x⟩ for every x ∈ V.Lemma 1. Let a semi inner product on a linear space V be given, and A ⊆ V is some affine space.For the following optimization problemargmin x∈A ∥x -p∥ 2where p ∈ V, x * is optimal if and only if ⟨x * -p, y -x * ⟩ = 0, ∀y ∈ A.(10)Proof. Suppose x * verifies Eq. ( 10), for every y ∈ A, ∥y -p∥ 2 = ∥x * -p∥ 2 + ∥y -x * ∥ 2 + 2⟨x * -p, y -x * ⟩ ≥ ∥x * -p∥ 2 .Next, suppose x * is optimal, and for the sake of contradiction, assume that there is some y ∈ A such that ⟨x * -p, y -x * ⟩ ̸ = 0. Write z = y -x * , for t ∈ R ∥x * + tz -p∥ 2 = ∥x * -p∥ 2 + t 2 ∥z∥ 2 + 2t⟨x * -p, z⟩.Since ⟨x * -p, z⟩ ̸ = 0, there exists some t o ∈ R such that t 2 ∥z∥ 2 + 2t⟨x * -p, z⟩ < 0, and thus ∥x * + t o z -p∥ 2 < ∥x * -p∥ 2 , a contradiction.Definition 3 (Projection Induced by a Semi Inner Product). Given a semi inner product on a linear space V, the set of all optimal solutions to the problemargmin x∈A ∥x -p∥ 2 ,where A ⊆ V is an affine space and p ∈ V, is denoted by Proj A ({p}). To account for the possibility that there are multiple optimal solutions, we extend the definition by letting Proj A (S) = p∈S Proj A ({p}). Lemma 2. Let V be a linear space with a semi inner product. Suppose there are two affine spaces B ⊆ A, for every p ∈ V, there isProj B (Proj A ({p})) ⊆ Proj B ({p}).Proof. We rephrase Lemma 1 to ease the proof. For each affine space A ⊆ V, define L A = A -q for some q ∈ A. Note that the resulting L A is independent of the choice of q ∈ A and it is a subspace in V. Therefore, Eq. ( 10) is equivalent to ⟨x * -p, z⟩ = 0, ∀z ∈ L A . Lemma 3 (Ruiz et al. 1998, Theorem 12) . Let v * be the uniquely optimal solution to argminEQUATIONwhere η s = p s-1 + p s for 2 ≤ s ≤ n. Then, there isv * i -v * j = ϕ i -ϕ j for every i, j ∈ [n].Recall that the problem ( 6) isargmin θ∈R n ,b∈R S⊆[n] η s+1 U (S) -b - i∈S θ i 2 ,and our goal is to prove thatθ * i -θ * j = v * i -v * j for every i, j ∈ [n], which together with Lemma 3 is sufficient to complete our proof. Theorem 2. Let (b * , θ * ) be the uniquely optimal solution to the problem (6) where η s = p s-1 + p s for 2 ≤ s ≤ n. Then, there isθ * j -θ * k = ϕ j -ϕ k for every j, k ∈ [n].Proof. The first part of our proof was inspired by (Hammer and Holzman 1992, Lemma 2.9) . LetG = {U : 2 [n] → R}, AG = {U ∈ G | U (S) = a 0 + i∈S a i for every S ⊆ [n]} and A U = {g ∈ AG | U ([n]) = g([n]) and U (∅) = g(∅)}. Note that G is a linear space and the other two are affine spaces with A U ⊆ AG. For clarity, each game in AG is written as [a 0 , a] where a ∈ R n .A semi inner product on G can be defined by letting⟨g 1 , g 2 ⟩ = S⊆[n] η s+1 • g 1 (S)g 2 (S) for every g 1 , g 2 ∈ G. Then, [b * , θ * ] is the projection of U onto AG, whereas [U (∅), v * ]is the projection of U onto A U where v * is the uniquely optimal solution to the problem (11).By Lemma 2, there isProj A U (Proj AG ({U })) ⊆ Proj A U ({U }). Moreover, the uniqueness in problem (11) implies that Proj A U ({U }) = {[U (∅), v * ]},Proj A U (Proj AG ({U })) = Proj A U ({U }) = {[U (∅), v * ]}. Since [b * , θ * ] ∈ Proj AG ({U }), the equality Proj A U ({[b * , θ * ]}) = {[U (∅), v * ]} means that [U ∅ , v * ]is the uniquely optimal solution to the problemEQUATION)Pick i, j ∈ [n] such that i ̸ = j, and define an additive game e i ∈ AG by letting e i (S) = 1 if i ∈ S and 0 otherwise, e j is defined similarly. Consider the problemEQUATION)Note that [U (∅), v * ] + t(e ie j ) ∈ A U for every t ∈ R, and the uniqueness to the problem ( 12) suggests that t * = 0 is the uniquely optimal solution to the problem ( 13). Removing all constant terms in the problem ( 13) yields an equivalent problemargmin t∈R S⊆[n] : i∈S,j̸ ∈S η s+1 ([U (∅), v * ](S) -[b * , θ * ](S) + t) 2 + S⊆[n] : i̸ ∈S,j∈S η s+1 ([U (∅), v * ](S) -[b * , θ * ](S) -t) 2 . Write g = [U (∅), v * ] -[b * , θ * ],since this problem is convex, letting the derivative equal 0 leads tot * = S⊆[n] : i̸ ∈S,j∈S η s+1 • g(S) -S⊆[n] : i∈S,j̸ ∈S η s+1 • g(S) 2 S : i∈S,j̸ ∈S η s+1 = 0. Write g = [g 0 , g] where g 0 = U (∅) -b * and g = v * -θ * , there is S⊆[n] : i∈S,j̸ ∈S η s+1 • g(S) = α(g 0 + g i ) + β 1≤k≤n : k̸ =i,j g k where α = n-1 s=1 n -2 s -1 η s+1 and β = n-1 s=2 n -3 s -2 η s+1 .Similarly, we have S⊆[n] : i̸ ∈S,j∈S η s+1 • g(S) = α(g 0 + g j ) + β 1≤k≤n : k̸ =i,j g k , and therefore α(g j -g i ) = 0.Since α > 0, we eventually get g i = g j . In other words,v * i -θ * i = v * j -θ * j .Because i and j are chosen arbitrarily, our proof is completed.To be self-contained, we also prove that the problem (6) has only one optimal solution provided that η s = p s-1 + p s for 2 ≤ s ≤ n. W.L.O.G., assume S⊆[n] η s+1 = 1. By letting the derivative of the problem (6) equal 0, we have Ax= b A =        1 κ κ • • • κ κ κ τ • • • τ κ τ κ . . . . . . . . . . . . . . . . . . τ κ τ • • • τ κ        , κ = n s=1 n -1 s -1 η s+1 , τ = n s=2 n -2 s -2 η s+1 , b 1 = S⊆[n] η s+1 U (S), b j+1 = S⊆[n] : j∈S η s+1 U (S) for every j ∈ [n], x 1 = b and x j+1 = θ j for every j ∈ [n].Left multiplying A with some row operation matrix R givesRA =        1 κ κ • • • κ 0 κ -κ 2 τ -κ 2 • • • τ -κ 2 0 τ -κ 2 κ -κ 2 . . . . . . . . . . . . . . . . . . . . . 0 τ -κ 2 • • • τ -κ 2 κ -κ 2        . It is sufficient to prove that the bottom-right n × n submatrix of RA is invertible. Suffice it to show κ -τ ̸ = 0 and κ + (n -1)τ -nκ 2 ̸ = 0. Using n s = n-1 s + n-1 s-1 , we have κ -τ = n-1 s=1 n -2 s -1 η s+1 > 0.Using n n-1 s-1 = s n s , we haveκ + (n -1)τ = n s=1 s n -1 s -1 η s+1 = 1 n n s=1 s 2 n s η s+1 , n • κ 2 = n • n s=1 n -1 s -1 η s+1 2 = 1 n n s=1 s n s η s+1 2 . Let γ = 1 -η 1 and ζ s = η s+1 /γ for every s ∈ [n], there is n • κ 2 = γ 2 n n s=1 s n s ζ s 2 = γ 2 n E[s] 2 ≤ γ 2 n E[s 2 ] = γ(κ + (n -1)τ ) ≤ κ + (n -1)τ.If η 1 > 0, the last inequality is strict as γ < 1. Otherwise, the first inequality is strict asVar[s] = E[s 2 ] -E[s] 2 > 0.Recall that each probabilistic value is defined to be, for every i ∈ [n],EQUATIONwhere p ∈ R n is a non-negative vector withn s=1 n-1 s-1 p s = 1. If p s = 1 0 w s-1 (1 -w) n-s dµ(w)for some probability measure µ on the closed interval [0, 1], the induced ϕ is referred to as a semi-value.The Sampling Lift Estimator (Moehle et al. 2022) The sampling lift estimator is based onϕ i = E S⊆[n]\i [U (S ∪ i) -U (S)] where P (S) = p s+1 .The sampling procedure is: i) sample a subset size s ∈ [n] with P (s) = n-1 s-1 p s , and then ii) sample a subset S uniformly from {R ⊆ [n]\i | r = s -1}. For semi-values such that p s = 1 0 w s-1 (1 -w) n-s dµ(w) where µ is a probability measure on the closed interval [0, 1], there is an alternative: i) sample a w ∈ [0, 1] according to µ, and then sample a subset S ⊆ [n]\i by incorporating each player in [n]\i with probability w. With a sequence of sampled subsets{S j } T j=1 , the i-th estimate is φi = 1 T T j=1 (U (S j ∪ i) -U (S j )).The Weighted Sampling Lift Estimator (Kwon and Zou 2022a) The formula it is built upon isϕ i = E Shap S⊆[n]\i p s+1 q s+1 (U (S ∪ i) -U (S)) where P (S) = q s+1 = s!(n -1 -s)! n! .Note that setting p = q in Eq. ( 14) leads to the Shapley value. The sampling procedure is: i) sample a w uniformly from [0, 1], and then ii) sample a subset S ⊆ [n]\i by incorporating each player in[n]\i with probability w. Then, the i-th estimate is φi = 1 T T j=1ps j +1 qs j +1 (U (S j ∪ i) -U (S j )).The KernelSHAP Estimator (Lundberg and Lee 2017) This estimator is specific to the Shapley value. It employs the fact that the Shapley value ϕ Shap i is the uniquely optimal solution to argminEQUATION)Note that the weights can be scaled so that the objective is an expectation. A sequence of subsets{S j } T j=1 where ∅ ⊊ S j ⊊ [n] is sampled according to P (S) ∝ n-2 s-1 -1. Then, we have an approximate problem asargmin ϕ∈R n 1 T T j=1   U (S j ) -U (∅) - i∈Sj ϕ i   2 s.t. i∈[n] ϕ i = U ([n]) -U (∅),the uniquely optimal solution of which is treated as the estimates, i.e.,φShap = Â-1 b -1 n 1 ⊤ n Â-1 b -U ([n]) + U (∅) 1 ⊤ n Â-1 1 n where Â = 1 T T j=1 1 Sj 1 ⊤ Sj and b = 1 T T j=1 (U (S j ) -U (∅)) • 1 Sj .Specifically, 1 Sj ∈ {0, 1} n such that its i-th entry is 1 if and only if i ∈ S j .The Unbiased KernelSHAP Estimator (Covert and Lee 2021) The uniquely optimal solution ϕ Shap to the problem ( 15) isϕ Shap = A -1 b -1 n 1 ⊤ n A -1 b -U ([n]) + U (∅) 1 ⊤ n A -1 1 n where A = E[1 S 1 ⊤ S ] and b = E[(U (S) -U (∅)) • 1 n ].This estimator employs the fact thatA ij = 1 2 if i = j and 1 n(n-1) n-1 s=2 s-1 n-s n-1 s=1 1 s(n-s)otherwise. In other words, the estimates of this estimator isEQUATIONParticularly {S j } T j=1 where ∅ ⊊ S j ⊊ [n] are sampled using P (S) ∝ n-2 s-1-1 .Recently, Fumagalli et al. (2024) proved that Eq. ( 16) can be simplified asφShap i = U ([n]) -U (∅) n + 2 n-1 s=1 1 s T T j=1 U (S j ) 1 i∈Sj - s j n .The ARM Estimator (Kolpaczki et al. 2024) This estimator is designed according toϕ i = E S∼P + |i∈S [U (S)] -E S∼P -|i̸ ∈S [U (S)]where P + (S) ∝ p s for every ∅ ⊊ S ⊆ [n] and P -(S) ∝ p s+1 for every S ⊊ [n] (Li and Yu 2024, Proposition 8). A sequence of subsets {S j } T j=1 are sampled using P + and P -alternatively, i.e., {S 2k-1 } T 2 k=1 are sampled independently according to P + , whereas {S 2k } T 2 k=1 are sampled independently using P -. Then, the i-th estimate isφi = 1 T + i T 2 k=1 U (S 2k-1 )1 i∈S 2k-1 - 1 T - i T 2 k=1 U (S 2k )1 i̸ ∈S 2kwhereT + i = T 2 k=1 1 i∈S 2k-1 and T - i = T 2 k=1 1 i̸ ∈S 2k .The AME Estimator (Lin et al. 2022) This estimator is restricted to a sub-family of semi-values that satisfy1 0 1 w(1-w) dµ(w) < ∞.For such a semi-value ϕ, it can be cast as a uniquely optimal solution to argminv∈R n E[(Y -X ⊤ v) 2 ]where X ∈ R n and Y are random variables. The sampling procedure is: i) sample a w ∈ (0, 1) using µ, ii) sample a subset S by incorporating each player with probability w, and then iii) Y = U (S) and X = X(S) such thatX i = 1 w•C if i ∈ S and -1 (1-w)C otherwise where C = 1 0 1 w(1-w) dµ(w). With a sequence of subsets {(w j , S j )} T j=1 , the uniquely optimal solution to the approximate problemargmin v∈R n 1 T T j=1 U (S j ) -X(S j ) ⊤ v 2is taken as the induced estimates, which is φ = (A ⊤ A) -1 A ⊤ b where the j-th row of A is X(S j ) ⊤ and b j = U (S j ).One Way to Improve the AME Estimator The limitation of the AME estimator is that it only applies to semi-values that satisfy1 0 1 w(1-w) dµ(w) < ∞.Meanwhile, another potential drawback is its need to compute the inverse of A ⊤ A, though it can be circumvented by solving the approximate problem using gradients. In this work, we make a small improvement to the AME estimator by extending its applicability to all semi-values, removing (A ⊤ A) -1 in the approximate formula and providing a more direct analysis of its convergence rate in terms of (ϵ, δ)-approximation.⊤ ] = I, suggesting that 1 T A ⊤ A -1 → Iby the law of large numbers and thus (A ⊤ A) -1 is redundant. Its removal leads to a simplified formula:φi = 1 T T j=1 i ∈ S j w j U (S j ) - i ̸ ∈ S j 1 -w j U (S j ) .We comment that the following proposition is complementary to (Lin et al. 2022, Proposition 3.3 ) that claims a similar result. Proposition 6.Assume that i) ∥U ∥ ∞ ≤ u and ii) µ([A, B]) = 1 for some 0 < A < B < 1, the improved AME estimator requires 2nu 2 C 2 ϵ 2 log 2n δ utility evaluations of U to achieve P (∥ φ -ϕ∥ 2 ≥ ϵ) ≤ δ where C = 1 min(A,1-B) .Proof. Notice that φi = 1 T T j=1 Z j where {Z j } T j=1 are i.i.d. random variables with E[Z j ] = ϕ i . By the Hoeffding's inequality, there isP (| φi -ϕ i | ≥ ϵ) ≤ 2 exp - T ϵ 2 2u 2 C 2 where C = 1 min(A,1-B) . Then, P (∥ φ -ϕ∥ 2 ≥ ϵ) ≤ P ( 1≤i≤n | φi -ϕ i | ≥ ϵ √ n ) ≤ 2n exp - T ϵ 2 2nu 2 C 2 . Solving 2n exp -T ϵ 2 2nu 2 C 2 ≤ δ leads to T ≥ 2nu 2 C 2 ϵ 2 log 2n δ .Remark 1. Notice that the improved AME estimator requires that µ({0, 1}) = 0. Nevertheless, semi-values are additively decomposable on µ and the part related to µ({0, 1}) can be computed exactly in linear time. Therefore, it is 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, p s = a s-1 (1-a) n-s . Each subset is sampled by incorporating each player with probability a, and then the i-th estimate isφi = 1 T + i T j=1 U (S j )1 i∈Sj - 1 T - i T j=1 U (S j )1 i̸ ∈SjwhereT + i = T j=1 1 i∈Sj and T - i = T j=1 1 i̸ ∈Sj .The GELS Estimator (Li and Yu 2024) This estimator is established using the fact thatϕ i = v * i -v * n+1 where v * ∈ R n+1is the uniquely optimal solution to argminv∈R n+1 ∅⊊S⊊[n+1] p s U (S ∩ [n]) - i∈S v i 2 .The subsets {S j } T j=1 where ∅ ⊊ S j ⊊ [n + 1] are sampled using P (S) ∝ p s , and then the i-th estimate isφi = n s=1 n s -1 p s (v i -vn+1 )where vk = 1T k T j=1 U (S j ∩ [n])1 k∈Sj and T k = T j=1 1 k∈Sj .The Complement Estimator (Zhang et al. 2023) The complement estimator is specific to the Shapley value using the fact thatϕ Shap i = 1 n S⊆[n]\i n -1 s -1 (U (S ∪ i) -U ([n]\(S ∪ i))) .The sequence of subsets {S j } T j=1 is sampled using i) sample a subset size s ∈ [n] uniformly, and then sample a subset S uniformly from {R ⊆ [n] | r = s}. Then, the i-th estimate isφShap i = 1 n n s=1 φi,s where φi,s = 1 T i,s n j=1 (v j i ∈ S j , s j = s -v j i ̸ ∈ S j , n -s j = s ) v j = U (S j ) -U ([n]\S j ) and T i,s = T j=1 ( i ∈ S j , s j = s + i ̸ ∈ S j , n -s j = s ) .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 to the Shapley value. A sequence of subsets {S j } T j=1 are independently sampled according to: i) sample a subset size s ∈ [n] using P (s) ∝ 1 s(n+1-s) , and then ii) sample a subset S uniformly from {R ⊆ [n + 1] | r = s}. Then, the i-th estimate isφShap i = 2 n s=1 1 s T T j=1 U (S j ∩ [n]) ( i ∈ S j , n + 1 ̸ ∈ S j -i ̸ ∈ S j , n + 1 ∈ S j ) .The Permutation Estimator (Castro et al. 2009) This estimator is specific to the Shapley value, using the formulaϕ Shap i = 1 n! π∈Π (U (P i (π) ∪ i) -U (P i (π)))where Π contains all permutations of [n] and P i (π) is the subset that contains all players preceding i in π . Thus, it samples a sequence of permutations {π j } T j=1 from Π uniformly with replacement, and then the i-th estimate isφShap i = 1 T T j=1 U (P i (π j ) ∪ i) -U (P i (π j )) .The WeightedSHAP Estimator (Kwon and Zou 2022b) As mentioned in the main paper, it is based onϕ i = n s=1 m s • E R⊆[n]\i r=s-1 [U (R ∪ i) -U (R)]where m s = n-1 s-1 p s . For each player i ∈ [n], it samples a sequence of permutations {π j } T j=1 of [n]\i. Then, the corresponding estimate is φi = n s=1 m s φi,s where φi,k =1 T T j=1 U (S k (π j ) ∪ i) -U (S k (π j )) and S k (π j ) is the subset that contains the first k -1 players in π j .The SHAP-IQ Estimator (Fumagalli et al. 2024) Recall that its underlying formula isϕ i = p n • (U ([n]) -U (∅)) + 2H • E ∅⊊S⊊[n] [((n -s)m s 1 i∈S -sm s+1 1 i̸ ∈S ) • (U (S) -U (∅))]where m s = n-1 s-1 p s , H = n-1 j=1 1 j , and P (S) ∝ n-2 s-1 -1 . Therefore, a sequence of subsets{S j } T j=1 where ∅ ⊊ S j ⊊ [n] is sampled using P (S) ∝ n-2 s-1 -1, and the i-th estimate isφi = p n • (U ([n]) -U (∅)) + 2H T T j=1 (U (S j ) -U (∅)) • (n -s)m s 1 i∈Sj -sm s+1 1 i̸ ∈Sj .NeurIPS Paper Checklist 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 a price to pay for using a fixed sampling scheme for all probabilistic values. Guidelines:• The answer NA means that the paper has no 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 a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.• 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 a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to 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 be possible for other researchers to have some path to reproducing or verifying the results. Guidelines:Using another definition,Musco and Witter (2024) claimed to have an estimator with convergence rate O(n log n) for the Shapley value after this work was accepted. 


Decision: **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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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). 

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? 

It 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)
questions: questions: Please see the weaknesses
limitations: 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.
paper_summary: paper_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 
(ϵ,δ)-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.
strength_weakness: strength_weakness: 1. The empirical results are demonstrated on a classification task using LeNet and small datasets like MNIST. 

2. 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.
questions: 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: limitations: Yes the authors have indicated the weakness of their proposed method
paper_summary: paper_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.

Specifically, 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.

Overall, they provide an efficient solution for approximating multiple probabilistic values simultaneously, with theoretical and practical implications.
strength_weakness: strength_weakness: 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$.

2. 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.

3. Similarly, a formal definition of "one-for-all estimators" is missing.

4. 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.

5. What does $q_s$ in line 159 mean?
questions: questions: See the weaknesses part.
limitations: limitations: The limitations are not discussed explicitly in the main text.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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). 

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.
questions: questions: See weaknesses.
limitations: limitations: See weaknesses.

Comments: comment: Thank you for the clarifications. I am keeping my current rating.
Thanks for the responses. I have raised my score from 5 to 6.
Thank you for the insightful discussion!
Thank you for the clarification! I will maintain my score.