acceptodds
Under review as a conference paper at ICLR 2027

On the Low Rank Theory for the Data Shapley: Kernel Perspective

Abstract

Data Shapley offers a principled framework for data valuation, but remains costly to compute at scale. Although FreeShap avoids repeated model fine-tuning through kernel regression, evaluating many sampled coalitions remains computationally demanding. Low-rank kernel approximation offers a natural acceleration strategy, but its effect on individual Data Shapley values is poorly understood. We investigate how kernel approximation relates to prediction and Data Shapley. Our analysis shows that kernel approximation error controls errors in individual Data Shapley values, whereas predictive agreement alone does not guarantee Shapley agreement. Together with our experiments, these results indicate that eigendecomposition is more reliable than Nystr\"om approximation for Data Shapley. Guided by this analysis, we propose LRFShap, which accelerates coalition evaluation using shared low-dimensional kernel features. Across three downstream tasks, LRFShap achieves performance comparable to FreeShap at suitable ranks, with speedups of up to on data selection.

Primary area:
interpretability and explainable AI
Keywords:
Data valuation, Data Shapley, Low rank kernel approximation, Neural tangent kernel

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_6zsbOpenReview ↗
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
  1. 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
  1. 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 O(B∣N∣3)O(B|N|^3) operations instead of O(B∣N∣4)O(B|N|^4) 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)?
  2. There are some negative/unclear experiment results.
  3. 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
  1. Address weakness 1.
  2. Why do LRFShap seem to perform significantly worse than FreeShap for some cases (e.g., wrong label detection)?
  3. Why are the Spearman/Pearson correlations much lower for some datasets (RTE) in Fig 9? Can the correlation be improved further?
  4. Address weakness 3.
9 comments
AuthorsOpenReview ↗

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∣K_{SS}+\gamma I_{|S|} is a leading principal submatrix of KNN+γI∣N∣K_{NN}+\gamma 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)O(p^2) triangular solves, so the solutions and predictions for all ∣N∣|N| prefixes can be obtained in O(∣N∣3)O(|N|^3) per permutation. The O(B∣N∣4)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=500h=500 on, the inverse is updated incrementally, and it is recomputed at every multiple of hh to limit accumulated round-off (Appendix F). LRFShap likewise uses Sherman–Morrison updates in feature space, at O(q2)O(q^2) per prefix. Therefore, the speedups reported in Tables 8–10 are measured against the incremental baseline with O(∣N∣3)O(|N|^3) per permutation, not against an O(∣N∣4)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∣)O(|N|^3+|C||N|^2|T|) and LRFShap costs O(∣N∣2q+∣C∣∣N∣q∣T∣)O(|N|^2q+|C||N|q|T|), so the ratio is approximately ∣N∣/q|N|/q (currently Table 5). The direct-factorization ratio (∣N∣/q)2(|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 qq is 1%1\% of ∣N∣|N|, we have ∣N∣/q=100|N|/q=100, and the observed 13–22× include the eigendecomposition time, direct solves for coalitions with ∣S∣<q|S|\lt q or ∣S∣<h|S|\lt 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)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.

AuthorsOpenReview ↗

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 U(S)U(S) as a user-provided black box and only require that it can be evaluated for an arbitrary coalition SS and is bounded. For example, Li & Yu (2024) treat UnU^n as a user-specified utility function, give "the performance of a model trained on SS" as an example, and assume only ∥Un∥∞≤u\lVert U^n\rVert_\infty\le u in their convergence analysis. Our utility Uacc(S)U_{acc}(S) lies in [0,1][0,1] and can be computed for any SS, whether with FreeShap or with LRFShap, so it satisfies this condition. In addition, the eNTK matrices KNN,KTNK_{NN},K_{TN} and the features (Φtr,Φte)(\Phi_{tr},\Phi_{te}) 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 U(S)U(S)); lines 4–11 and 16, which sample coalitions and aggregate marginal contributions, belong to TMC.

Examples

Therefore, any estimator that calls U(S)U(S) as a black box can be combined with LRFShap as is. Concretely, GELS-Shapley (Li & Yu, 2024) draws a size ss with probability ∝n/(s(n−s))\propto n/(s(n-s)), draws a subset SS of that size uniformly, evaluates U(S)U(S), and updates the running averages of all elements of SS; group testing (Jia et al., 2019) recovers ϕi−ϕj\phi_i-\phi_j from the values U(S)U(S) of subsets drawn in the same way; MSR (Wang & Jia, 2023) estimates the Banzhaf value from U(S)U(S) of subsets SS in which each element is included independently with probability 1/21/2; and stratified sampling (Burgess & Chapman, 2021) evaluates U(S∪i)−U(S)U(S\cup i)-U(S) within strata of coalition size. In all four cases, U(S)U(S) is computed by Equation (6), and the estimator code is unchanged. Our convention U(∅)=0U(\emptyset)=0 amounts to a constant shift, since these estimators use U(∅)U(\emptyset) only in the form U(N)−U(∅)U(N)-U(\emptyset).

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 ∣S∣/q|S|/q 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 O(min⁡(∣S∣,∣N∣−∣S∣)3)O(\min(|S|,|N|-|S|)^3) for every utility evaluation (even when using the Schur complement with respect to the complement set), whereas LRFShap needs only O(∣S∣q2+q3)O(|S|q^2+q^3) regardless of the sampling scheme. For medium-sized coalitions this ratio reaches (∣S∣/q)2(|S|/q)^2, and the direct-factorization comparison in Section 3.2 corresponds exactly to this case. For coalitions with ∣S∣<q|S|\lt q 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.

AuthorsOpenReview ↗

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-rr predictor can only produce smooth functions expressed by the top rr 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 57.6→47.957.6\to 47.9%, Llama-2 MR 87.0→81.087.0\to 81.0%), 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-k%k\% 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).

Reviewer_ockLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies how low-rank kernel approximation affects individual Data Shapley values in the eNTK-based, fine-tuning-free regime. It makes three contributions.

As far as I understand, to compute Shapley value, it first builds the low-rank NTK kernel matrices. Then grab a permutation, and for every prefix, take the prefix subset S to compute the prediction on testing set DTD_T, with which we can easily calculate the utility of the model with S. When the utility converges, we can assign zero marginal utility to the rest of the suffix (Though this step is really just a heuristic.). We do this for many permutations, and then we will be able to compute Shapley value as an average for each training point.

The main advantage over existing method FreeSHAP is that we don't pay for the full kernel computation. There's a new discovery in the paper, a more faithful low-rank approximation is not always better for data Shapley.

Critical strengths
  • LRFShap is a sensible and effective engineering contribution for computing FreeShap
  • The eigendecomposition vs. Nyström comparison is practically valuable.
Critical weaknesses
  • NTK regression is a surrogate for classification. The paper uses the first-logit eNTK and kernel ridge regression to approximate fine-tuning, then evaluates classification accuracy. The NTK framework is best understood for squared-loss regression; its use for classification is a known heuristic. In particular, the accuracy utility is a non-smooth function of the kernel, so the stability bound for the squared-error utility does not directly transfer.
  • The empirical evaluation is narrow relative to the data-valuation literature. FreeShap is the natural baseline because LRFShap accelerates it, but the paper does not compare against simpler data-selection baselines for SFT: for example, see paper "DATE-LM: Benchmarking Data Attribution Evaluation for Large Language Models". Prior work has shown that data selection for LLM fine-tuning is often difficult, and that sophisticated attribution methods do not always beat simple baselines. Without such comparisons, it is hard to judge whether LRFShap's Shapley values (including FreeShap's) are useful for downstream data selection.
  • Novelty is incremental, though reasonable. The paper combines well-known ingredients: eNTK regression (FreeShap), low-rank kernel approximation. The eigendecomposition-vs-Nyström empirical finding is useful but not deeply surprising: eigendecomposition is the optimal spectral approximation, so it should preserve spectral quantities better than sampling-based Nyström.
Questions for authors

See weaknesses.

10 comments
AuthorsOpenReview ↗

Response to summary

Thank you for summarizing our work. We would like to clarify a few points.

The truncation step mentioned in your summary is the truncated Monte Carlo (TMC) heuristic introduced by Ghorbani and Zou [1], which we adopt following FreeShap [2]. This step is optional. Our low-rank coalition evaluation and theoretical results do not rely on truncation, and our method also supports untruncated permutation Monte Carlo.

Regarding the computational advantage over FreeShap, we construct low-dimensional kernel features once and reuse them across coalition evaluations, reducing the costs of regression and test prediction performed at each prefix of each permutation. Thus, the computational benefit comes from accelerating these repeated evaluations.

[1] Amirata Ghorbani and James Zou. “Data Shapley: Equitable Valuation of Data for Machine Learning.” ICML, PMLR 97:2242–2251, 2019.

[2] Jingtan Wang, Xiaoqiang Lin, Rui Qiao, Chuan-Sheng Foo, and Bryan Kian Hsiang Low. “Helpful or Harmful Data? Fine-tuning-free Shapley Attribution for Explaining Language Model Predictions.” ICML, PMLR 235:50960–50991, 2024.

AuthorsOpenReview ↗

Answer for weakness 1 (NTK regression is a ...) (1)

We thank the reviewer for the positive and constructive feedback. We agree that the stability bound for the squared-error utility does not directly apply to the accuracy utility. Our theoretical analysis focuses on the effect of low-rank approximation on Data Shapley values within a kernel regression surrogate. Below, we first explain the scope of the NTK framework and the rationale for using this surrogate. We then distinguish the estimation of accuracy-based Data Shapley values from their stability under kernel approximation and discuss the additional conditions required for the latter.

1. Scope of the NTK framework

NTK dynamics are not restricted to the squared loss. Jacot et al. [1] explicitly include cross-entropy, and Lee et al. [2] derive the dynamics for softmax cross-entropy. What is special about the squared loss is that, with a fixed kernel, the prediction dynamics become linear and admit a closed-form solution.

Malladi et al. [3] show that, under suitable conditions, fine-tuning pretrained models can follow kernel dynamics, and investigate this connection empirically in prompt-based fine-tuning. Building on this connection, FreeShap [4] uses the eNTK computed at the pretrained weights to approximate coalition-specific fine-tuning by kernel regression.

Following FreeShap, we use the first-logit eNTK and a ridge-regression predictor. In the main text and Appendix B, we explicitly state the kernel-regime assumptions underlying this connection: the first-order linearization of the network remains valid during training, and the eNTK remains approximately constant. Furthermore, in Appendix C and Proposition 3.1, we quantitatively bound the difference between the Shapley values induced by finite-time gradient flow and those induced by the stationary predictor in a fixed RKHS with a regularized squared loss. This provides a theoretical justification for using the stationary predictor in that setting.

Our focus is on analyzing how low-rank kernel approximation affects Data Shapley values within this surrogate. This analysis does not guarantee equivalence to actual fine-tuning with cross-entropy. In Section 5, "Limitations and future work," we identify extensions beyond the kernel regime that account for changes in representations and kernels during fine-tuning as a direction for future research.

[1] Arthur Jacot, Franck Gabriel, and Clément Hongler. "Neural Tangent Kernel: Convergence and Generalization in Neural Networks." Advances in Neural Information Processing Systems, 31, 2018.

[2] Jaehoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. "Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent." Advances in Neural Information Processing Systems, 32, 2019.

[3] Sadhika Malladi, Alexander Wettig, Dingli Yu, Danqi Chen, and Sanjeev Arora. "A Kernel-Based View of Language Model Fine-Tuning." International Conference on Machine Learning, 2023.

[4] Jingtan Wang, Xiaoqiang Lin, Rui Qiao, Chuan-Sheng Foo, and Bryan Kian Hsiang Low. "Helpful or Harmful Data? Fine-tuning-free Shapley Attribution for Explaining Language Model Predictions." International Conference on Machine Learning, 2024.

2. Applicability to the accuracy utility

Data Shapley values can also be defined for the accuracy utility and estimated using permutation Monte Carlo. For example, Wu et al. [5] use the boundedness of the accuracy utility and its corresponding marginal contributions to control the Shapley estimation error due to permutation sampling via Hoeffding's inequality. This guarantee does not require accuracy to be continuous or differentiable with respect to the prediction scores.

However, this result concerns the error arising from estimating the Shapley values of a fixed accuracy utility using finitely many sampled permutations. In contrast, low-rank kernel approximation can change the prediction scores and the accuracy utility itself, so the resulting change in Shapley values requires a separate analysis.

AuthorsOpenReview ↗

Answer for weakness 1 (NTK regression is a ...) (2)

Since accuracy is discontinuous at classification decision boundaries, even a small change in prediction scores can change whether a prediction is correct. Therefore, connecting prediction-score stability to the stability of accuracy-based Shapley values requires additional control of classification margins. To make this concrete, let FS(t,c)F_S(t,c) denote the prediction score of class cc for test example tt computed with the full kernel on coalition SS, and let ct⋆c_t^\star be the correct class of tt. We define the margin for each coalition as

mS(t):=FS(t,ct⋆)−max⁡c≠ct⋆FS(t,c).m_S(t):=F_S(t,c_t^\star)-\max_{c\ne c_t^\star}F_S(t,c).

A positive margin indicates a correct classification, whereas a negative margin indicates a misclassification. We also define the fraction of test examples near the decision boundary and the maximum prediction-score error between the full-kernel and approximate-kernel predictors, respectively, as

QS(a):=1∣T∣∑t∈T1{∣mS(t)∣≤a},εS:=max⁡t∈T, c∣FS(t,c)−F~S(t,c)∣.Q_S(a):=\frac{1}{|T|}\sum_{t\in T}\mathbf 1\{|m_S(t)|\le a\},\qquad \varepsilon_S:=\max_{t\in T,\,c}|F_S(t,c)-\widetilde F_S(t,c)|.

One sufficient condition is the following linear bound on the fraction of test examples with small margins, with a common constant across all nonempty coalitions:

QS(a)≤Ba,a≥0,∅≠S⊆N,B>0.Q_S(a)\le Ba,\qquad a\ge 0,\quad \varnothing\ne S\subseteq N,\quad B>0.

Under this condition, the difference in accuracy utility can be bounded as

∣Uacc(S)−U~acc(S)∣≤QS(2εS)≤2BεS.|U_{\mathrm{acc}}(S)-\widetilde U_{\mathrm{acc}}(S)|\le Q_S(2\varepsilon_S)\le 2B\varepsilon_S.

This bound holds because a change in classification correctness can occur only for test examples whose absolute margin is at most twice the maximum prediction-score error.

If the empty-coalition utilities are identical in the two games, applying this bound to the weighted-average formula for Shapley values also controls the accuracy-based Shapley error. Thus, a similar stability analysis is possible for the accuracy utility under suitable margin assumptions. However, such a uniform margin condition is not guaranteed by our current kernel assumptions, and we therefore do not present a separate stability theorem based on this additional assumption.

In our experiments, we use the accuracy utility to evaluate individual data points' contributions to classification performance and to compare with FreeShap on the same basis, as this baseline also uses the accuracy utility. We explicitly describe and empirically investigate the difference between the theory using the squared-error utility and the implementation using the accuracy utility in Appendix E. In particular, we separately evaluate the agreement between the Shapley estimates obtained using low-rank kernels and those obtained using the corresponding full kernels under the accuracy utility (Table 4 and Figure 5).

[5] Mengmeng Wu et al. "Variance Reduced Shapley Value Estimation for Trustworthy Data Valuation." Computers & Operations Research, 159:106305, 2023.

Reviewer_q1PvOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

Data Shapley assigns a value to each training observation based on its average contribution to model performance across different training subsets. Computing these values is expensive, as it requires evaluating many subsets. FreeShap reduces this cost by replacing model retraining with kernel regression, but evaluating each subset remains computationally demanding. This paper investigates whether low-rank kernel approximations can further reduce this cost while preserving Shapley values. The authors prove that kernel approximation error controls the error in individual Shapley values, while accurate predictions using the full training set do not guarantee accurate Shapley values. Based on this analysis, they propose LRFShap, which uses low-dimensional kernel features to accelerate subset evaluations. The experiments compare two methods for approximating the kernel matrix, which are truncated eigendecomposition and Nyström approximation.

Critical strengths
  1. The theoretical analysis shows that preserving predictions on the full training set does not guarantee accurate Shapley values. The authors also establish a bound on individual Shapley value errors in terms of the kernel approximation error.
  2. The proposed algorithm is straightforward and well motivated. The experiments consistently compare spectral and Nyström approximations and report computational costs. The results demonstrate substantial savings relative to FreeShap.
Critical weaknesses
  1. Proposition 3.2 shows that a small error in the training kernel matrix leads to a small error in Shapley values. However, this result assumes that model performance is measured by squared prediction error and that the kernel matrix relating test and training observations is unchanged. In the experiments, the authors use classification accuracy and approximate both kernel matrices. The theoretical guarantee therefore does not directly apply to the Shapley values computed by LRFShap. The authors acknowledge these differences and examine their effects experimentally in Appendix E, but do not establish a theoretical error bound for the implemented method.
Questions for authors
  1. Appendix E examines the differences between Proposition 3.2 and the implemented LRFShap method experimentally. What prevents the theoretical bound from being extended to this setting? Could a similar bound be established under additional assumptions?
4 comments
AuthorsOpenReview ↗

Answer for weakness 1 and question 1 (1)

We thank the reviewer for the positive and constructive feedback. We agree that the differences between the assumptions of Proposition 3.2 and the implementation should be explained more clearly. In Appendix E, we introduce these differences step by step and examine their effects empirically. Since they have different implications for extending the theoretical analysis, we discuss each separately below.

1. Approximating the test–train kernel block

Proposition 3.2 approximates only the training kernel while keeping the test–train kernel block fixed, whereas the implementation approximates both blocks through the low-rank features. This difference is not a fundamental obstacle to extending the analysis. By decomposing the prediction-score difference into terms associated with perturbations of the two blocks and applying the identity for the difference of two matrix inverses, we can derive a bound that accounts for both approximation errors. This requires controlling the approximation error of the test–train block in addition to that of the training kernel.

Keeping the test–train block fixed is a deliberate analytical choice. We follow the setting of an existing kernel-approximation stability analysis [1] to isolate how training-kernel approximation errors affect individual Data Shapley values. Thus, this assumption serves to separate the additional error contribution and clarify the focus of the analysis; it was not introduced because an extension is impossible.

Appendix E provides complementary empirical evidence. At ranks of 5% and above on both datasets, the Spearman correlations of the variants before and after introducing the test–train approximation, each measured against its corresponding full-kernel reference, differed by at most 0.02. This suggests that the additional approximation had a relatively small effect in these experiments, although this observation does not replace a general theoretical guarantee.

An approach that explicitly accounts for data distributions would also be a useful direction for future research. From this perspective, training and test samples could be treated within a common probabilistic framework, and distribution-level tools such as kernel mean embeddings or MMD may simplify parts of the analysis. However, connecting these tools to coalition-level prediction errors and Shapley stability requires additional assumptions and analysis. The present study focuses on low-rank kernel approximation in a finite-sample setting, leaving such distribution-based extensions for future work.

[1] Corinna Cortes, Mehryar Mohri, and Ameet Talwalkar. "On the Impact of Kernel Approximation on Learning Accuracy." AISTATS, PMLR 9:113–120, 2010.

2. From squared-error utility to accuracy utility

This change requires additional assumptions. Unlike squared error, accuracy is discontinuous at classification decision boundaries, so even a small prediction-score error can change whether a sample is classified correctly.

To address this, we define the classification margin for each coalition using the full-kernel predictions as the difference between the score of the correct class and the highest score among the incorrect classes. In terms of the score matrix and the correct-class label, this is

mS(t):=FS(t,ct⋆)−max⁡c≠ct⋆FS(t,c).m_S(t):=F_S(t,c_t^\star)-\max_{c\ne c_t^\star}F_S(t,c).

A positive margin indicates correct classification, whereas a negative margin indicates misclassification. Samples with smaller absolute margins are more susceptible to changes in classification correctness under score perturbations.

One sufficient condition is a linear upper bound on the proportion of test samples with small absolute margins, with a constant common to all nonempty coalitions:

QS(a):=1∣T∣∑t∈T1{∣mS(t)∣≤a}≤Ba,a≥0,B>0.Q_S(a) := \frac{1}{|T|}\sum_{t\in T}\mathbf 1\{|m_S(t)|\le a\} \le Ba, \qquad a\ge 0,\quad B>0.

If the prediction-score errors across all test samples and classes satisfy

max⁡t,c∣(FS−F~S)t,c∣≤εS,\max_{t,c}\bigl|(F_S-\widetilde F_S)_{t,c}\bigr| \le \varepsilon_S,

then the margin changes by at most twice this error. Consequently, classification correctness is preserved for samples whose original absolute margin exceeds this threshold, giving

∣Uacc(S)−U~acc(S)∣≤QS(2εS)≤2BεS.\bigl|U_{\mathrm{acc}}(S)-\widetilde U_{\mathrm{acc}}(S)\bigr| \le Q_S(2\varepsilon_S) \le 2B\varepsilon_S.

Under this additional margin condition, a similar bound can be derived for accuracy-based Shapley values while retaining the remaining setting of Proposition 3.2. However, the condition must hold uniformly over all nonempty coalitions appearing in the Shapley computation, rather than only the grand coalition. We have not established this condition or controlled the associated constant under our current kernel assumptions. Accordingly, the manuscript does not provide a theoretical guarantee for accuracy-based Shapley values; instead, Appendix E examines the effect of changing the utility empirically.

AuthorsOpenReview ↗

Answer for weakness 1 and question 1 (2)

3. Coalition-size-scaled ridge versus fixed ridge

The theoretical analysis and implementation use different rules for choosing the ridge parameter. Proposition 3.2 uses a ridge proportional to coalition size, whereas the implementation follows FreeShap in using a fixed ridge independent of coalition size:

Theory: ρ∣S∣,Implementation: γ.\text{Theory: } \rho|S|, \qquad \text{Implementation: } \gamma.

In the theoretical setting, learning minimizes the average squared loss plus an RKHS norm penalty with the same coefficient across coalition sizes:

1∣S∣∑i∈S(f(xi)−yi)2+ρ∥f∥Hk2.\frac{1}{|S|}\sum_{i\in S}(f(x_i)-y_i)^2 + \rho\|f\|_{\mathcal H_k}^{2}.

Solving this objective yields a ridge proportional to coalition size in the kernel matrix. Conversely, fixing the ridge added to the matrix corresponds to the objective

1∣S∣∑i∈S(f(xi)−yi)2+γ∣S∣∥f∥Hk2.\frac{1}{|S|}\sum_{i\in S}(f(x_i)-y_i)^2 + \frac{\gamma}{|S|}\|f\|_{\mathcal H_k}^{2}.

Here, the coefficient of the RKHS norm penalty decreases as the coalition grows. For example, doubling the number of samples halves this coefficient. Thus, a coalition-size-scaled ridge keeps the weight of regularization relative to the average squared loss constant, whereas a fixed ridge reduces that weight as more data are included.

This distinction matters when analyzing kernel approximation errors. With a coalition-size-scaled ridge, we obtain

∥(KSS+ρ∣S∣I)−1∥2≤1ρ∣S∣.\bigl\|(K_{SS}+\rho|S|I)^{-1}\bigr\|_2 \le \frac{1}{\rho|S|}.

Proposition 3.2 uses this inequality to obtain a prediction-error bound that decreases inversely with coalition size for a fixed magnitude of kernel approximation error. Since Shapley values aggregate contributions across coalitions of different sizes, this coalition-level error control leads to the final Shapley-error bound.

Appendix D.1 also illustrates why regularization is needed. Without regularization, convergence of gradient flow to the limiting predictor can be very slow, depending on the data. A coalition-size-scaled ridge provides a convergence-rate guarantee that is uniform over coalition size. A fixed ridge also provides positive regularization, so it does not prevent theoretical analysis. The difference is that analogous bounds involve coalition size or the total sample size. Thus, error bounds can also be obtained with a fixed ridge, but the same sample-size dependence as in Proposition 3.2 is not necessarily retained.

We use a fixed ridge in the implementation to compare the effect of low-rank approximation under the same regularization setting as FreeShap. Changing the regularization rule as well would combine the effects of low-rank approximation and altered regularization in the comparison between the two methods. Appendix E examines this difference between theory and implementation separately.

Indeed, under the squared-error utility, increasing the fixed ridge from 0.01 to 0.1 raised the Spearman correlation with the full-kernel Shapley estimates at rank 30% from 0.79 to 0.94 on SST-2 and from 0.85 to 0.97 on MR. These results suggest that stronger regularization can mitigate the effect of low-rank approximation on Shapley values in these experiments. However, they do not establish that a coalition-size-scaled ridge is always superior to a fixed ridge.

We believe that the reviewer's main concerns have been addressed. Therefore, we kindly ask the reviewer to consider raising the score.

Thank you for your detailed response. This answers my question. The guarantee of Proposition 3.2 still does not formally cover the method as implemented, but the gap is now well characterized and complemented by the empirical analysis in Appendix E. I encourage the authors to include this discussion in the revised manuscript. I maintain my score.

Dear Reviewer q1Pv,

Thank you for your follow-up and for confirming that our response answers your question. Following your suggestion, we have incorporated this discussion into Appendix E of the revised manuscript. We believe this addition will help readers better understand our results and their scope. Thank you again for your feedback.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Common response

General Response to All Reviewers

Dear Reviewers,

Thank you for carefully reviewing our paper and providing valuable feedback. Your questions and suggestions have helped us clarify aspects that needed further explanation, address points we had overlooked, and improve the manuscript. This process has also given us an opportunity to learn and reflect more deeply on our research. We sincerely thank all reviewers for their time and effort.

Below, we summarize the key contributions of our work from algorithmic and empirical perspectives, followed by its theoretical contributions.

1. Algorithmic and empirical contributions. Building on FreeShap's eNTK regression, we propose LRFShap, which reuses low-dimensional features obtained through low-rank kernel approximation across coalition evaluations. This reduces the repeated regression and test-prediction costs involved in computing Data Shapley values. Experiments on data selection, data removal, and wrong-label detection using BERT, Llama-2, and ResNet-18 demonstrate that LRFShap maintains performance comparable to FreeShap at suitable ranks, achieving speedups of up to approximately 22× in data selection.

2. Theoretical contributions. In the setting of regularized kernel regression with a squared-error utility, we establish a stability bound that controls individual Data Shapley errors in terms of the training-kernel approximation error (Proposition 3.2). We also show that preserving predictions obtained using the full training set does not, by itself, guarantee the preservation of individual Shapley values (Proposition 3.3). In particular, we construct instances in which uniform Nyström approximation preserves the grand-coalition prediction exactly while incurring substantial relative errors in the Shapley values of some training samples (Corollary 3.1). These results, summarized in the KPS (kernel–prediction–Shapley) diagram in the Introduction, highlight the need to distinguish prediction preservation from Data Shapley preservation when evaluating low-rank approximation methods.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.