Most Influential Subset Selection: Challenges, Promises, and Beyond

We thank Reviewer Uyvf for taking the time to review our paper and their constructive feedback. Please find below our point-to-point response.

Remark 4.3. We note that starting from Section 3.2, we adopt the closed-form of individual influences ($A_{-{i}}$) instead of the influence estimates. The purpose is to separate the two failure modes: the errors incurred by the influence estimates (discussed in Section 3.1 and in prior works such as Basu et al., (2021)), and the non-additive structure of the group influence. Since the errors of influence estimates are not intrinsic to the greedy heuristics as well as their adaptive variants, it is only reasonable for us to use the ground-truth individual effect in order to study their fundamental properties.

Our positive result and the hypothesis in Section 4 also assume access to the ground-truth individual influence. In this context, the fragility of the influence estimates is a separate issue. The critical question is whether the adaptive greedy algorithm can effectively capture the interactions between samples and thereby solve the more general $k$-MISS problem. This is a challenging open problem, and an important first step is to formally define “cancellation” for more than two samples. We will clarify this in the revision, and leave this as future work.

Second-order group influence functions. We note that the approach adopted by Basu et al. (2020) is a simplification of the actual second-order influence function, which is part of a more general framework known as the higher-order infinitesimal jackknife [1] in the literature. The actual second-order influence function involves computing a third-order tensor, which is infeasible for deep neural networks (and much more computationally expensive than the adaptive greedy algorithm). Consequently, Basu et al. (2020) ignored the third-order derivative in their calculations, making their computational complexity roughly on the same order as the vanilla influence function and more efficient than the adaptive greedy algorithm. However, there are two main caveats: 1) The third-order term might contain rich information for large-scale neural networks and classification tasks; 2) The subset selection problem is reframed as a discrete quadratic optimization problem, and while it can be solved efficiently via relaxation and projected gradient descent, the additional step makes it challenging to obtain provable guarantees even in simple linear models.

Beyond computational efficiency, we believe these two approaches capture different types of interactions among samples. The second-order group influence function can detect clusters of samples, corresponding to the amplification effect, whereas the adaptive greedy algorithm can identify samples with cancellation effects, as demonstrated in our analysis. We believe a clever combination of these two approaches holds significant potential and leave this as a topic for future research.

Potential application scenarios. We will take ZAMinfluence [2], one of the most prominent algorithms in MISS, to discuss the broader impact of MISS.

ZAMinfluence was introduced to assess the sensitivity of applied econometric conclusions to the removal of a small fraction of samples. For example, suppose a conclusion involves determining whether a particular coefficient in a linear regression model is positive. If the sign of the coefficient flips after removing a few samples, we might be concerned as the conclusion is excessively sensitive to a small portion of the data. Conversely, if the sign remains the same regardless of which size-$k$ subset is removed, we can be more confident in the robustness of the conclusion.

ZAMinfluence has been applied to many disciplines, including but not limited to applied econometrics, economics, and social sciences (see Appendix A for a detailed summary). For instance, the following sentence is quoted from [3], a paper in economics: “Therefore, we use an approach proposed by Broderick et al. (2020) to test if sign and significance of our estimates could conceivably be overturned by removing small fractions of the data with the potentially largest influence on size and sign of estimated effects.” In experimental studies, the process of collecting samples is often not fully random, and the conclusions drawn from these samples might not be robust. In this case, it is necessary to apply MISS to assess the robustness of conclusions and identify potential sources of sampling bias.

In summary, MISS is framed as a machine learning problem, but it shines through its applications that extend far beyond machine learning, enhancing the reliability of analytical conclusions across a wide range of scientific domains.

References

[1] Giordano, Ryan, Michael I. Jordan, and Tamara Broderick. "A higher-order swiss army infinitesimal jackknife." arXiv preprint arXiv:1907.12116 (2019).

[2] Broderick, Tamara, Ryan Giordano, and Rachael Meager. "An automatic finite-sample robustness metric: when can dropping a little data make a big difference?." arXiv preprint arXiv:2011.14999 (2020).

[3] Finger, Robert, and Niklas Möhring. "The adoption of pesticide-free wheat production and farmers' perceptions of its environmental and health effects." Ecological Economics 198 (2022): 107463.

We thank Reviewer 3kwV for taking the time to review our paper. Before addressing the reviewer’s comments, we would like to clarify some misconceptions.

• Thesis and contributions. Our work falls under the category of learning theory, and our thesis is to advance the theoretical understanding of MISS – an important research topic in the field of data attribution. We do not claim any algorithmic contributions; instead, our aim is to build the foundation for future algorithmic advancements through a comprehensive analysis of the pros and cons of the common practices in MISS. The experiments are designed to corroborate and extend our theoretical findings, instead of showcasing that a particular algorithm has beaten the state-of-the-art.
• Related work. As stated in our general response, data selection and MISS are completely different research topics. They differ in objectives, applications and techniques. As for the relationship between MISS and Data Shapley, 1) influence functions and Data Shapley define the influence/contribution of individual samples in different ways; 2) MISS extends influence functions to modeling the influence of a set of samples. It is clear that MISS and Data Shapley are not comparable.

Below is our point-to-point response:

Efficiency of the adaptive greedy algorithm.

• To be clear, we didn’t propose the adaptive greedy algorithm and certainly were not claiming that it is an all-round solution. One of the main findings of the paper is that the adaptive greedy algorithm trades computational efficiency for performance gain, and the experiments are designed to corroborate and extend this finding.
• Although efficiency is not on our priority list, we have optimized our processes to the best of our available resources, which is detailed in Appendix D.4.
• We strongly believe that the 28-hour experimentation is part of the scientific discovery process and it would be unfair to dismiss it as wasteful.

Non-linear models. Influence functions have been applied to (deep) neural networks ever since the seminar work by Koh and Liang [1]. While our theoretical results are restricted to linear models, the experimental results on MLP clearly demonstrate that our findings can generalize to non-linear models.

Practical relevance. As stated above, we did not claim any algorithmic contributions, and our thesis is to advance the theoretical understanding of MISS. For use cases of these algorithms, we refer the reviewer to [2], which is the original paper that proposed ZAMinfluence. We have also summarized a few points in our response to Reviewer Uyvf under “Potential application scenarios”.

Theoretical understanding. We do not take such an unjustified claim since our entire work is dedicated to the theoretical understanding of MISS.

Contextualization. Please refer to our general response.

Established baseline and influential prior work. With due respect, these works are irrelevant to our study. The reasons are detailed in the general response and our clarification on the misconceptions.

Comparison with mentioned “SOTAs”. This is incompatible with the thesis of our work, plus they are not comparable. Please refer to our clarification on the misconceptions.

Robustness to hyperparameters. We clarify that apart from the randomness of training in the MLP experiments, there is no hyperparameter that needs to be tuned in both the vanilla and adaptive greedy algorithm. For the randomness in training MLPs, please refer to “Randomness in experiments” and our general response.

Implication on sensitive data. We believe that the implications of this very specific scenario is beyond the scope of a paper on learning theory that focuses on the fundamentals of the general MISS problem.

Experiments.

• Dataset.

  • UCI and MNIST are standard datasets in the machine learning community, and MNIST is widely used in the study of influence functions such as [1]. If the reviewer has any “representative” datasets in mind, can the reviewer please share with us?
  • We consider three different datasets in the experiment section, which we believe is sufficient for a paper on learning theory. This is further supported by Reviewer Uyvf: “The choice of datasets and experiments to run (synthetic data, MNIST on MLPs) fits the scope of the paper”.

• Size of the test set. We want to emphasize that the purpose of the test samples in our setting is very different from their usage in standard machine learning. Here, the test samples serve as the target function, and the size could be arbitrary. In fact, we focus on a single test sample in Sections 3 and 4 — in this case, MISS measures the alteration of model behavior on this particular sample of interest.

• Randomness in experiments. For MLP training, we have conducted additional experiments and we show that the results are consistent and robust across different random seeds. Please refer to the general response for details.

• Robustness checks such as sensitivity analysis and cross-validation. For linear regression and logistic regression, there is no need for sensitivity analysis or cross-validation as there’s no hyperparameter tuning. For MLP, we added details of cross-validation in Table 1 of the attached PDF in the general response. We also included them in Appendix D.3 in the draft.

References

[1] Koh, Pang Wei, and Percy Liang. "Understanding black-box predictions via influence functions." International conference on machine learning. PMLR, 2017.

[2] Broderick, Tamara, Ryan Giordano, and Rachael Meager. "An automatic finite-sample robustness metric: when can dropping a little data make a big difference?." arXiv preprint arXiv:2011.14999 (2020).

We thank Reviewer 2zFQ for taking the time to review our paper and their constructive feedback. Please find below our point-to-point response.

Comparison to [1,2].

• We believe the main and the most fundamental difference between our work and [1] is the topics of study — our work focuses on MISS, whereas [1] concerns data selection. As explained in the general response, these two terms differ in objectives, applications, and techniques (while influence functions are used in both our work and [1], they are used for sub-sampling in [1], which is not a part of our work). Consequently, the conclusions in these works are not transferable (i.e., the sub-optimality of IF in data selection does not necessarily imply its failure in MISS).
• Regarding [2], the underestimation of IF is only a by-product of our analysis in Section 3.1. In fact, we believe the main contribution of our work lies in Section 3.2, where we provide a comprehensive analysis of the non-additive structure of collective influence. The results in Section 3.1 are not particularly surprising given that influence functions are known to be fragile in prior works; we included it for the sake of completeness.
• Finally, we have provided a detailed discussion of the theoretical research in MISS in Appendix A.

Re-training. We conducted an additional experiment of full re-training following the reviewer’s suggestion. The results are demonstrated in Fig. 1 (right) of the attached PDF in the general response. The main takeaway is that switching from warm start to full re-training does not change our conclusion: the adaptive greedy algorithm consistently outperforms the vanilla one. As a side note, for the winning rate metric, the trend of full re-training does not fully match the one with warm start in Fig 4 of the submission. We believe randomness may have played a significant role in this discrepancy, particularly because full re-training involves more randomness compared to starting from fixed checkpoints. We will further investigate this and include the results of multiple trials with confidence intervals in the revision.

Data selection/coreset selection. Please refer to our general response. We will make sure to clarify the differences between data selection and MISS in the revision.

Examples in the original feature space (Figs 1-3). The samples in Figures 1 to 3 are 2d synthetic data that we crafted for demonstration purposes; they do not correspond to examples (e.g., images) in high-dimensional real-world datasets. The coordinates are generated from Eq. (7) plus some Gaussian noise. We hope this clarifies the reviewer’s question.

References

[1] Kolossov, Germain, Andrea Montanari, and Pulkit Tandon. "Towards a statistical theory of data selection under weak supervision." The Twelfth International Conference on Learning Representations.

[2] Koh, Pang Wei W., et al. "On the accuracy of influence functions for measuring group effects." Advances in neural information processing systems 32 (2019).

We thank Reviewer btdJ for taking the time to review our paper and their constructive feedback. Please find below our point-to-point response.

Non-invertible $N$. We assume $N$ to be invertible since influence functions rely on the uniqueness of the optimal solution. When this is violated, we can use $L_2$ regularization, which is a standard practice when applying influence functions to deep learning. Our analysis naturally extends to this case. More broadly, we have extended our analysis from OLS to weighted least squares and kernels. However, since these extensions did not provide additional insights, we have opted to present the analysis in its current form. We will ensure these potential generalizations are discussed in the revision.

Extension to $k$-MISS.

• We believe that our analysis being tailored to the adaptive greedy algorithm is not a weakness, as the purpose of Section 4 is to demonstrate that adaptivity helps in a non-trivial way.
• We acknowledge that under the cancellation setup, our current results are restricted to 2-MISS. We highlight a few challenges: 1) Conceptually, unlike the amplification setup, where it is straightforward to accommodate an arbitrary number of samples, it is not immediately clear how to define “cancellation” for more than two samples. 2) Technically, proving the success of MISS is extremely difficult, as it requires considering all possible subsets, whose size grows exponentially with $k$. In fact, even proving the results for 2-MISS turns out to be highly non-trivial. We will clarify these challenges in the revision and leave them as future research.

Mismatch between title and content. We fully understand that the reviewer was expecting a broader coverage of algorithms and a more general analysis beyond linear models. Nevertheless,

• MISS is a relatively new and underdeveloped field. To the best of our knowledge, all algorithms except the second-order group influence function (which we also discussed in Section 6), are based on influence-based greedy heuristics. In this regard, our work pioneers in MISS by systematically studying this dominant strategy.
• While our theoretical results are limited to linear models and the cancellation setup only concerns 2-MISS, we have conducted experiments on non-linear models and general $k$’s to extend our theoretical analysis.

Therefore, we believe the title is suitable for our work. However, if the reviewer has more concrete suggestions for the title, we would be very open to discussions.

Target functions.

• The numbers in Figure 1 are not the actual influences; they are the influence estimates computed by the influence function. We didn’t optimize these numbers hard as it is clear from the proof of Theorem 3.1 that the ratio between them can be arbitrary.
• Regardless of the target function, the influence function underestimates the change in parameters by $1/(1-h_{ii})$ in linear regression. This is the main reason why samples with high leverage scores could incur a large effect when removed. Based on this fact, it is not hard to generalize our results to other target functions.
• Take the sign of prediction as an example, we can slightly modify Figure 1 (by shifting the samples along the y-axis), so that the predictions of the original OLS and OLS without sample 8 are negative, but the prediction of OLS without sample 1 is positive. This means that removing sample 1 changes the sign of the prediction, but it does not have the largest influence estimate and is therefore not selected by the greedy algorithm.
• We posit that the choice of target function is a very important consideration in influence functions yet received insufficient attention from the literature. We have included a discussion in Section 6 in the hope of inspiring future research.

Procedure of correcting the influence estimate. In linear regression, it suffices to divide the influence estimate by $(1-h_{ii})$ to obtain the actual individual influence $A_{-\{i\}}$. Please refer to the paragraph under equation (9).

Comparison with ground truth influence. We concur that comparing the influences achieved by vanilla/adaptive greedy algorithms to the ground truth is an interesting question. To this end, we conducted additional experiments on a small-scale synthetic dataset.

More specifically, we focus on a binary classification task with logistic regression, and consider the target function $\phi(\theta) = p(z;\theta)$, where $z$ is the test sample and $p(z; \theta)$ is the softmax probability assigned to the correct class. The synthetic data is generated from a mixture of Gaussians: given $\sigma$, we sample $25$ training data points from $\mathcal{N}(c_i, \sigma I_2)$ for each $i\in \{0,1\}$, where $c_0 = (1, 0)$ and $c_1 = (-1, 0)$. The test sample $z$ is uniformly sampled from one of the Gaussians. We conducted the experiments for various $\sigma$’s, and for each $\sigma$, repeated the experiment 20 times using different random seeds to generate the train/test data. Finally, we report the averaged ratio of the obtained influence over the ground-truth influence.

The results are demonstrated in Fig. 2 of the attached PDF in the general response. In summary, the adaptive greedy algorithm outperforms the vanilla counterpart on all $\sigma$’s, and recovers the ground truth subset when $\sigma$ is large.

Robustness of results to randomness in training. We believe the drop around $k=50$ is due to randomness. To verify this hypothesis, we conducted two experiments targeting at different randomness in the process. We refer the reviewer to the general response for the detailed setting and the general takeaways of the experiments. Particularly, the first experiment (randomness in evaluation, Fig. 1 top left) clearly demonstrates that the drop in Fig. 4 of the submission is only due to randomness, as we have fixed the selected subset but the new figure does not exhibit the same drop.