Most Influential Subset Selection: Challenges, Promises, and Beyond

Authors: yuzheng  hu
pingbang  hu
han  zhao
jiaqi w ma
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-11 08:36:22

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.

Main paper: 
 introduction: 
 Unraveling the intricate connections between data and model predictions is critical in machine learning, particularly in high-stakes decision-making contexts such as healthcare, economics, 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 [Teso et 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 on 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-Ibarra et al., 2018] , and detecting trends and signals that emerge collectively within the data [Yang et al., 2020] . Gaining such insights is crucial for a more comprehensive understanding of model behaviors.In pursuit of advancing this field, in this paper, we 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, it 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, a 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 to incorporate the non-additive structure of the collective influence, can cause these heuristics to fail in MISS even in simple linear regression.• In contrast, we demonstrate the effectiveness of the adaptive greedy algorithm that dynamically updates the score for each remaining sample in response to selections already made. The improvement mainly comes from its ability to 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 to 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 as Linear Datamodeling Score, among others.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 can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
problem statement: 
 Consider a prediction task (e.g., regression or classification) with an input space X ⊂ R d and a target space Y ⊂ R. The prediction task aims to learn a function f (θ, •) : X → Y parameterized by θ ∈ R q . Specifically, denote {(x i , y i )} n i=1 as the training samples and L(•, •) as the loss function (e.g., squared error or cross-entropy), we aim to solve the following optimization problem:θ = arg min θ∈R q 1 n n i=1L(f (θ, x i ), y i ).(1)A key notion for analyzing the influential samples is the optimal model parameters after removing a subset of training samples. Denote 1 n i / ∈S L(f (θ, x i ), y i ).(2)Note that we do not adjust the normalizing constant as it does not affect the optimal solution to Eq.( 2). Finally, denote ϕ : R q → R as the target function, which takes the model parameters as input and returns a quantity of interest (e.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 k-Most Influential Subset Selection (k-MISS) problem refers to this discrete optimization problem:S opt,k = arg max S⊂[n],|S|≤kA -S , where A -S := ϕ( θ-S ) -ϕ( θ).(3)We refer to A -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 to the maximum actual effect. It can be viewed as analogous to adversarial examples [Biggio et al., 2013 , Szegedy et 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 an exponential time complexity in k, rendering it computationally intractable in practice. In fact, even in the context of linear regression, a 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 to select an approximately most influential subset.One of the most prominent algorithms for MISS, ZAMinfluence, was introduced by Broderick et al.[2020] and applied to assess the robustness of inferential results in earlier econometric studies [Attanasio et al., 2015 , Angelucci et al., 2015] . It builds upon the classic influence function [Koh and Liang, 2017] from robust statistics literature [Hampel, 1974 , Hampel et 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 to Section 7. Definition 2.2 (Upweighted objective). We denote the optimal solution to the upweighted objective w.r.t. a set of indices S as θ-S (δ) := arg minEQUATIONIt is straightforward to see that δ = 0 corresponds to θ, while δ = -1 n corresponds to θ-S . Similar 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 θ-S (δ) around δ = 0. This quantity is well-defined when L is strictly convex and can be computed via the Implicit Function Theorem [Krantz and Parks, 2002] . Definition 2.3 (Influence function of a set). The influence of upweighting S on the parameters is:EQUATIONwhereH θ = 1 n n i=1 ∇ 2 θ L(f ( θ, x i ), y i )is the Hessian of the loss function at θ.Using the chain rule and note that θ-S = θ-S (-1 n ), the actual effect can be estimated via the first-order approximation:EQUATIONThe 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) calculatingv i = ∇ θ ϕ( θ) ⊤ H -1 θ ∇ θ L(f ( θ, x i ), y i ) for each i ∈ [n];2) sorting v i 's; 3) returning the top i's with positive v i . In fact, a series of studies in MISS [Wang et al., 2023 , Yang et al., 2023a , Chhabra et al., 2024] follow a 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 influence-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 twice-differentiable objective function [Broderick et al., 2020] to obtain an influential subset w.r.t. any differentiable target function. The second is 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 heuristics is the lack of provable guarantees. It is well-known that even the influence estimates of individual samples can be fragile and erroneous, especially in complex models like neural networks [Basu et al., 2021 , Bae et al., 2022] . A more significant concern lies in the additivity assumption implicitly adopted by these heuristics (also see Guu et al. [2023] for discussions), as it fails to account for the interactions among samples. We critically examine these issues in Section 3.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: 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 is that it does not contribute to algorithmic development in this field.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 are encouraged to create a 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-specification, asymptotic approximations only holding locally). The authors should reflect on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 in solving MISS within the context of linear regression.Setup and notation. In standard linear regression, each x i ∈ R d represents a vector of covariates, and y i stands for a real-valued label. The first coordinate of each x i is set to 1 to account for the intercept term. We stack the row vectors x ⊤ i to form the design matrix X ∈ R n×d and concatenate the y i 's into the target vector y ∈ R n . We assume the labels are generated as follows: there exists a θ * ∈ R d (note q = d), a noise parameter ε > 0 and some p, such thatEQUATIONFor a subset S, X S and y S 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 ⊤ X is invertible, and that n-1 i=2 x i x ⊤ i is also invertible (when this assumption is violated, our results naturally extend to ridge regression). The hat matrix is denoted as H = XN -1 X ⊤ . The diagonal element h ii of H represents the leverage score of x i , and the off-diagonal element h ij represents the cross-leverage score [Chatterjee and Hadi, 2009 ] between x i and x j . The Ordinary Least Squares (OLS) estimator is given byEQUATIONLet ŷi = x ⊤ i θ be the prediction and r i = ŷi -y i be the negative residual for the i-th sample. Throughout Sections 3 and 4, we focus on the linear target function ϕ(θ) = x ⊤ test θ for x test = x1+pxn p+1 , whose first coordinate is also 1. This choice of x test is intentional: it greatly simplifies the analysis by making most of the individual effects negative, as reflected in Figures 1 to 3 and the calculations in Appendix A.1. Furthermore, due to the continuous nature of the problem, our conclusions hold for a set of x test with non-zero Lebesgue measure.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 challenge this viewpoint by pointing out a previously overlooked fact: the influence function fails to incorporate the leverage scores of individual samples in linear regression, which could result in its failure in selecting the most influential sample (i.e., 1-MISS).Plugging the squared loss into Eq.( 5), we have I(S) = -nN -1 i∈S x i r i . Therefore, ZAMinfluence assigns v i = x ⊤ test N -1 x i r i to each sample. We refer to them as influence estimates. On the other hand, it is well-known in the statistics literature [Beckman and Trussell, 1974, Cook, 1977] thatEQUATION)Figure 1 : Influence estimates suffer from disparate levels of under-estimation, leading to the failure of 1-MISS Consequently, the change in the target function is given by A-{i} = x ⊤ test N -1 xiri 1-hii, which deviates from the influence estimate by a factor of 1/(1 -h ii ) and implies underestimation (a phenomenon which was also reported in Koh et al. [2019] ). This is particularly concerning when a sample has a 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 1 : while point 8 ⃝ is scored highest by the influence function, it is however removing point 1 ⃝ (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 ZAMinfluence in 1-MISS, with the proof detailed in Appendix A.2. Theorem 3.1. Assume h 11 > h nn . Under the label generation process described in Eq.( 7), there exists some p, such that ZAMinfluence fails to select the most influential sample.Takeaway: Even when the influence estimates have high correlation with the individual effects, they can be misleading for extreme samples. As a result, the influence function may not be a reliable tool for MISS.Note that the individual effects A -{i} 's can be computed efficiently for linear regression (this is generally infeasible for more complicated tasks) by correcting the influence estimates v i 's with their corresponding leverage scores. Hence, a natural alternative is to directly perform greedy selection based on the A -{i} 's. We refer to this method as Leverage-Adjusted 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 haveEQUATION) Remark 3.3. Denote M S = X S N -1 X ⊤ S . It is straightforward to see that replacing the Neumann series (I k -M S ) -1 = I k + M S + M 2 S + • •• by the identity matrix yields the influence estimates, i.e., the first-order approximation. We further prove in Appendix A.4 that there is a one-to-one correspondence between the Taylor series of θ-S (δ) and the Neumann series: for any k ∈ N + , the k-th order approximation of θ-S (δ) is equivalent to truncating the Neumann series at M k-1 S . On the other hand, LAGS is based on the diagonal approximation of (I k -M S ).To systematically study the failure mode of LAGS, we consider S = {i, j}. In this case,EQUATION)Figure 2 : LAGS fails in 2-MISS due to amplification From Eq. ( 11), we identify two primary factors contributing to the nonadditivity of the group effect: the cross-leverage score h ij in the denominator, which can lead to superadditivity by inflating the sum of individual effects, and the cross terms x ⊤ test N -1 (x i r j + x j r i ) in the numerator, which may result in sub-additivity through the neutralization of individual effects. We refer to these phenomena as 'amplification' 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 of a set substantially exceeds the sum of individual effects. As suggested by Eq.( 11), this phenomenon is pronounced when the cross-leverage score is high. Therefore, we focus on scenarios where there are c ≥ 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 c copies of (x i , y i ). We haveEQUATIONwhere A -{i} c denotes the group effect of removing all c copies of (x i , y i ).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 h ii → 1 c . Put differently, a sample with minor influence can collectively cause a substantial effect when grouped with similar ones. In MISS, this could lead to the failure of LAGS when there is a cluster of samples with high leverage scores yet do not have the largest individual effects. This intuition is illustrated in Figure 2 : while points 7 ⃝ and 8⃝ (the pink cluster) have the highest individual effects due to their large residuals, points 1 ⃝ and 2 ⃝ (the green cluster) with high leverage scores constitute the most influential size-2 subset.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 c copies of (x 1 , y 1 ) and (x n , y n ), and that h 11 > h nn . Under the label generation process described in Eq.( 7), there exists some p, such that LAGS fails in c-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 is equivalent to A -{1,n} < A -{n} (we assume w.l.o.g. that A -{n} > A -{1} ). From Eq. ( 11), this inequality is likely to hold when A -{1} has a small magnitude compared to A -{n} , and the sign of h 1n differs from that of rn r1 . If we further have that A -{1} and A -{n} are the top-2 positive individual effects (which guarantees that they will be selected by the greedy algorithm), then LAGS will fail in this context.We illustrate this in Figure 3 : although points 8⃝ and 1 ⃝ have the top-2 individual effects and are positive, their group effect as a size-2 subset is less than the individual effect of point 8 ⃝.We present a more general result in the following theorem and defer its proof to Appendix A.7. Theorem 3.6. Assume h 1n ̸ = 0. Under the label generation process described in Eq.( 7), there exists some p, such that LAGS fails in 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 fragility. 
promises of the adaptive greedy algorithm: 
 Given the limitations of LAGS, a pertinent question arises: is it possible to capture the non-additive structure of the joint effect without enumerating subsets? In this section, we examine a refined heuristic proposed by Kuschnig et al. [2021] , and provide a 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 or 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 is 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 regression [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 to cancellation, the adaptive greedy algorithm can effectively address this problem by leveraging a scoring function that captures the marginal contributions relative to the removal of the most influential sample.Following the cancellation setup, (x n , y n ) is the most influential sample w.r.t. the full dataset. We denote A ′ -{i} as the actual effect of removing (x i , y i ) for 1 ≤ i ≤ n -1 after the removal of (x n , y n ). 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 ′ -{i} and (A -{i,n} -A -{i} ) have the same sign for 1 ≤ i ≤ n -1; 2. Order preservation: {A ′ -{i} } n-1 i=2 and {A -{i,n} } n-1 i=2 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 to the removal of (x n , y n ). Hence, in the cancellation setup, A ′ will not choose (x 1 , y 1 ), even though A -{1} 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 -{1} , A -{n} > 0, A -{1,n} < A -{n} (indicating cancellation), and that n ∈ S opt,2 (i.e., (x n , y n ) 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 (x n , y n ) is the most influential sample (the proof is deferred to Appendix B.3). This ensures that the adaptive greedy algorithm will select (x n , y n ) in the first step. We now discuss two cases separately.Case 1:If A -{i,n} -A -{n} < 0 for every 2 ≤ i ≤ n -1, then S opt,2 = {n}.Furthermore, by the first property of Proposition 4.1 we have A ′ -{i} < 0 for 1 ≤ i ≤ 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 ≤ i ≤ n -1, such that A -{i,n} -A -{n} > 0. We denote the most influential subset as S opt,2 = {i * , n}. Since A -{i * ,n} -A -{n} > 0, the first property of Proposition 4.1 implies A -{i * } > 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.Takeaway: In essence, the critical limitation of LAGS and other influence-based greedy heuristics is their reliance on a 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 to those in Shapley value [Ghorbani and Zou, 2019] , leading to more effective subset selection. 
experiments: 
 In this section, we empirically evaluate the efficacy of the adaptive greedy algorithm on real-world datasets by comparing the performance of the vanilla greedy algorithm versus the adaptive greedy algorithm across a range of k's. 1 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 a complement. Additional experiments on synthetic datasets can be found in Appendix C.1. Evaluation metrics. We evaluate the algorithms using two metrics, the averaged actual effect and the winning rate. Given a 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 a 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 classification. For the regression task, we adopt the target function ϕ(θ) = x ⊤ test θ on a given test point z := (x test , y test ). We utilize LAGS as the vanilla greedy algorithm. For the classification task, we consider the target function ϕ(θ) = log(p(z; θ)/(1 -p(z; θ))), where p(z; θ) 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 a 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) on 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 is impossible to 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 values from several independently trained models. Specifically, we train 5 models with the same initialization but different seeds. This works for both the greedy algorithm and evaluation: for the former, we estimate each model'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 a subset S by the averaged difference of the target values of each model, trained with or without S.While ensemble solves the non-uniqueness problem, it induces a significant computational burden. Noticeably, the adaptive greedy algorithm now requires retraining for (k × 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 to Appendix C.4.Results. We present the main results in Figure 4 . First, we see that as k increases, the averaged actual effect A -S given by both the vanilla and the adaptive greedy algorithms increase, which aligns with the intuition that removing a 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 non-linear 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.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
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 ∈ S opt,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 see that the adaptive greedy algorithms provably fail in c-MISS since it selects (x n , y n ) in the first place. Second-order approximation. To more effectively capture the amplification effect caused by clusters of similar samples, it is essential to 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:EQUATIONFrom here, the original MISS can be cast as a quadratic optimization problem (see Appendix D.1) and solved via L 1 relaxation and projected gradient descent. Furthermore, we have [1978] states that so long as the (set) value function satisfies the submodular property, the greedy algorithm will return a solution within a factor 1 -1/e 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 a 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.Q -{1} c = c 2 v 1 ∥x 1 ∥ 2 + cv 1 , Q -{n} c = c 2 v n ∥x n ∥ 2 + cv n ,The role of target function. Our negative results critically rely on the choice of x test , underscoring the importance of the target function -an issue that has been overlooked in prior research. In addition, we have identified a few target functions in which the influence-based greedy heuristics fail to provide meaningful results: 1) the change of norm, ϕ 1 (θ) = ∥θ -θ∥ 2 ; 2) the training loss, ϕ 2 (θ) = ∥Xθ -y∥ 2 . In both of these cases, we have ∇ θ ϕ( θ) = 0, implying that the scores assigned to each sample will also be 0.Implication on Linear Datamodeling Score. Recently, Linear Datamodeling Score (LDS) [Park et al., 2023] has emerged as a 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 it 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 in 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 et al., 2020 , Broderick et al., 2020] . 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] 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] , as well as to assess the sensitivity of inferential results in multiple domains such as applied econometrics [Attanasio et al., 2015 , Angelucci et al., 2015] , economics [Finger and Möhring, 2022, Martinez, 2022] , and social science [Eubank and Fresh, 2022] . Additionally, Kuschnig et al. [2021] proposed a refined version of ZAMinfluence based on iteratively refitting the model and removing the most influential sample, an approach which was also explored in Yang et al. [2023a] .Theoretical understanding of MISS. Despite its empirical success, the theoretical understanding of ZAMinfluence and other influence-based 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 α approaches zero. Fisher et al. [2023] extended the analysis to any fixed 0 < α < 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-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 a fine-grained analysis of the common practices in MISS, shedding light on the limitations of influence-based greedy heuristics as well as the potential of the adaptive greedy algorithm. Multiple outlier detection. Classical tools in statistics, such as Cook'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., 2016] . 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 a line of research in regression diagnostics [Fox, 2019] , known as multiple outlier detection. Prominent approaches include clustering [Gray and Ling, 1984, Hadi, 1985] , influence matrix [Peña and Yohai, 1995] , and a class of iterative procedures [Belsley et al., 1980 , Hadi and Simonoff, 1993 , She and Owen, 2011 , 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-independently, 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 Shapley value [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, we emphasize that MISS should not be confused with data selection [John and Draper, 1975, Kolossov et al., 2023] . While many data attribution algorithms can indeed be applied for data selection (e.g., a recent study Wang 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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to 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 a 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, or as supplemental material. 
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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are 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).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: The information on 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 or 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 as 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 or failed experiments that didn't make it into the paper). 
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 as a foundation for future algorithmic advancements.A Omitted details from Section 3 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 not 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 (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 we don't see immediate societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or 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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a 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 to 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model as 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. 
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 as 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 in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as 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. 
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 an equivalent approval/review based on 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 not involve crowdsourcing nor research with human subjects. • Depending on 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS 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. 
 
 Appendix: We start by calculating the OLS estimator, the negative residuals r i 's, the influence estimates v i 's, and the individual effects A -{i} 's. Suppose there are c copies of (x 1 , y 1 ) and (x n , y n ), where c = 1 unless otherwise noted. Under the label generation process in Eq.( 7), we haveEQUATIONTherefore, the negative residuals areEQUATIONandEQUATIONFor x test = x1+pxn p+1 , the influence estimates can be calculated as follows:EQUATIONwhereasEQUATIONFinally, we haveEQUATIONEQUATION)We also discuss a few properties of the hat matrix H. Lemma A.1. The leverage scores satisfy:h 11 < 1 c , h nn < 1 c .Proof. Note the hat matrix is idempotent, i.e., H 2 = H. As a consequence, we haveEQUATIONNote n-1 i=2 x i x ⊤ i is invertible, and that N -1 x 1 is a non-zero vector. As a consequence, we haveEQUATIONwhich further implies that the sequence {h 1i } n-1 i=2 cannot be all zero. Therefore, we have h 11 < 1 c . The same argument applies to h nn .Lemma A.2. The following inequalities hold:EQUATIONProof. Since N is positive definite (PD), P = √ N -1 is well-defined and is invertible. NoteEQUATION)Since h 11 > h nn , we have x 1 ̸ = x n , and therefore x 1 ∖ // x n since their first coordinates are the same. Therefore, Eq.( 24) follows from the Cauchy-Schwarz inequality.For the second inequality, denoteC ⊤ = ( √ cx 1 , √ cx n ) ∈ R d×2. Consider the following matrix:EQUATION)Since the Schur complement ofI 2 : S/I 2 = N -C ⊤ I 2 C = n-1 i=2 x i x ⊤ i ≻ 0,and that I 2 ≻ 0, we have S ≻ 0. This further implies that the Schur complement of N is positive definite, i.e.,EQUATION)As a consequence, we have det(S/N ) = (1-ch 11 )(1 -ch nn ) -c 2 h 2 1n > 0.A.2 Proof of Theorem 3.1Proof of Theorem 3.1. We will show that there exists some p, such thatEQUATIONand that v 1 and v n are positive. Since v i ≤ 0 for 2 ≤ i ≤ n -1, this implies that ZAMinfluence selects (x n , y n ) and fails to find the most influential sample (x 1 , y 1 ). We will discuss three cases.Case 1: h 1n = 0. In this case, both v 1 and v n are positive by Lemma A.1. Furthermore, we haveEQUATION)which is continuous and takes values in [0, ∞). Hence, there exists a p > 0 such that Eq.( 27) holds.Case 2:EQUATIONboth v 1 and v n are positive. Note Eq.( 29) forms a valid interval by the first inequality in Lemma A.2. Now considerEQUATIONwhich is continuous and approaches 0 as p → -h1n hnn and approaches ∞ as p → -h11 h1n . Hence, there exists a p > 0 such that Eq.( 27) holds.EQUATIONboth v 1 and v n 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.Proof of Proposition 3.2. Applying the Woodbury matrix identity, we haveEQUATIONand the actual effect of removing S isEQUATIONA.4 Correspondence between the Neumann series and the Taylor seriesWe will demonstrate that there is a one-to-one correspondence between the Neumann series (I k -M S ) -1 and the Taylor series of θ-S (δ). To see this, considerEQUATIONFrom Petersen et al. [2008] , we haveEQUATIONfor any invertible symmetric matrix K. By induction, we can show that for any i ≥ 1,EQUATIONTherefore, by Taylor expansion, we haveEQUATIONTherefore, truncating at the i-th element in the Neumann series is equivalent to the i th -order Taylor approximation of θ-S (δ). 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.4Proof of Proposition 3.4. Denote θ -{i} c as the optimal model parameters after removing all c copies of (x i , y i ), and z = n j=1 x j y j . Using the Sherman-Morrison formula, we haveEQUATIONConsequently,EQUATION)On the other hand, the influence of removing a single copy isEQUATIONA.6 Proof of Theorem 3.5Proof of Theorem 3.5. It suffices to show that there exists some p, such that A -{1} < A -{n} and A -{1} c > A -{n} c . This further implies that the failure of LAGS. From Proposition 3.4, it suffices to show there exists some p, such thatEQUATION)Note this is a valid interval sinceEQUATIONwhere we use c ≥ 2 and h 11 > h nn in the second inequality. Furthermore, Eq.( 52) is equivalent toEQUATIONwhere we use A -{i} = vi 1-hii . Therefore, we can repeat the analysis in the proof of Theorem 3.1 and conclude the existence of a desired p.Proof of Theorem 3.6. Recall from Eq.( 11) we haveEQUATION)Therefore, A -{1,n} < A -{n} is equivalent toEQUATION)Plugging in the formulas of A -{1} , A -{n} , r 1 , r n , Eq.( 58) is equivalent toEQUATION)Combining like terms, we getEQUATION)This could be simplified toEQUATIONEQUATION)Now it suffices to show there exists a p, such that A -{1} , A -{n} > 0, and that Eq.( 63) holds.Case 1:EQUATIONboth A -{1} and A -{n} are positive. Furthermore, we havelim p→- h 11 h 1n h 1n p + h 11 (1 -h nn ) + h 2 1n = h 2 1n -h 11 h nn < 0 (65)from Lemma A.2. This proves the existence of a desired p.Case 2:EQUATION)both A -{1} and A -{n} are positive. Similarly, we can pick a p that is sufficiently close to -h11 h1n , such that p ̸ = -1 and Eq.( 63) holds.Combining the above two cases finishes the proof as desired.We start by computing the updated OLS estimator, the negative residuals, and the individual effects after removing the sample (x n , y n ). Denote N ′ = n-1 i=1 x i x ⊤ i , the updated OLS estimator is θ′ = (N ′ ) -1 (N ′ θ * -εx 1 ).(67)Therefore, the updated negative residuals areEQUATION)Therefore, we haveh ′ 1i = h 1i + h 1n h in 1 -h nn , h ′ ii = h ii + h 2 in 1 -h nn , x ⊤ i (N ′ ) -1 x n = h in 1 -h nn (69) for 1 ≤ i ≤ n -1.Finally, the adjusted individual effects areEQUATIONandEQUATIONfor 2 ≤ i ≤ n -1.We will also make use of the following lemma.EQUATION)Proof. From Eq.( 11), we haveA -{i,n} = (1 -h ii )(1 -h nn )(A -{i} + A -{n} ) + h in x ⊤ test N -1 (x i r n + x n r i ) (1 -h ii )(1 -h nn ) -h 2 in .(73)Therefore, A -{i,n} < A -{n} is equivalent toEQUATION)Plugging in the formulas of A -{i} , A -{n} , r i , r n , Eq.( 74) is equivalent toEQUATION)Multiplying both side by (1-h nn ), the coefficient of p 2 is -h 2 in (1 -h nn ) 2 + h 2 in h nn (1 -h nn ) + h 2 in (1 -h nn )(1 -2h nn ) = 0; (76) the coefficient of p is -2h 1i h in (1 -h nn ) 2 + h 2 in h 1n (1 -2h nn ) + (1 -h nn )h in h 1i (1 -2h nn ) -2h 1n h in = -h 1i h in (1 -h nn ) -h 2 in h 1n ; (77)and the constant term isEQUATION)Therefore, Eq.( 75) is equivalent toEQUATIONB.2 Proof of Proposition 4.1Proof of sign consistency. For (x 1 , y 1 ), plugging Eq.( 69) into Eq.( 70), we haveEQUATIONwhich aligns with Eq.( 63). Therefore, A -{1,n} < A -{n} ⇐⇒ A ′ -{1} < 0. For (x i , y i ) where 2 ≤ i ≤ n -1, plugging Eq.( 69) into Eq.( 71), we haveEQUATION)This impliesEQUATIONwhich aligns with Eq.( 72) in Lemma B.1. Therefore, A -{i,n} < A -{n} ⇐⇒ A ′ -{i} < 0.Proof of order preservation. Plugging A -{i} , A -{n} into Eq.( 11), we haveEQUATION)DenoteEQUATION)and the constant term isEQUATIONTherefore,EQUATIONwhereEQUATIONSince h 1n , h nn , p are constants, {A -{i,n} } n-1 i=1 and {B i } n-1 i=1 are order-isomorphic. Furthermore, from Eq.( 83) we haveEQUATIONTherefore, {A ′ -{i} } n-1 i=2 and {B i } n-1 i=2 are also order-isomorphic. The conclusion then follows from the transitivity of order-isomorphism.We will show that when A -{1} , A -{n} > 0, A -{1,n} < A -{n} implies A -{1} < A -{n} . This guarantees (x n , y n ) to be the most influential sample since A -{i} ≤ 0 for 2 ≤ i ≤ n -1.Proof. Plugging in the formulas of A -{1} , A -{n} , we haveEQUATIONThis is equivalent toEQUATIONRecall from Eq. (63EQUATIONTherefore, it suffices to showEQUATIONWe now discuss two cases.Case 1: h 1n < 0. In this case, we must have p > 0 to ensure Eq. ( 63). Therefore, Eq. ( 100) is equivalent toEQUATIONPlugging in p = -h11(1-hnn)+h 2 1n h1n, it suffices to showEQUATIONThis is true sinceEQUATIONCase 2: h 1n > 0. In this case, we must have p < 0 to ensure Eq. ( 63). Therefore, Eq. ( 100) is equivalent toEQUATIONPlugging in p = -h11(1-hnn)+h 2 1n h1n, it suffices to showEQUATIONwhich is essentially Eq.( 102).Combining the above two cases finishes the proof as desired.C Omitted details from Section 5We first demonstrate our theory of linear regression empirically, Theorem 4.2 in particular, with a carefully designed synthetic dataset to create the cancellation phenomenon. Firstly, we random sampleθ * ∈ R d and X ∈ R (n-2•c)×d where each entrance is between [-1, 1].Here, c is the size of two clusters that will happen to create the cancellation phenomenon. We then artificially attached an all-one matrix 1 ∈ R (2•c)×d to (the bottom of) X, which corresponds to the farmost features of those two clusters. Then, we create the response y ∈ R n by first calculating the perfect response y * := Xθ * , and perturb it by adding and subtracting some noise ϵ from the two clusters, respectively. In particular, for each i ∈ [2 • c + 1, n], we sample a noise ϵ i ∼ y * i Z proportional to its original magnitude y * i , where Z ∼ N (1, σ 2 ) for some variance σ 2 > 0. Finally, we note that we create each test data point x test ∈ R d by again sampling each entry uniformly from [-1, 1].Intuitively, this training dataset contains two clusters on the opposite side of the ground truth θ * , hence creating the cancellation phenomenon. For demonstration, we choose d = 10, σ 2 = 0.2, and n = 1000 with a cluster size of c = 50. The results are reported in Figure 5 . We see that when k < c, the vanilla greedy and the adaptive greedy algorithm perform similarly. However, when k > c, we immediately see a 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. We detail two of the UCI datasets we chose in 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 two UCI datasets are licensed under CC-BY 4.0, while the MNIST dataset holds a CC BY-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 of the experiments, we sample 5000 data points from the train split for training and 50 data points from the test split for testing.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] as our activation function. We train the model using Stochastic Gradient Descent (SGD) [Ruder, 2016] till convergence, with a learning rate of 0.01 and momentum of 0.9. Empirically, we observe that after 30 epochs the model converges, hence for simplicity, we set the default epochs to be 30.Hyper-parameter selection. The reported hyper-parameters above were selected via grid search. We swept across hidden unit number (denoted as "width") ∈ {64, 128}, learning rate (denoted as "lr") ∈ {0.01, 0.05, 0.1, 0.5}, momentum (denoted as β) ∈ {0.9, 0.95}, and training epochs (denoted as "epochs") ∈ {30, 50}. For each combination of hyper-parameters, we performed 5-fold cross-validation. We present the comparisons in Table 1 , which supported our final choice of the hyper-parameters in the main experiments (width = 128, lr = 0.01, β = 0.9, epochs = 30).As mentioned in Section 5, the adaptive greedy algorithm is time-consuming as every run of the algorithm requires retraining for (k × number of ensembles) times if only one point is selected at each step. In our case, one evaluation requires around 10 4 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 a converged MLP, we leverage one of the most memory and time-efficient approximation algorithms known in the literature named EK-FAC [George et al., 2018] to expedite computation. EK-FAC is efficient enoughWe conduct our experiments on Intel(R) Xeon(R) Gold 6338 CPU @ 2.00GHz with Nvidia A40 GPU. 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 on MNIST, one 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, we can't 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, k = 50) takes roughly takes 28 hours.D Omitted details from Section 6 D.1 Discussion on the quadratic optimization Recall from Eq.( 13) thatEQUATION) Denote v = (v 1 , • • • , v n ) ⊤ and B = (b ij ), where b ij = (x ⊤ test N -1 x i )x ⊤ i x j r j .Under the secondorder approximation, k-MISS can be cast as a constrained quadratic optimization problem:max w∈{0,1} n w ⊤ v + w ⊤ Bw (108) s.t. ∥w∥ 0 ≤ k D.2 Discussion on the submodular property From Eq.( 107), we haveEQUATIONNote Q -S is submodular ⇐⇒ for every S 1 ⊂ S 2 and index k / ∈ S 1 ,EQUATIONPlugging Eq.( 109) into Eq.( 110), the submodular property requires thatEQUATIONwhich is equivalent tob ij + b ji ≤ 0, ∀i, j ∈ [n].(112) Eq. ( 112) is unlikely to hold especially if n is large, since it requires that the off-diagonal entries of S B := B + B ⊤ are all non-positive. For a more rigorous analysis, we focus on the case where the negative residuals r i 's are i.i.d. and symmetrically distributed with respect to the origin. Denotes ij = sgn(x ⊤ test N -1 x i x ⊤ i x j ) for i, j ∈ [n], and the event in Eq. ( 112) as E. Under this probability model, we haveEQUATIONwhich decays exponentially with n.NeurIPS Paper ChecklistOur code is publicly available at https://github.com/sleepymalc/MISS. 


Decision: 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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.
questions: 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?
2. Line 171: About correcting the influence with its corresponding leverage score, how does that process look like precisely?
3. 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.
4. 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: limitations: The paper is generally quite open about the limitations. However, please see the point 3 in weaknesses about the generality of the title.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.



[1] https://arxiv.org/abs/2309.14563
[2] https://arxiv.org/abs/1905.13289
questions: 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. 

- 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)

- 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: limitations: Satisfactory
paper_summary: paper_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. 
They discuss limitations of prevailing approaches in MISS and highlight issues with influence-based greedy heuristics.
The 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.
strength_weakness: strength_weakness: - 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.
- As reported in D.5, k-MISS-MLP-MNIST took 28 hours, which is quite wasteful.
- 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.
- The influence of randomness from stochastic gradients and initializations (of the MLP) is not discussed or modeled.
- 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.
- The paper does not convincingly demonstrate that the proposed solution advances our theoretical understanding of MISS.
- 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.
- 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.
- The paper does not recognize highly influential prior work on Data Subset Selection [http://proceedings.mlr.press/v37/wei15.html].
- The dataset selection lacks representativeness.
- The experimental assessment is based on too few datasets (Concrete Compressive Strength, Waveform Database Generator, and MNIST).
- The test set sizes are very small.
- It remains unclear how robust the proposed algorithm can deal with variations in hyperparameters.
- It remains unclear how robust the notion of influence can handle random effects from initialization and gradient batching.
- The experiment does not report any robustness checks, such as sensitivity analysis or cross-validation.
- 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.
questions: questions: ./.
limitations: limitations: - The authors haven't discussed the implications data sample selection from senstive data:
If the data is user-generated, non-private, and sensitive, this procedure might select and flag data records of certain individuals. 
- The experiments are limited and do not showcase practical limitations under different circumstances (see above)
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: The paper was very clear, and I only have a few questions to gain a better understanding of the potential impact: 
- See weaknesses.
- 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?
- 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: limitations: Yes, limitations are discussed in detail in the discussion section.

Comments: title: Raising my score
comment: Thank you for the detailed response. Most of my concerns were addressed and I am raising my score to accept. It would be great to add the additional discussion here on target functions and robustness to the final version of the paper.
Thank you again for reviewing and acknowledging our work!
Thank you for the detailed response. 

I appreciate the author's suggestion to clarify that their presented method addresses the 2-MISS problem and offers a starting point for the solution for the more general k-MISS problem and believe it will be useful for readers to assess the scope of the paper. 

My main concern was the potential application impact of this work, where the author's response convinced me of practical scenarios. Hence, I raise my score from 6 -> 7.