A Versatile Influence Function for Data Attribution with Non-Decomposable Loss

We thank the reviewer for the insightful comments and suggestions. We address your concerns point-to-point below.

Minor points and Lemma 2

We appreciate the careful and constructive feedback by the reviewer. We acknowledge that we missed some constants in Lemma 1 and Lemma 2 in the original submission, and the notations might be misleading due to heavy overloading.

To address these concerns, We have largely rewritten Section 3.4. We have also systematically revised our notations throughout the paper to avoid notation overloading.

Lemma 1: We have corrected the missing constant n. This lemma is now labeled as Lemma 3.1.

Lemma 2: We have included Lemma 2 as part of the new Theorem 3.1. The proof of which is provided in Appendix A.3. A key step in this proof is to utilize the fact that $\sum_{j=1}^n \nabla_{\theta} l(\hat{\theta}, z_j) = 0$, which implies that $\sum_{j=1, j\neq i}^n \nabla_{\theta} l(\hat{\theta}, z_j) = -\nabla_{\theta} l(\hat{\theta}, z_i)$.

The connection between $\mathcal{L}(\theta, P)$ and $\mathcal{L}(\theta, 1)$: We have provided a formal construction to connect these two loss definitions in the new Proposition 3.1. Specifically, for an empirical distribution on a (subset) of the n data points, we map the distribution to its support set, which corresponds to a binary vector based on whether each data point is present in this support set. The connection between the distribution and the binary vector is done through this mapping.

Efficient approximation of Hessian inverse

We agree that mitigating the computational cost of Hessian inverse is critical for practical applications. To address this concern, we have explored the application of efficient inverse Hessian approximation methods to VIF, including Conjugate Gradient (CG) and LiSSA employed by Koh and Liang (2017) [1]. We also experimented them on the Cox regression model.

The table below shows the Pearson correlation coefficients of different methods for Cox regression on the METABRIC dataset. We experimented with both linear and neural-network-based Cox regression. The efficient approximation methods, VIF (CG) and VIF (LiSSA) achieve similar performance as both the original VIF (Explicit) that explicitly inverts the Hessian and the Brute-Force LOO. The correlation coefficients of all methods on the neural network model are lower than those on the linear model due to the randomness inherent in the model training.

We further report the runtime of different methods on neural network models with varying model sizes. VIF (CG) and VIF (LiSSA) are not only faster than VIF (Explicit), especially as the model size grows, but also much more memory efficient. VIF (Explicit) runs out of memory quickly as the model size grows, while VIF (CG) and VIF (LiSSA) can be scaled to much larger models.

These results are also added to a new Appendix C.

Technical details of VIF (LiSSA): We note that LiSSA is originally designed for decomposable losses in the form $\sum_{i=1}^n \ell_i(\theta)$ and it accelerates the inverse Hessian vector product calculation by sampling the Hessians of individual loss terms, $\nabla_{\theta}^2\ell_i(\theta)$. The adaptation of LiSSA to VIF depends on the specific form of the loss function. In many non-decomposable losses (e.g., the all three examples in this paper), the total loss can still be written as the summation of simpler loss terms, even though they are not decomposable to individual data points. In such cases, LiSSA can still be applied to efficiently estimate the inverse Hessian vector product by sampling the simpler loss terms.

Applicability of other techniques such as Kwon et al. (2024): For non-decomposable losses that can be written as a summation of simpler (although not decomposable to data point level) loss terms, the Hessian matrix may be similarly approximated by the sum of outer products of these simpler loss terms, enabling tricks such as the one utilized by Kwon et al. (2024) to efficiently approximate the Hessian inverse.

[1] Koh, P. W., & Liang, P. (2017, July). Understanding black-box predictions via influence functions. In International conference on machine learning (pp. 1885-1894). PMLR.

Thank you for your response. My concerns have been addressed, so I will raise my score to 5. However, I still have some reservations regarding the contributions. While I acknowledge that the novelty of this work lies in adapting the influence function for non-decomposable losses, I feel that the contributions are somewhat limited, as I do not find anything particularly insightful for further studies. Precisely, in my view, Theorem 3.1, which focuses on decomposable losses, seems more like a paraphrase of the influence function. For decomposable losses, their linearity in $\epsilon$ makes it unsurprising that the influence function is equivalent to using finite differences.

I also noticed that the authors have added Theorem 3.2 to bound the proposed versatile influence function and influence function for cox regression, but I chose not to check the proof of it as I, personally, do not think it is a particularly interesting result for future work. So, I will drop my confidence to 3.

We thank the reviewer for the insightful comments and suggestions. We address your concerns point-to-point below.

Weakness 1: Justification of the finite difference

We thank the reviewer for the valuable question. We have largely rewritten Section 3.4 to provide clearer motivation for the finite difference.

In the updated draft, we have first formally defined the finite-difference influence function in Definition 3.2. Then we clearly stated the motivation for this finite-difference approximation in Theorem 3.1, where we demonstrated that, under the M-estimators, the statistical influence function involving a limit in Eq (7) exactly equals to a finite-difference influence function with a certain choice of $\varepsilon=-\frac{1}{n-1}$. We also showed that the finite difference approximation with $\varepsilon=1$ can be viewed as a “reparameterization” of the original $\varepsilon=-\frac{1}{n-1}$ finite-difference influence function. Specifically, the change from $\varepsilon=-\frac{1}{n-1}$ to $\varepsilon=1$ is a result of changing the perturbation direction $Q$ from $\delta_{z_i}$ to $\mathbb{Q}_{n-1}$. While $\varepsilon=1$ may appear large, $\mathbb{Q}_{n-1}$ is closer to $\mathbb{P}_n$ than $\delta_{z_i}, therefore the approximation is still good.

In short, the selection of $\varepsilon=1$ is not an arbitrary choice–it comes from a careful choice of the perturbation direction $Q$, with a theoretical observation under the M-estimators. We refer the reviewer to Theorem 3.1 for more details, which should better clarify the question of why this finite-difference approximation may approximate the original limit well.

Weakness 2: Approximation error on Cox regression

In our updated draft, we have further provided a formal characterization of the approximation error of VIF under the Cox regression model in Theorem 3.2, where we showed that the approximation error is in the order of $O(1/n)$, which vanishes for large training data size $n$.

Weakness 3: Limitations

We thank the reviewer for the suggestion. We have now included a limitation discussion at the end of the paper.

The convexity assumption is the main limitation in the formal derivation of the VIF. However, it is possible to adapt computational tricks from existing IF-based methods for decomposable losses to VIF. For example, we have included a new Appendix C exploring the application of Conjugate Gradient and LiSSA employed by Koh and Liang (2017) [1] to VIF. We have also successfully implemented them on neural-network-based Cox regression models. Please see Appendix C for more details about this.

[1] Koh, P. W., & Liang, P. (2017, July). Understanding black-box predictions via influence functions. In International conference on machine learning (pp. 1885-1894). PMLR.

Question 1: Heatmap

We newly added Appendix D to visualize the heatmap of influence estimated by VIF and LOO for two pairs of nodes. VIF could identify the top and bottom influential nodes accurately, while the estimation of node influence in the middle more noisy. One caveat of these heatmap plots is that there is a misalignment between the color maps for VIF and LOO. This reflects the fact that, while VIF is effective at having a decent correlation with LOO, the absolute values tend to be misaligned.

We thank the reviewer for the insightful comments and suggestions. We address your concerns point-to-point below.

Weakness 1: Empirical baselines such as retraining-based methods

We acknowledge that retraining-based methods can indeed be applied for non-decomposable losses. However, such methods are usually orders of magnitude slower than influence function style methods. In fact, for Data Shapley, there is a known lower bound O(n log n) on the number of model retraining required for a given approximation error [1]. Therefore it will be even slower than brute-force LOO for large n.

Moreover, in this study, we have used LOO as the ground truth for evaluation. Retraining-based methods such as Data Shapley are NOT designed to optimize for LOO, so they are UNLIKLEY to perform very well according to our evaluation metric, which is based on LOO correlation. While it is debatable whether LOO is always desirable as the data attribution target, arguably this is the most widely used criterion in the literature. Approximating data attribution targets other than LOO (such as Shapley value) is beyond the scope of this paper.

As a result, we consider comparisons with retraining-based methods unnecessary. Nevertheless, we carried out one additional experiment with Cox regression on the METABRIC dataset using Data Banzhaf [2], a retraining-based method close to Data Shapley (we have initially tried Data Shapley but our implementation failed to converge and we are still investigating the reason). This method took 20 min (LOO: 24 min, VIF: 2.43 sec), while achieving an LOO correlation of 0.657 (LOO: 0.997, VIF: 0.997).

Another empirical baseline we experimented with is a naive application of the conventional influence function on the Cox model. In this case, we pretend that the summation in Eq (4) is a decomposable loss, ignoring the impact of the interaction among data points in the loss. This naive baseline achieves an LOO correlation of 0.537 (LOO: 0.997, VIF: 0.997) on the METABRIC dataset. This result highlights the need for a principled design to approximate LOO on non-decomposable loss.

[1] Wang, J. T., & Jia, R. (2023). A Note on" Towards Efficient Data Valuation Based on the Shapley Value''. arXiv preprint arXiv:2302.11431.

[2] Wang, J. T., & Jia, R. (2023, April). Data banzhaf: A robust data valuation framework for machine learning. In International Conference on Artificial Intelligence and Statistics (pp. 6388-6421). PMLR.

Weakness 2 and Question 1: Theoretical discussions

We appreciate the reviewer’s feedback. To address the reviewer’s concern, we have largely rewritten Section 3.4 and 3.5 to make our statements more rigorous. Specifically to one point mentioned by the reviewer, we have provided a formal characterization of the approximation error of VIF under the Cox regression model in Theorem 3.2, where we showed that the approximation error is in the order of $O(1/n)$, which vanishes for large training data size $n$.

Regarding computational efficiency, we have explored the application of efficient inverse Hessian approximation methods to VIF, including Conjugate Gradient (CG) and LiSSA employed by Koh and Liang (2017) [1]. We also experimented them on the Cox regression model.

The table below shows the Pearson correlation coefficients of different methods for Cox regression on the METABRIC dataset. We experimented with both linear and neural-network-based Cox regression. The efficient approximation methods, VIF (CG) and VIF (LiSSA) achieve similar performance as both the original VIF (Explicit) that explicitly inverts the Hessian and the Brute-Force LOO. The correlation coefficients of all methods on the neural network model are lower than those on the linear model due to the randomness inherent in the model training.

We further report the runtime of different methods on neural network models with varying model sizes. VIF (CG) and VIF (LiSSA) are not only faster than VIF (Explicit), especially as the model size grows, but also much more memory efficient. VIF (Explicit) runs out of memory quickly as the model size grows, while VIF (CG) and VIF (LiSSA) can be scaled to much larger models.

These results are also added to a new Appendix C.

[1] Koh, P. W., & Liang, P. (2017, July). Understanding black-box predictions via influence functions. In International conference on machine learning (pp. 1885-1894). PMLR

We thank the reviewer for the insightful comments and suggestions. We address your concerns point-to-point below.

Weakness 1: Notations of P, Q, and the all one vector.

We clarify that we are not letting P be 1. There are two definitions of the loss function in our derivation, $\mathcal{L}(\theta, P)$ and $\mathcal{L}(\theta, b)$. The former depends on a probability measure, while the latter depends on a binary vector. In our original submission, we overloaded the notation $\mathcal{L}$ for the two definitions for convenience (we had a small footnote on page 3 in our original submission about this overloading). We also made some connection between the two definitions of the loss, and this may have led to the impression that we let P be 1 somewhere.

After reviewing our writing, we acknowledge that overloading the notations in our original submission may indeed lead to confusion. To address the reviewer’s concern, we have thoroughly revised our notations in the updated draft, avoiding all notation overloading.

In our updated draft, the loss function depending on the probability measure is now written as $\tilde{\mathcal{L}}$. Moreover, we have made it clearer and more rigorous about how we connect the two definitions of loss function in the new Proposition 3.1. Specifically, for an empirical distribution on a (subset) of the n data points, we map the distribution to its support set, which corresponds to a binary vector based on whether each data point is present in this support set. The connection between the distribution and the binary vector is done through this mapping.

Weakness 2: The motivation and theoretical guarantee of the finite difference

We thank the reviewer for this valuable question. We have largely rewritten Section 3.4 to provide clearer motivation for the finite difference.

In the updated draft, we have first formally defined the finite-difference influence function in Definition 3.2. Then we clearly stated the motivation for this finite-difference approximation in Theorem 3.1, where we demonstrated that, under the M-estimators, the statistical influence function involving a limit in Eq (7) exactly equals to a finite-difference influence function with a certain choice of $\varepsilon=-\frac{1}{n-1}$. We also showed that the finite difference approximation with $\varepsilon=1$ can be viewed as a “reparameterization” of the original $\varepsilon=-\frac{1}{n-1}$ finite-difference influence function. Specifically, the change from $\varepsilon=-\frac{1}{n-1}$ to $\varepsilon=1$ is a result of changing the perturbation direction $Q$ from $\delta_{z_i}$ to $\mathbb{Q}_{n-1}$. While $\varepsilon=1$ may appear large, $\mathbb{Q}_{n-1}$ is closer to $\mathbb{P}_n$ than $\delta_{z_i}, therefore the approximation is still good.

We refer the reviewer to Theorem 3.1 for more details, which should better clarify the question of why this finite-difference approximation may approximate the original limit well.

Regarding theoretical guarantees, in our original submission, we have shown that the proposed VIF falls back to the original influence function under M-estimators (decomposable losses) without any approximation error. In our updated draft, we have further provided a formal characterization of the approximation error of VIF under the Cox regression model in Theorem 3.2, where we showed that the approximation error is in the order of $O(1/n)$, which vanishes for large training data size $n$.