Most Influential Subset Selection: Challenges, Promises, and Beyond
Authors: Yuzheng Hu
Pingbang Hu
Han Zhao
Jiaqi Ma
Venue: NeurIPS 2024 poster (2024)
Keywords: influential subset
influence function
data attribution
interpretability
Primary area: interpretability_and_explainability
TL;DR: We provide a comprehensive study of the common practices in the Most Influential Subset Selection (MISS) problem.

Abstract: How can we attribute the behaviors of machine learning models to their training data? While the classic influence function sheds light on the impact of individual samples, it often fails to capture the more complex and pronounced collective influence of a set of samples. To tackle this challenge, we study the Most Influential Subset Selection (MISS) problem, which aims to identify a subset of training samples with the greatest collective influence. We conduct a comprehensive analysis of the prevailing approaches in MISS, elucidating their strengths and weaknesses. Our findings reveal that influence-based greedy heuristics, a dominant class of algorithms in MISS, can provably fail even in linear regression. We delineate the failure modes, including the errors of influence function and the non-additive structure of the collective influence. Conversely, we demonstrate that an adaptive version of these heuristics which applies them iteratively, can effectively capture the interactions among samples and thus partially address the issues. Experiments on real-world datasets corroborate these theoretical findings, and further demonstrate that the merit of adaptivity can extend to more complex scenarios such as classification tasks and non-linear neural networks. We conclude our analysis by emphasizing the inherent trade-off between performance and computational efficiency, questioning the use of additive metrics such as the linear datamodeling score, and offering a range of discussions.

Most Influential Subset Selection: Challenges, Promises, and Beyond
Yuzheng Hu'
Pingbang Hu² Han Zhao Jiaqi W. Ma²
'Deaarmentt of Computer Science
Schooo of Information Sciences
University Illinois Ltbana-Champarn
fyh46,pbb hanzhao, bannzhaab hinzha..j.aaimmaaa.......... jiagima)eillimois.
Abstract
How can attribute the behaviors of machine learning models their training data? While the classic influence function sheds light on the impact of individual samples, often fails capture the more complex and pronounced collective influence of set of samples. To tackle this challenge, we study the Most Influential Subset Selection (MISS) problem, which aims to identify subset of training samples with the greatest collective influence. We conduct a comprehensive analysis of the prevailing approaches in MISS, elucidating their strengths and weaknesses. Our findings reveal that influence-based greedy heuristics, dominant class of algorithms in MISS, can provably fail even in linear regression. We delineate the failure modes, including the errors of influence function and the non-additive structure the collective influence. Conversely, we demonstrate that adaptive version of these heuristics which applies them iteratively, effectively capture the interactions among samples and thus partially address the issues. Experiments real-world datasets corroborate these theoretical findings and further demonstrate that the merit of adaptivity can extend to more complex scenarios such classification tasks and non-linear neural networks. We conclude our analysis by emphasizing the inherent trade-off between performance and computational efficiency, questioning the use of additive metrics such as the Linear Datamodeling Score, and offering a range of discussions.
Introduction
Unraveling the intricate connections between data and model predictions is critical in machine learning, particularly in high-stakes decision-making contexts such healtheare, economies, and public policy [Bracke et al., 2019, Rudin, 2019, Amarasinghe et al., 2023]. A better understanding of these connections allows tackling tasks like data cleaning [TTeso al., 2021], model debugging [Guo et al., 2021], and assessing the robustness of inferential results [Broderick et al., 2020], all key to enhancing model interpretability and fostering trust between machine learning practitioners and domain experts. Among the various methodologies, the influence function adopted by Koh and Liang [2017] stands out as a particularly effective tool, sparking extensive research into identifying influential individual samples [Barshan et al., 2020, Schioppa et al., 2022, Grosse et al., 2023].
Nevertheless, focusing solely the influence of individual samples is often insufficient. In many scenarios, it is necessary to understand how sets of samples jointly affect model predictions. These include uncovering biases associated with specific demographic groups [Chen et al., 2018), fairly allocating credits among crowdworkers [Arrieta-lbarra et al., 201 8J. and detecting trends and signals that emerge collectively within the data (Yngg et al., 2020]. Gaining such insights crucial for more comprehensive understanding of model behaviors.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In pursuit of advancing this field, in this paper, delve into the most influential subset selection (MISS) problem [Fisher et al., 2023]. MISS attempts to find a set of samples that, when removed from the training set, results in the most significant change of a pre-defined target function. In essence, measures the worst-case collective influence.
Contributions. We provide a comprehensive analysis of existing algorithms to tackle MISS, revealing their weaknesses and strengths, and discussing the challenges and important considerations for future research. To summarize our contributions:
We systematically study the failure modes of influence-based greedy heuristics, dominant class of algorithms in MISS that assign a static score to each sample and subsequently perform a greedy selection. Specifically, the error of influence function, as well as the inability incorporate the non-additive structure of the collective influence, can cause these heuristics to fail in MISS even in simple linear regression.
In contrast, demonstrate the effectiveness of the adaptive greedy algorithm that dynamically up- dates the score for each remaining sample in response to selections already made. The improvement mainly comes from its ability capture the nuanced interactions among samples.
We conduct experiments on both synthetic and real-world datasets. The experimental results not only corroborate the theoretical findings but also extend more complex settings including classification tasks and non-linear models, showcasing the consistent benefits of adaptivity.
We discuss the inherent trade-offs between performance and efficiency in MISS, and the potential drawbacks of additive metrics such Linear Datamodeling Score, among others.
Concurrent work. We acknowledge a concurrent work [Huang et al., 2024], which was posted around the same time ours. Huang al. [2024] investigate the Maximum Influence Perturbation problem [Broderick et al.. 2020], which is equivalent to MISS. Both studies analyze the additive assumption and the adaptive greedy algorithm in OLS. but they differ in the theoretical results. Notably, we formally prove the failure of LAGS in solving MISS under a specific data generation process, uncovering the phenomena of amplification and cancellation. Huang al. [2024] analyze the approximation етror of variants of LAGS by comparing the closed-form expression of the approximate algorithm and the actual effect.
2 Preliminaries
2.1 Problem statement
Consider a prediction task (e.g.. regression or classification) with an input space X C Rd and a
target space y C I. The prediction task aims to learn function f(e.-) X' + ) parameterized by E TR?. Specifically, denote {<x,, 9:) y;)]== as the training samples and ...,.)) as the loss function (e.g., squared error or cross-entropy), we aim solve the following optimization problem:
arg min
a))) 1=1
OERY
72
A key notion for analyzing the influential samples is the optimal model parameters after removing a subset training samples. Denote [n] = 21, .....,,,, ,n] and the set of indices as S C [n]. this corresponds to
1 EL((O,0)).))) TI
d_ arg min
BER
$
Note that do not adjust the normalizing constant it does affect the optimal solution to (2) Finally, denote á IR9 + R as the target function, which takes the model parameters as input and returns a quantity of interest (c.g., the prediction on a test sample or the sign of its first coefficient). We now formally define the most influential subset selection problem.
Definition 2.1 (Most Influential Subset Selection (MISS)). Given a positive integer k < n, the MoMtst Influential Subset Selection (K-MISS) problem refers to this discrete optimization problem:
Sopt,
arg max A-s, where A o(0_s) -60).
(3)

---

We refer to A-s s as the actual effect of removing S. For clarity, we refer to the actual effect as the individual effect when |S| = 1 and the group effect otherwise. Essentially, MISS aims to identify a subset with bounded size, such that its removal from the training samples will lead the maximum actual effect. It can be viewed as analogous to adversarial examples [Biggio et al., 2013, Szegedy al., 2014], in that both characterize the alteration of model behaviors in the worst case, but MISS operates on the training data space and during training time.
Unfortunately, the naive approach of enumerating all possible subsets has exponential time complexity in k rendering it computationally intractable in practice. In fact, even in the context of linear regression, variant of MISS (where the target function depends on S) known as robust regression [Andersen, 2007] is proved to be NP-hard [Price et al., 2022]. To tackle this challenge, researchers have proposed various greedy heuristics select an approximately most influential subset.
2.2 Influence-based greedy heuristics
One of the most prominent algorithms for MISS, ZAMinflunnce, was introduced by Broderick et al. [2020] and applied to assess the robustness of inferential results in earlier econometric studies [At- tanasio et al., 2015, Angelucci et al., 2015J. It builds upon the classic influence function [Koh and Liang, 2017] from robust statisties literature [Hampel, 1974, Hampel al., 2005], extending its application from individual samples to a set of samples. A similar approach has been employed by Koh et al. [2019] to estimate group effects. We defer a detailed review of the literature Section 7.
Definition 2.2 (Upweighted objective). We denote the optimal solution the upweighted objective w.r.l a set of indices S as
0_s(o) arg min RERS
1 n2
L(f(0.x)..)) +8
Σ L(f(0,2)).))
It is straightforward to the influence function of individual samples [Koh and Liang, 2017]. the influence of a set S can be characterized by the local perturbation of Ô (0) around = O. This quantity is well-defined when L strictly convex and can be computed via the Implicit Function Theorem [Krantz and Parks, 2002].
that 5 corresponds to 0, while ō = corresponds to 0-s. Similar
Definition 2.3 (Influence function of set). The inftuence of upweighting S the parameters is:
I(S)= = d0-s(o)
= -HT² Σ VoL(f((,x:)..
(5)
d6 6=0
iES
where Hg = Σ. VZL(S(d, x.), vi) is the Hessian of the loss function at Ó.
Using the chain rule and note that o-s 0-s(- the actual effect can be estimated via the first-order approximation:
1 A =
dot0 dot0_s(0))
VoO = n
VVL((((,))). iES
(6)
n d8
6=0
The key observation is that the right-hand side of Eq. (6) displays an additive structure so that the group effect can be approximated by a summation of individual influences. This naturally yields the ZAMinfluence algorithm, which involves 1) calculating v; Vo)(0) "V'L 21)); yi) for cach i [n]: 2) sorting 0 's; 3) returning the top i's with positive U4 In fact, a series of studies in MISS [Wang al., 2023, Yang et al., 2023a, Chhabra al., 2024] follow similar approach: they score individual samples using variants of influence functions, and then greedily select those with the highest positive scores. We refer to these algorithms as inftuence-based greedy heuristics.
These heuristics are powerful in two aspects. The first is their broad applicability: they can be applied to any Z-estimator of a svice-differentiane objective function [Broderick et al., 2020] to obtain an influential subset w.r.t. any differentiable target function. The second their computational efficiency: once we have computed the scores for each sample, they can be executed in linear to log-linear time complexity. However, a major drawback of these heuristies is the lack of provable guarantees. is well-known that even the influence estimates of individual samples can be fragile and erroneous,
3

---

especially in complex models like neural networks [Basu al., 2021, Bae al., 2022]. more significant concern lies in the additivity assumption implicitly adopted by these heuristics (also see Guu al. [2023] for discussions), it fails account for the interactions among samples. We critically examine these issues in Section 3.
3 Pitfalls of greedy heuristics in Most Influential Subset Selection
In this section, we delve into the influence-based greedy heuristics introduced in Section 2, providing a comprehensive study of their limitations solving MISS within the context of linear regression.
Setup and notation. In standard linear regression, each I; Rd represents vector of covariates, and stands for a real-valued label. The first coordinate of each æ; is set to to account for the intercept term. We stack the row vectors x; to form the design matrix X IR" and concatenate the s into the target vector E IR". We assume the labels are generated as follows: there exists 8" I2 (note q = d), noise parameter ε >> O and some p. such that
= (c, 0, 0. pe) IR", y X0 -c.
For subset S, Xg and ys denote the corresponding covariates and responses, while X-s and y-s represent their complements. To ensure the uniqueness of the optimal solution, we assume N = = X is invertible. and that Σ x is also invertible (when this assumption is violated, our results naturally extend to ridge regression). The hat matrix is denoted as H = XN-IXT The diagonal element hą of H represents the leverage score of 2;, and the off-diagonal element hij represents the cross-leverage score [Chatterjee and Hadi, 2009] between z; and 2j-- The Ordinary Least Squares (OLS) estimator is given by
i arg min - n
Σ m
|x0 y11 N
(8)
Let ú: = =x be the prediction and r, = 01 y: be the negative residual for the i-th sample. Throughout Sections and 4, we focus on the linear target function ((0) = xeea for Jiest = p+1 whose first coordinate is also 1. This choice of Frest is intentional: it greatly simplifies the analysis by making most of the individual effects negative, as reflected in Figures 1 to and the calculations in Appendix A. Furthermore, due to the continuous nature of the problem, our conclusions hold for set of Fest with non-zero Lebesgue measure.
3.1 Influence function not accurate (even) in linear models
Influence function is widely acknowledged as an accurate alternative of leave-one- out re-training in linear models [Koh and Liang, 2017, Basu et al., 2021, Bae et al., 2022]. In this section, however, we chal- lenge this viewpoint by pointing out pre- viously overlooked fact: the influence func- tion fails to incorporate the leverage scores of individual samples in linear regression, which could result in its failure selecting the most influential sample (i.e., 1-MISS).
Influence Estimates
O 8: 0.120
0
3: 0.038
O
1: 0.117
0 60.054
7: -:00.1
50-005
2
4: -0.05
2:-0.061
0-
Test
Original OLS OLS w/o ! OLS w/o ?
Plugging the squared loss into Eq. (5), we have I(S) = -nN- Eies Z,7i. Therefore, ZAMinfluence assigns V; N IıP; to each sample. We refer to them as influence estimates. On the other hand, it is well-known in the statistics liter- ature [Beckman and Trussell, 1974, Cook, 1977] that
-2
-8
Figure 1: Influence estimates suffer from disparate lev- els of under-estimation, leading the failure of 1-MISS
0 θ_(0) 0 N-l
h4s

---

Consequently, the change in the target function is given by A- N N N which deviates his
from the influence estimate by a factor of 1/(1 - ha) and implies under-estimation (a phenomenon which was also reported in Koh al. [2019]). This is particularly concerning when sample has high leverage score (e.g., an outlier [Chatterjee and Hadi, 1986]): in this case, the influence function substantially under-estimates the individual effect, potentially leading to the failure of 1-MISS. We illustrate this intuition in Figure I: while point X is scored highest by the influence function, is however removing point ① (which has the highest leverage score) that leads to the greatest change in the prediction on the test sample. More generally, we present the following theorem illustrating the failure of ZAMinflunnce in I-MISS, with the proof detailed in Appendix A.2.
Theorem 3.1. Assume h11 > hyn- Under the label generation process described in Eq. (7), there exists some p. such that ZAMinftuence fails to select the most inftuential sample.
Takeaway: Even when the influence estimates have high correlation with the individual effects, they can be misleading for extreme samples. As result, the influence function may not be a reliable tool for MISS.
3.2 Violation of the additivity assumption: amplification and cancellation
Note that the individual effects (1) 's can be computed efficiently for linear regression (this is generally infeasible for more complicated tasks) by correcting the influence estimates U,'s with their corresponding leverage scores. Hence, natural alternative to directly perform greedy selection based on the A-(1) 's. We refer to this method as Leverage-Adjuster Greedy Selection (LAGS). Nevertheless, we will illustrate in this section that even with perfect individual influence estimation, LAGS may still fall short in MISS due to violations of the additivity assumption.
We start by computing the closed-form of A_s. The proof can be found in Appendix A.3. Proposition 3.2. For any set of indices S, we have
A == (0= <b0) Trsss XJ ( (I=-xsN-X33) (
(10)
Remark 3.3. Denote Ms X It is stratihttfrwward to see that replacing the Neumann series (I, 10-M5 Ms) I + Ms + M ... ... by the identity matrix yields the influence estimates, i.e., the first-order approximation. We further prove in Appendix A.4 that there is one-to-one correspondence between the Taylor series of (5)) and the Neumann series: for any k N+ the k-tth order approximation of 0- (8) is equivalent to truncating the Neumann series at M On the other hand, LAGS is based on the diagonal approximation of (Tx- Ms).
To systematically study the failure mode of LAGS, we consider S = [i, J. In this case, 2,,, , (1 - h11) 2 + (1 - hw)N -,,,,,- +
N DEANN'(aa (aary + zzm)
A-1is)
(i.)) = Fesst
(1 - h.s
h93) h22
(1 - h1) (A (1) + A ( + Te N N + +2m))
(11)
(1 h1 - h22) - h2
From Eq. we identify two primary factors contributing the non-additivity of the group effect: the cross- cross-leverage score has in the denominator, which can lead to adper-additiviy by inflating the sum of individual effects, and the cross terms TT - (( + ZyTT)) in the numerator, which may result in sub-additivity through the neutralization of individual effects. We refer these phenomena as "ammlification" and "cancellation," respectively, and will delve into how they provably lead to the failure of LAGS in what follows.
Amplification. Amplification occurs when the group effect a set substantially exceeds the sum of individual effects. As suggested by (11,,,, this phenomenon is pronounced when the cross-leverage score is high. Therefore, we focus on scenarios where there are c 2 2 identical copies of a sample, in which case the cross-leverage score becomes the leverage score. Intuitively, this setting can be generalized to a cluster of similar samples. We first prove a useful result in this context.
Proposition 3.4. Suppose there are copies of (xi, v:). We have
A_ c. (1 hw)) A_ A_()) (()
1 cha > c.
(12)
5

---

where A-1s3= denotes the group effect of removing all copies of (5i, Vs).
The proof can be found in Appendix A.5. It suggests that the group effect not only surpasses the sum of individual effects, but their ratio can be unbounded as h4 Put differently, a sample with minor in- fluence can collectively cause substan- tial effect when grouped with similar ones. In MISS, this could lead the failure of LAGS when there is cluster of samples with high leverage scores yet do not have the largest individual effects. This intuition illustrated in Figure 2: while points @ and @ (the pink cluster) have the highest in- dividual effects due to their large residuals, points ① and @ (the green cluster) with high leverage scores constitute the most influential size-2 subset.
Individual Effects
0 0.049
8: 0.138
0
3: 0.082
O
1: 0.129
0
5:-0.130
O
2: 0.083
O
6: 6:-0.138
0
Test
Original OLS
OLS w/o
-8
Figure LAGS fails in 2-MISS due amplification
We show a generalization of this example in the following theorem and defer its proof to Appendix A.6.
Theorem 3.5. Suppose there are e copies of (II, (11,,)) and (In, Vn), and that hus > hman Under the label generation process described in Eq. (7), there exists some p, such that LAGS fails in e-MISS.
Cancellation. Cancellation happens when the group effect of a set S is less than one of its subsets S', indicating that removing S S' induces a negative effect.
In this case, cancellation equivalent to A-(1,) A-(n)
(ny (we assume w.l.o.g. that A_(x) > (1)). From (11,) this inequality is likely to hold when A-(1) has a small magnitude compared to A A_()). and the sign of in differs from that of fz. If further have that A- (1) and (a) are
Individual Effects
O
0.466
O
2: 20-0.025
0.076
0
7:00.334
4: 0.008
O
5: 5:-0.079
-.00.13
O
6: 6:10.107
2
71
the top-2 positive individual effects (which
guarantees that they will be selected by the greedy algorithm), then LAGS will fail this context.
0
Test
Original OLS
OLS w/o ?
illustrate this in Figure 3: although points @ and I have the top-2 individual effects and are positive, their group effect size-2 subset is less than the individual effect of point X
OLS w/o ?
OLS 1
-2
-4
4
Figure 3: LAGS fails in 2-MISS due to cancellation
We present more general result in the following theorem and defer its proof to Appendix A.7.
Theorem 3.6. Assume hma F Under the label generation process described in Eq. (7), there exists some p. such that LAGS fails 2-MISS.
Takeaway: LAGS provably works for MISS when all cross-leverage scores are zero, but can fail with even a single non-zero cross-leverage score. This highlights the algorithm's 's fragility.
Promises of the adaptive greedy algorithm
Given the limitations of LAGS, pertinent question arises: is it possible to capture non-additive structure of the joint effect without enumerating subsets? In this section, we examine refined heuristic proposed by Kuschnig et [2021], and provide theoretical analysis following our framework in Section 3. Kuschnig et al. [2021] originally introduced this refined algorithm in the

---

context of linear regression, which applies to general influence-based greedy heuristics. The idea is to adaptively build the influential subset. Specifically, the algorithm works by 1) refitting the model on the current dataset and recalculating the individual effect influence estimate for each sample; 2) excluding the most influential sample from the current dataset; 3) adding it to the influential subset. This iterative process repeated until the subset reaches the desired size. We refer to this as the adaptive greedy algorithm.
It is empirically observed that the adaptive greedy algorithm outperforms LAGS in linear regres- sion [Kuschnig et al., 2021]. In this section, we further aim to provide theoretical support for the benefits of adaptivity. Specifically, we will show that in scenarios where LAGS fail due cancel- lation, the adaptive greedy algorithm can effectively address this problem by leveraging a scoring function that captures the marginal contributions relative the removal of the most influential sample.
Following the cancellation setup, (In, ynn) is the most influential sample w.r.t. the full dataset. We denote A {s} the actual effect of removing (2;, y1) for 1 S S n 1 after the removal of (In, Vn)) Essentially, A' is the scoring function employed in the second step of the adaptive greedy algorithm. We start by proving two useful properties of A' (the proof is deferred to Appendix B.2).
Proposition 4.1. The scoring function A' satisfies the following properties:
1. Sign consistency: A'{s3) and (A-(i.) A-(s)) have the same sign for 1 Sis
2. Order preservation: (A-(0)=2 1n-1 and {A (A-(im)) 1 are order-isomorphic.
These properties have significant implications. The first property indicates that A' is a more reliable scoring function as it captures the marginal contribution of each sample relative the removal of (In; )n). Hence, in the cancellation setup, A' will not choose (æ1, yn ). even though A represents the second-largest individual effect and is positive. In contrast, the actual effect A, which reflects the marginal contribution of each sample relative to the full dataset, does not account for how a newly selected sample interacts with those already selected. The second property further guarantees the success of MISS based on A'. Formally, we prove the following for the adaptive greedy algorithm.
Theorem 4.2. Under the label generation process described in Eq.(7), suppose A-11,, (m) > 0, A- (1.m3 < A-nn), (indicating cancellation). and that n E Sop, (i.e., (In, (En. is contained in the most influential subset), then the adaptive greedy algorithm solves 2-MISS.
Proof. We first show that the condition A-(1.n) < A--(n) implies that (Izz yn) the most influential sample (the proof is deferred to Appendix B.3). This ensures that the adaptive greedy algorithm will select (In: Un) in the first step. We now discuss two cases separately.
Case 1: If A- - A- [x] < O for every 2 < i S n 1, then Sape. {n). Furthermore, by the first property of Proposition 4.1 we have A'(1) < 0 for 1 S S n 1. This implies that the adaptive algorithm will return Ø in the second step since no scores are positive, as desired.
Case 2: If there exists some 2 < < n 1. such that A- A-(n) > 0. We denote the most influential subset as Sopt.2 = {i", n.". Since A_ [i+.n] - AA [(n] >> 0, the first property of Proposition 4.1 implies A-( > 0. Furthermore, by the second property of Proposition 4.1, the adaptive greedy algorithm will return the correct index i* in the second step.
Combining the above two cases finishes the proof of Theorem 4.2.
Remark 4.3. In the cancellation setup. our theoretical results are restricted to 2-MISS. We identify two challenges: 1) Conceptually, it is not immediately clear how to define cancellation for more than two samples; 2) Technically, proving the success of MISS is much harder than constructing a counterexample since it requires enumerating all possible subsets, whose number grows exponentially with k. We leave this as future work.
essence, the critical limitation of LAGS and other influence-basee greedy heuristics is their reliance one-pass procedure that measures the contribution of each sample solely in relation to the full training set. On the other hand, the adaptive greedy algorithm considers more complex interactions between samples, akin those in data Shapley [Ghorbani and Zou, 2019]. leading to more effective subset selection.
Takeaway:
7

---

5 Experiments
In this section, we empirically evaluate the efficacy of the adaptive greedy algorithm real-world datasets by comparing the performance of the vanilla greedy algorithm versus the adaptive greedy algorithm across a range of k's.' We cover the simple linear regression studied in Sections 3 and 4 as well as more complicated scenarios (including the classification task and non-linear neural networks) as complement. Additional experiments synthetic datasets can be found in Appendix C.I.
Linear Regression with Concrete
Logistic Regression with Waveform
MLP with MNIST
12-
2.50-
10-
2.00
1.75
1.50
1.25
1
10
20
30
40
50
60 70 80
100
1
10
20
30
40
50
60
80 90 100
1.00
1.0
1.0
Winning Rote
0.6
0.6
0.6
0.4
0.4-
0.2-
0.0
1
10
20
30
40
50
60
70
80
90
100
10
20
30
40
50
60
70
80
90
100
LAGS
Adaptive LAGS
ZAMinfluence
Adaptive ZAMinfluence
Figure 4: Adaptive Greedy v.s. Greedy Algorithm. Row Averaged actual effect A-s measures the averaged actual effect induced by the greedy and adaptive greedy algorithms. Row 2: Winning rate indicates the proportion of instances where one algorithm outperforms the other.
Evaluation metrics. We evaluate the algorithms using two metrics, the averaged actual effect and the winning rate. Given held-out test set, we define the averaged actual effect A_s as the mean of the actual effects w.r.t. each test point. A higher score of A-s indicates more influential subset is selected on average. Additionally, we report the winning rate across test data points in a held-out test set, namely the ratio of the algorithm outperforms the other one in terms of the actual effect A-s.
Target functions and greedy algorithms. We consider two types of tasks: regression and clas- sification. For the regression task, we adopt the target function ((0) = x =1es0 on given test point = (Frest: Mea)) We utilize LAGS as the vanilla greedy algorithm. For the classification task, we consider the target function (0) log(p(z; ())((( p(2; 0))), where p(2; 0) represents the softmax probability assigned to the correct class. We opt for the ZAMinfluence as the vanilla greedy algorithm.
Experimental setup. For regression, we choose popular UCI dataset Concrete Compressive Strength [Yeh, 2007]. For classification, we experiment with a moderate-scale UCI tabular dataset Waveform Database Generator [Breiman and Stone, 1988] and an image dataset MNIST [LeCun et al., 1998]. We apply logistic regression on the former and a simple 2-layer multi-layer perceptron (MLP) the latter. We defer details of the datasets, train/test split, and MLP training to Appendix C.
Approximated actual effect. We address one unique challenge for the MLP: for neural networks, it impossible obtain the actual effect since the optimal model is not unique in general. To address this, we adopt an ensemble technique used in recent literature [Park et al., 2023]: averaging the target function's 's values from several independently trained models. Specifically, same initialization but different seeds. This works for both the greedy algorithm and evaluation: for the former, we estimate each model's 's influence with the ZAMinfluence algorithm and select the most influential subset based on the averaged influence; for the latter, we approximate the actual effect of subset by the averaged difference the target values of each model, trained with or without S.
train models with the
While ensemble solves the non-uniqueness problem, it induces a significant computational burden. Noticeably, the adaptive greedy algorithm now requires retraining for (I: x number of ensembles) times. To mitigate it, we use an efficient approximate variant of the ZAMifluence estimation algorithm in our implementation and devise two strategies. We defer the concrete descriptions Appendix C.4.
Our code is publicly available at https: htap::://gtthutt

---

Results. We present the main results in Figure 4. First, we see that as k: increases, the averaged actual effect A given by both the vanilla and the adaptive greedy algorithms increase, which aligns with the intuition that removing larger set S induces a greater joint effect A.s. Furthermore, the adaptive greedy algorithm surpasses its vanilla counterpart across all scenarios and all k's under both metrics. This implies that the benefits of adaptivity extend beyond linear regression and apply to more complicated scenarios like classification tasks and even
neural networks.
Finally, for the experiment on MLP specifically, we report results of multiple random seeds in Appendix C.5 to account for the randomness in model training. The consistent results across different seeds demonstrate the robustness of the aforementioned conclusions.
6 Discussion
Failure of the adaptive greedy algorithm. While Theorem 4.2 demonstrates the advantages of the adaptive greedy algorithm, it is still not perfect. Specifically, the assumption n E Sopt.2 in Theorem 4.2 is actually necessary: if the most influential sample is not part of the most influential subset, the algorithm will make an error in the first step and cannot correct this mistake in subsequent procedures. For instance, under the amplification setup as in Theorem 3.5, it is straightforward to that the adaptive greedy algorithms provably fail in c-MISS since it selects (Ni, Mn) in the first place. Second-order approximation. To more effectively capture the amplification effect caused by clusters of similar samples, it is essential utilize algorithms that can detect higher-order interactions. In this context, the second-order group influence introduced by Basu et al. [2020] is a more powerful alternative. It is calculated based on the second-order approximation as described in Remark 3.3:
Q-s= = T - x3
4 + XsN-1X3 xx] (X - -v))
(13)
From here, the original MISS can be cast as a quadratic optimization problem (see Appendix D.1) and solved via L1 relaxation and projected gradient descent. Furthermore, we have Q- (1)e =
eur//2 ||2 cui, Q Q-ink- = v²v,, " 112 + cUn. indicating that quadratic approximation can capture the joint effect amplified by the leverage score by emphasizing the norm.
Submodular property. Given the challenges of finding an exact solution, it is tempting to explore approximate solutions to MISS with provable guarantees. A classical result of Nemhauser et al. [1978] states that so long as the (set) value function satisfies the submodular property, the greedy algorithm will return solution within factor 1 - 1/c of the optimum. While the value function associated with the first-order approximation is submodular due to linearity, we show in Appendix D.2 that this is generally not the case for Q-s. Since the second-order approximation is more accurate estimation of the actual effect, this suggests that the actual effect is unlikely to be submodular either. Therefore, MISS is expected to be hard even when we allow approximate solutions.
The role of target function. Our negative results critically rely on the choice of Fiest, underscoring the importance of the target function - an issue that has been overlooked in prior research. In addition, we have identified few target functions in which the influence-based greedy heuristics
fail to provide meaningful results: 1) the change of norm, Φ1 (0) = ||0 0| ; 2) the training loss, (2) = | - y/12. In both of these cases, we have Ve ( = 0, implying that the scores assigned to each sample will also be O.
Implication on Linear Datamodeling Score. Recently, Linear Datamodeling Score (LDS) [Park et al., 2023] has emerged as prominent metric for evaluating data attribution algorithms [Zheng et al., 2024, Bae et al., 2024]. Central to its design is the assumption that group influence is additive, which we critically examine in our work and reach a negative conclusion. This raises an important question: does a higher LDS result from a truly better data attribution algorithm, or are certain algorithms simply more aligned with the potentially flawed additive assumption? ? While LDS offers valuable insights into data attribution, we believe is crucial for the research community to develop evaluation metrics that better capture the non-additive and contextual nature of training data influence.
Limitation and future direction. Despite thorough theoretical and empirical analyses, our study does not offer algorithmic improvements over existing research. We believe solving general MISS is a challenging problem, and hypothesize that there is an inherent trade-off between performance and computational efficiency, in which an increase performance necessitates additional computing. This pattern is already reflected in the comparison between the vanilla and adaptive greedy algorithms, a trend that will likely continue in future research. To address this challenge, we suggest incorporating the knowledge of target function and data characteristics into algorithmic designs.

---

7 Related work
(Most) influential subset. Since the seminal work of Koh and Liang [2017], which utilized the influence function to identify influential individuals, subsequent research has explored finding an influential set of samples [Khanna et al., 2019, Basu al., 2020, Broderick et al., 2020J. Among them, a notable example is the ZAMinfluence algorithm by Broderick et al. [2020], which builds on the group influence function [Koh et al., 2019] I] and greedily selects an approximately most influential subset. ZAMinfluence is particularly renowned for its broad applicability: it can be used to improve various dimensions of machine learning such as pre-training [Wang et al., 2023], dataset pruning (Yang et al., 2023b], and trustworthiness [Wang et al., 2022, Sattigeri et al., 2022, Chhabra et al., 2024], well applied econometrics [Attanasio et al., 2015, Angelucci et al., 2015], economics [Finger and Möhring, 2022, Martinez, 2022], and social science [Fubank and Fresh, 2022]. Additionally, Kuschnig et al. [2021] proposed a refined version of Z.Minfluence based on iteratively refitting the model and removing the most influential sample, an approach which was also explored in Yang et al. [2023a].
assess the sensitivity of inferential results in multiple domains such as
Theoretical understanding of MISS. Despite its empirical success, the theoretical understanding of ZAMinfluence and other influence- greedy heuristics remains limited. Giordano et al. [2019a,b] provided finite sample error bounds between the approximated and actual effects, but consistency (i.e., the error uniformly converges to 0 for all subsets as the sample size goes to infinity) is only achieved as the fraction of removed samples a approaches zero. Fisher et al. [2023] extended the analysis to any fixed 0 < a < 1, but their consistency is not directly related to the actual effect, thus offering limited insights for MISS. Moitra and Rohatgi [2023], Freund and Hopkins [2023] examined finite- anite-sample stability (i.e., the minimum number of samples that need to be dropped in order to flip the sign of a coordinate) in linear regression and proposed algorithms with provable guarantees, yet they are confined to highly specific scenarios, such as very low dimensions or binary design matrices. Saunshi et al. [2023] explored the additivity assumption in group influence within a different yet less interpretable framework. We position our work as the first to provide fine-grained analysis of the common practices in MISS, shedding light on the limitations of influence-aased greedy heuristics as well as the potential of the adaptive greedy algorithm.
Multiple outlier detection. Classical tools in statistics, such as Cook's s distance and its variants, can detect a single outlier in linear regression [Cook, 1986, Chatterjee and Hadi, 1986] and generalized linear models [Wojnowicz et al., 20166. Nevertheless, they struggle with multiple outliers due to the well-known phenomena of swamping and masking [Rousseeuw and Leroy, 1987, Hadi and Simonoff, 1993]. This challenge has motivated line of research in regression diagnostics [Fox, 201 9I, known as multiple outlier detection. Prominent approaches include clustering [Gray and Ling, 1984, Hadi, 1985]. influence matrix [Peña and Yohai, 1995], and class of iterative procedures [Belsley et al., 1980, Hadi and Simonoff, 1993, She and Owen, 2011, 1, Roberts et al., 2015] that resemble Kuschnig et al. [2021]. While seemingly alike, its key distinction from influential subset selection is that the 'outlier' is defined context-independerr
rather than with respect to a specific quantity of interest.
Broader context. Our work falls under a broader research area that aims to attribute and interpret model behavior through the lens of data (a.k.a. data attribution). Beyond the influence function, which is central to our study, other popular approaches include the representer point method [Yeh et al., 2018], the data Shapley [Ghorbani and Zou, 2019, Jia et al., 2019], the TracIn algorithm [Pruthi et al., 2020], and more recently, the datamodels [Ilyas et al., 2022]. For a comprehensive review of this subject, we refer readers to Hammoudeh and Lowd [2024]. Finally, should not be confused with data selection [John and Draper, 1975, Kolossov et al., 2023]. While many data attribution algorithms et al. [2024] demonstrated that the effectiveness of data Shapley in data selection hinges on the utility function), data selection remains an independent research area. It typically involves subsampling a small fraction of the training data to enable effective and data-efficient learning or estimation, differing from MISS in its objectives, methodologies, and applications.
emphasize that MISS
indeed be applied for data selection (e.g., a recent study Wang
Conclusion
We have provided a comprehensive study of common practices in MISS, revealing the failure modes of influence-based greedy heuristics and uncovering the benefits of adaptivity. We hope our work will enhance the transparency and interpretability of machine learning models by illuminating the collective influence of training data, and serve a foundation for future algorithmic advancements.
10

---

Acknowledgement
YH and HZ. are partially supported by an NSF IIS grant No. 2416897. YH would like to thank Fan Wu for her generous help in the experiments. HZ would like to thank the support from a Google Research Scholar Award. The views and conclusions expressed in this paper are solely those of the authors and do not necessarily reflect the official policies or positions of the supporting companies and government agencies.
References
A. F. Agarap. Deep learning using rectified linear units (relu), arXiv preprint arXiv: arXiv: 1e03.0007.. 2018.
K. Amarasinghe, K. T. Rodolfa, H. Lamba, and R. Ghani. Explainable machine learning for public policy: Use cases, gaps, and research directions. Data & Policy. 5xe5, Jan. 2023.
R. Andersen. Modern Methods for Robust Regression. SAGE Publications, 2007.
M. Angelucci, D. Karlan, and J. Zinman. Microcredit impacts: Evidence from a randomized mierocredit program placement experiment by compartamos banco. American Economic Journal: Applied Economics, 7(1):151-182, 2015.
I. Ibbara,- L. Goff, D. Jiménez-Hernández, J. Lanier, and E. G. Weyl. Should we treat data as labor? moving beyond "free". AEA Papers and Proceedings, 108:38-42, 2018. ISSN 25740768, 25740776.
O. Attanasio, B. Augsburg, R. De Haas, E. Fitzsimons, and H. Harmgart. The impacts of microfi- nance: Evidence from liabi-liability lending in mongolia. American Economic Journal: Applied Economics, 7(1):90-122 2015.
Bac, N. H. Ng, A. Lo, M. Ghassemi, and R. Grosse. If influence functions are the answer, then what is the question? In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022.
J. Bae, W. Lin, J. Lorraine, and R. Grosse Training data attribution via approximate unrolled differentation. arXiv preprint arXiv:2405. 12186, 2024.
E. Barshan, M.-E. Brunet, and G. K. Dziugaite. Relatif: Identifying explanatory training samples via relative influence. In S. Chiappa and R. Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1899-1909, PMLR, 26-28 Aug 2020.
S. Basu, X. You, and S. Feizi. On second-order group influence functions for black-box predictions. In International Conference on Machine Learning, pages 715-724. PMLR, 2020.
S. Basu, P. Pope, and S. Feizi. Influence functions in deep learning fragile. In International Conference on Learning Representations, 2021.
R. Beckman and H. Trussell. The distribution of an arbitrary studentized residual and the effects of updating in multiple regression. Journal of the American Statistical Association, 69(345):199-20) 1974.
D. Belsley, E. Kuh, and R. Welsch. Regression Diagnostics: Identifying Influential Data and Sources of Collinearity. Wiley Series in Probability and Statistics Applied Probability and Statistics Section Series. Wiley, 1980. ISBN 9780471058564
B. Biggio, I. Corona, Maiorca, Nelson, N. Šindić P. Laskov, G. Giacinto, and F. Roli. Evasion attacks against machine learning at test time. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III 13, pages 387-402. Springer, 2013.

---

Bracke, A. Datta, C. Jung, and S. Sen. Machine learning explainability in finance: application to default risk analysis. Technical report, Bank of England, 2019.
L. Breiman and C. Stone. Waveform Database Generator (Version 1). UCI Machine Learning Repository, 1988. DOI: https//dbi.orgg1.22445222
Broderick, Giordano, and Meager. An automatic saitte-ample robustness metric: when can dropping a little data make a big difference? arXiv preprint 2rXiv:2011.14999 2020.
S. Chatterjee and Hadi. Influential observations, high leverage points, and outliers in linear regression. Statistical science, pages 379-393, 1986.
Chatterjee and A. Hadi. Sensitivity analysis linear regression. John Wiley & Sons, 2009.
I. Chen, F. D. Johansson, and D. Sontag. Why is my classifier discriminatory? In Advances in Neural Information Processing Systems, volume 31, Curran Associates, Inc., 2018.
A. Chhabra, P. Li, P. Mohapatra, and H. Liu. "what data benefits my classifier?" enhancing model performance and interpretability through influence- data selection. In The Twelfth International Conference on Learning Representations, 2024.
R. D. Cook. Detection of influential observation in linear regression. Technometrics, 19(1):15-18, 1977.
R. D. Cook. Assessment of local influence. Journal of the Royal Statistical Society Series B: Statistical Methodology, 48(2):133-155, 1986.
N. Eubank and A. Fresh. Enfranchisement and incarceration after the 1965 voting rights act. American Political Science Review, 116(3):91-8866 2022.
R. Finger and N. Möhring. The adoption of pesticide-free wheat production and farmers' perceptions of its environmental and health effects. Ecological Economics, 198: 107463, 2022.
J. Fisher, L. Liu, K. Pillutla, Y. Choi, and Z. Harchaoui. Influence diagnostics under self-concordance. In International Conference on Artificial Intelligence and Statistics, pages 10028-10076. PMLR, 2023.
J. Fox. Regression diagnostics: An introduction. Sage publications, 2019.
D. Freund and S. Hopkins. Towards practical robustness auditing for linear regression, arXiv preprint arXiv:2307.16315. 2023.
George, C. Laurent, X. Bouthillier, Ballas, and Vincent. Fast approximate natural gradient descent in kronecker factored eigenbasis. Advances in Neural Information Processing Systems, 31, 2018.
A. Ghorbani and J. Zou. Data shapley: Equitable valuation of data for machine learning. In International conference on machine learning, pages 2242-2251. PMLR, 2019.
R. Giordano, M. I. Jordan, and T. Broderick. A higher-order swiss army infinitesimal jackknife. arXiv preprint arXiv: 190..1217... 2019a.
R. Giordano, W. Stephenson, R. Liu, M. Jordan, and T. Broderick. A swiss army infinitesimal jackknife. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1139-1147. PMLR, 2019b.
J. B. Gray and R. F. Ling. K-elustering as a detection tool for influential subsets in regression. Technometrics, 26(4):305-318, 1984.
R. Grosse, J. Bae, C. Anil, N. Elhage, A. Tamkin, A. Tajdini, B. Steiner, D. Li, E. Durmus, E. Perez, E. Hubinger, Lukoλiūté, K. Nguyen, N. Joseph, S. McCandlish, J. Kaplan, and R. Bowman. Studying large language model generalization with influence functions, 2023.
12

---

H. Guo, N. Rajani, P. Hase, M. Bansal, and C. Xiong. FastlF: Scalable influence functions for efficient model interpretation and debugging. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 10333-10350. Association for Computational Linguistics, Nov. 2021.
K. Guu, Webson, Pavlick, L. Dixon, I. Tenney, and Bolukbasi. Simfluence: Modeling the influ- ence of individual training examples by simulating training runs, arXiv preprint arXiv:2303.081 2023.
A. S. Hadi. K-clustering and the detection of influential subsets. Technometrics, 27(3):323-324, 1985.
A. S. Hadi and J. S. Simonoff. Procedures for the identification of multiple outliers in linear models. Journal of the American statistical association, 164-222: 1993.
Z. Hammoudeh and D. Lowd. Training data influence analysis and estimation: A survey, Machine Learning, pages 1-53, 2024.
F. R. Hampel. The influence curve and its role in robust estimation. Journal of the american statistical association, 69(346)3383-335 3933 1974.
F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel. Robust Statistics: The Approach Based on Influence Functions. John Wiley Sons, 2005.
Huang, D. R. Burt, D. Nguyen, Y. Shen, and T. Broderick. Approximations to worst-case data dropping; unmasking failure modes. arXiv preprint arXiv:2408. 09008, 2024.
A. llyas, S. M. Park, Engstrom, G. Leclere, and A. Madry. Datamodels: Predicting predictions from training data. In International Conference on Machine Learning, pages 9525-9587. PMLR, 2022.
R. Jia, D. Dao, B. Wang, F. A. Hubis, N. Hynes, N. M. Gürel, B. Li, C. Zhang, D. Song, and C. J. Spanos. Towards efficient data valuation based on the shapley value. In The 22nd International Conference on Artificial Intelligence and Statisties, pages 1167-1176. PMLR, 2019.
R. John and N. R. Draper. D-optimality for regression designs: a review. Technometries, 17(1):
15-23, 1975.
R. Khanna, B. Kim, J. Ghosh, and S. Koyejo. Interpreting black box predictions using fisher kernels. In The 22nd International Conference Artificial Intelligence and Statistics, pages PMLR, 2019.
P. W. Koh and P. Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pages 1885-1894. PMLR, 2017.
W. W. Koh, K.-S. Ang, H. Teo, and P. S. Liang- On the accuracy of influence functions for measuring group effects. Advances in neural information processing systems, 32, 2019.
G. Kolossov, A. Montanari, and P. Tandon. Towards statistical theory of data selection under weak supervision. In The Twelfth International Conference on Learning Representations, 2023.
S. G. Krantz and H. R. Parks. The implicit function theorem: history, theory, and applications. Springer Science & Business Media, 2002.
N. Kuschnig, G. Zens, and J. C. Cuaresma. Hidden in plain sight: Influential sets in linear models. Technical report, CESifo, 2021.
Y. LeCun, I.. Bottou, Bengio, and Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, (1211)):278-2222 1998.
Martinez. How much should we trust the dictator's gdp growth estimates? Journal of Political Economy, 130(10):2711-276) 2022.
13

---

A. Moitra and D. Rohatgi. Provably auditing ordinary least squares in low dimensions. In The Eleventh International Conference on Learning Representations, 2023.
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions Muthematical programming. 14:265-294 1978.
S. M. Park, K. Georgiev. A. Ilyas, G. Leclerc, and A. Madry. Trak: Attributing model behavior at scale. In International Conference Machine Learning, pages 27074-20 27113. PMLR, 2023.
D. Peña and V. Yohai. The detection of influential subsets in linear regression by using an influence matrix. Journal of the Royal Statistical Sociery: Series B (Methodological), 57(1):145-11) 156, 1995.
K. B. Petersen, M. S. Pedersen, et al. The matrix cookbook. Technical University of Denmark, 7(15): 510, 2008.
E. Price, S. Silwal, and S. Zhou. Hardness and algorithms for robust and sparse optimization. In International Conference on Machine Learning, pages 17926-17944, PMLR, 2022.
G. Pruthi, Liu, Kale, and M. Sundararajan. Estimating training data influence by tracing gradient descent. In Advances in Neural Information Processing Systems, volume 33, pages 19920-19930, 2020.
S. Roberts, M. A. Martin, and L. Zheng. An adaptive, automatic multiple-case deletion technique for detecting influence in regression. Technometrics, 57(3):408-417 2015.
Rousseeuw and A. Leroy. Robust regression and outlier detection, 1987.
S. Ruder. An overview of gradient descent optimization algorithms. arXiv preprint arXiv: 2016.
C. Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-215 215, May 2019.
P. Sattigeri, S. Ghosh, I. Padhi, P. Dognin, and K. R. Varshney. Fair infinitesimal jackknife: Mitigating the influence of biased training data points without refitting. Advances Neural Information 2022.
Processing Systems, 35:35894-35500
N. Saunshi, A. Gupta, M. Braverman, and S. Arora. Understanding influence functions and datamodels via harmonic analysis. In The Eleventh International Conference on Learning Representations, 2023.
A. Schioppa, P. Zablotskaia, D. Vilar, and A. Sokolov. Scaling up influence functions. Proceedings of the AAAI Conference on Artificial Intelligence, (((8))8179-8188) Jun. 2022.
Y. She and A. B. Owen. Outlier detection using nonconvex penalized regression. Journal of the American Statistical Association, (06(494):626-633) 2011.
C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties neural networks. In 2nd International Conference on Learning Representations, ICLR 2014, 2014.
S. Teso, A. Bontempelli, Giunchiglia, and A. Passerini. Interactive label cleaning with example- based explanations. In Advances in Neural Information Processing Systems, 2021.
J. Wang, X. E. Wang, and Y. Liu. Understanding instance-level impact of fairness constraints. In International Conference on Machine Learning, pages 231 14--3333.. PMLR, 2022.
J. T. Wang, T. Yang, J. Zou, Y. Kwon, and R. Jia. Rethinking data shapley for data selection tasks: Misleads and merits. In International Conference Machine Learning, pages 52033-52063. PMLR, 2024.
X. Wang, W. Zhou, Q. Zhang, J. Zhou, S. Gao, J. Wang, M. Zhang, X. Gao, Y. W. Chen, and T. Gui. Farewell aimless large-scale pretraining: Influential subset selection for language model. In Findings of the Association for Computational Linguistics: ACL 2023, pages 555-568, 2023.
14

---

M. Wojnowicz, B. Cruz, X. Zhao, B. Wallace, M. Wolff, Luan,, and C. Crable. "influence sketching": Finding influential samples in large-scale regressions. In 2016 JEEE International Conference on Big Data (Big Data). IEEE, Dec. 2016.
J. Yang, S. Jain, and B. C. Wallace. How many and which training points would need to be removed to flip this prediction? In Proceedings of the 17th Conference the European Chapter of the Association for Computational Linguistics, pages 2571 3571-2584, 2023a.
S. Yang, 7. Xie, H. Peng, M. Xu, M. Sun, and P. Li. Dataset pruning: Reducing training data by examining generalization influence. In The Eleventh International Conference on Learning Representations, 2023b.
Y. Yang, G. Li, H. Qian, K. C. Wilhelmsen, Y. Shen, and Y. Li. SMNN: batch effect correction for single-cell RNA-seq data via supervised mutual nearest neighbor detection. Briefings in Bioinformatics, 22(3):bbaa097, 06 2020. ISSN 1477-4054.
C.-K. Ych, J. Kim, I. E.-H. Yen, and P. K. Ravikumar. Representer point selection for explaining deep neural networks. In Advances in Neural Information Processing Systems, volume 31, 2018.
I.C. Yeh. Concrete Compressive Strength. UCI Machine Learning Repository, 2007. DOI: https://doi.org/10.244442
X. Zheng, T. Pang, C. Du, J. Jiang, and M. Lin. Intriguing properties of data attribution diffusion models. The Twelfth International Conference on Learning Representations, 2024.
15

---

A Omitted details from Section 3
A.1 Preparation work
We start by calculating the OLS estimator, the negative residuals ry ys,, the influence estimates 7q and the individual effects A [i) ss Suppose there are e copies of (21, (21))) and (Zn, Vn)), where c = 1 unless otherwise noted. Under the label generation process in Eq.(7), we have
i = N (NO" -CE11 pCEx.).
(14)
Therefore, the negative residuals are
r1 = (1 chi pchinle,
In = (p - pelinn chinee
(15)
and
T; - (chi + pchin)e, 2 2sisn- n n-
(16)
For Tist
pitp the influence estimates can be calculated as follows: p+1
(h11 + phin)(1 chn1 pchin)E
(phnn + hin) - pchan chin)E
01
Un
(17)
p
p p+1
whereas
c(1ii + )
1
50, 25isn-1.
(18)
p
Finally, we have
A-(1)= = (hn + phin) - chn - pehia)e
(phan + -hin) - pch chin)e
Am)
(p 1)(1 h11)
(p + 1)(1 hnn)
(19)
and
A- = c(hie + phiii)?ss (p 1)(1 hi))
S0, 25isn-1.
(20)
We also discuss a few properties of the hat matrix H. Lemma A.1. The leverage scores satisfy: hn < 4.2 Ann < 1
Proof. Note the hat matrix is idempotent, i.e., H2 = H. As a consequence, we have
hu ch
Σ
hr + chi
(21)
2=2
Note Σ T,4y is invertible, and that V is a non-zero vector. As consequence, we have
2
T N- + 0,
(22)
which further implies that the sequence (1ud) cannot be all zero. Therefore, we have h11 < The same argument applies to h
Lemma A.2. The following inequalities hold:
h < hithan and (1- ch - chum) < h
(23)
Proof. Since N is positive definite (PD), P VN-I is well-defined and is invertible. Note hig = x 1-NN-o 'I, = (Px,, Paz). Therefore, h2, < hithan is equivalent to
(Px1, Px,) < || |Prall
(24)
Since bn > Jonn we have 21 A Ine and therefore x # Fa since their first coordinates are the same. Therefore, Eq. (24) follows from the
inequality.
16

---

For the second inequality, denote CT = (Veri, v vera) Rdx2
Consider the following matrix:
N
C
=
c
12
(25)
Since the Schur complement of I2: S/ =
TTC = Di= PAs; > 0, and that 72 > we have S > 0. This further implies that the Schur complement of N is positive definite, i.e.,
1 -C---'"==--tuuuu
chi1 -chin
=/N= = -CN-CCT
-chin
1 1 c-chn
0.
(26)
As a consequence, we have det = (1-chu1)(1 - chan) c² h1n > O.
ch11)((1
A.2 Proof of Theorem 3.1
Proof of Theorem 3.1. We will show that there exists some p. such that
Un <<
Ann
(27)
V1 1 h1 and that on and en are positive. Since 62 S 0 for S i n 1, this implies that ZAMinfluence selects (I's Vn. and fails find the most influential sample (x1,g1). We will discuss three cases.
Case 1: hin = O. this case, both V and Un are positive by Lemma A.l. Furthermore, we have
Up hnn (1 hnn)
p².
(28)
h1 (1 h11)
which is continuous and takes values in [0, oo). Hence, there exists ap > 0 such that (27) holds.
Case 2: hin 0. When
hnn
hn
(29)
han
hin
both en and v,, are positive, Note Eq. (29) forms a valid interval by the first inequality in Lemma A.2. Now consider
Up (plina + l1 (p - plaa - hin)
(30)
(h11 + ppph)) (1 h1 phin)
An which is continuous and approaches 0 as p > hin and approaches oo as p hin exists 0 such that Eq. (27) holds.
Hence, there
Ana
Case 3: h O. When
hin
h11
<p<
(31)
Bnn
hin
both Un and en are positive. This forms a valid interval by the second inequality in Lemma A.2. The rest of the analysis can be performed similarly as in Case 2.
A.3 Proof of Proposition 3.2
Proof of Proposition 3.2. Applying the Woodbury matrix identity, we have
(N- - X (xss) N + N x3 (Tg
x
1 -1x
(32)
= + N- Σ 1
1
r N-1
(33)
hus
Therefore.
0 0 (N X3 [x - -
(34)
= -N-- - N (14 - XsN- (XTx x - x3
-
//
(35)
=N-1X (T. -X (X リ- y-ys)
(36)
=N-IX_ (16 15-X (xxxN-113) (X50 - -
(37)
17

---

and the actual effect of removing S is
s-s:= = x(0_s) x(() = -iees-- 1 [T 1.-X (Xg0 ys).
(38)
A.4 Correspondence between the Neumann series and the Taylor series
We will demonstrate that there is one-to-one correspondence between the Neumann series (/+ Ms)-1 and the Taylor series of 0 (6) To see this, consider
a0_s(0) = n(x T nóx Xs) - (Xsd-s(0) ys)
(39)
06
From Petersen et al. [2008], we have
0K KK
0K 05
K-1
(40)
06
for any invertible symmetric matrix K. By induction, we can show that for any 2 1,
0'0_s(0) (nt. 2!) x X
08
(41)
[xs(X x nox Xs) 'X i-1
(X -ys).
Therefore, by Taylor expansion, we have
0.0 s(0)
(42)
O6
1=1
6=0
= =
(Ks.N (Xs:N-133)
(X50- - ys)
(43)
= =0+N-IX
Σ M5-1 (X50 - -s))
(44)
Therefore, truncating at the i-th element in the Neumann series is equivalent to the -hd-order Taylor approximation of (5). In particular, first-order approximation corresponds to the identity matrix, which does not concern the leverage scores at all. Conversely, higher-order approximations entail
more accurate information on the leverage scores but come at the cost of computational efficiency.
A.5 Proof of Proposition 3.4
Proof of Proposition 3.4. Denote (13= as the optimal model parameters after removing all e copies formula, we have
of (I,, v:), and z = -E Zzbý- Using the
0 0_()-- θ (N c....]) -1((=))00-00) = cr,yt) N-1
(45)
N + cN -N,1,, N-1
(3-cr,y1) - N
(46)
chii
cN 1111 T 0
chaa
C. c.N-l -cN-- 1 chis
(47)
chise 1-chi
cN 1iTs
(48)
chu
Consequently,
CT
T T
N 1gp
(49)
1 cha
18

---

On the other hand, the influence of removing single copy is
Fusst N rajs
A-(1)
(50)
his
Therefore,
A 01]
c. 6-(1-115h hit))
C.
(51)
A A-(0) clis
A.6 Proof of Theorem
Proof of Theorem 3.5. suffices to show that there exists some p. such that A-(1) < <A_(n) and A- fnje. This further implies that the failure of LAGS, From Proposition 3.4, it suffices to
show there exists some p. such that
A-(m)
< - chann) (1 h11) (1 ch11)(1 - hnn)
1 1<
(52)
A- (1)
Note this is valid interval since
(1 chi ch1 Ann) = 1 chi1 - hnn + ch
(53)
1 chan hn + chiihnn
(54)
(1 chan (1 - hn),
(55)
where we use 2 2 and h1 > Ann in the second inequality. Furthermore, (52) is equivalent to
hnn Un 1 chan h11
(56)
V1
chi1
where we use A- (3) I-h, Therefore, we can repeat the analysis in the proof of Theorem 3.1 and conclude the existence of desired p.
A.7 Proof of Theorem 3.6
Proof of Theorem 3.6. Recall from (11) we have
A-11 (1- (1-hm)(1 - hnw (Am)(A_(1))) A_(m)) + hin N- (2ITn + xnrr)
(57)
(1 hn)(1 Nnn) - 11
Therefore, A A_(1.n) A (m) equivalent to
(1 h1-11)(1 hmn) ( (1) h A_ (n) + Iindi N- + xart) < 0.
(58)
Plugging in the formulas of A_ A Ti, Tn. Eq. (58) is equivalent to
- hyn (hn + p1 hn phin) + 12 (plinn + hin) (p- (p- hin
hnn
h-hnn + ppin)(p phann hin) hphinn + hin) - h11 phin).
(59)
Combining like terms, we get
(In + phin) ((1 11-hhi h1)(( - Mnn) - plin (1 Bnn) + -hin hin(plen + (hm)))
(phiin phfn
h2m hnn
<phann + hmn)
han 011 + pphin) + linn
(60)
This could be simplified to (h11 + phin) ((1 h11)(1 hnn) - 1121)) < -hin (phan + hin) (1 hn (1 hnn) h2
hnn
(61)
19

---

Since (1 h1))(1 hmn) hnn 0 by Lemma A.2, the above inequality is equivalent to
hin + hin) + hnn (h11 + phin) < O,
(62)
or
himp + hn Ann) hin 0. Now suffices to show there exists p, such that A (1), A (n} O. and that Eq. holds.
(63)
Case 1: hin < O. When
hin <
h11
(64)
han
hin
both (1) and A A-(n) positive. Furthermore, we have
lim
hinP + h11 - hnn) + 12 = hinn hnnnnn < 0
(65)
from Lemma A.2. This proves the existence of desired p.
Case 2: hin 0. When
hu
hin hnn
< <
(66)
hin
both A1(1) and A-(n) are positive. Similarly, we can pick p that is sufficiently close to such that # - and Eq. holds.
h11
Combining the above two cases finishes the proof as desired.
B Omitted details from Section 4
B.1 Preparation work
We start by computing the updated OLS estimator, the negative residuals, and the individual effects after removing the sample (In, Un). Denote N' = - næa," the updated OLS estimator is
0' = (N'0' - =x1).
(67)
Therefore, the updated negative residuals are ri = (1 - -411) e and re = -hiis for 2 Ssis S By the Sherman-Morriss formula.
N x N-1
N-1 N In J. N-1
(N')-- N-1
(68)
x N -lnn
hnn
Therefore, we have
Ninhinn hnn
22
him
M1 = h1s +
1/ = his +
x. (N') 2x,
(69)
1 hun
for sis n Finally, the adjusted individual effects are
2 N' N A' (1)
111 + p (N') -x
(70)
M11
p+1
and
Log N' 2apt N'-lar
phl N'' 1if2 (p + 11()(1 14,
A' (8)
(71)
M/
for 2 n
We will also make use of the following lemma.
Lemma B.I. For 2 < is (i.m < A A_ fut
is equivalent to
(hasiiin (1 Imnn) + 12 + (bxx(1 Inn)) + himhhnn) 0.
(72)
20

---

Proof. From (q.(1 have
A-(im) (1 h1;)1 hnn (A- - A A- + Fust N (ItNn + tznrs)
(73)
(1 h1a) hnn)) 12
Therefore, A (i.m) < Am(mi {n} is equivalent to
(1 h (1 A + 1 A A (n} + hn N
(aren + InTr) > 0.
(74)
Plugging in the formulas of A A (n}, ri, rns Eq.(74) is equivalent to
-(his + phpn)p2 ) hnn) + (phnn hin) phvn hin Min
1 1 hnn
+ (114 + pl 2phnn 22hnn) > 0.
(75)
Multiplying both side by (1 - hnn), the coefficient of p² is
- (1 - )nn) + 1 Mnr (1 1nn)) + 11 Nnn) 22hnn) = 0;
(76)
the coefficient of
- -2h1ahin (1 Nnnn) )2 + 1 1in 2hmn) + (1 Menn (h1e(1 21bnn) 2hinnsn))
-hihha (1 - )m hins
(77)
and the constant term is
- (1 - hnn) 2 - h2 n 2hishinbin - fan))) (1110(1 hmnn) + -hentnnnn
(78)
Therefore, Eq. (75) is equivalent to
(hishennt (1- hnn) + 12 ke + (her(1 - fawn) + hintin) 2²= 0.
(79)
B.2 Proof of Proposition 4.1
Proof of sign consistency. For (æ1, v1), plugging (69) into (70), we have
h2 hnnn
hinhan
A' A'(1) (1) <0 h11
+p
h1n
(80)
1 Ann
hanP + h11(1 )ma)
h < 0,
(81)
which aligns with Eq. Therefore, (1,m) < AA
A' (1) < O.
For (Ii, W1) where < i 1, plugging Fq. (69) into Eq. (71), we have
phass h12 + Binkin 1-
h1s +
hanhin 1-hmn
Ihhnn
A' (1)
(82)
(p 1) 1 his
42
T-ham
plin (hinltin + hesil - knn)) + (11x11 hmn) + Minhin)
(83)
(p 1)(1 hnn)8:
This implies
1'10) <0
(niphin hnn) + N2 hin) p + (hia(1 - hnnn + hnn 2= (84)
which aligns with (72) in Lemma B.1. Therefore, A (i.) < (m) = A (i) < 0.
Proof of order preservation. Plugging A-1 (n) into Eq. we have
-(1 1mn) ph;n)? )2 + (1 (ah) + -in))nn phnn - hin)
+ hsn (h1 + phin (p 2phnn 2h
A. A_ (i.m)
(85)
(1 - h1a) - hnn) h2
21

---

Denote 8; =1 (1x)(11 hmn) h2 > In the numerator, the coefficient of p² is
-(1 - Nnn ) + Inn (1 hw)(1 - hnn) + 12 (1 - 2han) = hnn
(86)
the coefficient of is 12h1shinn han) + (1 (1-his)(1 hess Man (1 his Missnn
-2h + hesten 220m))
(87)
hishin hin + sylin hinknnl (1 hes)
(88)
(Mrsstion + hinl han) + Mimhinn + sihin (2lenn - 1))
(89)
1 Ana
(hin (Neiel hnn) Ninhan) syhin 11)
(90)
1 Ann
and the constant term is
(1 hnm Mhi - h2mm(1 -h;))= 22inh1shhm
(1- hnn) (nn) 2 + 2/ 1n hnn) + 12n 8, + 12
(91)
Ann
((b1s(1 - hnn) ) himltn) )² + 1 12
(92)
hnn
Therefore,
knanp + (1 - 22 Mein
h7
A A
p
+ Bir
(93)
Mnn
where
B, plin (his(1 mnnn) + 1 + (mii(1 hnn) + (iinhen)
(94)
84
Since hin, Annn p are constants, {A_ (i,m) Piz1 and {B: are order-isomorphic. Furthermore, from (83) we have
B,
A' (1) (p + 1)(1 han)
(95)
Therefore, (A' (2) Vi and {B are also order-isomorphic. The conclusion then follows from the transitivity of order-isomorphism.
B.3 Proof of technical lemma
We will show that when A-( (n) > 0, A.(.). <A-(m) implies A- (1) A A-(n) This guarantees (In, yn) to be the most influential sample since A-(1) S 0 for 2 < i
(1,n]
(n)-
Proof. Plugging in the formulas of A_ A (n),
A-(x), we have
(p
hin Amn
(phin + hmn) > (phin + h11) (1 (1-
phin
A- < Amp {m)
(96)
h1
This is equivalent to
h2
hin (h11 knn))
Nnn + 1 111
p²
hhi + 1 Iynn
> 0.
(97)
hni (1 knn)
Recall from Eq.(6)) that A [1,m] A < A_ (m) is equivalent to hinP + h2a(1 follows that
1nn))) + 113 < 0.
hin (h11 - Nnn)
hrn hin (h1 knn) hm (1 hmn) (1 h11) (1 hmn)
hin h11))
h1 +
+
(1 h11)(1 Innn)
I hnn
(98)
hin
p.
(99)
1111
22

---

Therefore, it suffices to show
h
hin
Nnn + 1- h1
p² +
> 0.
(100)
h11
We now discuss two cases.
Case 1: hin In this case, have p >> ensure Eq. (63). Therefore, Eq. (100) is equivalent to
hin + (Dona( - h1)) 1 p > 0.
(101)
(1 (on1(2mmm))i +hia it suffices to show hin
Plugging in p
(hn(ll (hn(l-han)) han) + hin) (hmn(1 hnd + hin) hîn
(102)
This is true since
(h11(1 hnn) + n2mn) (hnal1 (1 h12) + 11:n)
h1ihtn (1 - h11 hnn) + 12gn (fe11 1 + hnn) + (1i1/nn - k2nn) > 11 (1 h11 hnn) + 12 12 (h11 + hnn) 1
(103)
(104)
Case 2: hin
0. In this case, must have p < 0 ensure Eq. (63). Therefore, Eq. (100) is
equivalent to
hin + (hann1 h12) + h2n)) p < 0.
(105)
Plugging in p h1r(1 Kan +hāa it suffices to show hin
(1an)) + (2im) (hrmn( - hnd + nin) > 1
(106)
which is essentially (102).
Combining the above two cases finishes the proof as desired.
Omitted details from Section
C.1 Empirical justification with synthetic dataset
We first demonstrate our theory of linear regression empirically, Theorem 4.2 in particular, with carefully designed synthetic dataset to create the cancellation phenomenon. Firstly, we random sample f* Rdd and X (R where each entrance is between [-1, 1]. Here, e is the size of two clusters that will happen to create the cancellation lation phenomenon. We then artificially attached an all-one matrix
(2(2-))xd to (the bottom of) X, which corresponds to the farmost features of those two clusters. Then, create the response y R by first calculating the perfect response y" == -X0", and perturb it by adding and subtracting some noise from the two clusters, respectively. In particular, for each i [2 magnitude y where ~ (1, 2²) for some variance o² >> 0. Finally, we note that we create each test data point Fiest E Rd by again sampling each entry uniformly from [-1, 1].
nil, we sample noise e; y Z proportional to its original
Intuitively, this training dataset contains two clusters on the opposite side of the ground truth 0* hence creating the cancellation phenomenon. For demonstration, we choose = 10, 0² 0.2, and 1000 with a cluster size of 50. The results are reported in Figure 5. We see that when < the vanilla greedy and the adaptive greedy algorithm perform similarly. However, when > c, we immediately see clear separation in terms of the performance of the vanilla greedy and the adaptive greedy algorithm, which gives strong evidence that the adaptive greedy can capture the marginal effect after removing the entire cluster.
23

---

Linear Regression with cancellation
0.05
Winning g
0.04
0.6
0.03
0.4
0.02
0.2
0.01
0.00
0.0
10
20
30
40
50
60
70
80
90
100
1
10
20
30
40
50
60
70
80
90100
LAGS
Adaptive
Figure 5: Adaptive Greedy v.s. Greedy Algorithm. Left: Averaged actual effect A_s measures the averaged actual effect induced by the greedy and adaptive greedy algorithms. Right: Winning rate indicates the proportion of instances where one algorithm outperforms the other.
C.2 Details of the datasets
detail two of the UCI datasets we chose our experiments.
Concrete Compressive Strength [Yeh, 2007]: The dataset contains 1030 instances and 8 features.
Waveform Database Generator [Breiman and Stone, 1988]: It contains 5000 instances and 21 features, with three different classes. Since we consider binary classification for logistic regression, we select the first two classes for our experiments, which contain in total 3254 instances.
The UCI datasets licensed under CC-BY 4.0, while the MNIST dataset holds CCBY-SA 3.0 license.
Train/valid/test split. For the first two UCI datasets, we randomly sample 50 data points as the test set and use the remaining for training. For MNIST, to control the scale the experiments, we sample 5000 data points from the train split for training and 50 data points from the test split for testing.
C.3 Details of the MLP training
We consider a simple 2-layer MLP with input size 784 (to match the input size of images from MNIST [LeCun et al., 1998]) and a hidden-size of 128, with ReLU [Agarap, 2018] our activation function. We train the model using Stochastic Gradient Descent (SGD) [Ruder, 2016] till convergence, with learning rate of 0.01 and momentum of 0.9. Empirically, observe that after 30 epochs the model converges, hence for simplicity, we set the default epochs to be 30.
Plyper-parameee selection. The reported hyper- parametsssss above were selected via grid search. We swept across hidden unit number (denoted as "width") E (64, 128], learning rate (denoted as "Ir") E {0.01, 0.05, 0.1, 0.5). momentum (denoted as 3) E [0.9, 0.95), and training epochs (denoted as "epochs")) E (30, 50). For each combination of hyper-parameters, we performed 5-fold cross-validation. We present the comparisons in Table 1, which supported final choice of the hyper-parameters in the main experiments (width = 128, 0.01, B = 0.9, epochs = 30).
C.4 Enhancing computational efficiency for the MIP experiments
As mentioned in Section 5, the adaptive greedy algorithm is time-consuming every of the algorithm requires retraining for x number of ensembles) times only one point selected at each step. In our case, one evaluation requires around 10 many retraining. Hence, we adopt several efficient approximations to mitigate the computational burden.
Firstly, when computing the vanilla individual influence of training data points for converged MLP, we leverage one the most memory and time-efficient approximation algorithms known in literature named EK-FAC [George et al., 2018] to expedite computation. EK-FAC is efficient enough to deal with large language models, which suffices for our purpose. Additionally, we devise the following two strategies reduce the computational cost when being adaptive:

---

Table 1: Cross-validation performance for MLP Model MNIST. Width stands for the width of the hidden layer of the MLP, Ir stands for the learning rate, and 3 stands for the momentum.
width
Ir
g
epochs
Accuracy
width
Ir
8
epochs
Accuracy
64
0.01
0.9
30
91.96%
64
0.1
0.9
30
39.36%
128
0.01
0.9
30
93.44% %
128
0.1
0.9
30
40.08%
64
0.01
0.9
50
92.88%
64
0.1
0.9
50
41.64%
128
0.01
0.9
50
93.40%
128
0.1
0.9
50
45.36%
64
0.01
0.95
30
92.48%
64
0.1
0.95
30
13.48%
128
0.01
0.95
30
93.12%
128
0.1
0.95
30
13.36%
64
0.01
0.95
50
93.48% %
64
0.1
0.95
50
10.8%
128
0.01
0.95
50
94.68 %
128
0.1
0.95
50
15.71%
64
0.05
0.9
30
88.44%
64
0.5
0.9
30
11.68%
128
0.05
0.9
30
87.64%
128
0.5
0.9
30
1 11.68%
64
0.05
0.9
50
86.64%
64
0.5
0.9
50
11.68%
128
0.05
0.9
50
89.60%
128
0.5
0.9
50
11.68%
64
0.05
0.95
30
45.80%
64
0.5
0.95
30
11.04%
128
0.05
0.95
30
41.24%
128
0.5
0.95
30
11.20%
64
0.05
0.95
50
53.32%
0.5
0.95
50
11.20%
128
0.05
0.95
50
54.60%
128
0.5
0.95
50
11.20%
Adaptation with steps: We enhance the adaptive greedy with tunable parameter, step size f, i.e., we select the top l most influential training points into tentative most influential subset S each selection step. The standard adaptive greedy has l 1. In our experiment, we set = 5 in particular.
Warm start: At each step, we need obtain a new model that supposed to be trained without To make the adaptive greedy algorithm more efficient, we obtain a new model by first initializing the model parameters from the previous step (for each seed of the ensemble, respectively), and train without S until convergence. Empirically, we observed that compared to the cold start (which requires 30 epochs to converge), the warm start only requires epochs to converge, significantly reducing the computational time.
C.5 MLP experiments with multiple random seeds
We repeat the MLP experiments using multiple random seeds and report the results in Figure 4. The randomness in the experiments arises from neural network training. In summary, our results are generally consistent and robust across different random seeds. Specifically, the adaptive greedy algorithm consistently outperforms the vanilla greedy algorithm, though there are some fluctuations in the winning rate.
sead-0
Winning S79RSRER
30-
26
ZAHinfuence
Adaptive ZAMinfluence
Figure 6: The MLP experiment under different random seeds (0, 22, 42, 62, 82). We report the actual effect and the winning rate. Results in the main paper in Figure were obtained on seed 0.
25

---

C.6 Computational resource and complexity
We conduct our experiments on Intel (R) (Ro Gold 6338 CPU 2. 00GHz with Nvidia A40 CPU. All experiments except the MLP experiment are efficient due to parallelization and low memory requirements. Specifically, for linear regression, both experiments on synthetic and UCI datasets run under 20 seconds. As for logistic regression, the experiment finishes in 2 minutes.
On the other hand, for the MLP experiments MNIST, step of the adaptive greedy selection algorithm for a test data point on 5000 train data points takes roughly 200 seconds with an average GPU memory usage of 40000MiB. Therefore, can't I afford any parallelization over test points due to the high memory usage. Without parallelization, using the warm start and a step size of = 5, the whole evaluation (5000 train data points, 50 test data points, 50) takes roughly takes 28 hours.
D Omitted details from Section
D.1 Discussion on the quadratic optimization
Recall from Eq. (13) that
Q-s = Teest = N N (Ix [ N (X - -ys)
Σ Nea N rj + iE
Σ(x No x,)00
Σ x,
(107)
ieS
iES
Denote (vi,-.. Un) and B (beg), where bij (Z xx)) Zyyy. Under the second- order approximation, k-MISS can be cast as constrained quadratic optimization problem:
w v + w Bw
(108)
WE (0.1))
s.t.
|wllo S k
D.2 Discussion on the submodular property
From Eq. (107), we have
Q-s = Σ 02 Σ bij:
(109)
:ES
JUES
Note Q-s is submodular
for every St C 82 and index & & St.
Q-(((()) Q-s 2 Q Q-ssu(A) Q-
(110)
Plugging Eq. (109) into Eq. (110,, the submodular property requires that
(b.s + bui) S 0,
(111)
AES
which is equivalent to
bi + big 50. Vi,j E [n].
(112)
Eq. (112) is unlikely to hold especially n large, since requires that the off-diagonal entries of SB == B + BT are all non-positive. For a more rigorous analysis, we focus on the case where the negative residuals re's are i..dd and symmetrically distributed with respect to the origin. Denote 8; sg - α,) for i,j [m]. and the event Eq. (112) as E. Under this probability model, we have
141
Pr(8)= < II Pr(Su4417141 + 8(41))87ss 50)
(113)
f odd
which decays exponentially with n.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly define the scope of both the theoretical and empirical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The limitations are discussed in the last paragraph of Section 6. Our work focuses on analyzing the strengths and weaknesses of existing algorithms in MISS; however, the main limitation that it does not contribute algorithmic development this field.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
27

---

Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Given the theoretical nature of this paper, we have diligently ensured the accuracy of the theorem statements and proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofss can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Our code is
publicly
available at https://githu com/
iafluenntaalSSube/MMMS.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g.. with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers have some path to reproducing verifying the results.
28

---

5. Open access to data and code
Question: Does the paper provide open the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
code Inf IafluentialSubst/MEEE
Justification:
Our
publicly
available
https:///itthub. com/
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co public/ wewgggs/eoddduuieieeeeeee
wwtpommsssinooooooooo wonnolicyyyl for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. httpcc/pppcaacccc htwbbiiggguiees///eeeeeeeeeeieeh https//oooSSuusssiioiieeee wwwaiiissssoooioiioiooiooo onlllicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The details of the experiments are discussed in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: The experiments involve enumerating all subsets with size k, which is too computationally expensive.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
29

---

The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The information the computer resources is reported in Appendix C.6.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https /
Answer: [Yes]
Justification: Every author of this submission has reviewed the code of ethics guidelines and confirms compliance.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Our work is theoretical in nature, and don't see immediate societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
30

---

If the authors NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We properly cite the datasets and include their licenses in Section 5,
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
31

---

If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
32

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "kcq81OaKiS", "reviewer": "Reviewer_btdJ", "summary": "The paper explores the problem of most influential subset selection, that is, selecting a subset of training data points whose removal would change a machine learning model the most. The paper develops further on previous works (most notably of Chatterjee and Hadi, and Kuschnig et al) and shows why the greedy heuristics do not work well in practice. Greedy heuristics operate by computing the influence (e.g., following Koh and Liang) and simply selecting the data points with highest individual influence. The paper shows how indirect interactions can lead to under- and over-estimation of influence. The paper then shows why a specific adaptive method works well in practice. The analysis of the paper is limited to OLS. While the paper does not propose a new influential subset selection algorithm, the analysis conducted in the paper adds important theoretical insights that are likely to be helpful to the research community.", "questions": "1. Section 3.1: To what extent is the finding in Section 3.1 limited to the specific target function used here, that is, the prediction on $x_{test}$? After all, reading the legend in Figure 1, there is not a huge difference on the target function value between points 1 and 8 (0.120 vs. 0.117). More broadly, do we expect the effect of high leverage points to be this large when we take “less noisy” functions like the sign of the prediction on $x_{test}$ or accuracy on the whole test set?\n2. Line 171: About correcting the influence with its corresponding leverage score, how does that process look like precisely?\n3. If the reviewer understood correctly, $\\bar{A_{-S}}$ in Figure 3 shows the actual influence of the two approaches considered. Why not baseline this comparison with the “ground truth influence”, that is, the influence of the actual most influential data points? Clearly, this will ground truth will be very difficult to compute as $k$ increases, but some understanding over smaller values of $k$ might be very helpful for the reader.\n4. The results in Figure 4 are mostly as one would expect. However, in the case of MLP, the gap in $\\bar{A_{-S}}$ and winning rate starts shrinking around $k=50$. Any reason why that might be happening? How robust are the results to different choices of training data random seed?", "limitations": "The paper is generally quite open about the limitations. However, please see the point 3 in weaknesses about the generality of the title.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper does a very good job of setting up the problem and explaining the main results. The formalism is clean and easy to understand and the results are accompanied by intuitive explanations, e.g., in Figure 1.\n2. The key limitation of greedy heuristic methods (considering the full training dataset) is explained quite well in Section 4.\n3. While the paper does not quite add an algorithmic improvement, the theoretical analysis provided is an important building block in developing our understanding of the underlying mechanisms.", "weaknesses": "1. Some of the analysis is limited to simpler models like OLS and takes assumptions like the inevitability of the $N=X^TX$ matrix (which may not be the case in real world datasets). This per se is not a big weakness. However, some discussion here on how we expect these results to behave on real world datasets where $N$ is non-invertible, or on models beyond OLS would be greatly helpful.\n2. The result of theorem 4.2 seems a bit limited and too tailored to the adaptive greedy algorithm. Specifically, given the steps described in line 251, (remove most influential sample, retrain the model, repeat), and the proposition 4.1 (order preservation between two points), it is not immediately clear if/how much the Theorem 4.2 would extend to 3-MISS and beyond.\n3. The title of the paper seems to be quite general and a bit mismatched with the content. While the content shows the weaknesses of existing influence estimation approaches (that too with a OLS model, in a 2-MISS settings and a very specific adaptive algorithm), reading the title feels as if the paper would address a much broader range of models and algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer btdJ for taking the time to review our paper and their constructive feedback. Please find below our point-to-point response.\n\n**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.\n\n**Extension to $k$-MISS.**  \n- 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.\n- 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.\n\n\n**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,\n- 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. \n- 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. \n\nTherefore, 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.\n\n\n**Target functions.**  \n- 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.\n- 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.\n- 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. \n- 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.\n\n\n**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).\n\n**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. \n\nMore 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.\n\nThe 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.  \n\n**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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nbGfmpje1i", "reviewer": "Reviewer_2zFQ", "summary": "The paper explores the challenge of understanding the collective influence of subsets of training data on machine learning models, referred to as the Most Influential Subset Selection (MISS) problem. Traditional influence functions, which focus on individual data points, often miss the more complex interactions within subsets. The authors analyze existing influence-based greedy heuristics, revealing their potential failures, particularly in linear regression, due to errors in the influence function and the non-additive nature of collective influence. They propose an adaptive version of these heuristics, which iteratively updates sample scores to better capture interactions among data points. Their experiments on both synthetic and real-world datasets validate the theoretical findings, demonstrating that the adaptive approach can extend to more complex scenarios like classification tasks and non-linear models.", "questions": "- I understand that re-training was modified for the MLP experiments due to computational constraints, but I'm very curious how doing the full correct version would further improve the results in Figure 4. In particular, given the nature of NNs to overfit, I would suspect that partial re-training would not be enough to fully \"erase\" the influences of deleted points. \n\n- Though the paper focuses on MISS, it would be nice to comment a bit on related problems of dataset selection and coreset selection (which is more of an LISS)\n\n- Figures 1 through 3 should have axes labels. Also, would give more intuition of the examples in the original feature space are also shown.", "limitations": "Satisfactory", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Addresses a timely important problem of how to leverage pointwise influence estimates to remove datapoints (dataset selection is a very important topic imo, and a related work of [1] recently won a best paper at ICLR). Even if some of the results were known in the literature (see weaknesses), the paper provides a clear story and analysis.\n- Exceptional exposition for the most part; very lucid and clear narrative, and addresses both high-level and subtler points (for example, section 6 is a nice discussion of natural follow-up questions)", "weaknesses": "- My main concern is that the results presented in Section 3 are sort of a \"folklore\" in the IF literature (see, e.g., [1] and the references therein). The under-estimation of group effects is also analyzed in earlier work [2], for example.\n\n\n\n[1] https://arxiv.org/abs/2309.14563\n[2] https://arxiv.org/abs/1905.13289", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer 2zFQ for taking the time to review our paper and their constructive feedback. Please find below our point-to-point response.\n\n**Comparison to [1,2].** \n\n- 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).\n- 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.\n- Finally, we have provided a detailed discussion of the theoretical research in MISS in Appendix A.\n\n**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.\n\n**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. \n\n**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. \n\n**References**\n\n[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.\n\n[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).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "25qCamooOJ", "reviewer": "Reviewer_3kwV", "summary": "The authors investigate the Most Influential Subset Selection (MISS) problem, which aims to identify a subset of training samples with the greatest collective influence on machine learning model predictions. \nThey discuss limitations of prevailing approaches in MISS and highlight issues with influence-based greedy heuristics.\nThe paper proposes a new method to greedily select the k most influential samples, utilizing adaptive iterative updates to the importance weight of remaining samples that has not been selected by the greedy procedure.", "questions": "./.", "limitations": "- The authors haven't discussed the implications data sample selection from senstive data:\nIf the data is user-generated, non-private, and sensitive, this procedure might select and flag data records of certain individuals. \n- The experiments are limited and do not showcase practical limitations under different circumstances (see above)", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "- The concept of adaptively updating the influence weight per sample is reasonable.\n- The notion of influence is sensible.\n- The submodularity approach to studying data subset selection is reasonable.\n- The authors discuss the limitations of non-adaptive greedy heuristics for MISS.\n- The paper includes an in-depth example and visualizations of the shortcomings of regular greedy algorithms for MISS problems, clearly demonstrating the problems.\n- The implementation is publicly available.\n- The technical appendix appears to follow a sensible proof strategy; however, I haven't had the chance to formally check the appendix (disclaimer).", "weaknesses": "- By their nature, being greedy procedures that iteratively re-evaluate the influence of each individual sample, the proposed algorithms are too inefficient to be applicable to even moderately sized datasets or datasets where subset selection matters most. Consequently, the authors mostly consider small datasets in their experiments.\n- As reported in D.5, k-MISS-MLP-MNIST took 28 hours, which is quite wasteful.\n- The paper does not formally discuss potential problems and limitations with the applicability of k-MISS in the context of non-linear models; therefore, it remains unclear whether the influence function is truly applicable to non-linear models where samples may have unknown non-linear future influence.\n- The influence of randomness from stochastic gradients and initializations (of the MLP) is not discussed or modeled.\n- The paper does not convincingly demonstrate that the proposed solution has practical relevance. For example, there is no case study that demonstrates the practical usefulness of the reported results.\n- The paper does not convincingly demonstrate that the proposed solution advances our theoretical understanding of MISS.\n- The work lacks contextualization regarding highly related research areas, including Data Subset-Selection, Active Learning, Data Shapley, Importance Sampling, Landmark Selection, and Core-set Selection.\n- The paper does not compare the proposed solution to established baselines and highly related data, such as SELCO [http://proceedings.mlr.press/v139/s21a/s21a.pdf], which employs submodularity-based approximation strategies to jointly estimate coefficients and the most relevant data subset.\n- The paper does not recognize highly influential prior work on Data Subset Selection [http://proceedings.mlr.press/v37/wei15.html].\n- The dataset selection lacks representativeness.\n- The experimental assessment is based on too few datasets (Concrete Compressive Strength, Waveform Database Generator, and MNIST).\n- The test set sizes are very small.\n- It remains unclear how robust the proposed algorithm can deal with variations in hyperparameters.\n- It remains unclear how robust the notion of influence can handle random effects from initialization and gradient batching.\n- The experiment does not report any robustness checks, such as sensitivity analysis or cross-validation.\n- The experiments do not include a comparison with state-of-the-art methods from data subset selection or Data Shapley, which makes it difficult to assess its relative performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n- **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. \n- **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. \n\nBelow is our point-to-point response:\n\n**Efficiency of the adaptive greedy algorithm.**\n- 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.\n- 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. \n- 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.**\n\n**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.\n\n**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”. \n\n**Theoretical understanding.** We do not take such an unjustified claim since our entire work is dedicated to the theoretical understanding of MISS. \n\n**Contextualization.** Please refer to our general response.\n\n**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. \n\n**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. \n\n**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. \n\n**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. \n\n**Experiments.**\n\n- **Dataset.**\n\n  - 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?\n  - 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”. \n\n- **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.  \n\n- **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. \n\n- **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.\n\n\n**References**\n\n[1] Koh, Pang Wei, and Percy Liang. \"Understanding black-box predictions via influence functions.\" International conference on machine learning. PMLR, 2017.\n\n[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).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ckOupNNdGP", "reviewer": "Reviewer_Uyvf", "summary": "The paper presents a theoretical analysis of why existing greedy additive methods fail to solve the most influential subset selection (MISS) problem, which aims to find the subset of training data with the largest collective influence. Greedy additive methods (first assigning individual influence scores, ordering and taking the top-k group for example) assume linearity of collective influence and fail to account for the non-linearity due to interactions between samples of the group. Building on the analysis, the paper proposes an adaptive greedy algorithm where the individual influence scores are dynamically updated to capture interactions among samples and ensure that samples of the subset have consistent influence (sign + order of influence are preserved). This algorithm is demonstrated using synthetic and real-world (MNIST) experiments.", "questions": "The paper was very clear, and I only have a few questions to gain a better understanding of the potential impact: \n- See weaknesses.\n- You mention the second-order group influence functions by Basu et al. (2020) in your discussion as an alternative approach to compute group influence. How does the adaptive greedy approach you suggest compare to the second-order approach by Basu et al. (2020) in terms of computational efficiency (when considering group sizes >2, too)? Is it a faster alternative?\n- While I acknowledge that this is mainly a theory paper, I would like to understand the potential impact better. What would be potential application scenarios for finding the **most** influential subset?", "limitations": "Yes, limitations are discussed in detail in the discussion section.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The paper is very well written.\n- The paper contributes a thorough theoretical analysis of failure modes in existing greedy approaches to solve the most influential subset selection (MISS) problem and therefore shows why these approaches often fail to find meaningful subsets.\n- The problem of subset influence is interesting and increasingly relevant given the increasing scale of datasets. The paper is therefore not only relevant for the area of data influence but also data-centric AI overall.", "weaknesses": "This paper is mainly a theory paper, focusing on the failure modes of influence-based greedy heuristics for most influential subset selection (MISS). The choice of datasets and experiments to run (synthetic data, MNIST on MLPs) fits the scope of the paper. Yet, if I understand correctly, the proposed alternative approach to solve MISS dynamically with the adaptive greedy algorithm is shown for a subset size of 2 and does not scale to larger subset sizes. In Remark 4.3 (line 288), the authors hypothesize that the method would scale to subsets larger than 2 if the found subsets are truly already belonging to the most influential subset. Given the fragility of influence scores (Basu et al., 2021), I doubt that the scenario in the authors' hypothesis is realistic. I am unsure though if I understood the claim in this remark correctly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer Uyvf for taking the time to review our paper and their constructive feedback. Please find below our point-to-point response.\n\n\n**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. \n\nOur 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. \n\n\n**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.\n\nBeyond 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.\n\n\n**Potential application scenarios.** We will take ZAMinfluence [2], one of the most prominent algorithms in MISS, to discuss the broader impact of MISS.\n\nZAMinfluence 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.\n\nZAMinfluence 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. \n\nIn 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.\n\n\n**References**\n\n[1] Giordano, Ryan, Michael I. Jordan, and Tamara Broderick. \"A higher-order swiss army infinitesimal jackknife.\" arXiv preprint arXiv:1907.12116 (2019).\n\n[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).\n\n[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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We express our sincere gratitude to the reviewers for their detailed review. It is encouraging to see that the reviewers acknowledged the significance of the topic of study: “Addresses a timely important problem”, and “The paper is therefore not only relevant for the area of data influence but also data-centric AI overall”. It is also great to hear that our writing was described as “Exceptional exposition for the most part”, “very lucid and clear narrative”, “and “does a very good job of setting up the problem and explaining the main results”. 

The following comment addresses some common questions raised by multiple reviewers. We will attend to specific feedback from the reviewers in our individual responses.

**Related literature.** (Reviewer 2zFQ, 3kwV) 
- We would like to clarify that data selection/coreset selection are distinct research areas compared to most influential subset selection (MISS), despite their similar names. 
  - In terms of *objectives*, data selection aims to identify the most informative training examples for effective learning or estimation, whereas MISS aims to identify a set of training samples that will maximize the alteration of model behaviors. 
  - In terms of *applications*, data selection mostly concerns data efficiency, whereas MISS is typically used for diagnosis (e.g., whether the inferential results based on machine learning models are robust to small variation in data). 
  - In terms of *techniques*, MISS is largely built upon influence functions, whereas data selection is typically centered around sub-sampling. 
- Due to these differences, data selection/coreset selection are usually not mentioned in the literature of influence function/influential subset selection. Nevertheless, we are aware of the inspiring work [1] mentioned by Reviewer 2zFQ, and we have already discussed the broader context of MISS in Appendix A, including a brief discussion of data selection. We will further clarify these differences and move the literature review to the main text in the camera-ready version.
- Finally, Data Shapley and influence functions are two different approaches to modeling the influence of individual training samples. Influence function serves as an approximation of leave-one-out (LOO), whereas Data Shapley satisfies the equitable valuation conditions. Both methods have their own merits and are not directly comparable. 


**Robustness of the MLP experiment.**  (Reviewer btdJ, 3kwV) We appreciate the reviewers’ suggestion on analyzing the robustness of results to randomness in training. We conducted additional experiments using different random seeds, with the results presented in the attached PDF. Concretely, we examined the randomness in both the evaluation step (Fig. 1 left) and the selection step (Fig. 1 middle). In both cases, randomness arises from neural network training — to select the most influential subset, the adaptive greedy algorithm involves repeatedly retraining the MLP after selecting and excluding a new sample; to evaluate a selected subset, we need to train an MLP on the set of training samples excluding the subset. When examining the randomness in the evaluation step, we held the selected subsets fixed (the same ones used to produce Fig. 4 in the submission) and ran the evaluation using a different random seed. When examining the randomness in the selection step, we ran MISS with a different random seed, and then evaluated the newly obtained subsets. The latter scenario involves more randomness. 

In summary, our results are generally consistent and robust across different random seeds. Specifically, the adaptive greedy algorithm consistently outperforms the vanilla greedy algorithm, though there are some fluctuations in the winning rate (e.g., Fig. 1, middle). We believe this is still due to the inherent randomness in model training. However, due to limited time and computational resources, we could only run each experiment once during the rebuttal phase. We will include more results with multiple trials in the revision.

Meta-review: This paper provides a clear contribution to our understanding of most important subset selection (MISS), namely, the failure of the greedy approach in the case of linear regression, and the success of adaptive greedy for 2-MISS.  The paper clearly lays out this thesis and provides good discussion of other works and approaches, such as using submodularity.  The reviewers point out the limited nature of the empirical studies, but when taking the clarity of the exposition into account as well as the strong theoretical results, this paper is a clear contribution.

Pros:
1. Timely paper that is likely to guide future work on MISS
2. Exceptional exposition, which clearly addresses their primary thesis
3. The theoretical analysis is instructive, and builds intuition for solving future problems surrounding MISS

Cons:
1. The limited nature of the empirical study
2. The positive result is limited to 2-MISS and it is unclear if this work is extensible to k-MISS more generally
Decision: Accept (poster)