Generalized Group Data Attribution

Thank you for your thoughtful review of our paper. We would like to address the weaknesses you pointed out and provide clarification on the questions raised.

W1: Property function is not a contribution

We agree that the property function is not a novel contribution of our work. We simply wanted to highlight that our method is capable of handling general property functions as an additional feature. We have changed the writing in our revised version to clarify this point and avoid any potential misunderstanding about our claimed contributions.

W2a: Computational advantage doesn’t apply to Hessian computation

This is a very astute observation regarding the Hessian! It is true that modifying the Hessian estimation is critical to reducing the computational complexity of attribution estimation. While our draft has neglected to mention this in detail, our implementation also subsequently involves Hessian approximations, where we denote the Hessian as $H_{\theta} = \sum_z \nabla^2 \ell(z)$, thus rendering it to be a sum over number of groups. We mention this for TRAK, where we refer to the subsequent Fisher approximation as a “batched” Fisher approximation. We perform similar “batched” Hessian approximations for influence functions using the LiSSA estimator to ensure that per-sample computations are never performed. We again apologize for neglecting to discuss these batched Hessian approximations in our draft!

W2b: Whether batched approximation is good

We agree with the reviewer’s intuition that clustering algorithms are required to ensure a small approximation error. We emphasize that this is exactly the purpose of our group selection strategies! In particular, we found the gradient-based clustering to be highly effective, pointing to exactly the approximation benefit described by the reviewer.

Q1: TracIn definition is not standard

Thanks for bringing this to our notice! Our definition in equation (3) does deviate from the one proposed in the TracIn paper with a constant term involving the learning rate pre-multiplier. If a constant learning rate schedule is used throughout training, our variant is equivalent to the one proposed in the TracIn paper.

Please see the discussion in Appendix A.2 and A.3 for a complete discussion of the TracIn variant we employ.

Q2: Grad-K-Means requires individual gradients

We agree that a full gradient computation will brings down efficiency. Therefore, we choose to use gradients wrt last layer activations and NOT gradients wrt parameters as we discuss in line 354. Please also note that, as discussed in the paper, it is hard to efficiently compute batched versions of gradients wrt parameters, but not so for gradients wrt activations, whose batched versions can be trivially computed. While we agree that any grouping method must scale with $n$, our grouping method in practice is cheap and does not involve computing per-sample gradients wrt weights. Furthermore, these groups only need to be computed once offline, and do not need to be recomputed for subsequent influence estimations for new test data points / model properties.

Q3: Typos

Thank you for pointing out the typos. We have fixed them in the revised version of the paper.

Remark

Thank you once again for your insightful suggestions and comments, which have been instrumental in enhancing the quality of our paper. We believe that we have addressed all the concerns. If there is any aspect that you feel has not been fully resolved, we would be happy to provide further information. If you are satisfied with our response, we would truly appreciate your consideration in raising your evaluation score.

Thank you for your thoughtful review of our paper. Please see our response to the weaknesses and the questions below.

W1: large scale experiments

We are actively working on running experiments on ImageNet. This requires significant computational resources and running time. We will update the paper with these results as soon as they are available.

W2: Lack of K-Means analysis and runtimes.

Yes, we totally agree that an analysis of K-means runtime and providing more details about the code will enhance the paper, especially for reproducibility. Our K-means is based on a public implementation https://github.com/subhadarship/kmeans_pytorch. Our code is available in the supplementary material.

In analyzing computational costs, we would like to first highlight the distinction between two types of costs for any attribution method:

1. The offline training time cost, which refers to all computational overhead incurred during the preprocessing and model preparation phase. This includes data processing, model training, and any preparatory steps needed before deployment. Many retraining-based attribution methods like TRAK inherently have significant training time costs, as they require training multiple model checkpoints for ensemble.

2. The online serving time cost, which refers to the computational cost incurred during the actual attribution score computation for each test point.

The difference between these two types of costs is that the offline training time cost is incurred only once, and will be amortized over many test points, while the online serving time cost is incurred once for each attribution computation.

The K-means clustering in our approach belongs entirely to the offline training time cost category since it can be performed offline as a preprocessing step. The clustering is completed before seeing any test points and does not impact the online serving. Therefore, we choose to compare the serving time cost of attribution methods for practical consideration.

Nevertheless, we provide a detailed K-means runtime analysis below. Following the notation in [1], we let n be the number of training data points, p be the number of model parameters, d be the (hidden) feature dimension, and m be the number of test data points we want to compute the attribution for. Additionally, we let T be the number of training iterations (for TracIn), and J be the number of checkpoints to be ensembled (for TRAK). The results are shown in the Table below.

We start by explaining IF. Its run time is O(np) for each test data point [1], and O(mnp) in total for the entire test set. The GGDA version of IF will include the K-means computation, but only once. K-means has time complexity O(Knd), but using GGDA can bring down the per test instance time complexity to O(Kp). Therefore, GGDA-IF has time complexity O(mKp) + O(Knd).

Similarly, TracIn has time complexity O(mnpT). TRAK has a serving time complexity O(mnpJ), but also additional model training time O(npTJ).

For all cases, the GGDA runtime will be significantly better when K << n, which is the setting we adopt. Also, as m gets larger, the efficiency gain of GGDA will be further enhanced.

We also show that GGDA is much more efficient empirically even counting K-means time. In the tables below, we show the GGDA total attribution time (column 3) for IF-LiSSA, TracIn, and TRAK. The runtime of the original DA methods is bolded (row 1 with group size 1, i.e., n = K), whereas GGDA can be more than ten times faster even with K-means for larger K.

IF-LiSSA |GroupSize(n/K)|MeanGroupingTime|MeanAttributionTime|MeanTotalTime| |-|-|-|-| |1|0.00|612.90|612.90| |4|169.03|194.84|363.88| |16|127.63|77.62|205.26| |64|92.25|37.82|130.06| |256|58.87|29.34|88.21| |1024|28.54|27.27|55.80|

TracIn |GroupSize(n/K)|MeanGroupingTime|MeanAttributionTime|MeanTotalTime| |-|-|-|-| |1|0.00|430.17|430.17| |4|169.03|134.48|303.51| |16|127.63|57.25|184.89| |64|92.25|41.02|133.27| |256|58.87|36.82|95.69| |1024|28.54|35.60|64.13|

TRAK |GroupSize(n/K)|MeanGroupingTime|MeanAttributionTime|MeanTotalTime| |-|-|-|-| |1|0.00|4317.43|4317.43| |4|172.80|1463.22|1636.01| |16|132.48|617.34|749.82| |64|93.77|405.86|499.63| |256|57.68|349.92|407.59| |1024|28.54|335.64|364.18|

[1] Hammoudeh, Z., & Lowd, D. (2024). Training data influence analysis and estimation: A survey. Machine Learning, 113(5), 2351-2403.

Remark

Thank you once again for your insightful suggestions and comments, which have been instrumental in enhancing the quality of our paper. We believe that we have addressed all the concerns. If there is any aspect that you feel has not been fully resolved, we would be happy to provide further information. If you are satisfied with our response, we would truly appreciate your consideration in raising your evaluation score.

Thank you for your thoughtful review of our paper. Please see our response to the weaknesses and the questions below.

W1: large-scale experiments on ImageNet

We are actively working on running experiments on ImageNet. This requires significant computational resources and running time. We will update the paper with these results as soon as they are available.

W2: individual vs batch gradient speed, and efficient implementation using vmap.

We agree that our statement about batched gradient computation and per-sample gradient computation wasn't clear enough. What we meant was that computing gradients of a batch of B samples is much more efficient than looping through each of those B samples and computing gradients one at a time, because the computation of a larger B is not too much slower than the case of B = 1.

Regarding your suggestion about using efficient implementations like vmap. We were not using it but we really appreciate the suggestion. We indeed found that using vmap can speed up both per-sample gradient and batched gradients, which we illustrate in the table below. For this experiment, we consider the run time (ms) for computing gradients for 8192 training data points in four different cases, where we compare per-sample vs. batch and vmap vs. non-vmap.

We would like to emphasize that 1) Although we were not using vmap, our comparison in the paper was fair because all implementations didn't use it 2) Optimizations like vmap are orthogonal to what we are proposing and can be combined with our GGDA method as well.

We will consider rerunning our experiments with vmap in our next version. We really appreciate the suggestion.

W3: Table ± symbols

Thank you for seeking clarification here. The ± symbols in the tables do indeed indicate multiple training trials across 10 different seeds, while keeping groups and attributions fixed. Table 1 presents Logistic Regression (LR) results, where there is no variation across training trials due to convexity (hence, ± 0.0). We have updated the table captions to clarify these points.

W4: Add baselines to pruning tables.

Thank you for the suggestion. The baseline of no removal is added to both Table 1 and Table 2, where we see a clear improvement with GGDA.

W5: Rationale for clustering by activation gradient vs activations

We investigate both clustering strategies and find that gradient k-means outperforms activation k-means in most cases. The effectiveness of gradient k-means can be attributed to that it naturally aligns with how attribution values are calculated for most methods, particularly influence functions. This alignment helps ensure that points grouped together are likely to have similar attribution values.

However, this alignment is not guaranteed, which is why we investigate multiple grouping strategies in our work. The key insight is that an ideal grouping strategy should cluster together points with similar attribution values. The degree of this similarity can vary depending on the specific dataset and attribution method being used.

Q1: Why does grouping attribution outperform single-point attribution on data pruning?

We hypothesize that GGDA's superior performance in pruning stems from two key factors:

First, while per-sample attributors excel at identifying highly important datapoints, they struggle with accurately estimating the least important points, which is crucial for pruning tasks. This means that while the ranking of datapoint importance is reliable for important points, it becomes less accurate for unimportant ones. We believe this may be due to numerical instabilities in Hessian estimation, particularly affecting influence function methods. The use of groups in GGDA helps mitigate this by smoothing out independent estimation errors across different points.

Second, the effectiveness of GGDA relies heavily on appropriate group selection strategies. For semantically coherent data groups, the attribution values of all points within the groups should be uniform. This makes the identification of coherent data groups crucial for accurate attribution estimation. In contrast, bad grouping creates semantically incoherent sets of samples, making it difficult to estimate accurate attributions for the group as a whole. This highlights why proper group selection is crucial for realizing the benefits of our approach.

Remark

Thank you once again for your insightful suggestions and comments, which have been instrumental in enhancing the quality of our paper. We believe that we have addressed all the concerns. If there is any aspect that you feel has not been fully resolved, we would be happy to provide further information. If you are satisfied with our response, we would truly appreciate your consideration in raising your evaluation score.

Thank you for your patience and for engaging in our paper's discussion. Please see our global response on ImageNet results. We do observe that GGDA continues to maintain significant speedups in this large scale setting.

With regards to grouping/kmeans timing, the computation of penultimate layer activation gradients for the entire training set was ~1 hour / 3600 seconds and ~ 175 seconds, 955 seconds, and 3800 seconds for grad-K-Means grouping on group sizes 1024, 256 and 64 respectively. These times are small in comparison to the overall 88,000 seconds runtime for standard DA (group size 1) and may also be considered as pre-processing steps as previously mentioned to Reviewer X7t6.

Regarding evaluation, we are unable to perform retraining based evaluations in time, since training even the ResNet-18 on ImageNet requires significant runtime (>30 hours per retraining). We kindly refer to our ResNet-18 results for CIFAR-10 (Figure 2 in the pdf), where GGDA remains within +/- 0.5% test accuracy w.r.t. DA (lower test accuracy is better in the plot).

Thank you for your thoughtful review. Please see our response to the weaknesses and the questions below.

W1: Limited novelty

We want to clarify a potential misunderstanding here. While using groups instead of individual data points may seem conceptually straightforward, there are significant technical challenges and novel contributions in our work:

First, determining effective grouping strategies is non-trivial. We systematically investigate and compare four different grouping approaches, each with distinct theoretical and practical implications. Such comprehensive analysis of grouping strategies is novel to our knowledge.

Second, extending existing attribution methods to perform well with groups requires careful mathematical consideration and non-trivial algorithmic adjustments. For instance, methods like Influence Functions (IF) need specific modifications for accurate and efficient gradient computation. The complexity lies in properly handling group-level effects while maintaining the theoretical guarantees of the original methods, which we detail in Section 4 along with the modifications needed for other methods like TracIn and TRAK.

Furthermore, a key theoretical insight of our work is that the computational benefits do not come simply from summing individual attributions. Rather, the critical innovation is our ability to compute group attributions directly, reducing complexity from $O(points)$ to $O(groups)$ without performing intermediate per-sample calculations. This property holds for IF-style attributions due to their linearity, though notably not for Leave-One-Out (LOO) attributions where group effects cannot be decomposed into sums of individual effects.

W2: Investigation of combining individual attributions

We appreciate the questions about weighting schemes and robust estimators for combining individual attributions. However, we want to clarify our group attribution process. We don't combine attributions of individual points - instead, we directly compute attributions at the group level. This is a key advantage of our approach, avoiding the need to first compute individual attributions (which incurs significant computational cost).

As derived in our appendix, for IF specifically, the mathematically derived way to compute group attributions is through the summation of individual influences within the group. Importantly, the loss function applied to a group of points should not be mean reduced. The theoretical derivation for TRAK requires more non-trivial and more careful consideration. As such, these are not empirical choices, but follow directly from theoretical foundations.

W3: Why does GGDA work so well for pruning?

We hypothesize that GGDA's superior performance in pruning stems from two key factors:

First, while per-sample attributors are good at identifying highly important data points, they struggle with accurately estimating the least important points, which is crucial for pruning tasks. This means that while the ranking of data point importance is reliable for important points, it becomes less accurate for unimportant ones. We believe this may be due to numerical instabilities in Hessian estimation, particularly affecting IF methods. The use of groups in GGDA helps mitigate this by smoothing out independent estimation errors across different points.

Second, the effectiveness of GGDA relies heavily on appropriate group selection strategies. For semantically coherent data groups, the attribution values of all points within the groups should be uniform. This makes the identification of coherent data groups crucial for accurate attribution estimation. In contrast, bad grouping creates semantically incoherent sets of samples, making it difficult to estimate accurate attributions for the group as a whole.

We believe that further investigation into these aspects presents an interesting direction for future research.

Q1: Why does grad-k-means work so well?

The effectiveness of gradient k-means can be attributed to it naturally aligning with how attribution values are calculated for most methods, particularly IF. This alignment helps to ensure that points grouped together are likely to have similar attribution values.

However, this alignment is not guaranteed, which is why we investigate multiple grouping strategies in our work. The key insight is that an ideal grouping strategy should cluster together points with similar attribution values. The degree of this similarity can vary depending on the specific dataset and attribution method being used.

Remark

Thank you once again for your insightful suggestions and comments. We are actively incorporating the above explanations to enhance the quality of our paper. If there is any aspect that you feel has not been fully resolved, we would be happy to provide further information. If you are satisfied with our response, we would truly appreciate your consideration in raising your evaluation score.

Thank you for your patience and for engaging in our paper's discussion. Please see our global response on ImageNet results. We do observe that GGDA continues to maintain significant speedups in this large scale setting.

With regards to grouping/kmeans timing, the computation of penultimate layer activation gradients for the entire training set was ~1 hour / 3600 seconds and ~ 175 seconds, 955 seconds, and 3800 seconds for grad-K-Means grouping on group sizes 1024, 256 and 64 respectively. These times are small in comparison to the overall 88,000 seconds runtime for standard DA (group size 1) and may also be considered as pre-processing steps.