Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination
Authors: Ilias Diakonikolas
Giannis Iakovidis
Daniel Kane
Thanasis Pittas
Venue: ICML 2025 poster (2025)
Keywords: mean estimation
high-dimensional inference
robust statistics
contamination
computational efficiency
Primary area: theory->learning_theory
TL;DR: We present the first polynomial-time algorithm that achieves optimal error for high-dimensional mean estimation in the mean-shift contamination model.

Abstract: We study the algorithmic problem of robust mean estimation of an identity covariance Gaussian in the presence of mean-shift contamination. In this contamination model, we are given a set of points in $\mathbb{R}^d$ generated i.i.d. via the following process. For a parameter $\alpha<1/2$, the $i$-th sample $x_i$ is obtained as follows: with probability $1-\alpha$, $x_i$ is drawn from $\mathcal{N}(\mu, I)$, where $\mu \in \mathbb{R}^d$ is the target mean; and with probability $\alpha$, $x_i$ is drawn from $\mathcal{N}(z_i, I)$, where $z_i$ is unknown and potentially arbitrary. Prior work characterized the information-theoretic limits of this task. Specifically, it was shown that— in contrast to Huber contamination— in the presence of mean-shift contamination consistent estimation is possible. On the other hand, all known robust estimators in the mean-shift model have running times exponential in the dimension. Here we give the first computationally efficient algorithm for high-dimensional robust mean estimation with mean-shift contamination that can tolerate a constant fraction of outliers. In particular, our algorithm has near-optimal sample complexity, runs in sample-polynomial time, and approximates the target mean to any desired accuracy. Conceptually, our result contributes to a growing body of work that studies inference with respect to natural noise models lying in between fully adversarial and random settings.

Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination
Ilaas Diakonikolas' Giannis Iakovidis
Daniel Kane
Thanasis Pittas
Abstract
not accurately represent the underlying phenomenon. For example, ML security applications (Barreno et al., 2010; Biggio al., 2012: Steinhardt et al., 2017; Tran et al., 2018; Diakonikolas al., 2019), the data may be adversarially manipulated or contain out-of-distribution data which arise from unknown categories (Du et al., 2024); in biological applications, datasets often contain natural outliers (Rosen- berg et al., 2002; Paschou et al., 2010; Li et al., 2008) that may pollute downstream statistical analysis. The field of robust statisties originates from the early 1960s with the pioneering works of Tukey and Huber (Tukey, 1960; Huber, 1964). Early work in the field obtained minimax optimal robust estimators for the mean estimation and other tasks. However, the multivariate versions of these robust estima- tors incurred exponential runtime the dimension. A recent line of work in computer science, starting with Diakonikolas et al. (2016); Lai al. (2016), has led to a revival of robust statistics from algorithmic standpoint, by providing the first robust estimators in high dimensions with polynomial sample and time complexity.
We study the algorithmic problem of robust mean estimation of an identity covariance Gaussian in the presence of mean-shift contamination. In this contamination model, we are given set of points in Rd generated i.i.d. via the following process. For a parameter a < 1/2, the i-th sample z; is obtained as follows: with probability - a, 24 is drawn from N (N,, where μ E I is the target mean; and with probability a, 24 is drawn from (2 T), where 2, is unknown and potentially bitrary. Prior work characterized the information- theoretic limits of this task. Specifically, it was shown that- in contrast to Huber contamination in the presence of mean-shift contamination con- sistent estimation possible. On the other hand, known robust estimators the mean-shift model have running times exponential in the di- mension. Here we give the first computationally efficient algorithm for high-dimensional robust mean estimation with mean-shift contamination that can tolerate a constant fraction of outliers. In particular, our algorithm has near-optimal sample complexity, runs in sample-polynomen approximates the target mean to any desired ac- curacy. Conceptually, our result contributes to a growing body of work that studies inference with respect to natural noise models lying in between fully adversarial and random settings.
The prototypical robust statistics task is that of Gaussian mean estimation in Huber's 's contamination model (Huber, 1964). Letting a E (0, 1/2) be the contamination parameter, each sample Huber's model is drawn either from an inlier normal distribution ((,, 7) (where yı is the unknown target mean) with probability 1 a or from unknown and po- tentially arbitrary distribution E with probability a. Recent work has provided efficient algorithms with near-optimal guarantees in Huber's model (Diakonikolas et al., 201 8a; 2024). Huber's contamination is a rather strong model, as it allows for the unknown distribution of corruptions to be arbitrary. On the one hand, this level of generality makes the model quite powerful by allowing it to cover wider range of phenomena. On the other hand, its definition is inherently tied to significant information coormation--thoretii limita- tions. Specifically, it is known that even with an infinite number of samples, any mean estimator ç in Huber's model has ineur an error of I| - All = s(a). where a the rate of contamination. This happens because it is possible to start from two Gaussians (even in one dimension) with means ?(a) apart, and mix them with appropriate outlier distributions so that the contaminated distributions are iden- tical; see, e.g., Chapter I of Diakonikolas & Kane (2023).
time, and
1. Introduction
Robust statistics (Huber & Ronchetti, 2009; Diakonikolas & Kane, 2023) aims to develop accurate estimators in the presence of constant fraction of outliers. In a range of ma- chine learning scenarios, the standard i.i.d. assumption does
Authors are listed in alphabetical order. University of Wisconsin-Madison UUniversity of California, San Diego Corre- spondence to: Giannis lakovidis <iakovidis@ edsc, Thana- sis Pittas <pittas @ wis..
Proceedings of the 4 International Conference on Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
(Consistency is similarly unachievable in other commonly used corruption models like total variation contamination.)
ance case.) Intriguingly, and in sharp contrast to Huber's model, consistency is achievable in the mean-shift model. Intuitively, this happens because now all the samples are convoluted with a Gaussian; thus, given infinitely many samples, one can form the underlying distribution, perform deconvolution, and recover the single spike corresponding to the inliers. More specifically, Kotekal & Gao (2025) showed that, if the contamination parameter a is a positive constant strictly less than 1/2, the mean can be estimated to any desired accuracy e using 20(1/e²) samples. This can be used to show (see Proposition 2.1) that the d-dimensional version of the problem can be solved, up to f--error e, with n = dl d01///) samples an upper bound that is essentially best possible.
A natural way to achieve consistency is to impose additional structure on the contamination model. A prominent and well-studied assumption is that outliers do not follow arbi- trary distributions, but instead correspond to mean-shifted copies of the original distribution. Mean shift contamination has been extensively studied in the robust statisties litera- ture, for both regression (Sardy et al., 2001; Gannaz, 2007; McCann & Welsch, 2007; She & Owen, 2011) and mean estimation (Cai & Jin, 2010; Collier& & Dalalyan, 2019; Car- pentier et al., 2021; Li, 2023; Kotekal & Gao, 2025).
In this paper, we consider arguably the most basic version of mean shift contamination, where the inliers are drawn from known covariance Gaussian distribution with unknown mean μe, while each outlier is sampled from (potentially different) Gaussian with the same covariance and unknown arbitrary mean. The goal is to understand the statistical- computational landscape of mean estimation in this model.
While the one-dimensional estimators of Li (2023); Kotekal & Gao (2025) can be implemented in polynomial time, very little is known from an algorithmic standpoint for the multivariate problem. Specifically, the only known methods (achieving any desired accuracy) involve brute-force search with complexity that scales exponentially in the dimension (Proposition 2.1). Of course, one could apply efficient robust algorithms designed for Huber's model from the existing robust statistics literature. Unfortunately, such algorithms inherently cannot obtain error better than ((a)-while our goal is to achieve any desired accuracy e < a. This discussion leads to the following question, which was the main motivation for this work:
Definition 1.1 (Mean-Shift Contamination Model). For E (0, 1/2) and n E E4, a set T' of n points in Rd is called an o-corrupted set of points from ((. I) under the mean-shift model, if an adversary chooses ....... 2n, and each point x; E T is then sampled independently as follows: With probability - a, I; is sampled from N (Hs, I). and probability a. ze is sampled from I2.
Some comments are in order. A more general version of Definition 1.1 would allow the inliers and outliers be drawn from Gaussians with covariance matrix Σ. When Σ is known to the algorithm, it suffices to consider the case I (as we can transform the samples and reduce to this case). The known covariance version of the shift contam- ination model has been studied in a number of works, in- cluding Collier& & Dalalyan (2019); Carpentier et al. (2021); Li (2023); Kotekal & Gao (2025).' Moreover, the closely related (more challenging) model where the covariance is unknown has also been considered (Cai & Jin, 2010; Car- pentier et al., 2021; Kotekal & Gao, 2025). Mcan shift contamination has been studied from a theoretical statistics standpoint, with a focus on minimax rates, and as a model- ing assumption (Jin & Cai, 2007: Sun & Cai, 2007; Cai & Sun, 2009; Efron, 2004; 2007: 2008). Additional motivation can be found in (Kotekal& & Gao, 2025). A more detailed summary of related work is provided in Appendix A.
Is there a sample and computationally efficient multivariate robust mean estimator in the mean-shift model?
By the term "sample efficient", we mean estimator with sample complexity n poly(d, 21/²) samples. As is standard, computationally efficient refers to an algorithm with poly d) runtime. In this paper, we answer this question in the affirmative. As bonus, the sample complexity of our algorithm is minimax near-optimal, within logarithmic factors.
I=
Specifically, we establish the following theorem:
Theorem 1.2. (Main Algorithmic Result) Let d E E4 denote the dimension, μ E Bd be an unknown mean vector. E (0,1) be accuracy parameter, and a S +0.49 be contamination parameter. There exists an algorithm that takes as input e, draws n = =(d/f2+ol1) + 201122) a- corrupted samples from ((u, I) under the mean- meif-shiff model (Definition I. 1.1), runs in poly(n, d) time, and outputs po such that with probability at least 0.99 it holds 1 -6ll= S e.
The majority of prior work has primarily focused on the one- dimensional setting. Specifically, Kotekal & Gao (2025) obtained sharp minimax rates (upper and lower bounds) of estimating y in absolute error. (These works also con- sider the more general estimation task for the unknown vari-
Theorem 1.2 gives the first sample efficient algorithm for our problem that runs in sample-polynomial time. We re- mind the reader that, in the Huber contamination model, this goal is information iooomation-thhoreeicalll theoretically impossible; that is, no algorithm can achieve consistency regardless of its sample and computational resources. Note that the sample com-
'Carpentier al. (2021) considers special case of the model where 2; 11 are assumed to be non-negative.
2

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
plexity of our algorithm is close to optimal: even for one- dimension with a v 0.49, any estimator requires 20(1/2) samples (Carpentier et al., 2021; Kotekal & Gao, 2025); and linear dependence on d is necessary even for the outlier-free setting, Moreover, we point out that our algorithm does not need to know the value of the contamination parameter a. While we have assumed for simplicity of the statement that a S 0.49, we show in Appendix F (see Theorem F.1) that
estimator on that subspace. In particular, if we can find subspace V of dimension dim(V) S poly(1/e) such that
[Proiy (4)]l S e/2, then we can apply the algorithm of Proposition 2.1 to the projection of the dataset onto V to find a 7á E V with (1) - -ill I c/2. This would imply the desired error bound of || - A S.
A standard way to find such a V is by leveraging the sec- ond moment of the data. We have that E|az 4] E im 11 > 3zp" since at least 2/3 of samples (inliers) follow 7), and the terms corresponding to outliers are positive semidefinite. Therefore. if V is the subspace spanned by all of the eigenvectors of El Plz T - 1] with
by a mild increase in the error and sample complexity, our algorithm can be generalized to work for a E (0, 1/2 - c). for any constant E (0, 1/2), without the need know a priori.
eigenvalues more than e²/6, then ||Projy (1)] S </2. Un- fortunately, as m is unbounded, E/mm" "] could have many such eigenvalues. To fix this issue, we will need a way to effectively truncate the larger values of m.
1.1. Organization
The paper is structured as follows: In Section 1.2, we pro- vide intuition about the techniques used and the structure of the algorithm. In Section 2, we formally state the algorithm and sketch its analysis. Finally, in Section 3, we present our conclusions and discuss some interesting open problems.
To achieve this, we instead estimate the matrix A == E (xx T - T+2 exp(-((==)=- d)>]], for some carefully chosen y < 1. We can explicitly calculate the expectation for x ~ ((m, I), which turns out to be roughly equal to mm e [|m]l=]]> (cf. Lemma 2.3). Since 2/3 fraction of the samples have m nt, it follows that A >> 33 T Note that so long as || is not too large (indeed, we can assume it is ((1) by some naïve outlier removal), every unit vector with o. Av S </// must satisfy |e" yl S e/2 (cf. Lemma 2.9). Additionally, it is not hard to see that A has trace bounded by O(1/7): this implies that the num- ber of eigenvectors with eigenvalue larger than Ce2 is at most ((1((r2)) Thus, if we take V to be the span of such eigenvectors, we would have that ||Projy (w)Il S e/2 and dim()) = ((1/(re))
1.2. Our Techniques
Given samples of the form x ~ (mm, I), where m is a ran- dom variable taking the value m = ja with probability 2/3 (instead of 2/3, our model of Definition 1.1 uses - a; this is a simplification for the purpose of this proof overview), the goal is to estimate μ to f2-error e with high constant probability.
Note that, using the results of Li (2023); Kotekal & Gao (2025), it is straightforward to design a (computationally in- efficient) algorithm with sample complexity d20(1/2) and runtime 20(++1/²) via standard reduction to the 1- dimensional case (ef. Proposition 2.1). In particular, for every v in an exponentially-sizer cover of the unit sphere, we apply a robust miedinmeniooall estimator to the projec- tions of the samples u x. This gives us an e-approximation of v T ".. Piecing these values together for various values of allows us to reconstruct an e-approximation of μ.
This procedure implements one round of our dimension re- duction. For 7 = 1/vd, this reduces the dimension from d to ((vā/e)) That is, the dimension is reduced by a factor of 2 whenever dl is at least large constant multiple of 1 1/e². By repeating this procedure, we reduce the dimension down to O(1 /e.. Then, applying the algorithm of Proposition 2.1 on the remaining subspace of dimension d' = O(1/c*), completes the algorithm using 20('++1/2) = 20(1/e)) addi- tional samples and time.
As a first step towards Theorem 1.2, we will design algorithm with sample complexity poly(d)29(1/e) and run- time poly(d)29(1/+). Note that this is not yet a compu- tationally efficient algorithm, since the runtime is quasi- polynomial in the sample size. turns out that this simpler algorithm is a good start, will lay down the main ideas which eventually lead to the efficient algorithm of Theo- rem 1.2. The main idea is to design some kind of (data dependent) dimension reduction. Ideally, we would like to first find the direction /4/|μa|| along which μ lies, and then run a dieeenmnniionl robust estimator on that direc- tion to recover ||д|| More realistically, we will attempt to recover a low-dimensional subspace that on which μ has a large projection, and then run diw-dimensional robust
The first challenge towards implementing the above ap- proach is approximating A from samples. This is non-trivial, as exp exp(-([|=||2 d)-) can be as large as exp(dy), suggest- ing that we might need roughly this many samples. Fortu- nately, we note that ||ar||2 is unlikely to be much less than d. In particular, the squared norm of standard normal is approximately Gaussian distributed with mean d and stan- dard deviation vd. This implies that the expected size of exp(-([|x=]] - d)7) is approximately exp(d>²) (and it is smaller for Gaussians with other means). By simple con- centration arguments, for each entry of the matrix A, not difficult to show that poly(d/e) exp(d?3) samples suf-
3

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
fice for A to convergence . Thus, the choice 7 = 1/va made in the previous paragraph suffices for our purposes (Lemma 2.8).
We write x D for a random variable x following the distribution D and use E[a] for its expectation. We use N 2) to denote the Gaussian distribution with mean μ and covariance matrix E. For scalar random variable x, we define the T-p-norm of x to be | = E|[x||]//, We use a S 6 to denote that there exists an absolute universal constant C > 0 (independent of the variables or parameters on which a and depend) such that S Cb. We use polylog() to denote quantity that is polylogarithmic in its arguments and we use Ô to hide such factors.
We emphasize that there are two problems with this approach to be addressed. The first is that the run- time of the algorithm presented so far is not polynomial: this is because the overall number of samples is n poly(d)20(/e)) while the runtime of the final brute-force step is poly(d)290/<)) Second, we would like the sample complexity to be linear in d rather than poly(d).
In order to resolve the first issue, we need our dimensionality reduction to be able to bring the dimension all the way down to ((1/=))- rather than O(L/e*). To achieve this, can first reduce the dimension to d' = O(1/e),, described in the earlier paragraphs, and then change the value of y to 1/(vd'). This way, the next iteration will reduce d' to O(Vd'/e) /e) (which means that we can keep halving the dimension until d' becomes a constant multiple of 1/(2). Using this value for y implies that each iteration will be using exp(O(d'
2. Efficient Robust Mean Estimation in the Mean-Shift Model: Proof of Theorem 1.2
In this section, we present our algorithm (Algorithm 1) and establish Theorem 1.2. Section 2.1 provides a sample- efficient but computationally inefficient estimator, which will be employed at the final step of our algorithm (after the dimension has been significantly decreased). Sections 2.2 and 2.3 analyze our dimension reduction procedure: Sec- tion 2.2 records the desired properties of the reweighted second moment matrix that our algorithm relies on, and shows that they hold with high probability with sufficiently many samples. Finally, Section 2.3 provides the core anal- ysis of the dimension reduction procedure, and combines everything to prove Theorem 1.2.
exp(O(1/e²) samples and time (Lemma 2.8). Finally, we apply Proposition 2.1 to the resulting subspace V.
To improve the sample size dependence on the dimension (cf. Lemma 2.7), we require strong concentration bounds, in particular the Matrix Bernstein inequality. However, to ap- ply this inequality, one needs a universal bound for our ran- dom variable ax. exp(=[[|=<|] - d))), which is bad when ||a||| is small. Fortunately, this happens with small probabil- ity, and we are able to show that truncating the values when ||>|| is much smaller than d will not affect the final mean by much. However, taking 7 = 1 1/vd will prove not quite suf- ficient for our purposes: there will be roughly a 1/d 1/d-fraction of samples with |ax||² d d-D(v/ /d log(d)), leading to terms with norm on the order of d (exp(S(( v /log(d])), and it will take a slightly super-linear number of samples to average these away. To handle this, we need to use a slightly smaller value of 7, such as 1/ 1/vd/b/ log((d))
2.1. Computationally Inefficient Multivariate Robust Estimator
Proposition 2.1 below provides a robust multivariate mean estimator for the mean-shift model that uses n = d (1//)) samples and 20(d) poly(n, d) runtime. Although the run- time exponential in the dimension, it becomes just poly(n, d) if d o(1/²). Therefore, this estimator will be useful after our dimension reduction technique that will be developed in the next sections manages to reduce the dimension to O(1/2)).
Proposition 2.1 (Inefficient Estimator). Let d E Z, denote the dimension, and C. be a sufficiently large absolute con- stant. Let S 0.49, E <> O, and ò E (0, 1) be parameters, and μ Rd be an (unknown) vector. There exists an algo- rithm that, on input and any set of n 2 20/2² (d+log(1/0) c-corrupted set points from N T) under the mean-shift model (cf. Definition 1.1), outputs a ÿa such that l| -pll S e with probability at least 6. Moreover, it runs in time 20(d) poly(n, d).
Notation We use Z_ for the of positive integers. We denote [n|] = (I....., n... For vector we denote by ||ж||| its Euclidean norm. Let Ia denote the d x d identity matrix (omitting the subscript when it is clear from the context). We use T for the transpose of matrices and vectors. For a subspace V of Rdd of dimension m, we denote by ly e Rddd the orthogonal projection matrix of V. That is, if the subspace V is spanned by the columns of the matrix Rd we
A, then Hy A(A A(AAA)-1AA AA For vector use (z)jy(x) = Tyy to denote the orthogonal projection of x onto V. We say that symmetric d x d matrix A is PSD (positive semidefinite) and write A >> 0 if for all x E Rd it holds x Ax 2 O. We use ||Allop and ||Al|e for the operator (spectral) and Frobenius norm of a matrix A respectively.
Proposition 2.1 follows in a relatively standard way by tak- ing fine discretization of the unit sphere, running the one- dimensional estimator for each of the directions in that cover set, and combining the solutions to a vector (see, e.g., Sec- tion 1.5 of Diakonikolas & Kane (2023)). For completeness, we provide a proof of correctness in Appendix C using the
4

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
univariate estimator of Fact 2.2 as black-box. A nice prop- erty of the prior work is that the robust univariate estimator has breakdown point arbitrarily close to 1/2 and does not need to know the contamination parameter (c.f. Section 5.3 of Kotekal & Gao (2025)).
Fact 2.2 fone-dimensional estimator, see, c.g., Li (2023); Kotekal Gao (2025)), Let μ be an (unknown) mean. Let C be a sufficiently large constant and a S 0.49. There is algorithm that given. > 0, 5 (0,1) and set of n = 20/2 1og(1/8) a-corrupted samples from N(s. 1) according to the mean-shift model (Definition 1.1), finds IR such that, with probability least 1 5, it holds j ul S The runtime of the algorithm is poly(n).
Algorithm Mean Estimation under Definition 1.1
1: Input: Accuracy é >> 0.
2: Output: Tt E Rd such that 1 14/1 S.
3: Fix C a sufficiently large constant, no no=Cd,
Ty (dd log (d), and n2=20/² log (d).
/ "Rough Estimation:*/
2.2. Reweighted Second Moment Matrix
5: Draw To. set of no corrupted points according to Definition 1.1.
The structure of this section is as follows. Equation (1) de- fines the reweighted second moment matrix that will be used by our dimensionality reduction procedure. Subsequently, Definition 2.6 states the deterministic conditions regarding this matrix that will be required for the correctness of our dimension reduction algorithm. Finally, in Lemmas 2.7 and 2.8, we show that the matrix satisfies these conditions given sufficiently many samples.
6: Use To to find 7o with
{e.g.. Corollary
2.12 12 and Exercise 2.10 in Diakonikolas & Kane (2023)}
7: 1 Dimension Reduction:
8: Initialize + 1, k + d and Vi = R* .(K will denote the dimension of the current subspace)
while 1/e² do
10:
if l: 2 C log (d)/c5 then
11:
set B + v /log(k) and N t n2, mp + (e/logd)
For B E (0, 1). a subspace V S Rd of dimension h: S d, and points II, E V, define the matrix:
12:
else
13:
set 3 + and N +- 12, T) + 36e/vk.
14:
end if
n
Ā A:
= Σ
A,
where A. = Fa.n(z:)Za,a.
15:
Draw a TV of N corrupted points from the model of Definition 1.1.
11 i=1
++2
16:
T. + (Projy, (x πo): x ET).
ZB =
11
17:
Å. 17. En,en A, as defined in (1).
3vK)
18: Find the eigenvectors of oi (2+1) ,..., Ug
(e+1) of A.
BVK
1|x112
Fa ==
xx
Ily
AVE
(1)
with eigenvalue at least ne (let k' denote the number of such eigenvectors).
BVk +2 2
19: Let V be the subspace spanned by
where Hy denotes the orthogonal projection matrix of the subspace V. The subspace V will be the one that the algorithm maintains in each round (and whose dimension decreases in every round). For simplicity, the reader can think of V R and Ily Ls; however, since the basis of the subspace may not be aligned with the elements of the standard orthonormal basis, using Hy is required in general.
{or (o((+1) .....; u/ ((+1)).
20: Update ks - k'' and L 1+
21: end while
22: Run Inefficient Algorithm:*/
23: Sample set T of nz corrupted points from the model
of Definition 1.1.
24: T, + [Projy, (z) x E T...
The definition of A has been designed so that the ex- pectation of a single sample's deviation, namely (xxT
25: Use T, to find pn E V, with 1| Projy, (1)) S c.
[Use Algorithm from Proposition 2.1}
1=12 BVK T)e EVE when x ~ N(z, 7) is roughly proportional
26: return Projy/ (7o) + 7
BVk+2
1x=12
to =2 e DVW This shown in Lemma 2.3 below. The fac- tor Z3, is the appropriate normalization factor that arises. Lemma 2.3. Let V S dgd be subspace of pd of dimension h < d. For any z E V. we have that 1=12
Eg,,((,, [x)) Za,k = TzTe #VE+s, where Fg.k and Z are as defined in Equation (1).
5

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
The deterministic conditions that we require to hold with high probability quantify how close A needs to be its 1s,1"
Lemma 2.7. Let (0, 1) and k E 24 denote the dimen- sion, and assume k is bigger than a sufficiently large con- stant. There exists sample size n. = klogg (k)(1/))2+o()) such that the following holds: Let T be a set of a-- corrupted from (ju, T) according to Definition I.I with the assumption that || = O (1). Denote by =1 E1,.... Zan the adversarial centers in Definition 1.1. Then, with probability at least 1 8, T is (1), vlog (oggk)-ge -)-good with respect to μr, : Zun-
expectation A := E== 2,2, e 3V812. For the inlier tion 2.4). For the outlier samples, it will suffice to have the milder condition that the reweighted second moment is not too negative (cf. Definition 2.5). Finally, note that
points, we will require closeness of the reweighted second moment to its expectation in operator norm (ef. Defini-
1 2vR12 has
the expectation matrix A := Σ 1i=1 ziz
1 JV++3 S BVK + 2, where we used the elementary inequality ye ye-w/7 S y for y > O. The bounded trace will be a key property for the correctness of our dimensionality reduction procedure. We will thus re- quire the same property to hold for the empirical reweighted moment matrix. Definition 2.6 combines all three of the aforementioned conditions.
For the case 6, we can resort to a simpler proof which consists of calculating the variance of each entry of our ran- dom matrix and using Chebyshev's 's inequality entry-wise. This is done in Lemma 2.8. Although the resulting depen- dence on the dimension k scales as k-, we will use this bound only after the dimension has decreased to roughly 1/e"; meaning that the sample complexity will be domi- nated by the factor 20/²" The full proof can also be found in Appendix D.
tr(A)= E ||
Definition 2.4 (17, conocenntre set). Let 1 > 0 be parameters, V be a k-dimensional subspace of Rd and let Ii...., In V. We say that the set [I is (n. 3)- concentrated with respect to V and 21,..., En E V, if the
Lemma 2.8. Let T be a set of n a-corrupted set of points from (p, 1) according to Definition 1.1 for some μ with 12_ 2012 for sufficiently large
||||| O(1). Assume absolute constant C. where k 2 1/²² and n S c. Denote by 21.....2a0 Pan the adversarial points used in Definition I.1. Then, with probability at least -, 5, T is (1,,)) e)-ooo with respect to μt, : Zon-
matrix A defined in Equation (1) satisfies ||A - A lop S 1).
1
where A == 2/2 ET=1 242,12 BVE+2
Definition 2.5 ((1), ))-oositive definite). Let 1/, 3 > 0 be parameters and V be a k-dimensional subspace of Rd. We say that the set of points II, E V is (1z, B)-positivee definite, if the matrix À defined in Equation (1) satisfies oT Au 2 for all u E V with ||o|| =
We conelude this section with brief proof sketch of the first of these lemmata.
Definition 2.6 (11, ()-goo set). Let n. > 0 be param- eters and V be a k-dimensional subspace of Rd. A set T of points in V is called (11, -))-good with respect to V and the vectors [a, 21.-... : Zevn E if there exists S C T, with |S| = (1 - a) [T] such that:
Proof Sketch of Lemma 2.7. We focus on showing Item (i--psittive definiteness) for the set of outliers, as the other parts can be proved similarly. Let A Ex.,eT, A. where Ag as defined in Equation (1). First note that, A =
using Lemma 2.3, we have that B[A]
1. (Condition for inliers) S is (n. ()-coneenteete with re- spect to V and the vector sequence pt, pu...., (i.e., the sequence that has the p vector (1 o.)n times).
1- 1 Σ, 2,2,T e viDTa is positive semidefinite. Hence, in order to prove that Ā is r-positive definite, it suffices to prove that A cannot be much smaller than A in every direc- tion.
2. (Condition for outliers) T \ S is -)posivee definite.
3. (Bounded trace condition) The matrix A from (1) com- puted over all x4 E T has tr( ()) S 188VK.
|zy|2 WAT
First note that the e
Z factor appearing in the def- 1=,1²=>
inition of À behaves roughly like e V.loo,, as Z = @(evk/ ((egk//lok)) for 3 = Vlogk. Towards showing con- centration with linear number of samples, we first note that the || 1 (appearing before) is bounded, except with tiny probability. That is, we argue that, without loss of generality, we can work with the matrix of the form A' = Exeris (,) instead of A. Here &, is defined to be the following good event: | |2 - (I + k)
Lemmas 2.7 and 2.8 show that a sufficiently large set of samples from our model satisfies our (17, -oooddnsssss condi- tions with high probability. We need two lemmata because our algorithm will use 3 = vlog K for the most part, and 3 = for the last few iterations.
For the case B = vlog& Ti (corresponding to Lemma 2.7), we need to use strong concentration bounds in order for the sample complexity to scale linearly (up to polylog factors) with the dimension & (see proof sketch at the end of this section and full proof in Appendix D).
log(1/r) + (Vk- + || /log(1/T), where T == (1/n)² This is indeed without loss of generality because: (i) E, hold with probability 8 for all simultaneously (each 3, fails
6

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
with probability by Fact B.5, and thus the probability that
Aintiers uu BvR12,
T ZB. Σ FRa(x),
there exists& & that fails is at most S 1/n 8 by union
bound); and (ii) we can prove that [ - All S //2,,ie. i.e., the truncation shifts the mean by a small amount.
Aoutliers an ZETiS
Then we can apply standard concentration results on A', as our expressions are appropriately bounded. We achieve this by carefully decomposing A' into three terms by writ- ing I;- = 2 + 9i. where Ji ~ (0, I): A, = (99g)
1-112
Aoutliers ON
Σ iZ
2,2 e ov4+2
A'
where Zz, and F3. are as defined in Equation (I). We can decompose A into inliers and outliers, i.e., A = (1 a) Amaiters + ooouttiers. By the assumption that T is (17, B)- good (cf. Definition 2.6), we have that T \ SS is r-positive definite (cf. Definition 2.5); hence e Aouttiers 2 -1).
1
v (2) 1) + (zig, + +z
y (k)
+ 2,2, Je Vilogik) ZØ
Th: + T2: + T3S- For the first and second term, we use Hoeffding's inequality for subgaussian random variables along with cover argument. For the third term, we use the Matrix Bernstein Fact B.4 inequality. This ap- plication requires an absolute bound on ||Ta:ll S K that holds almost surely, as well as a bound for the matrix variance || [T]]l Given the "good events" from above, we can use that exp(-I|=||) / log Z)Z Vlog is roughly less than exp( [|= /v log k). We can thus obtain that [|Taa]| || S || 2 exx((-11=: 112/ /V log F) S vl log k and ||= 4 exp(-2 exp(-2||==11/////
By assumption, S is n-concentrated (Item 1 of Defini- tion 2.6); thus |e To Ainliers a Aiuiirs S n7.
Putting everything together. for every unit vector e for which v Av S 17, we have that:
(1 - a)u T Ainliers
(2)
= (1 aa)= Aintiess + (1 - (1-a)u (Ainliers A )v
log k) S log k. which results in hear-linear in k sample complexity.
= =v_ Av - ore" T Aoutlterst + (1 - a)v" (Aialiers - Amtters)
I n + an + (1 - -a) S $21.
2.3. Analysis of Algorithm 1
1el2 Using that Aiutiers = pu e Dv4+2, the above im- M|ml
The lemma below the core of the analysis for single iteration of our dimensionality reduction technique. Since the sample version A, of the matrix, that we use in Algo- rithm 1 of Algorithm 1, is close to its expectation, we show that our naïve estimator from the first step of the algorithm is accurate inside the subspace of small eigenvalues of Å, (see Lemma 2.9). Combined with Item of Definition 2.6, which bounds from above the number of high eigenvalues, conclude that single round of our dimensionality re- duction loop halves the dimension without accumulating error.
plies that (o u22 I 21 F S n. where the last
inequality is because || O(1). Finally, since
(19)1)(1)1 = max max j4/. it follows that Proju((1) S ((VT).
2.3.1. PROOF OF THEOREM 1.2
We are now ready to prove our main theorem. The full proof is deferred to Appendix E. We use the same notation as in the pseudocode provided in Algorithm 1: the t-th iteration of the while loop maintains subspace V., whose dimension, k starts from d and can only decrease from a round to the next one. This while loop has two distinct phases: Phase will refer to all the iterations during which C (log'())/ S k S d, and Phase 2 will refer to all the iterations with 1/e² & k < C' Cllog(d)/ The analysis of the algorithm consists of the claims stated below. The claims are that each of the following holds with high constant probability:
Lemma 2.9. Let B > O and V be subspace of TRd of dimension k S d. Let T be an (g, good set of n samples (cf. Desinition 2.6) with respect to the subspace V and the vectors p. 2,z,,... Ron E V, and assume that ||н||| = O1)). Define À as in (1). If is a subspace of V such that Av S for all unit vectors u E U, then we have that [Proju(19]] O(vT), where (-)ju(.) denotes the projection subspace U.
Proof. Without loss of generality, we will prove the lemma for the case where V = R Since T is (n, -oodo it can be partitioned into S (inliers) and TV, S (outliers), where the two sets satisfy the properties of Definition 2.6. Consider the matrices
1. Warm start: If تo is the estimator from line I of Algo- rithm 1, then 11 ا|| = O(1).
2. Dimension Reduction: If Ti, To denote the number of iterations of Phase 1 and Phase 2 respectively, then Ti < (d).)), T2 S 100 log(log(d)/ee) Moreover, for all I....,.. Ti + T2, we have ||rrojyz, (No - -+]l S
ZB.k Σ F9,((2),
Amiiers
Σ E Vig, where me are the values set in lines and
ZES
7

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
3. Estimator for the remaining subspace: The lines 1-1 of Algorithm 1 find a vector fún V such that l|ā1 - Proiy, (1))l S.
probability. Note that because of the warm start in line I and the transformation subtracting 7Ag in Algorithm 1, every sample essentially comes from the mean-shift with mean O(1, which makes Lemma 2.7 applicable. The number of eigenvectors with eigenvalue larger than t is at most tr tr(Aa)/ m & 18 18 log k/n, = O(log d Vllo k) I Ollog (d) where we first used the definition of (7,, vlog -oooddds (Definition 2.6) and then that 1):
Here we will sketch how each claim can be proved, with the full details in Appendix E. We start by showing how the claims imply that | all = O(e) for ç == No + ?
Consider t = Ti + T2. so that Vi denotes the subspace after exiting the while loop. By decomposing the true mean into the projections onto the two orthogonal subspaces we have that 1 Projy- (1) + Projy, (n)) By the Pythagorean theorem, write
(c/ log d)² Thus, long as k > C'log" (d)/c², Clog"(d)/c , the dimen- sion during each round gets halved. After Ti = O(log d) such iterations, the dimension reaches C' C'log" (d)/e", af- ter which the aforementioned no longer guarantees that it will continue to drop. This is the reason why we need to change the value of [ to e, and set 7/t == 36e /.le/vk in Algorithm for the remaining iterations (Phase 2). The argument for Phase 2 is similar, but uses different param- eters: our datasets are now e)goo) by Lemma 2.8, and the number of eigenvectors larger than Y/2 is now at most tr tr(A,)/m S 183/k/n = k/2. Thus, Phase 2 will continue to halve the dimension. Finally, the claim that [rrojyy (Ro - ا)] 2 Ei= vTy follows immediately from Lemma 2.9.
|| - /l2 = [|Proly; (Au 11) + Projy, (P1 11)l [|Projyt (No - 10)11 + [|Projy, (ū1 - m)1
The last term is ||Projy, (f1 -1)ل < e by Item 3. It suffices to bound the first term by O(c). Towards this end, denote = Cllog (d)/e5, which the dimension during the first iteration of Phase Then,
Proijy (Pa +)ll
T T2
T2
T VTv
T
Runtime and Sample Complexity of Algorithm It can be readily verified that the number of samples no, Ri, n2 defined in Algorithm 1 of the algorithm suffice for the afore- mentioned applications of Lemmas 2.7 and 2.8. Thus, the overall sample complexity of the algorithm is n (72 O(d)+d polylog(d)e-(2to05)) 20(1/2) polylog(d). (d). Regarding runtime, the most compu- tationally intensive part is the last step of the algorithm (Algorithm 1), which has runtime = 20(k) poly(nz, d), where the k = 1/e² here denotes the dimension of the final subspace. Since n2 20(122) sample-polynomile
The
+
Σ
Vie
1==1
P=1
V= +1
(from Item 2)
Ti+Ta
Ti+T,
<
Ti logd d
E + Σ
VTe Set +
Σ
VTe
("TT+1
==
36c
36c
36c
Set
+
VD
VD/2
V
V1/22)
oVE lg(De?
GVVE
i.e., polylog(d)) (d), that runtime is d). It is easy to check that the other parts of the algorithm are also polynomial in the size of the input.
sct
D1/4 Σ
21/4 sct
(21/4 1)D
i=0
6
= (21/4 - 1)D1/4 (D2)1/ASE. Se,
This completes the proof of Theorem 1.2.
where we used the definition of bh from lines 1,1, and direct calculations for the series (lg(-) denotes the logarithm with base 2).
3. Conclusions and Open Problems
In this paper, we provide the first polynomial-time algo- rithm for high-dimensional mean estimation under mean- shift outliers. In this model, the outliers are not completely adversarial as they include a randomized component. This additional structure allows for consistent estimation, which is unattainable in purely adversarial models.
Finally, we discuss briefly the proofs of the claims in Items 1 to 3. The first and the last follow immediately by Diakonikolas & Kane (2023) (Corollary 2.12 and Ex- ercise 2.10) and Proposition 2.1 respectively. Regarding Item 2, let us first consider Phase 1 (iterations during which k 2 C Cllog (d))ee). By an application of Lemma 2.7 with = Th = (e/ log df² and a union bound, all the sets Ti drawn in line will be (7,, vlog k) gooo with high constant
Our work takes a first algorithmic step in understanding the complexity of nigh-dimensional estimation for the known covariance mean-shift model of Definition 1.1. A number of concrete open problems and future directions suggest them selves. What is the complexity of robust mean estimation for the known covariance case when the underlying distribution
'The guarantee of Theorem 1.2 is 1|p - μIll < e. Here we show (e)) in order to keep the constants that appear simple. This is w.l.o.g. one can later replace e by e/C' for a large enough constant C to obtain Theorem 1.2.
8

---

Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination
Gaussian? there computationally efficient learner for the unknown covariance Gaussian case? We hope that this work will inspire further algorithmic work in robust estimation under structured contamination models.
in large-scale multiple testing. The Annals of Statistics, 38(1):100-145, 2010.
Cai, T. T. and Sun, W. Simultaneous testing of grouped hypotheses: Finding needles multiple haystacks. Jour- nal of the American Staristical Association, 104(488): 1467-1481, 2009.
Acknowledgments
ID was supported by NSF Medium Award CCF-2107079 and H.I. Romnes Faculty Fellowship. Gl was supported in part by NSF Medium Award CCF-2107079 and NSF Award DMS- (TRIPODS). DK was supported by NSF Medium Award CCF-2107547 and NSF Award CCF- 1553288 (CAREER). TP was supported by NSF Medium Award CCF-2107079.
Carpentier, A.. Delattre, S., Roquain, E., and Verzelen, N. Estimating minimum effect with outlier selection. The Annals of Statistics, 491):222-294, 2021.
Charikar, M., Steinhardt, J., and Valiant, G. Learning from untrusted data. pp. 47-60. ACM, 2017. doi: 10.1145/ 3055399.3055499
Chierichetti, F., Dasgupta, A., Kumar, R., and Lattanzi, Learning entangled single-sample gaussians. pp. 511- 522. SIAM, 2014. doi: 10. 10.113//19781161193442.333
Impact Statement
The primary contribution of this research lies in theoretical advancements and foundational insights. Therefore, we believe that it does not have direct implications for societal, ethical, or policy-related issues.
Collier, O. and Dalalyan, A. Multidimensional linear func- tional estimation sparse gaussian models and robust estimation of the mean. Electronic Journal of Statistics, 13:2830-2864, 2019.
References
Compton, S. and Valiant, G. Near-optimal mean estimation with unknown, heteroskedastic variances. In Proceed- ings of the 56th Anmual ACM Symposium on Theory of Computing, pp. 194-200. 2024.
Achlioptas, D. and McSherry, F. On spectral learning of mixtures of distributions. In Proc. 18th Annual Confer- ence on Learning Theory (COLT), 2005.
Arora, S. and Kannan, R. Learning mixtures of arbitrary Gaussians. In Proc. 33rd Annual ACM Symposium Theory of Computing (STOC), 2001.
Dalalyan, A. S. and Minasyan, A. All-in-one robust estima- tor of the gaussian mean. The Annals of Statistics, 50(2): 1193-1219, 2022.
Bakshi, A., Diakonikolas, I., Jia, H., Kane, D. M., Kothari, P. K., and Vempala, S. S. Robustly learning mixtures of arbitrary gaussians. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp- 1234-1247, 2022.
Dasgupta, S. Learning mixtures of Gaussians. In Proc. 40th IEEE Symposium Foundations of Computer Science (FOCS), 1999.
Devroye, L., Lattanzi, S., Lugosi, G., and Zhivotovskiy, N. On mean estimation for heteroscedastic random vari- ables. Annales de I l'Institut Henri Poincaré, Probabilités et Statistiques, 59(1):1-20 2023.
Barreno, M., Nelson, B., Joseph, A. D., and Tygar, J. D. The security of machine learning, Machine Learning, 81 22:121-148, 2010.
Diakonikolas, I. and Kane, D. M. Algorithmic high- dimensional robust statistics. Cambridge university press, 2023.
Belkin, M. and Sinha, K. Polynomial learning of distribution families. SIAM Journal on Computing, 44(4):889-91) 2015.
Diakonikolas, I., Kamath, G., Kane, D., Li, Moitra, A., and Stewart, A. Robust estimators in high high-dimensions without the computational intractability. FOCS 2016, SIAM Journal on Computing, 2016.
Biggio, B., Nelson, B., and Laskov, P. Poisoning attacks against support vector machines. In Proceedings of the 29th International Conference Machine Learning, ICML 2012, 2012.
Diakonikolas, I., Kamath, G., Kane, D. M., Li, Moitra, A., and Stewart, A. Robustly learning a gaussian: Getting optimal error, efficiently. In Proceedings of the Twenty- Ninth Annual ACM-SIAM Symposium on Discrete Algo- rithms, SODA 2018 pp.
Birgé, L. An alternative point of view on lepski's method. Lecture Notes-Mon Moosorooogg Series, 2001.
Cai, T. T. and Jin, J. Optimal rates of convergence for esti- mating the null density and proportion of nonnul effects
2018a. Full version available https//arriv.orgaab//1004..... 03366..

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
Diakonikolas, I., Kane, D. M., and Stewart, A. List- decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th An- nual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 1047-1060, 2018b. Full version avail- able at https//arriv.rr/aa////11.77
Hopkins, S. B. and Li, J. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th An- nual ACM SIGACT Symposium Theory of Computing, STOC 2018, pp. 1021 1034, 2018.
Huber, P. and Ronchetti, E. M. Robust statistics. Wiley New York, 2009.
Diakonikolas, I., Kamath, G., Kane, D., Li, J., Steinhardt, J., and Stewart, A. Sever: A robust meta-algorithm for stochastic optimization. In Proceedings of the 36th Inter- national Conference on Machine Learning, ICML 2019, pp. 1596-1606, 2019.
Huber, J. Robust estimation a location parameter. Ann. Math. Starist., 35(1):73-101, 03 1964.
Jin, J. and Cai, T. T. Estimating the null and the proportion of nonnull effects in large-scale multiple comparisons. Journal of the American Statistical Association, 102(478): 495-506, 2007.
Diakonikolas, I., Kane, D. M., Kongsgaard, D., Li, J., and Tian, K. Clustering mixture models in almost-lineas time via list-decodable mean estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022.
Kannan, R., Salmasian, H., and Vempala, S. The spectral method for general mixture models. Proc. 18th Annual Conference on Learning Theory (COLT), 2005.
Diakonikolas, I., Kane, D. M., Pittas, T., and Zarifis, N. SQ lower bounds for learning mixtures of separated and bounded covariance gaussians. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2319 2349. PMLR, 2023.
Kong, W., Somani, R., Song, Z., Kakade, S., and Oh, S. Meta-learning for mixed linear regression. In Interna- tional Conference Machine Learming, pp. 5394-5404. PMLR, 2020.
Diakonikolas, I., Kane, D., Pensia, A., and Pittas, T. Near- optimal algorithms for gaussians with huber contamina- tion: Mean estimation and linear regression. Advances in Neural Information Processing Systems, 36, 2024.
Kotekal, S. and Gao, C. Optimal estimation of the null distribution in large-scale inference. IEEE Transac- tions on Information Theory, 2025. Full version in arXiv:2401 2XXx:2401.06630..
Diakonikolas, I., Kane, D. M., Liu, S., and Pittas, T. En- tangled mean estimation in digh-diiensions. In Proc. 57th Annual ACM Symposium on Theory of Computing (STOC), 2025.
Kothari, P. K., Steinhardt, J., and Steurer, D. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 1035-1046, 2018.
Du, X., Fang, Z., Diakonikolas, I., and Li, Y. How does un- labeled data provably help out-of-distribution detection? arXiv preprint arXiv:2402.03551 2024. To appear in the International Conference on Learning Representations (ICLR) 2024.
Lai, K. A., Rao, A. B., and Vempala, S. Agnostic estimation of mean and covariance. In Proceedings of FOCS 16, 2016.
Efron, B. Large-scale simultaneous hypothesis testing: the choice of a null hypothesis. Journal of the American Statistical Association, 99(465):96-104, 2004.
Lepskii, O. V. On a problem of adaptive estimation in gaus- sian white noise. Theory of Probability & Its Applications, 35(3):454 466, 1991.
Efron, B. Correlation and large-scale simultancous sig- nificance testing. Journal of the American Statistical Association, 102(477):93-103, 2007.
Li, J., Absher, D., Tang, H., Southwick, A., Casto, A.. Ramachandran, S., Cann, H., Barsh, G., Feldman, M., Cavalli-Sforza, L., and Myers, R. Worldwide human relationships inferred from genome-wide patterns of vari- ation. Science, 319:1 100-11404 2008.
Efron, B. Microarrays, empirical bayes and the two-groups model. Statistical Science, (1):1 - 22, 2008
Gannaz, I. Robust estimation and wavelet thresholding in partially linear models. Statistics and Computing, 17: 293-310, 2007.
Li, S. Robust mean estimation against oblivious adversaries. Master's 's thesis, Carnegie Mellon University Pittsburgh, PA, 2023.
Gao, C. Minimax estimation in efron's two-groups model, 2024. URL https://///// //tw:.//wwwwee// wwwp:iiirt........m /x/ RepOrga/3087 //5111// deds wediiddsssminn hwt.//mmmiiiy..eee
Liang, and Yuan, H. Learning entangled single-sample Gaussians in the subset-of-sipee -iggnalls model. In Conference on Learning Theory, pp. 2712-2737. PMLR, 2020.
10

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
Liu, A. and Li, J. Clustering mixtures with almost opti- mal separation in polynomial time. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1248-1261, 2022.
Tran, B., Li, J., and Madry, A. Spectral signatures in back- door attacks. In Advances in Neural Information Pro- cessing Systems 31: Annual Conference Neural In- formation Processing Systems 2018, NeurlPS 2018, pp. 801 8011-8021, 2018.
McCann, L. and Welsch, R. E. Robust variable selection using least angle regression and elemental set sampling. Computational Statistics & Data Analysis, 52(1))249- 257, 2007.
Tukey, J. W. A survey of sampling from contaminated distributions. Contributions to probability and statistics, pp. 448 485, 1960.
Moitra, A. and Valiant, G. Settling the polynomial learnabil- ity of mixtures of gaussians. In 2010 IEEE 5/ Annual Symposium on Foundations of Computer Science, pp. 93- 102. IEEE, 2010.
Vershynin, R. High--imensional Probability: An Intro- duction with Applications in Data Science, Cambridge University Press, 2018.
Xia, D. Non-asymptotic bounds for percentiles of inde- pendent non-identical random variables. Statistics & Probability Letters, 152:1 2019.
Paschou, P., Lewis, J., Javed, A., and Drineas, P. Ancestry informative markers for fine-scale individual assignment to worldwide populations. Journal of Medical Genetics, 47:835-841 2010.
Yuan, H. and Liang. Learning entangled single-sample distributions via iterative trimming. In International Con- ference on Artificial Intelligence and Statistics, pp. 2666- 2676. PMLR, 2020.
Pensia, A., Jog, V., and Loh, P. Estimating location rameters in entangled single-sample distributions. CoRR, abs/1907.03087, 2019a.
Pensia, A., Jog, V., and Loh, P. Mean estimation for entan- gled single-sample distributions. pp. 3052-3056, 2019b.
doi: 10.1 1L.110//SIT.2219.884999
Pensia, A., Jog, V., and Loh, P.-.. Estimating location parameters in sample-hetroogeneous distributions. In- formation and Inference: A Journal of the IMA, 11:
959-1036, June 2021. ISSN 2049-8772. doi: 10. 1093/imaiaifiaab013. URL attps://doi.oor 1093/maaiii/aabbe
Rosenberg, N., Pritchard, J., Weber, J., Cann, H., Kidd, K.,
Zhivotovsky, L., and Feldman, M. Genetic structure of human populations. Science, 298:2381-2385, 2002.
Sardy, S., Tseng, P., and Bruce, A. Robust wavelet de- noising. IEEE transactions on signal processing, 49(6): 1146-1152, 2001.
She, Y. and Owen, A. B. Outlier detection using nonconvex penalized regression. Journal of the American Statistical Association, (66(494):626-63), 2011.
Steinhardt, J., Koh, P. W., and Liang, P. Certified defenses for data poisoning attacks. Advances in Neural Infor- mation Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pp. 3517- 3529, 2017.
Sun, W. and Cai, T. T. Oracle and adaptive compound decision rules for false discovery rate control. Journal of the American Statistical Association, 9021479): 2007.

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
Supplemental Material
The appendix is structured as follows: First, Appendix A includes a more detailed summary of related work. Appendix includes additional preliminaries required in subsequent technical sections. Appendix C gives the correctness analysis of Proposition 2.1. Appendix D contains the proof's of the technical lemmas involving the reweighted matrix used in Section 2.2. Appendix E contains the full proof of our main result (Theorem 1.2). Finally, Appendix F establishes Theorem F.I, which demonstrates adaptivity to unknown contamination parameter a arbitrarily close to 1/2.
A. Additional Related Work
Additional Related Work on Mean Shift Contamination The most closely related work to ours is Kotekal & Gao (2025). They study the same problem as ours in one dimension and derive matching information theoretic upper and lower bounds for mean estimation. Kotekal & Gao (2025) also considers estimating the variance in the case when it is unknown the algorithm. A similar upper bound for mean estimation in the unit variance case was also given in Li (2023). In earlier work, Carpentier et al. (2021) studied the sample complexity of robust mean estimation for the special case of Definition 1.1 in one dimension where z; > 0.
More broadly, the problem of mean estimation with mean shift outliers has its roots in influential work by Bradley Efron (Efron, 2004; 2007: 2008) in the context of multiple hypothesis testing. In these works, Efron noticed through empirical evidence that, because the parameters of the null distribution are unknown, testing should be done in two stages: (i) estimation of the null parameters, and (ii) testing of null alternative hypothesis using standard multiple testing procedures. Although the focus of our paper theoretical, we refer to the discussions in Carpentier et al. (2021); Kotekal & Gao (2025), the CIRM talk in Gao (2024) and the references therein, for a discussion of the connection between the mean-shift noise model and Efron's work.
Variance Parameter We highlight two points regarding the variance of samples in the mean-shift model. First, the variance may be unknown to the algorithm, unlike the identity/known covariance case in Definition 1.1. Specifically, consider a variant of the model (in one dimension for simplicity) where inliers are drawn from N(H, 0²) and outliers from N(z,, ) This setting has been studied in prior work (see, e-g.. Cai & Jin (2010); Carpentier et al. (2021); Kotekal & Gao (2025)). Notably, the last two works first analyze the case where the variance known and equal to one, and then extend to the more general setting where is unknown, designing estimators for both the variance and the mean. Even when the goal is solely mean estimation, their approach requires variance estimation as a first step. In contrast, Li (2023) considers only the known variance case.
The second point concerns what happens to the optimal error if outliers have different variances than inliers. Concretely, consider the model where inliers are drawn from N(p,, o²) and outliers from from ((2,, of). If outliers can have smaller variance than the inliers (a; < o), then estimation is intrinsically harder than in the case where a; 2 a. The reason is that estimation under Huber contamination can be reduced to estimation in the mean-shit model with a; < a. Specifically consider the Huber contaminated sample with inliers that follow N (M,, o²) and outliers z;. By adding (O a²) noise (with a >> 0) to both inliers and outliers, we have that the inliers after the transformation follow N(,,, o² + a²) and the outliers follow (22,, a²), which is an instance of mhan-shift contamination with d; < a. Importantly, the consequence is that estimation with error that goes to zero is not possible in the mean-shift model where outliers have smaller variance than the inliers. There exists experimental work in the literature (Cai & Sun, 2009) which includes experiments with both smaller and larger variance, however as we mentioned provable consistent estimation is impossible in such cases.
Furthermore, note that in the setting where o; 2 J, we can essentially assume that all o; are exactly equal to a. To see why, consider the random variable for single outlier sample: 5; 2; (O of). Observe that
rewrite o; as r; (z, (0, of d²)) + +0, o²). Hence, by treating the outlier centers themselves as random variables, one can run an algorithm that solves the mean estimmattnn problem in the mean mean-shift shift model with unknown variance. Finally, the same argument applies in higher dimensions, in the setting where E; > Σ. Let Σ, Σg be PSD matrices with Σ; > Σ. Then we can rewrite an outlier sample of the form x; = 2 + (0 Σ,) as x; = (#: + (00 E, - Σ)) + (O E), since Σ; Σ is PSD and therefore a valid covariance matrix.
The concept of more structured corruptions in the form of mean shifts has also been studied in the regression setting (Sardy et al., 2001; Gannaz, 2007; McCann & Welsch, 2007; She & Owen, 2011). In this model, it is assumed that y: = 33 x4 + 7s + E., where 7/4 are adversarial mean shifts on top of the standard Gaussian
Mean Shift Models for Other Problems
12

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
additive noise & ~ o
Comparison with Lai et al. (2016) The approach of dimension reduction until a low -iw-dimensional inefficient estimator can be employed has also appeared in previous robust statistics work (L.i et al., 2016), however that similarity is rather superficial and the underlying techniques are significantly different. Each iteration of dimension reduction in Lai et al. (2016) uses the centered second moment matrix to identify sizable "good" subspace (spanned by the bottom eigenvectors) where the empirical mcan achieves ((a) accuracy, and then it iterates on the remaining small subspace. Even in our more relaxed outlier model, the accuracy within the good subspace might be as bad as (?(a), which is insufficient for our purposes since we aim for c-error. Thus our Theorem 1.2 cannot be obtained by the technique of Lai et al. (2016) and we instead we have to look at the non-centered moment matrix after appropriate reweighting, as described in Section 1.2.
We conclude this section with two additional points of comparison.
Connection to Mixture Models The mean-shift model is related to the classical task of parameter learning for mixture models, albeit in regime that is qualitatively different from the one commonly studied. In the canonical setting (see Dasgupta (1999); Arora & Kannan (2001); Achlioptas & McSherry (2005); Kannan et al. (2005) for classic references and (Belkin & Sinha, 2015; Moitra & Valiant, 2010; Charikar et al., 2017; Hopkins & Li, 2018; Kothari et al., 2018; Diakonikolas et al., 2018b; Kong et al., 2020; Diakonikolas et al., 2022; Bakshi al., 2022: Liu & Li, 2022; Diakonikolas et al., 2023) for more recent work), it is typically assumed that there is a small (constant) number of components, &t < n, each with distinct mean. In contrast, in the mean-shift model, all inlier samples come from the same component, while each outlier is drawn from its own component. Consequently, parameter estimation of the outlier means is information-theorse theoretically impossible in the mean-shift model.
Connection to Entangled Mean Estimation Another related contamination model in the context of mean estimation is the heteroskedasticity model. In heteroskedastic mean estimation, each datapoint is drawn independently from potentially different distribution within a (known) family that shares a common mean. Such distributions are also referred to as entangled. For the Gaussian family, this model involves each sample having potentially different covariance (Chierichetti et al., 2014; Pensia et al., 2019a;b; 2021; Xia, 2019; Yuan & Liang. 2020; Liang & Yuan, 2020; Devroye et al., 2023; Compton Valiant, 2024; Diakonikolas et al., 2025). This contamination model can also be viewed as Gaussian mixture model. However, here each sample originates from its own component (k- = N). Importantly, the shared mean assumption enables meaningful results despite the large number of components.
B. Additional Preliminaries
Cover set of the unit sphere For some of our proofs, we will need the following standard facts about cover sets of the unit sphere:
Fact B.1 (see, e.g., Corollary 4.2.13 in Vershynin (2018)). Let & > 0. There exists set C of unit vectors of RRd such that
IC| < (1 + 2/E)d and for every E IRd with ||u|| = it holds mingec lly - u|| S.
Corollary B.2 (see, e.g., Exercise 4.4.3 (b) in Vershynin (2018)). There exists a subset C of the d-dimensional unit ball with |C| < 7d such that ||0||| < 2 maxxccle' T for all x E Rd and ||Allop I 3 maxxec x." for every symmetric A E ddd
We will use the notions of subgaussian and subexponential random variables in the following standard way that we briefly review below.
Subgaussian and subexponential random variables The following three statements are equivalent: (i) the random variable r x- --E[z] is subgaussian with "variance proxy" o² (ii) ||æ Eizille, S a / for all p 2 and (iii) Príiæ Eia|] > t] < /o( The following three are also equivalent: (i) the random variable x E[r] is subexponential with parameter A (ii) || - Eiz]Ile, 2 'd for all p 2 and (iii) Príiæ- - E > t < e- e(t//A)) If XI...., Xx, are zero- mean independent subexponential random variables with parameter X, and X = Eie(o) X,/n then Pr[| 1 S exp(-S(n) min((2/X², (/A)) (Bernstein's inequality).
Fact B.3 (see, e.g., Exercise 2.5.1 in Vershynin (2018)). X ~ N(O, 1) then for any p 2 1, |X|1, (E(I))) ((1+p)/2) 1/p ((12)
2
and thus by Stirling's 's approximation |X l,, & vole.
13

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
Fact B.4 (Matrix Bernstein Inequality; see, e-g., Theorem 5.4.1 in Vershynin (2018)), Let X1:... X N be independent,
mean zero, symmetric random matrices, such that [Xillap I K almost surely for all i. Then, for every t 2 O, we have
N
S 2n exp (-c- min
t2
))
02 K
where o²
E
[[
is the operator norm of the matrix variance of the sum.
op
The following is standard fact regarding concentration of norms for Gaussian vectors (see, c.g., Vershynin (2018) for version of the fact for zero-mean Gaussians). For completeness, we provide proof below.
Fact B.5 (Gaussian Norm Concentration). If ~ N (e, I). with probability 1 - we have that
||-|| 8 (11112 + (1111++d) z log T
+ (vā+ I1ull) v 1088 1
Proof.
Write r = 2 μ for 2 ~ N I) then
|| ull |all - d| = -11=112-d+22 d 2z u ||
+ 2
First, using Bernstein's inequality, we have that
-d/ 11=112- -
log + y dog
with probability at least Also as T N (0, (1al()) it satisfies the Gaussian tails
Pr || 14 o) se 20 10)2)
or equivalently
12 (4] S
||||| V log with probability T.
C. Omitted Proofs from Section 2.1
We restate and prove the following result. Proposition C.1 (Inefficient Estimator). Let d E Z.4 denote the dimension, and be a sufficiently large absolute constant. Let a < 0.49, e > O, and å E (0, 1) be parameters, and μ E Rdd an (unknown) vector. There exists an algorithm that, on input and any set o 2 20/2² (d - (o)) a-corrupted set of points from N I) under the mean-shift model (cf. Definition 1.1), outputs a jı such that 1| - μ4|l S with probability at least - ó. Moreover, runs in time 20(d) poly(n, d).
E Rdd an a-corrupted set of points from N 7) under the model of Definition 1.1 and denote by the the cover set of Corollary B.2. The algorithm the following: First, using the algorithm from Fact 2.2, calculate a m, for each E C such that [m, - v 1u] S e/8 (see next paragraph for more details on this step). Then, output the solution of the following linear program (note that the program always has solution, as is satisfied by 10):
Proof of Proposition 1. Denote by T {
Find ğ Rd s.t. |o p - m < E/A.VEEC.
The claim is that this solution f is indeed close to the target μr, since
|| /i < 2 maxl (o T (μ íi)]
(using Corollary B.2)
#EC
< max (Iv) /1 m. + mm,, - v [
#EC
14

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
2(e//++/44<<3 <e.
We now explain how to obtain the approximations my with the guarantee [my ToT--upp pl] S E/8. Fixing a direction Thus, if we apply algorithm
we
note that v NNv μ. 1) thus {u ) mm from Fact 2.2 with probability of failure 8' = 5/|C), the event [m,, - /a| S s/8 will hold with probability at least 1 - 6 [C]. By union bound, the probability all the events for v E C hold simultancously is at least 1 - 6. The number of samples for this application of Fact 2.2 is 200/e²) log(1/8") 200/e)) log((CI/á) 2001/))) (d log(1/6)).
is set of a-corrupted samples of W/v' ju,
We conclude with the runtime analysis. The runtime to find the m,'sis is [[C) poly(nd)) = 20(4) poly(nd) since for each fixed v E C we need (oly(nd) time to calculate the projection {x, 4} of our dataset onto v and poly(n) time to run the ome-dimensional estimator. The linear program can be solved using the ellipsoid algorithm. Consider the separation oracle that exhaustively checks all 20(d) constraints. We need poly(d) (d) log( ( calls to that separation oracle, where R, r are the radii of the bounding spheres of the feasible region. First, R S e, because we have already shown in (3) that the feasible set belongs in ball of radius around p. Regarding the upper bound r, note that all inside ball of radius E/8 around j feasible since |u' p m,l S |u j v yl| + |0 m.l s ||ū alll + e/8 S e/4. This means that r = e/4. Hence the total runtime for solving the LP is (0(d) poly(d) or simply 20(d)
D. Omitted Proofs from Section 2.2
In this section, we restate and prove Lemmas 2.3, 2.7 and 2.8.
Lemma D.I. Let V C IRd be subspace of R& of dimension k S d. For any E V, we have that 1s12
EgsN(s. [+))( Za,e = =z2 Te pVE12, where Fæ, and Za, are as defined in Equation (1).
Proof. We prove the lemma for V = R which has Ily I. The same proof generalizes arbitrary subspaces. First, for any function f: & - B we have that
1 AVE
1 1 f(z)e
1
1m
E z>N(2.1)
f(x)e
AVE 6 dr
(where z= (/2)
=
Z 3r
Z [ f(z)e
1
1012 11s-2|1 dr
OVE
7 [ (x)e 111011 +1)) +1) 2$ x+11=11)) dr
1
= 2 { f(z)e + 20 ++1l=11) dx
(where c:= 2 AVE
+ 1)
Z / f(x)e
1
[
f(x)e 3110-1111+ =11==1))) dx
Z g*
- -21-
J f(x)e -110-- dx
1+12 8VT12
[ f(x)e- ((x)=-11lz-0 --11=--111" dx
1-12 BVE42 7'
E
[f(x)]
(where Z' (2x) /
Z
1111
b
E
[f(x)]
(where b :==6 JVE+2 (1/c)
2
15

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
Therefore, for f(x) xx (1/c)I, we have that
1 -
1=12
1xl2
E
v. T
e
RVR
E
Ma)e
AVE
= b
E
[fx²]
(z,1)
(=,()
x~ 2.
b
E
-
b
I
c
1
22
-1
c
++
1+ll2
1
b
c
22
e
AVE+2
27
BVR
Lemma D.2. Le E (0, 1) and k E 24 denote the dimension, and assume k is bigger than a sufficiently large constant. There exists sample size n = klog" (1))(11)2++00) from N (H,I) according to Definition 1.1 with the assumption that ||||| = (1). Denote by 21,-.., Zan the adversarial centers in Definition 1.1. Then, with probability at least T is (1), vlog k)-good with respect to μa, 21,... Ron.
such that the following holds: Let T be a set of n o-corrupted points
Proof. We will show that Item 2 and Item I of Definition 2.6 hold. Without loss of generality, we use V = R in Definition 2.6, i.e. our subspace is the entire R We start with Item 2 since it more general. The other will be similar.
Proof of Item 2 We remind the reader that T= {xi........ -[T } is the set are the a-corrupted points and that T S denotes the subset of an outliers with 2; the associated center of x; 2 8. We want to show that the sample average over T \ S matrix À from (1), with / Vlog(k), satisfies e. Au -1 for all unit vectors v. Without loss of generality, instead of the definition of given in (1) we will use the following definition:
Ā
Σ
Ag
where A, = FaM(as)e k/look)) 1()))
(4)
where F3.5 as in Equation (1) and & is defined to be the following good event:
1
1 = (1=:1l² + +x) log _ + (VT++ + llzill) V log
(5)
where : (1/n)*+ The first change in our definition is that we replaced the normalization factor Zz, that appeared in (I) ((evk// log(k)), and using e ev/i log(k)
by the simpler expression evk/ k// log(k), This is because (1 2/( lo(()/) will be more convenient for our calculations later on. Without loss of generality we can use Hy = I as we can all of the statements that we aim to prove are similarity invariant. The second change is that we are using the good event in the definition of À. This is indeed without loss of generality because (i) by Fact B.5 we know that & holds for each sample I; with probability - т, thus by a union bound over all samples we have that all the events & hold simultancously with probability at least nt 2 1 1 1/n > 1 5/8 (for & 2 2), and (ii) using the indicator ((E,) the definition of A shifts the expected value Ā by negligible amount (much smaller than 11) as we show below:
Fa,s(z))eVii //llog////))))/// (kg( 1 - (zx)e /k/ (k/(o)(()) log(R) ((E))
E
3 (
(k)
1x
E
Velog(ts 11 (E,)
V kklg(() +
[k)
3--
E
(0 (0T2;)²
Vilos(e) 1 (Es)
klog(k) +2
((OTTa)
/ /k)g(())
1 27 Vilnget
Pr
E
(using Cauchy-Schward
V (ondd)
(2
/ kllog( (k) +
16

---

Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination
2
klog(k)
k)
Ixcl v (klox(R)
E (owN(ssdd)
(v (uTx;)²
(using Fact B.5 with (1/n)²)
(log(k)) +
2 $ /
(using Claim D.6 applied with V log(k))
(6)
where Claim D.6 that was used above is bound on the reweighted second moment that can be found in Appendix D.1. The
above is considering only single term in the definition of A. By triangle inequality it also follows that E A
A
S n/2,
where A
E
TAST Ei ( V
// log(k) ((E))
We now move to show that v T AA > -1 with high probability. Write x; = 2, + 9i where 9: ~ NN for E T S. We decompose the matrix A, for ; ii E T S into three terms
A: = ((0.5 9:9.
v (lo
)
1-,12-2
(219, + + + 2:24 (k) + +2
e
Vklog(() 1 (E.)
Ti Tai T3
where by TiG, T2: and Tax we denote each of the terms that sum to A; and by Tis; T2: and T3. we denote their corresponding expectations. We will show concentration for each of the terms separately and then combine the results to show that v Au 7
First Term Fix v E R ||a|| = and let i such that x; E T S. We bound the Tp norm of the random variable
T Th - Tis v as follows:
T Thi Tis) v Lp S
I TTie
(by triangle inequality and Jensen's 's inequality)
Lp 12,1 & Valog(A) 1(8))
(oT u0=
(k))
Vklog(k) +
4p
(0TT0)
V /klog(k)
U=:1 Valoo())
+0 (sggt//))(k/r))
1 (Ei)
(1/1)o(1))
/klog(k))
(by Claim D.3)
v kllggk) (k) +
||6TT) v)²) 21
v /klog())
(1/n)o(1)
or bonik/wl vilogiy)
(by Claim D.4)
/klog(k) +2)
Vklog(k)
(1)))((1)
(by Fact B.3 since g. v (O0, 1))
p
V <ll +
Sp. (1/1)((1)
where the third line above uses the definition of the good event & The proof follows by the definition of the events E; and some simple algebra. We include the proofs of both claims in Appendix D.I.
Claim D.3. Let & denote the event from (5). Then,
|
k (k)
|| / klog(k)
|
[<z:l\/o(((/)) log(k/n)
)) (1/m)ot))
exp
1())) S exp
+0
Vklog(k)
17

---

Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination
Claim D.4. Fix a k > 10,0 1
and C > 8. The following inequalities hold:
+ C " ()o(()
for all O. S o² ( v kkngg())
x² (k)
v
(llog(h)
log Viloggh)
log (b)
X C2 VElog klo (1) (1)
a Velog(h)
Vilogth) for all x 0.
lox (+)
2x2 Vilogiy
+o
iil ale
Mogg()
X C*klog(()) log
(+)
Vilogik) for all x > O.
(where Ti denotes the expectation of Tw) is sub-exponential random variable with parameter X = notty, hence from Bernstein's s inequality we have that
As a result of (7), we have that v (7i, Fic-Tih Tis)
(fan ( ))
Σ o. (TT: -Tis) 2 < 2exp (-emin
Pr
am ER
Using the above with n/66, we have that with n 1oR(1/6") +00101 samples we have that with probability at least 1 - 8'
1 Eiz, T. (Tu- Ti v S (1)) Now let C be a cover of the unit ball from
for a fixed vector v holds that an
Corollary B.2. By using 8' = T
82 O(k) and a union bound over C' we have that
sup [e
Σ u ( - Tis) v
10 max #EC
Σ v (T::
-hiz)
Tii)
an
am E
which can be made less than n/6 with probability - 5/8 8 by using n
d8og(1/8) of rll) samples.
P= Third Term For the third term T&p 2 e Vilocte we will use the Matrix Bernstein Inequality (Fact B.4). Recall our notation that T3, denotes the expected value of the random matrix Tyx. First, we have that
Tax
Ta: 1,
2 T3 lrpp
2,24 E
Vilogiks 1 (E.)
op
= -1|2,27
llap"
(E,)
1s,11
1x Toggt//
||
VMlor(h))
v/llo(h))
(1/1)
(using Claim D.3)
< / (k)
(by Claim D.4)
2 Vklog 3/2 (k) log(1/n)(1/)))
< Vklog 3/2 (1))))()))))
where the first inequality follows by the triangle inequality and Jensen's inequality almost surely. Moreover
E
(Tx
Tai
2
<
T
op
12:13
E
||
2,2T
(Alog(k) 1 (E,)
op
'Here have used that without loss of generality a 2(1) since we always treat of the inliers outliers in the model of Definition 1.1
18

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
Iz P Vilogioo
|
|
2,2
E
e
(8:)
op
21
lylnk(//))
< | Velng(k)
Vklog(t)
(1/1))(0)
(using Claim D.3)
of log(k//)) v Vllogley
s klog(k) 1 (k/n))
(1/1))(11)
(by Claim D.4)
Oc lout1/u) Valog(e)
x klog" (A:) log (1/n)e (o92()ne
(1/n)a(1)
s 2llgg(()) (1)
Hence, from Fact B.4, we have that
Pr
1 am
Σ
T3i-
T3i
2t s 2k exp
(-c- min
-c-min
-c-
tan
tan (1)1
kllo (1)))o)))
ES
op
In summary, using n = ((1/n)2to(1klogg (k) log (1/6)), we have that probability least 1 6/8.
1 on
Einery (fst -Tss-Tssll ll, S n/6 with
Second Term For the term T2 we will prove multiplicative bound. Again, fix a direction with ||o|| = 1. We will first show that v T2v is subgaussian by bounding the Lp-norms:
1 Velogees (EE)
00 (T2- - -Tx) u11,, 2 0 T20
(0) uz uutTuve
u)
=
1,
Lp
1=.12
+o [s (s:lly/nggt//))
s | elllpp 1 zile
Veluucks
v (louuhh)
(L/n)o(1) (using Claim D.3)
11,,12 Valneca)
t0
Leclly/uuttk/
vp v 24
v/log(A)
(1/1)(11) (since of U NOO, I))
Hence, it follows that TT (T2- T2i
v are independent subgaussian random variables with proxy standard
10,112
Tigg (klox(k)
deviations o; |uTzi zile
Vilou(())
(1/n)o(1) Thus, the proxy variance O² of the average
(I/on) St TT T2: T2i iis
-2 1 +0 1s, 1oxtte/)) Vilox(k)
0² S (an)2
Σ
(o (T 22
Alogits
(1/1)
i
Σ
(v (oT2))e -1==11 e11zz=
klog())) (1/m)o(1)
(an)2
S (an)²
Σ
(v (TT2)) 2 -1=111
-1l=z11 />/////gg(/))))) +2) (0)(111)))) o())
S 1 LOT Au(1 (()))
1
(for A:= on Ex 21zee Vennst332
where the second line used the following:
|
|| / Vlo((k/))
|
(0
| 112 <klog(k)
-2
+0
+
(log()))
(kl)
(k)
<llo(())
19

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
|
+ +0
(()(())))))
(og)) log(k//)) (/)
V (k)
(using Claim D.4 for last two terms)
|
+0 log(1/n)
vk log
1 an Σ, TT (Tss T2s) v, we have that with probability --8 8' holds
Using the subgaussian tails of the random variable
Te8) ( Σ V. (T (Ta)-TT v S o ooolog(1/8)) S
(v Av) (1/1))(() log(1/8").
(8)
an
Now let C be cover of the unit ball with accuracy Ç = n/k. The size of such a cover is [C] (O(k/n))* (Fact B.1). If we use 8' = (/(8)] and do a union bound over C we have that (8) holds with probability 1 8-8 8/8 for all v E C simultancously. By plugging the aforementioned value for 8', we get that the following holds for all v E C:
Σ v. (T(Ta: - T21) i
S
To Av) (1/)) llg(kk/)) log((1/6)
on
on
(uT Av) (1/n)o()llog(1/))))
an
By using an = O (k((1/))(()) log(1/6)) samples, the above implies that for all E C it holds
1
Σ
v T 2
Σ
v UT
(nn6)/o/ Av.
ERETYS
As result, combining the bounds for the three terms, we have that for every C:
v T
Au
Σ v T-
T2: + Tz))
ii ST
Σ
(Tii + T2i + Tsi) v nn3 (n/6) ATAu Au
aM
ET
E[A]
n/3 - (n/6)VoTAs
2 T Au
6' (n/6) v Av. Av.
(by (6)
From this, it now easily follows that T. Au > n by simple case analysis: If T Av > then
5
T Ao " (n/6)Vo T Ao r. Av
6"
VoT Av
(1 <<< 1)
where the last line uses that T Au Vu Au 2 0 whenever 0. Ar > 1. If on the other hand T. Av then bound
becomes v. Au - (n/6) v Ar 2 v
Au " (n/6) = T Av 77 2 -7,, where we also used that v AAv 2 0 b
1
definition of A = 1 Eiz,erss 2,4 [lxx(k)+2
So far we have shown that T A 2 - for every V E C, where C is a cover of the k-dimensional unit ball with accuracy & = n/k. It is easy to see that this implies that u Au 2 - 4n for all arbitrary u with ||u|] = 1. Consider
an arbitrary unit vector u. There exists E E such that A|l - ull S i.e. u w, with [|]]]] S E. Thus
20

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
u Au v Au v Aw w Av w Aw -1 To Aw ww |wl| 5 n/k, |ua Awl z || 7) and |wo T Aw S n S 1/-
Aul
|wo Avcl. Since || s
v /klog(k) and
The total probability of failure for Item 2 is 5/2 by the union bound as the proof relies on 4 events with probability of failure 6/8.
Proof of Item
We will use a similar argument as in Item 2. Let & be the same as in (5). First, we will use
Ā
Σ
A
where A, (3, loR(k) 1
SS]
ES
The points T2 E are all drawn from the same Gaussian component (i, 1). Fix v E RF: |||||| = 1. We bound the Lp
norm the random variable T. (A: - E[AJ) v for : my e as follows:
T A E[Ai)
(9)
4p
x 1 T Aiu 1.
(by triangle inequality and Jensen's inequality)
(z) v) 2
klog(k)
1= & Viloa( 1(E))
/llg(( (k) +
1 lel (lux(k//)) Vilgges
(r.Tu) u)
[kl
1n12 VMlglaj
+0
(1/1)0(1)
(by Claim D.3)
V /klo((k) k) +
(MT v + 9i)
(klog(k)
e
lul2 Vilox(k)
+0
Lel /lggit/n)
(1/n)o(1)
(x, = gb + 1 for gi ~ N(0, 1))
1.
v klog(A k)) +
(n (uTv)² 2 + +119?
v (klog(k)
e
lul2 Vklogikj
+o
lel (eggtern
Vklogik)
(1/1))(1)
klog(k) +2
/ klog(()) (k)
1all
(Illi/Tog(b/n)) VElnglE)
I| + p+
e
(1/1))(1)
(by Fact B.3)
klog(k) +
2 e Valogik)
Inll
+0
(ally/ww
/klog(k)
(1/1))(1)
$ {P(1/))(1)
(|dl = 0(1))
Hence, by cover argument identical to the one that we used when treating the first term in Item 2, we have that with
O
k log (1/6)
have that A E[A]|
< n/2 and hence | A 111.p Sn n with probability at least 5/2 where
of Tod))
1
A ppte VRlng(A]+2
Proof of Item 3 Let À the sample average matrix from (1) over the whole sample set T with 3 = 1, we will show that tr(A)= < 18 / (k). In fact, we will show that this holds with probability 1.
v Alog(A) k))
1-,12 Visogin (1 2/ (k)g(k)) k/2+2
(r(A)
Σ +E(n)
||a0||12
k
e
/klog(k)
/ klog(k) (k)
10
Σ
||
VilnglN e kk/log(k)) (1 1 2/ klog(k))) 1/242
e
72
Vklog(k)
TE(m)
21

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
We will show that each term in that sum individually is at most /klo(()). This will follow by two facts: (i)
have that e (k/log(k) (1 2/ /klog()))//2222 < for all k 2 10, and (ii) it is true that (I|ar 1 ko /klog(k)/(( +
(klog(k)
{log())))) (Mloo(()) I 3 klog(k), which we will show in what follows. Let y |2,|| klog(() +2+
k. We have that
||aza||
(kl v Alog(kk) +
1 V/Klou(K) = ye Vilouth) v 1
2VE
k
2. v klog(k)
ev klog(k)
S 3v <kloogk),
where the first step is a re-writing, the second step uses that SUPYER ye Vklug(k)
1 v /klog(k)/e and the last step uses that
2vR < 2 for all >> 10.
2+ (Hog())(
The result follows by union bound over over all three conditions.
Lemma D.5. Let T be a set of n o-corrupted set of points from N(,, T) according to Definition 1.1 for some p with 20/2 for sufficiently large absolute constant C, where k 2 1/e² and Denote by 21..... Zan the adversarial points used Definition 1.1. Then, with probability at least 5, T (1), c)-ood with respect μr -1,.... Zon-
||||| O(1). Assume
Proof. Let S be the subset of the samples that correspond to inliers and T \ S the subset corresponding to outliers. We want to establish the two conditions of Definition 2.6. We prove each one separately:
Proof of Item 2 Let A = 1 Ei A., where A, as defined in Equation (1) for 3 = e, also let A E[A]] Now define the matrix A = Ā A. We will show that for each element A.j. with high probability 1 - 5 it holds |Aayl - n//k which will allow us to conclude that ||||F
Σ iy 2 S v /12 n, which in its turn will imply the desired
|| < || ||F n-
Fix s, t E [k] and denote by e, the i-th element of the standard basis of IR By Lemma 2.3 we have that E[Aud] = and by Claim D.6 (applied with = e), we have that
e/22
Var[Ast] S (an)2 tareTT
Varle, (A: A)ed x
an
Thus, by Chebyshev's inequality, with probability least 1 7, we have that
A S V Var Aat
es/ek an
The right hand side becomes less than n/tk when = 0 (
et/e)) Finally, we can assume a = 2(1) without loss of generality, by simply treating some of inlier points as outliers in Definition 2.6.
Now, in order do union bound over all pairs (s, l). for [K]. L E [K], we will use T for the failure probability.
This brings the final sample complexity O 2
Proof of Item
The proof of this is a special case of the proof of Item 2 where all the 2, 's are the same and equal to μ..
22

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
Proof of Item Let Á the sample average matrix from (1) over the whole sample set T with 3 e, will show that (r) I 2ev with probability 1 - 6. From Item I and Item 2 we have proved that [ - A where
A 1 Σ SiN,eT, ET, 22,e les rVE+2 Consequently,
A) tr(A)+ +r(A))tr(AA A) + A|l= Sevk+ + vin S 2eVk.
where the last inequality uses that S e.
D.1. Proof of Supporting Claims
We restate and prove the following claims that were used in the previous section.
Claim D.6. Assume k > 1/8². Consider the random k x k matrix Ag == Za, Faa( with NN, Tx) is k-dimensional normal, and Zz Fa, as defined in Equation (1). For any two unit vectors v, u, it holds Varlu" T Agu) 2 e4/8 3²k.
Proof. For the random variable Y -. A'Au we have that
2"
Bvk
1n11
االستي dr
E E| =
(0 r) x)
e
e
(for = (22)
Z'
2 Bvk
Rd
2P
(0 x) T 2)
BvK
P
(avx avt
+1) 2x ut (+ll) dx
2' RR
2 Bvk
2h
(0 x) 2)
Byk
1P
+|| P- - Fe'+++lle #+ dx
(for
2p 3VR
+ 1)
2 RR
2 3VK
SP
/
(v (1 x)
BVK
P
601 -000==-u11++C
dx
7' RR
2+ 3Vk
Ze 111 !
3/k v²
p
(v (oTx)(uaa)
c 2- bull dx
Z'
RR
2 3VK
Z 201 Illl
z"
BVT.
E
(u (T)z((uTa)
+ BVK -
(for Z" = (2/ 4/2
Z'
20 201 I|ll
Zee
BVK
24 )a/2
E
(u x1 xx)
2+ 3/K 11 u
Byk
For = 2, this becomes
2
(1 + 2 k+4
2+3V8
BVK TT
1
BVk
E
(u 2vTx)(u x)
(1 + 4/ (B
2 BVk
4/32
41
2
E
(U [u)
BVK T ' 2 3
(explained below)
A/52 4+8VE
2
E
(uuT)(uTa)) 2²)
1/K To u2/
(using (a + b)2
3)255 < 2a. + 22b)
2 3VK
A/32
2
[((TTx)(uT x011
BVk
4+avE
E
2 3Vk)
4182
41
2
E
[|(o (((TT))(aTT x x bz TaTx))) +1
(u=av+bz for zLv, a==u U,
23

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
alu
e
4+2UT
E (a"(v") T x)* + 2ab(o T (= x) + b ())((
2lu12
=61 e 4t0VA
(a" E[a²)
+ 2ab
El
E
[
+ 1
E(a
1) (x ~ W u, :) and ~ = ()
2 A188
2|u12
||
||al
+ 1
++RVE
+
+
+1
ct
c
e²
(using |a| - 1,11 s 1 and E By- = 22 + 62200 + +300)
S S1 stove (Ilall* + 1)
21w12
(using
2p
+ +12 1)
Ovk
S A18 8²k.
(using the fact sup x² 8ec00"/ /1 S 7²)
We now explain the second step above, which claims that (1+ + AVE )²x)/++1(0
/(1 +
SVR ) S e418"; First note that since
A 1/B² we have that (1+ )² I 3 (1), thus it suffices to prove that (1+ 3² /1+ 2²22 S 4//8" Towards
this end. we will use the fact that ex I (1 + x/n)"*'//)))) +/2 for all x, n 0. Applying this with n = k/2 and x 2/k/B, we have that
$
xx
4
S
1
Bvb
Rearranging, this gives that
(1+
4
k/2
(1+
4 3vk
2 C
(10)
BVK
Finally, using that, we obtain:
1 +
2
(1+
Vk/B
1 1
k
e//3 [1
2
k
BVK
I
BVk)
BVK)
<
BVK
6
2.
2.
S 4133
k/2
2
2
e
BVK
Claim D.7. Let E, denote the event from (5), Then,
||,.||2 k kkog(k:))
||2:|| (11la11? +0
[l=illVTog((</g
)) (1/m)or)) /klog(k)
exp
((E)) I cxp
Vklog(k)
Proof. Let r == 1/n², then, by the definition of the event E, in (5):
- 1| + (log) + (vr + 12sl) v Vlg(1/T))
||r,1|2 - A (ko
exp
I(E)) exp
Vklog(k)
||
log(1/7)
Mog(1/r)
|| / [lo(1/T))
< cxp
kk)
kk)
v Vlog(k)
v klog(k)
|
log(k/n)
v /lg(k//)
I log(k/n)
S exp
[k)
/klog(k)
Vlg(k)
/ (k)g((k)
|
log(k) + log(1/n)
Vlog(k/n)
| 1zlll/ooo Ilo(k/n)
< exp
+
Ak)
/ /klog(k)
/log(k)
(klo(())
24

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
|
log(1/n)
log(k/n)
| log(k/n)
S exp
v (k)
(klog())
Vlog(k)
klog(k)
||:||2
log(1/n)
2 Vlog(k/n)
exxp
v Iog(1/n)
(k)
kkog(k)
klog(k)
|2:1|
|| v Vlog(k/n)
I exp
(1/1))(1)
kkog((k) k)
(klog(k)
In the above, we first used that = (1/n)0(1) ((1)) and n (k/n)) then we used that log(k)/VR = o(1). We have also used that eV eV Iog(1/n) (1/m)o(1) and e velogg (1/n)o(U,
(os()/m)
Claim D.8. Fix a k > 10,0 < < and C' > 8. The following inequalities hold:
(
( v (k)
i.
2² (R)
C
C²
for all O.
(Mgg(k)
+0 Jux Velogah))
(k)
i.. x²e Viluglk)
C Vklog k log
Viluatt) for all >> 0.
ii.. a'e Vklog(t)
2x2
+0
Iv Ligit//n
(klog(k)
(kolog(k) log" (+)
(kloxik) for all x > 0.
lox (
Proof. We prove each item in turn.
c (o)())
Proof ofi Let f(x) (llgg(k) v klog(()
lim f() and f(0) and continuous on (0, +0o)
we have that the maximum must occur on a point in (0, +oo) where the derivative is 0 either it is upper bounded than 0. Also
f'(x) =0
h:
-
log
2
Thus, as f((x) C² log(#) T Vklog(k) we get the result.
lox Molk(k
As lim f(x) = 0 and f(0) = 0 and f continuous on (0, +o0), we have that the maximum must occur on point in (0, +00) where the derivative is 0. We have
Proof of ii Let fz) _²e
Vilox(k)
(xx
2 log (
Lox
2x
('(x) = 2xe Vkluacky
+ C
v Vlekte
klog(k)
V (k)
so solving for x > 0 we get == (+(C//looo log (+) + v 1 kkog(k) + C log
Hence, it suffices to compute
C log () ()++ +
c log ()) + 16 /klog(k))
4
25

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
C lox (t)
Cy lox ($)
( C² lox ()
1
c log
+
16 1 klog(k) + C2 log
k
16
1
log
S CC²
C² V (logg() (oogg log
v (illauth)
(///kk/m)) VkloR(k)
30 lox (+) villou(k))
Hence, e
Vhlug(o
S C² (k) log
Proof of iii
Similarly to the previous inequality, let
f(x) = = Velogae +0 (yhoe(()) (+)
VMlug(A)
As -ime f(x) = -c and f(0) = 0 and f continuous on (0, +00), we have that the maximum must occur on a point in (0, +00) where the derivative is either it is upper bounded than 0. Also, we have that
(x)
log (+) 2
2x
V
3 Velug(a)
"V lox
4x
+C
=0
v (k)
(k)
k
CV log
+
64v 1/6//4//o ///loook))//)) + C2 log
(for x > 0)
Moreover,
A: (7)
kt
(1/10n log
+ 64 (k)z(()))) + C2 log
lox (#) Viclozik)
1:
aa
2 C Cokllogok))ll log²
17
E. Full Proof of Theorem 1.2
We now combine everything to prove the main theorem, which we restate below:
Theorem 1.2. (Main Algorithmic Result) Let d E4 denote the dimension, Rd be unknown mean vector, (0, 1) be an accuracy parameter, and or < 0.49 be a contamination purameter. There exists algorithm that takes as inpul e, draws n = + + 200122) a-corrupted samples from N(p,, 1) under the mean-shift model (Definition 1.1), runs in poly (n, d) time, and outputs Ti such that with probability at least 0.99 holds [] pall S
Proof. The main while loop of the algorithm maintains a subspace V; whose dimension, denoted by k in the pseudocode, starts from and can only decrease from round the next one. We will examine two distinct "phases" (or parts) of this while loop: Phase will refer all the iterations during which (d)g'
k S d, and phase 2 will refer to all the iterations with 1/e² < k < C' log e5. The algorithm and the analysis will be slightly different for each phase. Regarding notation, let us denote by Ti the number of rounds of phase and by T2 the number of rounds of phase 2 (i.c., phase consists of all the iterations for f = I,... Tii and phase 2 consists of the iterations for f = Ti + 1,...,, Ti + T2). The proof correctness relies on the following claims regarding each part of the algorithm. We first state the claims, we then show how we can prove the theorem using the claims, and we finally prove each claim individually.
26

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
1. Warm start: If Mu denotes the estimator from line of the algorithm, it holds 1|ão -all Q(1) with probability 0.999.
2. Phase 1 (Cllgg(d)/e < k S d):
(a) Let & for E 2,, be the event that the set Tr from line 1, after the transformation of line (At: (/log(())-ggo)
(cf. Definition 2.6) with respect to júg, 2(*) ,...,,."" 26. 2/(()
where 7/s is the parameter set in line 1, jo Projy, (M (u) and =(() ..... e(t) are some vectors in V4- Then, with probability at least 0.999, the events & for = 0, ..... log d are all true.
(b) Assuming & hold for t ... Ti. Phase terminates after at most Tj I log iterations.
(c) Let C' be sufficiently large absolute constant. Denote by V++1 the same subspace as in line 1 of the algorithm and by V441 its orthogonal complement. During the t-th iteration of the while loop, when the execution reaches line 1, it holds [|Projи;, (Ro - -i)l S CE TTs, where Ny is the value set in line 1.
3. Phase 2 21/e2 < Cllog
(a) Let E be the event that the set Tr from line 1, after the transformation of line is (7). c)-good (cf. Definition 2.6) with respect to ir, z(t) ..... =(t) where de is the parameter set in I, j Proiv, (n (0) and o ..... <(t) are some vectors in V, Then, with probability at least 0.999, the events E for t = Ti + +..... Ti + 100 log(lo(d))/e are all true.
(b) Assuming the events E from above hold, in every iteration of Phase 2 the dimension gets halved. As a corollary, the number of iterations of Phase 2 (i.e., number of iterations for which 1/e² S k S (loo"(d)/e) is
T2 100lo(log(dd)/))
(c) Let C' be a sufficiently large absolute constant. Denote by V++1 the same subspace as in line of the algorithm and by V its orthogonal complement. Assume that the events & for t E [fmax] are all true. Then, the following holds for any / E [m During the 1-th iteration of the while loop, when the execution reaches line 1, holds [|roovv, (Ro - p)ll S Er /nr, where Tee are the values set lines I and
4. Estimator for remaining subspace: With probability at least 0.999, the lines 1-1 of the algorithm find a vector Pa E V. such that [ - Projy, (1)] S.
We now show how given the claims above it follows that, with probability at least 0.99, the output of the algorithm p = Po + دr satisfies | Aa|l S Without loss of generality, it suffices to show 11 - اlر O(c) as, if this is true, then one can also obtain error exactly e by running the algorithm with ee in place of e, for e being a sufficiently small constant. Let = Ti + T2, so that V. denotes the subspace after exiting the while loop. By decomposing the true mean into the projections onto the two orthogonal subspaces we have that p = Projvy (1)) + Projy, (n): By the Pythagorean theorem:
A 111 |roiiyy (No pu) + Projy, (fr - wn)l²
|Proivy (No n)) + ||Projy, (fr -n)l1
The last term is Proojv (Pi - S c by Item 4. It suffices to bound the first term. Towards this end, denote D == C Clog" (d)/&², which is the dimension during the first iteration of phase 2. Item 2c for 1 Ti + Ta (which according notation denotes the last iteration of Phase 2) yields the following (we explain the derivations below):
T T
Projyy (No - w||l
Σ
Vie
(11)
1=1
Ti Ti+T2
<
VTe
+
Σ
Vne
(12)
1=1
U==+++1
Ti+T2
E
T
Vie
(13)
log d
M=
27

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
+ T2
S 6
The
(Ti S log d by Item 2b)
P=I++1
366
366
36c
VD
+
V
DD22
+
11/22
(14)
6VC
S 6 +
2:/4
(15)
D1/4
t=
GVE
Set
(16)
(21/4 1)D1/4
6VE
=e+ -1/4-1)D1/ (De2) SE.
(17)
We proceed to explain the steps above: (14) uses the definition of 1): := 36e/ / The dimension & for the first round of Phase is D and in every subsequent round gets divided by 2 (by the claim of Item 3b). Phase 2 ends when the dimension becomes 1/e², which corresponds the last term in the series. (15) is a rewriting. The summation goes from 0 to lg( (D²)) because Ig( De²) is the solution to the equation D/2" 1/e² which seeks to determine after how many rounds of halving the dimension becomes 1/c². The next line, (16) uses the closed form formula for that series.
We now prove all the individual claims.
Proof of Item This holds with probability at least 0.999 by an application of Corollary 2.12 in Diakonikolas & Kane (2023). Without loss of generality, we apply this corollary with the fraction of outliers being a = (2(1) since we can always treat some of the inliers as outliers in the model of Definition 1.1. That corollary yields that ni (()) samples suffice.
Proof of Item 2b We claim that each iteration of Phase 1 of the while loop decreases the dimension from i to k' == (BB/llo(k)) This is because ε, hold for i = 1, 1,...,4, 4, and Item 3 of Definition 1.1 states that (r(A) < 18 1 (k). This means that in line 1 of the algorithm, the number of eigenvectors with eigenvalue greater than can be at most tr( S 18 /klooog()))//
The dimension thus gets divided by 2 whenever 18 /loo(g))// < k/2.. By plugging in the value n == (e/ log d)² we obtain that the dimension gets halved whenever & 36² (d)/ct This indeed holds because of line 1. Hence the number of iterations is at most log(d).
Proof of Item 2a During the 1-th round of our algorithm let 2 denote the outlier centers that the adversary chooses for the samples, in the model of Definition 1.1. Note that performing the mean shift ã; = x; 7.o. means that the shifted points ū; effectively come from the model described in Definition 1.1 with shifted mean jú = ti and shifted outlier centers
(t) Pog Similarly, the projection operation of line 1 makes the points essentially come from model that uses mean jt, Proiv, (wo).
(()) 2
Now by a union bound over all of the log d iterations of Phase and Lemma 2.7 with n = 7t- (e/ d)g and 5 10-3/ log d, we have that all of the sets T. of points drawn line will be (N.- / (log(()))goo
with probability at least 0.999. Note that the condition ||ū.]| 5 ||и ño (11) that this lemma requires has already been established in Item 1, thus the lemma is indeed applicable. The sample complexity that this lemma yields is k log" k(1/))2ta(1)/ /8. By using ? 77 (c/ log 2)2 and 8 = 10-3/ log d this becomes k(log(d)/ (c)/ which is smaller than the number of samples n- that we use in our algorithm (cf. line 1).
Proof of Item 2c Proof by induction. Denote by C' the constant in the statement of Lemma 2.9. The base case f = 1 follows immediately by Lemma 2.9 applied with 24 Rdd and V Vt. For the induction step, assume that the claim
28

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
holds for l and we will show it for + Let V4+1 denote the subspace maintained by the algorithm at the end of (line 1) the t-th iteration. By inductive hypothesis, we know that ||Projy4,, (To p)ll - C vtr. The goal is show the bound for the end of the next iteration, i.e., show that [|Provya (Po ا1] - - Vr. We split Vi42 into two parts: 24 n V4+1 and 2 n 1++1- We now apply Lemma 2.9 with U V4+1, 3 = Vlog(d) and V VV42 O Ve+1- The lemma is indeed applicable because the set T, of points are (M. -log(k))goodd The application of the lemma yields that ||Pooyyaaaus (To - ,I)ll & CVTI+II Also, the inductive hypothesis that we mentioned earlier implies that [|Projy M/44 (To --)l= S C CE vrr. Combining the previous two we have that [Prooy, -800)]l: & CE VTr
Proof of Item 3a This follows by an application of Lemma 2.8 with probability of failure ö = 100 (oo(///ggg))) (d)/ Note that the requirement of that lemma that k > 1/e² holds since the algorithm would exit entirely the while loop of line I otherwise. Since the dimension is k S Colog' (d)/e& during this phase of the algorithm, and 7 = O (k)/ the sample & 20(1/²) mentioned in that lemma is overall 20(1/²)) polylog(d) By union bound over the iterations of the algorithm, we have that all the sets T, during the first 100 (oog)gdd)/f rounds of Phase 2 will be (Ne, e)-ood (and as we will show below, Phase 2 will not have more than 100 log(log (d)/c) /m)y rounds).
complexity n लहा
Proof of Item 3b Consider single iteration of Phase 2 of the algorithm, and let A, be the matrix from line 1. Since the set of points on which A, is computed is (Me, -)ggod, we have that tr (A) is at most 1 (cf. Item 3 of Definition 2.6). If k denotes the number of eigenvalues larger than T) then we have k' S 18E//// K/ne. ne. Note that, by definition of Th == 36e/ / Vk,
18c V
18c 18C/
S k/2.
36E
The dimension in each round is therefore being halved.
Proof of Item 3c This follows by the same argument we used for Phase 1, but applying Lemma 2.9 with B = insteed of Vlog K.
Proof of Item 4 This follows by an application of Proposition 2.1.
Runtime and Sample Complexity of Algorithm 1 that we denote by Ti the number of iterations of the first phase of the while loop (interactions for which Clog"(d)/e" < S d) and by T2 the number of the remaining iterations of the while loop. The sample complexity of the algorithm is the following:
Let no, A1, n2 be as defined in line Algorithm of the algorithm. Recall
n = no + m1 Ti + n2 (T2 + 1)
= O(d) + d dpolylog(d) + 201/)²) polylog(d) 2+0(1)
dpolylog(d) (2+a(1)
+ 20(1/2) polylog(d).
Regarding runtime: The runtime of the warm-start step is = (noy( The runtime of the while-loop part of the algorithm is T22 = (nly()nd) because each iteration runs in polynomial time and we have at most T₃ + T2 = O(lo d) iterations. The runtime of the last step of the algorithm (1) T3- = 20(k) poly(nzd), where = 1/e2 here denotes the dimension of the subspace V; for Ti + T2, i.e., the dimension that we end up after the while loop finishes. Since n2 = 20(1/²), that runtime is overall 73 = poly(nzd). Thus, the overall runtime of the algorithm is polynomial in the size of the input.
29

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
F. Higher Breakdown Point and Adaptivity
In this section, we use Lepskiï's method (Lepskii, 1991; Birgé, 2001) to prove Theorem F.1 (stated below), a generalization of Theorem 1.2 which provides similar guarantees as Theorem 1.2 but works for any contamination parameter a, and does not require priori knowledge of a. Specifically, we can generalize the algorithm to work for a E (0, 1/2 - c) for any e < 1/2, which is unknown to the algorithm. The price that we pay for that is a slightly larger dependence on in the sample complexity and the fact that the error becomes Oc(c) instead of c, where the O2 notation hides factors that depend on (i.e., if is constant, the error increases only by constant factor). Moreover, even in one dimension, Kotekal & Gao (2025) has shown that consistent estimation with arbitrarily small error e using the information theoretic optimal of (011c2) samples is only possible when e >>> 2 2-6(1/e), thus we only consider that regime in this section.
Theorem F.I. (Higher breakdown point) Let d E+ denote the dimension, μ E Id be an unknown mean vector, E (0,1) be an accuracy parameter. Fix n (d (1/c)C + +201e) )og (d), for a sufficiently large constant C. Suppose that we have sample access to a-corrupted samples from N(s, 1) under the mean-shift model (Defimition 1.1) with contamination parameter a E (0, 1/2 - c) where 2-1/(2e) < c S 1/2. There exists an algorithm that takes as input e, draws n samples, runs in poly(n, (n, d) time, and outputs P such that with probability at least 0.99 it holds || pll S O,(c).
The first step towards proving Theorem F.1 is to show that there exists an estimator that, having as input achieves error (,),, i.e., an estimator that requires knowledge of 7 but 7y can be arbitrary. We show this in Claim F.2. Then, we can use Lepskii's method to obtain an estimator with the same error, but without knowledge of 7--
Claim F22 Let E z_ denote the dimension, μ Rd be an unknown mean vector and e E (0.1) be an accuracy parameter. Let be contamination parameter. There exists algorithm that takes as input c, a, draws 20(1/²) 18) a-corrupted samples from N(u, T) under the mean-shift model (Definition 1.1), runs in poly(n, d) time, and outputs Ji such that, a S 1/2 2 2-1/(26), then with probability at least 1 - 5 it holds 1 - μ4| S (01((1-20)))
O(d/ ((dd(622+0()) +
Proof. For notational convenience, instead of working with the contamination parameter a from Definition 1.1, we will use 1
the reparameterization 7 = 1-2n We now describe the modifications that we need to do to Algorithm 1 and its analysis in order to obtain Claim F.2
First, we replace the rough estimation step of line I in Algorithm I with an estimator that takes a in its input and achieves error O(r) instead of an (1) (e.g., Dalalyan & Minasyan (2022), Exercise 2.10 Diakonikolas & Kane (2023)).
This change affects the error given by the analysis of the dimensionality reduction, Lemma 2.9. It is easy to see that the conclusion of that lemma will now become ||Proju (H)) O(e** VT) instead of [|Proju(()) O(e VT). This is because in the last line of the proof of Lemma 2.9 we have that for any u such that T. Au S
Lolf (TTn)² S 2meovers S Se²2 n
As result, we have that [|Proje())) ((2)) vn for U the subspace of V2 such that T Au S 1n for all unit vectors V E U. So propagating this change in the analysis of Algorithm I in Appendix E we get the e07?) error will appear as the contribution to the error by the subspace V,+
For the error on the orthogonal subspace, we need to calculate the error that our inefficient estimator in the final step of our algorithm will attain. Note that from Kotekal & Gao (2025) we have that when using 20(1/e2) samples the one dimensional estimator achieves error Vlog(L+2-01<)//>) S Olr")) when 7 < 2 21/(22)/2 1/2. As a result, a more refined
version of Proposition 2.1 exists error f is ||ā Mlll S 0 with probability 0.99.
Finally, although our analysis in Theorem 1.2 provides result that holds with a constant probability, this was done only for simplicity. It is easy to verify that because the conclusion of Lemmas 2.7 and 2.8 holds with probability 1 with 1/8 blowup in the sample complexity, we can follow the analysis done in Appendix to obtain a high probability conclusion for the final error of the algorithm.
30

---

Efficient Multivariate Robust Mean Estimation Under Mcan-Shift Contamination
Now will Claim F.2 along with Lepskii's method get an error guarantee that depends the true parameter 7 without it being known the algorithm. We state Lepskii's method guarantee below and then prove Theorem F.1.
decreasing r I + RR. Suppose Alg(n') is black-box algorithm that is guaranteed to return vector Ii such that 1|ū S r(r'), with probability at least 1 1-8, whenever 2 n. Then, there exists algorithm that returns Dí such that, with probability at least 1 - O(lg ((log(B/A)) it holds 11 2l12 - 3r(2)). Moreover, this algorithm calls Alg at most O(log( B/ A)) times.
Fact F.3 (Lepskii's Method), Let μ E RR A, O, y E [A, B), and
Proof of Theorem F.I. We will apply Lepskii's method (cf. Fact F.3), while using the algorithm of Claim F.2 with å 0.01e²/ log(d) for Alg and r(n) == cc. By assumption a S 1/2 1/v/ (and 2 1/n otherwise can treat of the samples as outlier make it at least 1/n) thus y will belong in the interval [n/(n 2), vn/2) thus Lepskii's method will search over the interval [A, B] where A = n - 2) and B = vn.22.
Now if we use the algorithm from Claim F.2 for this fixed n in Lepskii's method the number of calls to our algorithm - 2))) < log(vn) I log(d200/e)) < log(d)/E² (this is why we used Claim F.2 with 5 = 0.01c2/ log(d) in the beginning). Hence by the union bound, the probability of failure of any call of the algorithm in Lepskiï's s method is at most log(d)/ 28 & 0.01. Therefore, by Fact F.3, we obtain that there exists an algorithm that returns an estimate ÿi' such that 1 2اl I 3r (2 I elr2) c (c) with probability at least 0.99.
will be at most log(vn/
Regarding the sample complexity our algorithm, as at each call we use the same number of samples n and the number of such calls is at most log(d)/e², we have that the total number of samples is at most (log(d)/e))n I (oly((())/)) + 2001/3).. Furthermore, the runtime of the algorithm is (log(d)/e² /²) poly(n, d) poly(n, d), as Lepskii's 'ss method consists of log(d)/e calls to the algorithm of Claim F.2.
31


Reviews:
[{"review_id": "rUuL9lB3fO", "reviewer": "Reviewer_oS19", "summary": "This work studies a relaxed model of robust mean estimation of a spherical Gaussian with identity covariance, where the adversarial points do not follow arbitrary distribution Q, but are sampled from $\\mathcal{N}(z_i, I)$, where $z_i$ is an arbitrary point. Authors show that in such model consistent estimation is possible, and provide a computationally efficient algorithm for high-dimensional robust mean estimation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time, effort and their clarifying questions. We comment on the points mentioned and respond to the reviewers questions below:\n\n(**Identity covariance**) As pointed out by the reviewer, our algorithm works under the assumption that the covariance of the inliers is known. Please note that our algorithm does not require the covariance to be exactly equal to the identity; it is sufficient for the covariance to be *known*. (As pointed out in lines 85-88, for known covariance, by applying an appropriate transformation to the samples, we can reduce the problem to the identity covariance case.) We study the known covariance case, as it is the most fundamental setting for which we demonstrate the main conceptual point of the paper, which is an examination of how more structured adversaries in robust statistics can alter the statistical and computational landscape of estimation. As discussed in Section 3, extending our algorithmic result to the case of unknown covariance is an interesting problem for future work. There are several nuances in defining the problem for the unknown covariance case. For the sake of space, we point the reviewer to lines 629-654 for a thorough discussion. \n\n(**Dependence on alpha**). We discuss the two relevant points below:\n* (*Dependence in the main theorem*). The result in Theorem 1.2 holds for any $\\alpha < 0.49$ (where $0.49$ can be replaced by any constant near $1/2$, as shown in Appendix F). The main conceptual point of the theorem is that even when nearly half of the samples are outliers, the algorithm efficiently achieves any *desired* error $\\epsilon$ with the stated sample complexity of roughly $d/\\epsilon^{2 + o(1)} + 2^{O(1/\\epsilon^2)}$. This sample complexity is tight in this setting. Any prior algorithm would either require exponential runtime or incur a significantly larger error of $\\Omega(1)$ (see lines 72-80 of the paper where this is explained), whereas our result allows for arbitrarily small error. Regarding other regimes for $\\alpha$, prior work on one dimension (Kotekal & Gao (2025)) has fully specified the sample complexity as both a function of $\\alpha$ and $\\epsilon$. It would be interesting to investigate the exact dependence in high-dimensions. However, as with most prior work on robust statistics, the most interesting regime is to obtain a result for when the fraction of outliers $\\alpha$ is a positive constant. This is because this is the hardest scenario for estimation (with the smallest amount of information about the target mean).\n* (*Special cases for $\\alpha$*). Formally speaking, setting $\\alpha = \\epsilon$ is insufficient to obtain error $\\epsilon$ using a Huber robust estimator, as any estimator for the Huber model incurs an error of at least $C\\epsilon$ for some constant $C > 1$ (as established in the robust statistics literature). Ignoring this nuance regarding absolute constants, the regime $\\alpha = \\Theta(\\epsilon)$ (and even more so $\\alpha = 0$) corresponds to special cases where existing algorithms can be directly applied to achieve error $O(\\epsilon)$—specifically, any algorithm designed for Huber contamination or the sample mean setting, respectively. Thus, these cases are orthogonal to our work as they are special cases that can be handled by existing algorithms. As mentioned earlier, the main question we focus on is obtaining a result for the case when $\\epsilon \\ll \\alpha$, i.e., we aim to estimate with error significantly smaller than the fraction of outliers. This is an objective that was impossible to achieve with algorithms designed for the Huber model, and our algorithmic result for constant fraction of outliers has tight sample complexity.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Not applicable", "relation_to_broader_scientific_literature": "This work extends the literature on robust mean estimation, studies a high-dimensional setting of the mean-shift contamination. This is the first result which looks at the computationally efficient algorithms for such contamination model.", "essential_references_not_discussed": "No to the best of my knowledge.", "other_strengths_and_weaknesses": "Strengths: studies an interesting setting of robust mean estimation where consistent estimators exist. Proposes a computationally efficient algorithm for the case where inlier samples follow $\\mathcal{N}(\\mu, I)$.\n\nWeaknesses: \n1. The work only covers identity covariance case. \n2. The dependancy on the corruption rate $\\alpha$ does not appear in the main result.", "other_comments_or_suggestions": "I suggest adding more details on why the $2^{O(1 / \\varepsilon^2)}$ term is necessary in the sample complexity. I do not think it is true in general (see Questions).", "questions_for_authors": "It seems that the work implicitly assumes that $\\alpha = \\Omega(1)$?\nWhat happens when $\\alpha = 0$ or $\\alpha = \\varepsilon$? \nIn both cases there exists much more sample efficient algorithms then what is provided by the 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": "Lx4YSlVn0X", "reviewer": "Reviewer_BKkQ", "summary": "This paper continues the recent line of work in robust mean estimation in high dimensions, with focus on getting arbitrary small (eps) error in the mean despite an alpha-fraction (for alpha in [0, 0.49]) of outliers.  The more commonly studied Huber model for outliers contamination can only achieve O(alpha) error, so this method has more requirements:\n  - the inliers are of form N(mu, I) [this is very common], and outliers x_i of form N(z_i, I),  notably with same covariance as inliers\n  - the n = Omega(2^O(1/eps^2)) samples are required\n\nThe fact the outliers have the same covariance is outliers seems like a mild assumption, and could maybe be relaxed more; this seems mostly to show that outliers are full rank and their covariance is psd.  But the form considered is natural.  \nThe size of the samples is a large increase from Theta(d / eps^2) for robust methods that obtain O(alpha) error (with eps <= alpha).  But the 2^Omega(1/eps^2) appears necessary (from Kotekal+Gao 2025) for even d=1.  \n\nMoreover this second point allows that if we can reduce the problem to k=1/eps^2 dimensions, then we can net the space of directions (with 2^O(1/eps^2) directions), apply the 1-d version in each one, and return a point in the intersection of these intervals.  This is what the proposed method does.  \n\nWhat remains is to project to k dimensions so that the true inlier mean incurs at most eps error in this projection.  This is done iteratively somehow using the now-standard insight that the directions with most covariance contain both the true inlier mean, and any meaningfully biased set of outliers.  As such, the algorithm iteratively finds the top eigenvectors of the covariance matrix, and projects onto them -- reminiscent of Lai, Rao, Vempala 2016.  \nAlthough, some new ideas seem needed here -- especially ones that make use of the specific structure of the outlier distributions.  \n\nThere are numerous details to get this to work, and tighten the runtime.  The details are technical, and appear to be handled correctly, but do not seem to use wholesale new insights.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their effort and their positive assessment of our work. We respond to the comments below:\n\n* (**Comparison with Lai, Rao, and Vempala 2016**) As we discuss in detail in Appendix (lines 662–671), although Lai, Rao, and Vempala (2016) iteratively reduce the dimension using the centered second moment of the data, this approach can only achieve an error of order $\\alpha$, at best (in fact, their algorithm additionally incurs error with a logarithmic dependence in the dimension). Our dimension-reduction technique is fundamentally different, with the key innovation being the use of exponential reweighting for each sample. This mitigates the impact of outliers (in our model) and enables consistent estimation. Implementing this approach introduces additional challenges that must be addressed: (i) our dimension reduction method requires the space to have at least $1/\\epsilon^2$ dimensions (as opposed to just one dimension in Lai, Rao, and Vempala 2016); (ii) the parameter used in exponential reweighting influences both the centering applied in the computation of the centered second moment and the sample complexity. As explained in Section 1.2, the first attempt for setting this parameter correctly does not immediately allow for reduction all the way down to the desired level. Instead, our algorithm operates in two stages: the first stage performs the initial dimension reduction from the last sentence, and the second stage resets that parameter to a refined value that allows for further reduction.\n* (**Runtime**) As the reviewer points out, the runtime of $2^{O(1/\\epsilon^2)}$ is unavoidable, even in one dimension. This is because, even in the one-dimensional case, estimating the mean up to error $\\epsilon$ information-theoretically requires $2^{\\Omega(1/\\epsilon^2)}$ samples, as shown in Kotekal & Gao (2025). The key conceptual point of our paper is that, prior to our work, it was unknown whether the high-dimensional problem incurs a significantly higher runtime (e.g., $2^{\\Omega(d/\\epsilon^2)}$). We rule out this possibility by showing that runtime $poly(d)2^{\\Omega(1/\\epsilon^2)}$ is enough (i.e., the dependence on the dimension is polynomial instead of exponential). Notably, this implies that setting $\\epsilon = \\Theta(1/\\sqrt{\\log d})$ allows for error tending to zero as $d \\to \\infty$) within an overall $\\text{poly}(d)$ runtime. In contrast, every prior algorithm for the Huber model cannot achieve an error smaller than $\\Omega(\\alpha)$, which could be an absolute constant.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I followed the main arguments, and feel reasonable confident that they work.  But I did not verify all of the details.", "experimental_designs_or_analyses": "This is a theory paper, and not experiments are presented.  That is not a problem.", "relation_to_broader_scientific_literature": "The paper seems to have done a good job.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strength:  I think the arbitrary smaller error variant of this problem is interesting to study.  This paper makes a major advancement in that sense going from d=1 to high dimensions d.  \n\nWeakness:  the runtime of 2^O(1/eps^2) is quite large, and makes the ultimate result of less general relevance.  Albeit, recent prior work claims this is needed even in d=1.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "scxLrkPJKW", "reviewer": "Reviewer_GjRk", "summary": "The authors consider the problem of robust mean estimation of an identity covariance Gaussian in the presence of mean-shift contamination. They specifically give the first computationally efficient algorithm for high-dimensional robust mean estimation with mean-shift contamination. Their algorithm has near-optimal sample complexity, runs in sample-polynomial time, and approximates the target mean to any desired accuracy. It does so by using a data dependent dimension reduction technique which recovers a low-dimensional subspace on which μ has a large projection, and then running a low-dimensional robust estimator on that subspace.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and for their positive assessment of our work. Below, we provide a clarification in response to their comment.\n\nThe introductory proof sketch mentions that we can assume $\\lVert\\mu\\rVert = O(1)$ due to naive outlier removal. This means that even if $\\lVert\\mu\\rVert$ is arbitrary, we can preprocess the data to reduce it to the case where $\\lVert\\mu\\rVert = O(1)$; a step that is formally carried out in the subsequent sections containing the full proofs. The argument is quite simple: At the start of the algorithm (line 6 of Algorithm 1), we perform a preprocessing step to obtain a rough estimate $\\hat{\\mu}_0$ satisfying $\\lVert\\hat{\\mu}_0 - \\mu\\rVert = O(1)$. This can be achieved using any black-box outlier removal estimator designed for the Huber model from prior work. We then draw a new dataset and replace each point $x$ in that dataset by $x - \\hat{\\mu}_0$. This transformation effectively shifts the data distribution so that its true mean becomes $\\mu - \\hat{\\mu}_0$, which has norm $O(1)$. After the algorithm produces an $\\epsilon$-approximation $\\hat{\\mu}_1$ for this shifted mean, we simply add back $\\hat{\\mu}_0$ to $\\hat{\\mu}_1$, obtaining an $\\epsilon$-approximation of $\\mu$ (line 26 of Algorithm 1).", "claims_and_evidence": "The claims made in the submission supported by clear and convincing evidence", "methods_and_evaluation_criteria": "The proposed methods make sense for the problem or application at hand.", "theoretical_claims": "I checked the correctness of the claims in the main body and the full proof of Theorem 1.2 in the appendix, skipping all other technical claims in the appendix.", "experimental_designs_or_analyses": "There are no experimental designs in the paper.", "relation_to_broader_scientific_literature": "The paper formulates the first computationally algorithm for high-dimensional robust mean estimation that runs in time polynomial in the sample complexity.", "essential_references_not_discussed": "According to my knowledge, there are no essential works not currently cited in the paper.", "other_strengths_and_weaknesses": "The strength is the algorithm construction, which makes it run in sample polynomial time. The discussion on the algorithm construction is thorough, breaking it down to multiple intuitive steps.", "other_comments_or_suggestions": "In the paper, it is implicitly assumed that || \\mu || =O(1) while, n general, || \\mu || can be O(d). The authors should elaborate on why that is a reasonable assumption, and what happens to the algorithm in case this assumption doesn't hold.", "questions_for_authors": "I have no questions for the 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": "qXRNrqZfi8", "reviewer": "Reviewer_HXFc", "summary": "In this paper the authors look at the problem of robust mean estimation under the mean shift contamination. Here one receives samples from a standard d-variate Gaussian with mean m such that m is $\\mu$ with 2/3 probability and can be something else otherwise. The goal is to recover $\\mu$ up to an $\\epsilon$ error in L2 norm. Such a guarantee is information theoretically impossible under the Huber's contamination model. However, in this case one can use the fact that the contamination is not arbitrary but only a mean shift to solve the problem.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their effort and time in assessing our work. We respond to the points raised individually below:\n\n(**Experiments**) We would like to emphasize that our primary contribution is to characterize the computational-statistical landscape for this fundamental learning task—in terms of error guarantee, sample complexity, and runtime. That being said, our algorithm is already fairly simple and potentially practical, as it uses a dimension-reduction procedure with each step essentially being an SVD of a reweighted covariance matrix. Also, while it is easy to generate synthetic Gaussian data, it is not clear what distribution on errors should be considered, making the meaningfulness of experiments questionable.\n\n(**Novelty**) We would like to stress that our work develops a novel spectral dimension-reduction technique, rather than applying/adapting methods from prior work. To the best of our knowledge, there are two “spectral methods” proposed in prior work for robust mean estimation (in Huber’s model). Both of them are significantly different than our algorithm, as we discuss below:\n\n\n* (*Spectral filtering from Diakonikolas et. al (2016)*) This method consists of iteratively computing the top eigenvector of the empirical covariance and removing points whose projected deviation from the mean along that direction is higher than a carefully chosen threshold. This has the effect of removing more inliers than outliers until the dataset becomes so clean that the empirical mean is accurate. Importantly, this iterative filtering approach cannot yield consistent estimation (for the mean-shift model that we study), essentially because it does not take into account the additional structure of the outliers. \nThe algorithm we propose is fundamentally different. Rather than removing points based solely on the top eigenvector of the empirical covariance, our approach performs dimension reduction. It uses multiple eigenvectors of a reweighted covariance matrix as the subspace of the next iteration. In our method, each point is assigned an exponential weight, with carefully designed reweighting factors that are updated throughout the execution of the algorithm (see lines 126-144, second column and 175-186, first column for intuition on choosing the reweighting factor). Finally, once the problem’s dimension has been reduced sufficiently, we employ an inefficient estimator on the lower-dimensional data.\n \n\n\n* (*Dimension reduction from Lai et al. (2016)*) Although the goal in that technique is also to reduce the dimension, as we explain in lines 662-671 in Appendix A of the paper and in our response to Reviewer BKkQ, the similarities are only superficial. The method from Lai et al. (2016) uses the standard covariance matrix to identify the subspace for the next iteration. This method also fails to leverage the special nature of the outliers. In contrast, our method reweights the space with an exponential function that encodes our prior knowledge on the outliers in order to truncate their effect in the second moment matrix. Although one could broadly view this reweighting as a kind of “soft filtering”, this is fundamentally different from the filtering of the previous paragraph: there, points were removed based solely on their deviation along a single direction, where here the weight assigned to each point is based on the norm of the vector. Moreover, as we comment in lines 662-671 of the paper and in our response to Reviewer BKkQ, our dimension reduction comes with a number of technical obstacles that are due to the nature of our reweighting and need to be carefully addressed.\n\n(**Dependence on $\\alpha$**) Theorem 1.2 holds for any $\\alpha \\leq 0.49$. As we reply to Reviewer oS19, the most interesting parameter regime in our opinion  is when the fraction of outliers $\\alpha$ is a positive constant. Essentially,  this is the hardest setting for efficient estimation. In that regime, no sub-exponential time algorithm was known to achieve error lower than $\\Omega(1)$, while our algorithm can obtain arbitrarily small error in sample-polynomial time; and its sample complexity is information-theoretically near-optimal (as follows from the lower bound of Kotekal & Gao, 2025). As we show in Appendix F, the parameter $0.49$ in the condition of Theorem 1.2 can be replaced by any other absolute constant strictly smaller than $½$ (and the error will degrade by an absolute constant factor). Furthermore, if one prefers to use the reparameterization $\\alpha = ½ - c$, where $c$ is a parameter (rather than an absolute constant), the error degrades in a way that increases as $c$ approaches zero. We refer to the guarantee in Claim F.2 for the precise functional form of this dependence, which quantifies how the problem becomes more difficult as $\\alpha$ increases.", "claims_and_evidence": "The authors achieve a sample complexity of $poly(d,2^{\\epsilon^{-2}})$ and a time complexity of $poly(n,d)$ to solve this problem. \n\nThe claims look clear and convincing to me.", "methods_and_evaluation_criteria": "The authors give sound theoretical arguments to justify their paper", "theoretical_claims": "I haven't gone through the theoretical proofs given in the paper. But based on the overview given in 1.2 and the prior results on this topic, the results look correct to me.\n\nThe main idea is to find a direction where the mean has a large projection and once found it suffices to run an one-dimensional estimation along that direction. Along the way, the authors manage to address several technical hurdles, in particular, while obtaining the aforesaid direction.", "experimental_designs_or_analyses": "However, any experimental evaluation is missing. I thought experimental verification of the proposed algorithm would have added further value to the main claims of the paper.", "relation_to_broader_scientific_literature": "I think this particular spectral filtering algorithm and its variation has been extensively looked at numerous results in the last decade. This paper builds on this technique and one of the main contribution is finding out that this problem of mean estimation under mean-shift contamination where the aforesaid technique can be applied.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths: as mentioned before one of the main contribution is in finding out this problem where the recently proposed spectral techniques could be applied.\n\nWeakness: the main weakness I see that is the result looks incremental. As I said previously, this particular algorithm (spectral filtering algorithm) and its analysis have been investigated so many times in recent years. Also, lack of experimental evidence is another weakness of the paper given that it is easy to experiment with synthetic Gaussian data. This makes me less excited about the paper for a top ML venue such as ICML.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Where is the dependence on $\\alpha$ hiding in Theorem 1.2? I would guess the problem becomes harder as $\\alpha$ gets larger.", "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:

Meta-review: **Summary.**

The topic of this paper is robust mean estimation of a Gaussian distribution (multi-dimensional, with known covariance) when samples are contaminated in the sense where a (constant) proportion alpha comes from another Gaussian with (identical covariance matrix but) adversarially chosen mean (this is different from the more challenging Huber contamination model where the contamination distribution is arbitrary).

The main contribution is the design of an algorithm that: 

* Can approximate the mean to arbitrary accuracy.
* Is agnostic to the contamination parameter alpha.
* Has computational complexity that is polynomial in the dimension and the number of samples.
* Has sample complexity that is not significantly higher than in one dimension.

**Strengths.**

* What is interesting about this setting is that contrary to the Huber contamination model, it is here possible to reach an arbitrary error $\varepsilon$ (the question is intriguing).
* In high dimensions, the authors propose the first computationally efficient algorithms for the proposed contamination model (algorithmic novelty).
* New ideas were needed in their analysis (BKkQ) based on the structure of the outliers’ distribution (sufficient novelty in the proofs).

**Weaknesses.**

* The sample complexity is high (unavoidably so, refer to Kotekal & Gao (2025)) which undermines the practicality of the method.
* The lack of numerical experiments was pointed out (HXFc); although I do not consider this to be a strict requirement for a strong theory paper.

**Discussion and reviewer consensus.**

After the rebuttal and discussion, there is consensus among the reviewer that the paper should be accepted.

**Additional remarks.**

HXFc originally had an incrementality concern. However, it was dispelled by the author response.

**Overall recommendation.**

This is serious work; the authors make progress on a very fundamental problem in statistics. 
I don't think the lack of experiments should disqualify the paper. I recommend acceptance.
Decision: Accept (poster)