Source-linked AI summary
Most Influential Subset Selection: Challenges, Promises, and Beyond
Yuzheng Hu, Pingbang Hu, Han Zhao, Jiaqi W. Ma
TL;DR
The paper asks how to attribute model behavior to groups of training samples when individual influence functions miss collective effects. It analyzes MISS algorithms and shows that static influence-based heuristics can fail, whereas adaptive updating captures sample interactions more effectively across increasingly complex settings.
Problem
Individual influence functions often fail to capture the complex collective influence of training-sample subsets on model behavior.
Source: §1 · p. 1, §2.1 · p. 3Method
Results
Takeaways & Limitations
Adaptivity can capture interactions among samples and partially address the limitations of static additive influence estimates.
Source: §1 · p. 2, §4 · p. 7MISS is computationally constrained because exhaustive subset enumeration is exponential in k, and cancellation results are restricted to 2-MISS.
Source: §2.1 · p. 3, §4 · p. 7
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies MISS, which seeks subsets whose removal most strongly changes a target function, extending influence analysis from individual samples to collective effects. It analyzes existing heuristics, their failure modes, adaptive alternatives, and broader implications.
1 Introduction
- Individual-sample influence is insufficient for analyzing group biases, credit allocation, and trends that emerge collectively within data.Source: §1 · p. 1
- MISS identifies a bounded-size subset whose removal produces the greatest collective change in a target function.It measures worst-case collective influence rather than only individual-sample effects.Source: §1 · p. 2
- Influence-based greedy heuristics can fail even in linear regression because influence estimates may be erroneous and collective influence may be non-additive.The paper also compares these methods with concurrent work on equivalent influence-perturbation formulations.Source: §1 · p. 2
- Adaptive greedy selection addresses sample interactions by iteratively updating scores after previous selections.Experiments extend the benefits of adaptivity to classification and nonlinear neural networks.Source: §1 · p. 2
- The paper discusses performance–efficiency trade-offs and questions additive metrics such as the Linear Datamodeling Score.Source: §1 · p. 2
2 Preliminaries
MISS selects a small subset of training samples whose removal maximizes a target-function change, but exhaustive search is intractable. Influence-based greedy heuristics offer efficient approximations, yet their additive assumptions and fragile estimates limit reliability.
2.1 Problem statement
- MISS seeks a subset of at most k samples whose removal maximizes the actual effect on a target function.The actual effect is defined as the difference between the target after retraining without the subset and the original target.Source: §2.1 · pp. 2–3
- Exhaustively enumerating subsets is exponential in k, and a related robust-regression variant is NP-hard even for linear regression.Source: §2.1 · p. 3
2.2 Influence-based greedy heuristics
- Influence-based greedy heuristics approximate group effects by assigning static individual scores, sorting them, and selecting the highest positive scores.Their broad applicability and linear to log-linear execution cost make them computationally attractive.Source: §2.2 · p. 3
- These heuristics lack provable guarantees because individual influence estimates can be fragile and their additive assumption ignores interactions among samples.Source: §2.2 · pp. 3–4
3 Pitfalls of greedy heuristics in Most Influential Subset Selection
The analysis shows that influence-based greedy heuristics can fail in linear-regression MISS because individual influence estimates may be inaccurate and collective effects may be non-additive. These failures arise through leverage-driven under-estimation, amplification, and cancellation.
3 Pitfalls of greedy heuristics in Most Influential Subset Selection
- Influence-based greedy heuristics can fail in MISS even in linear regression because they use inaccurate individual estimates and cannot represent non-additive collective effects.The section studies these failure modes through linear-regression analysis and closed-form group effects.Source: §3.1 · p. 4, §3.2 · p. 5
3.1 Influence function is not accurate (even) in linear models
- Influence functions omit leverage-score corrections, so they can under-estimate high-leverage samples and select the wrong sample in 1-MISS.The discrepancy scales by 1/(1 − h_ii), and a theorem establishes failure under suitable conditions.Source: §3.1 · pp. 4–5, Figure 1 · p. 4
3.2 Violation of the additivity assumption: amplification and cancellation
- LAGS corrects individual influence estimates with leverage scores, but its one-pass selection still assumes that collective influence is additive.Thus, perfect individual-effect estimation does not guarantee correct subset selection.Source: §3.2 · p. 5
- High cross-leverage can amplify group effects beyond the sum of individual effects, allowing low-individual-influence clusters to form the most influential subset.The ratio between group and summed individual effects can become unbounded as h_ii approaches 1, and LAGS can fail for replicated samples.Source: §3.2 · pp. 5–6, Figure 2 · p. 6
- Cross terms can cause cancellation, making a group effect smaller than one member’s individual effect even when the members have the top individual effects.LAGS therefore can fail in 2-MISS under a single non-zero cross-leverage score.Source: §3.2 · p. 6, Figure 3 · p. 6
- LAGS is provably correct when all cross-leverage scores are zero, but even one non-zero cross-leverage score can make it fail.This identifies cross-sample interaction as the key boundary between additive and non-additive behavior.Source: §3.2 · pp. 5–6
4 Promises of the adaptive greedy algorithm
Adaptive greedy selection recalculates sample effects after each removal, capturing interactions that one-pass heuristics miss. Theoretical results show when this adaptivity succeeds, while also identifying conditions under which it fails.
Adaptive greedy algorithm
- Adaptive greedy repeatedly refits the model, recalculates effects for remaining samples, removes the most influential sample, and continues until the target subset size is reached.Source: §4 · p. 7
- In cancellation settings, adaptive scoring captures each sample’s marginal contribution after removing the first sample, rather than measuring contributions only against the full dataset.Source: §4 · p. 7
- The adaptive score is sign-consistent with marginal effects and preserves their ordering, supporting more reliable subsequent selections.Source: §4 · p. 7
Theoretical guarantees
- Under cancellation assumptions and n ∈Sopt,2, Theorem 4.2 proves that adaptive greedy solves 2-MISS.Source: §4 · p. 7
Implications
- The paper argues that adaptive greedy is more effective than one-pass heuristics because it accounts for interactions among selected and remaining samples, akin to data Shapley [Ghorbani and Zou, 2019].Source: §4 · p. 7
5 Experiments
Experiments compare vanilla and adaptive greedy selection across regression, classification, and neural-network settings using averaged actual effect and winning rate. Adaptive greedy consistently outperforms vanilla greedy across all tested scenarios and subset sizes.
Experimental setup
- The experiments cover linear regression, logistic-regression classification, and MNIST classification with a two-layer MLP.Source: §5 · p. 8
Evaluation metrics
- Averaged actual effect measures mean influence across held-out test points, while winning rate measures how often one algorithm achieves greater actual effect than the other.Source: §5 · p. 8, Figure 4 · p. 8
Experimental setup
- For neural networks, ensembles of five independently seeded models approximate actual effects and influence estimates because the optimal model is generally non-unique.Source: §5 · p. 8
Computational considerations
- Adaptive greedy requires retraining k times per ensemble, creating substantial computational burden that the implementation mitigates with approximate influence estimation.Source: §5 · p. 8
Results
- Adaptive greedy surpasses vanilla greedy across all scenarios and k values under both averaged actual effect and winning rate.Source: Figure 4 · p. 8, §5 · p. 9
- Increasing k raises the averaged actual effect for both algorithms, and repeated MLP experiments remain consistent across random seeds.Source: §5 · p. 9
6 Discussion
The discussion extends the analysis beyond adaptive greedy’s promises to approximation, target-function dependence, evaluation metrics, and computational limits. It argues that MISS remains difficult and that better methods must account for non-additive influence and problem characteristics.
Failure of the adaptive greedy algorithm
- Adaptive greedy itself is not universally reliable: its success requires the optimal subset to contain the initially selected most influential sample.Source: §6 · p. 9
Second-order approximation
- Second-order approximations can capture joint effects amplified by leverage scores by emphasizing sample norms, but the resulting quadratic formulation requires optimization methods such as L1 relaxation and projected gradient descent.Source: §6 · p. 9
Submodular property
- The second-order value function is generally non-submodular, suggesting that MISS remains hard even when approximate solutions are permitted.Source: §6 · p. 9
Role of target function
- Influence-based greedy heuristics can become meaningless for target functions such as parameter-norm change or training loss because their gradients at the optimum are zero.Source: §6 · p. 9
Linear Datamodeling Score
- The paper questions whether higher Linear Datamodeling Score reflects better attribution or merely alignment with an additive assumption that may fail for contextual, non-additive influence.Source: §6 · p. 9
Limitation and future direction
- The study does not provide algorithmic improvements and hypothesizes an inherent trade-off between performance and computational efficiency.Source: §6 · p. 9
7 Related work
Related work places MISS within data attribution, influential-subset selection, regression diagnostics, and theoretical analyses of influence heuristics. The paper distinguishes its fine-grained treatment of heuristic failures and adaptivity from prior empirical and specialized results.
(Most) influential subset
- ZAMinfluence greedily selects approximately influential subsets and has been applied to pre-training, dataset pruning, trustworthiness, and inferential sensitivity.Source: §7 · p. 10
Theoretical understanding of MISS
- Prior theory provides finite-sample error or stability guarantees, but existing results are limited by vanishing removal fractions, indirect consistency notions, or highly specific settings.Source: §7 · p. 10
- The paper positions itself as the first fine-grained analysis of common MISS practices, emphasizing limitations of influence-based greedy heuristics and the potential of adaptive greedy.Source: §7 · p. 10
Multiple outlier detection
- Multiple-outlier detection uses related iterative procedures, but defines outliers context-independently rather than relative to a specific quantity of interest.Source: §7 · p. 10
Broader context
- MISS differs from data selection because it seeks maximally influential removals, whereas data selection typically subsamples data for efficient learning or estimation.Source: §7 · p. 10
8 Conclusion
The conclusion frames the paper as a comprehensive study of MISS heuristics, emphasizing their failure modes and the benefits of adaptivity. The appendix develops OLS preparation results using residuals, influence estimates, leverage scores, and hat-matrix properties.
8 Conclusion
- The study analyzes common MISS practices, exposing failures of influence-based greedy heuristics and benefits of adaptive methods.The authors position these findings as a foundation for improving transparency, interpretability, and future MISS algorithms.Source: §8 · p. 10
A.1 Preparation work
- The OLS preparation derives negative residuals, influence estimates, and individual removal effects under a data-generation process with repeated endpoint samples.The setup also introduces the OLS hat matrix and its leverage-related properties.Source: §A.1 · p. 16
- The appendix establishes leverage-score inequalities using hat-matrix idempotence, invertibility conditions, and positive-definiteness arguments.These steps support later comparisons involving endpoint leverage and cross-leverage quantities.Source: §A.1 · pp. 16–17
A.2 Proof of Theorem 3.1
These appendices prove failures of influence-based selection and relate exact subset-removal effects to successive approximation terms. They also show that higher-order approximations improve leverage information while increasing computational cost.
A.2 Proof of Theorem 3.1
- The proof constructs a regime where ZAMinfluence selects (x_n, y_n) even though (x_1, y_1) is the most influential sample.The argument establishes positive influence estimates for the two endpoint samples while intermediate samples have nonpositive estimates.Source: §A.2 · p. 17
A.3 Proof of Proposition 3.2
- The actual effect of removing a subset is expanded through a Neumann series, connecting exact retraining behavior with higher-order interaction terms.The supplied proof uses the Woodbury identity and a Taylor expansion to establish this correspondence.Source: §A.3 · pp. 17–18, §A.4 · p. 18
A.4 Correspondence between the Neumann series and the Taylor series
- Truncating the Neumann series at order i equals an i-th-order Taylor approximation; first order ignores leverage, whereas higher orders improve accuracy at greater computational cost.This identifies a direct accuracy–efficiency trade-off in approximating subset-removal effects.Source: §A.4 · p. 18
A.6 Proof of Theorem 3.5
- Theorem 3.5 reduces LAGS failure to a regime where single-sample and repeated-copy effects reverse their ordering.The proof uses the relationship A−{i} = v_i/(1−h_ii) to connect individual influence quantities with actual effects.Source: §A.6 · p. 19
A.7 Proof of Theorem 3.6
The appendix proves additional OLS comparisons by analyzing endpoint effects, updated estimators, residuals, and sign consistency. Its technical preparation supplies the inequalities needed for the stated cases.
A.7 Proof of Theorem 3.6
- Theorem 3.6 is completed by treating the cases h_1n < 0 and h_1n > 0 and showing existence of a parameter p satisfying the required effect conditions.The proof ensures both endpoint effects are positive in the relevant construction.Source: §A.7 · pp. 19–20
B.1 Preparation work
- Removing (x_n, y_n) yields updated OLS estimators and residuals, while Lemma B.1 characterizes when removing another sample decreases the corresponding subset effect.The preparation reduces these comparisons to inequalities involving leverage and cross-leverage terms.Source: §B.1 · pp. 20–21
B.2 Proof of Proposition 4.1
- The sign-consistency proof compares endpoint and interior samples through polynomial coefficients and order-isomorphism arguments.These calculations establish the ordering needed for Proposition 4.1.Source: §B.2 · pp. 21–22
B.3 Proof of a technical lemma
The technical lemma shows that a two-sample subset comparison implies an ordering between the corresponding individual effects under separate sign cases.
B.3 Proof of a technical lemma
- When A−{1}, A−{n} > 0, the condition A−{1,n} < A−{n} implies A−{1} < A−{n}.This guarantees (x_n, y_n) is most influential when intermediate individual effects are nonpositive.Source: §B.3 · p. 22
- The proof handles h_1n < 0 and h_1n > 0 separately, selecting the corresponding sign of p to preserve the required inequality.Both cases are reduced to algebraic inequalities involving endpoint leverage and cross-leverage terms.Source: §B.3 · pp. 22–23
C.1 Empirical justification with synthetic dataset
The synthetic experiment shows adaptive greedy separates from vanilla greedy after selections exceed the cancellation-cluster size, while broader experiments examine datasets, training choices, efficiency, and seed robustness.
C.1 Empirical justification with synthetic dataset
- The synthetic dataset creates cancellation through two clusters with opposite perturbations around the ground truth, providing an empirical test of Theorem 4.2.The construction appends two all-one clusters and perturbs their responses with opposite noise.Source: §C.1 · p. 23
- When k > c, adaptive greedy clearly outperforms vanilla greedy, indicating that it captures marginal effects after removing an entire cluster.For k < c, the two methods perform similarly; the synthetic setup uses d = 10, σ2 = 0.2, n = 1000, and c = 50.Source: §C.1 · p. 23, Figure 5 · p. 24
C.2 Details of the datasets
- The UCI experiments use Concrete Compressive Strength with 1030 instances and 8 features, and a binary Waveform subset with 3254 instances and 21 features.The first two UCI datasets use 50 randomly sampled test points, with the remainder used for training.Source: §C.2 · p. 24
C.3 Details of the MLP training
- The MLP uses a 2-layer ReLU network with width 128, SGD, learning rate 0.01, momentum 0.9, and 30 training epochs selected through grid-search cross-validation.The tested hyperparameter combinations covered widths, learning rates, momentum values, and epoch counts.Source: §C.3 · p. 24, Table 1 · p. 25
C.4 Enhancing computational efficiency for the MLP experiments
- Adaptive MLP selection is accelerated with EK-FAC, step size ℓ = 5, and warm starts that reduce convergence from 30 to 8 epochs.Adaptive selection otherwise requires repeated retraining, motivating these approximations.Source: §C.4 · pp. 24–25
C.5 MLP experiments with multiple random seeds
- Across random seeds, adaptive greedy consistently outperforms vanilla greedy, but the MLP evaluation remains costly, taking roughly 28 hours for the reported configuration.One adaptive step takes about 200 seconds and uses approximately 40000MiB of GPU memory.Source: §C.5 · p. 25, Figure 6 · p. 25, §C.6 · p. 26
D.2 Discussion on the submodular property
The submodularity discussion shows that the required sign condition on quadratic cross-terms is unlikely in large problems, while the checklist documents theoretical, experimental, and reproducibility boundaries.
D.2 Discussion on the submodular property
- The submodular condition requires bij + bji ≤ 0 for every pair, meaning all off-diagonal entries of SB = B + B⊤ must be non-positive.Under the stated symmetric residual model, the probability of this event decays exponentially with n.Source: §D.2 · p. 26
NeurIPS Paper Checklist
- The paper identifies its main limitation as analyzing existing MISS algorithms without contributing a new algorithmic method.The limitations are discussed in the last paragraph of Section 6.Source: NeurIPS Paper Checklist · p. 27
- The paper provides complete theoretical-result assumptions and proofs, with the authors stating that theorem statements and proofs were checked for accuracy.The checklist says the theoretical nature of the work motivated diligence about theorem statements and proofs.Source: NeurIPS Paper Checklist · p. 28
- The authors state that code is publicly available and that experimental details are provided in Appendix C, including training settings and computational resources.The checklist also identifies Appendix C.6 as the location of resource information.Source: NeurIPS Paper Checklist · pp. 28–30
- The experiments do not report conventional statistical significance information because enumerating all subsets of size k is computationally expensive.This limitation is explicitly given as the justification for the checklist response.Source: NeurIPS Paper Checklist · p. 29