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

We are grateful for your review! Here is our response to your concerns.

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

A: 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).

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.

A: 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.

Thank you for your comments! This response is to address your concerns.

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}$.

A: Please let us know if our understanding of your question is not correct, and we'd be happy to respond to any further questions.

Our 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. Moreover, we have empirically verified that this indeed leads to slower empirical convergence in Figure 1. We'll make this part clearer in the revision.

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.

A: 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.

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

A: 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.

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.

A: 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.

The significance of our theoretical results, e.g., includes:

• 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;

• 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)$.

Q: What does $q_{s}$ in line 159 mean?

A: $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.

We appreciate your review and address your concerns below.

Q: The paper does not discuss much about the implementation details.

A: 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.

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.

A: 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. In 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.

Thank you for the thoughtful comments. We address your concerns below.

Q: Discuss further the sampling vector q.

A: 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.

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

We have added the above discussion and limitation to our revision.

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?

A: 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.