Robustness Auditing for Linear Regression: To Singularity and Beyond
Authors: Ittai Rubinstein
Samuel B. Hopkins
Venue: ICLR 2025 Poster (2025)
Keywords: Robust machine learning
linear regression
robustness auditing
data attribution
ordinary least squares
robust statistics
econometrics
Primary area: learning theory
TL;DR: We provide the first practical algorithms which can be used to certify robustness of linear regressions to removals of samples.

Abstract: It has recently been discovered that the conclusions of many highly influential econometrics studies can be overturned by removing a very small fraction of their samples (often less than $0.5\%$). These conclusions are typically based on the results of one or more Ordinary Least Squares (OLS) regressions, raising the question: given a dataset, can we certify the robustness of an OLS fit on this dataset to the removal of a given number of samples?

Brute-force techniques quickly break down even on small datasets. Existing approaches which go beyond brute force either can only find candidate small subsets to remove (but cannot certify their non-existence) [BGM20, KZC21], are computationally intractable beyond low dimensional settings [MR22], or require very strong assumptions on the data distribution and too many samples to give reasonable bounds in practice [BP21, FH23]. 

We present an efficient algorithm for certifying the robustness of linear regressions to removals of samples. We implement our algorithm and run it on several landmark econometrics datasets with hundreds of dimensions and tens of thousands of samples, giving the first non-trivial certificates of robustness to sample removal for datasets of dimension $4$ or greater. We prove that under distributional assumptions on a dataset, the bounds produced by our algorithm are tight up to a $1 + o(1)$ multiplicative factor.

Published as a conference paper at ICLR 2025
ROBUSTNESS AUDITING FOR LINEAR REGRESSION: To SINGULARITY AND BEYOND
Ittai Rubinstein & Samuel B. Hopkins
Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology Cambridge, MA, USA (ittair, samhop) @mi miit.est edu
ABSTRACT
It has recently been discovered that the conclusions of many highly influential econometries studies be overtumed by removing very small fraction of their samples (often less than 0.5%). These conclusions are typically based on the results of one more Ordinary Least Squares (OLS) regressions, raising the question: given a dataset, can we certify the robustness of an OLS fit on this dataset the removal of given number of samples? Brute-force techniques quickly break down even on small datasets. Existing approaches which go beyond brute force either can only find candidate small subsets remove (but cannot certify their non-existence) Broderick et al. (2020); Kuschnig et al. (2021), are computationally intractable beyond low dimensional settings Moitra & Rohatgi (2022), require very strong assumptions on the data distribution and too many samples to give reasonable bounds in practice Bakshi & Prasad (2021); Freund & Hopkins (2023). We present an efficient algorithm for certifying the robustness linear regressions to removals of samples. We implement our algorithm and run it several landmark econometrics datasets with hundreds of dimensions and tens of thousands of samples, giving the first non-trivial certificates of robustness sample removal for datasets of dimension 4 greater. We prove that under distributional assumptions on a dataset, the bounds produced by our algorithm are tight up to 1 + o(1) multiplicative factor.
INTRODUCTION
Consider a supervised learning problem with feature vectors XI...., X, E Idd and labels Yi...., Yn E. which we fit model f Rd F. Robustness auditing addresses the question:
How would f have differed if had been missing a small fraction of the data?
We study this question in the context of ordinary least squares (OLS) linear regression, where f(X) = (3, X) is the linear function minimizing the mean squared error Eisn (f(X,) Y,)². We focus on OLS for two reasons. First, OLS a statistics workhorse, with widespread use across economies, social science, finance, machine learning, and beyond. Second, its relative simplicity affords us the opportunity to design algorithms with provable guarantees, and offers stepping stone more complex models (logistic regression, kernel methods, neural networks).
Problem 1 (Robustness Auditing for OLS Regression). Given linear regression instance (X1, (Xa, Yn) E IRd+1, a direction E IR." and an integer k S n, what is
A+(e) = max (8(m) Bs. e) SCIml
-
where for T C [n], 3T ddd denotes the vector of OLS coefficients for the dataset {(x,, Y.) HiEr? In particular, for a threshold E what is the minimal number of removals kg ()(e) for which Ax(e) 0?

---

Published as a conference paper at ICLR 2025
Context and Applications for Robustness Auditing Problem I was introduced in this form by Broderick, Giordano, and Meager Broderick et al. (2020), who use a heuristic algorithm, AMIP, to identify very small subsets of landmark datasets from econometrics which can be removed to overturn important conclusions of the respective studies Finkelstein et al. (2012); Angelucci & De Giorgi (2009); often this be achieved by removing less than 0.5% of dataset. Researchers have subsequently used AMIP to audit a wide range of recent studies in economics Martinez (2022); Di & Xu (2022); Davies al. (2024); Zachmann et al. (2023); Burton & Roach (2023); Beuermann et al. (2024); Bondy et al. (2023). Subsequent algorithmic works Kuschnig et al. (2021); Moitra & Rohatgi (2022); Freund& & Hopkins (2023) develop additional algorithms for auditing similar notion of robustness; we discuss prior work in detail below.
is important that, similar to these prior works, we focus on robustness a shift of in only single user-specified direction e. This is because the main conclusion of a regression is often determined by the projection of its result on a particular axis. For instance:
ROBUSTNESS OF PARAMETER ESTIMATE A researcher may want to estimate the correlation (3, e) between a specific explanatory variable and a target variable, controlled for additional factors, where is the indicator vector corresponding the explanatory variable. Moreover, the sign and statistical significance of (3, e) is often of greatest interest.
This correlation can have a causal interpretation. For instance, in randomized control trial, where is the indicator for the treatment variable, the projection (3, e) can be used to estimate the "average treatment effect" (ATE) of new drug or policy on the outcome Y. while including the control variables in the regression can help reduce the variance of this estimate. Even more complex causal inferences (e.g., instrumental variables regression) can often be decomposed into a small number of OLS regressions, where the result of the causal inference depends on single coefficient from the result of each regression.
Conclusions from study where this shift (e is large when k < n are therefore driven by a small number of data points, meriting at minimum reinspection of a dataset, and perhaps casting doubt on generalizability. In many real world regressions, the sign of (33, e) is not robust to a small number of removals, even though it is statistically significant Broderick et al. (2020). Non-existence of a small set of highly influential samples indicates robustness of the measured effect to an interesting class of distribution shifts any removal of a small fraction of the population.
DATA ATTRIBUTION Suppose that instead of looking for the effect of particular feature on the label Y, instead we use the linear model f to predict the label of a fresh point X and we want to identify what part of the training data led to the prediction that Ysew == fX Following the counterfactual formulation of this data attribution problem from Koh & Liang (2017); Ilyas et al. (2022), we arrive again at robustness auditing: using e Xnew: we can find the smallest set of whose removal would significantly shift f(Wnew). We can evaluate the brittleness of the prediction by measuring the size of the smallest set of samples we could remove to cause f(Xnew) to cross a decision boundary.
Intractability, Heuristics and Upper Bounds As soon as k exceeds single digits, robustness auditing by brute-force search over all [S] = n & takes times (*). which is computationally intractable.
The works Broderick et al. (2020); Kuschnig et al. (2021) relax the goal to finding upper bounds on ko(e), for which they use greedy/local search algorithms. This approach leaves open the risk that ka(e) might be much smaller than the upper bound suggests. Indeed, later experiments by us (see Figure 1), Moitra & Rohatgi (2022), and Freund & Hopkins (2023) uncover numerous real-world examples where local search techniques give loose upper bounds.
Following Moitra & Rohatgi (2022), we aim for algorithms which provide unconditionally valid upper and lower bounds on ke(e) for every dataset {(X,, He) and which return high-quality upper/lower bounds (as close to matching each other as possible) under reasonable assumptions on
{(X,, Y.)..Y))) [i)) Prior approaches to go beyond greedy algorithms and provide lower bounds on (e) Klivans et al. (2018); Bakshi & Prasad (2021); Moitra & Rohatgi (2022); Freund & Hopkins (2023) so far don't 't yield results in practice for datasets of dimension 4 or greater, due to running times which scale exponentially in d and/or prohibitively strong assumptions on X X1,...a X
2

---

Published as a conference paper at ICLR 2025
Robust Regression
Brittle Regression
0.8
Y= 1.0x, 0.1X,
0.8
Fit: Y 1.0X, 0.6X,
0.6
Inliers Y== +.00k
Intiers fitt Y= 1.00, 1.4e2
02-
0.
0.0
X1
X1
(a) A robust dataset whose robustness cannot he certified by continuous algorithms such as Bakshi Prasad (2021); Freund & Hopkins (2023).
(h) A small perturbation 1a creates brittleness which is detected by AMPP (Broderick et al. (2020)) or Kuschnig et al. (2021).
Figure 1: A comparison of two regressions. Figure la shows regression from main variable X1 and an indicator variable X2 which is set to on only a very small subset of the samples (ze 1%). The labels Y are drawn from normal distribution around X1, resulting in an OLS vector 3 whose first coefficient is positive and whose sign robust to removing 2 15% of its samples. As shown in Claim G.I, we can perturb only the X2 values of the inlier samples to produce an extremely brittle regression (Figure lb). Because most current approaches to estimating the robustness of a linear regression produce outputs which vary smoothly with the input dataset (such as gradient descent Broderick et al. (2020), semidefinite programming Bakshi & Prasad (2021), or spectral decompositions Freund Hopkins (2023)), they cannot differentiate between these cases.
1.1 OUR CONTRIBUTIONS
We present and analyze new algorithms, ACRE and OHARE, which provide lower bounds ka (e), certifying robustness of OLS regression. Our algorithms provide the first nontrival bounds on the number of samples which must be removed flip the signs of important parameter estimates for benchmark datasets studied in prior work (including regressions with dimension d > 200 and with 30000 samples). We evaluate our algorithms experimentally and theory.
ACRE (Algorithm for Certifying Robustness Efficiently) takes as input a dataset X E Raxd Y R" and vector E RRd, runs in time O (n2d + n² log(n)). and outputs a set of upper and lower bounds U,L _ on the removal effects such that U2 2 A& > Li. In particular, this runtime avoids exponential dependence on k, d, and n. The upper and lower bounds ACRE provides are valid even making no assumptions whatsoever on and When X and Y are drawn from sufficiently "nice" distribution (such as linear model with subgaussian features and labels), then the bounds are also good, meaning that the upper and lower bounds are close to matching (see Theorem 1.2). We present ACRE in Section 3.
However, there a very important class datasets on which ACRE still provides very loose bounds: those using one-hot encodings (also known indicator dummy variables) to express categorical features. Even though one-hot encoded datasets can yield robust regressions, certifying this is challenging because of singularities which emerge in the covariance when samples are removed (see Figure 1).
OHARE (One-Hor aware Algorithm for certifying Robustness Efficiently) extends ACRE to certify robustness of datasets with a mix continuous and categorical features. It uses dynamic programming in conjunction with fine-grained annebralgeebric analysis of the contribution of categorical features. OHARE takes as input a dataset X E [nx(d+m) (where of the features represent one-hot encoding and the other are some continuous features) and a direction of interest e E Rd within the continuous features, runs in time O (n² + m) + n n2m log(n)) and outputs upper and lower bounds on the removal effect along the axis e. We present an overview of OHARE Section 3.5, with a detailed description deferred to Appendix F.
3

---

Published as a conference paper at ICLR 2025
The most important property of both ACRE and OHARE is that the bounds they produce are valid regardless of any assumptions on the dataset:
Theorem 1.1 (Correctness). Given e, X, and Y. ACRE and OHARE output lists of upper/lower bounds U, L E IR" S.I. VhE La S Ax(c)=
max SC
- -s, S Uk
The proof of Theorem 1.1 is given in Section 3.3 for ACRE and Section A for OHARE On its own, Theorem 1.1 says little about the usefulness of the upper and lower bounds L3, Ug. We provide two types of evidence that the bounds produced by ACRE and OHARE are interesting. First, demonstrate on real-world econometric datasets studied in prior work on robustness auditing that ACRE and OHARE produce significantly better lower bounds bounds than were previously known (see Figure 2 and Table 1). Second, we prove that both ACRE and OHARE produce nearly-matching upper and lower bounds under relatively mild distributional assumptions on X and Y, for the interesting range of k.
INTERESTING VALUES OF k For a direction e, we emphasize two values of kzr the number of removals needed to shift (B,e) outside its 95% confidence interval, and kiign( (e) k(s.e)- the number to flip the sign of (3, e). In the parameter estimation setting, (3, e} and 2a are often of similar magnitude, because rejecting null hypothesis often involves placing the estimator {8, e) in confidence interval which does not contain 0.
For comparison with prior works, we focus our experiments on ( We provide lower bounds on kegg(c) for benchmark datasets drawn from important studies in economies and social sciences, first investigated in the context of robustness auditing by Broderick et al. (2020).
Experimental Results
We study real-world datasets corresponding to each of the parameter estimation use-cases listed above: Nightlights Martinez (2022) (correlation controlled for additional features), Cash Transfer Angelucci & De Giorgi (2009) (randomized control trial), and the Oregon Health Insurance Experiment (OHIE) Finkelstein et al. (2012) (IV regression), with 14 distinct linear or instrumental-variabll regressions drawn from the corresponding papers, all of which appeared in top econometrics journals. In many cases, our lower bounds match known upper bounds up to a factor of 2 or 3, where no nontrivial lower bounds were previously known; see Figure and Table
To illustrate, consider Nightlights: Martinez (2022) studies whether democractic countries publish more accurate economic growth estimates than dictatorships, after controlling for variables like regional stability and wealth in natural resources. Martinez. formulates this as linear regression with dimension d 209, over 200 of which correspond to one-hot encoded categorical variables. The sign and statistical significance of single coordinate of /3 govern the conclusion of the study. Algorithms from prior work find subset of 2.8% of the samples which can be removed to reverse Martinez (2022)'s main conclusion, but prior algorithms could not rule out the existence of much smaller subsets. Our algorithm OHARE provides a certificate that no subset of < 0.7% of the samples would reverse the study's 's conclusion. See Table and Appendix C for our results Nightlights and the 13 other regressions we audit, and a detailed discussion of our experiments.
An implementation of our algorithms is available via Github. Our implementation is efficient enough to run our algorithms with n up to 3 x 10 and d up to 10 on a single CPU core with < 64G B of RAM. The main bottleneck in practice is storing floating-poit matrices of size n each.
Theory for ACRE Without some assumptions on X, Y. finding matching upper and lower bounds on (e(e) computationally intractable, under standard complexity assumptions Moitra & Rohatgi (2022). So, we analyze tightness of the bounds produced by ACRE and OHARE E under some relatively mild distributional assumptions on X and Y. Our main assumption for ACRE will be that the samples X1,..., X,, are drawn üid from well-behaved distribution:
Definition 1 (Well-Behaved Distribution). We say that a mean-zero distribution X on IRd with covariance Σ Ex-x [XX]] is wehl-behaved if it has exponentially decaying tails in the sense that
3C > 0 Ye E gd-1
Pr X~x (1,E-1//xx) > > S <xpp (t())
4

---

Published as a conference paper at ICLR 2025
Removals for Sign Change
ACRE on Synthetic
Aule)
ACREx
314
ACREaedix
Fround Hookins
K2C21
AMP
20
(a) A comparison of OHARE and known upper hounds on benchmark datasets.
(b) A comparison of ACRE and known bounds on synthetic dataset (AMIP and KZC coincide).
Figure 2: A comparison of our ACRE and OHARE algorithms with previous techniques. In Figure 2a, we plot the number of removals required to flip the sign of several linear regressions from landmark econometrics studies Martinez (2022); Angelucci & De Giorgi (2009); Finkelstein et al. (2012). Each of these studies contains number of linear regression central to their analyses, which include several applications of linear regression, such estimating correlation controlled for additional covariates, treatment effects, and instrumental variables regression. For each regression, we run AMIP Broderick et al. (2020) and KZC Kuschnig et al. (2021) obtain base-line upper bounds keign and compare the results to lower bounds produced by OHARE We list the number of samples and the dimension of each regression below the plot. In Figure 2b, we consider synthetic dataset comprised of n = 4000 samples in dimension d = 50, and plot bounds on the removal effects A& (e).. In this plot, the roles are reversed, with AMIP and KZC representing lower bounds on the removal effects, while our ACRE algorithm gives the first practical upper bound. We compare the bounds produced by ACRE to the previous state-of -htt for efficiently computable upper bounds Freund Hopkins (2023). Moreover, to ground the scale of the plot, consider the different bounds on 12 (the number of removals required to shift the regression results outside of their 95% confidence intervals). The ACRE algorithm has two possible backends spectral or RTI (see Section 4). RTI is more efficient and performs better practice, while the spectral analysis which uses ideas from Freund and Hopkins' algorithm has a somewhat slower runtime (Ō (n²) and offers a logarithmic advantage in some synthetic datasets. The bound produced by ACRE is almost tight on this range of values of while Freund and Hopkins' algorithm yields a trivial bound.
Note that the class of well-behaved distributions contains all subgaussian (C = and all subexpo- nential distributions (C = 1), but is not limited to these sets.
We will assume that the labels .......
, Yn are drawn according a ground-truth linear model specified by an unknown vector Sg E IRd.. Concretely, we assume Y, (Bg.. X2) + c; where (1, c1...., On are iid from A (1, o²) for an unknown variance parameter g² > 0.
Theorem 1.2 (Tightness of ACRE, Proof Section E). Let n, E N, e, B, E Rd, X,Y, and
be as above. There exists kithesshldd bounds Lg, Up produced by ACRE satisfy
θ min
Vd =z }) such that for all S kehreshold. the
Uk 1
d d+hvdd kvd
1+0
(2)
L
n
Note that this theorem holds even when the covariance E of X' is unknown a priori.
RELATIONSHIP OF k, d, AND n Theorem 1.2 guarantees that ACRE gives nearly optimal bounds so long > d and the number of removals is most k < @(min(n/ Vd, n² /d²)); note that in this regime the RHS of (2) is 1 + o(1). First of all, OLS is only appropriate when n 2 d, and all the datasets which perform experiments have well in excess of d. The range of interesting values
5

---

Published as a conference paper at ICLR 2025
of l is more subtle to illustrate, consider (e). Assuming reasonably well-behaved samples, expect 220 (e) O(vR), as long also have > d4/3, ACRE gives nearly tight bounds on (e). This represents mild multiplicative overhead of dz/33 samples compared to the d required anyway to use OLS regression.
Even though they are mild, the assumptions for ACRE are not satisfied by the real-world datasets used in our experiments, because of the presence of one-hot encoded categorical features, which is the reason we design OHARE in the first place. We also prove tightness theorem for OHARE - we now turn to the assumptions on X, Y which underlie it.
Theory for OHARE
We study regression in d + m dimensions that is, X E (= The block of m coordinates will be one-hot encoding of categorical variable, while the block of d coordinates will act as in the ACRE setting. Formally, let n E N and let Bi,..., B,n partition [r] into m buckets. Let e, Aat [R with supported only on the first d coordinates, and > O. For [n], let , X be iid draws from a d-dimensional well-behaved distribution and let X; be X concatenated with the j-th indicator vector, where Y; = (Bgt, Xz) + 6; where e1,- E1.-..,6n ~O,0,, a²).
j(i) is such that i E By. Finally, let
Theorem 1.3 (Tightness of OHARE, informal, see Section F). Let X,Y,e be described above. For any arbitrarily small & > O, if all buckets have sizes nf vd < [By] < 0.49m, and n 2 d5/4+0(1), then with high probability, for all l < kitreshold, where Rithrehhold = θ [mnn Va az. n the upper and lower bounds produced by OHARE satisfy
Us =1+0
(Vlogm) (v
Lx
Careful analysis is needed to prove Theorem 1.3 under the relatively weak assumptions [B]] > n v and n 2 (5/4+0(1), The stronger assumptions [B] > d or n 2 d would simplify the analysis. But neither assumption would be valid for all of our real-world datasets. Getting away with such weak assumptions ultimately requires to put together number of technical tools, including novel matrix concentration arguments (e.g. Lemma 121
Additionally, the error term 1/vlog which we believe is nearly tight, goes to zero slowly compared to the error term in Theorem 1.2 - to capture this fine-grained behavior of Uv/ our proof carefully exploits Gaussian anticoncentration.
2 PRELIMINARIES
Let (Xi,Yi),... ......., (Xn, Yn) E (d(+1) represent features/covariatee and labels/target variables of a linear regression instance. We always assume n 2 d. Let Σ XTX E dx denote the (un- normalized) empirical second moment of X, let 3 denote the OLS fit = - let R = 3X E R" denote the residuals on the complete regression. Finally, let e E Rd be some "direction of interest" along which wish to certify the robustness of B. Using standard normalization techniques, we may ensure that e E gd-1 has norm and I.
Rdd and
For any S [n] representing some subset of the samples, let Xs, Ys represent the samples limited to only those whose indices lie in S. Similarly, let Es, Bs denote the empirical second moment and regression when using only the samples in S T. Note that while we could set Σ removing some of the samples may change the covariance matrix Es = Σ - En # Σ.
Finally, we use standard asymptotic notation 0(-), O()). and we write ((n) = (g(n)) if there is constant C' such that fn) = Ogg(n) log" n),, and similarly for +.
3 ACRE: CERTIFYING ROBUSTNESS WITHOUT CATEGORICAL FEATURES
In this section we present ACRE (Algorithm for Certifying Robustness Efficiently), our algorithm for certifying robustness of regressions without categorical features. At the end of this section we give an overview of OHARE, but due space constraints defer the details of OHARE to Appendix A.

---

Published as a conference paper at ICLR 2025
3.1 SEPARATING FIRST ORDER AND HIGHER ORDER EFFECTS ON THE OLS FIT 3
We split the effect of data removal on 3 into a first order term and a higher order correction. The first order term linear in the datapoints X,, allowing us analyze it exactly. For well-behawe datasets, the higher order term is smaller in magnitude, so even loose bounds on the higher order will suffice generate tight bounds on the overall removal effect.
More concretely, let T' S [ni] be set of k [T'] < n samples we might remove from the regression data, and set [n|] \ T. simple analysis yields the identity
B Bs 25
Σ RXX;
where denotes the residuals the original regression and Es denotes the empirical 2nd moment of the retained samples Dg X x
The difficulty in analyzing equation (3) is the effect induced by the non-linear matrix inversion operation. Recall that we normalized our datasets so that the empirical second moment over the entire dataset Σ is the identity matrix. Eg generated by removing some the samples, so is no longer normalized.
Because only a very small number of samples were removed, we might hope Eg = Er still close to the identity matrix. Therefore, it makes sense try to develop equation (3) in orders of Er.
More concretely, we use the identity (I - -r)-1== I+ (I - ((---))-
=
Er to derive:
8- = E-
R2X, = Σ R ET Σ R,X,
iET
ET
(4)
first order term
higher order corecction
Projecting the first order term onto some axis e E Sd-1 yields the gradients influence scores used by the AMIP algorithm of Broderick al. (2020). Our analysis will focus bounding the higher order term.
3.2 MAXIMAL SUBSET SUM NORM (MSN) THE BACKEND OF ACRE
Under the hood of ACRE is a simple algorithm which places upper/lower bounds on the following optimization problem.
Problem 2 (Maximal Subset sum Norm (MSN)'). ) Given of vectors U1 ....... Un Rd with Gram
malrix G = ((v,, 15) vy)) we define
vk E [n]
MSN, (G)
max TC
max VIGGI
TC m ITI=
ITi=
constant-factor approximation MSN would refute the small-set expansion hypothesis Hopkins Li (2019), so we aim for MSN-bounding algorithms which place upper and lower bounds on the optimal value, with the aim that these bounds are close to tight on well-behaved v;s. For our purposes, a simple algorithm in Section 4 gives useful bounds, but ACRE can use any MSN-bounding algorithm as a subroutine, and improved MSN- ASS-dounding algorithms will lead improved performance for ACRE.
For now, we treat MSN- ASS-bboundig as a black- box, and show how ACRE produces its upper and lower bounds Uk. Lg by making few calls to an MSN-bounding algorithm.
3.3 REDUCING ROBUSTNESS CERTIFICATION TO MSN-BOUNDING
Recall equation (4) for the effect of removals on an OLS regression. Projecting onto we have
When the vectors have mean (Eeeta) Vi 0), MSN is equivalent resilience Steinhardt et al. (2017).
7

---

Published as a conference paper at ICLR 2025
(e, Bs)
c, Dg Σ
R
(X
2
Ere, ERix, iET
(5)
iET
iET
firsi order term
high order term
We compute the first order term of equation (5) exactly for all [n]] via a greedy algorithm time On (n)) For the rest of our analysis, focus on bounding the maximum value of the high order term. We use the following bound:
high order term| maxx(((33)))33 D)ll
Σ X,R leT
(6)
where max(A(Eg")) is the largest eigenvalue of Σg We show that each of the three terms in the RHS of equation (6) can be upper-bounded by the value of an MSN problem. The last term, Dier X; ||, is already corresponds MSN problem with the Gram matrix GRX diag (R) G diag (R), focus the other two terms.
MSN bound for max(A(2ig)) We start by simplifying the Vi term. Recall that Ds = 1 Mr, allowing us use
max {A (2555)
- 1 - max ({(T)}
(7)
so long max {A (ET)} < 1. Over the next few lines we bound assumption. We apply the inequality
|ET|], allowing to verify this
max (A(ET))
Σ
Σ X. & IET
>+EA(E)))
where || is the Frobenius norn of matrix M (&g norm of the vector of eigenvalues) and & denotes tensor product. So have MSN problem with the vectors X, @ X.
Even though this MSN is represented by n vectors of dimension df, its Gram matrix represen- tation Gxox still be computed in time O(n2d), d), by computing the Gram matrix Gx (XX, and squaring its entries to obtain
Gxox ((X, @ X,, @ Xy))i,semm = X()) (JE(M)
MSN bound for Ere Recall Ex Eier XIXT. Let Gx(x.)) be the Gram matrix of (X,(Xx,e))eenn So,
ETell
Σ X)
< <SN (Gx(x,)))
iET
3.4 ALGORITHM
Combining the results of the analysis above yields the following expression and the corresponding Algorithm 1:
A (e) (first-order term); <
MSN; (GxR) MSNN (Gxz)
MSN; (Gxwx)
8

---

Published as a conference paper at ICLR 2025
Algorithm 1: ACRE (Algorithm for Certifying Robustness Efficiently)
Input: Linear regression problem X E IR Y E IR., direction of interest E R
MSN-bounding algorithm M
Output: Upper and lower bounds U, L E I such that Us 2 (e(e) Lx
Compute the Gram matrix Gx = X E IR"x";
Compute the projection of the samples the direction of interest Z Xe;
3 Define A = cumulat ivee sum (sorted( (RZ))
4 Gxax = pointwise square of the entries of Gx;
GXR diag (R) Gx diag (R);
6 Gx(X,)) = diag (2) Gx diag (Z);
Run the MSN-bound algorithm .M on these Gxxx, GxR, Gx(x,e) to compute upper bounds Mxæx. MxR, (x.e) E :::
8 return U, A+ Mxxx Mxxxx
// pointwise operations
3.5 OHARE: AWARENESS OF CATEGORICAL FEATURES
We present an overview of OHARE (One-Hot aware Algorithm for certifying Robustness Efficiently), deferring details to the appendix. Suppose that i,.... X,, gd+m consist of d continuous-valle valued features and single categorical feature with m categories, one-hot encoded.
The bounds computed by ACRE are valid for such Xj.... X,. But, consider removing the samples T comprising any single category, encoded in coordinate i; let S = [n]] T. The matrix Σs is singular, since all variance from category i has been removed. So our approach to bounding the high-order term from (6) by pulling out max (A(Eg))) is doomed to failure once k exceeds the size of the smallest category, since max (axx5)(23) )) co. We will assume that the direction of interest lies orthogonal to the one-hot features,
E RRd.
The key idea in OHARE is to rephrase the OLS algorithm as a two-phase process, first explicitly controlling for the categorical feature by computing a "controlled" dataset {(X,, Yi) C Rd+1, then performing OLS on the controlled dataset to arrive at 3 E IR.d. We show that this process yields the same which would have been produced by running OLS on the original dataset ((X,, Y2) he( (Claim A. and restricting to the span orthogonal to the one-hot encoding.
We derive explicit formulae for X., Y, by analyzing the Sraa-Schmidtt orthogonalization process which we call "reaveraging". The upshot is that we replace each term in (6) as well as the first order effect, with two terms: one corresponding to the direct effect of sample removals the X, Y regression, and one corresponding to effects of removing Xy, Yr on the remaining controlled samples Xs, Ys through reaveraging. Crucially, this process allows us to certify that the matrix Σs is nonsingular even in cases where Dg can be singular.
To bound the new correction term coming from the influence of categorical features on the sample- removal effect, we knapsack-style dynamic program to combine bounds the influence of data removals from each category into a single bound by searching over partitions = K1 +... + km-
4 MSN-BOUNDING ALGORIHTS
In this section we discuss the simple MSN- bounding algorithm we use as the backend of ACRE and OHARE for all our experiemnts on real-world data. We call this algorithm Refined Triangle Inequality (RTI). We implemented other ASN-bbuudiig algorithms, in particular one based on eigenvalues and eigenvectors of the Gram matrix G. but found that they improved over RTI only on synthetic data, so we defer them to the appendix.
RTI relies the following inequality, evaluating the RHS via greedy algorithm:
max IT
Σ X
max =
Σ (X,,
S
Σ
(X,, X,).
(8)
|T) II..S (ETJES,
iET
JJT
9

---

Published as a conference paper at ICLR 2025
Algorithm 2: Refined Triangle Inequality
Input: Gram matrix G of size n x n where Gi = 2,)
Output:
A vector V of length n, where Vi is upper bound on the Eg norm of the sum of any kt vectors in Z, for
to n Sort each row of G in decreasing order;
2 Compute the cumulative sum of the rows of G and store the result in C;
Sort the columns of C' in decreasing order;
Compute the cumulative sums of the columns of C' and store the results in S:
for k 1 to n do
L Set Vi to be / /
return V;
Greedy Algorithm for Diagnosing Robustness Failures via MSN We also implement a simple greedy algorithm to compute lower bounds on MSN, discussed in Section B. This algorithm is not used in ACRE or OHARE, but can be used to diagnose robustness failures by finding subsets of influential samples, thereby complementing AMIP.
PRIOR WORK AND FUTURE DIRECTIONS
Prior Work Robustness in linear regression too vast survey here, so we restrict attention to recent works in robustness auditing. As previously discussed, our work is preceded by Broderick et al. (2020); Kuschnig al. (2021); Moitra & Rohatgi (2022); Freund Hopkins (2023), all studying robustness auditing for least-squares regression. Unlike any of these prior works, our algorithms provide nontrivial lower bounds on ky practice for datasets with tens/hundreds of dimensions. All these algorithms and ours fit into the broader tradition of influence functions as a measure of robustness in regression, dating at least to Cook & Weisberg (1980).
Our algorithms are partly inspired by recent developments in algorithmic robust statistics Diakonikolas Kane (2023) and references therein. While the main goal in robust statistics differs somewhat from robustness auditing, modern algorithms for robust regression typically contain subroutines for tasks very similar to robustness auditing. But the subroutines recent breakthroughs in robust regression Klivans et al. (2018); Bakshi & Prasad (2021) due to reliance on semidefinite programming.
practically implementable
Future Directions
We propose several directions for future work:
BEYOND OLS Given the prevalence of regression beyond ordinary least squares in machine learning, an important next step is to design algorithms to certify robustness of other regression methods which arise by minimizing convex loss e.g. logistic regression and LASSO Tibshirani (1996).
APPLICATIONS TO DIFFERENTIAL PRIVACY (DP) DP Dwork al. (2006) is the gold-standard mathematically rigorous approach to protecting privacy of individuals represented in dataset. Tighter certificates of robustness for regression have great potential improve privacy-accurage tradeoffss in private regression Dwork & Lei (2009); poor privacy- tradeoffs are major roadblock to widespread adoption of private data analysis techniques.
INTERPRETATIONS OF ROBUSTNESS CERTIFICATES It is appealing intuition that statistical conclusions which are robust to removing many samples should generalize better formalizations of the relationship between stability and generalization have been highly influential, e.g. Bousquet & Elisseeff (2002). Can this intuition be formalized? Can robustness certificates yield e.g. tighter empirical confidence intervals, or out-of-distribution generalization guarantees?
Removing small set of datapoints is just one of many potential ways to perturb a dataset. Can we certify robustness of OLS or other regression algorithms to other types of dataset perturbation, e.g. l or f.e- bouunde perturbations of the feature vectors?
BEYOND SAMPLE REMOVAL
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by NSF CAREER award no. 2238080 and CSAIL Alliances.
REFERENCES
Manuela Angelucci and Giacomo De Giorgi. Indirect effects of an aid program: how do cash transfers affect ineligibles' consumption? American economic review, 9984)888-5008 2009.
Ainesh Bakshi and Adarsh Prasad. Robust linear regression: Optimal rates in polynomial time. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 102-115, 2021.
Diether W Beuermann, Nicolas L. Bottan, Bridget Hoffmann, C Kirabo Jackson, and Diego Vera- Cossio. Does education prevent job loss during downturns? evidence from exogenous school assignments and covid-19 in barbados. European Economic Review, 162:104675, 2024.
Matthew V Bondy, Samuel V Cai, and John J Donohue. Estimating the effect of us concealed carry laws on homicide: A replication and sensitivity analysis. International Review of Law and Economics, 75:106141, 2023.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research,
2002.
Tamara Broderick, Ryan Giordano, and Rachael Meager. An automatic finite-sample robustness metric: Can dropping little data change conclusions. arXiv preprint 1.Xi::20111149900 16, 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, Working Paper, 2023.
Dennis Cook and Sanford Weisberg. Characterizations of empirical influence function for detecting influential cases in regression. Technometrics, 22(4):495-55) 508, 1980.
Elwyn Davies, Peter Deffebach, Leonardo lacovone, and David Mckenzie. Training microen- trepreneurs over zoom: Experimental evidence from mexico. Journal of Development Economics, 167:103244, 2024.
Michael Di and Ke Xu. Covid-19 vaccine and post-pandemic recovery: Evidence from bitcoin cross-asset implied volatility spillover. Finance Research Letters, 50: 103289, 2022.
Ilias Diakonikolas and Daniel M Kane, Algorithmic high-dimensional robust statistics. Cambridge university press, 2023.
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-fost annual ACM symposium on Theory of computing, pp. 371-380, 2009.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryplography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-284, Springer, 2006.
Amy Finkelstein, Sarah Taubman, Bill Wright, Mira Bernstein, Jonathan Gruber, Joseph P Newhouse, Heidi Allen, Katherine Baicker, and Oregon Health Study Group. The oregon health insurance experiment: evidence from the first year. The Quarterly journal of economics, 127(3): 1057-11666 2012.
Daniel Freund and Samuel B Hopkins. Towards practical robustness auditing for linear regression. arXiv preprint arXiv:2307.16311 2023.
J Vernon Henderson, Adam Storeygard, and David N Weil. Mcasuring economic growth from outer space. American economic review, 102(2):994-108)) 1028, 2012.
Samuel B Hopkins and Jerry Li. How hard is robust mean estimation? In Conference on learning theory, pp. 1649-1682. PMLR, 2019.
11

---

Published as a conference paper at ICLR 2025
Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclere, and Aleksander Madry. Data- models: Predicting predictions from training data. In Proceedings of the 39th International Conference Machine Learning, 2022.
Adam Klivans, Pravesh K Kothari, and Raghu Meka. Efficient algorithms for outlier-robust regression.. In Conference On Learning Theory, pp. 1420-1430. PMLR, 2018.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pp. 1885-1899 1894. PMLR, 2017.
Nikolas Kuschnig. Gregor Zens, and Jesús Crespo Cuaresma. Hidden in plain sight: Influential sets in linear models. 2021.
Luis R Martinez. How much should trust the dictator's gdp growth estimates? Journal of Political Economy, (30(10):73112269) 2022.
Ankur Moitra and Dhruv Robatgi. Provably auditing ordinary least squares in low dimensions. arXiv preprint arXiv:2205. 14284, 2022.
Jacob Steinhardt, Moses Charikar, and Gregory Valiant. Resilience: A criterion for learning in the presence of arbitrary outliers. arXiv preprint arXiv: 2017.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):267-288, 1996.
Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-22 2015.
Lucca Zachmann, Chloe McCallum, and Robert Finger. Nudging farmers towards low-pesticide practices: Evidence from randomized experiment in viticulture. Journal of the Agricultural and Applied Economics Association, 2(3):497-514, 2023.
12

---

Published as a conference paper at ICLR 2025
A SARGORIICAL-WARE ROBUSTNESS ANALYSIS (OHARE)
ACRE encounters an issue when the regression includes a one-hot encoding of a categorical feature. This is because removing all the samples from one category of the one-hot encoding could cause Es to have a singularity, making our bound, which depends linearly on max{A(2s })) meaningless.
} effectively
Moreover, as we show in Appendix G, it is possible to perturb datasets with one-hot encodings, even those which are robust many sample removals, to make them extremely brittle to sample removals. Therefore, any "continuous" algorithm which does not somehow utilize the discreteness of the one-hot encoding doomed to fail.
A.1 REGRESSING OVER A CATEGORICAL FEATURE
Consider a linear regression over set of feature vectors, P; E Rd for i E and an additional m dimensions corresponding to a one-hot encoding with buckets B1 LJ U Bm = [rz]. where we want to fit our labels L; to model of the form
L ~
F +
Σ tylien jE(m)
JE/4
This linear regression would be represented by matrix X R whose rows are the samples X, = -F,, .......... l..B.... Then, if we are interested in the correlation between one of the continuous features F.j and the labels Y (controlled for the rest of categorical continuous features), we may compute this correlation by running an OLS regression B (XTX)-IXTY and output the relevant entry 33 of the fit.
Analyzing the robustness of this process is challenging, and we proceed by performing the Gram Schmidt orthogonalization between the dummy variables and the continuous features explicitly. Before delving into the details of this analysis, note that OHARE can be used to certify robustness for a slightly more general class of regressions. Using this more general notation will help motivate orthogonalization process and is crucial for certifying the robustness of weighted regressions with categorical features (such as the ones in the OHIE study see Appendix C.4).
Indeed, let ,.,..., Um be the columns representing the dummy variables. So long for any sample i E [ra] there is a unique = b(t) (representing the bucket to which the ith sample belongs) such that uy.s F (and for all j + j', we have uy' 0). This property ensures that for any S C [m). these columns are still perpendicular to one another uj.s 1 uy,s.
1. For each bucket B3 C [n). we compute the weighted averages over the features J3.a uut F = EieR, uy,sf,, ||u]|2 bucket. When the samples are unweighted Uj,i = B, these are equal to the averages
[|u=]| Uj,; and over the labels é Eien, uj.et
||uy||2 új for samples from this
over the features/ / labels fn Exe B, [F.,] and E ExeB, [L,], and when the samples weighted, these are the projections of the continuous features / labels onto the space spanned by the indicator columns.
2. Compute the normalized features X E kdx= obtained by subtracting the feature averages of each bucket from its samples, and the normalized labels E I2" obtained by subtracting the average label from each bucket:
X, = Fi,: - So00
Y L, Lo())
3. Perform a linear regression on Y as function of X and output the fit B (XTX)-IXTY.
Claim A.I. The output of the process described above /3 is equal to the coefficients for the continuous features on a fall OLS with the dummy variables.
The proof of Claim A.1 follows directly by performing the Gram-Schmidt orthogonalization (to compute Σ E explicitly while taking the one-hot encoding columns into account (see Section A.6). This approach of explicitly writing Gram-Sehmidt orthogonalization to remove the effects of
13

---

Published as a conference paper at ICLR 2025
some of the controls could potentially be used whenever have two sets of features, one of which easier to analyze than the other.
Our focus one-hot encodings is due to their prevalence in econometrics datasets, along with the fact that, as we will see over the next few pages, the perpendicular structure of the indicator variables makes them particularly amenable such divide and conquer strategy (and much harder to deal with using previous techniques).
For ease of notation, will normalize the dummy variables so that ||u,|
1 for all j E [m].
A.2 FIRST ORDER EFFECTS
Claim A. allows us to reduce the problem of performing a regression on d continuous feature and categorical feature with m potential values into a regression on just reaveraged version of the d continuous features. Using this reduction, we can split the effects of removing samples from the smaller linear regression into direct removal effects that change the regression fit directly by removing samples from the d-dimensional regression X, Y, and reaveraging effects that shift the regression fit by causing the expectation of the data within each bucket to change (effectively shifting the values of the retained rows of X, Y).
In particular, we may again write
8 - Bs)
= e,
(9)
iES
where : is the value of after the new reaveraging due to the removal of the elements in T. More concretely, we have
8, = (01), where Ty
Σ
Xaug
V'EB
(10)
R; R. (b()) where rj
Σ
Rauj
VEB,nS
From here, we can derive elosed form formula for the new versions of all the terms in the previous analysis. For instance, the "first order effect" (i.e., the effect we would have seen on the regression, had Eg been equal to I), which was previously given by First Ordercontinuous >ieT R2 (e, X,) is now given by
X.Ri ) = --(1)) E(x, 2002) 2000)6()))))..
First OrdeTonc-hot
e, Σ
e, Σ Σ (X, - r, )===
jE(m] iEB,nS
((e,
e, Σ Σ
X.R.
Σ
2j Σ
JE(m] iEB
JElm]
iEB
e, Σ Σ
X.R.
+
e, Σ r
Σ
Uz
jE(m] iEB
jE(m)
iEB,nS
EieByn Nen5.
X
Σ
Σ
Rauz
Σ iETnB,
(e, X.) Uj
|
fE/m)
VETrB,
First Order
Correction Term
(11)
14

---

Published as a conference paper at ICLR 2025
In order to bound the right-hand-side of equation (11), consider each of the terms EiETnB, Rg X,), EiETnB, Raug, and Lienne, (e, X,) UJ separately. Using a greedy al- gorithm, we can maximize / minimize each of these terms separately as a function of ky [T Byl can then combine these into a bound the form
(kt)
bound (k; = d2 (kg)
{1le,ss,1??
min 8, [(tt)
where
d,(kg) = max T,CB;
Σ
Rá (e, Xi)
[ IET,
(kg) max
max Bj [ky SET,
Reuja
max TJCB; [Tyl= iET,
Σ (e, Xe)
min Σ Rauza TJCB [2y EET,
min T,BB Tty Tyl=ky iEI,
Σ (e, Xz) Ujjt
9f (kz) min
min ET
R,uja
max T.C ITil=K,
Σ (e, (e) ugs
max 1,CB TTi=k,
Σ Rauza
min Σ (e, X:) uga
k
SE,
VEI
|T SET
For k; nij there is reaveraging effect and bound (n,) dz(ng).
We can then combine these bounds on the individual buckets by using dynamic programming algorithm to solve the integer knapsack problem of
max
bound (ký)
5mmm]
From equation (11), is clear that these maximizations yield upper and lower bounds on the maximal first order removal effect
)}
max ki + km
A:
bound (kz)
max SE(!"))
e,
X
max to +..... Rin
bound (kz)
JE(m]
JE(m)
The upper bound on the overall first order effect tends to be larger than the continuous first order effect but only by 1 o(1) factor. This is because d, tends be the dominant effect, while ej are typically much smaller.
For instance, consider an unweighted regression on normally distributed samples (X,, Y:), and let O V Eienn R2 denote the noot-mean-square (RMS) scale of the residuals. With high probability, we can find removal sets that would have dj R ky LR log(n/k) (by taking only samples which are the tail end of the distribution of having both large residual and large inner product with the direction of interest). On the other hand, for sufficiently large buckets [B, > log(n), we
expect to have ej- = 0 B.I...
k.
<0
kg (ORR.
they tend to be somewhat smaller than dj.
Moreover, by using a dynamic programming algorithm, we can enforce the constraint that the number of samples removed from each bucket k; has to be the same for the direct effects and for the reaveraging effect. This constraint limits causes the contribution of the reaveraging effects to be even smaller, they require taking many samples from the same bucket to enjoy the quadratic scaling of ky. while the more dominant direct effects are typically optimized by selecting samples evenly from the buckets.
15

---

Published as a conference paper at ICLR 2025
Algorithm 3: Dynamic Programming Algorithm for Integer Knapsack
Input: List of bounds (bound, [ky)]] maximal budget kmax
Output: Array F where F[k] is the highest total score possible for budget it m < [(boundd(k;))
2 kmax f- kmax +1;
// Adjusting for 0-based indexing in NumPy arrays
3 Initialize F array of size (m 1) x kmax with -00;
Set the first column of F 0;
5 for j - 1 to m do bound <- boundy;
F(j. 0 (bouudddd) + bound : kimax];
F[ + max(F(i. Flj 1,:1);
for òg < 1 to min(kmax, 1en len(bound)) 1 do
10
Flj, 6% :] t max(F (f, 6% FIj 1,: 6x] + bound(og])
11
return Flm,: : kmax - 1]
A.3
HIGHI ORDER TERMS
We continue our analysis of equation (9). As in the continuous analysis, we have
(e, 38)
e, 2
R,
iES
(,, (Igg -1) Σ X,R,
e, I Σ R
ES
SES
(12)
First Order ooee bot +
135 (1- Eig)
XiRi
iES
< First Order one hot + max {a (x($5)) x
||(1 Essee
ell
Σ iES
X.R.
To analyze the first higher order terms, begin with an analysis of Eg. This analysis shows that Eg essentially behaves like Eg with minor correction for each bucket:
'S = Σ I
Σ
(X, 22
iSS
fElm) BEB
Σ
X1(X, - 2 u.,
Σ Φj
Σ
XT
jE[m) 88
5E(ml
iEBsns
(13)
= Σ
Σ
X Σ
Σ
XzUgi
Σ
X₁
=
jE[m] is
jE(m]
iEByrT
iEB,NT
1 Ex
XaUlit
Xiuys
|uyssl
jm(m]
iEBYnT
iEBynT
In order to bound max { ( = min x (is
from above, we begin by bounding max {A (Σr)} from above (using the same MSS-bboundig reductions from Section 3). We then MSN-bounding algorithm and the same dynamic programming above bound the term in
16

---

Published as a conference paper at ICLR 2025
equation (14) (MSN-bounding bound the individual terms and dynamic programming combine them).
)
}}
max
A
Σ Xiusit iEByNT
Σ iEBYNT
Xiug,
||s
JEmm]
(14)
2
max Ri
max T,S T3 mky
Xzuga
Km
jefm mins,
{Ilu,,s,)* 11²]
iET,
For each j, we can bound max D, {|EIET, Xeusss [Tyl=k MSN bounding algorithm. However, we can refine the results of this MSN bounding call (especially with regards larger values of k3 2 2
( from above by performing call to an
21 ), by utilizing the fact that ΣiEB, X, O, which implies that
{ Σ Xzuj,
Σ Xiuja IT,
max T,CB, (T) kyy-k
T.B. 1
Therefore, if My is the result of an MSN bounding algorithm (such as RTT) on the n, x nz Gram matrix of the samples in the jth bucket, we have the bound
Σ Xxus IET
s min (M,(())), - kz)
B, ky
Similarly, we may bound the other terms. Using equation (13), we have
(1-Es) E e=
+ Σ
Σ
Xauja
Σ
Xauja
6=
jE(m]
iEBynT
iEBYnT
(15)
(X,,e)))
Σ iETOB,
Xzuys
Σ IETnB,
(Xie)) uje
|us
IET
jE(m]
As usual, we bound the norm of the first term Eier X; (X,,e) using an MSN-bounding algorithm, and for each bucket, we bound ΣieTna, X1u3a and ΣieTnB, (X,,e) Un,a as a function of k, n Byl. We then combine these bounds using the triangle inequality, and the same symmetry and dynamic programming algorithm as above.
Finally, to bound
Eies R. we use the same analytic techniques to write
X = Σ Σ
(X, - I, ....
IS
jE(m] isB,ns
(16)
Σ
X,R,
Σ
Xauga
Σ
Raujs
|
NE
JE[mJ
iEB,nT
iEB,nT
which can be bounded by the same MSN symmetry dynamic programming above.
17

---

Published as a conference paper at ICLR 2025
A.4 THE OHARE ALGORITHM
Algorithm 4: The OHARE Algorithm
Input: Samples X; E Rd (s.t. X Rdxd) and residuals RG E R for i E [n]. vector Rd, separation of the samples into buckets b: [n]] + [m]] (based on some additional
categorical feature), weights w E R" (by default all 1s).
Output: U, L I= that bound the removal effects (e).).
/* Step 1: Split the samples and residuals by their b value into buckets BI...., Bm. S [m]
for j to m do
for Kj f 1 to [By] do Compute bound (k2) = dk(k)) + e((k)) 1B with ej and dj as defined above;
/* Step 2: Compute Influences using the ID Dynamic Programming Algorithm
Use the "ID Dynamic Programming Algorithm" defined above to compute the bounds on the direct influences and store the result Influences;
/ Step 3: Compute upper bounds on May, Uny Pky and CRy for each bucket
for jrnj+11 1 m do
Use an MSN bounding algorithm to compute an upper bound on Mr,- 2 max |Eirr
for all k3 E [ to compute Uk, =1 maX Eieruha Use a similar sort + cumulative sum to compute pE; maxT |T|=k {Eier Peus,il:
Use sort + cumulative
Use a similar sort + cumulative sum to compute Cky = ,,, {EiET Zeuis
10
Use the symmetry to refine our bounds
Mr, = min (M,y =, Pky == min {Pk,, Pky Ske == min (Sky,
Step 4: Compute indi rect contribut ions using the 2D Dynamic Programming Algorithm 11 Use 3 calls to the 2D Dynamic Programming Algorithm 6 to generate arrays from k u to the maximum over the choice of .y...., Km with total k of which non-zero of:
ME,
1. Indirect CS Contribution: Eje(m)
UNg
MkyPy; Uky
2. Indirect XR Contribution:
EjE(m)
MR, Un,
3. Indirect XZ Contribution: EjE(m)
/* Step Compute direct contributions using the KU Triangle Inequality
12 Use the KU Triangle Inequality also compute upper bounds on the Direct CS, XR, and XZ Contributions;
/* Step 6: Compute final bounds and return the result Direct XR+ Indinett XR x Direct Hndindieect XZ]
return Uk. La Influences + max,,
1-Diroet CS Indirest
A.5 SUPPLEMENTARY ALGORITHMS
We begin by an extension of the RTI Algorithm 2 that bounds the triangle inequality terms as a function of l (number of removals) and (number of unique buckets from which samples were removed). The basic idea is the same as with the original RTI algorithm and requires only minor adaptations to track which row-column pairs largest in their respective buckets.
18

---

Published as a conference paper at ICLR 2025
Algorithm 5: KU Triangle Inequality
Input:
Gram matrix G of size n x nt where Gij (U, U3) representing an MSN-bounding problem
Output: Matrix of size Umar x kmers where Va is an upper bound on the l2 norm of the sum of & vectors taken from unique buckets.
> Split each row of G into the largest and the non non- largest
entries per bucket.
Initialize m as the number of buckets;
Initialize as the number of vectors;
Compute bucket indices from bucket sizes;
for j - m do
Sort entries in each bucket j in decreasing order; Store the largest entry of each bucket in best_ent pest__nttres;
Remove these entries from the Gram matrix;
Compute the cumulative contributions of the largest and non-largest entries per bucket.
Compute best_uu _est____oot c_s__r_contiiiiin as cumulative sums of sorted
Compute best_kmmuccome Jemuu___omtruuuiinnn as cumulative sums the modified Gram matrix; x* Compute the contributions of each sample for the triangle inequality.
Initialize caanple_comtribbtee
array of -00;
II for u 4- to min(Umar. Kmaz) do
for k u to kmaaz do
13
Compute contributions by combining best_u_contte stt____ooorrbbbitons and muss__mmu_contrrbutate
Enforce the constraint that T must use exactly u separate
buckets.
for
j m do
15
Move the largest elements of each bucket to the start using partition;
16
Copy the largest elements best_ contributions:
17
Remove these elements from cumplee_cmttrbbbiie
18
Sort rest__contribttinns and compute their cumulative sums as gramssunbest_comrriiee Compute the norms squared using the constraints. Initialize
19
as an array of -o;;
for + 1 to Umaz do for k <- u to kmaz do Compute sum over u largest elements of sample_contriuutions and u largest elements of cumsum _estt contributions:
21
22
23
Update horms_ssuarees k.) k|];
/* Compute the norms and handle invalid values. Compute norms the square root of norms _suuredd;; return norms;
25
We also adapt Algorithm to the case where we wish to keep track of both the total number of removals and the number of unique buckets from which we remove samples.
19

---

Published as a conference paper at ICLR 2025
Algorithm 6: Dynamic Programming 2D
Input:
list bucket scores B
Output: A table V where (uu, k) is the maximal score for using unique buckets with total budget &
/* Initialize parameters and dynamic programming table
Compute cumulative sums of bucket lengths; Initialize dp_ table with -0o and set dp tablef: 0, 0] 0;
/+ Fill the dynamic programming table
for j - 1 to length of B do
Get the current bucket B[i]; Set min(m,,)::
Set k as min(n, cumsum bucket lengths(];;
/* Base case for the first bucket
if == 0 then
Set dp_table(0, 1, k] B[O][: k);
else
* Case where we do not update the table with new bucket
values
10
Set dp_lablelj, 1: u, k] dp_lablejj - 1, u,: kj;
+ Case where we add values from the new bucket for òN 1 to min(length of k]]],k) - do
11
12
Update lp__ablelj, u, 6g k) with the maximum of the current value and dp dp_tablelj - 1,: 1. k 5z] + B[j][d]]
return dp_table(-1e -1,;
A.6 PROOF OF CLAIM A.1
The main analytic idea we use in the OHARE algorithm is alternative description of what happens when we perform a linear regression while controlling for categorical feature. We formalise this process in Claim A. which we prove here:
Proof of Claim A.I. Let X (F) be the covariates for the original regression, Consider the Gram-Schmidt orthogonalization process, and define
(F-D-
where D UTU is the diagonal matrix whose jth entry is ||u]].
X now has block-diagonal covariance matrix
X 1000-((---))) -V----URY-----UT D)
These labels are now also perpendicular to the dummy variables U. Therefore, for = F DDD-UUF, = XT,, we have
Similarly, let y =
-- XTV
(F D-UU1F)(F---UT 0 D
F - -UTF (X (X-D-'UTY) (17)
5-1 D-NUT (D-UUYYY--
20

---

Published as a conference paper at ICLR 2025
B ADDITIONAL MSN-BOUNDING ALGORIHTSS
B. SPECTRAL DECOMPOSITION
At a high-level, this algorithm similarly tries to bound |>eer 2.11² 1,G1y for the same Gram matrix G, but here we use spectral decomposition. We refine the standard spectral algorithms which might output || max X(G) = vk max X(G). by computing naive bounds on the inner products between Lg and each of the top cigenvalues using a standard greedy algorithm.
Algorithm 7: Spectral Bound Algorithm
representing Gram matrix of set of vectors Gt,, (744, 2n) Output: A vector V whose kth entry an upper bound on maxp/]= ||Eier Zi|l Compute eigenvalues À
Input: A matrix G of size
An and corresponding eigenvectors " Un of G;
2 for k = 1 to n do
/* For each of the eigenvectors, compute upper and lower bounds on a; = (IT,u,) v.). To do this, we note that is the
sum of entries of v. so it is bounded from below by l sum over k smallest entries of e; and from above by sum over largest entries of U;
Sort the entries of each in ascending order and store the cumulative sum in &;; Sort entries of each e; descending order and store the cumulative sum in us;
/* Compute upper bound on ag² I u.
Compute b, = max uē]:
Combine this with bound on overall weight of spectral decomposition Σ, ==
If E
jei b, 2 k, set 6 = max (0, - - Ej{;bb}
Set V&= VE, Arbs:
return V:
B.2 GREEDY LOWER BOUND
In order to get some additional diagnostic capabilities and improve the interpretability our results, also implemented simple greedy algorithm that helps generate fower-bounde the MSNs. Algorithm initializes candidate set T to contain the longest vector v; in our MSN instance, and greedily adds vectors to this set in attempt increase [Eie vi as fast possible.
21

---

Published as a conference paper at ICLR 2025
Algorithm 8: Greedy Algorithm for Lower Bound and Candidate Set
Input: matrix G of size n X n representing Gram matrix of vectors, where Gij = my)
Output: ordering of the indices T, and series of lower bounds L3 T. GIT,, I ( G1r
Initialize empty list T := []:
2 Initialize the scores array A where A = G. for all i é [n];
x maps each index i E [n] to the change in 1,GIT caused by x/ adding to T.
Initialize Lo = 0;
while T < do
Select = argmax Ay;
Choose the index not in T with the maximum change in score.
Add i to I' and update La = -
/* Update the lower bounds by adding the score of the newly added index.
Update the scores Adjust A to reflect the change in 1,G1, after adding i */ T.
A 2G
8 return T and L;
In real-world datasets, we found that the upper bounds obtained by Algorithms 2 and 7 tend to be very close to the greedy lower bounds on their respective MSNs.
Moreover, when analyzing the Cash Transfer study (see Section C.3), noticed that our analysis behaved poorly in some regimes. Using this greedy lower bound technique, we were able to identify that this behaviour was caused by small number of households (< 0.5%) dominating the variance in ownershpp (> 80%), which was included the study in linear scale. Converting the land- ownership to logarithmic scale resolved this issue (allowing us certify robustness removing many more samples).
C APPLIED EXPERIMENTS
Our main experimental results are detailed in Table 1:
Paper
AMIP
KZC21
OHARE
Runtime
Memory
Nightlights
3895
209
136
110
29
25
3.81 GiB
Cash Transfer
4543
5
68
1.78 GiB
3769
18
21
21
17
4
2.80 GiB
4191
18
26
26
20
5
1.73 GiB
10781
18
225
224
119
50
11.20 GiB
9489
18
321
314
126
24 s
5.37 GiB
10368
18
570
555
178
29
6.59 GiB
OHIE
23361
18
257
257
77
9 5m5s
34.19 GiB
23361
18
149
149
40
9 m 10
43.50 GiB
23407
18
184
184
52
9m
10
43.55 GiB
21881
72
7 m9
38.64 GiB
21384
18
84
84
25
7 17
45.77 GiB
21601
18
118
118
31
7 m
20
46.21 GiB
23147
18
116
116
32
8
m.
51.53 GiB
Table 1: A comparison of the lower bounds ksign(e) produced by OHARE vs the corresponding upper bounds produced by AMIP and KZC. In all cases, no non-trivial lower bound was previously known. The runtimes listed for single core AMD processor.
22

---

Published as a conference paper at ICLR 2025
Throughout this section, we will present the details of the data analysis and experimental procedures used to generate Table
C.I METHODOLOGY OF TABLE
In Table 1, compare several bounds (e) (the number of removals required flip the sign of the "main" coefficient e) for several regressions taken from highly influential econometries datasets.
Before delving into the source each regression we give brief overview of the methodology used to construct each column of the table.
Metadata The first few columns ("Paper", "Regression", n. and d) give some of the metadata for the regression.
The paper column details which paper each regression was drawn from, and for papers with multiple regressions we list the name of each regression in the paper. For more details about each of these papers see the following subsections.
The and d columns list the number of samples and the dimension of each regression.
AMIP The AMIP algorithm by Broderick et al. Broderick et al. (2020) can be used to estimate the robustness of linear regression in one of two ways. The fastest option compute the AMIP gradients influence scores, and estimate that the number of samples one must remove in order to change the fit by certain amount by taking cummulative sum over the sorted gradients.
However, this method both typically tends to overestimate the robustness of a dataset, and despite this does not even provide formal upper bound on kisgg k2.- Instead, for experiments samples from most influential to least influential and remove them one at a time until the fit crosses the threshold we are considering.
the
The robustness estimation algorithm by Kusching et al. Kuschnig et al. (2021) utilizes greedy approach at each point we select the sample whose removal would have the greatest effect on our metric of interest and remove that sample. We repeat this process until the decision boundary has been crossed (in our case, until the sign the regression coefficient has been flipped).
KZC
As with AMIP, we report the size of the smallest set produced by the algorithm that actually produced a sign flip.
OHARE Assume WLOG that our coefficient of interest is positive in the original regression (3.e) > 0 (otherwise we set e' =e).
Running the OHARE algorithm yields series of upper bounds Us the removal effects. In particular, we know that for k = kisign we must have A&(e) > (8, e), so by computing
kOHARE(e) min (k E [n]] U (8,e)}
yields lower bound as ksign(e) 2 ROHARE(E).
Computational Resources the columns "Runtime" and "Memory", we list the total runtime and memory cost of running the OHARE algorithm in this case. All experiments were run a single core of an AMD EPYC 9654 96-Core Processor.
C.2 How MUCH SHOULD WE TRUST THE DICTATOR'S 's GDP GROWTH ESTIMATES?
C.2.1 PAPER OVERVIEW
Reliable estimates of GDP figures are crucial for analysts to assess the performance an economy. However, leaders often have variety of political and financial incentives manipulate GDP figures in order to improve their perception. Therefore, economists often use proxies to obtain independent estimates of these figures that may be harder to manipulate. One such method which has gained lot of attention in recent years is to simply measure the amount light emitted from a region at night (nightlights NTL),, observed by satellite imaging Henderson al. (2012).
23

---

Published as a conference paper at ICLR 2025
Martinez Martinez (2022) uses this proxy in conjunction with several well-known measures for the democracy of a country (such as the freedom-in -n in-the-world or FiW metric), in an effort to find evidence of GDP figure manipulation in autocratic regimes. One methods used by Martinez is to measure the "autocracy gradient in the elasticity of GDP". In practice, this translates to running regression of the form
In(GDP) #4 + + d0 (n(NTL);;, + di FiW. FiW + d (a[In(NTL) x FiWlar t (18)
where i represents the index of a country, t the year from which this sample was taken, μ4 and 5, control for country-specific or time-specific effects, Φn, Φ1, d2 control for the direct correlation between nightlights and GDP, as well as for any I 2nd order dependence between GDP and democracy, Φ3 is the main effect we wish to observe, and a positive value of c3 could be explained by autocratic regimes being more prone to embellishing their GDP figures.
Martinez reports a statistically significant positive value of da. as well as additional evidence for GDP figure manipulation in autocratic regimes (such larger difference between NTL-based estimates and reported GDP in years leading up to IMF evaluations autocratic regimes). Martinez hypothesises that the separation of powers and cross-cxaminationn of figures by opposition contribute to making GDP figures more reliable in democratic countries.
C.2.2 ROBUSTNESS
Martinez uses the AMIP tool Broderick et al. (2020) to assess the robustness of the regression (18). AMIP finds set of 136 samples whose removal flips the sign of the OLS fit on the [In(NTL) FFW] term. Kusching et al. Kuschnig et al. (2021) improve this upper bound on the stability by finding a set of 110 samples that flip the sign of the fit parameter.
Running our continuous regression toolkit on the Martinez dataset can only certify robustness to the removal of at most samples, the dataset contains one-hot encoding of the country and it contains only 8 samples from Monetenegro. To overcome this, we apply our one-hot aware algorithms to the same data, and are able certify the sign of this parameter Martinez' regression requires least ksign 2 29 to overturn.
C.3 INDIRECT EFFECTS OF AN AID PROGRAM: How Do CASH TRANSFERS AFFECT INELIGIBLES' CONSUMPTION?
C.3.1 PAPER OVERVIEW
Angelueci and De Giorgi Angelucci & De Giorgi (2009) study the indirect effect of the Progresa welfare program in Mexico. This program gave financial aid to eligible households within "treated" villages, and did not give aid ineligible households or households from "untreated" villages.
Angelucci and De Giorgi then track spending patterns of eligible and incligible households from both treated and untreated villages. They then use linear regressions to estimate the treatment effects on both eligible and ineligible households when controlling on various other features.
C.3.2 MINOR DIFFICULTIES IN USING THE DATA
We found two different regression formula that have been attributed to this paper. The formula use slightly different control, with one option controlling for: head of household age, sex, literacy and education level, household poverty index and amount of land owned, local poverty index, number of households in the village and "average shock" (to the best of our knowledge, this was the regression used in Angelucci and De Giorgi's original paper). The regression used in the later paper by Broderick et al. Broderick et al. (2020) also controls for head of household marital status and which region the samples came from (using one-hot encoding). Ultimately, these additional controls had very little effect on the fit parameters or their error bars, and we chose to focus on the latter to maintain consistency with previous benchmarks.
more significant issue is that the dataset also contained many clear outliers. For instance, almost all the entries of the column for head of household sex were either "hombre" or "mujer" with very small fraction (roughly 16 out of 59455 samples) having the value 9.0, and many columns had entries of "nr" (presumably no response).
24

---

Published as a conference paper at ICLR 2025
We removed these "bad samples" for the sake of our analysis (both to avoid regressing clearly problematic dataset, and also because not doing so would cause the regression to include nearly empty categories in several different one-hot encodings which is beyond the scope of the OHARE algorithm). This had only minor effect on the regression results.
Column
Values Removed
Samples Removed
hhhsex
9.0, nr nr, 2.0 nr
16
hhhalpha
hhhspouse
546
p16
146
hhhage
97% y más, no sabe, nr
205
Total
921
Table 2: Number and values of outliers we removed from each of the covariates in Angelucci and De Giorgi's study Angelucci & De Giorgi (2009).
C.3.3 ROBUSTNESS
We ran our tools on the 6 regressions from Angelucci and De Giorgi's paper (treatment effects on eligible ineligible over 3 periods). Our robustness lower bounds nearly match the AMIP upper bound for the ineligible studies, but left room for improvement on the eligible regressions.
To find the root of this gap, we first noted that the main component of our bound that failed was that after removing s 50 samples, our bound max {A(2s') )} becomes very large. Using Algorithm 8, we were able to find the samples responsible for these loose bounds: s 50 households (out of 10000) that account for more than 80% of the variance in the amount of land owned by each household.
When one of the columns of a linear regression is heavy-tailed, it is not uncommon replace this column with its logarithm. This presented slight challenge in this case, as many of the household in the eligible studies owned no land all. To overcome this, we replace the hectacres (amount of land owned) column with log (hectacres + median hectacres). We then reran the regression and robustness analysis to see the effects of this change produce the results in Table and Figure 2.
C.4
THE OREGON HEALTH INSURANCE EXPERIMENT: EVIDENCE FROM THE FIRST YEAR
C.4.1 PAPER OVERVIEW
The Oregon Health Insurance Experiment provides unique opportunity assess the effects of expanding access to public health insurance on low-income adults using a randomized controlled design. In 2008, Oregon implemented lottery to select uninsured low-income adults to apply for Medicaid. This random assignment allows researchers to compare the outcomes of the treatment group (those selected by the lottery) with the control group (those not selected).
Finkelstein et al. Finkelstein et al. (2012) analyze data from the first year after the lottery to evaluate the impacts health care utilization, financial strain, and health outcomes. The study finds that individuals in the treatment group were about 25 percentage points more likely to have health insurance compared the control group. The results show that the treatment group experienced higher health care utilization, including increased primary and preventive care visits, and hospitalizations. They also faced lower out-of oft-ket medical expenditures and medical debt, evidenced by fewer bills sent to collection agencies.
Moreover, the treatment group reported better physical and mental health than the control group. The authors suggest that the increase in health care utilization due to insurance coverage led to improved health outcomes and reduced financial strain. These findings provide significant evidence on the benefits of expanding Medicaid coverage to low-income populations.
C.4.2 REGRESSION ANALYSIS
The regression analysis conducted by Finkelstein et al. utilized instrumental variable (IV) regression to estimate the impact of Medicaid coverage on various health and financial outcomes. They used
25

---

Published as a conference paper at ICLR 2025
treatment variable the instrument and several dummy variable controls corresponding to different medical metrics (e.g.. "Not bad days physical").
IV regression is particularly useful in this context it helps address potential endogeneity issues, where the treatment (Medicaid enrollment) might correlated with unobserved factors affecting the outcomes. By using the lottery selection more accurate estimation of the causal effect.
instrument for Medicaid enrollment, they ensured
The IV regression be computed the ratio of two ordinary least squares (OLS) regressions: estimating the relationship between the instrument (lottery selection) and the endogenous variable (Medicaid enrollment), and the other estimating the relationship between the instrument and the outcome (health or financial metrics). This implies that if both OLS regressions are robust to sign changes, so their ratio. In this study, the correlation between the instrument and the endogenous variable was very strong and robust, making the primary robustness concern the OLS regression between the endogenous variable and the outcome.
Finkelstein et al. used weighted OLS regressions with several dummy variables, some of which had very sparse categories. This sparsity caused singularities after 13- removals, making difficult to certify robustness with the ACRE algorithm. Therefore, the OHARE algorithm was used to certify the robustness of these regressions.
Outcome
Type
ACRE
OHARE
AMIP
KZC21
Instrument vs Endogenous
752
10%
2 10%
Health genflip
Instrument vs Outcome
14
77
257
257
Instrument vs Endogenous
14
752
2 10%
2 10%
Health notpoor
Instrument Outcome
14
40
149
149
Instrument vs Endogenous
14
755
10%
2 10%
Health change flip
Instrument vs Outcome
184
184
Instrument Endogenous
13
685
10%
2 10%
Not bad days total
Instrument vs Outcome
13
72
Instrument vs Endogenous
13
669
10%
N 10%
Not bad days physical
Instrument vs Outcome
13
25
84
84
Instrument vs Endogenous
13
676
10%
2 10%
Not bad days mental
Instrument vs Outcome
13
31
118
118
Instrument vs Endogenous
14
742
10%
> 10%
Nodep Screen
Instrument Outcome
14
32
116
116
D SYNTHETIC DATA EXPERIMENTS
D.1 METHODOLOGY
We evaluate the performance of the ACRE algorithm on synthetic datasets drawn from two distinct distributions:
Normally Distributed Regressions As a baseline, we the algorithm normally distributed covariates. Specifically, the covariates are drawn i.i.d. from a standard normal distribution, ( 1).
Power-Law Distribution To stress-test the algorithm. we evaluate its performance on covariates drawn i.i.d. from heavy-tailed power-law (Pareto) distribution. In this setting, set the power b = 4 and draw covariates X,, i.i.d. from a distribution with density:
f(x) 1//21 (b++1.
This distribution has finite first, second, and third moments, but its fourth moment diverges, making a challenging test case.
Target Variable In both cases, the target variables (labels) Y; are drawn independently from standard normal distribution: Y, (O,
26

---

Published as a conference paper at ICLR 2025
D.2 RESULTS
D.2.1 COMPARISON OF KNOWN BOUNDS
We evaluate the performance of the ACRE algorithm on synthetic regression datasets drawn from the two distributions described earlier, with = 4000 samples and d' = 50 covariates. Specifically, we compare the upper bounds produced by ACRE, denoted U2. with the state-of-the-art upper bounds by Freund and Hopkins, well the lower bounds produced by AMIP and KZC (see Figure 3).
As shown the results, ACRE produces significantly tighter bounds than Freund and Hopkins across both normally distributed and power-law distributed covariates. Furthermore, ACRE's upper bounds closely approach the lower bounds from AMIP and KZC for values up to removal effects that push the regression outside the 2a confidence interval 1:20-
ACRE Synthetic Data
ACRE Synthetic Power-Law Data
10
ACREAT
ACRE
Hopkins
KZC21
10-1
AMIP
124
Axie)
ACREm
ACRE
39-
Hopinns
KZC21
K
(a) Normally distributed covariates.
(b) Power-law distributed covariates.
Figure 3: Comparison the upper bounds Uk produced by the ACRE algorithm with the state-of- the-art bounds from Freund and Hopkins and the lower bounds from AMIP and KZC. Each dataset consists of n = 4000 samples and d 50 covariates, with covariates drawn i.i.d. from either a normal distribution (Figure 3a) a power-law distribution (Figure 3b). For each figure, plot two versions of the ACRE algorithm: one that uses RTI as its MSN bounding component in the backend, and another that uses spectral algorithm. On these synthetic datasets, the spectral bound slightly outperforms the RTI backend, but has longer runtime.
D.2.2 SCALING OF kirrehold WITH
In this experiment, we aim to analyze how kinneshold (the maximal value of k for which the bounds of ACRE are close to tight) scales with the number of samples n.
We fix the dimension d = 20 and draw Amax 5000 samples with covariates drawn i.i.d. from either normal or paw distribution. The ACRE algorithm is then run on series of regressions, corresponding to subsets of this dataset, with the number of samples varying from 7d to mmax
For each regression, we compute the ACRE upper and lower bounds, Up and Lg, and use a heatmap
to visualize the ratio Us L, as function of l and the sample size Contour plots indicate the regions where Lt are close to tight.
Us falls below specific thresholds (e.g., 1.1), highlighting the values of k: for which our bounds
As shown in Figure 4, for both normally and pawer-law distributed covariates, kineshold appears to scale approximately linearly with n. This consistent with the scaling predicted by Theorem 1.2,
Asign is not appropriate metric for this experiment, as it is directly influenced by our choice of the ground truth model.
27

---

Published as a conference paper at ICLR 2025
which gives:
n n² vd
Fibreshold
52
min
~
d2
vd
Normally buted Samples
PowsisLaw Distributed Samples
Jogscaeel
Dogecale
(a) Normally distributed covariates.
(b) Power-law distributed covariates.
Figure 4: The ratio Us between the upper and lower bounds produced by ACRE for synthetic linear regressions with covariates drawn from either normal distribution (Figure 4a) or a power-law distribution (Figure 4b). Heatmaps show the tightness of the bounds as a function of and the number of samples n. Contour plots indicate regions where Lx below specific thresholds (e.g., 1.1), I. highlighting the scaling of kirrehoodd In both cases, kihresoodd scales roughly linearly with n, consistent with the theoretical prediction of Theorem 1.2.
D.2.3 SCALING OF kitreshold WITH
Finally, we examine how kihreshold (the maximal value of k for which the bounds of ACRE are close to tight) scales with the dimension the regression for fixed number of samples n.
In this experiment, we fix the number of samples to 4000 and sample regression with samples and dmax = 500 features, where the covariates are drawn i.i.d. from either normal or power-law distribution. We then vary d by limiting each regression to subsets of the features, varying the dimension from to d dmax-
Theoretically, expect kitresholdd to scale as:
Vd' de })
n n²
Ritneshold = min
which predicts two regimes:
For relatively small d, the first term dominates and we have kihreshold
Vd
2 For larger d, the second term dominates and have kihreshold
28

---

Published as a conference paper at ICLR 2025
Normally Samples
1.00
11
5 Nopecatel
Degescali
(a) Normally distributed covariates.
(b) Power-law distributed covariates.
Figure 5: The ratio between the upper and lower bounds produced by ACRE for synthetic linear regressions with covariates drawn from either normal distribution (Figure 5a) power-law distribution (Figure 5b). Contour plots illustrate the values kihreshold for some given thresholds, as a function of the dimension d. For relatively small (right side of the plot), fthreshold scales approximately as Va" Conversely, for larger d (left side of the plot), Athreshold decays faster, consistent
with the n² scaling predicted by our theoretical analysis.
E TIGHTNESS OF ACRE
In this section, we will prove that the ACRE algorithm produces tight bounds on "well-behaved" distributions, proving Theorem 1.2.
E.1 PRELIMINARIES
Throughout this section, we use Ō/0/Ωt to denote big-O statements that hold up to a factor of polylog(n). We will make no attempt to optimize the polylog(n) factors this analysis.
Moreover, say that 1 is negligible if 1) (1) is superpolynomial in n. Finally, say an event happens with very high probability if happens with probability - for negligible v,.
E.2
MAIN RESULT
Our main goal for this section will be to prove that ACRE produces good bounds with high probability when the regression data is drawn from a well behaved distribution:
Theorem E.1 (ACRE Bounds are Tight on Well-behaved Data). Let X Baxd Y E R be linear regression problem such that the covariates (i.e., the rows of X) are drawn from well-behaved distribution X; X and the oulcomes Y are drawn iid from Y N (X ~N Beg, In).
Then, for any axis gd-1, with very high probability, the upper and lower bounds produced by ACRE on this regression are close to tight
/ d kvd
Uk
=
Lb
n
for all k < kihreshold, where kithesholld
θ
[min
n²
In particular, if the samples X,, Y; are drawn iid from some normal distribution (0, X0) (for some covariance E' e g(d+1)x(d+)) D), or the covariates X, are drawn iid from the hypercube or unit sphere and the target variable Y, (Bg.. X,) +N(00 aR) drawn iid from normal distribution around some ground truth model, then Theorem E. holds for them. Therefore. Theorem 1.2 follows from Theorem E.
29

---

Published as a conference paper at ICLR 2025
Our goal for the rest of this section will be to prove Theorem E.1.
E.3 PROOF SKETCII
First, we note that if n = O(d), Theorem E.1 holds vacuously, as Ritresoold < 1. Therefore, we limit analysis the cases where Asbreshold for some Nohreshood x polylog(n) (the exact power of this polylogarithmic factor will depend on the specific constant C' in the exponential decay assumption in Definition 1.
To prove Theorem E.I, we first define a set of condition under which we can prove that ACRE will produce good bounds:
Definition 2 (ACRE-friendly). Let X,Y be the covariates and target variable of regression. Ler Σ = XTX denote the unnormalized empirical covariance of the covariates, and let R Y - XX-IX-xX
denote the residuals.
We say that this regression ACRE-friendly for direction e E Rdd with removals and parameters
PI, P2. Pa. P4 if
1. The covariates are bounded in Mahalanobis distance maxie[n] X7E 1 P1
2. The inner products of samples are bounded max]/je(m] X7E X, S P2 Yd.
3. The residuals are bounded maxie[m] R S P30 where OR = V EiEn))) R..
4. The inner products between the covariates and the axis of interest are bounded max (eTE- P4 Esein
(x) P P
5. Let a; -TE-IX,,, be the AMIP influence scores. We require that the over the largest influence scores is at least
Σ
=
max TE (
ai
2
O2
Ps
iET
where = = for for Z, = c
When PI...., Ps are most polylogarithmic in n, we say that the regression ACRE-friendly.
Our proof of Theorem E, will have two main components. The first and smaller portion of the proof will be to show that the bounds produced by ACRE are close to tight when a regression is ACRE-friendl) It should not be surprising that Definition 2 is sufficient condition for producing good bounds with ACRE, since ACRE essentially checks a slightly more robust version of these conditions.
Claim F.2 (ACRE bounds are nearly tight on ACRE-friendly regressions). Let X,Y, e be an ACRE- friendly regression with parameters Pl...., Ps for all k. S ki Then, there exists lithessoold
θ min { (.aa t2.=2koa /ooly (et/oolyP......... (Pa.....P)) such that for all ks S kitueshoola the bounds La,, Un produced by
ACRE satisfy
Un La
d d kvd x poly (PI...., Po)
11+0
The second and longer portion of our proof will be devoted showing that well-behaved distributions yield ACRE-friendly regressions with high probability.
Claim E.3 bWellebehaved distributions yield ACRE-friendly regressions with high probability). Let n. d be above, and let X, Y be in Theorem E.I.
Then, for any axis e gd-1, with very high probability, the regression X,Y Y is ACRE-friendly for all & ko, for ko = 5())).
Combined, Claims E.2 and E.3 yield Theorem E.I.
30

---

Published as a conference paper at ICLR 2025
E.4 SYMMETRIES
Before proceeding to the proofs of Claims E.2 and E.3, we note that our definitions of well-behaved distributions and of ACRE-friendly regressions are normalized in way that permits some symmetries. Indeed, it is easy to see that for any invertible matrix E RRdxd and positive scalars 0ie, Qy E IR+, regression X, Y,e is well-behaved / ACRE-friendly if and only if the regression X XL, Y a,, Y, = O₂ Le is well-behaved / ACRE-friendly. Moreover, such reparametrizations also has no effect on the robustness of the regression, we may apply this symmetry on the input and output of Theorem E. or Claims E.2 and E.3.
For Theorem E.1 or Claim E.3, may apply this symmetry with T. E-1/2, where E the ground truth covariance of the distribution X, resulting in distribution with covariance identity. Note that this renormalization not the same the renormalization process in the ACRE algorithm. In the ACRE algorithm, we renormalize by the empirical covariance, whereas the renormalization above by the ground-truth covariance. One of the steps of our analysis will be show that when the regression is drawn from a well-behaved distribution, the two are close to one another with high probability, but this not immediate.
For the proof of Claim E.2, we renormalize the samples according to their empirical covariance. This would result a set of samples such that 2 = X = Moreover, we use the ay symmetry to ensure that the residuals to have standard deviation oR = 1 and the de symmetry to ensure that has norm 1.
E.5 PROOF OF CLAIM E.2
After this renormalization step above, the conditions the normalized regression simplify to:
1. The covariates are bounded in & norm max || Pi
2. The inner products of samples are bounded max (X X3) < P2 v7
3. The residuals are bounded max R S P3.
4. The inner products between the covariates and the axis of interest are bounded max4e(1] (e, x,)² P4
5. Let a; (c, X R, be the AMIP influence scores. We require that the sum the k largest influence scores is at least
Σ ET
max TE(
P
VI
We prove Claim E.2, working with the normalized regression. Recall that ACRE produces its bounds by combining RTI bounds the following Gram matrices:
1. Gxex whose entries are the squared entries of the Gram matrix Gx of the original covari- ates. By assumptions the maximal norm and inner products of covariates, know that the diagonal entries of this matrix are bounded by o P? and its off-diagonal entries are bounded by d x P?
2. Gxr whose entries are inner products between covariates multiplied by the product of two residuals. Therefore, the diagonal entries of this matrix are bounded (in absolute value) by
d PPPP3 and its off-diagonal entries by a/d T P2Ps.
"
3. and Gxz whose entries are inner products between covariates, rescaled by the product their weights on the axis of interest e. Therefore, its diagonal entries are bounded (in vd P2
absolute value) by 7
d P P4 and its off-diagonal entries by 7?
Note that the output of the RTT algorithm is an upper bound on the resulting MSN problem. The output of the RTT algorithm squared is always equal to the sum of k diagonal entries of the Gram matrix plus fewer than &a off-diagonal entries. Therefore, we have:
RTI Bound & / 1: x Largest Diagonal Entry + 122 x Largest Off-Diagonal Entry
(19)
31

---

Published as a conference paper at ICLR 2025
The X & X Term Let Mxex denote the MSN- -Suud obtained by running the RTI algorithm the Gxex. Combining equation (19) with our knowledge of the diagonal and off-diagonal entries of G we clearly have:
k de n
Mxex S
V
Pf
+ k2 P
n²
n²
Therefore, for all k S Kihreshodd = min
VdP222 :2P4 ). Mxox is at most
Mxsx V / <1
The X and XZ Terms Similarly, let M and Mxz denote the MSN bounds obtained by the RTI algorithm on rr and Gxz respectively. As before, we combine equation (19) with our bounds on the diagonal and off off-diagonal terms of Gxn and Gxz to show that
d + k2 Vd
P-PPPP + 12 Vd
MxR S
P-PiP's
P2P S
Pals
and
Mx2 S k d P.P 12
Vd
d PoP S / n²
12 Vd ni?
PiPa +
/
P.Pa
n²
n²
Wrapping Up Therefore, for all k S kithreshold. we have
1 MxR by Mxsx
v2PpPa V2
kd 32/2
13/2
12 RVdd
(Md 123/2
kkd + 12 12
P1 +
P1P2
P2
xpoly (P1....
33/2
123/2
Finally, applying the 5th condition, we have
Uk ag bk
by
dd+kvd poly (Pi,...; Pb)
1 0
1
T4 0% bk
ak
n
completing the proof of Claim E.2.
E.6 PROOF OF CLAIM E.3
We move to the main portion of the proof which will be devoted to showing that when the covariates X; ~ X' are drawn from a well-behaved distribution and the target variable Y; ~ [(X] fg. 1) are drawn from a normal distribution around some ground truth linear model, the resulting regression is ACRE-friendly with very high probability (i.c., to prove Claim E.3). Recall that we showed in Section E.4, it suffices to prove this result for the case where the ground-truth covariance of the distribution X' is equal to identity.
Main Challenge and Proof Strategy The main challenge will be that the requirements of Defini- tion 2 (ACRE-friendly) require statements like o --w--w small, where v and w are related to the samples of the regression (e.g., v, might be two samples X,, Xyy) and from here on out, X denotes the unnormalized empirical covariance (recall that we normalized the ground truth covariance be the identity).
Because of our assumption that n > d x polylog(n), we can use matrix Bernstein to prove that the empirical covariance is close its expectation Σ nI, but even for moderate dimensions d, our bounds on the overall error of this approximation (i.e., || - n/ll) would not be strong enough to prove Claim H.3. For any fixed v, w E Rd that do not depend on the sample distributions, we can easily prove sufficiently strong concentration bounds o oTΣ w.. However, the v, pairs for which we will need to prove our concentration bounds do depend on the samples, creating the potential for alignment between the large eigenvectors of Σ n. and this pair.
Our proof strategy will be to expand Σ into terms that depend on v w and terms that do not. The terms that do not depend v, terms that do depend on v, w will be so small to begin with that we can bound them very loosely using the matrix Bernstein inequality (see Lemma R.4).
be tightly bounded using simple concentration bounds. and the
32

---

Published as a conference paper at ICLR 2025
E.6.1 MATRIX BERNSTEIN INEQUALITY
Throughout our analysis will often make use of the matrix Bernstein inequality:
Lemma E.4 (Matrix Bernstein Tropp et al. (2015)). Let Zi.... Zn be mudependenty-diisribbreee random symmetric d x d matrices with mean E [Zi] = 0. Moreover, assume that || S L and
Eiel E
[ - o², then
-t/2 02 + Lt/3
Pr
Σ |E(n]
Z
N
2d exp
In many cases however, our input will not directly fit the assumptions of this inequality and instead of a statement of the form || L, we will only have statement the form Pr |ill || 2 L] S 8 for some negligible probability 8. Therefore it will be useful for us to have an extension of this theorem to cases when the assumption fails, with very small probability:
disperrdenttydddiiiiutteeddd Lemma E.5 (Approximate Matrix Bernstein). Ler Zi...., Zn be independently- distributed random symmetric d x matrices with mean E [2,] = O. Moreover, assume that for all i, Pr [|| 2 L] S and E [ || < r2, and that
Σ
E [
< 0², then
Siclm
-1212 02 + Lt/3)
)
Pr
Σ Z
nTVō
$ 2d exp
nd
sE/n]
Proof of Lemma E.5. Let Std = {z E Rdxd Z
} denote the space of symmetric real valued
x d matrices.
Consider the random variable C = Zi x 1 2.1 At first it might seem like we can directly apply the matrix Bernstein inequality to these new variables, and then use the fact that Z, = Gi for all w.p. 2 nó.
The issue is that no longer know that these Ç maintain the other assumptions of the matrix Bernstein inequality. In particular, will bound | (sill and EEetn [c,"]] from above.
Let fa denote the probability density function of Z,, and consider
/ |
B [c] E [c.]
IE [Z.]
Zf((Z)
Let U, w E Sd-1 be any two points on the unit sphere. Using the CS inequality, we have
aE [6/ = / 1 (TZwf((Z) = - (uNisuTZZf((Z) s V / 1121)11((2)
(uTZw)² f((Z)
BES
The first term in the RHS is bounded by
V (1z))
|| L Vi
For the latter term, we use the CS inequality again:
Vr zesa (vT (w)) (())) s / / |Z |1 f((Z) -V Vr ut uTZZuf((2) = -TE ST
Therefore
|E [G:] T
33

---

Published as a conference paper at ICLR 2025
Finally, we bound the change in the variance of these variables.
Cov (C:) = E [c3]
E [ci] 3 E [<:] 3 [2
Cov
(C:)
S
Σ xE(M]
E
[
0
(E(M)
Therefore, we may apply the matrix Bernstein inequality (Lemma E.4) on the matrices to obtaín the bound
= -
-8/2
Pr
Σ RE(n]
C
2
<
Pr
Σ kc(m)
C
Σ
26
S 2d exp
o L1/3)
yielding the main claim.
E.6.2 A USEFUL COROLLARY OF LEMMA E.5
Recall that defined "well-behaved distribution" to be distribution whose tails decay rapidly when projected on any direction. will be beneficial to our use-case to work with a more relaxed condition the decay of these tails, by allowing additional poly(n) factor. Note that any well-behaved distribution is clearly also almost well-behaved.
Definition 3. We say that a mean-zero distribution X on IR is almost well-behaved with respect to the scaling parameter n, if has exponentially decaying tails in the sense that
3C> Vo E 1
11, >t s poly(n) exp (-22 (t0)) X~x
Pr
where
== E [XX]] = (ovariance( X~X
In the previous section, we proved generalisation of the matrix Bernstein inequality that can deal with a small probability that the norm bound assumption of the Bernstein inequality is violated. corollary of this result that almost well-behaved distributions are closed to summation over polynomially many iid samples. More concretely:
Lemma E.6. Let X be distribution that is almost well-behaved with respect to the scaling parameter n. Let k = poly(n) and let .1....,yy ~ X be iid random variables in IRd,, drawn from X.
Then, the distribution of their empirical mean (i.e., of the variable X 1/ Eie(n) X,) is also almost well-behaved.
Proof of Lemma E.6. Let & denote the distribution of X.
First, note that from linearity of expectation
[x 1 Σ EiEN E[X,] 0, so X' is indeed
mean zero distribution. Let Σ = Ex-x [XXT]. Again, using linearity of expectation, we have
Σ
E XXT X~8
k
VE
Finally, need to show that the tails of d are bounded. Let v E gd-1 be any vector the unit sphere. From our assumption that X' is well-behaved, for any > 0, we have
K Uu 1//x) 2 s poly(n) x exp (-2((t))
Pr X
Now, consider
2= 1-.2-112))
Vk Σ se(k]
(
1
34

---

Published as a conference paper at ICLR 2025
We would like to bound the probability that [Z] is greater than some threshold T.
Let Z (v. _-) These are iid random variables and our goal is to prove a concentration bound on their sum, so we may try to use Bernstein-type inequalities to do so.
Since E [ = and E [X, = Σ, we have that E' [ and E [Z,]² 1. Moreover, from the assumption that X' is well behaved, we have concentration bounds on these individual variables. Indeed, for any i, we have that
8e del Pr| 2
poly(n) exp (-1(t()
Therefore, from the = dimensional case of the approximate matrix Bernstein inequality (Lemma E.5), we have that
1
Pr (0 E 1/2 /22) ZT+ S eex
+ x poly(n) exp (-S2 (t)) + {(TVK)
Setting t V 2. we consider two regimes. When t < fuhreshlld = θ (log(n))1C) the bound
Pr [= 2 r] S poly(n) exp (-I
holds vacuously, since the RHS is greater than and the LHS is a probability.
When Abresholdd we can ensure that ó, 11/k2 1/poly(n). Therefore in this case for T = f2, we have
Pr 1u, (2))) sPr s 2 + + k 5v sexp (-12 (+112) + +kxpol(()))ee (-2(-012))
completing our proof of Lemma E.6.
E.6.3 RENORMALIZATION
Our goal in this portion of the proof will be to show that the empirical covariance matrix = X not far from the expectation Egt Ex-xx [XTX] nl. In particular, we prove the following claim:
Claim E.7. Let XI...., X, with covariance identity. Let E = Lie(n] X,X] denote the unnormalized empirical covariance, and
be samples drawn iid from an almost well-behaved distribution X
set
Eng
del
E
[Σ] = nI. Then,
With very high probability. || Eyll Ō (Vnd + d) o(n).
Moreover, for all i, we have | [|x,|| X:XT
|| = 00 and with very high probability |Xx|||=
(d).
Proof of Claim E.7. We prove Claim E.7 using our adaptation of the matrix Bernstein inequality (see Lemma E.5). We will apply this inequality for the Z; X;X! La. allowing to obtain probabilistic bounds on
Σ --
Eg
Zi
To use the approximate matrix Bernstein, we begin by proving bound on the norm of max; | Note that
that holds with probability 1 superpoly(n)
1 < IXXXX + ||| = |x +1=
Σ
(e,, xe)²
+1
EEld
35

---

Published as a conference paper at ICLR 2025
Next, use the fact that X; is drawn from well-behaved distribution X' to prove strong tail bounds on the distribution of its norm. In particular for any primary axis e, (for j [d), we have (e) S polylog(n) with very high probability. Therefore, using the union bound over all j, also have that with very high probability
(e. S polylog (n)
max
se
jeld (d)
Therefore, with very high probability
12 =
(20)
Next, we consider the second moment of Zz.
E
! E
| X - 2x:X + = E | X
Fix some pair of primary axis е, and unit vector E gd-1 Recall that by our definition of X' being well-behaved distribution, we have an exponentially decaying concentration bound on the projection of our samples onto either of these axes
Pr [max (KXX, ex,, b) 2 e- X
Therefore, a similar exponential tail bound also holds on the square of the product of these projections
((x,,)) u))² 2 exp (-2 (80/))
Pr Xxx
In particular, we can conclude the far milder bound that the expectation of the squared product of these projections has bounded mean:
E x~x (1x,,)))11
Pr w)| = -.egn.,) Xax (xx,,))) J
J.s(a..)) exp (- (3((1144) = 0(1)
exp
(21)
Note that equation (21) is longer concentration bound that holds with high probability, but bound on the expectation of random variable, that holds for any such pair eg. In particular, we have
{ Xxxx
((xx, wi } -0
0(1)
max v.
Therefore, for any E gd-1
TE [|X, x v= x,) 1|x,
Σ (u, X,)² (c., x,)²
Σ sE
{u, X,) 2 (e,, X;) O(d)
SEIM
and since this holds for all v, it is also true when maximizing over the unit sphere
E |
x
{OT [Xx x 0o) (dd
max vEga-1
Therefore
Σ
E
z
E
[2]] O(nd)
(22)
#E|m]
iEin]
Combining equations (20) and (22) with Lemma E.5 yields Claim E.7
36

---

Published as a conference paper at ICLR 2025
E.6.4 MAXIMAL NORM
We now proceed to prove that each of the conditions required for regression to be well- behaved occurs with very high probability. The first (and easiest to prove) is the condition that [aXie[m] X X, is bounded.
Claim E.8. Let XI...., ~ X' be samples drawn iid from an almost well- bell-behaved distribution X with covariance identity. Let E = Die(n] X; X denote the unnormalized empirical covariance, and
set
Eng
der
= nJ.
Then, with very high probability
[XP5-1X Ō KE[n]
max
Proof of Claim E.8. Let denote the spectrum of matrix. In the proof of Claim E.7, we already showed that with very high probability ||> Egnl = o(n) = o (min (Eg)). When this holds, we also have
x
(1 (1 (
π2
Moreover, the second part of Claim E.7 states that with very high probability max4((1) ||,,|? (d). Combining these results, we have that with very high probability
(X]E-iXA S max (E- max
-
max
k
sE(m
E.6.5 BOUNDED INNER PRODUCTS
For the next step of our proof, we show that the second condition of ACRE-friendlines of the regression holds with very high probability. In particular, we will show that
Claim E.9. Let XI...., Xn X be samples drawn tid from almost well-behaved distribution X with covariance identity. Let = -iejn)) X;X1 denote the unnormalized empirical covariance, and set
Egg
E. E nI.
Then, with very high probability
max {1xTE- = Vd *
Proof of Claim E.9. Denote = Σ XXXX =
= -mj and = X,. Note that from Claim E.7, we
know that with very high probability o A | |A- δ ( o(1).
Therefore, in this regime we may apply the Sherman-Morrriso formula to show that
--1 A-1
Σー -A=
1 A
Note that neither A nor X,, depend on X,, so from our assumption that X' is well behaved, with very high probability
XTA-'X, = 0 = Ō Vd
37

---

Published as a conference paper at ICLR 2025
Similarly, for target expression, with very high probability,
X-1X,XT 1-1
| = X? A -+ X X3
=(1- 11-1--XA--XX |XTA-
X )
=
Vd
E.6.6 PROJECTION ON THE AXTS
For the next property of well-behaved regressions, will want show that with very high probability eT is bounded for all i. Note that from the exponential decay assumption due to X being well-behaved would suffice to give good bound on - but as before, the challenge will be to show that - doesn't 't rotate X; onto e.
Claim E.10. Let XI...., X,, X be samples drawn iid from almost well-behaved distribution X with covariance identity. Let Σ Lie(n) X;X; denote the unnormalized empirical covariance, and set Eg def
E nI. Lete Sd-1 be any fixed vector independent the X..
Then, with very high probability
eTX; I [n] e
1
n
11
In particular, with very high probability
KE -
max xE(m
x eTM-Te
Proof of Claim E. As in the proof of Claim E.9, let X; and = --rtT Moreover, because with very high probability 1 = o(1) < 1, we may apply the Aherman-Morriso formula
Σー (A + ---))-=-1-- A u
1 UT A
Therefore, with high very high probability,
ETA eTA-1X,X' XXXXXXXXXX
1 1+X7A-1 A
et xTA- --
- X₂ e (A-1- X,
1+ +
From Claim E.7, we know that with very high probability
d + Vnd
| Eg' 2n
| - Ene1 =
n
X IX ō
_
Therefore, using the fact that X; is well-behaved and independent of e and A, we have that with very high probability
X =Ö (2t+v/
Vnd
1
T X; - e ETEg X1 < _ (A-1 - Eg. x
1 1
n²
= 0
12
38

---

Published as a conference paper at ICLR 2025
E.6.7 BOUNDED RESIDUALS
For the next step of our analysis will show that the residuals bounded with very high probability. Recall that under the assumptions of Claim E.3, we assume that the labels are drawn from the distribution
Y = X3g - X + N (7.
Therefore, we clearly have that with very high probability maxie[n] Gil S log(n) = Õ(1) as required. The issue is that the residuals of the regression are not necessarily equal to Ç.
Recall that the residuals are equal to
R y = -X-XX-XXT
Claim E.11. With very high probability
Vi
R. 4i o(()
Proof of Claim E.1I. Fix some index i E [nc.
R; ( -
- G - =
Σ - -
(23)
j4t
Therefore, from Claim E.8, we have
d +
RR G|= EGXTE
+0
E 1X, +0(1)
This leaves us with the task of analyzing the term
XT=
Σ ESXX/
=I 2 jt
where 2,= XX,= To bound this term, we view the process of generating the samples as first generating the covariates X,, and then after fixing some values for the X₁. it generates the errors Gj. In other words, we will show that with very high probability over the X;
Pr
Σ
23 > jæi
d(1)
GoN((.1)
super-poly(n)
In particular, with very high probability over the covariates, we have
サi (x)=-X,,²² =
Σ
(x)=-"x))=-0
n
jE(m|M()
Therefore, fixing the covariates X,, and viewing Σ E/ Zg as a random variable dependent on the randomness of the errors Çj. we have
Σソッ~~ x(10, Σ (xTx->x,²² =N -N(00.0 (1.00())
J JE(n]((0
yielding the claim.
39

---

Published as a conference paper at ICLR 2025
E.6.8 LARGE INFLUENCE SCORES
For the final step of our proof of Claim E.3, we will show that with very high probability, there are many samples in the regression that have relatively high AMIP influence scores.
Claim E.12. Let a;; = = R,R; denote the AMIP influence score of the ith sample. Then with very high probability, there are is a set To S [n)] of least kn (2()) "influential samples" ie., such that vi E T ai Z 10n
Proving Claim E.12 will also conclude our proof of Claim E.3, as this will show that all conditions required for regression to be well-behaved are fulfilled with very high probability.
Proof of Claim 12 To prove Claim E. we first show that a very large number of samples must have relatively high inner product with the axis of interest. In other words, we will show that with very high probability
8 Kiler
X
=(())
(24)
2n
To prove equation (24), note that:
ETI == 1+ol1) (this follows immediately from Claim E.7).
Eie(n)
ex ?
Eie(n) -x
. In Claim E.10, we showed that wvhp Vi ( et
x
Therefore, must have least (2(n) samples with l X,
1
Let i be the index of such
sample. sign (eT (x,)
f.J then will also have a; 2 10m
In the proof of Claim 1. showed that wvhp RR G = o(1) for all (where = Y, X! Ber are the "ground truth residuals", and are drawn iid from a normal distribution). In particular, wvhp vi RR Gul < 1 f so as long as sign
G 1. we have a; 2 IDm
But Çi is drawn iid from normal distribution, so sign (x) 1 has constant probability and is independent of X,. Therefore, applying the Hoeffding- -hhirnoff bound, we can easily see that wvhp at least constant fraction of the 2(n) samples for which |eT 2
also have
0g I0n thus concluding our proof of Claims E. 12 and E.3.
F TIGHTNESS OF OHARE
In the previous section, proved Theorem E.1 which says that for "well-behaved" data, the ACRE algorithm outputs nearly tight bounds on the removal effects for a range of removal set sizes k. In this section, will extend those results the one-hot aware version of the algorithm - OHARE.
Theorem E. (OHARE Bounds Tight Wehl-behaved Data). Consider linear regression from a set of continuous features X E Raxd and a set of m dummy variables, representing a calegorical feature B, L. B,, [n), target variable Y. For any any fixed > O, there exists v E polylog(n) such that:
n. BBy denote the number of samples that take the value j in the categorical feature, and for all
j E [m], we have
nº +vvvv <n 0.49n,
that the dimension of the continuous features d is at most d S n//5/vv. and that the continuous features are then drawn iid from a well-behaved distribution X, ~ X independently of their value on the categorical feature.
40

---

Published as a conference paper at ICLR 2025
And if the outcomes Y drawn tid from normal distribution around a linear model of the features
Y1
(xx:Bet)
(0,)
categorical contribation
continuos contribution
emror
for some unknown ground truth linear model (M, (g)) Rm+d
Then, for any axis S with very high probability, the upper and lower bounds produced by OHARE on this regression are close to tight
U L
+0 polyloglog(n)
Vlog(n)
for all k < kihreshold, where
n² ① min
n m
})
lehreshold
da
Our goal for the rest of this section will to prove Theorem F.I.
MAIN CHALLENGES AND PROOF STRUCTURE
Recall from Section F that the key idea of the OHARE algorithm is to analyse process that is equivalent to the regression with a one-hot encoding. In this alternative formulation of one-hot controlled regression, first split samples into buckets B3 S [mi] corresponding each of the potential values of the categorical feature, reaverage the samples in each bucket
X; X;
E
[xy]
R
(6)
Y = Y
E ME
and perform regression with just the reaveraged continuous features. The OHARE algorithm then computes the same MSN bounds as the ACRE algorithm would, but on these reaveraged continous features and combines them with terms corresponding to the effect a removal might have on the reaveraging process.
Our proof of Theorem F.1 will follow similar path. We will first prove a claim very similar to Claim E.3 adapted to the OHARE case:
Claim F.2 (Well-behaved distributions yield well-behaved regressions with high probability after reaveraging). Let n, d, m, X, Y be in Theorem F.l.
Then, for any axis gd-1, with very high probability, the regression X, y is ACRE-friendly for all k ko, for Ko 1=))
Note that Claim F.2 does not follow immediately from the corresponding Claim E.3 for ACRE, since the continuous features X are no longer drawn iid from well-behaved distribution as the reaveraging step could have changed them and similarly the reaveraged labels Y are drawn iid from normal distribution around a linear combination of the continous features. The proof of Claim F22 will follow very similar path to the proof of Claim E.3, but will also have to account for these additional corrections.
Finally, we will prove that the additional corrections taken into account by OHARE will change the upper and lower bounds too much, yielding Theorem F.I.
F.2 PROOF OF CLAIM F.2
We begin by adapting the analysis from the continuous features (Claim E.3) to the reaveraged samples. Throughout this section, let X E gaxd denote just the continuous covariates and X Bexd denote the reaveraged continuous covariates.
41

---

Published as a conference paper at ICLR 2025
As in the proof of Claim E.3, normalize samples so that the ground truth covariance of the continuous features is equal to the identity, and denote by Σ = X E Rdxd the unnormalized empirical covariance of X and by Σ = x E Rgdd denote the unnormalized empirical covariance of the reaveraged samples covariates.
F.2.1 REAVERAGING
The first step of our analysis will be to show that with very high probability the reaveraging step makes only a small change to the covariates as well as the target variable. Let j E [ml] be the index of any bucket of samples and let
& y1 denote the averaging effect for this bucket.
Σ X;
[ iEB,
n sEB,
Σ iEB
Y E
[X] sEB
Claim F.3. The mean and covariance &j are
E [Eyy] = 0
E [S nJ
Moreover, with very high probability
||=ll| S δ (V /d/ns = o(Vd)
1ys 14 - (5)) (1(/ o(1)
Finally, the fourth moments of are also bounded
0 d
G5
n3
Proof of Claim F.3. First, recall that our covariate distribution X' was normalized have mean 0 and covariance identity, yiclding the first part of Claim F.3 immediately from the fact that & is the empirical average of n; iid samples drawn from X.
Recall that we assumed the target variable was drawn from a normal distribution
Y1 M3 + (X,, Bg)) + 10,
In particular,
E Y. 14g
E KX,, (g)]
iEB,
iEB;
is the empirical average over ny samples of this normal distribution, yielding the claim that with very high probability
yj - #1 (5, Bgx) S 5 (1/ o
The rest of Claim F.3 will follow from a combination of Claim E.7 (which bounds the norms and higher moments of well-behaved distributions), and Lemma E.6 (which states that the sum iid samples from well-behaver distribution is also well-behaved).
Indeed & is the empirical average over n, (n)y(n) samples from well-behaved distribution X, so Lemma E.6 ensures that for all j. the variable / / is well behaved, and, as noted above, it has covariance identity. Therefore, follows from Claim E.7 that
E |&
655
<
42

---

Published as a conference paper at ICLR 2025
and that with very high probability
|k&/ll - Ō ((aim))
F.2.2 RENORMALIZATION
Let = > [|[n] X be the unnormalized empirical covariance of the continuous features, and let Eg nl | lines as the proof of Claim E.3 by adapting Claim E.7 to the reaveraged setting:
be the ground truth mean these features. We continue along the same
Claim F4. With very high probability,
| |||
Ô (d m).
In particular, due to Claim E.7 and the triangle inequality
Σ E
Σ + || Egil = (Vnd + d d+ mm) =0 =Ō(vnd+ m) d(n)
Proof of Claim F.4. We have
Σ Σ X Σ
(xi - (50) (xi - -sto) Σ x
Σ
S005J0 = Øー Σ ngE;5]
kE|n]
E||m]
ic(m
ic(m]
5E(ml
Therefore, only remains to bound
(00)
Σ
n
JE[m]
We do this using our approximate matrix Bernstein inequality Lemma E.5. Let Z, = n In Claim E3, we showed that E [Z,] that [z}]
n3 |kyl1 [ has bounded norm
E n ||& [ (d))
(d)
and that with very high probability
|2 = n1
Therefore, from Lemma E.5, with very high probability
Σ [E(m]
7
<
Σ @E[m]
Z
E [
m = -
Vmd Vid+ + m) (dd+v
Ō (d + m)
JE/ma]
Finally, recall that we assumed have at least n" samples in the smallest category. Therefore, m < n² 1-c & completing the proof.
F.2.3 MAXIMAL NORM
We proceed prove that each of the conditions required for the regression be well-behaved occurs with very high probability. The first (and easiest to prove) is the condition that maX4e(m) X Σ X; bounded.
Claim F.5. With very high probability
= 4
max VE
43

---

Published as a conference paper at ICLR 2025
Proof of Claim F.3. Let À denote the spectrum of matrix. In the proof of Claim F.4, we already showed that with very high probability | Eg o(n) = o (min A (En)) (where Egt = n.). When this holds, we also have
= =L 1
Moreover, in Claim E.7 we show that with very high probability max4e[n]
||,|| = -d).. Combined
with Claim F.3 and the triangle inequality, we can derive bound on X < ||xx|l + ||sol =
Vd with very high probability.
Therefore, with very high probability
max iefn
{ { I max {a (A(E-1)
max iE|n|
[|x
Ō
d
n
F.2.4 BOUNDED INNER PRODUCTS
For the next step of our proof, we show that the second condition of ACRE-friendinnss of the regression holds with very high probability. In particular, will show that
Claim F.6. For M E < the following inequalities hold with very high probability
(1 ME = (_v Va (1+
d dirgi
max 2u Em
x
n
vd
Vi E [n].j E [m]
|XTME) =Ō
l B,
n,/
Vd
{ { 1 (
M X δ
max
n
Claim E.9 proves the third inequality of Claim F.6 for the where M Σ-1 The following Lemma F.7 will prove the first inequality for this same case.
Lemma F7, Let ji # j2 E [m]] be the indices of two distinct buckets, and let E XTX
Eiely) X,XI denote the unnormalized empirical covariance of the unaveraged samples.
With very high probability
Vd
x (1+ d
|c] Mーーー -
=
x n
n
The proof of Lemma F.7 is very long and technical, and we devote Section F.3 to it. For now, let us continue with our proof of the rest of the inequalities Claim F.6 assuming Lemma F.7.
Proof of Claim F.6. We begin by bounding the inner product between the bucket averages through the covariance 5-1, Define
5 Σ 1
del
max
J1:32
x
d
Our first goal will be show that with very high probability 7) = Ō(1)
44

---

Published as a conference paper at ICLR 2025
Consider the following identity (where A and B are d x d matrices such that A and A B are invertible):
A (A - B) B.
Multiplying this equation by (A B) from the left and A- yields the following identity that we will use in our analysis.
(A B) -1 = A + (A B) BA-
B)
(25)
We apply equation (25) for A Σ, B = E 5= Eje(m) nyS5JJ giving us the identity
3-1=Eー1 Σ E- f
je/ml
Therefore, from the triangle incquality,
Vd
x 1 dvT.j MJj
S S
Σ jE|m]
ST 1 Emn
r My, R4
=
For all j * j1, j2, from Lemma F.7, with very high probability
dnj
Siz = Ō " yn 1852
1 (1+
n2
Therefore, with very high probability
Σ [ = Ō
md
d3
x x-=
(
n2
n Mn n2ja
where the last step utilized our assumptions that m
and that n² >> dt.
When j = j1, we have
d
Vd
(1+ dymi (1+)/m)) ))
-- &n E1e =
- Σ 111 =
En
x n
nij
Mi T0ja
=ō vd
(1+ d d
Mmj n222
Similarly, for j = j2. have
Vdn
1 d )
GEE=~Sn,ET2--1 Ex2
= -|,] Sy - - 1-1 Ō
x nzz x
X n2ja
7i 11ja
Vdn
1 d ditisi
( Jn Rij2
Therefore, with very high probability
1 + Eje(m)
1 E,2
531
Ō (1)+o(n)
17
Vi
d
va
(1+
Ma Righ
May "agn
Therefore, with very high probability 17 n= Ō1), proving the first portion of our claim.
Next, consider term of the form XTE-1Ex To bound this term, we open Σ-1 again using equation (25). Indeed, we have
X ' < 1
Σ XTX - Eyn
45

---

Published as a conference paper at ICLR 2025
Define
1 X,LIEB, n
EJ
X₁ i Bj
Si. = Eg
i & Bj
S..j over B, bucket had the X; sample been replaced with the 0 vector. Note that with very high probability
LeB; nj
[
xI- (E, - G.)5
Xil
| = ō
nmj
To proceed, we apply the Sherman-Morrison identity with X; and A = 111(((0 = E - VuT, to show that
-ーーーーー-_ A 1 uT ATA
A
Moreover, because both A and Su are independent of the ith sample and X' is well-behaved, with very high probability
vd
0 =
Combining this with the Sherman-Morrisee formula, have
I (1 (1--
XTA-1X;
vd (Tin
I-XXXAXXX -1-11-XAAX
|XTA Ge =
Therefore, for all j E [m], with very high probability
Vd Vn,n
+ LiB
-----=-=
ny
Therefore, with very high probability
En
3. s
F'Emm]
Vd
dlien, nny
Vil
drys
1z=ydd ( ))
Σ f'mmm]
x xn x
1+
n nzy
n
δ
d2 /ag
d Vn,n²
63/2 d3/21 LiEB,
(1+ 11
dung
d flIEB, 1s=8 n2n
n2
mi
n VT
n
3'E(m]
vd
lie
d
md n2
d3/2
dlieB,
vd
liB d nng
=
+
Mnjn
nyn
mn
n VTg
Vngnn
nin
where the last step utilizes our assumptions that m δ
and that df = =ō(n')
Finally, let i is be the indices of two samples. From Claim E.9, we have that with very high probability | -xxl = Ō //l Opening S-1 again using equation (25), we see that with very high probability
X 1 X
+ Σ
X
jE/m]
Vd
Vd
IUEB,d n,n
Vd vnyn
+ lIBEB,d) nyn
)
x xn/ xm))
n
Vnnn
jE[m]
Vd
md
d2
Vd
=
+ δ
+
n
n²
2
m'in
46

---

Published as a conference paper at ICLR 2025
where minn jim] {ng} 52 (vd).
def
F.2.5 PROJECTION ON THE & AXIS
For the next property of well- belavee regressions, we will want to show that with very high probability eTΣ- X; is bounded for all Note that from the exponential decay assumption due to X being well-behaved would suffice to give good bound on et Egg X; (where Egt = nT), but as before, the challenge will be to show that E-1 doesn't rotate X; onto Claim F.8. With very high probability
(5-Xx1e)
eTX; to
1 12
Vi E [n]
In particular, with very high probability
( ())
x -
max E
Our proof of Claim E.8, will make of the following Lemma F.9 that will also be proved in Section F.3. Lemma F99. For any j [m]) with very high probability,
(1+ dv ))= n
L E, - δ
nn/ng x
Proof of Claim F88. the proof of Claim F.6, we will use the matrix identity in equation (25) to show that
--1= E-1 +
where --E-E= E=E-E=Ejem Eje(m) m5{je]
Define
max jElm
Using Lemma F.9, we see that with very high probability
-6
(
)) =Ō(=1))
17 T E S - E,
ET
n
Opening Σ-1 again, we have
-
T T5 -
Σ
jE(m]
From Claim E.10, we know that with very high probability
eT
1
ET X
=
Therefore, from Claim F.6, with very high probability TT X; - - x,
< Σ
T
Enn
ET
jE[m]
1
Vd
d1 dl
))
Σ
ny x
+
n
ny
nn,
jE[m]
= =ō
(vdm
d
1
n?
n²
Temin
47

---

Published as a conference paper at ICLR 2025
Altogether, have that with very high probability
eTxi
- xx, etXi
- X;
S T
Ex(
+ -x
n
n
F.2.6 BOUNDED RESIDUALS
Recall that we assumed that the samples of our regression were drawn from a ground truth linear model plus an iid normally distributed error. Therefore, in order to bound the empirical residuals, it suffices to show that they are close to the ground truth residuals with very high probability.
In particular, in the setting of Theorem F.I, assumed that
Y
15(01
(g),
+N (0.1)
categorical contribution
continuous contribution
errer
Define the ground truth residuals to be
Rgt = (Y; Mj(1) - (X,, Bgi) [E(n]
and the empirical residuals to be
R R= X33 y XTV.
Claim F110. With very high prohability,
R - Rgil = =0())
Proof of Claim F.10. Denote
j4 def 1 Y= + + 1 Σ (Re);
n2
nj KEB
KEB
From the definitions of the residuals and the ground truth residuals, we have
R4 - (Rar), = (x; - m5()) - (x, ESt) B (Y; 1360 - xxT =
cT B0) - ni(()) PE
Σ (Rg) - X7 (B Ba) + +T(08 =
(Ra), XT (3 Bg)
no((1) VEBJO
Expanding on the difference between the results of the reaveraged OLS and the ground truth linear model, we have
8- 1== ミー1 x
(Ā - (xxx8))= -5-1 - (v. (Yi-15e 1500 (Y: 1500) - (Rg))) + S11) iEim)
---1
(Rg), - S1 n1(()) ren
Σ
(Rg) + &100 Bgr
iE(n]
ēT (Ra), 7g(6) (eB,t)
Σ (Ray
SEim]
Therefore,
R; (Ry); T1(()) veB
Σ
(Ra) - -X XT (Ry) (1((()) reB
Σ
(Bede
48

---

Published as a conference paper at ICLR 2025
Summing over the contributions of the second term, we have
XT--
(Ba)) ng((") ('Bs(i
(Rad)
- XTS
(x.-
- (Rai
1* E
re(mm]
N
E
(X (x.- -G(0)))))) - =N =N(0.0
(0.0(m²))))
d2 #22) )²))
n²
M7min
PEN
so with very high probability this contribution is bounded in absolute value by o(1).
Similarly.
1 L
Σ
(Raug N ( n3t0)
-M = ( (+)
R2t0 (EBJO)
so with very high probability this term is also o(1), concluding our proof of Claim F.10.
F.2.7 LARGE INFLUENCE SCORES
For the final step of our proof of Claim F.2, we will show that with very high probability, there are many samples in the regression that have relatively high AMIP influence scores.
Claim F.1. Let or ET R;R; denote the AMIP influence score of the ith sample. Then with very high probability, there are is a set To [n]] of least kn (2(n--E) "influential samples" iee, such that
Vlog(n) 72
1
VIET ai 2
Proving Claim F.11 will also conclude our proof of Claim F.2, as this will show that all conditions required for regression to be well-behaved are fulfilled with very high probability.
Proof of Claim F. The proof of Claim F.11 will follow the same approach as our proof of its ACRE counterpart - Claim 12. Indeed, we first note that from the definition E and Claim F.4, with very high probability,
- 1 o1)
( (M(M)
Σ
x,
TT
e
72
(E(n]
Moreover, from Claim F.8, with very high probability, the contribution each individual sample to this sum is at most (4) -facctinn of this total. Therefore, with very high probability
{ e
N 2n
= [m)
As in the proof of Claim E.12, we note that Claim F.10 guarantees that with very high probability Vi R, - (Rx), = o(1) 20 Moreover, because the ground truth residuals (Rzz); are normally def (ET X, x (Rg).-
distributed independently of anything else, it follows that so are =
sign
Therefore, with very high probability, at least (n' (r) of the samples such that l X 2n
have p; 2(v ([glo(()) (this is because probability of each of 6; being above this threshold is >> n- (n) iid p.).
set the constants in the Ω to be such that the " allowing us to apply Hoeffding on the
Therefore, for this set samples holds that
a; - X, = (1 o(1)) eT pi = =Ω Vlog(n)
49

---

Published as a conference paper at ICLR 2025
F.3 PROOF OF LEMMAS F.7 AND F.9
Recall the lemma we wish to prove:
Lemma F.12. Let XI...., Xn. X be nu iid samples of well-behaved distribution X' with covari- ance Laxds Let & = +L Eiely X; be the empirical average over the first k < 0.49m of these samples, and let R be any vector that is independent of these first h samples (but may depend on the other samples). Finally, denote by Σ del
EiE(n) X,X; the unnormalized empirical second moment of
these samples.
Then, with very high probability,
||||| kn
dv
=
x
1
Clearly, Lemma F.12 implies Lemma F.7 (set & = Ej and v = Es2) and Lemma F.9 (set & = E and e).
F.3.1 PROOF SKETCH
We will split the proof of Lemma F.7 into 3 main steps. To do this, let Eis X:XX Enn [M] be the contributions to the empirical covariance due to samples not amongst the first k, and let C' = Σ - S be the contributions from within the bucket. From a standard analysis, so long C' < S, we have
- -- - CS
-
and these components will correspond to the main components of our analysis. We will show that the incquality C' < S holds with very high probability, before proving the following claims the rest of this section:
Claim F.13. With very high probability
STS-'o==0
Claim F.14. Let E Rd be any vector that does not depend on the first k samples. Then, with very high probability,
|wl|| vk
dvk
Cul =
(1
Claim F.15. Let E Rd be any vector that does not depend on the first samples. Then, with very high probability,
||w||| Vk
dvk
lsT (S- --- Cwl =
n
The proofs of Claims F.13, F.14 and F.15 will grow progressively more complex and each claim will build on ideas from the previous one. Throughout the latter two, the key challenge will be to deal with cases where both the <
def kg term and the C or Σ multiplicand may depend on the same samples.
In these cases, we will proceed by applying sort of divide-and-conquer approach by splitting the bucket into two subsets. For instance. instead of analyzing CT directly, we will split the samples in the bucket into two subsets and track their contributions to both ( = Co + Çi and C = Co Ct. Cw ( +() C1)
STS + -
(26)
diagonal lerms
off diagonal terms
The "off-diagonal" subsets will be relatively simple bound they contain inner products of independent vectors in Rd (and this independence will give 1/Vd scaling their inner product),
50

---

Published as a conference paper at ICLR 2025
and the diagonal elements will be split again recursively. This will also leave with a large number of "single sample" diagonal elements of the form
X15-1x;XJw
These single-sample terms will no longer enjoy the same 1/vd scaling the other terms gain due to independence, but will instead gain a sort of 1/k scaling, because instead having k22 sample-timen sample contributions in
C=
Σ (.EM
XTAXxX3w.
we have only & terms in the sum
Σ EE|E
XTAXXX7
Finally, in Claim F.15, we will have types of diagonal vs off-diagonal splits. The first will be to track the cases where and C' may depend on the same samples and will very similar to our analysis of Claim F.14. The second and much more difficult of the two will be dealing with dependencies between Σ and Ç.
F.3.2 SETUP AND PROOF CLAIM F.13
Recall our assumption from Lemma F.7 that kt S 0.49n. Therefore n k 0.51n k + M(n).
Let S = ExenNN X,X! = [x))))) From Claim E.7, we have that with very high probability
||S (n k) I|l o(n).
Combined with Lemma E.6, which shows that is well-behaved, have that with high probability
1 ||5 = ( max {a (8 x |1l1] - oT (1/
1
||l|l
(V x
Our goal for the rest of the proof will be to show similar bound for E Let S and - be our "main" and "correction" terms. Applying Claim E.7 again, we have that with very high
probability C kl + o(n) (n k)l o(n) 3 S. so both and I S-1C are invertible. We have
Vー = (1+
s S-+S-1 s- ---0--==-----" ----
Therefore, it remains to bound -= (where -- in absolute value. To do this, we once again use the intuition that in some sense E, and first bound - u. We will then slowly break down the difference between CC--c and EJ, Σ 20-CCS--- into series of corrections and bound each of these corrections in absolute value.
F.3.3 PROOF OF CLAIM F.14
Before proving Claim F.14, we prove a lemma that will help us in our analysis. Lemma F.16. With very high probability
|[Cw]] = ((=++ Vkdd (m1l)
Proof of Lemma F.16. At first glance, it might seem like Lemma F.16 should follow immediately from Claim E.7, but this is only true when & 52 (d), and will want to apply Lemma F.16 even when k & d.
We prove Lemma F.16 using the approximate matrix Bernstein inequality (Lemma E.5). Indeed,
Cw
X,XT w
[k]
[E(
51

---

Published as a conference paper at ICLR 2025
can be written as the sum of iid vectors oy def X,XTw.
From the fact that the X,s are well behaved and independent of w, we have that with very high probability,
eall S v |wl
Moreover, from our assumption that X' has covariance identity, we have that
E [
= EE
X Tw = w.
Finally, from Claim E.7, have that
|Xxi|| x:x? w Ō Ō(d (d/lool)) || w
E
Therefore, applying the approximate matrix Bernstein inequality on the standard embedding matrix
0
[(d+1)x(d+1),
V
2/
yields the desired result.
We now return to the proof of of Claim F.14.
Proof of Claim F.14. Let Ç kg = Σiejk XT. Using this notation, we have
ETS Cw = 1 -T
(27)
will bound the RHS equation (27) by breaking the contributions to Ç and to C' into smaller and smaller subsets of the bucket [k:]
We will split the contributions from the first samples into "clusters" based on their index modulus some number, and the assumption above is just to ensure that the subsets of roughly equal size.
Indeed, for any string of bits a = (ao. a.) E {0, 1)", define the ath cluster of samples to be the set of indices from [k] whose bitwise representation ends with the string
C. def E [
mod 2 do + a,2 + 0,,'
e the empty string, then C. [kt], and for all a, we have
C. Coo Li Cal
Similarly, we may split the contributions of samples [k] to and Ç based on their cluster
C. def
X.XI
jEC.
(28)
Sa def
X;
SEC
Moreover, we have the property that C. = Coo + Ca1 and Sa = Sao + Sa1. Using this property, we may begin to split the RHS of equation (27) to smaller components
CTS-IC' (Su + (1) A (C G
Cow Cow G
Cow + -JS
(29)
diagonal terms
off disgonal terms
We split the terms in the RHS of equation (29) into "diagonal" terms which correspond to the contributions where the term and the term correspond to the same samples and "off-diagonal" terms where ( and C depend on disjoint sets of samples.
52

---

Published as a conference paper at ICLR 2025
To bound the contribution of the off-diagonal terms, note that for any bitstring (ao, ................................ az), it holds that Ça is well-behaved (as is the sum over [Cal iid samples from X) and has covariance [C = θ ( k (this is because |C₂l s ς Moreover, the other terms in the product do not depend on the samples in Cas so with very high probability
2r
1 Ô (Vk |S (s-'C(wll)
Moreover, applying Claim E.7, we have that with very high probability
|| - (n - k = o(n) = ||S =
and applying Lemma F.16, we have that with very high probability,
|| = (( vkd) |1wel)
Therefore, with very high probability
(v -'vvv'
+ vkd
- =
and similarly for the other off-diagonal term, with very high probability
Vk k vkd
KTS (TT Ō
||m||]
now remains to bound the diagonal terms. Consider - Cow. We can open up the next bit of the indices of the samples to obtain
SJ Core
(Coo + Co A (Coo + Ca1)
(30)
C30 S- + 4T S STOS- C] Coow
We split the RHS of equation (30) again into diagonal and off-diagonal terms. The off-diagonal terms can bounded again in exactly the same manner and the off diagonal can again be split by specifying another bit of the sample indices. Applying this logic recursively, have
Diagonal, CTS CCw
Cow CTS C ST + -
Diagonalo
Diagonal
Diagonal,
Diagonalo,
Diagonal
Diagonal 01 Diagonal Diagonal, Off Off- Off-Diagonal,,0 Off-Diagonal
Off Off-Diagonal + OfftDDiagnnagg.uu + Oft-Diagonal + Off-Diagonal
(k)]
Diagonal
Σ
Off- Off-Diagonal, 4 Off- Off-Diagonal,111 1,4
aE(0.,1²
(31)
From the same analysis as the one above, we see that for any bitstring a E 10,1)' and bit b E (0, 1}. it holds that with very high probability
C.
+
C. d
Ō 2 2 2-V kd ||m||
Off- Seff-Diaoona, [b.ath a/
C.
|
Union bounding over the O (2t) [n) off-diagonal combinations, we see that with very high probability they are all bounded. Summing over these off-diagonal terms gives us
t= [k)]
Σ
Off-Diagonal a/0,a|1 + Off-Diagonal, 4/1,00 S
aE 10
t= [k)
1: + Vkd ||m||
= - (
k: + /dd
2 2 -'
|w0||
n
53

---

Published as a conference paper at ICLR 2025
Now, consider a Diagonal, term X [ w. Because w is independent of the ith sample X,, with very high probability,
X w| = Ô (Iwwl))
and from Claim E.7, we have that with very high probability,
Therefore, from the triangle inequality, with very high probability
Diagonal,
Diagonal,|
=6
kd
||w/l]
n2
(E(A]
Altogether, have
||0
dvk
))
C = Ō
1 + x
V
concluding the proof Claim F.14.
F.3.4 PROOF OF CLAIM F.15
In the previous portion of the proof, we bounded 5 Cws, when w is independent of &. The rest of analysis will be devoted to bounding the effect that replacing S-1 with E-1 will not make this inner product much larger.
As in the previous portion of the proof, we Ç kç, and separate samples into clusters based on the least significant bits of the bitwise representations of their indices. In particular, for any bitstring a, let C.. Sa and C₂ be defined above, and define
S. = Σ - C. = Emi|Nc. = Σ XXX
<E(M]]C.
to be the unnormalized empirical covariance of the samples not in the C2 cluster.
As in the proof of Claim F.14, will separate the contributions ÇT (S-1 Σー Cw based on the cluster of the samples and label these contributions as diagonal or off-diagonal based on whether or not the same samples were used in { and C.
ST (I---- Cw (Co +1) -S-1 (Co G
GJ
----- Cow + (S---- - C,w
diagoaul terms
(32)
+ CJ (S - 1 Ciw S (S-1 E Cow
off-diagonal terms
In other words, we have the recursive formula that for all E 10,
Diagonal Term, Diagonal Term Diagonal Term
(33)
Off- Diagonal Termajo.aj1 + Off-Diagonal Term 11,
Applying equation (33) recursively, we have 1 ÇT 1---) Cw = Diagonal Term =
Diagonal Term, +
xe [k]
Tog(k)) Σ
OOff- Offf-Diagonal Term a|0.e/1 Off- Off-Doagonal Term T1.ma/1.aa0)
af (E(111
54

---

Published as a conference paper at ICLR 2025
In Claim F.17, we will bound the off off-diagonal terms. We will show that with very high probability.
Off--Diagonal Term = Ō v|Cal
(1cb1 + vicold) x | x [1 dvh
x
Vk δ 2 (1/|+111/22
1+ dvk
n2 x (ks + vkr)) x |wll x
Since in our case |a] = |b| = t, we may conclude that with very high probability
2- - Vk n² x (++ vkd x |wl||
dvk n
Offf-Diagonal Terma.bl Ō
x
Applying the triangle inequality, with very high probability the total contribution of all the off-diagonal terms is of order
[lg(())
Σ
Offf-Diagonal Term |1 + Off-Diagonal Term ferma)).alo)
at ao,0,
[og[
Σ
Offt Offf-Dagonal aer + Offf-Diagonal Terma]1,aj0
aE(0,1)*
ToR(k)]
VK n²
||/| x 1 dvk ))
Σ
2 2
x (k: v vkd
(E(0.
(og(k)
VK
+ dvk
n²
x
(k + kd
x ||0
x
=
n
1=0
Vi
dv
x
+ kkd] x || wil
x
1
n²
This leaves us with only the "single-sample" diagonal terms Diagonal Term, XT --------- w.
To analyse this term, simply note that from Claim E.7 and the CS inequality, with very high probability,
XT (S-1---1) x < ||x,|| (I|s~ 'I || Ō d
Moreover, from our assumption that X; X' is well-behaved and that w is independent of X,, we have that with very high probability
[ w| = Ō ([]wl))
Therefore, with very high probability
Diagonal Term. = =ō Ö ||0|| (1|w)
dvk n
K
RE
Bounding the Off-Diagonal Terms
Claim F.17, Consider the off-diagonal term
C (s-1 -- C.w,
where a + b are bitstrings representing disjoint clusters C. nC, = 0.
With very high probability.
C (S-1---1 C&w = [lCal x (Ica) + vicold) x ||w|| x 11 dvk
55

---

Published as a conference paper at ICLR 2025
Proof of Claim F.17. Our goal is to bound the following term in absolute value
5J -
1) Cow.
The difficulty in analysing this term is that both Sa and (5-1-2 -- may depend on the same samples. To circumvent this, we begin by splitting (S-1- - and small correction:
(s-1- -) into term that is easy to deal with
(5---- = -
+ -
where - X,XT.
The first component has the property that it does not depend on the samples in Ca, while Ça depends only on the samples in a. Therefore, because Ca well-behaved with covariance [Ca]A, with very high probability
CI -5 Cool = (V(icall|(ss -ssa SS')
We begin by bounding the norm of (5-1- Cow. First, we note that Lemma F.16, with very high probability
||Cww]| = 00(cc= + viGold) |
Let A = S. and B = Sa EiE(ANNc X,X!. - 1- To continue, we bound the norm of (S-1-Sa- We utilize the identity
(A (A-
= BA- - BA-1,
as well as Claim E.7 which states that with very high probability
(A - B) B)- 1||--1||=
and that |B||| Ō (k + d) to show that with very high probability
((x²² n
k d
||-- 5---s1111-0 =
Therefore, with very high probability
[TT (S-1- 1) Caull =
k+d VCal x n²
x (1ca) + vicold) x [Iwell)
VICal x (1cal + vicald) x ||li||
It remains to bound the contribution of the S,1 - --1-E-1 term, which brings with it the added difficulty that it may depend on the samples in C., To bound the effect of this term, we split the contributions to once more
Hard Term,,6
def CJ (S ---1) Caw=
(Sao + Sa1) (S- ---1----- Cbu
STo (S-- S C&w + Cd (S - STi Cbw+
(34)
Easy Terms
+ cT ( 1 Σ 1) Cow + St al E Cow=
Hard Terms
Easy Term 40,6 + Easy Terma1.6 Hard Term,o Hard Terma1.
We split the right hand side of equation (34) into "easy" terms which can be dealt with using the same logic above and hard terms which can again be split into smaller easy and hard terms. Applying equation (34) recursively, we have that:
56

---

Published as a conference paper at ICLR 2025
Hard Termo,6 = Easy a,,b + Easy Term + Hard Term. + Hard Terma1
Ca D+1
(35)
Hard T +
Σ
Easy aja,,,
xECa
d'E(0.1)' =E(0.1)
To bound the easy terms, we note that as in the analysis above, the samples included in their Ç are disjoint from the samples included in their other factors. Therefore, with very high probability
Easy Term a.s.ll
def <T (5 1 - C.wl = Ō (ViCael 11(5== - -S Cbacl
Recall that we showed above that with very high probability
[|Caw]| = (5(((1)) ((c6) vicald) x [|
From here, we set = Saz and = Caz = Saz Sa. and recall the identity
(A B) -1 A = 1 B (A B)
to obtain the equation
9-1 S=1 = ST=
From here, might be tempting to simply bound the norm of this product, but that would result in too loose of a bound. Instead, we perform the somewhat finer relaxation
( ( Cowll C C,wl "C, < | ||C.SS Coul|
S
The advantage this finer analysis is that we can now use Lemma F.16 again, but this time on the matrix C.z. Indeed, Sa depends only on the samples outside C, 2 Caz, C. depends only on the samples C. which is disjoint from Ca. and S and wo do not depend on the first & samples. Therefore, Cas independent of them all, so applying Lemma F.16, we have that with very high probability
(Ca.SSat C = = ((Caz + Casld *|Saa"Caull s Ō (Icaal + (Cazid
||
I1 ||
= Caaz + V/Caz ld x (1cal + Vicold) x ||w/l|
Altogether, have that with very high probability
Easy Term a, = ( Ca + Cald
x (ccsl + vicold) x [|ool|
n
Therefore, for a' of length t - 1, we have |aaprl so 2- "Cal so with very high probability
Easy Term b.. = VICotarl Calarl + / Calarll
(1cal v(cold) x ||wl|]|
n1
2-1/2 Ca + Viaa d (1cal + vICold) ||/!||
= = 2 22-V/Cal
Cal
n²
57

---

Published as a conference paper at ICLR 2025
Therefore, summing over all of the easy terms and applying the triangle inequality, we have that with very high probability
log(IC. D+1
Σ
Σ
Easy Term aja' ,,,
Σ
Easy Term ald',z.b
t=1
a' (',
1=1
('E =E(0,1)
(0,1)
Ca + vdCal x (Ical + vicold) x |1 [nell)
Vlcal
n²
= Ō VICa
x (1Ga) + v /Gllld) x l|w|l
It remains to bound the single-sample hard terms. That is, want bound
X ( - -- Crul
Using the same matrix identity in the previous terms, we have that
Thi E-- -x-xx (M/(
Therefore, with very high probability, we have
XT (2o)ie0) xー Couo
Σ 10/0 -2-1 Cru ||x|||
||x
1x (10 Crw -
S ||xx||||=>|||
| xT Core -
< || |X δ Siotte Cavol)
dd (1cs) + cold
= || | 10 |(owll) 1[owol== =
||20
n²
(36)
Therefore, from the triangle inequality, with very high probability
Hard Term,, -ō (1c,1 d (/G, +Cod)
Hard Term,
Σ
||/|||
REC.
iEC.
completing our proof of Claim F.17.
F.4 PROOF OF THEOREM F.1
Recall that the OHARE algorithm works by computing each of the MSN style bounds produced by the ACRE algorithm and then adds a correction term to each one, where these correction terms correspond to the indirect removal effects due to the change in the reaveraging step.
In the previous subsection, we proved Claim F.2 which shows that with very high probability the regressions
ACRE components of the OHARE algorithm will produce good bounds on with categorical features. In order to conclude Theorem F.I, we would also need to bound the higher order corrections that OHARE takes into account.
Finally, note that for the case of an unweighted one-hot encoding, we have uzy = Lien, (i.c., the columns corresponding the dummy variables are indicators of their respective buckets).
58

---

Published as a conference paper at ICLR 2025
F.4.1 INDIRECT CONTRIBUTIONS TO THE FIRST ORDER TERM
Analysing the indirect contributions the first order term in OHARE will require significantly more care than our analysis of the higher order terms. This is because the first order term is the dominant one begin with and the indirect contributions it are smaller than the main effect by only / (nog(n) factor, foreing to track polylog(n) (n) factors much more carefully.
Recall from Section A.2, that the OHARE algorithm bounds the first order effect of removals on the regression result from above/below by
bound (Kg) = -d(ks) + (k,)
11 kj
where d, represents AMIP gradients on the reaveraged samples X₁:
d, (k₃) = max Σ CB ITyl=k ET
and (kz) represents the effect that reaveraging after the removals can have on the AMIP gradients of the retained samples:
of (ky) max
max TJCB [2
Σ
Rí
max Σ E T,C 12y RET
min T,BB 12 VEli
Σ Ri
min TJCB |Ty|=kk EET
Σ ET
1ET,
(kg) = max
min TJC bل
Σ
R4
max TJB |2
Σ ET
max TJB 125|=k,
Σ Rs
min Σ T,c k
TT
iE
iET;
For k; = ny, there is no reaveraging effect and bound f (n,) = (ny)).
Our goal will to show that d, (ki)), which is the contribution of the AMIP gradients to this first order effect, is the dominant effect. In particular, the main claim will prove in this subsection is
Claim F.18. Let hitreshold = 52 (n²-=) be as promised by Claim F.1..
Then, with very high probability
(
Viog(m)) )) AMIP(())
Yk <
kibreshold;
max 4.+
bound (kz))
1+0
jc(m)
where
AMIP(K) = max TE(
Σ Qi EET
is the sum over the k largest AMIP influence scores
-
Proof of Claim F.18. We expect (k,) to grow roughly linearly with ky, which motivates us to focus on the expression
Scaled Indirect Effect = 11 (kt, der max {1ct (ke) 10, (ks)
ky(ng - kj)
We will bound these ny in the following lemma:
Claim E11. There exists some v = polylog(n) such that for all k; S ng with very high probability
n, (k)) = O
59

---

Published as a conference paper at ICLR 2025
Moreover, for any v/ polylog(n) there exists some threshold polyloglog(n), such that with very high probability,
Ki B₁ [2 7} n Ki B, - r
1
n V
In particular, for all kj 2 ni with very high probability
(oolyloloo(n))
max T, TT)(
Σ ai
x kj)
iET;
ny (kgg = polyloglog(n)
n
where a; -
17 R,Ra are the AMIP influence scores.
The first part of Claim F.19 promises that the fl components to the bound are very small any bucket for which there are not too many removals k; polylog(m]] while the second portion of the
claim will help us bound the total contribution of buckets from which more than (olylog(n) removed.
ny have been
Let T argmax (e(()) (Eier as} denote the set of h samples with largest AMIP influences, and let n2 = [B n TT denote the distribution of these samples across the buckets. By definition, we have
Σ ag AMIP(k) ET
From Claim F.11, we know that with very high probability all the samples in T must have influence
at least minger {a:} = Vlog(n)
But from the second part of Claim F.19, we know that with
very high probability, for all j. the jth bucket cannot have more than 2y such samples, so with very high probability K2 %
Consider our maximization problem
MaxScore
max Km
bound
+ (kz)
A
jE[m]
This maximization is lower bounded by every valid assignment to k....., km so in particular is lower bounded by the score of Ki..... Kin- Utilising the first part of Claim F.19 to bound ny (Kz)), we have
MAR bound (kz)
bound (kzz = Σ 04 Σ 1ET
(g)g(K)) E AMIP O
[m(m
jE(m)
jElm
Now, consider any other assignment ki,..., p.....,km Am- If we still have ky < By for all j. then
Eje(m) bound (k;) will still be bounded by AMIP(k) + O (*) following the same logic as above.
Otherwise, let ji....,je denote the set of buckets for whick ky. Rii and define ky def k Kj. - kjz- From the same analysis as above, we have
Σ {bound (kg:)} + +0 k' (E(
bound (kz) S AMIP(K') +
eE mT)
60

---

Published as a conference paper at ICLR 2025
Next, note that we know that with very high probability
(Vog(n) (k k')
AM) 2 AMIP(K)
π
because Claim F.11 tells us that with very high probability, there are at least kihreshold 2 samples, each of which has sufficiently large contribution to the AMIP score.
Therefore, using the last part of Claim F.19, which bounds with very high probability every term in the bounds of buckets with more than " removals, we have
K'
bound (k₂) < (KIP(K) + Σ
bound (kj,)+ +0
-
S
JE[m]
polyloglog(n) n) x (k: k')
VVog(n) - k)) (K-))
k' (m)
(k) +
+0 m
S
n
20
k
AMIP(K) + +0
Altogether, we have bounded our maximization target from above and from below by AMIP(k) -
+ = 1 Ving(n))
AMIP(k), completing our proof.
Proof of Claim F.19. If kiz
m1 < njj then we use the bound
c (kt)
< n ky
k3
max ([R, 3Ejn
max ic|m| (e
kj vn
kj n
Next, note that due Claim F.10 (which states that with very high probability the empirical residuals R; is close to the ground truth residual (Rg),), we have that with very high probability for all i:
R4 - (Ra),) = o(1) < 1.
From our assumption that the ground truth residuals were normally distributed, we have that
Pr (o).))(().))
2v
Combining the two, along with the Hoeffding bound which promises that with very high probability
Hi E B, |R > r - 1-1 Sinnnn nJ ((n))~~((0.)
Pr
[[( > - 1] + (V(r))
we have that with very high probability
> + < iE By [Z m2 3/
Kii E B₁
R&
We bound {i By | X in much the same manner, by utilizing Claim F88 which - - eXX = (+), and our assumption that the X; very well behaved, which shows that there can't 't be too many samples in given bucket for which leT X2| > polyloglognn).
states that with very high probability
61

---

Published as a conference paper at ICLR 2025
F.4.2 INDIRECT CONTRIBUTIONS TO THE HIGHER ORDER TERMS
Indirect Contributions to the Covariance Shift Term Recall from Section A.3 that we bound the covariance shift as
E
} 1 - max {a ( maXXA +... +.... Ri mi
max
EEee( m--k, EieTnR E-1/2X:1 }
Each component in the denominator is bounded separately by running an MSN-bounding algorithm. The first MSN is run the Gram matrix Gxex whose i,j entry is:
( (X!E-1X,) 2
From Claim F.2, the regression X, Y is well-behaved, allowing us to use the same analysis as in Claim E.2 bound the output of this MSN by
d2 (
d n
Mx =
k2
Similarly, we define Mj to be the MSN bound achieved by RTI on the Gram matrix
G,lin, = X
Claims F.5 and F.6 promise that with very high probability the largest diagonal entry of this Gram matrix is most Ô (=) and its largest off off-diagonal entry is at most Ô vd MSN bounds are at most
Therefore, the resulting
"
(v
( k3Va
Ryd hyd++
My(k)) Ō
Recall that for our actual OHARE bound, we also utilize the symmetry that allows us to replace (ky) with M (ky) min (M,( M, k2)}.
For all ky < Ba T
we have
(k,))
M2(kg) (n, -k,
+ k,
Vd n
δ
(ng k2
n(n kz)
and for all kj 2, we have
M (k:))
Mn(n, k2,)
Vd
Ō
(n, k;j
(n.j - ki
n
Therefore, for all k Kitreshold
M, Mk,k,)² k;
v dk
(Mxxx -1))
Thj
/E[m]
Therefore, in this regime the covariance shift term does not contribute a factor of more than 3.
Indirect Contributions to the X Term Recall from Section A.3 that the residual contributions to the indirect XR term are bounded by
del min
max T)E(?,)
Ra
max Ty ((?)
Σ
Rd
NET,
(EBAAT
62

---

Published as a conference paper at ICLR 2025
where R, are the empirical residuals.
With an analysis similar to the one above, we can utilize Claim F.10 which states that with very high probability max { = Ô (1) to show that with very high probability
Pg(kg) Ō
v (ng k2)
Combining this with our bound on
kg))) we have
M, (kg)
M,(kg)ps(kk)
=ō
Vd n
max
k
7 - kj
JE(mJ
Note that this also smaller than the bound we proved for the direct contribution to the XR term in Section E.5,
kd
MXR=
and which we can apply after reaveraging due to Claim F.2 which states that X, Y is an ACRE-friendly with very high probability.
Indirect Contributions to the XZ Term Finally, recall from Section A.3 that the Z component of the indirect effect the X Z term was bounded by
(k( min
max T)E(2)
Σ |2,1 IETS
max (3)
|Z,l |]
iEB
where Z; = E
Using the same analysis above and Claim E.8 which states that with very high probability [Z, δ (+) for all [n]. we have that with very high probability
(11)))
1
δ
(ky k,)
71
Combining this with our bound on (ky);), we have
M, M,(kg)g nj nj-kj kj
Vd n²
k
JELMI
As before, this is smaller than bound on the direct effect
oV kd
Mxz - =
1.2 /d
n
n²
Putting it all together In Claim F.18 and over the last few paragraphs, we have bounded all the individual terms that go into generating the OHARE bounds. In particular, we have shown that
Direct XR + Indirect XR| |Direct XZ + Indirect XZ
Uk. LA
=
First Order
1 - Direct CS Indirect CS
1+
XAMIP(A)
Vingin)
kd
1.2 V2
1 +
X AMIP(K) +
(og((n)
n3/2
33/22
1 +
X AMIP(K),
log(n)
for all & < kitreshold, concluding proof of Theorem F.1.
63

---

Published as a conference paper at ICLR 2025
G ONE-HOT ENCODINGS ARE ALMOST BRITTLE
In this section, we will prove our claim from the introduction that datasets with one-hot encodings arbitrarily close being extremely brittle. In particular, we will show that
Claim G.1. Let X Ruxd be array of features and let Y E R be some labels, such that one of the features is on all but kaucket < n - of the samples. In other words, for some set S C [n]] of
size [S]
Bbucket, have
ViES X
Then, for all y E Rd-1 and for all c > 0, there exists a linear regression X', , Y' such that || - X11 | Yl < e, and OLS (X's: (a)
The reason regressions become so close to brittle is that with one of the features being always 0, we can make very small change to its value, in way that creates very strong correlations.
Proof of Claim G.I. The proof of Claim G.I is relatively simple.
First, we want to ensure that the original regression problem has no other degeneracies. We do this to ensure that the resulting OLS has unique solution.
Let V C Rn-Aaaa the linear space spanned by the columns of Xs.ja-11 and Ys. V is spanned by d vectors. Therefore, dim V < d.
dim V d, we can skip this step, and if this inequality is strict we say that Xs, Ys are degenerate. If dim V < d, is easy to see that almost all X Sss-a-ij Y's in Be/2 (Xs.ja-1). Ys) (i.e. in the ball of radius c/2 around the original regression) are non-degenerate. Therefore, let X s. Y's be such non-degenerate pair.
Now, consider the vector R = Y X 15 This is the residual vector for the linear model Y'S RJ X | and by our assumption that X s.jo-1) Y3 are non-degenerate, R + 0 and is not in the span of the columns of X's_j--1'
is only left to decide the values of X's.a Setting X's the samples in S
e R, our regression has a perfect fit on 2|
Y' = X's
By our construction, Σ = =X')) X's is full rank, making this OLS solution unique.
64


Reviews:
[{"review_id": "s1OBCBpvcw", "reviewer": "Reviewer_CjMq", "summary": "This paper studies data-based robustness for linear regression. Given an OLS solution that predicts $Y$ from $X$ (based on dataset $(X_1, Y_1), \\dots, (X_n, Y_n)$), target direction $e$, and $1 \\leq k \\leq n$, they estimate $\\Delta_k(e)$, the maximum possible change along the direction $e$ in $\\beta$, the solution to the OLS, that can be achieved by removing $k$ points from the dataset. In essence, $\\Delta_k(e)$ measures the robustness of a linear regression to potential training-time adversarial attacks.\n\nTheir main contribution is an algorithm, ACRE, which computes upper and lower bounds $U_k$ and $L_k$ for $\\Delta_k(e)$. ACRE operates by bounding the difference between $\\beta_S$, the value of $\\beta$ after restricting to a subset, $S$ of the data, and $\\beta$ by expressing it with two terms: first, a combination of the residuals of the original regression, and second, a higher order term, that factors in matrix terms based on the dataset $X$.\n\nNext, ACRE bounds each of these terms by reducing them to Maximum Subset Norm (MSN) problems. The MSN problem consists of computing a subset of vectors from a set of vectors with the largest possible $L_2$-norm of their sum. This problem, while still posing significant combinatorial difficulty, is subsequently solved by a Refined Triangle Inequality (RTI)-based method which essentially uses a greedy approach.\n\nTheir first theoretical result shows that the upper and lower bounds absolutely hold for any data-set. The quality of the solution, however, is based on the difference between $U_k$ and $L_k$. They then show that for exponentially tailed distributions, the ratio $\\frac{U_k}{L_k}$ is at most $1 + O \\left( \\frac{d + k \\sqrt{d}}{n} \\right)$. \n\nThis paper also includes an adaptation of their algorithm for regressions that involve categorical data called OHARE. For this algorithm, they show that for datasets satisfying certain technical properties, they can obtain a bound of $\\frac{U_k}{L_k}$ of at most $1 + O\\left(\\frac{1}{\\sqrt{\\log n}}\\right)$. They then experimentally validate this algorithm by demonstrating its effectiveness in the Nightlights study, where they obtain a provable lower bound on the minimum number of examples that need to be changed in order to reverse the main findings of the study. \n\nThey also include audits of 13 other linear regressions.", "questions": "Do you have a comment on how to expand your theoretical tightness results to broader types of assumptions on $X$ and $Y$. In particular, can you show a more general (but perhaps weaker) bound on $\\frac{U_k}{L_k}$.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper is well written and proposes a nice solution to a simple fundamental problem. Due to the challenging nature of this problem, their results still hinge on a reduction to an NP-complete problem. However, they are able to give performance bounds on their algorithm's tightness (both theoretically and experimentally), and crucially their algorithm improves over the naive approach (trying all subsets of size $k$) enough to provide meaningful audits of how robust the results from real-life linear regressions are.", "weaknesses": "There is, of course, a gap between the theoretical bounds on $\\frac{U_k}{L_k}$ and its behavior in practice (probably due to the nature of the assumptions needed to prove bounds on this quantity). Additionally, this algorithm is probably still not feasible for very large values of $k$. However, I do view this last weakness to be quite thoroughly addressed with the comprehensive empirical evaluation provided on real regressions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "EInAKrWU27", "reviewer": "Reviewer_SWFy", "summary": "The paper presents two algorithms, ACRE and OHARE, designed to audit the robustness of Ordinary Least Squares (OLS) regression models. This robustness is assessed by determining how removing a small subset of data points can alter the regression parameter vector. For detailed comments, please see strengths, weakness, questions section.", "questions": "1) Line 79: The authors talk about crossing a decision boundary. In terms of the regression problem addressed in the paper, a decision boundary is slightly inappropriate. It suits better for classification problem. \n2) Line 158: ACRE and OHARE are claimed to produce nearly matching upper and lower bounds. When do they (ACRE and OHARE) produce the same bounds, and when do they perform differently? \n3) Line 267: ACRE and OHARE are proposed for n>>d. What happens for the more interesting case when n is comparable to d or a high dimensional setting? \n4) Line 352: The norm is not specified in the equation. Is it Euclidean? \n5) Line 385: The authors assume the knowledge of the population covariance matrix.  What is the approach when it is unknown? \n6) Line 464: The authors use a greedy algorithm to obtain the bound. What is the computational complexity?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1) The paper addresses an interesting problem of auditing in linear regression. \n2) Rigorous theoretical analysis using interesting proof techniques like bounds via maximal subset sum norm (MSN) or knapsack-style dynamic programming.  \n3) The authors have tried experiments on real datasets.", "weaknesses": "1) Line 22: Instead of saying hundreds of dimensions, the authors should specify the exact value of d and n. Later in the paper, the authors have specified that they assume n>>d. Hence, saying hundreds of dimensions sounds slightly misleading. \n2) Line 135: The authors claim no assumptions whatsoever on X and Y. Aren’t you assuming well-behaved in Definition 1 and also iid? Also, see line 159 about assumptions. \n3) Line 253: Authors claim distributions with heavier tails than sub-exponential can still be well-behaved. \nWhile this is true, the authors should provide more information or intuition on which heavy-tailed distributions can specifically be well-behaved and which are not. For example, the counter-statement with some heavy-tailed distribution not being well-behaved can also be true.\n4) Line 295: The authors believe that the error term 1/\\sqrt(\\log(n)) is nearly tight. Is there a formal proof for the tightness of the bound?\n5) Line 322: The authors claim that loose bounds suffice. Why? Are the proposed bounds loose? Because the authors have also claimed the bounds to be nearly tight. This is slightly contradictory. What are the challenges in deriving tighter bounds? \n6) Line 374: The authors bound the first term using a greedy algorithm. What will the computational complexity be for that? Is this greedy step just for theoretical analysis? \n7) Line 390: The authors assume the max eigenvalue of a matrix which is a function of T (an unknown variable or variable of interest). This is slightly unconventional. \n8) Line 399: Can the computational complexity be improved from O(n^2 d) to something better? \n9) Line 440: Typo: direct -> direction \n10) Line 441: The assumption on $e$ should be specified in the main theorem. \n11) Line 497: The authors criticize existing works due to their reliance on semi-definite programming. Is the computational complexity of ACRE and OHARE better than existing works? \n\nAlthough the contributions are noteworthy, it is slightly challenging to follow the paper: \n1) It is tough to follow the story. The authors propose ACRE and then criticize it for proposing OHARE. \n2) Theorem 1.2 and 1.3 are presented even before describing the respective methods.  \n3) This makes it tough to develop an intuitive understanding of theorems. For example, please explain the implication of bucket size from Theorem 1.3. What role does it play? What happens if all the bucket sizes are different or if all of them are the same? \n4) It feels like the authors have tried to squeeze in a lot of information, breaking the story's flow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "dAFezpxJ92", "reviewer": "Reviewer_UrpZ", "summary": "The paper presents two algorithms, ACRE (Algorithm for Certifying Robustness Efficiently) and OHARE (One-Hot aware Algorithm for certifying Robustness Efficiently), for certifying the robustness of Ordinary Least Squares (OLS) regression to sample removal in the dataset with upper and lower bounds. The first algorithm is shown to work for continuous features and the second one with a mixture of categorical and one-hot encoded features.\nGiven a dataset with features $X_1,...,X_n \\in \\mathbb{R}^d$ and labels $Y_1,...,Y_n \\in \\mathbb{R}$, the algorithms provide bounds on how much the OLS coefficients can change when removing $k$ samples. The authors call the maximal discrepancy between the OLS with full dataset and the one where $k$ data points are removed $\\Delta_k(e)$ along the direction $e$.\n\nThe algorithms provide upper and lower bounds $U_k, L_k$ such that $L_k \\leq \\Delta_k(e) \\leq U_k$, where $\\Delta_k(e)$ represents the maximum possible change in the projection of $\\beta$ onto direction $e$ when removing $k$ samples. The bounds are proven to be (logarithmically) tight under mild distributional assumptions. One main characteristic of the algorithm is Minimal Subset-sum Norm bounding.\n\nThe authors provide some empirical analysis of the efficiency of these algorithms and an explanation of the correctness of ACRE.\nThe analysis is based on the decomposition of $\\beta - \\beta_S$ into linear order and higher-order terms where $\\beta_S$ is the OLS estimator after the removal of samples.", "questions": "* How sensitive are the bounds values $U_k$ and $L_k$ to the choice of MSN-bounding algorithm?\n* How do the algorithms perform when the assumptions about data distribution are violated? In lines 252-253, the authors mention that the result is valid also without the exponential decaying tail assumption. Have the authors tried the algorithm on PowerLaw synthetic data?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* The authors provide an implementation in their anonymous repository. The algorithm proposed by them is able to run on consumer grade machines for datasets of sizes of order $n = 10^{4}$.\n* The main text provides an excellent introduction to ACRE, explaining the idea behind its definition. The connection to MSN (Maximal Subset-sum Norm) is clearly explained.", "weaknesses": "* The clarity of the paper is a central issue. In Section 3, the intuition for the actual definition of the algorithm explains the setting and assumptions under which the result is obtained, and the authors believe the algorithm's work is not precise. \nThe connection between theoretical guarantees and practical performance needs to be better explained. for example Theorem1.2 and 1.3 could be tested in varying the numbers $n,d$ used for Table 1\n\n* The process of obtaining the values in Table 1 needs to be clearly explained, and the table needs to be clearer. For example, while the algorithms output bounds $(U_k, L_k)$ for each $k$, how these translate to the final numbers reported needs to be clarified. The comparison methodology with baseline methods needs more detail. Any form of cross-validation missing from the experimental results\n\n* Additional experiments can be conducted to strengthen the results.\nPerformance could be assessed under different types of data distributions using synthetic datasets with known ground truth.\nComparison could also be made with simple baselines (e.g., random sampling).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)