Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
47,834 characters · 27 sections · 29 citation commands
Finding Most Influential Sets
\twocolumn[ \icmltitle{Finding Most Influential Sets} \icmlsetsymbol{equal}{*}
\icmlaffiliation{wu}{Vienna University of Economics and Business, Austria} \icmlaffiliation{monash}{Monash University, Australia}
\icmlcorrespondingauthor{Nikolas Kuschnig}{[email removed]}
\icmlkeywords{ attribution, least squares, optimization, compression, robustness auditing, algorithmic fairness, causal inference, econometrics, tatistics, machine learning }
\vskip 0.3in ]
\printAffiliationsAndNotice{\icmlEqualContribution}
Most influential sets (MIS) are subsets of the training data whose removal induces the largest change in a target quantity of interest, such as a regression coefficient, treatment effect, or prediction. Formally, for a target functional $\phi$ and a leave-set-out estimator, the size-$k$ MIS, ${\mathbb{S}}_k^{\max}$, maximizes the leave-set-out discrepancy over all subsets ${\mathbb{S}}$ with $\lvert {\mathbb{S}} \rvert = k.$ Set influence differs qualitatively from singleton influence because observations interact; some points reinforce each other, while others mask each others' effects. MIS therefore help diagnose which subsamples drive inferences and how models amplify or suppress particular groups.
In applied work, MIS provide target-specific diagnostics for interpretability, accountability, fairness, robustness, and data curation barocas2020fairness, chhabra_what_2023, ghorbani_data_2019, rudin_stop_2019, hudgens2008toward, souly2025, cote2024data, mirzasoleiman2020coresets.
Despite their relevance, the study of MIS has historically been constrained by computation. Exact identification requires maximizing over $\binom{n}{k}$ subsets, which is computationally infeasible, even for moderate datasets. Classical influence diagnostics focus on individual data points cook1979Influential, and practical extensions to sets are largely insensitive to higher-order interactions chatterjee_influential_1986. Consequently, the literature has often favored robust estimation --- controlling rather than identifying worst-case sensitivity huber2009robust.
Recent work on influence functions --- infinitesimal approximations that are widely used as diagnostic tools hampel_influence_1974, koh_understanding_2017 --- has renewed interest in MIS. This has yielded influence-function-based approximations broderick_automatic_2021, greedy heuristics and failure modes hu2024Most, huang_approximations_2025, kuschnig_hidden_2021, influence bounds moitra_provably_2023, freund_towards_2023, rubinstein_robustness_2024, and formal tests for excessive influence konrad_testing_2025. However, influence functions remain inaccurate for extreme influence and for sets of data points basu_second-order_2020, koh_accuracy_2019, and efficient and accurate methods for MIS selection have remained unavailable.
In this paper, we develop an efficient algorithm for size-$k$ MIS selection for influence targets whose leave-set-out effects admit a ratio representation. The key is that these effects can be written as linear-fractional functions of the removed set, transforming the combinatorial search into a one-dimensional parametric optimization problem. Using dinkelbach1967's method, each subproblem reduces to selecting the top-$k$ scores, giving $\mathcal{O}(n)$ cost per iteration and finite termination. For fixed residualized inputs, the algorithm returns a globally optimal set for the corresponding univariate ratio objective. In partial linear models, this gives exact oracle MIS selection when the nuisance functions are known. With estimated nuisance functions, Neyman orthogonality supports first-stage stability; a separation condition yields consistent selection of the oracle MIS.
We make four contributions.
The remainder of this paper is organized as follows. (ref) introduces the partial linear setting and formalizes the MIS problem. (ref) develops the linear-fractional reduction, presents the algorithm, and states the theoretical guarantees. (ref) evaluates the method in simulations and applications. (ref) discusses relevance, limitations, and implications, and (ref) concludes.\footnote{ The Appendix contains proofs and additional details; code is provided at \url{https://github.com/nk027/findingMIS}. }
We study influential sets using residualization in partial linear models chernozhukov2018, robinson1988root. This section introduces the model and estimator, then formalizes influence and $k$-most influential sets.
Consider the PLM
where $(y_i, x_i, Z_i)_{i=1}^n$ are i.i.d.\ draws from $P,$ $x_i\in\mathbb{R}$ is the treatment, $\beta_0 \in \mathbb{R}$ is the parameter of interest, and $g_0 : \mathbb{R}^d \to \mathbb{R}$ is an unknown nuisance function of covariates $Z_i \in \mathbb{R}^d$. Assume $\mathbb{E}[u_i^2 \!\mid\! Z_i] = \sigma^2(Z_i) < \infty.$
Let $h_0(Z_i) \coloneqq \mathbb{E}[ x_i \!\mid\! Z_i ],$ write \( x_i = h_0(Z_i) + v_i, \) and define $m_0(Z_i) \coloneqq \mathbb{E}[y_i\!\mid\! Z_i] = g_0(Z_i) + \beta_0 h_0(Z_i).$
We estimate $\beta_0$ using residualized outcomes and treatments:
where $(\hat m, \hat h)$ are flexible cross-fitting first-stage estimators. The residualized (Robinson) second-stage estimator is the ordinary least squares (OLS) coefficient from regressing $\tilde y_i$ on $\tilde x_i,$
This estimator exists when $\sum_{i=1}^n \tilde x_i^2 > 0;$ otherwise a ridge-stabilized version can be used.
Let $[n]\coloneqq \{1, \dots, n\}$. For any index set ${\mathbb{S}} \subseteq [n]$, let $\hat\beta_{-{\mathbb{S}}}$ denote the residualized estimator after dropping ${\mathbb{S}}$ from the second stage and recomputing on $[n] \setminus {\mathbb{S}}.$
The target functional determines the direction and scale of change. We focus on signed affine targets, $\phi(\beta) = a \beta + b$. Because $b$ cancels and non-zero $a$ only rescales, and possibly reverses, the ordering of sets, we set $a = 1$ in the exposition. Targets with $a<0$ correspond to directed decreases, while predicted-value targets at treatment level $x_0$ correspond to $a = x_0.$
The influence of ${\mathbb{S}}$ on $\hat \beta$ in (ref) admits a ratio form.
This is an exact finite-sample deletion identity, and not an infinitesimal influence-function approximation. It separates two mechanisms; the numerator \[ W({\mathbb{S}}) \coloneqq \sum_{s\in{\mathbb{S}}}\tilde x_s\tilde r_s \] is the score removed from the full-sample normal equation, while the denominator \[ G({\mathbb{S}}) \coloneqq \sum_{i\notin{\mathbb{S}}}\tilde x_i^2 \] is the residual curvature that remains after removal. Thus, a set can be influential either because it removes observations with large aligned scores, or because it removes high-curvature observations that amplify the effect of the remaining score imbalance.
Although $W({\mathbb{S}})$ and $G({\mathbb{S}})$ are additive separately, their ratio is not. For $i \notin {\mathbb{S}}$, \[ \frac{W({\mathbb{S}})+w_i}{G({\mathbb{S}})-c_i} - \frac{W({\mathbb{S}})}{G({\mathbb{S}})} = \frac{ w_iG({\mathbb{S}})+c_iW({\mathbb{S}}) }{ G({\mathbb{S}})\{G({\mathbb{S}})-c_i\} }, \] where $w_i = \tilde x_i \tilde r_i$ and $c_i = \tilde x_i^2$. The first term reflects $i$'s direct score contribution; the second depends on the score already accumulated by ${\mathbb{S}}$. These interactions generate two phenomena. First, influence can be joint: observations with limited singleton influence may become highly influential when removed together. Second, influence can be masked: observations may appear unimportant in singleton rankings because their effect emerges only after other observations are removed. We use these terms informally in the main text; formal definitions of joint influence, masking, and greedy failure are given in (ref).
Standard methods for identifying MIS face obstacles:\footnote{ See the discussion in kuschnig_hidden_2021, hu2024Most, huang_approximations_2025 for further discussion. }
Finding MIS requires balancing additive score contributions in the numerator against amplification from the shrinking denominator in (ref). Conditional on fixed residualized inputs, this trade-off yields a linear-fractional optimization problem over subsets.
Map the influence components in (ref) to weights and costs, \[ w_i \coloneqq \tilde x_i \tilde r_i, \qquad c_i \coloneqq \tilde x_i^2, \qquad T \coloneqq \sum_{i=1}^n c_i. \] For any set ${\mathbb{S}}$ of size $k$,
where $W({\mathbb{S}}) \coloneqq \sum_{i\in{\mathbb{S}}} w_i,$ and $G({\mathbb{S}}) \coloneqq T - \sum_{i\in{\mathbb{S}}}c_i.$
(ref) ensures that the estimator and fractional objective are well defined on the feasible class. If the condition fails for some sets, the same reduction applies to a ridge-stabilized denominator, replacing $G({\mathbb{S}})$ by $G({\mathbb{S}}) + \lambda$ for $\lambda > 0$.
To maximize the fixed-input ratio over size-$k$ sets, we use dinkelbach1967's method. For an auxiliary parameter $\eta$, define
For fixed $\eta$, \[ F_\eta({\mathbb{S}}) = \sum_{i\in{\mathbb{S}}} (w_i + \eta c_i) - \eta T, \] so the term $-\eta T$ is constant in ${\mathbb{S}}$. Maximizing $F_\eta({\mathbb{S}})$ over $|{\mathbb{S}}| = k$ is therefore equivalent to selecting the $k$ largest scores \[ s_i(\eta) \coloneqq w_i + \eta c_i. \] (ref) alternates between this top-$k$ selection and the ratio update \[ \eta^{(t+1)} = \frac{ W(S^{(t+1)}) }{ G(S^{(t+1)}) }. \] With exact arithmetic, finite termination occurs when the selected set no longer changes, equivalently when the Dinkelbach residual is zero. The tolerance $\tau$ is used as a numerical stopping rule.
\paragraph{Warm-start} At the optimum, the Dinkelbach parameter equals the maximal fixed-input influence, \[ \eta^\star = \max_{|{\mathbb{S}}|=k} \frac{W({\mathbb{S}})}{G({\mathbb{S}})}. \] This identity can be used to reduce iterations when computing MIS paths across subset sizes. When tracing $k=1, \dots, K$, (ref) initializes the run for size $k$ at the solution value from size $k - 1$.
\paragraph{Computational Complexity}
Each iteration of (ref) has three steps. First, the scores $s_i(\eta)=w_i+\eta c_i$ are computed in $\mathcal{O}(n)$ time. Second, the top-$k$ scores are selected, which can be done in expected $\mathcal{O}(n)$ time using linear-time selection, or in $\mathcal{O}(n \log k)$ time using a size-$k$ heap. Once the set is selected, $W({\mathbb{S}})$ and $G({\mathbb{S}})$ are computed in $\mathcal{O}(k)$ time. Thus, with linear-time selection, each iteration costs $\mathcal{O}(n)$ time and $\mathcal{O}(n)$ memory.
Let $I_k$ denote the number of Dinkelbach iterations for subset size $k$. The total cost for one size-$k$ problem is therefore $\mathcal{O}(I_k n)$. For an MIS path over $k = 1, \dots, K$, the cost is $ \mathcal{O}\!\left( n \sum_{k=1}^K I_k \right), $ with warm starts from (ref) typically reducing $I_k$. Because the feasible class is finite, the algorithm terminates finitely; empirically, only a small number of iterations is needed.
The algorithm solves the fixed-input fractional optimization problem exactly. It converts the ratio problem into a sequence of linear maximization problems over a finite feasible class, each solved exactly by top-$k$ selection.
Under absolute continuity and non-degeneracy of the realized weights and costs, ties between distinct feasible ratios occur with probability zero. In that case, $\hat{\mathbb{S}}_k^{\max}$ is almost surely unique.
(ref) solves the fixed-input fractional optimization problem exactly. In a partial linear model, however, the inputs \[ w_i = \tilde x_i \tilde r_i, \qquad c_i = \tilde x_i^2 \] are generated by first-stage residualization. The statistical question is whether the empirical problem is close to the oracle problem based on the unknown residuals \[ v_i = x_i - h_0(Z_i), \qquad u_i = y_i - x_i \beta_0 - g_0(Z_i). \]
For fixed $k$, the relevant first-order oracle objective is additive. Let \[ \phi_i \coloneqq \frac{v_i u_i}{\mu_v} \quad\text{with} \quad \mu_v \coloneqq \mathbb{E}[v_i^2] > 0, \] and define \[ Q_n^{\mathrm{or}}({\mathbb{S}}) \coloneqq \sum_{i\in{\mathbb{S}}} \phi_i, \qquad |{\mathbb{S}}|=k. \] Let \[ {\mathbb{S}}_{k}^{\mathrm{or}} \in \arg\max_{|{\mathbb{S}}|=k} Q_n^{\mathrm{or}}({\mathbb{S}}) \] denote an oracle first-order $k$-MIS. The empirical scaled objective is \[ \widehat Q_n({\mathbb{S}}) \coloneqq n\{\hat\beta-\hat\beta_{-{\mathbb{S}}}\} = n \frac{ \sum_{i\in{\mathbb{S}}}\tilde x_i\tilde r_i }{ \sum_{j\notin{\mathbb{S}}}\tilde x_j^2 }. \]
For fixed $k$, define \[ E_{{\mathbb{S}}} \coloneqq \sum_{i\in{\mathbb{S}}}(\tilde x_i\tilde r_i-v_i u_i), \qquad A_{{\mathbb{S}}} \coloneqq \sum_{i\in{\mathbb{S}}} v_i u_i, \] and
Primitive sufficient conditions include cross-fitting, bounded moments, non-degenerate treatment residual variance, and first-stage nuisance rates strong enough that the generated score error over fixed-size subsets is $o_p(1)$; details are given in the Appendix.
We evaluate the method in simulations and applications. The simulations verify exact optimization against enumeration in small problems, and they measure runtime and iteration counts at scales where enumeration is impossible. The applications then use MIS traces as diagnostics in randomized experiments, linearized prediction tasks, and benchmark regression problems.
Across settings, we compute MIS in both signed directions, identifying sets that maximally increase and maximally decrease the target. We summarize results with influence traces, plotting the optimal influence value as a function of $k$. We also track non-nestedness events, $\hat{\mathbb{S}}_k \not\subset \hat{\mathbb{S}}_{k+1}$, and set overlap using the Jaccard index \( J({\mathbb{A}},{\mathbb{B}}) \coloneqq |{\mathbb{A}}\cap{\mathbb{B}}|/|{\mathbb{A}}\cup{\mathbb{B}}|. \)
We use simulations for two main purposes: (i) to validate theoretical predictions and (ii) to characterize runtime and iteration counts at scale.
\paragraph{Optimization exactness} To validate (ref), we compare (ref) with enumeration and greedy baselines in problems where exhaustive search is feasible ($n \leqslant 50$, $k \leqslant 3$). We use data-generating processes (DGPs) designed to stress the selection problem, including heteroskedasticity, heavy tails, mixtures, nonlinearities, endogeneity, autocorrelated errors, and masking. Across more than 10{,}000 Monte Carlo replications per design, (ref) always matches the enumerated optimum, while greedy selection sometimes returns suboptimal sets.
We next assess the residualized setting motivated by (ref). The simulation design contains two seeded influential groups of three observations each, built-in masking kuschnig_hidden_2021, and nonparametric confounding. We vary $n \in \{1000, 5000, 10000\}$, estimate the nuisance functions with gradient boosting and $5$-fold cross-fitting, and compare the recovered empirical MIS with the known oracle-style score benchmark. Details are given in Appendix (ref).
The residualized influence values track the oracle values closely, even at moderate sample sizes. Set recovery is more demanding; strongly influential sets are recovered reliably, whereas weakly separated or moderately influential sets converge more slowly. This matches (ref) --- value approximation is stable under weaker conditions than exact recovery of the maximizing set.
We benchmark an implementation of (ref) on synthetic univariate regressions across a grid of sample sizes $n$ and set sizes $k$, recording wall-clock time (across 100 runs) and the number of Dinkelbach iterations. As shown in (ref), the median wall-clock time for $n = 10^6, k = 10^5$ remains below $200$ ms.\footnote{ The implementation uses a size-$k$ heap for ordering, and is implemented in R and Rcpp eddelbuettel2011rcpp, on a Ryzen AI Max+ Pro 395, using a single thread. We also benchmarked an implementation of the greedy algorithm by kuschnig_hidden_2021 on a subset of the grid (a runtime of $200$ ms is achieved for $n = 10^4$ and $k = 50$), as well as the approximations implemented by broderick_automatic_2021; across a range of settings for $(n, k)$, our method is typically faster to compute, often by an order of magnitude. } Across the entire grid, (ref) converged in a median of three iterations, with a maximum of six.
To stress-test convergence, we further scale the implementation and use adversarial warm starts. At $n=10^8$, runtime is roughly five seconds for $k=10^6$ and 60 seconds for $k=10^7$. At $n=10^9$, where memory becomes limiting, runtime is about ten seconds for $k=10^6$, 80 seconds for $k=10^7$, and fifteen minutes for $k=10^8$. For the $n=10^8,k=10^7$ case, replacing the warm start with $\eta^{(0)}\in\{10^3,10^6,10^9,10^{12},10^{18}\}$ delays convergence by only one iteration, from five to six.
We use the method as a set-level sensitivity diagnostic in three classes of applications. In randomized experiments, the target is a fixed residualized univariate ratio and the algorithm identifies exact empirical MIS. In linearized prediction of semantic similarity, MIS quantify which training subsets most affect a local scalar prediction. In observational benchmark regressions, the PLM theory gives a first-order oracle interpretation when residualized-score stability is credible. In all applications we compute signed MIS in both directions.
We revisit the seven microcredit RCTs studied by meager_understanding_2019 and broderick_automatic_2021. These trials are useful stress tests because average treatment effect (ATE) estimates can be sensitive to small influential subsets --- in two trials removing a single observation flips the sign of the estimated ATE, and sets of size 15 suffice across all trials. Previous work has used approximations, as enumeration is infeasible at the smallest size ($n \geqslant 961$). Our algorithm traces exact $k$-MIS over the full range of $k$ at negligible computational cost.
(ref) shows the Mongolia trial of attanasio_impacts_2015. The increasing and decreasing traces differ substantially. In the increasing direction, non-nestedness is frequent but mostly local: the greedy trace remains close in value even as set overlap declines. In the decreasing direction, one non-nestedness event causes a large and persistent shift in the optimal set. Because greedy selection cannot revise earlier choices, it remains trapped on a suboptimal path and the influence gap accumulates.
(ref) reports the remaining six trials. Non-nestedness is common across trials, confirming that optimal MIS paths are generally not nested in $k$. Greedy selection often approximates influence magnitudes well, but it need not recover the maximizing sets. The Philippines trial features the clearest asymmetry --- the increasing trace is initially stable and later accelerates, while the decreasing trace follows the opposite pattern. These results suggest that value approximation and set recovery should be evaluated separately, consistent with (ref).
Next, we use MIS for a linearized prediction task. We predict semantic similarity for $n=5{,}749$ English sentence pairs from the STS benchmark cer-etal-2017-semeval. Each pair is mapped to frozen sentence embeddings using a pre-trained transformer model song2020mpnet, and the scalar regressor is the cosine similarity between the two embeddings. For three query pairs with low, medium, and high similarity, we study the local prediction target $\phi(\beta) = x_0 \beta$.
(ref) reports the full-sample fitted score, the fitted scores after removing the $5{,}000$-MIS in each direction, and the smallest $k$ for which the fitted score exceeds $1.0$ for three specific sentences (with minimal, average, and maximal similarity). Because the target scales with $x_0$, high-similarity query pairs are mechanically more sensitive to removal of influential training subsets. The traces reveal substantial sensitivity for the medium- and high-similarity pairs, including cases where deleting a subset pushes the linearized score outside the nominal $[0,1]$ range. Further details are provided in Appendix (ref).
We also apply the method to benchmark datasets from economics, biology, statistics, and machine learning; details are in Appendix (ref). Across these datasets, greedy selection usually tracks the optimal influence value closely, but exact and greedy sets often differ. Most non-nestedness events are short-lived, in contrast to the persistent failure seen in the Mongolia trial. Warm-starting along the MIS path in (ref) keeps iteration counts small, with at most four iterations in these applications. Runtime is dominated by fitting the original model rather than by MIS selection.
This paper makes most influential set analysis computationally explicit for a broad class of fixed-input univariate objectives. The key reduction is algebraic --- once leave-set-out influence is written as a score-over-curvature ratio, the search over $\binom{n}{k}$ subsets reduces to repeated top-$k$ selection along a one-dimensional parameter path. For the fixed residualized inputs covered by (ref), the result is the exact global optimum, not a greedy or local approximation.
The statistical interpretation depends on how those inputs are generated. In randomized experiments and other fixed-input settings, the empirical MIS is the target. In partial linear models, (ref) shows that the scaled residualized objective has a first-order oracle interpretation when residualized scores and denominators are stable. This distinction is important: orthogonality supports value stability, but exact recovery of the selected set also requires separation between the best and second-best oracle sets.
We recommend reporting signed MIS traces over a range of $k$. The increasing and decreasing traces answer different robustness questions and can implicate different subsets. Large early jumps indicate sensitivity to few observations; gradual traces suggest dispersed influence; sharp composition changes signal non-nestedness and potential failure of greedy approximations. The implicated sets should then be inspected directly, especially when they contain duplicated records, unusual covariate patterns, high-leverage observations, or observations tied to a common source.
\paragraph{Robustness Auditing} MIS traces provide target-specific worst-case deletion diagnostics. Compared with singleton influence measures, they reveal whether sensitivity is concentrated in one record or distributed across interacting observations. Compared with ad-hoc deletion checks, each set is the most adverse set of its size for the chosen target. Compared with greedy approximations, the exact trace is not constrained to follow a nested deletion path. Our experiments show that greedy methods may approximate the influence value while missing the maximizing set, and in some cases a single non-nestedness event produces persistent error.
\paragraph{Data Curation} MIS can guide preprocessing and data cleaning without relying on blunt transformations such as trimming or winsorization. The selected sets identify which observations actually drive the downstream estimate or prediction. This can prioritize manual review, reveal duplicated or contaminated records, and document whether proposed cleaning rules address the relevant sources of sensitivity.
\paragraph{Prediction Diagnostics} For linearized prediction targets, MIS provide dataset-level explanations that complement feature-level attributions. A large singleton effect indicates that one example matters on its own. A large set effect indicates that the prediction is anchored by a subset whose collective role may not be visible from individual records. This is useful for identifying duplicated, highly similar, or mutually masking examples that jointly support a prediction.
The computational reduction requires a linear-fractional leave-set-out objective. This covers residualized univariate least-squares targets and related affine functionals, but non-linear estimands, vector-valued targets, and general $M$-estimators may require approximation, local linearization, or different optimization subproblems.
The PLM result is also deliberately first-order. For fixed $k$, the scaled residualized objective is close to an oracle orthogonal-score objective under residualized-score stability. This does not imply that arbitrary first-stage learners produce identical MIS, nor that exact set recovery is guaranteed without a gap. When first-stage learners are unstable for high-leverage or extreme-score observations, the recovered set remains the exact empirical MIS for the residualized regression but may not estimate the oracle first-order MIS.
Finally, exact MIS are diagnostic rather than prescriptive. A highly influential set may reveal contamination, model misspecification, subgroup heterogeneity, or genuine scientific signal. The method identifies the subset responsible for sensitivity; substantive interpretation still requires domain knowledge.
Several extensions are natural. Ridge-stabilized denominators preserve the same basic reduction and can improve behavior when residual curvature is small. For broader classes of smooth estimators, approximate score-over-curvature representations may yield local or asymptotic analogues of the present algorithm. Structured versions of MIS are also promising; replacing the top-$k$ step with a constrained selection subproblem would allow influential clusters, time-contiguous blocks, group-balanced removals, or stratified deletion rules.
A second direction is inference on the traces themselves. Exact MIS computation makes it feasible to separate ordinary sampling variability from unusually influential subsets, and can provide candidate sets for formal tests of excessive influence konrad_testing_2025. This shifts the next question from how to find influential sets to which influential sets are substantively or statistically anomalous.
Efficient MIS computation turns set-level sensitivity analysis from a bespoke forensic exercise into a routine diagnostic. The method complements robust estimation, which limits the effect of contamination; meanwhile MIS identify which observations are responsible for sensitivity and how that sensitivity accumulates with set size. In high-stakes empirical and machine-learning pipelines, such inspectable counterfactual subsets can improve transparency, support data provenance, and clarify the relationship between data and conclusions.
We introduced an exact algorithm for identifying most influential sets when leave-set-out effects have a linear-fractional representation. The method reduces the combinatorial search over $\binom{n}{k}$ subsets to a finite sequence of top-$k$ selection problems, with $\mathcal{O}(n)$ cost per iteration and few iterations in practice.
The guarantees separate computation from statistical interpretation. For fixed residualized inputs, the algorithm returns a globally optimal empirical MIS. For partial linear models, the scaled residualized influence objective is first-order equivalent to an oracle orthogonal-score objective under residualized-score stability; value consistency follows directly, and exact set recovery follows under a separation condition.
Empirically, the method scales to datasets far beyond the reach of enumeration. Across randomized experiments, semantic similarity prediction, and benchmark regressions, exact MIS traces reveal frequent non-nestedness and show where greedy approximations succeed or fail. These traces provide actionable diagnostics for robustness auditing, data curation, and prediction analysis. Future work can extend the framework to structured deletion constraints, vector-valued or nonlinear targets, and formal inference for anomalous influence.
This paper develops methods for identifying most influential sets, whose removal induces the greatest change in a target quantity of interest. The primary goal is to improve robustness auditing and clarify how empirical conclusions depend on specific subsets of data.
Potential positive impacts include improved accountability, data provenance, and reliability. By identifying the subsets that drive estimates or predictions, the method can help practitioners detect contamination, duplicated records, unstable estimates, subgroup dependence, or other sources of sensitivity. It can also guide targeted data cleaning and make robustness analyses more reproducible.
A potential risk is adversarial use. An actor could use influence information to identify records whose inclusion or removal would steer a model or estimate in a desired direction. We view transparency as the appropriate mitigation. Set-level sensitivity already exists whether or not it is measured; efficient diagnostics make these dependencies visible, auditable, and easier to report.
The computational footprint is modest relative to enumeration. In our benchmarks, the method scales to millions of observations on a single thread, and the runtime is typically dominated by fitting the original model rather than by MIS selection.