- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes LRFShap, a more efficient version of FreeShap, for data valuation. The key idea is to use low-rank approximations of the kernel matrices instead. The theoretical results show that the error in Shapley values is controlled by the error in the kernel approximation (but not the error in the predicted utilities). The empirical results on various datasets show that (1) eigendecomposition lead to lower relative error in Shapley error than the Nystrom approximation and (2) LRFShap can achieve 20x over speedup and for smaller ranks, LRFShap evaluates fewer coalitions before truncating Monte Carlo.
Critical strengths
- The problem tackled is significant. Reducing the computational cost of Data Shapley/FreeShap will benefit downstream applications. The empirical results clearly demonstrate the strengths of using low rank eigendecomposition
Critical weaknesses
- The main paper does not explicitly or sufficiently discuss alternative speedup for Data Shapley/FreeShap.
- App B in FreeShap mentions using block inverse and incrementally computing the inverse/predictions. As the Shapley permutation sampling result in nested sequences/leading principal submatrices, it is also possible to compute the Cholesky decomposition only once per permutation to compute all inverses/predictions. Thus, in Sec 3.2, FreeShap can require operations instead of operations.
- Is LRFShap still needed then? Do LRFShap also benefit from incremental computation? There is some discussion in Table 5 in the appendix but no discussion in the main paper and experimental results.
- Can LRFShap be used with other Shapley approximation methods (not permutation sampling)?
- There are some negative/unclear experiment results.
- The writing in Sec 3 is not easy to follow.
- Do the propositions have different implications for the eigendecomposition and Nystrom approximation?
- It would be better to clearly separate between (1) just applying existing low-rank approximation methods and (2) new contributions/steps that are unique to Shapley value approximation. Some details in (1) can be abstracted away.
Questions for authors
- Address weakness 1.
- Why do LRFShap seem to perform significantly worse than FreeShap for some cases (e.g., wrong label detection)?
- Why are the Spearman/Pearson correlations much lower for some datasets (RTE) in Fig 9? Can the correlation be improved further?
- Address weakness 3.
9 comments
Answer for weakness 1-3 (Can LRFShap be ...)
Thank you for this comment. Yes, LRFShap can be used with Shapley value approximation methods other than permutation sampling.
Why LRFShap can be combined with other estimators
This is possible because LRFShap changes only one step, the computation of the utility. The estimators of the kind mentioned by the reviewer treat the utility as a user-provided black box and only require that it can be evaluated for an arbitrary coalition and is bounded. For example, Li & Yu (2024) treat as a user-specified utility function, give "the performance of a model trained on " as an example, and assume only in their convergence analysis. Our utility lies in and can be computed for any , whether with FreeShap or with LRFShap, so it satisfies this condition. In addition, the eNTK matrices and the features are computed only once before any estimator is run (line 2 of Algorithm 1), exactly as in FreeShap. The only LRFShap-specific part of Algorithm 1 is lines 12–14 (the computation of ); lines 4–11 and 16, which sample coalitions and aggregate marginal contributions, belong to TMC.
Examples
Therefore, any estimator that calls as a black box can be combined with LRFShap as is. Concretely, GELS-Shapley (Li & Yu, 2024) draws a size with probability , draws a subset of that size uniformly, evaluates , and updates the running averages of all elements of ; group testing (Jia et al., 2019) recovers from the values of subsets drawn in the same way; MSR (Wang & Jia, 2023) estimates the Banzhaf value from of subsets in which each element is included independently with probability ; and stratified sampling (Burgess & Chapman, 2021) evaluates within strata of coalition size. In all four cases, is computed by Equation (6), and the estimator code is unchanged. Our convention amounts to a constant shift, since these estimators use only in the form .
Computational gain in this setting
We note two differences from the setting in the paper. First, the cost ratio changes. The incremental computation mentioned by the reviewer (block inverse, or one Cholesky factorization per permutation) is possible only when the coalitions form nested prefixes, so the ratio is for permutation-based estimators (TMC; Mitchell et al., 2022). For estimators that sample coalitions independently, such as the four above, FreeShap must perform a new factorization costing for every utility evaluation (even when using the Schur complement with respect to the complement set), whereas LRFShap needs only regardless of the sampling scheme. For medium-sized coalitions this ratio reaches , and the direct-factorization comparison in Section 3.2 corresponds exactly to this case. For coalitions with there is no dimension reduction (Appendix F), but such coalitions are cheap for both methods. Second, these estimators have no TMC early stopping, so the early-stopping effect in Figure 4 disappears, and the speedup factors reported in the paper do not transfer directly.
Answer for question 2
Performance drop in WLD
The drop in WLD is concentrated at rank 1%. In 14 of the 15 settings in Tables 17–19, rank 1% is lower than the baseline by more than 0.01, and at rank 5%, AG News, MR, SST-2, CIFAR-10, QQP (Llama-2), and MRPC (BERT) return to within 0.01. QQP (BERT), RTE (BERT), and MNLI (Llama-2) need 10%, MRPC (Llama-2) 15%, RTE (Llama-2) 20%, and MNLI (BERT) 30%. In contrast, for data selection, rank 1% is sufficient in 11 of the 15 settings (Table 1). The required rank differs across tasks, and WLD requires the highest rank.
Cause analysis
We attribute the cause to the kind of functions that a low-rank predictor can represent. A rank- predictor can only produce smooth functions expressed by the top eigen-directions. The effect of a label-flipped sample on predictions is a local pattern, namely "a label opposite to its neighbors," and reflecting this pattern in predictions requires the tail eigen-directions. Hence, with a low-rank predictor, adding a label-flipped sample to a coalition does not degrade predictions much, and the marginal contribution of that sample becomes less negative. In our experiments, the fraction of label-flipped samples receiving negative values decreases for all datasets and models (by up to 9.7%p, median about 4.6%p; BERT RTE %, Llama-2 MR %), and the recall within the bottom 10% and the clean/flipped separation AUC decrease together. At rank 5% the gap narrows: AG News, MR, and CIFAR-10 return to the FreeShap level or above, while the gap remains for MNLI, RTE, and MRPC, which need higher ranks. On the other hand, the Spearman correlation within the bottom 20% (by FreeShap value) is actually higher than that within the top 20% (14 of 15), so the ordering within the tail is not disturbed. Rather, the values of the label-flipped samples are shifted as a whole toward those of the clean samples.
Difference between selection and WLD
The same shift has little effect on selection because the two metrics are of a different nature. Selection measures the accuracy of a model trained on the top- set, so even if the composition of the set changes, the accuracy hardly changes as long as the replaced samples are of similar quality. Indeed, at rank 1% the Spearman correlation between LRFShap and FreeShap is 0.45–0.83 (Figures 8–9), which is far from perfect, yet selection is within 0.01 of the baseline in 12 of 15 settings. In contrast, at the same rank, WLD is lower by more than 0.01 in most cases. The same approximation error appears differently in the two metrics.
Planned revisions
In the revision, we will add a table of the minimum comparable rank for each task and dataset, and state in the caption of Table 1 that it is based on data selection. For WLD, we recommend rank 5–10% in most settings and higher for MNLI and RTE; even at rank 5%, a speedup of about 4–11× (excluding RTE) is maintained on BERT (Table 8).
Answer for weakness 1-1 and 1-2 (App B ... & Is LRFShap still ...)
We thank the reviewer for the positive and constructive feedback. We address your concerns here.
Exact computational complexity of FreeShap
We agree with this point. Under permutation sampling, the coalitions are nested prefixes, so KSS+γI∣S∣ is a leading principal submatrix of KNN+γI∣N∣ reordered according to the permutation. As the reviewer notes, one Cholesky factorization per permutation yields the factors of all prefix systems, and each prefix then requires only O(p2) triangular solves, so the solutions and predictions for all ∣N∣ prefixes can be obtained in O(∣N∣3) per permutation. The O(B∣N∣4) in Section 3.2 was stated under a direct-factorization convention in which every prefix system is factorized from scratch. Presenting this as the cost of FreeShap was an overstatement, and we will correct it in the revision.
Implementation of FreeShap and LRFShap
We would like to clarify, however, that our experiments were already conducted against the incremental baseline. Our FreeShap baseline uses the block-inverse scheme of the official implementation as is (FreeShap, Appendix B): from coalition size h=500 on, the inverse is updated incrementally, and it is recomputed at every multiple of h to limit accumulated round-off (Appendix F). LRFShap likewise uses Sherman–Morrison updates in feature space, at O(q2) per prefix. Therefore, the speedups reported in Tables 8–10 are measured against the incremental baseline with O(∣N∣3) per permutation, not against an O(∣N∣4) baseline.
Corrected complexity statement
In the revision, we will move the incremental comparison to the main text. Per permutation, FreeShap costs O(∣N∣3+∣C∣∣N∣2∣T∣) and LRFShap costs O(∣N∣2q+∣C∣∣N∣q∣T∣), so the ratio is approximately ∣N∣/q (currently Table 5). The direct-factorization ratio (∣N∣/q)2 will be stated as the comparison that applies to estimators whose coalitions are not nested (e.g., group testing and least-squares estimators), since incremental updates cannot be used in that case. When q is 1% of ∣N∣, we have ∣N∣/q=100, and the observed 13–22× include the eigendecomposition time, direct solves for coalitions with ∣S∣<q or ∣S∣<h, and fixed overheads, so they are consistent with the theoretical ratio.
The Cholesky-once scheme suggested by the reviewer and the block-inverse scheme have the same order; the former avoids periodic recomputation and is numerically cleaner. One difference is that, under TMC early stopping, the former pays the O(∣N∣3) factorization cost up front, whereas the latter pays only for the prefixes that are actually evaluated; when early stopping occurs early (e.g., Llama-2 on MR, convergence ratio 18%), the latter is therefore the cheaper baseline.