Approximations to worst-case data dropping: unmasking failure modes
Authors: Jenny Y. Huang
David R. Burt
Yunyi Shen
Tin D. Nguyen
Tamara Broderick
Venue: Accepted by TMLR ()

Abstract: A data analyst might worry about generalization if dropping a very small fraction of data points from a study could change its substantive conclusions. Checking this non-robustness directly poses a combinatorial optimization problem and is intractable even for simple models and moderate data sizes. Recently various authors have proposed a diverse set of approximations to detect this non-robustness. In the present work, we show that, even in a setting as simple as ordinary least squares (OLS) linear regression, many of these approximations can fail to detect (true) non-robustness in realistic data arrangements. We focus on OLS in the present work due its widespread use and since some approximations work only for OLS. Across our synthetic and real-world data sets, we find that a simple recursive greedy algorithm is the sole algorithm that does not fail any of our tests and also that it can be orders of magnitude faster to run than some competitors.

Published in Transactions on Machine Learning Research (07/2025)
Approximations to worst-case data dropping: unmasking failure modes
Jenny Y. Huang
jhuang9@mit. edu
MIT EECS and MIT-IBM Watson AT Lob
David R. Burt
dbart&mmit.cm edu
MIT EECS and MIT-IBM Watson AT Lab
Yunyi Shen
yshen99@mit, edu
MIT EECS and MIT-IBM Watson AT Lab
Tin D. Nguyen
tdn@mmt edu
MIT EECS and MIT-IBM Watson Al Lab
Tamara Broderick
throderick@miit. edu
MIT EECS and MIT-IBM Watson AT Lab
Reviewed on OpenReview: https: openreiiee. net/ forum? id= m6EV
Abstract
data analyst might worry about generalization dropping a very small fraction of data points from a study could change its substantive conclusions. Checking this non-robustness directly poses combinatorial optimization problem and is intractable even for simple models and moderate data sizes. Recently various authors have proposed diverse set of approximations to detect this non-robustness. In the present work, show that, even in setting as simple as ordinary least squares (OLS) linear regression, many of these approximations can fail to detect (true) non-robustness in realistic data arrangements. We focus on OLS in the present work due its widespread use and since some approximations work only for OLS. Across our synthetic and worl-world data sets, we find that a simple recursive greedy algorithm is the sole algorithm that does not faail any of our tests and also that can be orders of magnitude faster run than some competitors.
1 Introduction
Researchers typically run data analysis with the goal of applying any conclusions in the future. For instance, economists run randomized controlled trials (RCTss of microcredit with particular set of people at a particular time. If the resulting data analysis shows that microcredit increases business profit, policymaker might. distribute microcredit. people in the future, on the assumption that microcredit. will help these people too. We might worry whether this assumption warranted if we could drop a very small fraction of people from the original trial and instead conclude that microcredit decreases business profit. As concrete example, Broderick et al. (2020) show that it is possible to drop 15 households out of over 16,500 in influential microcredit. RCT and change the result to statistically significant conclusion of the opposite sign.
In many cases, then, it behooves us to check: can we find a small fraction of data that, if dropped, would change the conclusion of the analysis? A brute force approach to answering this question enumerates every possible small data subset and re-runs the analysis combinatorially large number of times. E.g., suppose we might be concerned dropping 0.1% of our data could change our conclusions, Running (16500) 1-second-long data analyses would take over 1046 years.

---

Published in Transactions on Machine Learning Research (07/2025)
Given these computational challenges, researchers have suggested various approximations instead. Broderick et al. (2020) suggest using an approximation based on instantiating continuous weights the data points and differentiating with respect to these weights. The authors use this approximation to identify small data subsets that, when dropped, change conclusions in multiple landmark papers in economics (c.g. Angelueci
& De Giorgi 2009; Finkelstein et al. 2012). In follow-up work focused on OLS, K Kuschnig el al. (2021)
introduced two additional ideas for finding the worst-case data subset: (1) approximating the impact of removing a group of points by the sum of the impacts of exactly removing individual data points and (2)
greedily removing one data point at time. Mootra & Rohatgi (2023): Freund & Hopkins (2023) provide
additional approximations that are specific to OLS.
Recently, scientists and social scientists have used some of these approximations to assess the robustness of important findings in econometrics (Martinez 2022), epidemiology (Di & Xu 2022), and the social sciences (Davies et al.) 2024 Burton & Roach, 2023). Given the deployment of these approximations in practice, we ask when and how they can fail in realistic data analyscs- to alert practitioners and motivate further approximation development. Previous works have identified particular instances of failure modes, without comparison of failures across approximation methods (Broderick et al. 2020 Nguyen et al. 2024). Other works have illustrated failure modes in adversarial constructions or settings where a large fraction of the data
(2 1%) needed to be removed (Moitra& & Rohatgi 2023 Freund & Hopkins 2023 Kuschnig et al. 2021 J.
In the present work, we systematically explore whether approximations can detect if there exists a very small fraction (< 1%) of data that, if dropped, can change conclusions. In other words, we ask whether approximations can detect a particular form of non-robustness in a data analysis. We focus on natural data settings with adversary. In order to include the approximations of Moitra & Rohatgi (2023); 15 Freund & Hopkins 2023) in our comparison, we focus linear regression fit with OLS. Before the present work and contemporancous work by Hu et al. (2024). there had not been studies systematically characterizing non-adversarial failure modes of approximations for this form of robustness or studies comparing the prominent existing approximations.
In many aspects, Huu et al. (2024) and our present work are complementary. While Hu et al. (0024) focus on exact recovery of the most influential data subset with cardinality at most equal to a stated value, we focus on finding whether there exists a small subset of data that, if dropped, could change substantive conclusions. Given our different focuses, Hu et al. (2024) find it useful to separate masking into two phenomena: amplification and cancellation. Meanwhile, we find it useful to point out failure modes due to poor conditioning of the bulk of data. Hu et al. (2024)'s 's theory assumes a particular daata-generating process (their Equation 7]: while we don't make this assumption, we instead need to take a limit of an outlier data point's position to derive our results (Proposition 4.3
Both Hu et al. 2024) and our work focus on OLS for theory and illustration of failure modes. While linear regression is less common in engineering disciplines, Castro Torres & Akbaritabar (2024) demonstrate that, as recently as 2022, (often well) over half of all papers reporting any methods in Medical and Health Sciences, Agricultural Sciences, Social Sciences, and the Humanitics used linear regression. Indeed, most of the applicd papers cited in the discussion above use linear regression (Angelucci & De Giorgi 2009; Finkelstein et al., 2012 Martinez 2022 Davies et al. 2024 Burton & Roach 2023). We suspect OLS is the most common form of linear regression used in practice.
In the present work, we identify failures to detect. (true) non-robustness in approximations from Broderick et al. ), Kuschnig et al. (0021), Moitra & Rohatgi (2023) and Freund & Hopkins (2023). We are able to identify failures even in lincar regression with a single covariate and an intercept term. In contrast to the two works most similar to our own (Kuschnig et al.| 2021 Hu et al. 2024). we compare to three new OLS--pecific approximations developed by Mootra & Rohatgi (2023); Freund & Hopkins (2023). and we present a theoretical runtime analysis along with an empirical runtime comparison of all methods presented. Importantly, we present new, targeted illustrations of failure modes, each aimed at revealing a specific factor contributing to failure (e-g., & point with extremely high leverage and low residual, small clump of points far away from the rest of the data).
Across worst-case data-dropping approximations, we conclude that a simple greedy algorithm (suggested by Kuschnig et al. (2021) does not fail our accuracy tests (both on synthetic and real-world data), is
2

---

Published in Transactions on Machine Learning Research (07/2025)
conceptually straightforward, and can offer orders of magnitude savings in running time over the OLS-specific mathematical programming alternatives.
Code for our work is available at graaharttacccbaaahpppiiggaaaaaee including all scripts for reproducing the results in this paper.
2 Setup
We first establish notation for OLS analysis paired with worst-case data dropping. The approximations of Moitra & Rohatgi (2023); Freund & Hopkins (2023) require that the data analysis be linear regression fit with OLS, and morcover that the data-analysis conclusion be changed if the sign of regression cocfficient. were to change. To include these methods in our comparison, we focus on this case.
In particular, 1et N be the number of data points. We write the data as di:N == {dn [d where d, == (In, ya) consists of covariates in a column-vector In E R and scalar response yn E R. OLS estimates an unknown column-vector parameter 0 E R² by minimizing a sum of squared losses to a linear trend: i arg ming (yn A )- We will often (but not always) include an intercept term, in which case we think of the Pth covariate as an all-ones covariate.
We focus on conclusions that would be changed if the direction (i.e., sign) of an estimated effect 8, changed. For example, in "Contradicted and Initially Stronger Effects in Highly Cited Clinical Research," " "Toannidis] (2005) describes two studies that initially concluded hormone therapy reduces coronary artery events in women-are and also two larger studies that instead concluded hormone therapy increases coronary artery events; due to the change in sign, Loannidis (2005) counts the first two studies as "contradicted findings." " Similarly, in Mostly Harmless Econometrics, Angrist Pischke (2009) end of Section 2.2) describe conflicting regression analyses that conclude standardized Lest scores increase or decrease, respectively, with class size. As in the examples above, the sign of effect often guides interpretation and decision-making in fields such biomedicine or economics. Indeed, (Gelman & Carlin 2014) argue that Type S (sign) errors (and also Type M, for magnitude, errors) are more relevant for data analysis practice than conventional Type 1 and 2 errors.
We might be concerned if dropping a small fraction a E (0. 1) of our data changed our substantive conclusions. The value of a is user-defined. We follow Broderick et al. (2020) and use a = 0.01 (i.e., 1% of the data) as a default. Broderick et al.] (2020) define the Marimum Influence Perturbation as the largest possible change induced in some quantity of interest by dropping at most 100a% of the data. Since we presently assume conclusions made from the sign of fp, our quantity of interest will always be fp. Without loss of generality, we assume 0, > 0, and we ask whether we can change the result. to a negative sign.
To write the optimization problem implied by the Maximum Influence Perturbation (Equation 1 below), let Wn represent weight on the nth data point, and collect vector of data weights, w := (Wi,..., Wx). Define (ww) == arg ming ΣA wn (n T ( x. Sotting w = 1v, the all-ones vector of length N, recovers the original data analysis, and sebting w, to zero corresponds to dropping the nth point. We collect all weightings that correspond to dropping at most 100a% of the data in Wa = {w {0,1)* Ex=i(1 Wn) < aN). Finally, the Maximum Influence Perturbation for this particular OLS effect-size quantity of interes can be written
max WE
(0,(IN)- ((ll))-0((0 00p(())
(1)
The Most Influential Set is defined to be the set of dropped data corresponding to the maximizing w value.
In principle, one might solve Equation ① by computing (p(w) for each of the (1w7)) values within W.. As detailed in Section I this brute force approach can be computationally prohibitive even for moderate N.
3 Approximations
We next review various approximations to the solution of Equation 1 that are available from the literature. While many authors have considered approximating dropping a pre-defined (single) subset of data from an
See Broderick al. (2020) for more general definition, including other data analyses and other quantities interest..
3

---

Published in Transactions on Machine Learning Research (07/2025)
analysis, we here focus dropping the worst-case subset of data in Equation ( see Appendix A.3 for further discussion of this distinction and related work. We also provide a systematic comparison of theoretical running time costs; an empirical comparison of costs appears in our experiments.
3.1 Additive approximations
We start with what we call additive approzimations. In particular, additive approximations (a) approximate the impact (to a quantity of interest) due to dropping a single data point and (b) add up the individual impacts to approximate the impact of dropping a group of data points.
A Approximate Maximum Influence Perturbation (AMIP). Broderick et al. (2020) propose relaxing w to allow continuous values and replacing the w-specific quantity of interest with a first-order Taylor series expansion with respect to around 1v. This approximation applies to more general data analyses and quantities of interest. In our case (cf. Appendix B.1), this approxination amounts to replacing Equation with
(w)
Σ max WE W..
(1 Wp) Own
w=
Let Ep denote the pth standard basis vector and X E RRP denote the design matrix, where N > P and we assume X is full rank. For OLS with an effect-size quantity of interest, Opp the formula for the influence score of the nth data point is a product of a leverage-like term and a residual term,
06 (w)) Ow,
In (y2 0(IN) 2n).
(3)
w==y
leverage- like torm
rosidual term
For a derivation of Equation For the quantity of interest Op then, the AMIP approximation replaces Equation problem that can be solved by maximizing a sum of influence scores:
18 see Equation 10 in Appendix B.1
[ with an optimization
Σ Em (1- wn)e (x (xx -x-xxx=xnn "mn - 0(1x)) x.n))
max WEW. W.W.
(4)
The AMIP algorithm solves Equation (4p by (a) running the original data analysis, (b) computing the influence scores (Fquation (3), (c) finding the largest [a.]] values, and (d) adding up the influence scores to approximate the impact of dropping the group. The approximate Most Influential Set returned here is preciscly the set of points with the largest |aN]] inftuence scores. The overall cost of rumning AMIP for general data analysis is O(Analysis + N log(aNN + N2 + p&) P where Analysis represents the cost of the data analysis. The cost of rumning OLS is O(N + pa). So, for OLS with an effect-size quantity of interest, the cost of running AMIP is O(N + ps + N log(a:N)).
Additive One-Exact Kuschnig et al. 2021) approximate the change in effect size that results from dropping group of data points OLS by the sum of the impacts of dropping individual points; the idea may be applied more broadly, for more general losses quantities of interest. We call this approach Addilive One-Eract, The broad idea is to (a) compute the exact impact of dropping each single data point the quantity of interest, (b) find the [a:N] data points that, when dropped individually, yield the changes of largest magnitude in the desired direction, and (c) add up those individual impacts to approximate the impact of dropping the group. Here, the approximate Most Influential ial Set returded is the set of [a:] points that, when dropped individually, yield the changes of largest magnitude in the desired direction. For general losses, Additive One-Exace can cost N times the cost of a single data analysis and need not be exact for [aN]> 1. In the special case of OLS with an effect-size quantity of interest, Additive just a single data analysis but still need not be exact for [aN] 1.
requires
When we simultancously consider (a) OLS lincar regression and (b) the effect-size quantity of interest, we observe that Additive One-Exact can be seen as equivalent to another approximation, which we call Additive
2he floor function introduces discrete rounding effects that are negligible in the asymptotic regime; Appendix B.5 more details.
4

---

Published in Transactions on Machine Learning Research (07/2025)
One-step Newton and define in Appendix B.2 Without the " "Additive" descriptor, One-step Newton is popular existing approximation that, in the recent machine learning literature, has been used in estimating the impact of dropping a fixed subset of data (Beirami et al., 2017 Sekhari et al. 2021 Koh et al. 2019; Ghosh et al. 2020). Additive One-stop Newton adds up salle-dtt--oointt approximations from Onc-step Newton; see Appendix B.2 for details. The special case of Additive One-step Newton for logistic regression was first proposed by Park et al. (2023) in the context of data attribution. We hope that our more general formula for Additive One-step Newton provides another angle on extending the Additive One-Exact algorithm to models beyond OLS, to the more general class of differentiable losses.
In the general data analysis setting, the computation of One-Exact scores involves re-running the data analysis upon dropping each individual point in a data set, a cost that is O(N x Analysis). In the setting of OLS, we can take advantage of the One-step Newton update in place of re-running the analysis N times (see Appendix B.2 for more details). Using this rank-one update, the cost of computing One-Exact scores for N data points becomes O(NP3 + PP), or simply O(NPS). Notice the additional P factor relative to the ((N term in the AMIP computation; the improved precision of One-Exact scores over influence scores comes at the cost of this additional factor of P. Specifically, for Additive One-Exact the Hessian matrix is reweighted to account for cach dropped data point (see Equation (17 in Appendix B.2 for the equation for this approximation) while, for AMIP, this reweighting is omitted.
Thus, the general cost of running Additive Exe-Exact is O(N x Analysis + N log(a:N), and the cost specific to OLS with an effect size quantity of interest is O(N p3 + N Nlog(aN)). See Appendix B.4 for more details.
3.2 Greedy approximations
Next we discuss greedy approzimations. Greedy approximations itcratively (a) approximate the change (to the quantity of interest) upon dropping each data point individually, (b) select the point that results in the biggest approximated change when dropped, and (c) re-rum the data analysis without this point (Belsley Section 2.1).
et al.
980
The outlier detection literature has highlighted the combinatorial cost of finding influential subsets exactly. This literature also describes the masking problem that can arise in additive approximations of influence: namely, when one outlier hides the impact of another (Belsley et al., 1980 Atkinson 1986). To address these issues, Belsley et al. (1980) Section 2.1) suggest to greedily remove one outlier point at time in stepwise procedure. Kuschnig et al. (2021) propose a similar greedy procedure for approximating the Maximum Inftuence Porturbation; namely, they iteratively: (a) compute the exact change (lo the quantity of interest) upon dropping each dala point individually, (b) select the point that results in the biggest change when dropped, and (c) re-run the data analysis (Belsley et al. 1980 Section 2.1). In general, Greedy Onc-Exact requires [oN] times the cost of an additive approximation.
Greedy One-Exact.
For a general data analysis, Greedy One-Exact involves running N re-runs of a data analysis for [aN] iterations. Thus, the overall cost of running Greedy One-Exact is O(aN2 Analysis). In the OpS-specifie setting, we can again take advantage of the rank-one update as described for Additive One-Exact. Specifically, to compute One-step Newton scores for N data points costs P(N)²); repeated over [aN] iterations, step (a) costs 2 To find the top One-Fxact score [aN] times, step (b) costs O(aN2). One run of OT.S costs P2 + p²); performed over [aN] J iterations, step (c) costs ((NNP)).
Thus, for OLS with an effect size quantity of interest, the cost reduces to P()N2p'). We find this cost is not prohibitive in our examples below; see Section g for an empirical analysis of running time. See Appendix B.4 for more detailed description of the asymptotic running time analysis just above.
We define Greedy AMIP analogously to Greedy One-Exact, replacing the exact effect of removing a point with the influence score approximation. To the best of our knowledge, Greedy AMIP has not previously been proposed in the literature, for any data analysis or quantity of interest.
Greedy AMIP.
For a general data analysis, running Greedy AMIP costs [aN] times the cost of running AMIP. This cost is O(aN x Analysis + aNV22 + P²). Substituting in the cost of OLS, we find that the cost of running Greedy AMIP for OLS with an effect size quantity of interest is O(aN p2 + P3). See Appendix B.4 for the more detailed description of these results.
5

---

Published in Transactions on Machine Learning Research (07/2025)
3.3 Approximations specific to Ordinary Least Squares with effect-size quantity of interest
A line of recent works provide mathematical programs that give upper bounds on the size of the Most Influential Set for settings of OLS where the quantity of interest is an effect size (Moitra & Rohatgi 2023 Fround & Hopkins 2023). Unlike the additive and greedy approximations, these algorithms do not directly output the approximation of the Maximum Influence Perturbation or the Most Influential Set. Both quantities, however, are straightforward to obtain from the algorithms, we describe next.
AetApprox. The NetApprox algorithm of Moitra & Rohatgi 2023 seeks to find the size of the smallest data subset that, if removed or down-weighted (this algorithm works with fractional data weights), would zero out the sign of a particular regression coefficient.
In order to use the output of NetApprox for the Maximum Influence Perturbation task, we first obtain the fractional data-weights, w := (ui...., WN) where wn E [0, 1), computod using NetApppox [ We set the Approximate Most Influential Set. to be the set of [a.N] points that have the smallest weights (i.e., weights closest to 0) and such that those weights are strictly less than 1 1 We then drop the points in the approximated Most Influential Set and refit the model to find the approximated Maximum Influence Perturbation (i.c., the maximum change in the effect size that can be induced by dropping subset of at most [aN] data points).
In order to make computations tractable, NetApprox works by strategically selecting a "net," a finite number of coefficient vector configurations. For every chosen configuration, the algorithm solves a linear program to determine the minimum number of samples that need to be removed in order to zero out the first regression coefficient. Running NetApprox involves solving O( línear programs; altogether, the runtime for this algorithm is O(PP12 poly(N)).
FH-Gurobi. Freund & Hopkins (023) provide their own implementations of the mathematical program introduced in Moitra & Rohatgi (2023). In particular, the authors implement two versions of this mathematical
program: (1) a fractionally-rellxxt version, where data weights can take values between 0 and 1 (inclusive), and (2) an integer-constraiin
version, where data weights are forced to take on the integers 0 or 1. Both versions are solved using exact solver methods supported from Gurobi 9.0 onwards (specifically, the authors note that these methods apply a globally optimal spatial branch-and- boundd method that recursively partitions the feasible region into subdomains). The paper refers to these two mathematical programs as Gurobi, for the optimization software they were implemented in. For ease of distinguishing this approximation from the commercial optimization software it was implemented in, we refer to the approximation as FH-Gurobi. Freund & Hopkins (2023) found that the
version of FH-Gurobi showed substantially worse performance for their task, so the authors recommend running it with a warm start from the rounded weights obtained using the fractionally-relaxed version.
In the experiments that follow, compare against two versions of the algorithm Freund & Hopkins (023 proposed for the Maximum Influence Perturbation problem. In the first version, which we call FH-Gurobi, we run the integer-oonstrained mathematical program and deem the approximate Most Influential Set as the set of indices with weight 0. If the size of this set is no greater than [aN], we refit OLS upon dropping these points and deem the difference between the original fit and the new fit to be the approximated Maximum Influence Perturbation (i.c., the maximum change in the effect size that can be induced by dropping a subsot of at most [a:N] data points). If the algorithm sets more than [o:N] data weights to O, then we conclude that there does not exist such a subset that can be dropped to change conclusions (i.e., the data analysis is robust). In the second version, which mathematical program, then use those outputs (i.e., the fractional weights) as input to the coneter-constrained mathematical program. We then determine the approximate Most Influential Set and Maximum Influence Perturbation in the same way as we do for the integer-constraiie version.
call FH-Gurobb (warm-start), we first run the fractionally-relaxel
The original NetApprox algorithm computes, but docs not return, the data weights. 'In all of our experiments, NetApprox returned at least [aN] points with weight strictly less than 1, so the question of how to bandle weights equal to 1 did not arise practice.
6

---

Published in Transactions on Machine Learning Research (07 (275))
3.4 Lower bound algorithms
Just as there are algorithms that provide upper bounds on the size of the Most Influential Set, there are algorithms that provide lower bounds (Moitra & Rohatgi 2023 Fround & Hopkins 2023 Rubinstein &
Hopkins 2025 However, we are not able easily determine a Most Influential Set using these algorithms, so
we do not compare to these in the sections below. For more details on these algorithms, see Appendix A.6
4 Failure modes
We start by defining what failure means in the present context, and then we show a range of experiments demonstrating failures for some of the approximations above.
4.1 What failure means here
We consider the data analyst interested in whether their analysis is robust to dropping a small fraction of data. With that in mind, we say that an approximation fails if there truly exists a small fraction of data that can drop to change the conclusions of the analysís, but the approximation reports that such data subset does not exist. For OLS, expect that analysts are willing to ro-run their analysis at least once (after any of the approxinations defined above) with the approximate Most Influential Set dropped, so we are most concerned about the following type of failure.
Definition 4.1. We say there is failure with re-run if (a) there exists a small fraction of data that we can drop to change conclusions and (b) we remove the points suggested by the method and re-run the analysis, but we do not see an actual change in conclusions upon re-running.
The greedy approximations (Section 3.2p and NetApprox (Section 3.3) already require the analyst to re-run their analysis with the suggested points dropped. Both FH-Gurobi algorithms also effectively require re-runs; see Appendix C33 for a discussion of some subtleties. The additive approximations (Section 3.1), however, do not inherently require re-runs of the data analysis. Thus, the additive approximations introduce the potential for additional type of failure, which we define next.
Definition 4.2. We say there is failure without re-run if there exists small fraction of data that can drop to change conclusions, but the approximation reports that such data subset does not exist.
We contrast these notions of failure specific to the problem of drto-iro robustness with alternative notions. For instance, Moitra & Rohatgi (2023); Freund & Hopkins (2023): Rubinstein & Hopkins (2025) Hu et al. (0024) are concerned with exact recovery of the set of data points that, if dropped, change the quantity of interest by the largest amount. However, we note that even 2 data points out of 10,000 can be dropped to change conclusions, a practitioner might be similarly worried to hear that 3 data points can be dropped to change conclusions. Moitra & Rohatgi (2023); Fround & Hopkins (2023 : Rubinstein & Hopkins (2025); Hu et al. (2024) are also concerned with larger a fractions, but locus on 0.01 since small a fractions are the concern of the present form of robustness (see Section 2). Finally Moitra & Rohatgi (2023 are concerned with adversarially constructed data configurations, but we focus on data configurations that
could arise naturally in practice.
Our failure modes focus on underestimation of sensitivity; the data analyst willing to re-run their analysis once, any non-robustness found from that re-run is conclusive. So in this case, overestimation (i.e., a false positive, where the method detects non-robustness when it should not) is not concern.
4.2
One outlier
We start by considering a case with single data point far from the bulk of the data. We find experimental failures in AMPP and FH-Gurobi (without warm start) and support findings with intuition from theory.
7

---

Published in Transactions on Machine Learning Research (07/202) 2225)
x10
10-
10-
15
10
-4-
0.5
-6
-10
-1.5
-1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
-5
10
15
20
25
30
-2.0
-15
-1.0
-0.5
0.0
0.5
x10
AMIP
Additive
Greedy
Greedy
AMIP
Additive
Greedy
Greedy 1Exact
AMIP
Additive
Greedy
Greedy 1Exact
X
X
X
NetAgprox
I8-Gurobi
78-Gurobi (warn-start)
NetApprox
Fil-Gurobi
FilGurobi
NetApprox
Pil-Gurobi
FllCurobi
(wacn-start)
(warn-stact)
X
X
X
Figure 1: Our examples: one-outlier (left), Simpson's paradox (middle), poor conditioning (right). A dashed line represents the OLS-cstimated slope on the entire data set while a solid line represents the slope with black dots removed. The left plot includes an inset zoomed in on the bulk of the data. The tables display the performance of the approximations for the corresponding example: a red X indicates failure with re-rum, and green check indicates succoss.
4.2.1 One outlier experiment
Setup. In realistic data settings, we may have a single data point far from the bulk of the data; this outlier may arise due to data-entry errors, machine-meant measurement errors, or heavy tails in both the covariate and response. To construct the plot in Figure [ (left), draw 1,000 red crosses by taking xn N(0 1) i.i.d. use ((u,a²) to denote the normal distribution
and Y/, - Cn with (0, (,, 1) i.idd. Throughout, with mean and variance o². The black dot appears at yn = 106. We fit OLS with an intercept. The OLS-estimated slope on the full data set is nearly 1; after dropping the black point (less than 0.1% of the data sct), the estimate is nearly -1, representing a sign change.
Experimental Results. We summarize the performance with re-run the left table of Figure When asked find the worst-case 0.1% of the data to drop, Additive is exact for removing single point. AMIP chooses red cross to drop; it predicts that sign change will be achieved, and dropping the chosen point and re-running also does not achieve sign change. It follows that AMPP suffers both types of failure (i.e., with and without re-run) in this example. When considering failure with re-run, there is no distinction between greedy and additive algorithms when [a:]] = 1, so Greedy One- Exact and Greedy AMIP perform the same as their additive counterparts. FH-Gurobi (without warm-start) fails while both NetApprox and FH-Gurobi (warm-start) succeed in this setting. Tn this experiment, failures with and without re-run align for each approximation. We provide more detail on performance Table Appendix C.1
succeeds because, by construction, it
The leverage of the black-dot point must be one in order to construct this failure mode; that is, the black dot must account for most of the variance in the covariance matrix. However, we note that the exact alignment of the black dot on the line such failures when the black-dot point is chosen with yn = cr, for any constant e > 0 and sufficiently large |n We also note that, although Kuschnig al. (2021) have observed that high-leverage obscrvations can lead to problems for the AMIP, they do not demonstrate this result a setting with one outlier or provide supporting theory.
In is incidental. In our theory next, we prove that we can expect
8

---

Published in Transactions on Machine Learning Research (07 (07/2025)
4.2.2 One outlier theory
Our theory illustrates why we might expect AMIP to fail in this one-outlier case. particular, we first demonstrate why a point far from the bulk of the data might have a low influence score. Second, we demonstrate why we might expect other data points to have higher influence scores. Together, these facts suggest why the outlier point might have lower influence score than central points and thereby not be chosen for dropping in the approximation, potentially leading to failure with re-rum.
We do not need to assume any data- data-generating process to prove our results. Rather, we take a single point increasingly far away from the origin. First, observe that, in lincar regression, the influence score factorizes into two terms: the residual times a leverage-like term [Hampel 1974); see Appendix and Equation 3 for full details. A sufficiently-fal outlier will have a very low residual. Mcanwhile we show that the leverage- like term goes to zero as the outlier gets farther away (see Lemma C.2). So sufficiently-far outlier will have a vanishingly low influence score. We let this outlier be the first data point in the result in Proposition below. If this outlier caused all the other influence scores to become vanishingly low as well, it might still have the largest influence. We show this collective vanishing behavior need not happen in Example below; in particular a second data point's influence score does not vanish.
Before stating our results, we introduce some notation relating to fitting OLS on all data points except the first point, which we will take to be the outlier. Let X-1 ((-x)) be the design matrix with the first row deleted, and let y-1 E RN-1 be the response vector with the first entry deleted. Define A-1 = x_ and b-1 == v_,X-1-
Proposition 4.3. Choose any v E TR with |el| = 1 and any constant c> > O. Let (I1,91) = (Au, Ac). Let (In, yn) W2) be any points in Rp x R such that X-1 has rank P. Let Bp denote the pth entry of the OLS estimator, 0, fit without an intercept. Then, for all 1 SPSPP
(0)(w)
lim 06,(1))
st
lim X000
0,
(5)
and
(6)
Owy
1==N
A
Owl
1w=1y
(v_
A
where 8 = (v ne A 32 - eT A {_) and f. (y247 T A_ cu
To - |
A_ 022
A- 822
A
v
b A-1A_ vv A- A_1x2).
Equation (5] is the limiting value of the influence score for the first data point (the outlier). And so Proposition 4.3 tells us that under mild conditions, an extreme outlier has a small influence score. Equation [ is the limiting value of influence score of an (arbitrary) other point in the data set, and we see that it converges. When its limit is not equal to 0, Proposition 4.3 implies that, for extreme enough outliers in the response and covariate directions, the inffuence score of the outlier point will be smaller in magnitude than that of another
point in the data set. Note, when P = 1, is always equal to 0, so the right hand side of Equation (6) is also
0. Next, we give an example (in P > 1) where 8, t + 0, and so the righthand side of Equation 6 is nonzero.
X
0
Xx
Example 1. Consider the data set with X
3
4
y
Suppose we are making a decision based on 3
2
5 6
the sign of the second effect, = 2. In this setting,
(6,(w)
st
lim 000
= 0.0178 > 0.
(7)
Our
1w=1N
(u
A
0)
1
!1 0
[3]
34
42]
Proof. We have v =
c 1, x2
=
1/2 = 2. follows that A- 4
42 52
8
1, 1 3, and
(uT ) = 169.
While these theoretical results are presented without an intercept and our numerical results are fit with an intercept, we find similar failure modes regardless of the inclusion of the intercopt. See Appendix C.2 for a version of the numerical results fit without an intercept and a more nuanced discussion on the impact of the intercept term.
9

---

Published in Transactions on Machine Learning Research (07/ (025))
4.3
Multiple outliers
We next identify two realistic cases with multiple outliers far from the bulk of the data such that the additive approximations and FH-Gurobi (without warm start) fail. We support our empirical findings with thcory. Essentially we see how failure changes if we have small group of outliers instead of just a single outlier.
4.3.1 Simpson's paradox
It is common to have (at least) two noisy subpopulations within a single data set; we consider the case where one subpopulation represents small fraction of the total. For instance, we might have heterogeneity in the population that the regression model does not account for; Simpson's 's paradox describes the case when the trend within subpopulations reverses the trend across the full populations.
Setup. In the particular example in Figure | (middle), the overall slope (across all the data) has different sign than the slope in just the red data or just the black data. To create the illustration in Figure | (middle), we draw 1,000 red crosses with In ~ (N 0.25) i..d., yn = -nn + cas and c, ~ NO0 1) i.i.d. We draw 10 black dots with Ve, ~ ~2,5,, 0.25); Yn = -xn n + 40 + en i.i.d., and en as before. The OLS-estimatedd slope on the full data set 0.52. Dropping the black dots (1% of the data) yields a slope of -0.99, a sign change.
Experimental results. We summarize the performance with re-run in the middle table of Figure [ When asked to find the worst-case 1% (i.e., 10 data points) of the data set to drop, both AMIP and Additive One-Exact choose some red-cross points and some black-dot points to drop; see Table 2 in Appendix C.1 for full detail. Both methods predict there will be no sign change (a failure without re-run). Upon removing the flagged data points and re-running the data analysis, in both cases we find no sign change (a failure with re-run). At extra computational expense, both greedy methods flag exactly the black-dot data points as the points to drop, so neither suffers a failure. At the cost of further increasing compute time, NetAAprox and FH-Gurobi (warm-start) both report that data subset of size 10 exists to flip the sign, while FH-Gurobi without warm-start fails to report the existence of such subset.
Discussion. Once we leave the regime of one data point, we see that both additive methods (AMIP, Additive One-Exact) and FH-Gurobi (without warm start) can fail. We see that errors can arise when we approximate the change in dropping a group of data points by the sum of the changes of dropping individual data points. This phenomenon is known more broadly as masking, where one outlier can hide the effect of another (Belsley et al. 1980 Atkinson 1986). To overcome masking problems, previous work has noted the success of using greedy procedures, both in problems of outlier detection (Hadi & Simonoff, 1993 Lawrance
1995) as well in the problem of identifying the Maximun Influence Perturbation (Kuschnig et al. 2021). Although both of our multi-outlier examples (Simpson's 's paradox here and poor conditioning below) demonstrate the phenomenon of masking, the failure modes we surface are distinct from the simulation studies of Kuschnig ct al. 2021]: ; our examples demonstrate scttings where removing a small fraction of the data can lead to a change in sign of the regression coefficient & failure of the approximation, according to our definition in Section 4 The examples in Kuschnig et al. (2021) demonstrate cases where AMIP can misestimate the change of an effect's magnitude in the face of masking. But those examples demonstrate neither failure without re-rum or a failure with re-run. See Appendix A.5 for more discussion masking.
4.3.2 Poor conditioning
We do not expect that the alignment of data points within the outlier cluster (black dots) in the example above will be germane our results. However, recall that the OLS objective not rotationally invariant in the two-dimensional space defined by single covariate and response. So it is a priori possible for the alignment of the relative trend in the bulk of the data (red crossos) and the trend across the full data to matter. In particular, we next consider a case where the bulk of the data is ill-conditioned on its own.
condly-conditooned data are a common concern to users of OLS regression (Chatterjee & Hadi 1986). Here, we adapt an example presented in Moitra Rohatgi (202)). In the example of Moitra & Rohatgi (2023) ; the data points were constructed to lie perfectly along two straight lines (see Figure 77. Moreover, the small subset of outlier data points lie perfectly along the OT.S-estimated slope for the entire data set. The removal
10

---

Published in Transactions on Machine Learning Research (07/2025)
of the black points causes all variation along covariate space to be lost and the OLS solution to become ill-defnnd.
Setup. We alter the adversarial setup of Moitra & Rohatgi 2023) into one that might arise in natural data settings with no adversary (see Figure 1 (right)). ) To that end, we add generous amounts of noise to both red-cross points and black-dot points and translate the black-dot points to no longer lie along the OLS-estimated slope. We generate the red crosses so as to have poor conditioning; since there is much more noise around the (zero) trend than variation in the covariates, there is no clear regression solution. In particular, we generate the 1,000 red crosses with En (0, iid., Vn En, and cn N/ 1) i.d. We draw the 10 black dots as In, ~ ~~((-10000 i..dd., Vn -En - 10 Cn, and en as before. When we consider both black dots and red crosses together as a single data set, there is no poor conditioning. The OLS-estimated slope on the full data set is around 7.40; dropping the black dots (1% of the data) yields a slope of about -1.04, a sign change.
Experimental results. We summarize the performance with re-run in the right table of Figure | We ask each method whether it is possible to drop at most 1% (10 data points) of the data set and change the sign of the effect. Both AMIP and Additive One-Exact choose some red crosses and some black dots; see Table 3 Both methods in turn suffer failures with and without re-run. The greedy methods are more computationally expensive but succeed. NetAAprrx and FH-Gurobi (warm-start) both report that a data subset of size 10 exists to flip the sign, while FH-GGuobb without warm-start fails to report the existence of such a subset.
4.3.3 Theory
A common theme in multi-outlier examples is that, in general, the impacts of data-dropping are non- additive. Our theory illustrates that, even in simple sctup, data points can mask cach other's impacts. In particular, our theory shows we can have masking issues even in OLS with just. a single covariate and no intercept, and even between just two outlier data points. The issues in our one-outlier theory (Proposition 4.3 could be overcome by using a One-Exact method. But our next results show that Additive One-Exact falls prey masking issues.
Proposition 4.4. Let X, c R. Consider pair of data points, (I1, (A, and (x2, y2) = (A, Let (In, Ba) be any points in R x R such that at least one of (Ir) is non-zero. We apply OLS to the single covariate x and response y with no intercept; we make a decision based on the sign of the resulting effect size. As A + 00, the Additive Ene-Exact opprozimation (Section 3.1) to the change in effect size from dropping (11, 31), (2), tends to zero, while the true change in effect size tends to (E Inynn/ E
In the setup of Proposition 4.4 P = 1, and there is no intercept. So the assumption that at least one of (xn 3a is non-zero is equivalent to an assumption that the design matrix with the first two points removed is full rank. That is, the assumption ensures the OLS solution remains well-defined after dropping the first two data points. See Appendix C.7 for the proof of Proposition
Proposition 4.4 that, as a pair of points taken to infinity logether, the sum of their individual impacts (i.e., the change in effect size from dropping each point individually) always approaches zero, regardless of what the group impact (i.c., the change in effect size from dropping the pair together) approaches. Indeed, the impact of dropping the group may result in substantive change in effect size, information that cannot be gleaned solely from looking at individual impacts.
While the theory in this section is presented without an intercept term, we find that the exclusion of the intercept has very little effect on the numerical results presented in Section 4 In particular, we run versions of the numerical results fit. without an intercept term in Appendix C.2 and find little difference.
4.4 Greedy failures
Moitra & Rohatgi (2023) Section 5.1) construct failure mode of greedy approximations an adversarial way. We find it helpful to visualize their (text) construction; see Figure 7 in Appendix C.7.2 We surface similar adversarial examples where greedy algorithms fail; see Figure and Figure
But we have yet to
11

---

Published in Transactions on Machine Learning Research (07/202) 2025)
5
32
700
Price ($1000s)
30-
600
3-
500
400
2-
300
24
22
0-
20
-1
100
200 300 400 sáo 660 700 a00
22
24
26
28
30
32
14
Vip
Pool Area sq (t)
Head
AMIP
Additive 18xact:
Greedy AMIP
Greedy 1Exact
AHIP
Addiitive tive 1Exact:
Greedy AMIP
Greedy 18xact
ANIP
Additive 1Rxact
Greedy AMIP
Greedy 1Exact
X
X
X
NetApprox
18-Gurobi
F8-Gurobi (Marn-stert)
XetApprox
FH-Gurobi
Pg-Gurobi (wazn-stezt)
NetApprox
Ill-Guobii
Il-Gurobi (vacn-staatt)
X
X
X
X
Figure 2: Our examples: Single-cell Genomics (left), Ames Housing (middle), Bird Morphometrics (right), A dashed line represents the OLS-cstimated slope on the entire data set while solid line represents the slope with black dots removed. We do not plot fitted models for the Bird Morphometrics data since the regression involved two additional covariate dimensions. The tables display the performance of all approximations for the corresponding example: a rod indicates a failure with re-run, and a green check indicates a success.
identify realistic, non-adversarial examples of greody failures beyond the dropping of a single data point. Furthermore, we were unable identify any realistic failures Greedy One-Exact.
5 Examples in real-world data
We next illustrate failures in real-data analyses. We able to surface failures in real-data analyses for all but the greedy approximations. We also illustrate various real-data analyses where all methods succeed in Appendix C.4 In each of the following real-world examples, we know that we can drop less than 1% of the data and change the sign of the OLS regression coefficient since at least one method successfully identifies such a set. We check whother all methods do so.
The Single-cell Genomics and Ames Housing data sets demonstrate multi-outlier failure modes, while the Bird Morphometrics example demonstrates one-outlier failure mode.
5.1 Single-cell Genomics
Setup. Our first data set. is taken from study on the impact of sensory experiences gene expression in the mouse visual cortex (Hrvatin et al. 2018). The data set contains total of 65,539 points. As is common in gene expression data, these data are heavily zero-inflated; 99.5% of the Vip gene values (shown on the x-axis in Figure 2 (left)) are O, and 97. 97.39% of the Gadl gene values (shown on the y-axis) are Practitioners are often interested in the association between two genes. We consider a linear regression (with intercopt) of Gadl values on Vip values.
This data analysis is not robust to dropping 1% of the data. In particular, there exists subset of size 172 (0.26% of the data) that, when dropped, can change the sign of the regression coefficient from positive (0.536)
to negative (-0.003). We plot these 172 points as black dots in Figure 2 (left). We plot the remaining points of the data set as red crosses. Note that, due to zero-inflation, many data points are stacked at (0,0).
Experimental results. We summarize the performance with re-run in the left table of Figure 2 We ask each method whether is possible drop most 1% (656 data points) of the data and change the sign of the effect. Both AMIP and Additive
predict there will be sign change (a failure without.
12

---

Published in Transactions on Machine Learning Research (07 (07/2025)
re-run). Upon removing the flagged worst-case 1% of data points and re-running the data analysis, in both cases we still find no sign change (a failure with re-run). Both of the greedy methods, however, successfully identify 172 data points to drop to change the sign, so neither suffers a failure. NetApprox also successfully identifics such a set. FH-Gurobi returns a set of size 1712 to drop, which is larger than 1% of the data, so it fails here. Interestingly, FH-Gurobi (warm-start) does successfully identify a set of size 172 points to drop, but the subset it returns incorrect that, when dropped, the regression coefficient still greater than (it was 0.00150), and thus no sign change is detected. See Table in Appendix C.1 for full details.
5.2 Ames Housing
Setup. The Ames Housing data set provides a comprehensive collection of residential property data from Ames, Iowa, and is a widely utilized data set for regression modeling exercises (De Cock 2011). The response variable here is SalePrice, the final selling price of each home, while the covariates consist of building, land, and facility characteristics. We perform onc-dimensional lincar regression (with intercept) of SalePrico on the pool area covariate (i.e., the pool area of each property in square feet). The training data set on Kaggle contained 1,460 points.
This data analysis is not robust to dropping 1% of the data. Dropping 4 out of the 1,460 (0.27%) points changes the sign of the regression coefficient. from positive (182.71) to negative (-15.09). In Figure 2 (middle), we plot the four points as black dots, and the rest of the data set we plot as red crosses.
Experimental results. We summarize the performance with re-rum in the middle table of Figure 2 When asked if is possible to drop at most 1% (14 data points) of the data and change the sign, both AMIP and Additíve One-Exact predict that there will be sign change (a failure without re-rum). Upon removing the flagged worst-case 1% of points and re-running OLS, in both cases still find no sign change (a failure with re-run). Both of the greedy methods, however, successfully identify 4 data points to drop to change the sign, so neither of these greedy methods fails. All of the OLS-specific methods succeed. See Table in Appendix C.1 for full details.
5.3 Bird Morphometrics
Sctup. This data set is taken from ccological study the morphometric features of the saltmarsh sparrow Ammodramus candaculus (Zuur et. al. 2010). Ecologists commonly use linear models to understand the association between animal features. The outlier in this data set may be a different species, a typing mistake, or indeed correct record (Zuur et al. 2010).
The original data set contains 1,295 points. Tn order for data point to account for roughly 1% of the total, we sampled 10% of the full data (129 points) uniformly at random without replacement; happened that our first random sample retained the outlier point, so we kept this single sample. Then, we ran OLS regression (with intercept) on the features "head" (head length), "wingerd" (wing length), and "culmen" (beak length). Removing just the single black-dot point (0.77% of the data) in Figure 2 (right) ) is sufficient to change the sign of the regression coefficient for "head" from negative (-0.69) to positive (0.399). We plot the remainder of the data set we consider as red crosses.
Experimental results. We summarize the performance with re-run in the right table of Figure 2 When asked to find the worst-case 1% of the data to drop, both AMIP and Additive One-Exact succeed, as do both greedy approximations. Net.Approx, however, does not identify the point that, when dropped, changes
13

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
3500
Q AMIP
Additive 1Exact
200
3000
O
Greedy AMIP
time (in seconds)
V
Greedy 1Exact
NetApprox
2500
FH-Gurobi
A4
2000
0
FH-Gurobi (warm-start)
0
50
1500
1000
500
0
0
0
10
20
30
40
50
dimension size
Figure 3: Plot of approximation runtimes on simulated data set of size N 75,000. We omit results that take over one hour to run; in particular, FH-Gurobi (warm-start) takes over one hour on dimension sizes 10 or larger. The plot includes an inset zoomed in on algorithms that run in under 200 seconds (i.e., the greedy and additive algorithms, as well as particular settings of FH-Gurobi without warm start).
the sign. Similarly, both versions of FH-Gurobi fail here, with each choosing a different subset of 4 points to drop. Since the subset identifiod > 1% of the data, both constitute failure
6 Runtime comparison
We next compare running times across approximations. In addition to being the sole algorithm that did not fail any our tests, we find that Greedy One-Fxact can be orders of magnitude faster than the OLS-specific approximations. All experiments were conducted in Python on a personal computer equipped with an Apple M1 Pro CPU at 3200 MHz and 16 GB of RAM.
Setup. We simulate data sets of size N = 75,000, and we vary dimension P up to P 50. We choose both N and P to be larger than those of any data set considered by Broderick et al. (020) and any data set in the present paper. Let Ip denote the identity matrix of dimension P and 1p denote the the one-vector of dimension P. We draw samples with In (0, ii.d. yr. = (In, 1p) + En, and en ~ ~M i.dd
Results. We show the runtimes of different approxinations in Figure 3 The additive algorithms (AMIP and Additive One-Exact) run the fastest for all dimensions. At dimension P = 50, AMIP runs for 0.03 seconds and Additive One-Exact for 0.05 seconds. The greedy algorithms are the next fastest. At dimension P 50, Greedy AMIP runs for just over minute (62.84 seconds) and Greedy One-Exact for 75.54 seconds. The third fastest is FH-Gurobi without warm-start. At P = 50, this algorithm runs for 238. 20 seconds, or just under 4 minutes. NetApprox and FH-Gurobi (warm-start) are substantially slower than the other algorithms. At P = 50, NetApprox runs for 3589.93 seconds (just over 59 minutes). P = 10, the FHH-urobi (warm-start) algorithm is unable to run in under hour; it ran for 3968.39 seconds, or just over 66 minutes. We are unable run FH-Gurobi (warm-start) for dimensions much larger than 10 in our time budget. Notably, in the present experiment, Greedy Ono-Exact can be over 47 times faster (at P = 50) than the OLS-specific methods.
When running ID version of OL.S (fit with intercept) on the bird morphometrics data with head length as the sole predictor, all methods are able succeed.
14

---

Published in Transactions on Machine Learning Research (07/ (225)
7 Discussion
In the present work, we identify non-adversarial failure modes of approximations to the Maximum Influence Perturbation. We focus on linear regression fit with ordinary least squares and where the decision is made based on the sign of an effect. For users interested in the Maximum Influence Perturbation for this case, we recommend the following: (1) running Greedy One-Exace if the user is willing to incur the computational expense and (2) that users visualize their data with diagnostic plots (c.g., scatter plots, leverage plots, residual plots). Our recommendation of Greedy
agrees with that of Kuschhig et al. (2021). though the notion of failure guiding our comparison is different.
Across our experiments, we find that Greedy One-Exact is able to succossfully detect non-robustness when laced with both synthetic and real-world data examples. Additionally, we find that it is orders of magnitude faster than the OLS- approximations on plausibly-sized data sets. Our experiments suggest that, for data sets with N S 75,000 and P S 50, Greedy One-Exact should not take much longer than a minute to run; we believe this rumning time cost should not be prohibitive for users. Moreover, Greedy One-Exact is conceptually straightforward and should be straightforward to implement in practice; unlike Net and F1H-Gurobi, it does not require the use of commercial software that may not be accessible to all users.
Since NetApprox and FH-Gurobi were originally designed to estimate upper bounds on the number of points that must be removed to induce a sign change a regression coefficient, it not surprising that these algorithms might struggle with identifying a particular small subset of data points to drop to achieve a sign change. For example, in the bird morphometries dataset, NepApp accuralely estimates the number of points that need to be dropped but fails to pinpoint the specific data point whose removal flips the sign. A similar issuc arises with FH-Gurobi (warm-start) on the single-cell genomics data. Additional failure cases for both FH-Gurobi variants can be altributed to the looseness of the returned upper bounds.
While the additive methods also fail our tests, we note that AMIP can be over 2500 times faster than Greedy One-Exact in our experiments here with N 75,000, smaller compute-ting time budgets may still find useful to run additive approximations if the Greedy One-Exact becomes prohibitive in cost. We find that the additive methods (AMIP, Additive One-Fxact) tend to fail in the presence of points with extreme leverage scores, as seen in the scatter plots in Figure [ and in the residual-leverage plots in Figure G While AMIP may not be able to detect such non-robustness, a simple visualization of the data certainly would. This finding further highlights the importance of visualizing the data alongside running data-dropping robustness checks.
50. Users with larger problems (in N or P) and
Not only is linear regression widely used in practice, but we believe that finding approximation failure modes in such a simple and intuitive analysis should lead us to suspect failure modes in more complex analyses until proven otherwisc. It remains to investigate how alternative models (beyond low-dimensional lincar regression) might interact with different data arrangements to affect approximation qualily. Geometries of interest include those arising from high-dimensional covariates, generalized linear models (and other cases with constrained residuals), constrained parameter spaces (e.g., for variance parameters) @ mixed-effect models (related to Bayesian hierarchies) and other more-complex models. Across our synthetic and real-world data sets, we find that the leverage scores of the black-dot points are extremely large; see Figure F Higb-leverage points may not have the same impact on an analysis under alternative geometries. Moreover, it remains to investigate approximation performance for decisions beyond the sign of an OLS-lcarned effect; for instance, decisions based statistical significance or Bayesian posterior means and variances are especially widespread. Finally, it remains to investigate the speed and accuracy trade-offs in additive and greedy approaches for data analyses more computationally expensive than the low-dimensional linear regression examples considered here; there exist many cases where a practitioner is not willing to re-rum their data analysis [aN] times.
Thhis geometry was flagged challenging in Broderick et al. 2020
Section 4.4.2).
7hhis geometry was flagged potentially challenging in guueen el al. 2024 Section 6.3).
15

---

Published in Transactions on Machine Learning Research (07 (025))
Acknowledgments
This work was supported in part by ONR Early Career Grant, the MIT-IBM Watson Al Lab, the NSF TRIPODS program (award DMS-2022448), and a AlchhnedecriinAAppiccotoiSSSSSSS grateful to Tom Rainforth, Vishwak Srinivasan, Ittai Rubinstein, and Ryan Giordano for helpful discussions.
Seed Award. We are
References
Manuela Angelucci and Giacomo De Giorgi. Indirect effects of an aid program: how do cash transfers affect incligibles' consumption? American Economic Review, 99(1):886-508, 2009.
Joshua D. Angrist and Jörn-Steffen Pischke. Mostly harmless econometrics: An empiricist's companion. Princeton university press, 2009.
AC Atkinson. Masking unmasked. Biometrika, 73(3):533 541, 1986.
Ahmad Beirami, Meisam Razaviyayn, Shahin Shahrampour, and Vahid Tarokh. On optimal generalizability in parametric learning. Advances in Neural Information Processing Systems, 30, 2017.
David A. Belsley, Edwin Kuh, and Roy E. Welsch. Regression diagnostics: Identifying Inftuentiol Data and Sources of Collinearity. John Wiley & Sons, 1980.
SM Bendre. Masking and swamping effects on tests for multiple outliers in normal sample. Communications in Slalistics- Theory and Melhods, 18(2):697-77) 710, 1989.
Olivier Bousquet and André Elisscoff. Stability and generalization. The Journal of Machine Learning Reseorch, 2:499-54 526, 2002.
Fric T. Bradlow and Alan M. Zaslavsky. Case influence analysis in Bayesian inference. Journal of Compula- tional and Graphical Statistics, 6(3):314 331, 1997.
Tamara Broderick, Ryan Giordano, and Rachael Meager. An automatic finito-sample robustness metric:
When can dropping little data make big difference? arXiv preprint arXiv:2011.44999v. 2020.
Anne M. Burton and Travis Roach. Negative externalities of temporary reductions in cognition: Evidence from particulate matter pollution and fatal car crashes. Technical report, University of Texas at Dallas, 2023. Working Paper,
Roach Pollution. pdf
Bradley P. Carlin and Nicholas G. Polson. An expected utility approach to influence diagnostics. Journal of the American Statisticol Association, 86(416):1013 1021, 1991.
Andrés F. Castro Torres and Aliakbar Akbaritabar. The use of linear models in quantitative rescarch. Quantilative Science Studies, pp. 1 1-21, 2024.
Samprit Chatterjee and Ali S. Hadi. Influential observations, high leverage points, and outliers linear regression. Statistical Science, pp. 379 393, 1986.
Samprit Chatterjee and Ali S. Hadi. Sensitivily analysis in linear regression. John Wiley & Sons, 1988.
R. Dennis Cook. Detection influential observation in linear regression. Technometrics, 42(1):65 68, 1977.
R Dennis Cook. Assessment of local influence. Journal of the Royal Statistical Society Series B: Statistical Methodology, 48(2):133-155. 1986.
Elwyn Davies, Peter Deffebach, Leonardo lacovone, and David McKenzie. Training microentrepreneurs over
Zoom: Experimental evidence from Mexico. Journal of Development Economics, 167:103244, 2024.
Dean De Cock. Ames, Iowa: Alternative the boston housing data as an end of semester regression project.
Journal of Statislics Education, 19(3), 2011.
16

---

Published in Transactions on Machine Learning Research (07/2025)
Michael Di and Ke Xu. Covid-19 vaccine and post-pandemic recovery: Evidence from bitcoin cross-asset implied volatility spillover. Finance Research Letters, 50: 10328,, 2022.
Amy Finkelstein, Sarah Taubman, Bill Wright, Mira Bernstein, Jonathan Gruber, Joseph Newhouse, Heidi Allen, Katherine Baicker, and the Oregon Health Study Group. The Oregon health insurance experiment: evidence from the first year. The Quarterly Journal of Economics, 127(3):0057-1106, 2012.
Ronald A. Fisher. Statistical Methods for Research Workers. Oliver and Boyd, Edinburgh, UK, 1st edition, 1925.
Daniel Freund and Samuel B. Hopkins. Towards practical robustness auditing for linear regression. arXiv preprinl ar Xiv:2307. 16315v1, 2023.
Andrew Gelman and John Carlin. Beyond power calculations: Assessing lype (sign) and type m (magnitude) errors. Perspectives on psychological science, 9(6):641 651, 2014.
Amirata Ghorbani and James Zou. Data Shapley: Equitable valuation of data for machine learning. In International Conference on Machine Learning. PMLR, 2019.
Soumya Ghosh, Will Stephenson, Tin D. Nguyen, Sameer Deshpande, and Tamara Broderick. Approximate cross-validation for structured models. Advances in Neural Information Processing Systems, 33:8741 8752, 2020.
Ryan Giordano, William Stephenson, Runjing Liu, Michael Jordan, and Tamara Broderick. A Swiss Army infinitesimal jackknife. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1139-1147. PMLR, 2019.
J. Brian Gray and Robert F. Ling. K-clustering as a detection tool for influential subsets in regression. Technometries, 26(4):305 318, 1984.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In International Conference Machine Learning, pp. 1832-3842 PMLR, 2020.
Ali Hadi and Jeffrey S. Simouoff. Procedures for the identification of multiple outliers in linear models. Journal of the American Statistical Association, 88(424):1264 1272, 1993.
Frank R. Hampel. The influence curve and its role in robust estimation. Journal of the American Statistical Association, 69(36)) 1974.
Sinisa Hrvatin, Daniel R. Hochbaum, M. Aurel Nagy, Marcelo Cicconet, Keiramarie Robertson, Lucas Cheadle, Rapolas Zilionis, Alex Ratner, Rebeca Norges-Mouroy, Allon M. Klein, Bernardo L. Sabatini, and Michael E. Greenberg. Single-cell analysis of experience-dependent transcriptomic states in the mouse visual cortex. Nature neuroscience, 21(1):120-13) 129, 2018.
Yuzheng Hu, Pingbang Hu, Han Zhao, and Jiaqi W. Ma. Most influential subset selection: Challenges, promises, and beyond. In Advances in Neural Information Processing Systems, volume 38, 2024.
Andrew Tlyas, Sung Min Park, Logan Engstrom, Guillaume Leclere, and Aleksander Madry. Datamodels: Predicting predictions from training data. In International Conference on Machine Learning, PMLR, 2022.
John P.A. loannidis. Contradicted and initially stronger effects in highly cited clinical research. juma, 294(2):
218-228, 2005.
Louis A. Jacckel. The infinitesimal jackknife, memorandum. Technical report, Bell Lab, 1972.
Wesley Johnson and Scymour Gcisser. A predictive view of the detection and characterization of influential observations in regression analysis. Journal of the American Statistical Association, 78(381):137-144, 1983.
Pang Wei Koh and Percy Liang. Understanding black- box predictions via influence functions. In International Conference Machine Learning, pp. 1885-1894. PMLR, 2017.
17

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Pang Wei Koh, Kai-Siang Ang, Hubert H.K. Teo, and Percy Liang. On the accuracy of influence functions for measuring group effects. Advances in Newral Information Processing Systems, 32, 2019.
Nikolas Kuschnig, Gregor Zens, and Jesús Crespo Cuaresma. Hidden in plain sight: Influential sets in linear models. Technical report, Vienna University of Economics and Business, 2021. CESifo Working Paper, attp://dxk doi. 1o0/0.0011..... 0tt9///snn.8191000
A.J. Lawrance. Deletion influence and masking regression. Journal of the Royal Statistical Sociely Series B: Statistical Methodology, 57(11:1811 189, 1995.
Allen Liu and Ankur Moitra. Learning GMMs with nearly optimal robustness guarantees. In Conference Learning Theory, pp. 2815-2895. PMLR, 2022.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. The 6th International Conference on Learning Representations (ICLR 2018), 1050(9), 2018.
Luis R. Martincz. How much should we trust the dictator's GDP growth estimates? Journal of Political Economy, 130(10):2731 2769, 2022.
Ankur Moitra and Dhruv Rohatgi. Provably auditing ordinary least squares in low dimensions. The 11th International Conference on Learning Representations (ICLR 2023), 2023.
Tin D. Nguyen, Ryan Giordano, Rachael Meager, and Tamara Broderick. Using gradicnts to check scnsitivity of MCMC-based analyses to removing data. In ICML 2024 Workshop Differentiable Almost Everylhing: Differentiable Relazations, Algorithms, Operators, and Simulators, 2024. URL httts://opeerevieee net// net/
forum?id forum?1dd+GPANVcq3M
Sung Min Park, Kristian Georgiev, Andrew Iyys, Guillaumc Leclere, and Alcksander Madry. TRAK: Attributing model behavior at scale. In International Conference on Machine Learning, pp. 27074 27113.
PMLR, 2023.
Daryl Pregibon. Logistic Regression Diagnostics. The Annals of Statistics, 9(4), 1981.
Kamiar Rad and Arian Malcki. A scalable estimate of the out-of-sample prediction error via approximate leave-one-out cross-validation. Journal of the Royal Statistical Sociely, Series B, 82(4):965 996, 2020.
Ittai Rubinstein and Samuel Hopkins. Robustness auditing for linear regression: To singularity and beyond.
The 13th International Conference on Learning Representations (ICLR 2025), 2025.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithus for machine unlearning. Advances in Neural Information Processing Systems, 34:18075-18086, 2021.
William Stephenson and Tamara Broderick. Approximate cross- crossvaaldation in high dimensions with guarantees. In International Conference on Artificial Intelligence and Statistics, pp. 2424-2422 2434..44. PMLR, 2020.
Vinith Suriyakumar and Ashia C. Wilson. Algorithms that approximate data removal: New results and limitations. Advances in Neural Information Processing Systems, 35:18892-18903, 2022.
Fernando Valladares, S. Joseph Wright, Eloisa Lasso, Kaoru Kitajima, and Robert W. Pearcy. Plastic phenotypic response to light 16 congeneric shrubs from a Panamanian rainforest. Ecology, 81(7): 1925 1936, 2000.
Robert A. York. BAAD: biomass and allometry database for woody plants. Ecology, 96(5), 2016.
Hongtu Zhu, Joseph G. Ibrahim, Sikyum Lee, and Heping Zhang. Perturbation selection and influence measures in local influence analysis. Annals of Statistics, 35(6):2565 -5888, 2007.
18

---

Published in Transactions on Machine Learning Research (07/)025)
Hongtu Zhu, Joseph G. Ibrahim, Hyunsoon Cho, and Niansheng Tang. Bayesian case inffuence measures for statistical models with missing data. Journal of Compulational and Graphccal Statislães, 21 21(1):253 2212277,, 2012.
Alain F. Zuur, Elena N. Icno, and Chris S. Elphick. A protocol for data exploration to avoid common statistical problems. Methods in ecology and evolution, 1(1::3 14, 2010.
A Related works
A.1 Related notions of robustness
In this section, we discuss related notions of robustness and explain why robustness to worst-case data dropping provides a new and useful check on generalizability. Many tools in statistios, such as p-values and confidence intervals, are meant to measure the generalizability of sample-baser based conclusions (Fisher) 1925 Similarly, works on algorithmic stability in the learning theory literature quantify an algorithm's 's generalization error (Bousquet & Elisseeff 2002). However, these tools rely on an assumption that the data are drawn independently and identically (i.i.d.) from the underlying larget population. In most real world settings, we cannot assume the population that the samples are drawn from is identical to the target population. For instance, we might look to apply the conclusions from a specific sample to a slightly different future population. Departing from the i.i.d. regime, we can no longer rely on the theory behind classical tools alone to tell us something definitive about the generalizability of sample- based conclusions. Prior works have also studied the robustness of estimators to gross outliers and adversarially corrupted samples, arbitrary corruptions of a data-point or small collection of data points (Hampel 1974 Madry et al., 2018 Liu & Moitra 2022)- The influence function has played central role in the study of gross outlier sensitivity since the pioneering work of Hampel (1974). Specific to linear regression, Cook 1977 introduced Cook's Distance, for detecting outliers and gross errors. However, conclusions may still fail to generalize in the absence of gross outliers (Broderick et al. 2020). As these related notions of robustness alone do not provide a comprehensive check, a data analyst might still worry about generalizability if dropping a very small fraction of the sample can lead to drastically different conclusions.
A.2 Computational difficulties of determining robustness to worst-case data dropping
An exact computation of the Maximum Influence Perturbation is computationally intractable. A brute force approach involves enumerating over every possible data subset, which amounts to rerumning ( ([oN) data analyses, where N is the number of points in the dataset. Inspired by the Maximum Influence Perturbation
problem, Moïtra & Rohatgi (2023): ; Freund & Hopkins (2023) y
Rubinstein & Hopkins 2025 tackle a slightly
different but related problem, one of finding the minimum number of samples (in a fractional sense) that need to be removed to zero out a particular regression coefficient. For OLS regression, Moitra & Rohatgi (2023
Theorem 1.3) shows that there is no No(P) time algorithu that, given a non-negative integer k, can determine whether the minimum number of samples that need to be dropped to zero out regression coefficient is less than or equal to { More specifically, Mooira & Rohatgi (2023) shows that this problem requires N time. Although their complexity result applies to the slightly different problem of determining the minimum number that need to be dropped to change the sign of the regression coefficient, this hardness result also applies to our problem of determining the existence of a subset of size at most 100a% of the data that can be dropped to change the sign. Consider the following reduction. Suppose there existed an algorithm that solves the existence problem in faster than (T((P) computations. Specifically, for some l less than 100a% of the data, the algorithm determincs the existence of a subset of size at most i that can be dropped to change the sign of the regression coellicient. If such an algorithm were to exist, we could run it for k [1, [a.N] ]] (an operation that is O(N)) to determine the minimum number of samples required to be dropped to zero out the regression coefficient. The existence of such algorithm would contradict Moitra & Rohatgi 2023 Theorem 1.3), which shows that such a task requires at least (PP() computations. Thus, determining robustness to
Moitra & Rohatgi (2023 worked with fractionally relaxed version of this problem, where the weight of a data point can take on non-integer values. This result precludes the existence of faster solution the integer version, as one could the integer version solve the weighted version (up to an approximation) by making several copies of the dataset.
19

---

Published in Transactions on Machine Learning Research (07/2025)
small-fraction data-dropping is expensive, even in the simple setting of OLS linear regression. This prompts the need for approximations.
A.3 Approximations to (non-worst-case) data dropping
In this section, we discuss langential works that use approximations to data dropping in settings where the subset to drop is known. Since we are concerned with developing algorithms to overcome the combinatorial problem of searching for some worst-case subset to induce the largest change in a quantity of interest, the works discussed in this section do not provide a fast way to search for the worst-case data subset to drop.
The idea of using approximations to data dropping goes as far back as Jacckel (1972) and Hampel (9774). who
introduced the influence function in the context of robust statistics. Shortly after, Cook (1977) introduced inffuence measures, such Cook's Distance, in the context of detecting outliers and gross errors. Pregibon (981) introduced the One-step Newton approximation in the context of logistic regression diagnosties.
As models become increasingly expensive to run and datasets increasingly large, data-dropping approximations have gained popularity in several areas of machine learning. Many works have developed gradient based
approximations for cross validation (Beirami et al. 2017 Rad & Maleki 2020 Giordano et al. 2019
Stephenson Broderick 2020; Ghosh ct al. 20200) Works in the data privacy space have used approximations
for deleting user dala from models (Guo el al. 2020: Sekhari el al.) 2021 Suriyakumar & Wilson 2022
Within the model interpretability and data attribution space, methods such Shapley value estimators [Ghorbani & Zou 2019 and datamodels (Ilyas et al.,
2022) require retraining the model a large number of times on different subsets of the data in order to quantify the impact of particular training points on the model output. In response, several works have proposed using approximations to retraining based on the
influence function (Koh & Liang 2017 Koh et al.) 2019 Park et al.) 2023). These gradient- based based approximations achieve great gains in computation while maintaining comparable accuracy to methods that rely on model retraining, as shown in Park et al. 2023 Figure 1). While these works (Koh & Liang) 2017 Koh et al. 2019 Park et al.) 2023) investigate the performance of data dropping approximations for the task of dropping & pre-defined subset, we investigate the performance of data-dropping approximations for the task of dropping a worst-case data subset. The performance of an approximation may be quite different on an average-case compared to the worst-case data subset.
A.4 Case Influence Analysis
The case influence analysis literature studies the importance of individual or groups of cases (data points)
on posterior dist.riuttions (Bradlow & Zaslavsky 1997: Carlin Polson 1991 Zhu et al. 2012), predictive distributions (Johnson & Geisser 1983), and likelihoods [Cook 1986;
Zhu et al. 2007). Like the recent works Kuschnig et al. 2021). these works use
Maximum Influence Perturbation (MIP) (Broderick et al. 2020
first-order approximations to avoid re-running a full model; while the broad aim of both lines of work is to
assess the impact of deleting cases on inferential results in data analysis, there are handful of notable distinctions between these works.
Works that develop approximations to the MIP propose algorithms to solve the optimization problem of searching for the worst-case data subset, Le. the subset of data whose removal maximally changes some user- specified inferential quantity. Works in the case influence literature do not present solutions this worst-case data-subset search. Rather, the case influence literature focuses on the impact of deleting observations that are specified in advance. While Zhu et al. (2012) Theorem 2) uses first-order approxination that appears to asymptotically treat the case of dropping non-vanishing proportion of the data, Theorem 2 is proved for a particular dropped subset, rather than a uniform bound over all subsets of a particular size, a key property allowing AMIP to approximate the deletion of the worst-case data subset. This is again shown in simulation studics, where Zhu et al. (2012) work with pre-specified subsots, namely those obsorvations within a group in a Bayesian hierarchical model, and compares the posterior summary statistics obtained after deleting these subsets to those on the full data.
20

---

Published in Transactions on Machine Learning Research (07/2025)
Furthermore, works in case influence typically concern whole-model sensitivity metrics- likelihood function [Cook] 1986 Zhu et al.) 2007), posterior distribution (Zhu et al. 2012), and predictive distribution (Johnson & Geisser 1983), rather than a particular inferential quantity, such as a particular OLS regression coefficient. Sensitivity of a single regression coefficient is not sufficient to imply scnsitivity to more global objects, like the entire vector of coefficients. Works on approximations to the MTP instead let the analyst specily any inferential trrget-often a single quantity that drives a data analysis conclusion, such as the sign or significance of one OLS coefficient and asks how fragile that quantity of interest is to worst-case data deletion.
A.5 Masking
We identify cases where masking, a situation where one outlier "hides" the effect of another outlier, can interfere with finding the Most Influential Set. Masking itself has been a widely studied phenomenon in the context of multi-outlier detection. Hampel (1974), foundational text in robust statistics, notes that masking can make the identification of multiple outliers cumbersome and erroneous (Hampel) 1974 Section 1.4). Belsley et al.) [1980] Section 2.1) also discussed the masking phenomenon and proposed a stepwise procodure for identifying groups of inftuential outliers. [Bendre| (1989) noted that masking can change the results for some common multiple outlier tests. Lawrance (1995) noted that masking can create errors in common diagnostic quantities, such as Cook's Distance. In the context of outlier detection, [Atiisson| (1986) proposed solution that able to mitigate the effects of masking: it is based on two-step procedure that first fits subsamples of the data using least median of squares regression, which identifies potential groups of outliers, then uses single-point influence measures to confirm whether the points identified are indeed outliers. Gray & Ling (1944) note that the off-diagonal entries of the Hat matrix contain information about pairwise interaction effects between data points and propose an algorithm that uses this information in an attempt to overcome masking when identifying influential subsets. Both Lawrance (1995); Chatterjee & Hadi 1988) examine the the delction of a pair of cases. Lawrance (1995) focused soicly on Cook's distance as the quantity of interest, while Chatterjee & Hadi (1988) examines a range of influence measure. The works find that the degree of masking between two data points is function of the residuals, the leverages, and the off- off-diagonal entries of the Hat matrix. To address masking effects in this work, we consider stepwise approach (Greedy AMIP and One-Exact similar to the one taken in Belsley et al. (1980) Section 2.1) to overcome a combinatorial problem of searching for a Most Influential Set. The concurrent work Hu el, al. (024)) present theory on the non-additivity of data-dropping as well, but their focus is on most influential subset selection as opposed to detecting sensitivity of statistical conclusions to worst-case small-fraction data dropping. Finally, [Kucchni et al. (2021) compare greedy and additive approximations in context of worst-case small-fraction data dropping; we build on their work by (1) identifying instances where these methods result in conclusive failures through the definitions in Section 4 and (2) providing mathematical insight into these failure modes, as we present in Section 4
A.6 Lower bound algorithms
Following Broderick et al. 22200) line of works (Moitra & Rohatgi 2023 Freund & Hopkins 2023 Rubinstein & Hopkins| 2025) provide lower bounds on the number of points that must be removed to zero out a particular regression coefficient in OLS linear regression. However, these lower bound algorithms (1) do not identify a Most Inftuential Set and (2) do not compute an approximation to the Maximum Influence Perturbation, so we do not compare to these methods in this work.
However, the line of algorithms providing lower bounds can inspire future methodological development for the Most Influential Set problem in OLS. For example, Freund & Hopkins (2233 introduce spectral algorithm that takes more global approach than those taken by either the additive greedy approximations. As another example. Rubinstein & Hopkins (2025) introduce a lower bound algorithm based on analyzing the error term between the AMIP approximation and the true effect of rerunning an analysis without the dropped subset. They then provide new ways to upper bound the error term expression, offering mathematical insight into the error accrued by using influence-uunction based approximations to the Maximum Inffuence Porturbation. Despite these connections, there is currently no direct way to use these algorithms identify a Most Influential Set, so it is not the focus of this paper.
21

---

Published in Transactions on Machine Learning Research (07 (075)
A.7 Failure modes
Past works have pointed out cases where worst-case data-dropping approximations may perform poorly, but these works do not define notions of failure within the context of gencralization of cample-basod conclusions. We define these notions of failure concretely in Section and then surface examples of failures with respect. to these specific definitions. Whereas previous works have pointed out failures in adversarial examples and in settings of dropping larger data fractions > 1% (Moitra & Rohatgi 2023 Freund & Hopkins 2023), we are concerned with failures that might arise in natural data settings without an adversary and (for purposes of generalization) where dropping a surprisingly small fraction of data leads to changes in conclusions. Certain past works have surfaced failure modes of AMIP in real-world settings without further investigations. Specifically, Broderick et al. (2020) Section 4.3) and Nguyen et al. (2024) Section 6.2) point to settings where the approximation performs poorly on a study on microcredit (Angelucci & De Giorgi 2009). [roderick et al. 2020, Section 4.3) points out a failure of the AMIP in setting where the quantity of interest is iypervariance parameter in hierarchical model. Here, AMIP approximates a positive effect while the actual refit gives a negative effect. This failure mode has another layer of distinction from our problem, as it points to a failure that may arise due to a constrained parameter space. Nguyen et al. (2024 Section 6.2) point out a sctting where the approximations perform poorly for component of a hicrarchical model fitted with MCMC; in particular, they identify a selting where the confidence interval for AMIP undercovers. Finally, for the same microcredit study, Kuschnig et al. (2021); Moitra & Rohatgi (2023): Freund & Hopkins (2023) compare the performance of different approximation algorithms but not within the context of the failure definitions laid out in Section 4
B Approximation supplementals
B.1 AMIP supplementals
Broderick et al. 2020 consider a linear approximation to dropping data that can be used in any setting where the loss function 0) is twice continuously differentiable in 0, They define quantity-of-interee @00, w); to be a scalar related to the conclusion of a data analysis, which one is concerned about obscrving a change in upon dropping a very small fraction of data. Common quantities of interest in a data analysis include the sign or significance of regression coefficient.
Specifically, they lincarize the quantity-offinterest function of the deighwe
Σ Wwn - 1) @d(w)
N
Iin (w) = @(IN) +
(8)
Own la=
The derivative @ dwn
is known as the influence score of data point for & at In.
w=IN
Although the AMIP methodology has been developed and used for general quantities of interest, (0((r), w), we focus on the change in sign of specified regression coefficient; thus, Φ(0(w), w) (w).). Under the general setting where x(1x) is the solution to the equation ( (of( dz)) = Op (which is the case in our setup as @(1x) ) is a minimizer of a loss function) the implicit function theorem allows us to transform a derivative w space into a derivative space
a i
H(1N) -
Own 1i=NN
where H(w) = En w. (2 dm,) is the Hessian of the weighted loss. See Broderick et. al. (2020) for a detailed derivation of Equation 9 In the context of OLS, we consider the squared error loss, ((((I)),d)) (yn ((1N) ( x² The gradient for this loss is (of(Ō(LN), dn) = 2x, (yn. 0(1x) T In), and the Hessian is (O d..) 2r (Belsley et al. 1980 Thus, from Equation we get the expression
22

---

Published in Transactions on Machine Learning Research (07 (025)
for the inftuence score for data point n,
(6(w) (J)
x
nn
yn
0(1x) 2n).
(10)
Own
d=ix
leverage-like term
residual term
Let ep be the pth standard basis vector. Then the linear approximation in the setting where the quantity of interest is the sign of the pth regression cocfficient becomes
N t% = +
E
(wn 1)Vof(((NN)
(11)
B.2 Additive One-step Newton approximation
Past work has proposed using the One-step Newton (1sN) approximation to estimate how much dropping & pre-defined subset of data changes the loss, for general losses (Beirami el al. 2017 Sekhari et al. 2021
Koh et al. 2019; Ghosh et al. 2020). When we simultaneously consider (a) OLS linear regression and (b) our particular (effect-size) quantity of interest, Additive One-step Newton equivalent to the Additive One-Exact approximation. So for the experiments in this work, there is no distinction. While Park al. (2023) first proposed the special case of Additive One-step Newton for logistic regression (in the context of data attribution), we develop general form of the approximation below. We hope the more general form will prove useful in future works on worst-case data dropping beyond OLS; in particular, in models that are expensive to run, a practitioner might be unwilling to incur the cost of running Additive One-Fxact.
The One-step Newton approximation works by optimizing a second-order Taylor expansion to the loss around w 1x. In the case where we must search for the worst-case data subset to drop, we approximate ((w) with
و (w) = 6(1)) H(w) n= (w,, 1)Vof(0(1N),
Σ
(12)
The One-step Newton approximation allows us to approximate 8(w) = arg min En wnf(0, (0, d,) with a second-order Taylor series expansion (in 0) centered at the estimate for the full data, 0(1N).
Wn Wnf(O, dr) f(0(LN),
Σ Wn (100
(13)
N Σ w. -
+ 2
(0 ((1)))
n=1
In order to solve for arg min ΣN wn, f,, d,), we can minimize the quadratic approximation to get
N
N (()
glaN (w) = 0(1N) + Win (3((((N))
(14)
In the recent machine learning literature, this One-step Newton approximation (Equation 14) has been
proposed to estimate the effect of dropping known subsets of data (Beirami et al. 2017 Sekhari et al. 2021
Koh et al. 2019 Ghosh et al. 2020) in the context of general twice-differentiable losses.
In the selting of simple linear regression, the One-step Newlon approximation gives the exact solution to the reweighted OLS estimate of a regression coefficient (Pregibon 1981 Equation 3). Let X NxP denote the design matrix and y E R- denote the response vector. Let S denote the dropped set (i.e., the observations indexed by S in the design matrix and response vector) and \5 denote its complement. Tet jieN (w) denote the Onc-step Nowton approximation of 6(w) given in Equation 12
glaN (w) (XTx) x x y
[X sus
X X X X (x X s X (T))
= =XT X y x ss)
(X
Tsnss
X
(15)
-(X
23

---

Published in Transactions on Machine Learning Research (07 (07/2023 /025)
such that
((w) - (w) (X)) 'X, "ss
stsss - (x) = 0.
(16)
The One-step Newton approximation has not been proposed in the context of the Maximum Influence Perturbation problem because (unlike influence scores) the approximation is non-additive. This non-additivity prechudes the fast solution of approximating the Most Inftuential Set by ranking and taking a sum of the top individual scores (Brodcrick al. 2020). As a solution, we adapt idcas from the AMIP consider an approxination that uses sum of One-step Newton scores for leaving out individual data points (Equation (7) We refer to this approxination, which was first proposed for the special case of logistic regression by Park
et al. 2023 (in the context of data attribution), as Additive One-step Newton (Add-1sh) 1sN).
jAdd-IaN (w) 0(1N) + Σ WES
Σ xe x
(OJ((())) -1 "V((((N))d))
(17)
Add-1sN applies to general differentiable losses, though continue to focus on quantity of interest equal to particular parameter value (so approximation does not include decision based on statistical significance).
A promising direction for future research is to extend the Add-1sN to more general quantities of interest and Z esstimmaoors. Ideally, such extensions would be automatic through autodiff, similar to the approach taken for the computation of the AMIP (sce Broddrick et al. (2020 ). We anticipate that techniques developed for the AMIP aid in extending the Add-1sN to more general quantities of interest.
B.3 Analytic expressions for the error of additive approximations
As the approximation methods presented in Section 3 are local approximations based on removing individual observations, errors may accrue when there exists subsets of points with high joint influence measures but low individual influence measures.
In linear regression, we can formalize this intuition by looking at an analytic expression for the OLS estimator of the pth regression coefficient, 0. Let e, IRd denote the pth standard basis vector. Let X E Nxx denote the design matrix and y R. denote the response vector. Let S denote the dropped set (i... the observations indexed by S in the design matrix and response vector) and VS denote its complement. Let ('r(w) denote the influence function approximation
given in Equation 11 and let gAdd-1Exact, (w) denote the approximation
given Equation 12
Let X_n denote the design matrix leaving out data point n, En E Rd denote the value of the nihh data point, and In (yn, 0(1N)Tzz denote the residual value of the nth data point.
The error incurred by AMIP can be written as
@AMIT - 0(w) = Σ c (X X)
Innn Σ
(X
(X
nES
DES
= x) (x X xis))
(18)
nES
x) (X)s 11
and the error by Additive One-Exact can be written as
Add 1exaet (w:) ((w)= = Σ p
n X x_n) - En (XT(XTsXxs)
Intn
nES
nES
(19)
Σ
X ) - ( )
p
n
nES
24

---

Published in Transactions on Machine Learning Research (07/ (025))
B.4 Time complexity supplementals
The AMIP algorithm can be broken down into four steps: (a) run the data analysis on the full dataset, (b) compute the influence scores for each data point, (c) rank the influence scores, and (d) sum the top [a_V] scores. In the context of OLS, the cost of step (a) is O(N + P More generally, we can denote the cost of (a) as being O(Analysis). The cost of (b), computing the influence score for N data points, O(N + P Recall that the influence score can be expressed as a Hessian-vector product (see Equation (9). The Hessian is a matrix of dimension P x P. For N data points, the cost of computing the Hessian is P2). To invert the Hessian (which is done once in the computation) costs O(P)). The gradient is vector of dimension P. To compute the gradient for N data points costs O(NP). To multiply the Hessian by the gradient, for N data points, costs D(NP2) Step (c), finding the top [aN] influence scores, costs ONN log aN) P Step (d), the summing of top scores, costs O(N).
AMIP:
In general, the overall cost of running AMIP is O(Analysis + N log(aN) + -NP2 + P3), For OLS with an effect size quantity of interest, the cost of running OLS, O(Anllysis), is O(NP2 + P Hence, the cost. becomes O(N log(a.N) - p
algorithm can be broken down into four steps: (a) run the data analysis on the full datasct, (b) compute the One-cxact scores (the exact impact of dropping an individual data point) for each point, (c) rank the One-exact scores, and (d) sum the top [a-V] scores. The only difference between running this algorithm and running AMIP is in step (b). In the general data analysis setting, the computation of One-Exact scores involves the re-running of data analyses upon dropping each individual point in a dataset, a cost that is O(N x Analysis). In the setting of OLS, we can take advantage of the One-step Newton update in place of re-running the analysis N times (see Appendix B.2 for more dotails). Using this rank-one update, the cost of computing One-Exact scores for N data points becomes OSN + P²), or simply O(NPS). Notice that the cost differs from computing influence scores by an extra factor of P (recall that the cost of computing influence scores for AMIP is O(N + P$)). The improved precision of One-Fxact scores over influence scores comes at the cost of this additional factor of P; specifically, for Additive Ohe-Exact, the Hessian matrix is reweighted to account for each dropped data point (see Equation 17 in Appendix B.2 for the equation for this approximation) while, for AMIP, the reweighting is omitted.
Additive One-Exact:
The Additive
In general, the overall cost of rumning Additive One-Exact is O(N x Analysis + N log(a:N)) and the cost specific to OLS with an effect size quantity of interest is O(N log(aN) + P3).
The Greedy AMIP algorithm can be broken down into three steps, iterated over [aN] times: a) approximate the change (to the quantity of interest) upon dropping each data point individually using an influence function approximation, (b) select the point that results in the biggest approximated change when dropped, and (c) re-run the data analysis. Recall that computing the influence scores for N data points costs O(N p2 + P²); iterated for [aN] times, step (a) costs O(aNa p2 a.N ps). To find the top influence score |a-V] times, step (b) costs O(aN3). Finally, to re-run the data analysis [aN]] times with the point dropped, step (c) costs O(aN x Analysis). In general, running Greedy AMIP costs O(aN x Amalysis + p2 + aN). For OLS with an effect size quantity of interest, the cost of running OLS, O(Analysis), is O(NP² + p3). Thus, the cost of running Greedy AMIP for OLS with an effect size quantity of interest is OaaN2p2 + aN)...
Greedy AMIP:
Greedy One-Exact: The Greedy One-Exact algorithm can be broken down into three steps, iterated over [aN] times: a) compute the exact change (to the quantity of interest) upon dropping each data point individually, (b) select the point that results in the biggest change when dropped, and (c) re-run the data analysis. In the general data analysis setting, when iterated for |aN] times, computing the exact changes for leaving out each point individually, step (a) costs O(aN22 x Analysis). To find the top score costs O(N). Repeated over |aN] times, step (b) costs O(aN2). To re-run the data analysis after dropping the top point, step (c) costs O(NN x Analysis).
Thus, the general overall cost of running Greedy One- Exact is O(aN2 Analysis). For OLS with an effect size quantity of interest, this cost roduces to 2(aN223) p3).
TTn the limit, [aN] is equivalent a...
25

---

Published in Transactions on Machine Learning Research (07 (025)
B.5 Asymptotic Equivalence of [oN] and aN
The floor function introduces discrete rounding effects that are negligible in the asymptolic regime. We formalize this intuition below.
We begin with the incquality:
o:N - 15 LaoN S o...
(20)
This inequality holds for all (0,1) and all N E N. To simplify the comparison in big-O notation, seek multiplicative bounds.
Observe that for N > 3 we have that
1 aN
2 JaV,
(21)
which implies,
1
2 aN S LaN] N...
(22)
Hence, for sufficiently large N, the floor term LaN] is sandwiched between two constants times aN, so we conclude:
LaN] = O(aN) and a. = O(LNN).
(23)
Thus, [aN] and aN are asymptotically equivalent up to constant factors.
C Failure modes supplementals
C.1 Tables demonstrating results of approximation methods
Table I shows that, in the One Outlier example, AMIP fails both with and without re-run. While there exists one point (in black) that can change the sign the regression coefficient, the method reports that no subsets of size one exist that can change the sign (a failure without re-run). Upon removal of the point suggested change in sign (a failure with
by AMIP (which is red point) and refitting the model, still do not re-run). Greedy AMIP also faces a failure with re-run because the sigu does not change upon refitting after remove the point identified by the algorithm. In this example, Additive One-Fxact and Greedy One-Exact succeed. Of the OLS-specific algorithms, NetApprox and FHHGurobbi (warm-start) also succeed, while integral FH-Gurobi (without warm-starr) fails to identify a subset of size one that can change the sign.
Table shows that in the Simpson's Paradox example, AMIP and Additive One-Exact fail both with and without re-run. While there exists a group of ten points (a 0.01) (specifically, the group of points in black) such that, upon removal, the sign of the regression coefficient changes from positive to negative, both AMIP and Additive One-Exact report that no such subset of this size or smaller exists. The sign also does not change upon refitting, after removing the points identified by the algorithms. In this example, the greedy versions of both approximations succeed. Of the mathematical programming algorithms, NetAApprox and FH-Gurobi (warm-start) also succeed, while integral T'HGurobi (without warm-start) fails to identify a subset of size 10 that can change the sign.
Similar to the Simpson's Paradox example, Table shows that in the Poor Conditioning example, AMIP and Additive One-Exact fail both with and without re-run, while the greedy versions of both approximations succoed. Again, of the mathenatical programming algorithms, NetApprox and FH-Gurobi (warm-start) succeed while integral FH-Gurobi (without warm-start) fails to identify subset of size 10 that can change the sign.
Table 4 through Table display the performance the data-dropping approximations on real-world data sets.
26

---

Published in Transactions on Machine Learning Research (07 (225))
Table Performance of methods under the One Outlier example, where an outlier is placed at (X, Y) = (1e6, 1c6). We know that there exists subset (one data point!) such that, upon removal, the sign of the regression coelficient changes from positive (1.000) to negative (-1.000). Hence, Φ is sulficient to lead to a failure mode. The "Predicted Estimate" column shows the estimate predicted by the approximation algorithm, and the "Refit Estimate" column shows the result of refitting the model after removing the approximate Most Influential Subset specified by the algorithm. The "Points Dropped" column shows the number of red (R) and black (B) points that the algorithm drops. The values highlighted in green indicate that the algorithm succeeded. Non-highlin highhigghlghhted values under "Predicted Estimate" indicate a failure without re-rum, while highligglg values under "Refit Estimate" indicate failure with re-run.
Method
Predicted Estimate
Refit Estimate
Points Dropped
Removing Population
-1.000
(R: 0, B: 1)
AMIP
0.999
0.999
(R: 1, B: 0)
Additive One-Exact
-1.000
-1.000
(R: 0, B: 1)
Greedy AMIP
0.999
(R: 1, B: 0)
Greedy One-Exact
-1.000
(R: 0, B: 1)
NetApprox
-1.000
(R: O, B: 1)
FH-Gurobi
RR: 62, B: 1)
FH-Gurobi (warm-start)
-1.000
(R: 0, B: 1)
Table 2: Performance of methods under the Simpson's Paradox example. We know that there exists a subset (namely, the 10 points in Population A (a 0.01) in Figure D such that, upon removal, the sign of the regression coefficient changes from positive (0.586) to negative (-0.990). The "Predicted Estimate" column shows the estimate predicted by the approximation algorithm, and the "Refit Estimate" column shows the result of refitting the model after removing the approximale Most Influential Subset specified by the algorithm. The "Points Dropped" column shows the number of red (R) and black (B) points that the algorithm drops. The values highlighted in green indicate that the algorithm succceded. highlihgll values under "Predicted Estimate" indicate a failure without re-run, while non-highlighted values under "Refit
Estimate" indicate a failure with re-run.
Method
Predicted Estimate
Refit Estimate
Points Dropped
Removing Population
-0.990
(R: 0, B: 10)
AMIP
0.462
0.279
(R: 2, B: 8)
Additive One-Exact
0.456
0.279
(R: 2, B: 8)
Greedy AMIP
-0.990
(R: 0, B: 10)
Greedy One-Exact
-0.990
(R: 0, B: 10)
NetApprox
-0.990
(R: O, B: 10)
FH-Gurobi
RR: 112, B: 10)
FH-Gurobi (warm-start)
-0.990
RR: O, B: 10)
27

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Table 3: Performance of methods under the Poor Conditioning example. We know that there exists a subset (namely, the 10 points in Population A (a 0.01) in Figure D such that, upon removal, the sign of the regression coefficient changes from positive (8.452) to negative (-1.049). The "Predicted Estimate" column shows the estimate predicted by the approximation algorithm, and the "Refit Estimate" column shows the result of refitting the model after removing the approximate Most Influential Subset specified by the algorithm. The "Points Dropped" column shows the mumber of red (R) and black (B) points that the algorithm drops. The values highlighted in green indicate that the algorithm succeeded. Non-highlightes values under "Predicted Estimate" indicate failure of type (i), while oighhigll values under "Refit
Estimate" indicate failure of type (ii).
Method
Predicted Estimate
Refit Estimate
Indices Dropped
Removing Population
-1.049
(R: 0, B: 10)
AMIP
6.724
5.376
(R:5, B:5)
Additive One-Exact
6.667
5.376
(R: 3, B: 7)
Greedy AMIP
- .049
(R: 0, B: 10)
Greedy One-Exact
-.049
(R: 0, B: 10)
NetApprox
-1.049
(R: O, B: 10)
FH-Gurobi
(R: 991, B: 10)
FH-Gurobi (warm-start)
-1.049
(R: 0, B: 10)
Table 4: Performance of methods on the mouse brain single-cell analysis data set, where a 1% is sufficient to lead to a failure mode. The "Predicted Estimate" column shows the estimate predicted by the approximation algorithm, and the "Refit Estimate" column shows the result of refitting the model after removing the approximate Most Influential Subset specified by the algorithm. The "Number Dropped" column shows the number of points that the algorithm drops. The values highlighted in green indicate that the algorithm succeeded. Non-highlighted values under "Predicted Estimate" " indicate failure type (i), while non- highlighted values under "Refit Estimate" indicate a failure of type (ii).
Method
Predicted Estimate
Refit Estimate
Number Dropped
AMIP
0.451
0.355
656
Additive Exxct
0.4511
0.355
656
Greedy AMIP
-0.003
172
Greedy 1xxact
-0.003
172
NetApprox
-0.002
656
FH-Gurobi
0.000
1712
FH- Gurobi (warm-start)
0.002
172
28

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Table Performance of methods on the Ames Housing data set, where a 1% sufficient to lead failure mode. The "Predicted Estimate" column shows the estimate predicted by the approximation algorithm, and the "Refit Estimate" column shows the result. of refitting the model afler removing the approximate Most Influential Subset specified by the algorithm. The "Number Dropped" column shows the number of points that the algorithm drops. The values highlighted in green indicate that the algorithm succeeded. Non-highlighted values under "Predicted Estimate" indicate failure of type (i), while non-highlighted values under "Refit. Estimate" indicate a failure of type (ii).
Method
Predicted Estimate
Refit Estimate
Number Dropped
AMIP
72.010
55.845
14
Additive 1Exact
55.844
55.845
14
Greedy AMIP
15.09
4
Greedy 1Exact
-15.09
4
NetApprox
-14.11
14
FH-Gurobi
-15.55
5
FH-Gurobi (ws)
-15.05
5
Table 6: Performance of methods the bird morphometrics data set, where 1% is sufficient to lead to failure mode. The "Predicted Estimate" column shows the estimale predicted by the approximation algorithm, and the "Refit Estimate" column shows the result of refitting the model after removing the approximate Most Influential Subset specified by the algorithm. The "Number Droppod" column shows the mumber of points that the algorithm drops. The values highlighted in green indicate that the algorithm succeeded. Non-highlighted values under "Predicted Estimate" indicate failure of type (i), while non-highlighted values under "Refit Estimate" indicate failure of type (ii).
Method
Predicted Estimate
Refit Estimate
Number Dropped
AMIP
-0.401
0.399
Additive 1Exact
0.399
0.399
1
Greedy AMIP
0.399
1
Greedy 1Exact
0.399
1
NetApprox
-0.719
1
FH-Gurobi
0.410
4
FH-Gurobi (warm-start)
0.554
4
29

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Table 7: Performance of methods on the photosyuthesis measurements data set, where all methods succeed with refit at 0.0036. The "Predicted Estimate" column shows the estimate predicted by the approximation algorithm, and the "Refit Estimate" column shows the result of refitting the model after removing the approximate Most Influential Subset specified by the algorithm. The "Number Dropped" column shows the number of points that the algorithm drops. The values highlighted in green indicate that the algorithm succoeded. Non-highlighted values under "Predicted Estimate" " indicate a failure of type (i), while non- highlighted values under "Refit. Estimate" indicate a failure of type (ii).
Method
Predicted Estimate
Refit Estimate
Number Dropped
AMIP
-0.0117
-0.0038
2
Additive 1Exact
-0.0129
-0.00377
2
Greedy AMIP
-0.00377
2
Greedy 1Exact
0.00377
2
NetApprox
0.00377
2
FH-Gurobi
-0.00377
2
FH-Gurobi (warm-start)
-0.00377
2
Table 8: Performance of methods on the forestry data set, where all methods succeed with refit a 1%. The "Predicted Estimate" column shows the estimate predicted by the approximation algorithm, and the "Refit Estimatc" column shows the result of refitting the model after removing the approximate Most Influential Subset specified by the algorithm. The "Number Dropped" column shows the number of points that the algorithm drops. The values highlighted in green indicate that the algorithm succeeded. Non-highlighted values under "Predicted Estimate" indicate failure of type (i), while non-highlighted values under "Refit
Estimate" indicate a failure of type (ii).
Method
Predicted Estimate
Refit Estimate
Number Dropped
AMIP
0.0167
-0.0115
Additive 1Exact
-0.0115
-0.0115
1
Greedy AMIP
-0.0115
1
Greedy 1Exact
-0.01 15
1
NetAAprox
-0.01 15
FH-Gurobi
-0.0115
1
FH-Gurobl (warm-start)
-0.0115
1
C.2
Failure modes without an intercept term
In this section, we find that fitting without the intercept does not significantly affect the numerical results in Section 4 and that most of the same failure modes still hold.
The one exception to this observation that, with an intercept term, AMIP with re-run (which the same as Greedy-AMIP for dropping one data point) fails in the one-outlier example with an intercept terin, but without an intercept term, it succeeds. Here, we note that for the case when P 1 and intercept term, the limiting expression for the arbitrary non-outlier point discussed in Proposition 4.3 (Equation (6) is always O because Ep and are collinear by design. In more than 1 dimension, however, this collincarity need no longer hold, and so Equation G may indeed converge to a non-zero constant, which may again result in failure modes with re-run without an intercept term.
One-Outlier example. Upon fitting OLS without an intercept, the coefficient fit on the full dataset 1.000. The fit with the black-dot, points removed is -1.033. The removal of the intercept has negligible effects the numerical results of the algorithms, with the exception of AMIP SHIP//Geed: /GreedG-r AMIP "Refit Estimate" (which was 0.999 with an intercept and is -1.033 without intercept) (Table I
30

---

Published in Transactions on Machine Learning Research (07 (225))
Table Performance of methods under the One Outlier example, where an outlier is placed at (X, Y) = (1e6, 1c6). We know that there exists subset (one data point!) such that, upon removal, the sign of the regression coefficient changes from positive (1.000) to negative (-1.033). Hence, a v is sulficient to lead to failure mode. The "Predicted Estimate" column shows the estimate predicted by the approximation algorithm, and the "Refit Estimate" column shows the result of refitting the model after removing the approximate Most Influential Subset specified by the algorithm. The "Points Dropped" column shows the number of red (R) and black (B) points that the algorithm drops. The values highlighted in green indicate that the algorithm succeeded. Non-highling highhiggllghhted values under "Predicted Estimate" indicate a failure without re-run, while highhiigl values under "Refit Estimate" indicate failure with re-run.
Method
Predicted Estimate
Refit Estimate
Points Dropped
Removing Population
-1.033
(R: 0, B: 1)
AMIP
1.000
-1.33
(R: 0, B: 1)
Additive Ono-Exact
-1.033
- -1.03
(R: 0, B: 1)
Greedy AMIP
1.033
(R: 0, B: 1)
Greedy One-Exan -xxct
-1.000
(R: 0, B: 1)
NetApprox
-1.033
(R: 0, B: 1)
FH-Gurobi
-1. 1.033
(R: 0, B: 1)
FH-Gurobi (warm-start)
-1.038
(R: 0, B: 1)
Simpon's Paradox. When we do not include an intercopt, the coefficient fit on the full dataset is 0.516. The fit with the black-dot points removed -0.990. The removal of the intercept has negligible effects on the numerical results of the additive and greedy algorithms (Table 2 However, FH-Gurobi (warm-start) now presents an additional failure.
Table 10: Performance of methods under the Simpson's 's Paradox example. We know that there exists subset (namely, the 10 points in Population A (a 0.01) in Figure D such that, upon removal, the sign of the regression coefficient changes from positive (0.516) to negative (-0.990). The "Predicted Estimate" column shows the estimate predicted by the approximation algorithm, and the "Refit Estimate" column shows the result of refitting the model after removing the approximate Most Influential Subset specified by the algorithm. The "Points Dropped" column shows the number of red (R) and black (B) points that the algorithm drops. The values highlighted in green indicate that the algorithm succeeded. Non- Non-highlighted values under "Predicted Estimate" indicate a failure without re-run, while non-highlighted values under "Refit
Estimate" indicate a failure with re-run.
Method
Predicted Estimate
Refit Estimate
Points Dropped
Removing Population A
-0.990
(R: 0, B: 10)
AMIP
0.462
0.278
(R: 2, B: 8)
Additive One-Fxact
0.455
0.278
(R: 2, B: 8)
Greedy AMIP
-0.990
(R: 0, B: 10)
Greedy One-Fxact
-0.990
(R: O, B: 10)
NetApprox
-0.990
(R: O, B: 10)
FHH-Gurbbi
(R: 810, B: 10)
FH-Gurobi (warm-start)
0.514
(R: 0, B: 1)
Poor Conditioning. When we do not include an intercept, the coefficient fit on the full dataset is 7.405. The fit with the black-dot points removed is -1.02. The removal of the intercept has negligible effects on all numerical results (Table 3).
31

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Table 11: Performance of methods under the Poor Conditioning example. We know that there exists a subset (namely, the 10 points in Population A (a 0.01) in Figure I such that, upon removal, the sign of the regression coefficient changes from positive (8.452) to negative (-1.049). The "Predicted Estimate" column shows the estimate predicted by the approximation algorithm, and the "Refit Estimate" column shows the result of refitting the model after removing the approximate Most Influential Subset specified by the algorithm. The "Points Dropped" column shows the mumber of red (R) and black (B) points that the algorithm drops. The values highlighted in green indicate that the algorithm succeeded. Non-highlightes values under "Predicted Estimate" indicate failure of type (i), while highhigll values under "Refit
Estimate" indicate failure of type (ii).
Method
Predicted Estimate
Refit Estimate
Indices Dropped
Removing Population
-1.049
(R: 0, B: 10)
AMIP
6.616
5.376
(R:3, B:7)
Additive One-Exact
6.548
5.376
(R: 3, B: 7)
Greedy AMIP
- .049
(R: 0, B: 10)
Greedy One-Exact
-.042
(R: 0, B: 10)
NetApprox
-1.049
(R: O, B: 10)
FH-Gurobi
(R: 991, B: 10)
FH-Gurobi (warm-start)
-1.049
(R: O, B: 10)
C.3
Failure with and without re-run for FH-Gurobi
In this section, we discuss the distinction between failure with and without re-run for FH-Gurobi. Technically, the FH-Gurobi algorithms do not always require the user to re-run their data analysis with the suggested points dropped. However, the two failure modes are still equivalent for these approximations. To see the equivalence, assume that the data are non-robust data dropping specifically, that there exists some of drop to change conclusions. If the approximation returns set of size no greater than
size |oN] that [aN],, then approximation calls for users to re-run the data analysis with the identified subset dropped, in order to determine whether conclusion (e.g., the sign of an effect size) indeed changes. Thus, the two failure modes are equivalent in this setting. If the method returns a set of size greater than [aN], then a failure has occurred because no set size at most |aN] was found, so the user does not have to re-rum their data analysis. If they had re-run their analysis without this subset, the set is still greater than size [o.], which still implies that the approximation failed. Thus, both failure types are again equivalent.
C.4 Successful examples in real-world data
To get sense of examples which data-dropping approximations do succeed in the real world, we provide some real-world data sets that are non-robust frall-frationn data dropping, yet for which all methods succeed.
C.4.1 Plants
32

---

Published in Transactions on Machine Learning Research (07/202) 2025)
0.8
0.7
0.6
h.t (height)
0.5
0.4
0.3
0.2
0.1
0.0
0.0
0.2
0.4
0.6
0.8
1.0
d.st (dark respiration)
Figure 4: Plant photosyuthesis data. Dashed line indicates the fit to the full data while solid line indicates the fit with the 2 black-dot points removed.
Setup. This data set is taken from an ecological study on the plastic phenotypic response to light of shrubs from a Panamanian rainforest, Valladares el. al. (2000). We consider a 1D linear regression (with intercept) of height on dark respiration.
Experimental results. We know that there exists subset of size points (0.36% of the data) that we drop to change the sign of the regression coefficient from positive (0.0249) to negative (-0.014). In this example, all methods succeed at identifying the two points that, when dropped, change the sign. Thus, all methods succeed at = 1%.
C.4.2 Forestry
33

---

Published in Transactions on Machine Learning Research (07/200) 2025)
16
14
12
10
Cot
8
6-
4
2
0
0
2
8
10 12
Diam
Figure 5: Forestry data. Dashed line indicates the fit to the full data while solid line indicates the fit with the black-dot point removed. Though it is not visually apparent from the plot, we note here that the black-dot point overlays one other red-cross point (with slightly different x and y values).
Setup. This data set is taken from database recording various characteristics of woody plants (age, leaf size, leaf mass per arca, wood density, nitrogen content of leaves and wood), as well information about their growing environment (location, light, experimental trealment, vegetation type) (York) 2016). To ensure that data point around 1% (this data set has a total of 92 points with non-missing values), we augmented the data by repcating the red-cross points closest euclidean distance the mcan of the red-cross points. We consider 1D linear regression (with intercept) of the two variables Cot (plausibly component of tree biomass specific measurement related to tree structure Lo Diam (stem diameter).
Experimental results. We know that there exists point in 101 (0.99% of the data) that we can drop to change the sign of the regression coefficient from positive (0.170) to negative (-0.0115). In this example, methods succeed at identifying the one black-dot point that, when dropped, change the sign. Thus, all methods succeed at a = 1%.
C.5 On the relationship between leverage scores and failures of additive approximations
A common theme across the multi-outlier failure modes presented in Section 4.3 is that the leverage scores of the outlier points are extremely large (see Figure 6).
10rariabee definition explicitly stated in the paper
34

---

Published in Transactions on Machine Learning Research (07/202) 2025)
6
Pop Pop
Pap. Pop.
4
2
Residual
Residual
Residual
0
-1
-1
-2
-3
Pap. A
Pap.
81
0.0
0.2
0.4
0.6
0.a
1.0
0.00
0.02
0.04
0.06
0.08
0.10
0.00
0.02
0.04
0.06 Leverage
0.08
0.10
0.12
Leverage
Leverage
6
15-
Pop. A
Pop. Pop. B
Pop.
Residual
Residual
Residual
Pop. A
0-
Pop.
-5-
10
0.2 Leverage
0.3
0.4
0.00
0.10
-10
0.00
0.05
0.10
0. 0.20 0.25 0.30 Leverage
Leverage
Figure 6: Plots of Residual vs. Leverage: one-outlier (top left), Simpson's paradox (lop middle), poor conditioning (top right), two outliers (bottom left), two-outlier groups (bottom middle), two populations (bottom right). In all surfaced failure modes, the leverage values of each black-dot point is larger than the leverage values of each red-cross point.
Data-dropping is, in general, non-additive (Belsley et al. 1980 Gray & Ling 1984.. This fact becomes more apparent when the data points being dropped have high leverage scores. Data points with high leverage scores may interact with other data points highly non-linear ways, leading pronounced non-additivity data-dropping (Gray & Ling 1984 Lawrance 1995).
Recall, the leverage score for data point is the nth diagonal entry of the least-squares projection matrix (also known as the Hat matrix). This value can be interpreted as the degree by which the nth obsorvation impacts the nth fitted value (see Equation 24hh (Belsley et al. 1980). Similarly, the (n, m)th off-diagonal entry of the Hat. matrix, Inmm, can be interpreted as the degree by which the nth observation impacts the mith fitted value Gray Ling 1984). Thus, the entries the Hat matrix tell us important information about the second-order interaction effects between pairs of data points, information that the additive approximations fail to capture.
aün
han Oyn
(24)
The leverage score, Ann, bounds the off-diagonal elements of the Hat matrix, ham- These off-diagonal elements capture information about pairwise interactions between points (see Proposition C.I). When hum large, additive approximations become poor approximations. This explains why, all the surfaced failure modes of Section 4.3 the leverage scores for points in the Most Influential Set are large.
Proposition C.1. Let In E P denote the nth column of the design matriz X E NxP, Let ham = 2 x -tmm denole the entries of the Hat matria H X(X -X It follows that.
[hmm S V knn
(25)
Proof. The Sauchy-Schwary inequality states that for any vectors a, b, in an inner product space,
(a, b) < ||||||||||
35

---

Published in Transactions on Machine Learning Research (07/2025)
Let and b: terms of our defined vectors, Num (a, b), hun ||al12 hmm ||b]]2
() X) x) x)-1//Zm Notice that the entries of the Hat matrix can be written in
Taking square roots, We thus conclude that
||a|| v Mrmns ||b||
hrmm-
Wmml V Anntumm.
C.6 One-outlier example
C.6.1
One-outlier failure mode theory
We saw that both AMIP and Greedy AMIP break down in the one-outlier setting. This is because the influence score of the outlier vanishes as the point approaches infinity in the æ and y directions. In Proposition 4.3 we examine the mathematics behind this phenomenon.
Lemma C.2. Let R and ep E R be the pth standard basis vector. Let In E R denote the nth row of the design matrir X E NRP, and let yn denote the nih entry of the response vector y E TRN Let X-1 E --1xx denote the design matrix with the 1st row deleted, and let y-1 RR denote the response vector with the 1st entry deleted. Let A-1 A-1= = and b-1 --_,-_1 For any u Rp with ||||]] and any constant e >> 0, let (I1, (Au, eX). For 2 S N, let (In, Vn) E RP, x E be arbitrary points with the constraint that X-1 has rank P. The influence score of data point (11,81) is,
(w)(w) Ow
1
eg Juuc - b_ A 2-1 A (v A 00
(26)
w=lx
X
Proof. Recall that, for OLS linear regression and the effect size quantity of interest, Op, the formula for the influence score of the nth data point is
(6,(w) Own
X)
In (yn 0 xn))
(27)
w=lx
leverago-liko like
residual term
We start by examining the leverage-Hie term,
X x) Iz.
(28)
Using the Sherman-Mortnn formula, the leverago-like term is equivalent to
A 1 A
of (A_ + x1 x1 = 6p
A
(29)
1 20 A
Substituting Z1 = Au and y1 = cd, this term bocomes
Ae A
(30)
1 A A=
which tends to zero as X + cc.
We next look at the residual term.
The fitted value for æ1
ØT Φ = - [X x) -111-
(31)
36

---

Published in Transactions on Machine Learning Research (07/2025)
Using the Oherman-Morrisse formula, the fitted value can be written
XAA D XAA 1 a
(32)
++ A 101
Through algebraic simplification, the above expression can be written under one fraction,
y xA V x A A
(1- (1- 1++ A 1
x A
1 1 = y xA 11
y y'AA1111
(33)
1+ A
(!² + bb1))_
1+ A_
Substituting x1 Au ERP, y1 = =c,, we get
(ct2vT T +b-1)A
C
A AA 16_1A_1
(34)
1 A2v A_
1 A26 A3
Finally, subtracting the fitted value from y1, the residual is
cA 1b-
v1 - - x1
(35)
1+ X
Taken together, the influence score of (x1, is
Xce A 1 A A
xx -x - x1)) =
+ 2X20 A A
( A_
(36)
e v - b-1
X²
A- 22 20 A (c" 2
We saw that AMTP failed both with and without re-run in the one-outlier setting.
In the one-outlier case in Section 4.2 we that, for sufficiently large X, the inffuence score for the outlier becomes smaller than that of non-outlier. In Proposition
explain this phenomenon more formally.
Proposition 4.3. Choose any v E TR.. with || and any constant e > Let (I11 91) = (Au, Ac). Let (Ins yn N= be any points in R x R such that X_, has rank P. Let Or denote the pth entry of the OLS estimator, 0, fit without an intercept. Then, for all 1 SP
(w)(w)
lim 06,(w)
st
lim +
=0,
(5)
and
(6)
Own
1w=1N
Ow2
lw=ly
(v (oTA]]u))
where (v A_ A
A A and f. == (y2uTA
A - cv AA- - b- A_
} 828 A-
b_ b- vvv A=)x2).
Proof. Let Ep E R denote the pth standard basis vector. Let A-1 x_ and b_1 = v_,x___ where
V-1 E N-1 denotes the response vector with the nth entry deleted.
We begin by examining the influence score of (01, v1).
37

---

Published in Transactions on Machine Learning Research (07 (07/2025)
From Lemma C.2
Equation
36
that the inffuence score of data point (01, v1)
is
(w)
C AT - A
(37)
Ow
1amlx IN
XX
+ 2X 2v A A 1 (v A 1)
Taking a limit as + oo, this expression goes to zero at rate 0 x+)))
e A - b- A
lim A X2
=0
(38)
- 1 + (v /-
We next examine the influence score of (I2, 92). We start by examining the leverage-like term,
(x x2
(39)
Using the Shernan-Morrison formula, this equivalent
A - A e (A + )) x2 c (A
_ A 22
(40)
Substituting x = Au and combining fractions, the leverage-like term becomes
e x) 22 A + (2 A ue A x2
6 u A A
(41)
1 + X2
We next look at the residual term.
Using the formula for the OLS solution, the residual for (æ2, 1/2) is
y2 0 x22 = x -222
(42)
Using the Sherman-Morrison formula, this can be written as
XA xXA]aa1 A
12 0 52 y22
(43)
1 A A=101
Substituting x2 = Au and = Ac and combining fractions, we get
(A3ex T + +b1) X2 +b-))A 00 A A-122
1/2 - @T = 1/2
12x²² A
(44)
X A A_ + X²6 12b_1A]10 A
= 1/2 X2c00
A_ X2o0TAA + b
1 22 A
Finally, combining fractions, we get that the residual
0 UT2- (222v A_ - co A_ - b_ A
2220' 1 + b- A 100 A_ + 9/2 b-, A |
1 X2 A_
(45)
Taking Equations
41 and 45
together, the influence score of (12,, y2) is
o x x) 12 - @T x2) = st X2s(12 b 1 + X te A 1/ + e A- 22 b_1 (22)
( A v) 2 - 2
(46)
38

---

Published in Transactions on Machine Learning Research (07 (07/202) /025)
where
(v) A A A_
cp A_ A 22)
(47)
(yzv) T A cv" AA_ - b-1 x2v' A + b x2))
(48)
Taking a limit in Equation 466 as + 00,
A + 2² - b- A1)) 3 A + +.00 A A 1 - b-1 A_12
lim ep (x X) A-000
xx) 3x)''x2220 "22(y2 0 x22)
lim X+000
A² A=]u)² 2 -
A
lim A+00 X²(2T A=
st
(v A 1
(49) E
C.6.2 Generality of conditions in the one-outlier theory: simulation study.
To assess the strictness of the conditions posed in Proposition 4.3 WC run a simulation study following the setup and assumptions outlined in Proposition
Next, for N 1,000, we generate 5,000 datasets for each of dimensions, 3, 6, and For each data set, choose 1 data point uniformly at random from the inlier samples to be (z22, 12), a random integer between and P (inclusive) for the value of in Ep, and a random unit vector for E IR.. Additionally, we take À to be large (1020) and choose (21, to be the point at the first index. We then compute the values of and t.
In 5,000 simulations for each dimension, we observe that neither s nor are ever zero. This provides further empirical evidence to suggest that Proposition 4.3 holds more broadly than just the specific toy example provided Section 4.2.2
C.6.3 One-outlier example, empirical findings supplementals.
Table 12 and Table 13 display empirical findings for the data generating process described in Section 4.2 The tables present empirical evidence showing that a sufficiently far outlier will have vanishingly low influence score (see Proposition 4.3). As the black-dot point (the outlier) moves far from the group of red-cross points (the central points) in both the x and y directions, both the leverage-like term and the residual term of the influence score approach zero rate O (see numerical results in columns 3 and 4 of Table 12 When observing the behavior of the red-cross point with the largest influence score in Table 13 see that the leverage-like like term approaches zero while the residual term stays relatively constant (within the same order of magnitude). Thus, for sufficiently large values of (z), 31), the influence score for the black-dot point becomes smaller than that of a red-cross point (sce the highlighted values in Table 12 and Table 13 For the (æ,, yi) values with highlighted influence scores (see Table 12), both AMIP and Greedy AMIP fail (both with and without re-run). This occurs x =y y = 10th for the data generating process described in Section 4.2
39

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
Table 12: This table shows the influence and One-Exact scores for the black-dot point at various values of (1z yi)
for the data generating process described in Section 4.2 (see plot for the setting where (I,, M4) = (10%, 10 in
Figure 1 (left)). In order to obtain the infiuence with respect 81, we let e (0. 1), the standard basis vector corresponding to the x term in our linear regression setup, The influence score, e (X x) "x, Ox.)), is a product between the quantity in column (which we call the leverage-like term, see Equation (3) and column 4 (the residuals). The One-Exact score is the change in effect size that results from dropping the single data point at (Fi, Dt) and refitting OLS. The influence scores highlighted in yellow those that smaller than the influence score of red-cross point, leading AMIP and Greedy AMIP to misidentify the Most Influential Set of size 1, resulting in a failure with re-run.
BLACK DOT POINT
(THE OUTLIER):
2;
y
of (X'X)-=
X)-'x; 24
(y: Ōz.))
INFLUENCE SCORE
ONE-EXACT SCORE
1:1
1s1
9.36E-3
18.390
1.72k-1
1.90g-1
1:2
1s2
9.11E-3
17.981
1.64g-1
1.85
124
1B4
1.00p-5
1.97E-1
1.97E-5
2.03
186
186
1.00E-6
1.97E-3
1.97E-9
2.03
188
1B8
1.00
2.00g-5
1.97g-13
2.18
1E10
1R10
1.00F-10
1.00R-5
9.54R-16
2.03
Table 13: This table shows the influence and One-Exact scores for the red-cross point with the largest influence score when the black-dol, point (see Figure (left)) is placed at the (Ii, Mi) position shown in the corresponding row of Table 12 In order to obtain the influence with respect to 01, we let e₁ = (0, 1), the standard basis voctor corresponding to the x term in our lincar regression sctup. The Influence Score, eX x)=x)xxx(( (, - Òx,)), is product between the quantity in column 3 (which we call the leverage-like term, see Equation 33) and column (the residuals). The One-Exact score the change in effect size that results from dropping the single data point (zz, M;) and refitting OLS. The influence scores highlighted in yellow are those that are larger than the influence score of the black-dot point, leading AMIP and Greedy AMIP to misidentify the Most. Influential Set of size 1, resulting in failure with re-run.
RED CROSS POINT (A CENTRAL POINT):
Z
eT (XTX)-'a,
(vs - ATy))
INFLURNCE SCORE
ONR-EXACT SCORE
2.13
-0.09
2.02E-3
1.66
3.38E-3
3.40p-3
-0.72
-2.05
7.10R-5
-1.57
1.12F-4
1.12p-1
2.70
-4.85
7.25m-5
-7.66
5.55r-7
5.55p-7
2.70
-4.85
7.25B-8
-7.65
7.63E-9
7.64E-9
2.70
-4.85
9.97E-10
-7.65
7-65E-11
7.66F-11
2.70
-4.85
1.00E-14
-7.65
7.65g-1
7.66g- 13
40

---

Published in Transactions on Machine Learning Research (07 (07/2023) /025)
C.7 Multi-outlier examples
C.7.1 Multi-outlier failure mode theory
Additive approximations may be inaccurate, even for approximating the removal of two data points. In Proposition 4.4 we show mathematically that when a pair of points, off by constant term, go together lowards infinily, the Additive One-Exaci approximation to dropping the pair tends towards zero, regardless of what the true change in effect size approaches.
Proposition 4.4. Let X, c R. Consider pair of data points, (I1, = (), and (æ V2) = (2. Let (Ins Yn m be any points in R R such that at least one of (xn)m=3 is non-zero. We apply OLS to the single covariate x and response y with intercept; we make a decision based on the sign of the resulting effect size. As X + 00, the Additive One- Exact approcimation (Section 3.1) to the change in effect size from dropping (11, y1), (22, y2) tends zero, while the true change in effect size tends to (E Inyra En xn)
Proof. Let 0-1 denote the OLS solution fit to the data after dropping point (I1, 81), and let 01-1.-2 denote the OLS solution fit to the data after dropping the pair, (æ1, yı), (x2, y2)- Let Additive One- Exact approximation to the change in effect size after dropping (21,31), (12, 12). Finally, let S EM o and S2 = En 1,2 In.
denote the
Add- (id-1Exact(112) is expressed as
Add-1Exact(11
(0--0)))(0-00) 0_2) X²(Si - 02) N
X² - S2) + A%c
(Si + + 2
(Si + (2) + +
(50)
2A7(S) - 52)
(Si + (²) + 212).
As + 00, Equation 50
tends to zero.
2(S) - S2)x
lim Add-1Exact = lim
X
X 2X* + X3 Si
(51)
0.
In contrast, the expression for the true change in effect size from dropping the two points is expressed as
4(S; 82) 2(5) S
0 0 -1,-2)
(S) +
(52)
- -
+ +0 1
48
x2
Taking limit in Equation 52 X 00,
4($1 S2)
1
lim 00-0_,--)) lim X+000
+ +0
X+000
4S
12
S2
(53)
S
EN Un
Un
Ex x3
7
41

---

Published in Transactions on Machine Learning Research (07 (07/2025)
C.7.2 Additional multi-outlier examples
Adversarial Example. Moitra & Rohatgi (2023 presents an adversarially constructed example which there exists small fraction of points that can be dropped such that the covariance matrix becomes singular. This leads failure mode of approximation algorithms. In Section we attempt alter this adversarial setup into one that might arisc in natural data scttings with no adversary (sec Figure 1 (right)). We see that even modest levels of instability in the covariance malrix can lead to failure modes in the approximation methods.
To visualize the example presented in Moitra & Rohatgi 2023), we generate the red crosses so as to have a singular covariance matrix (see Figure 7 In particular, we generate the 1,000 red crosses with Tnp = 0,
Vn = =n; and 6, jid N/ 1). We draw the 10 black dots as 2n lid (V(110001), Yn. = 2n. When we consider poor conditioning. However, when
both black dots and red crosses together drop the red population, pathological change occurs in the covariance matrix; becomes singular. The OLS-estimated slope the full dalaset is about 1.00; dropping the black dots (1% of the data) yields a slope of exactly O. Note, although the removal of the black-dot points do not induce sign change in this example, going from a positive signed coefficient to still constitutes a conceivable conclusion change in a data analysis.
single dataset, there
-5
-2.0
-1.5
-1.0
-0.5
0.0
0.5
Figure 7: Example of poor conditioning presented in Section 5.1 of Moitra & Rohatgi 2023
Greedy AMIP Failure Example. In the following example, we illustrate case in which Greedy AMIP fails (See Figure 8j. In partieular, when there is black dot left. to remove, Greedy AMIP is unable to identify the black dot as the point to remove. This is because the residual of the last remaining black dot becomes vanishingly small when the second to last black dot is removed in the previous iteration.
In this example, we generate the 1,000 red crosses with H, = 0, y, = e,, and 6n iid N(00, 1). We draw the black dots as In ild (M-1, 0.01), Vn -5x, - 10. The OLS-estimated slope on the full dataset is about 4.94; dropping the black dots (1% of the data) yields slope of about 0.
In this example, Greedy One-Exact succeeds. For the mathematical programs algorithms, NetApprox succoeds while FH-Gurobi fails.
Greedy AMIP and Greedy One-Exact Failure Example. In the next example (See Figure 9p, by clustering outliers tightly into small clump, we can construct an instance where both greody AMIP and IsN fail identify the k outlier cluster. This repeated & points centered around one clump (where large) produces example where the residuals vanishingly small in the outlier cluster, while the leverage
42

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
Pop. A
x
Pop. B
-6-
-1.5 -1.0
-0.5
0.0
0.5
1.0
Figure 8: This is example where Greedy AMIP fails but Greedy One-Exaci succeeds.
only be big 1/k. Hence, the One- Exact scores of certain points in the red inlier population (population B) will be larger. In this instance, if we computed the One-Exact score for every subset of size k however, we would be able to correctly identify population A as the Most Influential Set.
For the mathematical programs algorithms, Approp succeeds while FH-Gurobi fails.
In this example, we generate the 1,000 red crosses with Fn 0, yn en. and 6n iid NO 1). We draw the 10 black dots In nd N(-1,10-7) 7), Yn. -5x, 10. The OLS-estimatedr slope the full dataset is about 4.94; dropping the black dots (1% of the data) yields a slope of about 0.
3
Pop. A
2-
x
Pop. B
1
0
> -1
2
3-
-1.5
-1.0
-0.5
0.0
0.5
1.0
Figure 9: This is example where Greedy AMIP and Greedy One-Exact both fail.
Observe from Equation (18 that the error arises from a failure to correctly reweight the inverse Hessian term by the dropped subset, S. While AMPP disregards this reweighting entirely, Additive One-Exact decreases the crror by reweighting the Hcssian on an individual point basis (See Equation
19
43


Reviews:
[{"review_id": "jCiBqBDxLF", "reviewer": "Reviewer_Y1Kf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is overall well-written and easy to follow. The authors provide a\n   clear motivation for the study, and the presentation is clear and coherent.\n2. The paper addresses an important problem in statistical analysis and data\n   science. It may have a significant impact on real-life decision making if the\n   conclusion from the data analysis can be reversed by removing even a tiny\n   proportion of the data.\n3. The theoretical insights provided in the paper match the empirical\n   observations well.\n\nWeaknesses:\n1. The scenarios and numerical examples considered are simple. Real data\n   patterns are often more complex. Not requesting to investigate more\n   complicate cased, but it would be better to make this point clear.\n2. According to the theoretical results, the major reason for not being able to\n   detect the impact of the outliers is due to the limitations of AMIP. It's\n   better to clarify this point. In real data analysis, it is very important to\n   perform regression diagnostics to identify outliers, and the outliers in the\n   paper can be easily identified by classical diagnostic techniques.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the robustness of data-dropping methods in the context\nof ordinary least squares (OLS) for linear regression. The authors focus on\nApproximate Maximum Influence Perturbation (AMIP) and compare various approaches\nthat utilize AMIP to detect the most influential sets of data points.  They\ndemonstrate that many of these approaches can fail to detect the most\ninfluential sets of data points in simplified data scenarios. The authors also\nprovide theoretical insights into why AMIP may not serve as a reliable criterion\nin certain situations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The weaknesses mentioned above should be addressed.\n2. Put the expression after $max_{w\\in W_α}$ in parentheses, or move\n   $max_{w\\in W_α}$ in front of $\\hat{θ}_p(w)$ in (1).\n3. Equation (3) already requires that $N>p$ and $X$ is full rank. It is better\n   to clarify this point here rather than later in the paper.\n4. I am not clear what you mean by \"Analysis represents the cost of the data\n   analysis\" on page 5. Is this just the OLS calculation?\n5. For the Additive One-Exact method, does it only require finding the data\n   point with the largest influence? If so, should $N\\log N$ be replaced by\n   $N$, as this can be done in linear time? This is in the paragraph above\n   Section 3.2.\n6. The last paragraph on page 6 talks about the equivalence of two failures,\n   but cases (1) and (2) refer to successes. This can be revised for easier \n   reading.\n7. Above Section 4.2, by \"overestimation\", do you mean a false positive—i.e., the\n   method detects non-robustness when it should not? Please clarify this point.\n8. The numerical experiments fit OLS with an intercept, while the theoretical \n   results fit without an intercept. Although it is mentioned elsewhere that the\n   numerical results are not much affected by the intercept, this inconsistency\n   may confuse readers. Please make them consistent and state that the intercept\n   does not significantly affect the numerical results.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4Vrxzq2sli", "reviewer": "Reviewer_MPJ3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- write up seems solid. Experiemnts and theoetic reasoning are provided\n- in general the problem whether dropping a small amount of the data leads to significant change seems to be an interesting question\n\nWeaknesses:\n\n- only three synthetic datasets are considered.\n- the criteria (i.e. change of sign a specific coordinate) seems a bit arbitrary.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Authors consider the following question: Given a dataset consisting $X \\in \\mathbb{R}^{N \\times P}$ and $y \\in \\mathbb{R}^N$, $p \\in [P]$ and $\\alpha \\leq 0.01$ are the $\\alpha N$ or less rows in $X$ such that dropping these rows causes a sign flip in the $p$-th coordinate of the optimum solution of the OLS estimator.\n\nThey compare the following algorithms: \nadditive approximations: Approximate Maximum Influence Perturbation (AMIP) and Additive One-Exact\nGreedy approximations: Greedy One-Exact and Greedy AMIP\nApproximations Specific to Ordinary Least Squares: NetApprox, FH-Gurobi (with and without warm start)\n\nMore precisely they construct three synthetic datasets (a daataset with a  single outlier and two datasets with multiple outliers) and analyze the running time of the algorithms as well as whether they are able to answer the question correctly using the output of the algorithms.\n\nTheir result is Greedy One-Exact,NetApprox and FH-Gurobi (with warm start) answer the question correctly for all three datasets while each other algorithm fails for at least one dataset. Moreover the additvie approximationalgorithm run faster than the greedy algorithms which run faster as the specific algorithms. Authors thus recommend to use greedy algorithms if there is enough compuetation power.\n\nThey further enhance their findings by stating and proving why the algorithms fail on these instances.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- There could be an explanation on how $p$ is chosen.\n\n- There shouild be a reference or derivation of equation (3)", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2OeA04futQ", "reviewer": "Reviewer_sA6M", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n\n- The paper provides a comprehensive discussion and analysis of relevant related work.\n- Comparisons are clearly presented from both theoretical and empirical perspectives.\n\n\nWeaknesses\n\n- The paper states to focus on realistic data configurations, but the reviewer could not find any experiments conducted on real-world datasets. More comprehensive evaluations using several real-world datasets would be beneficial.\n\n- The paper appears to be a review of recent studies on data dropping, without presenting any particularly novel findings. As such, the reviewer feels that the contribution is somewhat limited in terms of originality.\n\n- Additionally, the work focuses primarily on OLS, which is relatively simple. The reviewer is concerned about the practical relevance and applicability of this work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the issue of model generalization sensitivity in the context of OLS regression. Specifically, it examines the non-robustness of model conclusions to the removal of a small fraction of data points—a problem that is computationally intractable to check exactly. While several approximation methods have been proposed to detect such non-robustness, the authors demonstrate that many of these fail in practice, even in the relatively simple OLS setting. Through empirical evaluation, they show that a recursive greedy algorithm not only reliably detects non-robustness but also does so with significantly greater computational efficiency than competing methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)