Diff-In: Data Influence Estimation with Differential Approximation

Authors: Haoru Tan, Sitong Wu, Bo Zhao, Zeke Xie, XIAOJUAN QI
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords: Deep Learning, Influence Function

Abstract:
In this paper, we introduce a new formulation to approximate a sample's influence by accumulating the differences in influence between consecutive learning steps, which we term Diff-In. Specifically, we formulate the sample-wise influence as the cumulative sum of its changes/differences across successive training iterations. 
By employing second-order approximations, we approximate these difference terms with high accuracy while eliminating the need for model convexity required by existing methods.
Despite being a second-order method, Diff-In maintains computational complexity comparable to that of first-order methods and remains scalable. This efficiency is achieved by computing the product of the Hessian and gradient, which can be efficiently approximated using finite differences of first-order gradients. 
We assess the approximation accuracy of Diff-In both theoretically and empirically. Our theoretical analysis demonstrates that Diff-In achieves significantly lower approximation error compared to existing influence estimators. Extensive experiments further confirm its superior performance across multiple benchmark datasets in three data-centric tasks: data cleaning, data deletion, and coreset selection. 
Notably, our experiments on data pruning for large-scale vision-language pre-training show that Diff-In can scale to millions of data points and outperforms strong baselines.

Decision: reject
Reviewer scores: 6, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730446986110

thread_type:
official_review

<thread_object>
creator: reviewer_3kxb

<content>
summary:
This paper introduces a novel method called Diff-In for estimating the influence of data points during model training. Unlike existing methods that rely on convexity assumptions or first-order approximations, Diff-In calculates the cumulative differences in influence between consecutive training steps. By using second-order approximations of the Hessian-gradient product, it achieves higher accuracy without increasing computational complexity. The approach is scalable and can be applied to large datasets. Extensive experiments demonstrate that Diff-In outperforms previous methods in data-centric tasks like data cleaning, data deletion, and coreset selection, particularly excelling in large-scale vision-language pretraining tasks.

strengths:
- Innovative Approach: Diff-In offers a fresh perspective by focusing on the temporal differences in influence, which significantly improves accuracy without relying on model convexity. Moreover, Diff-In achieves second-order estimation accuracy with computational complexity similar to first-order methods, combining high accuracy with efficiency.
- Scalability: The method is computationally efficient and scalable to large datasets, making it suitable for modern machine learning applications. 
- Comprehensive Evaluation: The paper presents extensive experiments on various tasks, demonstrating Diff-In’s superior performance over existing methods across several benchmarks.

weaknesses:
- Polynomial growth of estimation error: The theoretical upper limit of the Diff-In estimation error grows polynomially with the number of training steps. This growth may still limit the scalability of the method in longer training scenarios. Exploring the actual trade-off between training steps T and error can enhance the applicability of the method.
- Matching between data quality and model capabilities: Using influence scores directly for data management does not seem to take into account the matching of data quality and model capabilities. For example, when performing core set selection, can only considering the influence score alone really select a high-quality data subset or a subset that is most helpful for downstream tasks?

questions:
None
</content>
</thread_object>

</thread>
<thread>
creation date:
1730578588928

thread_type:
official_review

<thread_object>
creator: reviewer_gkrm

<content>
summary:
This paper introduces Diff-In, a novel approach for estimating the influence of training samples across multiple learning steps. The core innovation of Diff-In lies in approximating the second-order Hessian-gradient product using only first-order computations. This approach enables Diff-In to achieve the high accuracy typical of second-order methods while maintaining the computational efficiency of first-order techniques.  Theoretical analysis and extensive experiments support Diff-In's effectiveness.

strengths:
- The paper is well-written and clearly structured, making the methodology easy to follow.
- The formulation is intuitive, and the theoretical analysis appears generally sound.
- Experimental results show Diff-In's effectiveness.

weaknesses:
- Diff-In closely follows TraceIn’s approach of accumulating influence over successive training steps. The main technical advancement appears to be an extension of TraceIn’s formulation (Eq. 3) to Eq. 5, limiting its novelty.
- The baseline choices are somewhat outdated, and the authors should include comparisons with more recent state-of-the-art methods, such as [1-2].
- Additionally, speed comparisons with these newer approaches are missing, which would provide a more comprehensive evaluation.

[1] Studying Large Language Model Generalization with Influence Functions

[2] Trak: Attributing Model Behavior at Scale

questions:
- The authors evaluate Diff-In through downstream applications but do not consider counterfactual-type metrics, such as the Linear Data Modeling Score (LDS) introduced in [2]. Would such metrics provide further insight into Diff-In's performance?
- While Figure 3 demonstrates that Diff-In incurs minimal computational overhead compared to TracIn, this may be limited to smaller models. Could the authors provide similar speed comparisons for large-scale models?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730675076846

thread_type:
official_review

<thread_object>
creator: reviewer_7tcf

<content>
summary:
The paper proposes a new formulation for influence estimation by accumulating differences in influence computation over iterative training timesteps, using second order approximations for the difference terms. The authors also conduct experiments in 3 task settings (data cleaning, data deletion, and coreset selection) and report performance alongside other influence computation methods and baselines.

strengths:
- The approach to estimate influence by a second order approximation of the finite difference terms is novel.
- The results showcase that Diff-In can improve performance compared to the other methods considered in the paper.

weaknesses:
Overall, I like the direction of the work, but find that it possesses certain issues, such as the (random) selection of checkpoints, missing experimental analysis and comparisons with other relevant influence methods, that would allow me to recommend acceptance. I am happy to engage more on the points listed below:

1. **Selecting Checkpoints (i.e. choosing $m$)**: I find the (hyperparameter) step of selecting checkpoints to be one of the major drawbacks with the approach as this is implicitly assumed by the method. While the authors conduct experiments on CIFAR-10 and ResNet-18 in Section 5.4 (and in Figure 2 on sampling strategies), these recommendations cannot generalize to new datasets and ideally this step will need to be carried out prior to utilizing Diff-In. That is, the appropriate value of $m$ might be different for other datasets and models, and it essentially becomes a hyperparameter in need of optimization. This step can be prohibitively expensive to undertake for models with a large number of parameters (e.g. LLMs). Furthermore, the authors recommend using random sampling to select the relevant set of checkpoints $\mathcal{T}_m$ which introduces another potential issue. It is possible, especially with small $m$ (i.e. $m=5$) that all the checkpoints chosen can lead to inaccurate estimation. That is, for the same setting of $m=5$, a practitioner utilizing Diff-In could obtain very different results, and it is not clear to me how this randomness in performance can be mitigated. Ideally, ablations on other datasets and models need to be undertaken to showcase if indeed the value of $m$ is general across datasets/models, which seems unlikely. 
2. **Missing Experimental Analysis**: First, I find that the paper is lacking more extensive comparison with other relevant influence based approaches. To truly assess the benefits of Diff-In, the authors should compare with recent influence approaches designed for larger models (such as EK-FAC [1], TRAK [2], and/or Arnoldi iteration [3]) and better Hessian-free methods (for instance, IP [4] and outlier gradient influence [5] seem to be very relevant for the data cleaning task). I think it is especially important to consider methods that circumvent the convexity assumption as we are dealing with larger models-- for e.g. EK-FAC estimates PBRF instead of LOO by using the Gauss-Newton Hessian instead of the standard Hessian. Second, I believe that for the data cleaning experiments of Section 5.1 the authors should consider standard influence estimation alongside self-influence as in prior work [5,6]. What are the results when the influence is computed on a clean validation set? Is Diff-In still the top performer? Third, since the paper claims that Diff-In remains scalable across larger models, I believe it is necessary to have more comprehensive analysis of running time especially with larger models and other methods. Specifically, running time analysis should be conducted on other datasets/models (preferably larger models) where both performance and running time should be provided for comparison. I also feel that the time taken to select the ideal number of checkpoints $m$ (if not fixed as 5) should be factored in as well. 
3. **Data Deletion and Machine Unlearning**: The data deletion setting seems to me to be conceptually equivalent to undertaking machine unlearning [7] and as the unlearning community has studied this problem extensively, it would be useful to utilize some recent and popular approaches (refer to [7]) for fair comparison (and not just 2 influence approaches). I would also suggest that the authors reframe this subsection and task to reflect that it is conceptually just unlearning (or otherwise list out the key differences). Data deletion in past work [5,6] has usually allowed one model retraining, and so that readers are not confused I think this should be made clear both in name and through better descriptions by referring to it as unlearning.
4. **Adding to Related Works**: Despite a comprehensive related works in the appendix, I think there are a number of papers that should also be discussed that are currently missing. Alongside a few of the papers mentioned above (for experimental comparison), it would also be beneficial to include descriptions on methods such as Datamodels [8], LoGra [9], tree estimation [10], HyDRA [11], data reweighing [12], among other relevant work in this space [13,14].
5. **Typos**: There are some typos in the paper that can be revised. For instance on line 84 (page 2), "TraceIn" -> "TracIn", and the section heading for Section 3 should read "Appromati" -> "Approximation". There are also repeated references: for instance, the paper "On second-order group influence functions for black-box predictions" by Basu et al appears twice in the bibliography.

**References**:
1. https://arxiv.org/pdf/2308.03296
2. https://arxiv.org/pdf/2303.14186
3. https://arxiv.org/pdf/2112.03052
4. https://arxiv.org/pdf/2405.17490
5. https://arxiv.org/pdf/2405.03869
6. https://arxiv.org/pdf/2310.00902
7. https://arxiv.org/pdf/2209.02299v6
8. https://arxiv.org/pdf/2202.00622
9. https://arxiv.org/pdf/2405.13954
10. https://openreview.net/pdf?id=HE9eUQlAvo
11. https://arxiv.org/pdf/2102.02515
12. https://proceedings.mlr.press/v162/li22p/li22p.pdf
13. https://arxiv.org/pdf/2409.17357
14. https://openaccess.thecvf.com/content/ICCV2021/papers/Liu_Influence_Selection_for_Active_Learning_ICCV_2021_paper.pdf

questions:
Each of the weaknesses listed above can be considered as a question.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730691586949

thread_type:
official_review

<thread_object>
creator: reviewer_yitw

<content>
summary:
This paper proposes Diff-In to estimate the data influence by accumulating differences between consecutive training steps. Diff-In approximates data influence as temporal differences with second-order methods. However, its computational cost is comparable with a first-order method.

I am not an expert in data influence. I feel my assessment of the paper's novelty may not be accurate. However, I acknowledge the theoretical and empirical results presented in the paper, and think that this is a solid paper.

strengths:
1. Novel Theoretical Framework: Provides rigorous mathematical formulation with error bounds for influence estimation without requiring model convexity.

2. Computational Efficiency: Achieves complexity comparable to first-order methods despite using second-order approximations through efficient Hessian-gradient product calculations.

3. Strong Empirical Results: Demonstrates consistent superior performance across data cleaning (9% improvement), data deletion (2% improvement), and coreset selection tasks on multiple datasets.

weaknesses:
1. Checkpoint Dependency: Implementation relies heavily on saved checkpoints during training, with unclear guidelines on optimal checkpoint selection.

2. Limited Generalizability: Currently focused on sample-level influence, lacking broader application to model hyperparameters.

3. Theoretical Assumptions: Analysis assumes Lipschitz continuous gradients and bounded gradient norms, with limited discussion of assumption violations.

questions:
Please refer to the weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732389549462

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response to ACs and Reviewers

comment:
Dear Reviewers and ACs:

We sincerely appreciate your constructive comments and insightful reviews, which have significantly contributed to enhancing our work. We have thoroughly considered all your suggestions and made substantial revisions to our previous draft, with the main changes highlighted in blue. 

Specifically, we have made the following changes:

    1. Fixed typos (main paper). 

    2. Added new references [1-13] in the related work section (appendix, Sec.C). 

    3. Added clarification of Data deletion and new baseline [14, 15] (main paper). 

    4. Added speed and performance comparison with SOTA methods on experiments for Llama-3-8B on OpenMathInstruct (appendix, Sec.D.4.1 and Table 11). 

    5. Added further ablation study on the choice of the number of selected checkpoints (appendix, Sec.D.4.2 and Table.11 and Table 13). 

    6. Added further performance comparison with IP and OGI on the cleaning experiments for GSM8K  (appendix, Sec.D.4.1 and Table.12). 

    7. Added guidelines for checkpoint selection (appendix, Sec.D.4.3). 

    8. Added experiments and discussion about the growth of the bound (appendix, Sec.D.5.1). 

    9. Added discussion about the assumption of the bound (appendix, Sec.D.5.2). 

    10. Moved the discussion of limitations to the appendix.  

**Reference:** 

    [1]. Studying Large Language Model Generalization with Influence Functions. Arxiv 2308.03296. 

    [2]. TRAK: Attributing Model Behavior at Scale. ICML 2023. 

    [3]. Scaling Up Influence Functions. AAAI 2022. 

    [4]. Revisit, Extend, and Enhance Hessian-Free Influence Functions. Arxiv 2405.17490

    [5]. Outlier Gradient Analysis: Efficiently Improving Deep Learning Model Performance via Hessian-Free Influence Functions. Arxiv 2405.03869. 

    [6]. DataInf: Efficiently Estimating Data Influence in LoRA-tuned LLMs and Diffusion Models. ICLR 2024.

    [7]. A Survey of Machine Unlearning. Arxiv 2209.02299.

    [8]. Datamodels: Predicting Predictions from Training Data. ICML 2022. 

    [9]. What is Your Data Worth to GPT? LLM-Scale Data Valuation with Influence Functions. ArXiv 2405.13954

    [10]. "What Data Benefits My Classifier?" Enhancing Model Performance and Interpretability through Influence-Based Data Selection. ICLR 2024.

    [11]. HYDRA: Hypergradient Data Relevance Analysis for Interpreting Deep Neural Networks. AAAI 2021. 

    [12]. Achieving Fairness at No Utility Cost via Data Reweighing with Influence. ICML 2022. 

    [13]. Revisiting inverse Hessian vector products for calculating influence functions. Arxiv 2409.17357

    [14]. Efficiently Erasing Samples from Trained Machine Learning Models. NeurIPS 2021 Workshop.

    [15]. Machine Unlearning Method Based On Projection Residual. DSSA 2022.

Thank you very much again!

Best regards,
Authors of Paper1257
</content>
</thread_object>

</thread>


Metareview:
metareview:
I have read all the materials of this paper including the manuscript, appendix, comments, and response. Based on collected information from all reviewers and my personal judgment, I can make the recommendation on this paper, reject. No objection from reviewers who participated in the internal discussion was raised against the reject recommendation.

**Research Question**

This paper considers the sample influence estimation problem. 

**Challenge Analysis**

The authors argue that the current methods suffer from the convex assumption and Hessian-free method limit its accuracy. 

**Philosophy**

The authors aim to present the sample influence as the cumulative sum between successive training steps, without replying on convexity assumption. Note that TracIn has a similar philosophy (See Eq.(52) in [1]) and this is not a weakness from my eyes. 

**Solution**

The authors propose Diff-In, a second-order method for the cumulative sum between successive training steps. To reduce the computational cost, the authors estimate the product of Hessian and gradient using finite differences of first-order gradients.  I believe such cumulation can alleviate the convexity assumption, however, I do not see any novelty in computational saving, where the authors employ mature techniques. Checkpoints are well studies in this paper, especially when few checkpoints are selected, it is uncertain whether the claimed unrelaxing assumption holds.

**Theoretical Analysis**

One reviewer pointed out that the theoretical upper limit of the Diff-In estimation error grows polynomially with the number of training steps. Respectively and personally, I do not think this theorem is very helpful in practice, or brings in computational saving, or sheds any insights in parameter selection. Not every paper needs this part. 

**Experiments**

I have big concerns on this part.

1.	The experiment setup needs more details. The current version including appendix does have the parameters used in the proposed method. For example, the gradient is the complete one or just the last layer.

2.	The competitive methods in Table 2 are not consistent with Table 1. At least, influence-function based methods should be added in Table 2. 

3.	The datasets used in different tasks are also different. Why?  

4.	I have concerns about the running time in Figure 3(b). It seems that Diff-In has similar execution time with TracIn. It seems that calculating the batch Hessian does not take much time. Why? 

**Other issues**

1.	Figure 1 plays a good motivation on the inaccuracy of existing influence function-based methods. However, the results are questionable. (i) Since the performance of deep models is affected by random seeds, the results are not deterministic even with the whole training set. Moreover, removing a single training sample may not have a significant impact, especially when considering the inherent randomness in the training process. Based on my personal experience on using ResNet on CIFAR-10 and comparing performance with the complete training set versus with one sample removed, after running these experiments multiple times, the average performance between the two settings did not show statistical significance. (ii) The definition of “30 most influential data points” is unclear. The most influential is based on which algorithm? If it is based on the proposed method, the results might be biased. 

[1] Training Data Influence Analysis and Estimation: A Survey.