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.
42,518 characters · 19 sections · 30 citation commands
Testing Most Influential Sets
\lhead
Machine learning (ML) models and statistical inferences can be highly sensitive to small subsets of data. In many applications, just a handful of samples can overturn key conclusions: two countries nullify the estimated effect of geography on development kuschnig_hidden_2021, a single outlier flips the sign of a treatment effect broderick_automatic_2021, or a small group of individuals drives disparate outcomes in algorithmic decision-making black_leave-one-out_2021. These most influential sets --- data subsets with the greatest influence on model predictions --- are central to questions of interprtability, fairness, and robustness in modern machine learning black_leave-one-out_2021, chen_why_2018, chhabra_what_2023, ghorbani_data_2019, sattigeri_fair_2022.
Despite their practical importance, practitioners lack principled tools to assess whether a set's influence is genuinely problematic. Current practice relies on heuristics, ad-hoc sensitivity checks, and domain expertise, while approximate methods such as influence functions koh_understanding_2017, fisher2023Influence, schioppa_theoretical_2023 systematically underestimate the impacts of sets and extreme cases basu_second-order_2020, koh_accuracy_2019. Recent work highlights both the promises and challenges of most influential subsets --- small sets can drive results even in randomized trials broderick_automatic_2021, kuschnig_hidden_2021, heuristic algorithms can fail in simple settings hu2024Most, huang_approximations_2025, and influence bounds remain an active area of research moitra_provably_2023, freund_towards_2023, rubinstein_robustness_2024. What remains missing is a principled method to distinguish natural sampling variation from genuinely excessive influence.
We develop a statistical framework for assessing the significance of most influential sets. By focusing on linear regression --- a tractable, interpretable, and widely-used setting that underlies many modern methods --- we derive the exact asymptotic distributions of maximal influence. We show that two distinct regimes emerge depending on the size of the influential set: when the size is fixed, maximal influence converges to a heavy-tailed Fréchet distribution; when the size grows with the sample, maximal influence converges to a well-behaved Gumbel distribution. Our results enable principled hypothesis tests for excessive influence, replacing ad-hoc diagnostics with rigorous statistical procedures. We demonstrate their practical value via applications across economics, biology, and machine learning benchmarks, resolving ambiguous cases where influential sets drive contested findings.
\paragraph{Contributions.} We present a comprehensive analysis of the influence of most influential sets, both theoretically and in practical applications. Our main contributions are:
To summarize --- we provide the first rigorous theoretical results that allow us to interpret influence, and demonstrate practicality by resolving contested findings.
\paragraph{Outline.} The remainder of the paper is structured as follows. Section (ref) introduces the problem of most influential sets and formalizes the setting. Section (ref) presents our theoretical results on the distribution of maximal influence. Section (ref) demonstrates the practical merits of our framework through simulations and empirical applications. Section (ref) discusses implications, limitations, and future directions, and Section (ref) concludes.
Practitioners routinely encounter situations where small subsets of data points drive key conclusions. Consider the following scenarios:
At the core of these examples lie most influential sets, which exert disproportionate influence on an estimate or prediction. These sets are intuitive to interpret, directly tied to the quantity of interest, and provide a new dimension for assessing estimates by highlighting their support in the data.
What has been unclear, however, is how to interpret and deal with influential sets. Existing influence methods quantify how much changes, but offer little guidance on interpretation. Current practice relies heavily on domain expertise and ad-hoc rules, lacking a statistically rigorous framework for judging influence. Heuristics, such as sign-flips or significance thresholds, can flag effects that are stable and miss genuinely problematic influence. We address this gap by quantifying whether observed maximum influence is statistically compatible with natural sampling variation.
We consider a supervised learning task with input space $\mathcal{X} \subset \mathbb{R}^P$ and target space $\mathcal{Y} \subset \mathbb{R}.$ The goal is to learn a function $f(\theta, \cdot) : \mathcal{X} \mapsto \mathcal{Y}$ parameterized by $\theta \in \mathbb{R}^Q.$ Given training data $\left\{\left( x_n, y_n \right)\right\}_{n = 1}^N$ and a loss function $\mathcal{L}\left(\cdot, \cdot\right),$ we learn parameters by solving \[ \hat\theta = \underset{\theta \in \mathbb{R}^Q}{\arg\min} \sum_{n = 1}^N \mathcal{L}\left( f(\theta, x_n), y_n \right). \] Let $\left[ N \right] = \left\{1, \dots, N\right\}$ and denote both an index set and its corresponding subsample as ${\mathbb{S}} \subset \left[ N \right].$ For any subset ${\mathbb{S}},$ we use a subscript $\hat\theta_{-{\mathbb{S}}}$ to denote an estimate $\hat\theta$ without ${\mathbb{S}},$ i.e. \[ \hat\theta_{-{\mathbb{S}}} = \underset{\theta \in \mathbb{R}^Q}{\arg\min} \sum_{n \not\in {\mathbb{S}}} \mathcal{L}\left(f( \theta, x_n), y_n \right). \]
\paragraph{Research Question.} What is the probability distribution of $\Delta^{\max},$ and how can we distinguish excessive influence from natural sampling variation?
A common and related approach to study influence is via influence functions fisher2023Influence, hu2024Most, koh_understanding_2017. These are motivated by reweighing via the perturbation \[ \hat\theta(\epsilon; {\mathbb{S}}) \coloneqq \underset{\theta \in \mathbb{R}^Q}{\arg\min} \frac{1}{N} \sum_{n=1}^N \mathcal{L}\left(f( \theta, x_n), y_n \right) + \epsilon \sum_{i \in {\mathbb{S}}} \mathcal{L}\left(f( \theta, x_i), y_i \right). \] Setting $\epsilon = 0$ recovers $\hat\theta,$ while $\epsilon = -N^{-1}$ yields $\hat\theta_{-{\mathbb{S}}}.$ The influence function is the first-order linear approximation at $\epsilon = 0.$
While influence functions are computationally convenient, they are unreliable even for simple models basu_second-order_2020, hu2024Most, huang_approximations_2025, koh_accuracy_2019. In particular, they systematically underestimate the impact of (a) sets of data points and (b) highly influential data points. This occurs because the first-order approximation cannot reflect higher-order effects from the interplay between data points or differential leverage scores.
\paragraph{Exact Maximum Influence.} We therefore derive an exact influence formula (in Section (ref)) and characterize the behavior of maximum influence (Section (ref)) to enable principled testing (Section (ref)). We focus on the tractable but ubiquitous linear setting, allowing us to accurately portray most influential sets, for which extreme behavior dominates and first-order approximations fail most dramatically.
Our goal is to characterize the behavior of $\Delta^{\max},$ the influence of the most influential set. This quantity is defined through maximization over all possible subsets, and its distribution is governed by extreme value theory rather than classical asymptotics. See (ref) for an illustration. When taking maxima over random quantities, three possible limiting distributions can emerge fisher_tippett_limiting_1928, gnedenko_sur_1945: the well-behaved Gumbel (Type I), the heavy-tailed Fréchet (Type II), and the bounded Weibull (Type III).
We need to determine which extreme value distribution (EVD) attracts $\Delta^{\max}.$ Specifically, we distinguish between the Gumbel distribution with exponential tails, and the Fréchet distribution with polynomial tails allowing for potentially arbitrarily large influence. (The Weibull distribution can be ruled out since influence is unbounded.) Once we establish the asymptotic distribution, we show how it applies to finite samples.
Consider the standard linear regression model, where $f$ is a linear function relating random features $X$ to the outcome $Y$ via the parameter vector $\theta$. The ordinary least-squares (OLS) population estimator of $\theta$ is \[ \tilde{\theta} \coloneqq\mathbb{E}[XX']^{-1}\mathbb{E}[XY] \] yielding fitted values $\hat{Y}=X'\tilde{\theta}$ and the associated residuals $R= Y-X'\tilde{\theta}$. Stacking $N$ observed training samples yields the design matrix $\mathbf{X} \in \mathbb{R}^{N \times P}$ and outcome vector $\mathbf{y} \in \mathbb{R}^N.$ For OLS, we assume that $\mathbf{X}' \mathbf{X}$ is invertible and remains so after removing any subset.\footnote{ This is not necessary for our results, as they extend to ridge regression, where the penalization parameter $\lambda > 0$ in $\mathbf{X}' \mathbf{X} + \lambda \mathbf{I}$ creates a ridge that guarantees invertibility. } The sample OLS estimator is then \[ \hat\theta \coloneqq \underset{\theta}{\arg\min} \lVert \mathbf{y} - \mathbf{X} \theta \rVert^2 = \left( \mathbf{X}' \mathbf{X} \right)^{-1} \mathbf{X}' \mathbf{y}, \] yielding predictions $\hat{\mathbf{y}} = \mathbf{X} \hat\theta$ and residuals $\mathbf{r} = \mathbf{y} - \hat{\mathbf{y}}.$
For our main results, we consider least-squares estimates of the regression coefficients, with and without penalization. For illustration, however, we will consider a univariate model with one positive coefficient of interest and target function $\phi(\theta) = \theta_1.$ This eases notation considerably and comes without loss of generality --- theoretical results apply to more general settings.\footnote{ Multiple features can be factored out via the Frisch-Waugh-Lovell theorem under mild assumptions, leaving an equivalent univariate regression. A different sign can be accommodated by simply sign-flipping the feature of interest or adjusting the target function $\phi$ accordingly. }
The influence of a single observation $i$ is well-known belsley_regression_1980, cook1979Influential, walker_influence_1988 to be
where $h_i$ is the leverage score and $r_i$ the residual of observation $i.$
We extend this result to be (i) applicable to sets of observations, and (ii) analytically convenient.
(ref) reveals the additive structure of individual contributions in the numerator, as well as the multiplicative adjustment from the denominator. It provides an exact closed-form expression that avoids re-fitting the model for each candidate subset.
We now turn to finding the distribution of $\Delta({\mathbb{S}})$ for the most influential set, ${\mathbb{S}}_k^{\max}.$ Since this quantity is defined by an extremal operation (maximization over all possible subsets), its asymptotic behavior is governed by extreme value theory. Specifically, we seek the limiting EVD $H$ such that $\Delta^{\max} \in \mathrm{MDA}\left( H \right),$ i.e., $\Delta^{\max}$ lies in the maximum domain of attraction of $H.$
Two canonical EVDs are of particular interest: the Fréchet (Type II) distribution $\Phi_{\alpha}$ for heavy-tailed variables, and the Gumbel (Type I) distribution $\Lambda$ for light-tailed variables. We distinguish two practically relevant regimes based on how the subset size $k$ scales with sample size $N$:
Both regimes have been considered in practical applications broderick_automatic_2021, kuschnig_hidden_2021, and --- as we will show next --- they yield fundamentally different asymptotic behavior with important implications for the interpretation of influence.
This result shows that, for constant-size sets, $\Delta^{\max}$ inherits tail behavior from the heavier tail of $R$ and $X.$ If one of them is sufficiently heavy-tailed, even small sets can exert extreme influence with non-negligible probability. (ref) simplifies (ref) in absence of heavy tails.
When the most influential set grows `slow enough' with the sample size, the central limit theorem (CLT) dominates the asymptotic behavior:
This reveals a fundamental distinction: constant-size sets are dominated by the heaviest tail, while, for growing sets, $\Delta^{\max}$ converges to a well-behaved Gumbel distribution with exponentially decaying tails. This result holds regardless of the underlying distributions of $X$ and $R$ as long as the variance of $X_i\cdot R_i$ is finite.
With the theoretical results established, we turn towards practical implementation. Assuming there is a most influential set of interest,\footnote{ This set can be obtained with any of the methods in the literature broderick_automatic_2021, kuschnig_hidden_2021, freund_towards_2023, and could, e.g., be the smallest set that achieves a sign-flip --- a commonly considered heuristic cutoff. If no such heuristic is used and multiple tests are considered (e.g., for different coefficients or sets sizes), a multiple testing correction should be applied. Note that EVT controls the implicit search for the most influential set over the $\binom{N}{k}$ possible subsets. } our procedure follows three steps:
\paragraph{Computation.} Thanks to (ref), our procedure is practical and computationally convenient, allowing for application to large and varied datasets. While accurately estimating Extreme Value Distributions (EVDs) is a recognized and separate challenge in its own right, the maximum likelihood steps within our framework are simple and well-behaved, optimizing over only two parameters in the Gumbel case. The primary computational constraint instead stems from finding most influential sets --- we need to approximate $\Delta^{\max}$ for the $M$ block maxima estimates. For computational tractability, we use an adaptive greedy algorithm hu2024Most, kuschnig_hidden_2021 with complexity $\mathcal{O}(Mk)$ and an efficient implementation based on our closed-form influence formula for sets.
In this section, we validate our theoretical predictions, investigate convergence in small samples, and demonstrate their practical relevance and utility through real-world applications spanning economics, biology, and machine learning.
We begin with a controlled setting, where we (i) illustrate, (ii) investigate convergence for small samples, and (iii) evaluate empirical estimation.
\paragraph{Illustration.} (ref) illustrates our approach on a simple linear regression with one moderately influential point due to high leverage. Panel A visualizes the data, significance thresholds (at the 10, 5, and 1% significance levels) as a function of predictor and response values. Panel B presents the underlying extreme value analysis: block maxima inform the estimated Gumbel distribution, yielding a $p$-value of 0.04 for the observation of interest.
Next, we verify that maximal influence converges to the predicted extreme value distributions. We consider four scenarios based on combinations of the standard Normal and $t(5)$ distributions for $X, R.$ For each scenario, we simulate $1,000$ datasets of sizes between $N = 20$ and $N = 1000,$ and compare the empirical parameter estimates with the theoretical prediction. Overall, we find rapid convergence, implying that our theoretical predictions are applicable with small samples.
(ref) shows convergence of the scenarios to the predictions, which are indicated by dashed horizontal lines. (Details are provided in (ref) of the Appendix.) All scenarios reliably converge for moderate sample sizes. The Normal-Normal scenario is insignificantly different from Gumbel behavior ($\xi^{-1} = 0$) for $N \geqslant 50,$ and the heavy-tailed cases also exhibit the predicted Fréchet behavior ($\xi^{-1} = 0.2$). Notably, the $t(5)$--Normal case converges at slower rates, likely due to the relative instability of the inverse $\left( \mathbf{X}' \mathbf{X} \right)^{-1}_{\mathbb{S}}$ in small samples. Overall, the simulation results support the applicability of (ref) in small samples.
\paragraph{Location and Scale Estimation.} Next, we evaluate whether block maximum MLE accurately captures the location and scale parameters for empirical testing. Results are provided in (ref) of the Appendix. We find that bias-corrected estimation of the location parameter works well, while the scale estimate is consistent but exhibits a minor downward bias that disappears asymptotically dombry2019mle. For our goal of hypothesis testing, the overall distribution and its quantiles are recovered effectively.
We investigate several real-world datasets --- two applications from economics and biology, and four machine learning benchmarks --- and provide the first conclusive investigation of influence.
\paragraph{Economic Development and Geography.} We re-examine the controversial finding that rugged terrain benefits African economies when compared to the rest of the world nunn2012Ruggedness. kuschnig_hidden_2021 call the influence of the Seychelles, which remove significance of the estimate of interest when coupled with any of Rwanda, Lesotho, Eswatini, and the Comoros. However, lacking the statistical framework that we provide, they were not able to test whether this level of influence should be deemed excessive or not.
We can now decisively resolve this controversy. (ref) reveals the Seychelles as excessively influential on $\hat\theta_{\text{rugged}}$, both individually ($p < 0.001$) and in combination with other outliers, except for Lesotho. This substantiates the suspected confounding from the size of nations kuschnig_hidden_2021, lending statistical rigor to prior concerns and calling into question the differential relation between ruggedness and income in Africa.
\paragraph{Sparrow Morphology --- Big Heads and Beaks.} We analyze the relation between head and tarsus length in saltmarsh sparrows, based on measurements of $N = 1,295$ sparrows with known outliers gjerdrum_egg_2008, zuur_protocol_2010. The baseline regression yields $\hat\theta = 0.011$ with a standard error of $(.030),$ implying a relation that is statistically indistinguishable from zero.
However, a curious data point moves the estimate to $0.219 (.029)$, turning the estimate significantly positive. An additional data point further moves the estimate to $0.288 (.032).$ These extreme impacts from a vanishing fraction of the sample are deemed excessive by our approach at any conventional significance level (both $p < 0.001$).\footnote{ One possible explanation for this excessive influence are data entry errors: The first observation (an outlier in both head and tarsus size) may have the two (adjacent) features mixed up --- when swapped, they would fit well into overall averages. The second observation (an outlier in one feature) stands out with both values being equal up to the one significant digit. }
\paragraph{Machine Learning Benchmarks.} We apply our framework to four widely-used regression benchmarks: Law School, Adult Income, Boston Housing, and Communities & Crime. For each dataset, we identify a most influential set of interest and test for excessive influence.
We develop the first rigorous statistical framework for assessing when most influential sets represent genuine problems rather than natural sampling variation. By deriving the extreme value distribution of maximal influence, we allow practitioners to replace ad-hoc sensitivity checks with principled statistical decision rules.
Our key insight is how maximal influence fundamentally depends on set size and tail behavior. For constant-size sets with polynomial tails, maximal influence follows a heavy-tailed Fréchet distribution, implying that extreme influence can be arbitrarily large. For growing sets or exponential-tailed data, maximal influence converges to a well-behaved Gumbel distribution.
These results address a critical gap in interpretable machine learning. While recent work has developed methods to identify influential sets broderick_automatic_2021, freund_towards_2023, hu2024Most, no formal theory existed to determine when their influence is excessive. Our framework provides the long-missing theoretical foundation that enables rigorous statistical inference for influential observations and sets cook1979Influential.
We can clarify the applicability of heuristics that are commonly used for identifying excessive influence, and provide conclusive answers when excessively influential sets are suspected kuschnig_hidden_2021. The $2/\sqrt{N}$ threshold for coefficient influence belsley_regression_1980, e.g., is asymptotically accurate for randomly selected observations, but is too restrictive for most influential observations, where the selection procedure necessitates extreme value theory.
\paragraph{Practical Recommendations.} In general, most influential sets hold valuable information for inference. Our test is deliberately conservative, controlling Type I errors (false claims of excessive influence) at the cost of some Type II errors (failing to detect truly excessive influence). This reflects our view that influential sets are a natural feature of data and not a problem to be eliminated. When our test identifies an excessively influential set, however, we recommend:
\paragraph{Limitations and Future Work.} Our analysis focuses on linear regression --- foundational for theory and modern ML methods, but limited to contexts where interpretability is valued rudin_stop_2019. Extensions to generalized linear models, tree-based methods, or non-parametric estimators require further developments. Our asymptotic arguments leverage independence between features and residuals, which may be restrictive when dependence affects influence patterns. Explicitly addressing dependence between influence components through the selected set and across sets is possible through generalizations. While simulations show that small-sample behavior quickly converges to asymptotic predictions (even at $N = 100$), further investigation of the theory-practice gap is warranted.
Practicality of our approach hinges on estimating the extreme value null, and, hence, approximating maximum influence. Finite-sample estimation of tail behavior and EVD parameters can be delicate, and improving these estimators would directly sharpen $p$-values. Two options include leveraging domain-specific information and improved bias correction methods dombry2019mle, oorschot_abm_2020. Advances in finding influential sets remain an active research area hu2024Most, huang_approximations_2025, and could substantially improve block-maxima, reduce runtime, and broaden applicability.
\paragraph{Broader Implications.} Our framework enables more reliable decision-making across domains where linear models remain the method of choice. Principled tools for understanding data points that drive model behavior are crucial for building trustworthy systems. Applications span fairness assessments --- where influential sets can reveal algorithmic bias --- to causal inference settings, such as randomized controlled trials or quasi-experimental econometric analyses where small data subsets can fundamentally alter estimates.
Importantly, we reframe influence as a natural feature of data requiring appropriate treatment rather than a problem to be fixed. Influential sets can represent genuine heterogeneity or important edge cases that should inform model development. This perspective enables more nuanced approaches to data analysis, where information is preserved and assessed through principled statistical inference rather than discarded based on rules of thumb.
We developed a statistical framework that transforms the assessment of most influential sets from art to science. By deriving the extreme value distributions of maximal influence, we enable rigorous hypothesis testing to distinguish excessive influence from natural variation. Applications across economics, biology, and machine learning benchmarks demonstrate the practical utility of our approach.
Our method offers clear guidance to practitioners --- when small sets overturn results of interest, our tests reveal whether this influence is statistically excessive. This enables more robust and transparent decision-making in settings where reliability matters, from medical trials to policy evaluation to algorithmic systems. By providing theoretical foundations for influential set analysis, this work advances both the theory and practice of interpretable machine learning.
Proofs are detailed in the Appendix, datasets are from the cited sources, and code to reproduce results are available at \url{https://github.com/konradld/testingMIS}.
Large language models were used to (i) aid and polish writing, (ii) discover and retrieve related work, (iii) check results for apparent mistakes.