Research map / Learning theory and algorithms / Prediction and decision losses
Most Influential Subset Selection: Challenges, Promises, and Beyond
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes influence-based greedy heuristics for most influential subset selection (MISS), showing they provably fail in linear regression due to influence-function error and non-additivity, and that an adaptive greedy variant partially fixes this.
Problem
Identifying the training subset whose removal causes the largest change in a target function (MISS); existing influence-based greedy heuristics assume additivity and lack provable guarantees.
Approach
Shows that influence-based greedy heuristics (ZAMinfluence, leverage-adjusted greedy selection) provably fail in linear regression due to under-estimation by influence functions and non-additive amplification/cancellation, and that an adaptive greedy algorithm that iteratively refits and removes the top sample provably solves 2-MISS in a cancellation setting.
Key results
- Theory: ZAMinfluence provably fails to select the most influential single sample in linear regression under a specific label generation process (Theorem 3.1), and LAGS fails for 2-MISS under cancellation and amplification.
- The adaptive greedy algorithm provably solves 2-MISS under the cancellation setup (Theorem 4.2) where vanilla LAGS fails.
- Experiments show the adaptive greedy algorithm outperforms the vanilla greedy algorithm in averaged actual effect and winning rate across all k on Concrete, Waveform logistic regression, and MNIST MLP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use adaptive greedy instead of LAGS | MISS on Concrete Compressive Strength · Concrete Compressive Strength | averaged actual effect | Helped |
| use adaptive greedy instead of LAGS | MISS on Concrete Compressive Strength · Concrete Compressive Strength | winning rate | Helped |
| use adaptive greedy instead of ZAMinfluence | MISS on Waveform Database Generator · Waveform Database Generator | averaged actual effect | Helped |
| use adaptive greedy instead of ZAMinfluence | MISS on Waveform Database Generator · Waveform Database Generator | winning rate | Helped |
| use adaptive greedy instead of ZAMinfluence | MISS on MNIST with a 2-layer MLP · MNIST | averaged actual effect | Helped |
| use adaptive greedy instead of ZAMinfluence | MISS on MNIST with a 2-layer MLP · MNIST | winning rate | Helped |
| increase the selected subset size k | vanilla and adaptive greedy algorithms · real-world experiments across regression and classification tasks | averaged actual effect | Helped |
Surprising findings
- Influence function under-estimates individual effects by a factor 1/(1-h_ii), so it can fail to rank the most influential single sample even in linear regression.
- The value function of the second-order approximation is generally not submodular, suggesting MISS is hard even for approximate solutions.
Limitations
- Theoretical failure and success results are restricted to specific label generation processes and 2-MISS for the adaptive algorithm.
- The paper does not propose an algorithm that improves over existing methods; adaptivity comes with higher computational cost.
- MLP actual effect is approximated via a 5-model ensemble, which is a noisy proxy.
Experimental setup
Datasets: Concrete Compressive Strength Waveform Database Generator MNIST
Benchmarks: Concrete Compressive Strength Waveform Database Generator MNIST
Metrics: averaged actual effect winning rate
Baselines: ZAMinfluence leverage-adjusted greedy selection adaptive greedy algorithm
Builds on: ZAMinfluence influence function data Shapley Linear Datamodeling Score
Closest papers by meaning
- Towards a statistical theory of data selection under weak supervision (ICLR 2024 · similarity 0.87)
- Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond (ICML 2024 · similarity 0.87)
- Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination (ICML 2025 · similarity 0.87)
- A Versatile Influence Function for Data Attribution with Non-Decomposable Loss (ICML 2025 · similarity 0.86)
- SAND: One-Shot Feature Selection with Additive Noise Distortion (ICML 2025 · similarity 0.85)
- The Impact of Coreset Selection on Spurious Correlations and Group Robustness (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.